Kernel Fisher diskriminant analys

I statistik är kärn Fisher diskriminantanalys (KFD) , även känd som generaliserad diskriminantanalys och kärndiskriminantanalys , en kärnbaserad version av linjär diskriminantanalys ( LDA). Den är uppkallad efter Ronald Fisher .

Linjär diskriminantanalys

Intuitivt är tanken med LDA att hitta en projektion där klassseparationen är maximerad. Givet två uppsättningar märkta data, $\mathbf {C} _{1}$ och $\mathbf {C} _{2}$ , kan vi beräkna medelvärdet för varje klass, $\mathbf {m} _{1}$ och $\mathbf {m} _{2}$ , som

$\mathbf {m} _{i}={\frac {1}{l_{i}}}\sum _{n=1} ^{l_{i}}\mathbf {x} _{n}^{i},$

där $l_{i}$ är antalet exempel på klass $\mathbf {C} _{i}$ . Målet med linjär diskriminantanalys är att ge en stor separation av klassmedlen samtidigt som variansen i klassen hålls liten. Detta är formulerat som att maximera, med avseende på $\mathbf {w}$ , följande förhållande:

$J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }},$

där $\mathbf {S} _{B}$ är kovariansmatrisen mellan klassen och $\mathbf {S} _{W}$ är den totala kovariansmatrisen inom klassen:

${\begin{aligned}\mathbf {S} _{B}&=(\mathbf {m} _{2}-\mathbf {m} _{1})(\mathbf {m} _{2 }-\mathbf {m} _{1})^{\text{T}}\\\mathbf {S} _{W}&=\summa _{i=1,2}\summa _{n=1 }^{l_{i}}(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})^{\text{T}}.\end{aligned}}$

Det maximala förhållandet ovan uppnås vid

$\mathbf {w} \propto \mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).$

som kan visas med Lagrange multiplikatormetoden (skiss av bevis):

Maximerar ${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }}} motsvarar att$ maximera

$\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w}$

föremål för

$\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} =1.$

Detta är i sin tur ekvivalent med att maximera $I(\mathbf {w} ,\lambda )=\mathbf { w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} -\lambda (\mathbf {w} ^{\text{T}}\mathbf {S} _{W} \mathbf {w} -1)$ , där $\lambda$ är Lagrange-multiplikatorn.

måste derivatorna av $I(\mathbf {w} ,\lambda )$ med avseende på $\mathbf {w}$ och $\lambda$ vara noll. Att ta ${\frac {dI}{d\mathbf {w} }}=\mathbf {0}$ ger

$\mathbf {S} _{B}\mathbf {w} -\lambda \mathbf {S} _{W}\mathbf {w} =\mathbf {0} ,$

vilket är trivialt tillfredsställt av $\mathbf {w} =c\mathbf {S} _{W}^{-1}(\mathbf {m} _ {2}-\mathbf {m} _{1})$ och $\lambda =(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\mathbf {S} _{W}^{-1}( \mathbf {m} _{2}-\mathbf {m} _{1}).$

Förlänger LDA

För att utöka LDA till icke-linjära mappningar kan data, angivna som $\ell$ punkterna $\mathbf {x} _{i},$ mappas till ett nytt funktionsutrymme, $F,$ via någon funktion $\phi .$ I detta nya funktionsutrymme är funktionen som behöver maximeras

$J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf { S} _{B}^{\phi }\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }},$

var

${\begin{aligned}\mathbf {S} _{B}^{\phi }&=\left(\mathbf {m} _{ 2}^{\phi}-\mathbf {m} _{1}^{\phi}\right)\left(\mathbf {m} _{2}^{\phi}-\mathbf {m} _{ 1}^{\phi }\right)^{\text{T}}\\\mathbf {S} _{W}^{\phi}&=\summa _{i=1,2}\summa _{ n=1}^{l_{i}}\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)\ vänster(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)^{\text{T}},\end{justerad }}$

och

$\mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\summa _{j=1}^{l_{i}}\phi (\ mathbf {x} _{j}^{i}).$

Observera vidare att $\mathbf {w} \in F$ . Att explicit beräkna mappningarna $\phi (\mathbf {x} _{i})$ och sedan utföra LDA kan vara beräkningsmässigt dyrt och i många fall svåröverskådligt. Till exempel $F$ vara oändligt dimensionell. Således, snarare än att explicit mappa data till $F$ , kan data implicit bäddas in genom att skriva om algoritmen i termer av punktprodukter och använda kärnfunktioner där punktprodukten i det nya funktionsutrymmet ersätts av en kärna funktion, $k(\mathbf {x} ,\mathbf {y} )=\phi (\mathbf {x} )\cdot \phi ( \mathbf {y} )$ .

LDA kan omformuleras i termer av punktprodukter genom att först notera att $\mathbf {w}$ kommer att ha en expansion av formen

$\mathbf {w} =\sum _{i=1}^{l}\alpha _{i}\phi (\mathbf {x} _{i}).$

Notera det då

