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
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.