カーネルフィッシャー判別分析

統計学において、カーネルフィッシャー判別分析（KFD）^[1]は、一般化判別分析^[2]やカーネル判別分析^[3]とも呼ばれ、線形判別分析（LDA）のカーネル化バージョンです。ロナルド・フィッシャーにちなんで名付けられました。

直感的に言えば、LDAの考え方は、クラス分離が最大化される投影を見つけることです。2つのラベル付きデータセットとが与えられた場合、各クラスの平均値とを次のように計算できます。 ${\displaystyle \mathbf {C} _{1}}$${\displaystyle \mathbf {C} _{2}}$${\displaystyle \mathbf {m} _{1}}$${\displaystyle \mathbf {m} _{2}}$

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

ここで、 はクラス の例の数です。線形判別分析の目的は、クラス内分散を小さく保ちながら、クラス平均を大きく分離することです。^[4] これは、 に関して、次の比を最大化することとして定式化されます。 ${\displaystyle l_{i}}$${\displaystyle \mathbf {C} _{i}}$${\displaystyle \mathbf {w} }$

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

ここで、はクラス間共分散行列であり、はクラス内共分散行列の合計です。 ${\displaystyle \mathbf {S} _{B}}$${\displaystyle \mathbf {S} _{W}}$

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

上記の比率の最大値は、

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

ラグランジュ乗数法（証明の概要） で示すと次のようになります。

最大化は最大化と同じである ${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }}}$

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

対象となる

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

これは、 を最大化することと同等です。ここで、はラグランジュ乗数です。 ${\displaystyle I(\mathbf {w} ,\lambda )=\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} -\lambda (\mathbf {w } ^{\text{T}}\mathbf {S} _{W}\mathbf {w} -1)}$${\displaystyle \lambda}$

最大限では、とに関するの導関数は ゼロでなければならない。${\displaystyle I(\mathbf {w} ,\lambda )}$${\displaystyle \mathbf {w} }$${\displaystyle \lambda}$${\displaystyle {\frac {dI}{d\mathbf {w} }}=\mathbf {0} }$

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

これは、次のように自明に満たされる。${\displaystyle \mathbf {w} =c\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1})}$${\displaystyle \lambda =(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).}$

LDAを非線形マッピングに拡張するには、点として与えられたデータを何らかの関数を介して新しい特徴空間にマッピングすることができます。この新しい特徴空間では、最大化する必要がある関数は^[1]です。${\displaystyle \ell }$${\displaystyle \mathbf {x} _{i},}$${\displaystyle F,}$${\displaystyle \phi .}$

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

どこ

${\displaystyle {\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 }&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)^{\text{T}},\end{aligned}}}$

そして

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

さらに、 に注意してください。 マッピングを明示的に計算してから LDA を実行すると、計算コストが高くなり、多くの場合、手に負えなくなります。 たとえば、は無限次元である可能性があります。 したがって、データを に明示的にマッピングするのではなく、ドット積に関してアルゴリズムを書き直し、新しい特徴空間のドット積がカーネル関数 に置き換えられたカーネル関数を使用することで、データを暗黙的に埋め込むことができます。 ${\displaystyle \mathbf {w} \in F}$${\displaystyle \phi (\mathbf {x} _{i})}$${\displaystyle F}$${\displaystyle F}$${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\phi (\mathbf {x} )\cdot \phi (\mathbf {y} )}$

LDAはドット積の観点から再定式化することができ、まずは次のような形式に展開されることに注意する必要がある^[5]。${\displaystyle \mathbf {w} }$

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

次に、

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

どこ

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

の分子は次のように書くことができます。 ${\displaystyle J(\mathbf {w} )}$

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} =\mathbf {w} ^{\text{T}}\left(\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{where}}\qquad \mathbf {M} =(\mathbf {M} _{2}-\mathbf {M} _{1})(\mathbf {M} _{2}-\mathbf {M} _{1})^{\text{T}}.}$

同様に分母は次のように書ける。

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

