Lineare Schätzer II

Page 1

Lineare Schätzer I

Referat von Arno Schödl

im Seminar Klassifikation und Regression mit neuronalen Netzen im SoSe 97

Betreuer Dr. Klaus-Robert Müller

1 Der Bayessche Satz

Der Ansatz der Bayessche Entscheidungstheorie ist, daß wir Annahmen über den Zustand der

Wirklichkeit basierend auf Wahrscheinlichkeitsannahmen und unseren Beobachtungen von

Merkmalen der Wirklichkeit machen.

Nehmen wir also ein praktisches Beispiel: Wir stehen an einem Holzsägewerk, in dem

manchmal eine Esche und manchmal eine Birke zu Brettern zersägt wird. Wir beobachten

nun die Bretter, die aus dem Sägewerk kommen. Nachdem uns der Werksleiter eine Zeitlang

erklärt hat, welches Brett Esche und welches Birke ist, ist es nun an uns, das Holz des

nächsten Bretts zu bestimmen.

Nehmen wir an, wir können überhaupt keinen Unterschied zwischen Eschen- und

Birkenbrettern erkennen, ebensowenig gibt es eine Regelmäßigkeit in der Reihenfolge. Das

einzige, worauf wir unsere Entscheidung stützen können, ist die Anzahl an Birken- und

Eschenbrettern, die bisher aus dem Werk gekommen sind. Kamen bisher mehr Birkenbretter

als Eschenbretter aus dem Werk, so werden wir als vernünftige Menschen schätzen, daß das

Wir rechnen für jede Holzart den Posterior aus und entscheiden uns für den größten Posterior. nächste Brett auch ein Birkenbrett ist.

Der Nenner des Bayesschen Satzes hängt allerdings nur von der Beobachtung x ab und ist für

jede Holzart ωi gleich, daher ist bei gegebener Beobachtung unsere Entscheidung nur vom Formaler gesprochen, haben wir für die beiden Ereignisse, nennen wir das Ereignis

Eschenholz ω1 und das Ereignis Birkenholz ω2, je eine Wahrscheinlichkeit P(ω1) und P(ω2). Zähler abhängig.

Ist P(ω1)>P(ω2), entscheiden wir uns für ω1, sonst für ω2. Die Wahrscheinlichkeiten P(ω1),

Die gesamte Argumentation ist natürlich ohne weiteres auf mehr Zustände als zwei P(ω2) bezeichnet man als Prior, weil sie die Wahrscheinlichkeiten für das eine oder andere

übertragbar, im Bayesschen Satz oben ist bereits die Summe nicht über zwei, sondern Ereignis vor irgendeiner Beobachtung sind.

allgemein über N mögliche Zustände geschrieben. Beobachtet man mehrere Variablen statt

nur einer, kann man sie zu einem Vektor zusammenfassen und dann ebenso behandeln wie Was ist nun, wenn wir als Entscheidungsgrundlage die Helligkeit des Holzes gemessen

eine einzige Variable. Aus der Kurve der Wahrscheinlichkeitsdichte wird dabei natürlich bei haben? Wir haben außerdem durch lange Meßreihen mit dem Werksleiter herausgefunden,

einem zweidimensionalen Vektor eine Fläche oder eine Hyperfläche bei noch mehr welche Helligkeit Birken- bzw. Eschenholz haben. Da Helligkeit ja eine stetige Größe ist,

beobachteten Merkmalen. haben wir keine diskreten Wahrscheinlichkeiten ermittelt, sondern eine

Wahrscheinlichkeitsdichte, im folgenden immer mit einem kleinen p bezeichnet. Die

Wahrscheinlichkeitsvariable x soll die Helligkeit bezeichnen. p(x) bezeichnet dann die

Wahrscheinlichkeitsdichte für eine bestimmte Helligkeit x unabhängig vom Holz, p(x|ω1) ist

