Lineare Schätzer II

) 2 ( ) 1 (

2 Entscheidung mit Kosten

g

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:

α

| (

R

i

=

1

j

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

ω ω

) ( ) | (

P x p

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)

abhängig machen, in beiden Fällen haben wir eine Funktionenschar, die von unserem

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

∀

(

g j

i

Unsere beiden Entscheidungsgrundlagen Posterior und Risiko sind trivial als Diskriminanten

darstellbar:

∫

j i

die sogenannte Likelihood der Daten, ist

oder in Matrizenschreibweise

N

∫

= Σ

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

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

N 1

=

n

dem Verfahren der Maximum Likelihood bestimmen.

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

g

i

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

ein, wird unsere Diskriminante zu

g

i

π

−

2 ln ist nur eine additive Konstante und kann deshalb entfallen, d. h. es bleibt

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

2

Vereinfachungen:

1

−

1

T

ω µ µ

+ − Σ − − Σ − =

1 P x x x g

) ( ln ) ( ) ( | | ln ) (

i

− =

Im folgenden werden zwei Spezialfälle angegeben, die vereinfachende Annahmen über die

Kovarianzmatrix machen und damit eine im Merkmalsvektor x lineare Diskriminante

ermöglichen. Als drittes folgt der allgemeine Fall, der zu einer quadratischen Diskriminante

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):

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

w T 0 = − x

so ist

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.

6 Diskrete Merkmale

g l

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

Die Definition des Risikos R(αi|x) bleibt unverändert, ebenso die Entscheidungskriterien, die

wir bisher entwickelt haben.

6.2 Unabhängige binäre Merkmale

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

so beschreibt

der Diskriminante.

Nehmen wir an, die Elemente des Merkmalsvektors x können nur die Werte xi=1 oder xi=0

=

0

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

1

x

ϖ

− ⋅ = k

P P x P ) 1 ( ) | ( kl kl l k

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 ) ( x p x g l

ergibt