$\mathbf {w} ^{\text{ T}}\mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\summa _{j=1}^{l}\summa _{k=1 }^{l_{i}}\alpha _{j}k\left(\mathbf {x} _{j},\mathbf {x} _{k}^{i}\right)=\mathbf {\alpha } ^{\text{T}}\mathbf {M} _{i},$

var

$(\mathbf {M} _{i})_{j}={\frac {1}{l_{i}}}\summa _{k=1}^{l_{i}}k(\ mathbf {x} _{j},\mathbf {x} _{k}^{i}).$

Täljaren för $J(\mathbf {w} )$ kan sedan skrivas som:

$\mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} =\mathbf {w} ^{\text{T}}\ vänster(\mathbf {m} _{2}^{\phi}-\mathbf {m} _{1}^{\phi}\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\mathbf {w} =\mathbf {\alpha} ^{\text{T}}\mathbf { M} \mathbf {\alpha } ,\qquad {\text{där}}\qquad \mathbf {M} =(\mathbf {M} _{2}-\mathbf {M} _{1})(\mathbf {M} _{2}-\mathbf {M} _{1})^{\text{T}}.$

På liknande sätt kan nämnaren skrivas som

$\mathbf {w} ^{\text{T}} \mathbf {S} _{W}^{\phi}\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } ,\qquad {\ text{där}}\qquad \mathbf {N} =\sum _{j=1,2}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j} })\mathbf {K} _{j}^{\text{T}},$

med den ${\displaystyle n^{\text{th}},m^{\text{th}}}-$ komponenten av $\mathbf {K} _{j}$ definierad som ${\displaystyle k(\mathbf {x} _{n},\mathbf {x} _{m}^{j}),\mathbf {I} } är$ identitetsmatrisen , och $\mathbf {1} _{l_{j}}$ matrisen med alla poster lika med $1/l_{j}$ . Denna identitet kan härledas genom att börja med uttrycket för $\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w}$ och med expansionen av $\mathbf {w}$ och definitionerna av $\mathbf {S} _{W}^{\phi }$ och ${\ displaystyle \mathbf {m} _{i}^{\phi }}$

${\begin{aligned}\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} &=\left(\sum _{ i=1}^{l}\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\right)\left(\summa _{j=1,2 }\summa _{n=1}^{l_{j}}\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}} \right)\left(\summa _{k=1}^{l}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\summa _{j= 1,2}\summa _{i=1}^{l}\summa _{n=1}^{l_{j}}\summa _{k=1}^{l}\left(\alpha _{ i}\phi ^{\text{T}}(\mathbf {x} _{i})\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _ {j}^{\phi}\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi}\right)^ {\text{T}}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\summa _{j=1,2}\summa _{i=1 }^{l}\summa _{n=1}^{l_{j}}\summa _{k=1}^{l}\left(\alpha _{i}k(\mathbf {x} _{ i},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\summa _{p=1}^{l_{j}}\alpha _{ i}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})\höger)\left(\alpha _{k}k(\mathbf {x} _{k },\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\summa _{q=1}^{l_{j}}\alpha _{k }k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\\&=\summa _{j=1,2}\left(\summa _ {i=1}^{l}\summa _{n=1}^{l_{j}}\summa _{k=1}^{l}\left(\alpha _{i}\alpha _{k }k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{ j})-{\frac {2\alpha _{i}\alpha _{k}}{l_{j}}}\summa _{p=1}^{l_{j}}k(\mathbf {x } _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})+{\frac {\alpha _{i}\alpha _{k}}{l_{j}^{2}}}\summa _{p=1}^{l_{j}}\summa _{q=1}^{ l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})k(\mathbf {x} _{k},\mathbf {x} _{ q}^{j})\right)\right)\\&=\summa _{j=1,2}\left(\summa _{i=1}^{l}\summa _{n=1} ^{l_{j}}\summa _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x } _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {\alpha _{i}\alpha _ {k}}{l_{j}}}\summa _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j })k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})\right)\right)\\[6pt]&=\summa _{j=1,2 }\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } -\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {1} _{l_{j}}\mathbf {K} _{j}^{\text{T}} \mathbf {\alpha } \\[4pt]&=\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } .\end{aligned}}$

Med dessa ekvationer för täljaren och nämnaren för ${\displaystyle J(\mathbf {w} )} , kan$ ekvationen för $J$ skrivas om som

$J(\mathbf {\alpha } )={\frac {\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } }{\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } }}.$

Då ger differentiering och inställning lika med noll

$(\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } )\mathbf {N} \mathbf {\alpha } =(\mathbf {\alpha } ^ {\text{T}}\mathbf {N} \mathbf {\alpha } )\mathbf {M} \mathbf {\alpha } .$

Eftersom endast riktningen för $\mathbf {w}$ , och därmed riktningen för $\mathbf {\alpha } ,$ spelar roll, kan ovanstående lösas för $\mathbf {\ alfa }$ som

$\mathbf {\alpha } =\mathbf {N} ^{-1}(\mathbf {M} _{2}-\mathbf {M} _{1}).$

Observera att i praktiken är $\mathbf {N}$ vanligtvis singular och därför läggs en multipel av identiteten till den