die bedingte Wahrscheinlichkeitsdichte, daß ein Brett aus Birkenholz die Helligkeit x hat. Die

Größen p(x|ωi) bezeichnet man als Likelihood.

Wie groß ist nun die Wahrscheinlichkeit, daß ein Brett Birke oder Esche ist, wenn wir seine

Helligkeit beobachtet haben und die Wahrscheinlichkeitsverteilungen p(x|ωi) kennen? Da wir

jetzt mehr Informationen über das individuelle Brett haben, sollte sich die Wahrscheinlichkeit

für die eine oder andere Holzart verändern. Gesucht ist offensichtlich die Wahrscheinlichkeit

für eine Holzart, gegeben eine Beobachtung, oder formal P(ωi|x). Das ist die neue

Wahrscheinlichkeit für eine Holzart nach der Beobachtung, daher bezeichnet man sie als

Posterior. Der Bayessche Satz rechnet mit Hilfe der gegebenen Größen genau diesen

Posterior aus:

Page 2

2 Entscheidung mit Kosten α ω − = = ) | ( ) ( bzw. ) | ( ) ( x R x g x P x g i i i i

Die Diskriminanten zerteilen den Merkmalsraum in Bereiche, die jeweils gleich klassifiziert Bisher haben wir versucht, möglichst wenig Fehler beim Erraten der Holzarten zu machen.

werden. An den Grenzen sind die Werte mindestens zweier Diskriminanten gleich, dann ist es Welche Fehler wir machen, war uns dabei egal, ebenso, ob wir eher Birken- oder eher

egal, für welche der beiden Klassen wir uns entscheiden. Eschenbretter richtig einordnen. Was ist nun, wenn wir für unterschiedliche Fehler

unterschiedlich bestraft werden, oder für richtige Klassifikationen unterschiedlich belohnt, Da es nur auf die Relationen zwischen Funktionswerten der Diskriminanten ankommt, kann

abhängig von der Art des Holzes? man jede streng monoton wachsende Funktion auf die Diskriminante anwenden, ohne die

Klassifikation zu verändern. Diese Funktion kann sogar von unserem Merkmalsvektor x Wir wollen den Ansatz allgemeiner fassen. Wir haben mehrere Zustände ωi. Einer davon ist

abhängen. Folgende Diskriminanten ergeben die gleiche Klassifikation: der wahre Zustand. Die Wahrscheinlichkeit, daß ein ωi wahr ist, basiert auf unserem

Merkmalsvektor x P(ωi|x). In unserem Beispiel war es unsere Aufgabe, diesen wirklichen

Zustand zu erraten. Man kann sich aber beliebige Aktionen α i vorstellen, für die wir uns

basierend auf unserer Analyse der Wirklichkeit per Bayesschem Satz entscheiden können.

Wir kennen eine Kosten- oder Bestrafungsfunktion λij, die die Kosten angibt, wenn im

Zustand der Wirklichkeit ωj die Aktion αi ausgeführt wird. λij könnte natürlich ebenso gut

eine Belohnungsfunktion sein, aber Informatiker minimieren eben gern. In unserem Beispiel

haben wir zwei verschiedene Wirklichkeiten, Eschenholz oder Birkenholz, und zwei

verschiedene Aktionen, nämlich die, zu behaupten, es sei Eschenholz (α1), oder die, zu

behaupten, es sei Birkenholz (α2). Die Kosten für die richtige Wahl könnte man z. B. mit 0

annehmen, also λ11=0 und λ22=0, die Kosten für die falsche Wahl jeweils mit 1, also λ12=1

und λ21=1. Interessant ist nun der Fall, wenn diese Kosten nicht paarweise gleich sind.

Um auch in diesem Fall die optimale Entscheidung zu treffen, müssen wir für jede Aktion αi

anhand der Beobachtung x das Risiko der Aktion αi R(αi|x) ausrechnen, das ist die nach den

Wahrscheinlichkeiten des Auftretens einer Wirklichkeit P(ωj|x) gewichtete Summe über die

bei dieser Wirklichkeit eintretenden Kosten λij bei Auswahl der Aktion αi:

N ∑ λ ω α ⋅ = ) | ( ) | ( x P x R Eine Entscheidungsgrenze bei zweidimensionalem Merkmalsvektor ij i i

= 1 j

Die Aktion mit minimalem Risiko ist die Aktion unserer Wahl. Das Risiko dieser Aktion wird

Bayes-Risiko genannt.

3 Diskriminanten und Entscheidungsgrenzen

Egal, ob wir unsere Entscheidung von dem Posterior P(ωi|x) oder von dem Risiko R(αi|x)

Die letzte Schreibweise für die Diskriminante werden wir im folgenden verwenden, weil sie abhängig machen, in beiden Fällen haben wir eine Funktionenschar, die von unserem

es erlaubt, Likelihood und Prior getrennt zu betrachten. Merkmalsvektor x auf eine reelle Zahl abbildet. Für ein gegebenes x entscheiden wir uns dann

für die Klasse, in unserem Fall Zustandsvorhersage oder Aktion, für die die entsprechende

Funktion im Falle der Kosten minimal bzw. im Falle der Wahrscheinlichkeit maximal ist.

Eine allgemeine Form, solche Klassifikationsprobleme darzustellen, sind Diskriminanten.

Für jede mögliche Wahl j ist eine Diskriminante gj(x) gegeben, wir entscheiden uns für die

Klasse i, für die gilt

≥ ∀ ) ( ) ( x g x g j j i

Unsere beiden Entscheidungsgrundlagen Posterior und Risiko sind trivial als Diskriminanten

darstellbar:

Page 3

Wahrscheinlichkeitsdichte p(x|θ) angeben, die die Verteilung des vom Modell mit den

Σ ist die Kovarianzmatrix der Daten: Parametern θ erzeugten Daten x angibt. Nehmen wir nun an, das Modell mit Parametern θ

hätte als unabhängige Sequenz hintereinander unsere Trainingsmenge erzeugt, erst den ersten

T ∫ µ µ − − = Σ x d x x x p ) )( )( ( ) ( Wert x1, dann x2 und so fort bis zum letzten Datum xN. Die Wahrscheinlichkeitsdichte dafür, ij j i j i die sogenannte Likelihood der Daten, ist

oder in Matrizenschreibweise

∫ = Σ p (

Nun erscheint es vernünftig, den Parametersatz als Modell für die Daten anzunehmen, für den Wiederum ist der Punkt, wo die Daten am dichtesten liegen, gleichzeitig der Schwerpunkt der

die Wahrscheinlichkeit, daß er die Daten als eine Sequenz erzeugt, am höchsten ist. Dieses Daten µ. Die Form und Orientierung der Datenwolke gibt die Kovarianzmatrix an. Die

Verfahren wird Maximum Likelihood genannt. Für die meisten Datenmodelle muß der Hauptachsen der Verteilung sind die Eigenvektoren der Kovarianzmatrix. Die Varianz

Parametersatz mit maximaler Likelihood durch Ableiten der Likelihood und dann iterativ per entlang der Hauptachsen sind die dazugehörigen Eigenwerte.

Gradientenaufstieg in der Parameterlandschaft gefunden werden. Im Falle der

Normalverteilung ist eine analytische Lösung möglich. Die Herleitung ist hier nicht

angegeben. Die Parameter µ ˆ und Σ ˆ werden mit diesem Verfahren geschätzt als 4.2 Herleitung der Parameter µ und Σ aus Trainingsdaten

Wenn wir eine Menge X={x1...xN} von Trainingsvektoren gegeben haben, für die wir eine

Normalverteilung annehmen, ist die Herleitung der beiden Parameter Mittelwert und

Kovarianzmatrix wünschenswert.

Hat man sich für ein Modell der Datenverteilung entschieden, in unserem Fall für die

Normalverteilung, kann man die Parameter des Modells, hier als Vektor θ geschrieben, mit

dem Verfahren der Maximum Likelihood bestimmen.

Page 4

Der Mittelwert der Normalverteilung wird einfach angenommen als der Mittelwert der

Trainingsdaten, ebenso wird die Kovarianzmatrix der Normalverteilung angenommen als die

Kovarianzmatrix der Daten.

Diese Schätzungen scheinen intuitiv einwandfrei zu sein. Sie sind auch die anhand der Daten

bestmöglichen Schätzungen. Jedoch ist der Mittelwert natürlich fehlerbehaftet, weil nur eine

endliche Zahl von Trainingsbeispielen vorgegeben wird. Ebenso ist die Varianz der Daten

nicht korrekt, weil sie zum einen wieder von der endlichen Zahl von Trainingsdaten, zum

anderen aber auch von dem bereits fehlerbehafteten Mittelwert abhängt. Dieser Fehler wird

sehr augenfällig bei nur einelementiger Trainingsmenge. Der Mittelwert liegt dann irgendwo

in der Datenwolke, und die Varianz wird zu Null.

5 Die Diskriminante der Normalverteilung

Im folgenden werden wir die Entscheidungsbereiche für den Spezialfall betrachten, daß die

beobachteten Merkmale für eine Klasse normalverteilt sind. Wenn wir eine Klassifizierung

anhand des Posteriors durchführen, können wir die oben aufgeführte Diskriminante

ω ω + = P x p x g ) ( ln ) | ( ln ) ( i i i

5.1 Fall Σ i =σ 2 1

verwenden. Setzen wir nun als Likelihood p(x|ωi) eine mehrdimensionale Normalverteilung

ein, wird unsere Diskriminante zu Sind alle Kovarianzmatrizen das gleiche Vielfache der Einheitsmatrix, so haben alle

g i

−

unabhängig von i. Dieser Term kann daher auch entfallen. Daraus ergeben sich die 2

Vereinfachungen:

− = x g ) ( i

− =

Im folgenden werden zwei Spezialfälle angegeben, die vereinfachende Annahmen über die gi(x) ist nun in x linear, d. h. g(x) läßt sich darstellen als

Kovarianzmatrix machen und damit eine im Merkmalsvektor x lineare Diskriminante

T + = ermöglichen. Als drittes folgt der allgemeine Fall, der zu einer quadratischen Diskriminante w x w x g ) ( 0 i i i führt.

Die Grenze zwischen zwei Clustern i und j ist bei linearer Form der Diskriminante immer

eine Hyperebene. Um die Punkt-Normalenform dieser Ebene herzuleiten, setzen wir zur

Bestimmung der Grenze gi(x)= gj(x):

Page 5

5.3 Fall Σ i beliebig Schreibt man für den betrachteten Spezialfall die Grenze als

w T 0 = − x
) (

x so ist

ordnen nach den Potenzen von x:

w

Die Diskriminante ist in diesem Fall inhärent quadratisch. Als Entscheidungsgrenzen

Die Normale der Ebene ist die Verbindungsachse zwischen den beiden Clusterzentren. Sind kommen alle möglichen quadratische Formen vor. Das folgende Bild zeigt einige mögliche beide Clusterzentren gleich wahrscheinlich, so liegt die Trennung genau auf halbem Weg Grenzen:

zwischen den Zentren, ist ein Cluster wahrscheinlicher, so verschiebt sich die Trennung von

ihm weg.

Page 6

6 Diskrete Merkmale

6.1 Einführung

Bisher waren unsere Merkmale stetig, wie im Falle der Helligkeit des Holzes. Wir gehen nun Wieder ergibt sich eine lineare Diskriminante. Man kann sich die Menge der möglichen

über auf diskrete Merkmale und betrachten im Anschluß binäre Merkmale. Im Fall von Merkmalsvektoren x, deren Elemente die diskreten Werte xi = {0,1} annehmen können, als

die Ecken eines Hyperwürfels vorstellen. Durch diesen Hyperwürfel läuft eine Ebene, die die diskreten Merkmalen ist keine Wahrscheinlichkeitsdichte p(x|ωi) gegeben, sondern eine

Ecken des Würfels zwischen den beiden Clustern aufteilt. bestimmte Wahrscheinlichkeit P(x|ωi) für jeden einzelnen Wert des Merkmals. Der

Bayessche Satz sieht jetzt so aus:

ω ω P x P ) ( ) | ( i i ω = 7 Perzeptrone und lineare Separabilität x P ) | ( i N ∑ ω ω P x P ) ( ) | ( j j

= 1 j Um die Aktivierungsgrenze zwischen zwei Clustern zu finden, haben wir bisher immer

= − ⇔ = Die Definition des Risikos R(αi|x) bleibt unverändert, ebenso die Entscheidungskriterien, die 0 ) ( ) ( ) ( ) ( x g x g x g x g j i j i

wir bisher entwickelt haben.

gesetzt. Sind gi(x) und gj(x) jeweils lineare Funktionen wie im Fall der Normalverteilung mit

vereinfachenden Annahmen oder bei unabhängigen binären Merkmalsvektoren mit

6.2 Unabhängige binäre Merkmale T T + = + = ) ( w x w x g und ) ( w x w x g , 0 0 j j i i j i

Für den Fall binärer statistisch unabhängiger Merkmalsvektoren folgt nun eine Betrachtung

so beschreibt der Diskriminante.

T Nehmen wir an, die Elemente des Merkmalsvektors x können nur die Werte xi=1 oder xi=0 − + − = ) ( 0 w w x w w 0 0 j i j i annehmen. Die Likelihood im binären Fall ist vollständig beschrieben durch einen einzige

Wahrscheinlichkeit pro Merkmal k und Klasse l, z. B. P(xk=1|ωl), im folgenden geschrieben die Clustergrenze. Ein McCulloch-Pitts-Perzeptron mit der logistischen Ausgabefunktion

als Pkl. Es gilt dann natürlich P(xk=0|ωl)=1- Pkl. Die Wahrscheinlichkeit P(xk|ωl) kann man

dann schreiben als T θ − = ) sgn( ) ( , x w x y

− 1 x x ϖ − ⋅ = k k P P x P ) 1 ( ) | ( . mit dem Gewichtsvektor w = wi - wj und der Schwelle θ = wj0 - wi0 der Eingabe x leistet genau kl kl l k

die Trennung zwischen Cluster i und Cluster j. Es feuert genau dann, wenn x zu Cluster i

Dieser Ausdruck mutet zunächst etwas merkwürdig an, nimmt aber für xk=1 den Wert Pkl und gehört. McCulloch-Pitts-Perzeptrone können genau solche Klassifizierungsprobleme lösen,

für xk=0 den Wert 1-Pkl an. die linear separabel sind, wo also eine Trennebene im Merkmalsraum existiert.

Bei statistisch unkorrelierten Einzelmerkmalen ist die Wahrscheinlichkeit für den gesamten d- Literatur

dimensionalen Merkmalsvektor x dann

Bishop, C.M. (1995), Neural networks for pattern recognition, Oxford University Press

d (Kapitel 1, 2.1-2.8, 3.1-3.4) − ∏ 1 x x ( ϖ − ⋅ = k k P P x P ) 1 ( ) | . kl kl l

= Duda, R.O, Hart, P.E. (1973), Pattern classification and scene analysis, Wiley (Kapitel 1, 2) 1 l

Einsetzen in die Diskriminante

ϖ ϖ + = ) ( ln ) | ( ln ) ( P x p x g l l l

ergibt