\[ %汎用 \newcommand{\ctext}[1]{\raise0.2ex\hbox{\textcircled{\scriptsize{#1}}}} %数学 %汎用 \newcommand{\as}{{\quad\textrm{as}\quad}} \newcommand{\st}{{\textrm{ s.t. }}} \newcommand{\set}[2]{\left\{\left.#1\;\right|\;#2\right\}} \newcommand{\naturalNumbers}{\mathbb{N}} \newcommand{\integers}{\mathbb{Z}} \newcommand{\rationalNumbers}{\mathbb{Q}} \newcommand{\realNumbers}{\mathbb{R}} \newcommand{\complexNumbers}{\mathbb{C}} \newcommand{\field}{\mathbb{F}} \newcommand{\func}[2]{{#1}\left({#2}\right)} \newcommand{\argmax}{\mathop{\textrm{arg~max}}} \newcommand{\argmin}{\mathop{\textrm{arg~min}}} %集合論 \newcommand{\range}[2]{\{#1,\dotsc,#2\}} \renewcommand{\complement}{\mathrm{c}} \newcommand{\ind}[2]{\mathbbm{1}_{#1}\left(#2\right)} \newcommand{\indII}[1]{\mathbbm{1}\left\{#1\right\}} %数論 \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\combi}[2]{{_{#1}\mathrm{C}_{#2}}} \newcommand{\perm}[2]{{_{#1}\mathrm{P}_{#2}}} \newcommand{\GaloisField}[1]{\mathrm{GF}\left(#1\right)} %解析学 \newcommand{\sgn}[1]{\operatorname{sgn}\left(#1\right)} \newcommand{\cl}[1]{\operatorname{cl}#1} \newcommand{\Img}[1]{\operatorname{Img}\left(#1\right)} \newcommand{\dom}[1]{\operatorname{dom}\left(#1\right)} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{\ceil}[1]{\left\lceil#1\right\rceil} \newcommand{\expo}[1]{\exp\left(#1\right)} \newcommand{\sinc}{\mathop{\textrm{sinc}}} \newcommand{\GammaFunc}[1]{\Gamma\left(#1\right)} %逆三角関数 \newcommand{\asin}[1]{\operatorname{Sin}^{-1}{#1}} \newcommand{\acos}[1]{\operatorname{Cos}^{-1}{#1}} \newcommand{\atan}[1]{\operatorname{{Tan}^{-1}}{#1}} \newcommand{\atanEx}[2]{\atan{\left(#1,#2\right)}} %微分 \newcommand{\deriv}[3]{\frac{\operatorname{d}^{#3}#1}{\operatorname{d}{#2}^{#3}}} \newcommand{\derivLong}[3]{\frac{\operatorname{d}^{#3}}{\operatorname{d}{#2}^{#3}}#1} \newcommand{\partDeriv}[3]{\frac{\operatorname{\partial}^{#3}#1}{\operatorname{\partial}{#2}^{#3}}} \newcommand{\partDerivLong}[3]{\frac{\operatorname{\partial}^{#3}}{\operatorname{\partial}{#2}^{#3}}#1} \newcommand{\partDerivIIHetero}[3]{\frac{\operatorname{\partial}^2#1}{\partial#2\operatorname{\partial}#3}} \newcommand{\partDerivIIHeteroLong}[3]{{\frac{\operatorname{\partial}^2}{\partial#2\operatorname{\partial}#3}#1}} %積分 \newcommand{\integrate}[5]{\int_{#1}^{#2}{#3}{\mathrm{d}^{#4}}#5} \newcommand{\LebInteg}[4]{\int_{#1} {#2} {#3}\left(\mathrm{d}#4\right)} %複素解析 \newcommand{\conj}[1]{\overline{#1}} \renewcommand{\Re}[1]{{\operatorname{Re}{\left(#1\right)}}} \renewcommand{\Im}[1]{{\operatorname{Im}{\left(#1\right)}}} \newcommand{\Arg}[1]{\operatorname{Arg}{\left({#1}\right)}} \newcommand{\Log}[1]{\operatorname{Log}{#1}} %ラプラス変換 \newcommand{\LPLC}[1]{\operatorname{\mathcal{L}}\left[#1\right]} \newcommand{\ILPLC}[1]{\operatorname{\mathcal{L}}^{-1}\left[#1\right]} %線形代数 \newcommand{\bm}[1]{{\boldsymbol{#1}}} \newcommand{\Span}[1]{\operatorname{span}\left[#1\right]} \newcommand{\Ker}[1]{\operatorname{Ker}\left(#1\right)} \newcommand{\rank}[1]{\operatorname{rank}\left(#1\right)} \newcommand{\inprod}[2]{\left\langle#1,#2\right\rangle} \newcommand{\HadamardProd}{\odot} \newcommand{\HadamardDiv}{\oslash} \newcommand{\matEntry}[3]{#1\left[#2\right]\left[#3\right]} \newcommand{\matPart}[5]{\matEntry{#1}{#2:#3}{#4:#5}} \newcommand{\diag}[1]{\operatorname{diag}\left(#1\right)} \newcommand{\tr}[1]{\operatorname{tr}{\left(#1\right)}} %ベクトル %単位ベクトル \newcommand{\vix}{\bm{i}_x} \newcommand{\viy}{\bm{i}_y} \newcommand{\viz}{\bm{i}_z} %確率論 \newcommand{\PDF}[2]{\operatorname{PDF}\left[#1,\;#2\right]} \newcommand{\Ber}[1]{\operatorname{Ber}\left(#1\right)} \newcommand{\Beta}[2]{\operatorname{Beta}\left(#1,#2\right)} \newcommand{\ExpDist}[1]{\operatorname{ExpDist}\left(#1\right)} \newcommand{\ErlangDist}[2]{\operatorname{ErlangDist}\left(#1,#2\right)} \newcommand{\PoissonDist}[1]{\operatorname{PoissonDist}\left(#1\right)} \newcommand{\GammaDist}[2]{\operatorname{Gamma}\left(#1,#2\right)} \newcommand{\cind}[2]{\ind{#1\left| #2\right.}} %条件付き指示関数 \renewcommand{\Pr}[1]{\operatorname{Pr}\left[#1\right]} \newcommand{\cPr}[2]{\Pr{#1\left| #2\right.}} \newcommand{\E}[2]{\operatorname{E}_{#1}\left[#2\right]} \newcommand{\cE}[3]{\E{#1}{\left.#2\right|#3}} \newcommand{\Var}[2]{\operatorname{Var}_{#1}\left[#2\right]} \newcommand{\Cov}[2]{\operatorname{Cov}\left[#1,#2\right]} \newcommand{\CovMat}[1]{\operatorname{Cov}\left[#1\right]} %グラフ理論 \newcommand{\neighborhood}{\mathcal{N}} %プログラミング \newcommand{\plpl}{\mathrel{++}} \newcommand{\pleq}{\mathrel{+}=} \newcommand{\asteq}{\mathrel{*}=} \]

Fisher の線形判別分析のベクトルwをガチで導出する


Fisher の線形判別分析のベクトル$\bm{w}$の導出を厳密にやってみたくなった


 2クラスの分類問題を解く線形判別器の構築法の一つに Fisher の線形判別分析 というのがある。この手法自体の解説は例えばフィッシャーの線形判別分析法とかフィッシャーの線形判別が参考になるが、1つ目のページではLagrangeの未定乗数法による詳細な過程が省略されている。2つ目の記事では評価関数の勾配が零になることをもって最適解としてしまう早計な議論が行われている。評価関数は凸ではなく、勾配が零になるからといって最適解であるとは言えない。本記事では判別器を構成するベクトル$\bm{w}$を厳密に導出する。

最大化問題の定式化


 クラス内共分散行列とクラス間共分散行列をそれぞれ$\SW,\;\SB \coloneqq (\xbar^1 - \xbar^2)(\xbar^1 - \xbar^2)^\top$とする。ここに$\xbar^1,\xbar^2$はクラス1,2のサンプルデータの平均である。$\SW$の正則性と$\xbar^1 \neq \xbar^2$を仮定すると、$\SW$は正定値対称、$\SB$は半正定値対称階数は1となる。

($\xbar^1 \neq \xbar^2$とするのは自然な仮定である。そうでなければ2つのクラスタが激しく重なっており、線形判別は意味を成さない。また、ある軸方向に射影すると一点に集まるようなふざけたサンプル(超平面上に綺麗に乗ったデータ)を扱わない限り$\SW$は常に正則となるので、この仮定も自然である。)

 クラス間分散とクラス内分散の比
\[ r(\bm{w}) \coloneqq \frac{\bm{w}^\top\SB\bm{w}}{\bm{w}^\top\SW\bm{w}} \]
$\bm{w}$の定数倍の差に影響されない。ある$\bm{w}^*$が$r$を最大化するならば任意の$\alpha\neq 0$に対して$\alpha\bm{w}^*$も$r$を最大化する。よって$\bm{w}^\top\SW\bm{w} = 1$という制約を加えても$r$の最大値は変わらないから、結局次の問題の解集合を含む最小の部分空間から$\bm{0}$を抜いたものが元の問題の解集合となる。
\begin{align*}
\textrm{maximize} &\quad f(\bm{w}) \coloneqq \bm{w}^\top\SB\bm{w} \\
\textrm{subject to} &\quad g(\bm{w}) \coloneqq \bm{w}^\top\SW\bm{w} - 1 = 0
\end{align*}
実行可能領域は有界閉集合($n$次元の楕円)であり、目的関数は連続であるからこの最大化問題は解をもつ。$\SW$は正定値であるから実行可能領域に特異点は存在せず、Lagrangeの未定乗数法が使える。

Lagrangeの未定乗数法


制約条件に対するLagrange定数を$\lambda$とすると、最適解の満たすべき必要条件は次のようになる。
\begin{cases}
(\SB - \lambda\SW)\bm{w} & = \bm{0} & \quad (1)\\
\bm{w}^\top\SW\bm{w} & = 1 & \quad (2)
\end{cases}
(2)より$\bm{w}\neq\bm{0}$であるから、(1)の行列$\SB - \lambda\SW$が非正則になる必要がある。ここで$\lambda = 0$としてみると(1)より$\SB\bm{w} = \bm{0}$つまり$f(\bm{w}) = 0$となるが、$\SB$は階数1の半正定値行列なのでこのような$\bm{w}$は明らかに最大化問題の解ではない。($\SB$の固有値の一つが正で他の$n-1$個が0なので$f(\bm{w})>0$となる$\bm{w}$が実行可能領域に必ず存在する。)よって$\lambda\neq 0$である。(1)の両辺に左から$\SW^{-1}$を掛けると上の連立方程式は次のようになる。
\begin{cases}
(\SW^{-1}\SB - \lambda I_n)\bm{w} &= \bm{0} & \quad (3)\\
\bm{w}^\top\SW\bm{w} &= 1 & \quad (4)
\end{cases}
(3)より$\SW^{-1}\SB\bm{w} = \lambda\bm{w}$となるので$\lambda$は$\SW^{-1}\SB$の固有値であり、$\bm{w}$は対応する固有ベクトルである。

とりあえず解候補を見つける


突然だがここで
\begin{align*}
\bm{w}^* &= \frac{\SW^{-1}(\xbar^1 - \xbar^2)}{\sqrt{\left(\SW^{-1}(\xbar^1 - \xbar^2)\right)^\top\SW\left(\SW^{-1}(\xbar^1 - \xbar^2)\right)}} \quad (\neq\bm{0}) \\
\lambda^* &= \left(\SW^{-1}(\xbar^1 - \xbar^2)\right)^\top\SW\left(\SW^{-1}(\xbar^1 - \xbar^2)\right) \quad (>0)
\end{align*}
とおいてみると
\begin{align*}
\SW^{-1}\SB\bm{w}^* &= \SW^{-1}(\xbar^1 - \xbar^2)(\xbar^1 - \xbar^2)^\top\frac{\SW^{-1}(\xbar^1 - \xbar^2)}{\sqrt{\left(\SW^{-1}(\xbar^1 - \xbar^2)\right)^\top\SW\left(\SW^{-1}(\xbar^1 - \xbar^2)\right)}} \\
&= \sqrt{\left(\SW^{-1}(\xbar^1 - \xbar^2)\right)^\top\SW\left(\SW^{-1}(\xbar^1 - \xbar^2)\right)} \SW^{-1}(\xbar^1 - \xbar^2) \\
&= \left(\SW^{-1}(\xbar^1 - \xbar^2)\right)^\top\SW\left(\SW^{-1}(\xbar^1 - \xbar^2)\right) \bm{w}^* \\
&= \lambda^*\bm{w}^* \\
\end{align*}
となり、$\lambda^*, \bm{w}^*$はそれぞれ$\SW^{-1}\SB$の固有値,固有ベクトルになっている。さらに${\bm{w}^*}^\top\SW\bm{w}^* = 1$となる。 よって力任せに作った$(\lambda^*, \bm{w}^*)$は(3),(4)の解である。同様に$(\lambda^*, -\bm{w}^*)$も解である。この2つ以外に解が存在しないことを示す。

他に解がないことを示す


$\SW^{-1}\SB$は階数1であるから、Jordan分解すると次のようになる。
\[
\SW^{-1}\SB = JDJ^{-1},
\quad D =
\begin{bmatrix}
d & 0 & \cdots & 0 \\
0 & 0 & \cdots & \vdots \\
\vdots & \vdots & \ddots & \vdots \\
0 & \cdots & \cdots & 0
\end{bmatrix},
\quad d\neq 0
\]
ここに正則行列$J$はJordan標準形への適当な変換行列である。$\bm{z} = J^{-1}\bm{w}$すなわち$\bm{w} = J\bm{z}$なる変数変換を行うと次のようになる。
\begin{align*}
\left\{
\begin{matrix}
(3) \\
(4)
\end{matrix}
\right. &\iff
\left\{
\begin{matrix}
(\SW^{-1}\SB - \lambda I_n)J\bm{z} &= \bm{0} \\
\bm{z}^\top J^\top\SW J\bm{z} &= 1
\end{matrix}
\right. \iff
\left\{
\begin{matrix}
J^{-1}(\SW^{-1}\SB - \lambda I_n)J\bm{z} &= \bm{0} \\
\bm{z}^\top J^\top\SW J\bm{z} &= 1
\end{matrix}
\right. \iff
\left\{
\begin{matrix}
(D - \lambda I_n)\bm{z} &= \bm{0} & \quad (5)\\
\bm{z}^\top J^\top\SW J\bm{z} &= 1 & \quad (6)
\end{matrix}
\right.
\end{align*}
$\lambda \neq 0,d$のとき$D - \lambda I_n$は正則なので連立方程式は解を持たない。$\lambda = 0$は先述の通り最大化問題の解ではないので除外する。$\lambda = d$のとき$D - \lambda I_n$の階数は$n-1$となる。すなわち$D$の固有値$d$に対応する固有空間の次元は1であるから連立方程式の解は符号の違いによる2つしかない。よって先程作った$\lambda^* > 0$が実は$d$だったのであり、$(\lambda^*, \bm{w}^*)$と$(\lambda^*, -\bm{w}^*)$が連立方程式(3),(4)の解の全てである。

連立方程式の解が問題の最適解であること


Lagrangeの未定乗数法に基づく連立方程式(3),(4)は最大化問題の解の必要条件に過ぎないが、今回は解候補が2つしかなく、両方が同じ目的関数値を与えるのでこれが最適解である(そうでないと元の問題に最適解が存在しないことになり、冒頭の仮定に矛盾する)。

実用上は規格化しなくてもよい


ここまでは考察のために$\bm{w}^\top\SW\bm{w} = 1$という制約を付けていた。しかし冒頭で述べたように元の最大化問題では$\bm{w}$の定数倍の差は関係ないので、上の議論の$\bm{w}^*$ように規格化の手間を掛ける必要はなく、$\bm{w}$のノルムに関心が無いときは$\bm{w} = \SW^{-1}(\xbar^1 - \xbar^2)$とするだけで構わない。
関連記事
スポンサーサイト



コメント

非公開コメント

プロフィール

motchy

Author:motchy
・信号処理
・無線
・組込

GitHub/motchy869

検索フォーム