$\mathbf {N} _{\epsilon }=\mathbf {N} +\epsilon \mathbf {I} .$

Givet lösningen för $\mathbf {\alpha }$ ges projektionen av en ny datapunkt av

$y(\mathbf {x} )=(\mathbf {w} \cdot \phi (\mathbf {x} ))=\summa _{i=1}^{l}\alpha _{i}k (\mathbf {x} _{i},\mathbf {x} ).$

Flerklassig KFD

Utvidgningen till fall där det finns fler än två klasser är relativt okomplicerad. Låt $c$ vara antalet klasser. Sedan involverar flerklass-KFD att projicera data till ett $(c-1)$ -dimensionellt utrymme med användning av $(c-1)$ diskriminantfunktioner

$y_{i}=\mathbf {w} _{i}^{\text{T}}\phi (\mathbf {x} )\qquad i=1,\ldots ,c-1.$

Detta kan skrivas i matrisnotation

$\mathbf {y} =\mathbf {W} ^{\text{T}}\phi (\mathbf {x} ),$

där $\mathbf {w} _{i}$ är kolumnerna i $\mathbf {W}$ . Vidare är kovariansmatrisen mellan klasser nu

$\mathbf {S} _{B}^{\phi }=\summa _ {i=1}^{c}l_{i}(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })(\mathbf {m} _{i} ^{\phi }-\mathbf {m} ^{\phi })^{\text{T}},$

där $\mathbf {m} ^{\phi }$ är medelvärdet av all data i det nya objektutrymmet. Kovariansmatrisen inom klassen är

$\mathbf {S} _ {W}^{\phi }=\summa _{i=1}^{c}\summa _{n=1}^{l_{i}}(\phi (\mathbf {x} _{n}^ {i})-\mathbf {m} _{i}^{\phi })(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{ \phi })^{\text{T}},$

Lösningen erhålls nu genom att maximera

$J(\mathbf {W} )={\frac {\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {W } \right|}{\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {W} \right|}}.$

Kärntricket kan återigen användas och målet med multi-class KFD blir

$\mathbf {A} ^{*}={\underset {\mathbf {A} }{\operatörsnamn {argmax} }}={\frac {\left|\mathbf {A} ^{\text{ T}}\mathbf {M} \mathbf {A} \right|}{\left|\mathbf {A} ^{\text{T}}\mathbf {N} \mathbf {A} \right|}},$

där $A=[\mathbf {\alpha } _{1},\ldots ,\mathbf {\alpha } _{c-1}]$ och

${\begin{aligned}M&=\sum _{j=1}^{c}l_{j}(\mathbf {M} _{j}-\mathbf {M} _{*})(\ mathbf {M} _{j}-\mathbf {M} _{*})^{\text{T}}\\N&=\summa _{j=1}^{c}\mathbf {K} _{ j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}}.\end{aligned}}$

M $\mathbf {M} _{i}$ definieras som i avsnittet ovan och $\displaystyle \mathbf {M} _{*}}$ definieras som

$(\mathbf {M} _{*})_{j}={\frac {1}{l}}\summa _{k=1}^{l}k(\mathbf {x} _{ j},\mathbf {x} _{k}).$

$\mathbf {A} ^{*}$ kan sedan beräknas genom att hitta de $(c-1)$ ledande egenvektorerna för $\mathbf {N } ^{-1}\mathbf {M}$ . Dessutom ges projektionen av en ny ingång, ${\displaystyle \mathbf {x} _{t}} , av$

$\mathbf {y} (\mathbf {x} _{t})=\left(\mathbf {A} ^{*}\right)^ {\text{T}}\mathbf {K} _{t},$

där ${\displaystyle i^{th}}-$ komponenten av $\mathbf {K} _{t}$ ges av $k(\mathbf { x} _{i},\mathbf {x} _{t})$ .

Klassificering med KFD

I både två-klass och multi-klass KFD kan klassetiketten för en ny ingång tilldelas som

$f(\mathbf {x} )=arg\min _{j}D(\mathbf {y} (\ mathbf {x} ),{\bar {\mathbf {y} }}_{j}),$

där ${\bar {\mathbf {y} }}_{j}$ är det projicerade medelvärdet för klass $j$ och $D(\cdot , \cdot )$ är en avståndsfunktion.

Ansökningar

Kärndiskriminantanalys har använts i en mängd olika tillämpningar. Dessa inkluderar:

• Ansiktsigenkänning och detektering
• Handskriven sifferigenkänning
• Handavtrycksigenkänning
• Klassificering av maligna och benigna klustermikroförkalkningar
• Fröklassificering
• Sök efter Higgs Boson på CERN

Se även

• Faktoranalys
• Analys av kärnans huvudkomponent
• Kärntrick
• Linjär diskriminantanalys

externa länkar

• Kernel Discriminant Analysis i C# - C# kod för att utföra KFD.
• Matlab Toolbox for Dimensionality Reduction - Inkluderar en metod för att utföra KFD.
• Handskriftsigenkänning med kärndiskriminerande analys - C#-kod som demonstrerar handskriven sifferigenkänning med hjälp av KFD.