機械学習基礎理論独習

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

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

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

ヘッセ行列

ヘッセ行列を計算します。
目的関数を{\bf w}_j微分した計算結果は、ロジスティック回帰 - 多値分類の記事より、以下の式でした。

\begin{eqnarray}
\nabla_{{\bf w}_j}E({\bf w}_1,\ldots,{\bf w}_K)&=&\frac{\partial}{\partial{\bf w}_j}E({\bf w}_1,\ldots,{\bf w}_K)\\
&=&\sum_{n=1}^N(y_{nj}-t_{nj}){\boldsymbol\phi}_n\tag{1}
\end{eqnarray}

目的関数を{\bf w}_j微分した後、{\bf w}_k微分したヘッセ行列を求めます。

\begin{eqnarray}
\nabla_{{\bf w}_k}\nabla_{{\bf w}_j} E({\bf w}_1,\ldots,{\bf w}_K)&=&\frac{\partial}{\partial{{\bf w}_k}}\left(\frac{\partial}{\partial{{\bf w}_j}^\top}E({\bf w}_1,\ldots,{\bf w}_K)\right)\\
&=&\frac{\partial}{\partial{{\bf w}_k}}\left(\frac{\partial}{\partial{{\bf w}_j}}E({\bf w}_1,\ldots,{\bf w}_K)\right)^\top\\
&=&\frac{\partial}{\partial{{\bf w}_k}}\left(\sum_{n=1}^N(y_{nj}-t_{nj}){\boldsymbol\phi}_n^\top\right)\\
&=&\sum_{n=1}^N\frac{\partial}{\partial{{\bf w}_k}}y_{nj}{\boldsymbol\phi}_n^\top\\
&=&\sum_{n=1}^Ny_{nk}(I_{kj}-y_{nj}){\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top\tag{2}
\end{eqnarray}

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

\begin{eqnarray}
\frac{\partial}{\partial{\bf w}_k}y_{nj}=y_{nk}(I_{kj}-y_{nj}){\boldsymbol\phi}_n\tag{3}
\end{eqnarray}

ここで{\bf H}_{jk}=\nabla_{{\bf w}_k}\nabla_{{\bf w}_j} E({\bf w}_1,\ldots,{\bf w}_K)おきます。
ヘッセ行列は{\bf H}\in\mathbb{R}^{MK\times MK}であり、求めた(8)はのヘッセ行列の{\bf H}_{jk}\in\mathbb{R}^{M\times M}のブロックです。

\begin{eqnarray}
{\bf H}=\begin{pmatrix}
{\bf H}_{11}&\cdots&{\bf H}_{1k}&\cdots&{\bf H}_{1K}\\
\vdots&\ddots&\vdots&\ddots&\vdots\\
{\bf H}_{j1}&\cdots&{\bf H}_{jk}&\cdots&{\bf H}_{jK}\\
\vdots&\ddots&\vdots&\ddots&\vdots\\
{\bf H}_{K1}&\cdots&{\bf H}_{Kk}&\cdots&{\bf H}_{KK}\\
\end{pmatrix}\tag{4}
\end{eqnarray}

{\bf w}=({\bf w}_1^\top,\cdots,{\bf w}_K^\top)^\topとします。

ニュートン法による{\bf w}の更新は以下のようになります。

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

(5){\bf H}{\bf w}^{(old)}から計算されるものです。

目的関数が凸関数

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

任意のベクトル{\bf u}\not={\bf 0}に対して、{\bf u}^\top{\bf H}{\bf u}\geq 0となることを示します。
{\bf u}=({\bf u}_1^\top,\ldots,{\bf u}_K)^\top\in\mathbb{R}^{MK},{\bf u}_j\in\mathbb{R}^Mとします。

\begin{eqnarray}
{\bf u}^\top{\bf H}{\bf u}&=&\sum_{k=1}^K\sum_{j=1}^K{\bf u}_j^\top{\bf H}_{jk}{\bf u}_k\\
&=&\sum_{k=1}^K\sum_{j=1}^K{\bf u}_j^\top\sum_{n=1}^Ny_{nk}(I_{kj}-y_{nj}){\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top{\bf u}_k\\
&=&\sum_{k=1}^K\sum_{j=1}^K\sum_{n=1}^N{\bf u}_j^\top y_{nk}(I_{kj}-y_{nj}){\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top{\bf u}_k\\
&=&\sum_{k=1}^K\sum_{j=1}^K\sum_{n=1}^N\left({\bf u}_j^\top y_{nk}I_{kj}{\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top{\bf u}_k-{\bf u}_j^\top y_{nk}y_{nj}{\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top{\bf u}_k\right)\\
&=&\sum_{k=1}^K\sum_{n=1}^N\left({\bf u}_k^\top y_{nk}{\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top{\bf u}_k-\sum_{j=1}^K{\bf u}_j^\top y_{nk}y_{nj}{\boldsymbol\phi}_n{\boldsymbol\phi}_n^\top{\bf u}_k\right)\\
&=&\sum_{k=1}^K\sum_{n=1}^N\left(y_{nk}({\bf u}_k^\top {\boldsymbol\phi}_n)^2-\sum_{j=1}^Ky_{nj}{\bf u}_j^\top {\boldsymbol\phi}_ny_{nk}{\boldsymbol\phi}_n^\top{\bf u}_k\right)\\
&=&\sum_{n=1}^N\left(\sum_{k=1}^Ky_{nk}({\bf u}_k^\top {\boldsymbol\phi}_n)^2-\sum_{k=1}^K\sum_{j=1}^Ky_{nj}{\bf u}_j^\top {\boldsymbol\phi}_ny_{nk}{\boldsymbol\phi}_n^\top{\bf u}_k\right)\\
&=&\sum_{n=1}^N\left(\sum_{k=1}^Ky_{nk}({\bf u}_k^\top {\boldsymbol\phi}_n)^2-\left(\sum_{k=1}^Ky_{nk}{\boldsymbol\phi}_n^\top{\bf u}_k\right)^2\right)\geq 0\tag{6}\\
\end{eqnarray}

(6)の8行目の\geq 0の説明をします。
f(x)=x^2は凸で、y_{nk}>0,\sum_{k=1}^Ky_{nk}=1なので、イェンゼンの不等式から以下が成り立ちます。

\begin{eqnarray}
\sum_{k=1}^Ky_{nk}({\bf u}_k^\top {\boldsymbol\phi}_n)^2&=&\sum_{k=1}^Ky_{nk}f\left({\bf u}_k^\top {\boldsymbol\phi}_n)\right)\\
&\geq&f\left(\sum_{k=1}^Ky_{nk}({\bf u}_k^\top {\boldsymbol\phi}_n)\right)\\
&=&\left(\sum_{k=1}^Ky_{nk}{\boldsymbol\phi}_n^\top{\bf u}_k\right)^2\tag{7}
\end{eqnarray}

目的関数のヘッセ行列は半正定値行列であることが示せました。
よって、目的関数は凸関数です。

目次へ戻る