機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

ニュートン法による最適化 - 2クラス分類

ニュートン法

ロジスティック回帰 - 2値分類の記事より、2値分類のロジスティック回帰の誤差関数は以下の式でした。

\begin{eqnarray}
E({\bf w})&=&-\sum_{n=1}^N(t_n\ln y_n+(1-t_n)\ln(1-y_n))\tag{1}
\end{eqnarray}

この誤差関数は局所二次近似を利用するニュートン法に基づく効率的な反復最適化手順を用いて最小化することができます。
関数E({\bf w})を最小化するニュートン法{\bf w}の更新は、以下の式で行われます。

\begin{eqnarray}
{\bf w}^{(new)}={\bf w}^{(old)}-{\bf H}^{-1}\nabla E({\bf w}^{(old)})\tag{2}
\end{eqnarray}

ここで、{\bf H}E({\bf w}){\bf w}に関するヘッセ行列です。

ヘッセ行列

目的関数E({\bf w}){\bf w}微分した計算結果は、ロジスティック回帰 - 2値分類の記事より、以下の式でした。

\begin{eqnarray}
\nabla E({\bf w})&=&\frac{\partial}{\partial{\bf w}}E({\bf w})\\
&=&\sum_{n=1}^N(y_n-t_n){\boldsymbol\phi}_n\\
&=&{\boldsymbol\Phi}^\top({\bf y}-{\bf t})\tag{3}
\end{eqnarray}

ヘッセ行列を求めます。

\begin{eqnarray}
\nabla\nabla E({\bf w})&=&\frac{\partial}{\partial{\bf w}}\left(\frac{\partial}{\partial{\bf w}^\top}E({\bf w})\right)\\
&=&\frac{\partial}{\partial{\bf w}}\left(\frac{\partial}{\partial{\bf w}}E({\bf w})\right)^\top\\
&=&\frac{\partial}{\partial{\bf w}}\left(\sum_{n=1}^N(y_n-t_n){\boldsymbol\phi}_n^\top\right)\\
&=&\sum_{n=1}^N\frac{\partial}{\partial{\bf w}}y_n{\boldsymbol\phi}_n^\top\\
&=&\sum_{n=1}^Ny_n(1-y_n){\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top\\
&=&{\boldsymbol\Phi}^\top{\bf R}{\boldsymbol\Phi}\tag{4}
\end{eqnarray}

(4)の5行目の式変形ですが、ロジスティック回帰 - 2値分類の記事より、以下を用いました。

\begin{eqnarray}
\frac{\partial}{\partial{\bf w}}y_n=y_n(1-y_n){\boldsymbol\phi}_n\tag{5}
\end{eqnarray}

また(4)では、要素が以下の式で与えられるN\times Nの対角行列{\bf R}を導入しています。

\begin{eqnarray}
R_{nn}=y_n(1-y_n)\tag{6}
\end{eqnarray}

ヘッセ行列が求まりましたので、ニュートン法{\bf w}の更新式を求めます。
(4)(2)に代入します。

\begin{eqnarray}
{\bf w}^{(new)}&=&{\bf w}^{(old)}-({\boldsymbol\Phi}^\top{\bf R}{\boldsymbol\Phi})^{-1}\nabla E({\bf w}^{(old)})\\
&=&({\boldsymbol\Phi}^\top{\bf R}{\boldsymbol\Phi})^{-1}({\boldsymbol\Phi}^\top{\bf R}{\boldsymbol\Phi}-\nabla E({\bf w}^{(old)}))\\
&=&({\boldsymbol\Phi}^\top{\bf R}{\boldsymbol\Phi})^{-1}{\boldsymbol\Phi}^\top{\bf R}{\bf z}\tag{7}
\end{eqnarray}

ここで、{\bf z}は以下を要素とするN次元ベクトルです。

\begin{eqnarray}
{\bf z}={\boldsymbol\Phi}{\bf w}^{(old)}-{\bf R}^{-1}({\bf y}-{\bf t})\tag{8}
\end{eqnarray}

重み付け行列\bf Rは定数ではなく、\bf wに依存しているので、\bf wが新たに求められる度に\bf Rを計算し直して、
正規方程式を繰り返し解かなければなりません。
このアルゴリズムは反復再重み付け最小二乗法またはIRLS(iterative reweighted least squares method) として知られています。

目的関数が凸関数で唯一の最小解を持つ

目的関数が凸関数で唯一の最小解を持つことを示すには、目的関数のヘッセ行列が正定値行列であることを示せばよいです。
以下、証明です。

任意のベクトル{\bf u}\not={\bf 0}に対して、{\bf u}^\top{\bf H}{\bf u}>0となることを示します。

\begin{eqnarray}
{\bf u}^\top{\bf H}{\bf u}&=&{\bf u}{\boldsymbol\Phi}^\top{\bf R}{\boldsymbol\Phi}{\bf u}\\
&=&\left({\bf R}^{\frac{1}{2}}{\boldsymbol\Phi}{\bf u}\right)^\top\left({\bf R}^{\frac{1}{2}}{\boldsymbol\Phi}{\bf u}\right)\\
&=&||({\bf R}^{\frac{1}{2}}{\boldsymbol\Phi}{\bf u})||^2>0\tag{9}
\end{eqnarray}

(9){\bf R}^{1/2}{\bf R}={\bf R}^{1/2}{\bf R}^{1/2}を満たすものとします。

(9)y_n\in(0,1)であるため、\bf Rの対角成分はすべて正です。
よって、||({\bf R}^{\frac{1}{2}}{\boldsymbol\Phi}{\bf u})||^2>0となります。

目的関数のヘッセ行列は正定値行列であることが示せました。
したがって、目的関数は凸関数で唯一の最小解をもちます。

偉人の名言

f:id:olj611:20210417070848p:plain:w300
何も咲かない寒い日は、下へ下へと根をのばせ。
やがて大きな花が咲く。
高橋尚子

参考文献

パターン認識機械学習 上巻

参考リンク

Matrix calculus - wikipedia

動画

目次へ戻る