Wie berechnet man Fisher-Kriterium-Gewichte?

12

Ich studiere Mustererkennung und maschinelles Lernen und bin auf die folgende Frage gestoßen.

Betrachten Sie ein Zweiklassen-Klassifizierungsproblem mit gleicher Wahrscheinlichkeit für die vorherige Klasse

P(D1)=P(D2)=12

und die Verteilung der Instanzen in den einzelnen Klassen von

p(x|D1)=N([00],[2001]),

p(x|D2)=N([44],[1001]).

Wie berechnet man Fisher-Kriterium-Gewichte?

Update 2: Das berechnete Gewicht in meinem Buch ist: W=[4329].

Update 3: Wie von @xeon angedeutet, sollte ich die Projektionslinie für die Fisher-Diskriminante bestimmen.

Update 4: Sei die Richtung der Projektionslinie, dann stellt die lineare Diskriminanzmethode von Fisher fest, dass das beste W dasjenige ist, für das die Kriteriumsfunktion maximiert ist. Die verbleibende Herausforderung besteht darin, wie wir den numerischen W- Vektor erhalten können.WWW

Dr. Hoshang
quelle
Ihre erste Distribution ist undefiniert. Insbesondere hat die zweite Variante des Paares eine entartete Verteilung mit der Varianz 0, hat jedoch eine positive Kovarianz mit der ersten Variante, was unmöglich ist.
Owensmartin
@owensmartin Hast du eine Idee, wie diese Werte berechnet werden?
Dr. Hoshang
Wie ist das Fisher-Kriterium Gewicht definiert?
Vladislavs Dovgalecs
Ich meine, die lineare Diskriminanz von Fisher ist durch den Vektor w gegeben, der maximiert ... sie ist auf jedem Material vermerkt, wie beispielsweise luthuli.cs.uiuc.edu/~daf/courses/Learning/Kernelpapers/ . 2. Ist es okey @xeon?
Dr. Hoshang
Hinweis: Was ist die Grenze zwischen den beiden Klassen? Linear, Polynom, noch etwas?
Vladislavs Dovgalecs

Antworten:

11

Nach dem Papier , das Sie verknüpfen (Mika et al., 1999) , müssen wir finden die der maximiert den so genannten generali Rayleighquotienten ,w

wSBwwSWw,

wo für bedeutet und covariances C 1 , C 2 ,m1,m2C1,C2

SB=(m1m2)(m1m2),SW=C1+C2.

Die Lösung kann durch Lösen des verallgemeinerten Eigenwertproblems indem zuerst die Eigenwerte λ durch Lösen von det ( S B - λ S W ) = 0 berechnet und dann nach dem Eigenvektor w gelöst werden . In Ihrem Fall S B - λ S W = ( 16 - 3 λ 16 16 16 - 2 λ ) .

SBw=λSWw,
λ
det(SBλSW)=0
w
SBλSW=(163λ1616162λ).
Die Determinante dieser 2x2-Matrix kann von Hand berechnet werden.

Der Eigenvektor mit dem größten Eigenwert maximiert den Rayleigh-Quotienten. Anstatt die Berechnungen von Hand durchzuführen , löste ich das verallgemeinerte Eigenwertproblem in Python mit scipy.linalg.eigund erhielt was sich von der Lösung unterscheidet, die Sie in Ihrem Buch gefunden haben. Unten habe ich die optimale Hyperebene des gefundenen Gewichtsvektors (schwarz) und die Hyerebene des in Ihrem Buch gefundenen Gewichtsvektors (rot) aufgetragen.

w10.5547,w20.8321,

enter image description here

Lucas
quelle
1
Dieses Beispiel ist sehr interessant. Die beiden Linien trennen die beiden Klassen, aber eine davon ist aus lerntheoretischer Sicht "besser".
Vladislavs Dovgalecs
2
Das Fisher-Kriterium wird in Abschnitt 5-2-3 auf books.google.com/…
nini am
1
@Lucas Vielleicht liegt das fragliche Ergebnis in der Nähe von xeon-Kommentaren: "Vielleicht sollten wir den Einheitsvektor w melden, da die Hyperebene durch die Richtung und nicht durch die Größe definiert ist."
Nini
1
Oh !!! herausfordernde Frage, ich empfehle allen, Seite 2 auf dml.ir/wp-content/uploads/2012/04/SPR-S12-M-Sol.pdf zu sehen
user153695
1
@ Lucas Danke. Würden Sie bitte ein weiteres Bild für W = [- 2/3 -2/3] und W = [- 4/3 -2/3] und W = [- 2 -3] mit drei verschiedenen Farben hinzufügen, um die Grenze zu sehen? Vielen Dank. Ich setze dir ein Kopfgeld für eine nette Antwort.
Nini
7

SOLUTION1:

Nach Duda et al. (Musterklassifizierung), die eine alternative Lösung zu @lucas bietet und in diesem Fall eine sehr einfach zu berechnende Lösung von Hand darstellt. (Hoffe, diese alternative Lösung hilft !! :))

In zwei Klassen LDA ist das Ziel:

wTSBwwTSWw

SB=(m1m2)(m1m2)TSW=S1+S2S1,S2m1,m2

Die Lösung dieses verallgemeinerten Raleigh-Quotienten ist ein verallgemeinertes Eigenwertproblem.

SBw=λSWwSW1SBw=λw

SBm1m2wSW1(m1m2)

w

SW1(m1m2)=(S1+S2)1(m1m2)=([2001]+[1001])1([00][44])=([1/3001/2])([00][44])=[1.33332.0000][0.55470.8321]

Ref: Pattern Classification von Duda, Hart, Stork

SOLUTION2:

SBw=λSWw

determinant(SBλSW)SBw=λSWwλ1,λ2,...,λn,λ=λi,i{1,2,..,n}SBwi=λiSWwi{wi}i=1n

determinant(SBλSW)=[163λ1616162λ]=6λ280λ, So eigen values are roots to polynomial 6λ280λ.

So λ= 0 and 40/3 are the two solutions. For LDA, eigen vector corresponding to highest eigen value is the solution.

Solution to system of equation (SBλiSW)wi=0 and λi=40/3

which turns out to be [163λ1616162λ]wi[72484832]wi=0

Solution to the above system of equation is [0.55470.8321][0.55470.8321] which is same as previous solution.

Alternatively, we can say that [0.55470.8321] lies in the null space of [72484832].

For two class LDA, eigen vector with highest eigen value is the solution. In general, for C class LDA, the first C - 1 eigen vectors to highest C - 1 eigen values constitute the solution.

This video explains how to compute eigen vectors for simple eigen value problem. ( https://www.khanacademy.org/math/linear-algebra/alternate_bases/eigen_everything/v/linear-algebra-finding-eigenvectors-and-eigenspaces-example )

Following is an example. http://www.sosmath.com/matrix/eigen2/eigen2.html

Multi-class LDA: http://en.wikipedia.org/wiki/Linear_discriminant_analysis#Multiclass_LDA

Calculating Null Space of a matrix: https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/null_column_space/v/null-space-2-calculating-the-null-space-of-a-matrix

dksahuji
quelle
1
Nice answer, you means answer of book is wrong!! Okey?
Dr. Hoshang
I believe that this answer is correct and if your book defines SW and SB differently then see what you get with those definitions.
dksahuji
2
-1.33 is equal to -4/3 but the second element is differ. Maybe book report unit vector w? Isn't right? Thanks so much
Dr. Hoshang
2
please complete solution 2 to reach value of W to bounty it
nini
1
@Dr.Hoshang: The solution in your book is wrong. I have no idea why.
amoeba says Reinstate Monica