の成分がと定義される行列は単位行列であり、すべての要素が と等しい行列である。この単位行列は、 の式から始めて の展開と の定義および の定義を使用することで導出できる。${\displaystyle n^{\text{th}},m^{\text{th}}}$${\displaystyle \mathbf {K} _{j}}$${\displaystyle k(\mathbf {x} _{n},\mathbf {x} _{m}^{j}),\mathbf {I} }$${\displaystyle \mathbf {1} _{l_{j}}}$${\displaystyle 1/l_{j}}$${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }$${\displaystyle \mathbf {w} }$${\displaystyle \mathbf {S} _{W}^{\phi }}$${\displaystyle \mathbf {m} _{i}^{\phi }}$

${\displaystyle {\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(\sum _{j=1,2}\sum _{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(\sum _{k=1}^{l}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{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)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{p=1}^{l_{j}}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})\right)\left(\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{q=1}^{l_{j}}\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{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}}}\sum _{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}}}\sum _{p=1}^{l_{j}}\sum _{q=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{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}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})\right)\right)\\[6pt]&=\sum _{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}}}$

の分子と分母に関するこれらの式を用いると、 の式は次のように書き直すことができる。 ${\displaystyle J(\mathbf {w} )}$${\displaystyle J}$

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

次に微分してゼロにすると、

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

の方向、つまり の方向だけが重要なので、上記は次のよう に解くことができる。${\displaystyle \mathbf {w} }$${\displaystyle \mathbf {\alpha } ,}$${\displaystyle \mathbf {\alpha } }$

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

実際には、は普通は単数形なので、恒等式の倍数がそれに加算されることに注意してください^[1]${\displaystyle \mathbf {N} }$

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

の解が与えられた場合、新しいデータポイントの投影は^{[1]で与えられる。}${\displaystyle \mathbf {\alpha } }$

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

2つ以上のクラスがある場合への拡張は比較的簡単です。^{[2] [6] [7] を}クラスの数と します。すると、多クラスKFDは判別関数 を使用してデータを次元空間に投影します。${\displaystyle c}$${\displaystyle (c-1)}$${\displaystyle (c-1)}$

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

これは行列表記で書くことができる

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

ここで、はの列である。^[6] さらに、クラス間共分散行列は、 ${\displaystyle \mathbf {w} _{i}}$${\displaystyle \mathbf {W} }$

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

ここで、新しい特徴空間内のすべてのデータの平均です。クラス内共分散行列は ${\displaystyle \mathbf {m} ^{\phi }}$

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

解は最大化することで得られる。

${\displaystyle 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|}}.}$

カーネルトリックを再び使用することができ、マルチクラスKFDの目標は次のようになる^[7]。

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

どこでそして ${\displaystyle A=[\mathbf {\alpha } _{1},\ldots ,\mathbf {\alpha } _{c-1}]}$

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

は上記のセクションで定義されており、は次のように定義されています。 ${\displaystyle \mathbf {M} _{i}}$${\displaystyle \mathbf {M} _{*}}$

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

${\displaystyle \mathbf {A} ^{*}}$は、の主固有ベクトルを見つけることによって計算できる。^[7] さらに、新しい入力の射影は、^[7]で与えられる。${\displaystyle (c-1)}$${\displaystyle \mathbf {N} ^{-1}\mathbf {M} }$${\displaystyle \mathbf {x} _{t}}$

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

ここでの成分はで与えられます。 ${\displaystyle i^{th}}$${\displaystyle \mathbf {K} _{t}}$${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{t})}$

2クラスと多クラスKFDの両方において、新しい入力のクラスラベルは次のように割り当てられる^[7]

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

ここで、 はクラスの投影平均であり、は距離関数です。 ${\displaystyle {\bar {\mathbf {y} }}_{j}}$${\displaystyle j}$${\displaystyle D(\cdot ,\cdot )}$

カーネル判別分析は、さまざまなアプリケーションで使用されています。これには以下が含まれます。

• 顔認識^{[3] [8] [9]}と検出^{[10] [11]}
• 手書き数字認識^{[1] [12]}
• 掌紋認識^[13]
• 悪性および良性のクラスター微小石灰化の分類^[14]
• 種子の分類^[2]
• CERNにおけるヒッグス粒子の探索^[15]

• 因子分析
• カーネル主成分分析
• カーネルトリック
• 線形判別分析

• C# でのカーネル判別分析 - KFD を実行する C# コード。
• 次元削減のための Matlab ツールボックス - KFD を実行するためのメソッドが含まれています。
• カーネル判別分析を使用した手書き認識 - KFD を使用して手書きの数字認識を示す C# コード。