4.3.4：多クラスロジスティック回帰の導出【PRMLのノート】

　$n$番目の入力$\mathbf{x}_n$に対して、基底関数$\boldsymbol{\phi}(\mathbf{x}_n) = (\phi_0(\mathbf{x}_n), \phi_1(\mathbf{x}_n), \cdots, \phi_{M-1}(\mathbf{x}_n))^{\top}$を用いて非線形な変換を行います。
　数式を簡略化するために、非線形変換を行った入力を$\boldsymbol{\phi}_n = \boldsymbol{\phi}(\mathbf{x}_n)$で表すことにします。

　$\boldsymbol{\phi}_n$とクラス$k$の重みパラメータ$\mathbf{w}_k$の内積(重み付き和)を計算します。

$$ a_{n,k} = \mathbf{w}_k^{\top} \boldsymbol{\phi}_n $$

　クラス数を$K$として、$K$個の重みパラメータをまとめて$\mathbf{W} = \{\mathbf{w}_1, \cdots, \mathbf{w}_K\}$で表します。また、クラス$k$のことを$C_k$とも表記します(が、この記事では登場しません)。
　全てのクラスの重み付き和$\mathbf{a}_n = (a_{n,1}, \cdots, a_{n,K})^{\top}$をソフトマックス関数で変換します。

$$ y_{n,k} = \frac{ \exp(a_{n,k}) }{ \sum_{k=1}^K \exp(a_{n,k}) } \tag{4.104} $$

　出力$\mathbf{y}_n = (y_{n,1}, \cdots, y_{n,K})^{\top}$の各項は、$0 < y_{n,k} < 1$、$\sum_{k=1}^K y_{n,k} = 1$に変換されるので、カテゴリ分布のパラメータとして用います。

$$ p(\mathbf{t}_n | \mathbf{W}) = \mathrm{Cat}(\mathbf{t}_n | \mathbf{y}_n) = \prod_{k=1}^K y_{n,k}^{t_{n,k}} $$

　$\mathbf{t}_n = (t_{n,1}, \cdots, t_{n,K})^{\top}$は、1つの要素が1で、それ以外の要素が0をとります。$t_{n,k} = 1$($k$番目の要素が1)のとき、$n$番目の入力$\mathbf{x}_n$のクラスが$k$であることを表します。このような表記を、1-of-K符号化法またはone-hot表現と言います。$t_{n,k}$が0か1の2値をとることを$t_{n,k} \in \{0, 1\}$で表し、1つの要素のみが1なので$\sum_{k=1}^K t_{n,k} = 1$となります。
　$y_{n,k}$は$t_{n,k} = 1$となる確率を表します。

　ここまでは、1つのデータでした。次は、複数のデータの場合を考えます。

　$N$個のデータ$\mathbf{X} = \{\mathbf{x}_1, \cdots, \mathbf{x}_N\}$、$\mathbf{T} = \{\mathbf{t}_1, \cdots, \mathbf{t}_N\}$が独立に生成されていると仮定すると、尤度関数は$N$個のカテゴリ分布の積で表せます。

$$ p(\mathbf{T} | \mathbf{W}) = \prod_{n=1}^N p(\mathbf{t}_n | \mathbf{W}) = \prod_{n=1}^N \mathrm{Cat}(\mathbf{t}_n | \mathbf{y}_n) = \prod_{n=1}^N \prod_{k=1}^K y_{n,k}^{t_{n,k}} \tag{4.107} $$

　指数部分の計算を分かりやすくするために対数をとります。また、符号を反転させます(-1を掛けます)。

$$ - \ln p(\mathbf{T} | \mathbf{W}) = - \sum_{n=1}^N \ln \mathrm{Cat}(\mathbf{t}_n | \mathbf{y}_n) = - \sum_{n=1}^N \sum_{k=1}^K t_{n,k} \ln y_{n,k} \equiv E(\mathbf{W}) $$

　負の値をとるようにした対数尤度関数なので、負の対数尤度関数と言います。ロジスティック回帰と同様に、負の対数尤度関数を最小化することで、尤度関数を最大化します。またこの式は、交差エントロピー誤差の式でもあります。よって、負の対数尤度関数の最小化(尤度関数の最大化)は、交差エントロピー誤差の最小化とも言えます。
　この式を多クラスロジスティック回帰の誤差関数$E(\mathbf{W})$として用います。

・勾配の導出

　誤差関数(負の対数尤度関数・交差エントロピー誤差)の勾配(1階微分)を求めます。

　ロジスティック回帰と同様に、負の対数尤度関数の$\mathbf{w}_i\ (i = 1, \cdots, K)$に関する勾配を求めます。連鎖律(合成関数の微分)により次の2つの計算式で求められます。
　1つ目の式は、$a_{n,i}$が$\mathbf{y}_n$の$K$個(全て)の要素に影響していることから、$K$個($j = 1, \cdots, K$)の$\frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial a_{n,i}} = \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,j}} \frac{\partial y_{n,j}}{\partial a_{n,i}}$の和から求めます。

$$ \frac{\partial E(\mathbf{W})}{\partial \mathbf{w}_i} = - \sum_{n=1}^N \left\{ \sum_{j=1}^K \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,j}} \frac{\partial y_{n,j}}{\partial a_{n,i}} \right\} \frac{\partial a_{n,i}}{\partial \mathbf{w}_i} \tag{1} $$

　2つ目の式は、ベクトル$\mathbf{u} = \mathbf{u}(\mathbf{x})$の合成関数$g(\mathbf{u})$の微分$\frac{\partial g(\mathbf{u})}{\partial \mathbf{x}} = \frac{\partial \mathbf{u}}{\partial \mathbf{x}} \frac{\partial g(\mathbf{u})}{\partial \mathbf{u}}$から求めます(こっちは自信ないけどこうでもしないと転置が合わない？)。

$$ \frac{\partial E(\mathbf{W})}{\partial \mathbf{w}_i} = - \sum_{n=1}^N \left( \frac{\partial \mathbf{y}_n}{\partial a_{n,i}} \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial \mathbf{y}_n} \right) \frac{\partial a_{n,i}}{\partial \mathbf{w}_i} \tag{2} $$

　式(1)の1つ目の項は、対数をとったカテゴリ分布の微分です。

$$ \begin{aligned} \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,j}} &= \frac{\partial}{\partial y_{n,j}} \left\{ \sum_{k=1}^K t_{n,k} \ln y_{n,k} \right\} \\ &= \frac{\partial}{\partial y_{n,j}} \Bigl\{ t_{n,1} \ln y_{n,1} + \cdots + t_{n,j} \ln y_{n,j} + \cdots + t_{n,K} \ln y_{n,K} \Bigr\} \\ &= \frac{\partial t_{n,1} \ln y_{n,1}}{\partial y_{n,j}} + \cdots + \frac{\partial t_{n,j} \ln y_{n,j}}{\partial y_{n,j}} + \cdots + \frac{\partial t_{n,K} \ln y_{n,K}}{\partial y_{n,j}} \\ &= 0 + \cdots + t_{n,j} \frac{\partial \ln y_{n,j}}{\partial y_{n,j}} + \cdots + 0 \\ &= \frac{t_{n,j}}{y_{n,j}} \end{aligned} $$

　$y_{n,j}$での偏微分なので$j$番目の項のみが残ります。対数の微分$\frac{d \ln x}{d x} = \frac{1}{x}$を行っています。
　他の項も同様に計算できるので、式(2)の2つ目の項は

$$ \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial \mathbf{y}_n} = \begin{pmatrix} \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,1}} \\ \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,2}} \\ \vdots \\ \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,K}} \end{pmatrix} = \begin{pmatrix} \frac{t_{n,1}}{y_{n,1}} \\ \frac{t_{n,2}}{y_{n,2}} \\ \vdots \\ \frac{t_{n,K}}{y_{n,K}} \end{pmatrix} $$

となります。

　式(1)の2つ目の項は、ソフトマックス関数の微分です。ソフトマックス関数の微分は、$y_{n,j}, a_{n,i}$の成分$j, i$によって計算式が異なります。

$$ \begin{aligned} \frac{\partial y_{n,i}}{\partial a_{n,i}} &= y_{n,i} (1 - y_{n,i}) & (j = i) \\ \frac{\partial y_{n,j}}{\partial a_{n,i}} &= - y_{n,j} y_{n,i} & (j \neq i) \end{aligned} $$

　$j = i$のとき上の式、$j \neq i$のとき下の式になります。この2つの計算式は、$K \times K$の単位行列

$$ \mathbf{I} = \begin{pmatrix} I_{1,1} & I_{1,2} & \cdots & I_{1,K} \\ I_{2,1} & I_{2,2} & \cdots & I_{2,K} \\ \vdots & \vdots & \ddots & \vdots \\ I_{K,1} & I_{K,2} & \cdots & I_{K,K} \end{pmatrix} = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix} $$

を用いてまとめられます。

$$ \frac{\partial y_{n,j}}{\partial a_{n,i}} = y_{n,j} (I_{j,i} - y_{n,i}) $$

　$I_{j,i}$は単位行列の要素です。この式は、$j = i$のとき$I_{i,i} = 1$となり上の式に、$j \neq i$のとき$I_{j,i} = 0$となり下の式になります。
　他の項も同様に計算できるので、式(2)の1つ目の項は

$$ \begin{aligned} \frac{\partial \mathbf{y}_n}{\partial a_{n,i}} &= \begin{pmatrix} \frac{\partial y_{n,1}}{\partial a_{n,i}} & \frac{\partial y_{n,2}}{\partial a_{n,i}} & \cdots & \frac{\partial y_{n,K}}{\partial a_{n,i}} \end{pmatrix} \\ &= \begin{pmatrix} y_{n,1} (I_{1,i} - y_{n,i}) & y_{n,2} (I_{2,i} - y_{n,i}) & \cdots & y_{n,K} (I_{K,i} - y_{n,i}) \end{pmatrix} \end{aligned} $$

となります。

　3つ目の項は、重み付き和の微分です。

$$ \frac{\partial a_{n,i}}{\partial \mathbf{w}_i} = \frac{\partial \mathbf{w}_i^{\top} \boldsymbol{\phi}_n}{\partial \mathbf{w}_i} = \boldsymbol{\phi}_n $$

　内積の微分は$\frac{\partial \mathbf{x}^{\top} \mathbf{a}}{\partial \mathbf{x}} = \frac{\partial \mathbf{a}^{\top} \mathbf{x}}{\partial \mathbf{x}} = \mathbf{a}$です。

　3つの微分の項が求まったので、それぞれ式(1)に代入します。

$$ \begin{align} \frac{\partial E(\mathbf{W})}{\partial \mathbf{w}_i} &= - \sum_{n=1}^N \left\{ \sum_{j=1}^K \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial y_{n,j}} \frac{\partial y_{n,j}}{\partial a_{n,i}} \right\} \frac{\partial a_{n,i}}{\partial \mathbf{w}_i} \tag{1}\\ &= - \sum_{n=1}^N \left\{ \sum_{j=1}^K \frac{t_{n,j}}{y_{n,j}} y_{n,j} (I_{j,i} - y_{n,i}) \right\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N \Bigl\{ t_{n,1} (I_{1,i} - y_{n,i}) + \cdots + t_{n,i} (I_{i,i} - y_{n,i}) + \cdots + t_{n,K} (I_{K,i} - y_{n,i}) \Bigr\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N \Bigl\{ - t_{n,1} y_{n,i} + \cdots + t_{n,i} - t_{n,i} y_{n,i} + \cdots - t_{n,K} y_{n,i} \Bigr\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N \Bigl\{ t_{n,i} - (t_{n,1} + \cdots + t_{n,i} + \cdots + t_{n,K}) y_{n,i} \Bigr\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N (t_{n,k} - y_{n,i}) \boldsymbol{\phi}_n \\ &= \sum_{n=1}^N (y_{n,i} - t_{n,i}) \boldsymbol{\phi}_n \equiv \nabla_{\mathbf{w}_i} E(\mathbf{W}) \tag{4.109} \end{align} $$

　3行目から4行目では、$j = 1, \cdots, K$の$i$番目の項のみ$I_{i,i} = 1$なので$t_{n,i} - t_{n,i} y_{n,i}$となります。
　4行目から5行目では、$y_{n,i}$を括りました。
　5行目から6行目では、定義より$\sum_{k=1}^K t_{n,k} = 1$です。

　また、それぞれ式(2)に代入すると

$$ \begin{align} \frac{\partial E(\mathbf{W})}{\partial \mathbf{w}_i} &= - \sum_{n=1}^N \frac{\partial \mathbf{y}_n}{\partial a_{n,i}} \frac{\partial \ln p(\mathbf{t}_n | \mathbf{y}_n)}{\partial \mathbf{y}_n} \frac{\partial a_{n,i}}{\partial \mathbf{w}_i} \tag{2}\\ &= - \sum_{n=1}^N \begin{pmatrix} y_{n,1} (I_{1,i} - y_{n,i}) & \cdots & y_{n,i} (I_{i,i} - y_{n,i}) & \cdots & y_{n,K} (I_{K,i} - y_{n,i}) \end{pmatrix} \begin{pmatrix} \frac{t_{n,1}}{y_{n,1}} \\ \vdots \\ \frac{t_{n,i}}{y_{n,i}} \\ \vdots \\ \frac{t_{n,K}}{y_{n,K}} \end{pmatrix} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N \left\{ y_{n,1} (I_{1,i} - y_{n,i}) \frac{t_{n,1}}{y_{n,1}} + \cdots + y_{n,i} (I_{i,i} - y_{n,i}) \frac{t_{n,i}}{y_{n,i}} + \cdots + y_{n,K} (I_{k,i} - y_{n,i}) \frac{t_{n,K}}{y_{n,K}} \right\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N \Bigl\{ - t_{n,1} y_{n,i} + \cdots + t_{n,i} - t_{n,i} + \cdots - t_{n,K} y_{n,i} \Bigr\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N \Bigl\{ t_{n,i} - (t_{n,1} + \cdots + t_{n,i} y_{n,i} + \cdots + t_{n,K}) y_{n,i} \Bigr\} \boldsymbol{\phi}_n \\ &= - \sum_{n=1}^N (t_{n,k} - y_{n,i}) \boldsymbol{\phi}_n \\ &= \sum_{n=1}^N (y_{n,i} - t_{n,i}) \boldsymbol{\phi}_n \equiv \nabla_{\mathbf{w}_i} E(\mathbf{W}) \end{align} $$

式(1)の場合と一致しました。

　多クラスロジスティック回帰の誤差関数の$\mathbf{w}_i$に関する勾配$\nabla_{\mathbf{w}_i} E(\mathbf{W})$が得られました。勾配を用いることで、勾配降下法などによってパラメータを更新できます。

　ちなみに、$t_{n,i} = 0$(正解クラスでない)のとき、$y_{n,i}$が0に近いほど$y_{n,i} - t_{n,i}$が小さくなり勾配も小さくなります。逆に、$y_{n,i}$が1に近いほど$y_{n,i} - t_{n,i}$が大きくなり勾配も大きくなります。また、$t_{n,i} = 1$(正解クラス)のとき、$y_{n,k}$が1に近いほど$y_{n,i} - t_{n,i}$の絶対値が小さくなり勾配も小さくなります。逆に、$y_{n,k}$が0に近いほど$y_{n,i} - t_{n,i}$の絶対値が大きくなり勾配も大きくなります。

　またこのベクトルは、4.3.3項と同様にして次のように変形できます。

$$ \nabla_{\mathbf{w}_i} E(\mathbf{W}) = \sum_{n=1}^N (y_{n,i} - t_{n,i}) \boldsymbol{\phi}_n = \boldsymbol{\Phi}^{\top} (\mathbf{y}_i - \mathbf{t}_i) \tag{4.109} $$

　ただし、$\mathbf{Y}, \mathbf{T}$から$i$番目の要素($i$列目)を取り出したベクトルを$\mathbf{y}_i, \mathbf{t}_i$とおきました。

・ヘッセ行列の導出

　誤差関数(負の対数尤度関数・交差エントロピー誤差)のヘッセ行列(2階微分)を求めます。

　$\nabla_{\mathbf{w}_i} E(\mathbf{W})$を更に$\mathbf{w}_j$で偏微分します。

$$ \begin{aligned} \frac{\partial^2 E(\mathbf{W})}{\partial \mathbf{w}_i \partial \mathbf{w}_j^{\top}} &= \frac{\partial}{\partial \mathbf{w}_j} \frac{\partial E(\mathbf{W})}{\partial \mathbf{w}_i} \\ &= \sum_{n=1}^N \frac{\partial}{\partial \mathbf{w}_j} (y_{n,i} - t_{n,i}) \boldsymbol{\phi}_n \\ &= \sum_{n=1}^N \left\{ \frac{\partial y_{n,i} \boldsymbol{\phi}_n}{\partial \mathbf{w}_j} - \frac{\partial t_{n,i} \boldsymbol{\phi}_n}{\partial \mathbf{w}_j} \right\} \end{aligned} $$

　後の項は、$\mathbf{w}_j$を含まないので0行列になり消えます。前の項に関して、スカラ$v = v(\mathbf{x})$とベクトル$\mathbf{a}$の積の微分$\frac{\partial v \mathbf{a}}{\partial \mathbf{x}} = \frac{\partial v}{\partial \mathbf{x}} \mathbf{a}^{\top}$より

$$ \frac{\partial y_{n,i} \boldsymbol{\phi}_n}{\partial \mathbf{w}_j} = \frac{\partial y_{n,i}}{\partial \mathbf{w}_j} \boldsymbol{\phi}_n^{\top} $$

となります。また、連鎖律(合成関数の微分)により2つの微分の積に分解できます。

$$ \begin{aligned} \frac{\partial y_{n,i}}{\partial \mathbf{w}_j} &= \frac{\partial y_{n,i}}{\partial a_{n,j}} \frac{\partial a_{n,j}}{\partial \mathbf{w}_j} \\ &= y_{n,i} (I_{i,j} - y_{n,j}) \boldsymbol{\phi}_n \end{aligned} $$

　前の項はソフトマックス関数の微分、後の項は重み付き和の微分です。どちらも先ほど求めしました。
　この式を上の式に代入します。

$$ \frac{\partial^2 E(\mathbf{W})}{\partial \mathbf{w}_i \partial \mathbf{w}_j^{\top}} = \sum_{n=1}^N y_{n,i} (I_{i,j} - y_{n,j}) \boldsymbol{\phi}_n \boldsymbol{\phi}_n^{\top} \equiv \nabla_{\mathbf{w}_i} \nabla_{\mathbf{w}_j} E(\mathbf{W}) $$

　多クラスロジスティック回帰の誤差関数の$\mathbf{w}_i, \mathbf{w}_j$に関するヘッセ行列$\nabla_{\mathbf{w}_i} \nabla_{\mathbf{w}_j} E(\mathbf{W})$が得られました。

　またこの行列は、4.3.3項と同様にして次のように変形できます。

$$ \nabla_{\mathbf{w}_i} \nabla_{\mathbf{w}_j} E(\mathbf{W}) = \sum_{n=1}^N y_{n,i} (I_{i,j} - y_{n,j}) \boldsymbol{\phi}_n \boldsymbol{\phi}_n^{\top} = \boldsymbol{\Phi}^{\top} \mathbf{R} \boldsymbol{\Phi} \equiv \mathbf{H} \tag{4.100} $$

　ここで、$\mathbf{R}$は$y_{n,i} (I_{i,j} - y_{n,j})$を対角成分とする対角行列

$$ \mathbf{R} = \begin{pmatrix} y_{1,i} (I_{i,j} - y_{1,j}) & 0 & \cdots & 0 \\ 0 & y_{2,i} (I_{i,j} - y_{2,j}) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & y_{N,i} (I_{i,j} - y_{N,j}) \end{pmatrix} $$

です。

・パラメータの更新式の導出

　ニュートン-ラフソン法によって、多クラスロジスティック回帰のパラメータの最尤解を求めます。ニュートン-ラフソン法については4.3.3項を参照してください。

　ニュートン-ラフソン法の更新式(4.92)にそれぞれ代入します。

$$ \begin{align} \mathbf{w}_j^{(\mathrm{new})} &= \mathbf{w}_j^{(\mathrm{old})} - \mathbf{H}^{-1} \nabla_{\mathbf{w}_j} E(\mathbf{W}) \tag{4.92}\\ &= \mathbf{w}_j^{(\mathrm{old})} - (\boldsymbol{\Phi}^{\top} \mathbf{R} \boldsymbol{\Phi})^{-1} \boldsymbol{\Phi}^{\top} (\mathbf{y}_i - \mathbf{t}_i) \end{align} $$

　4.3.3項と同様にして、この更新式を次のように変形します。

$$ \mathbf{w}_j^{(\mathrm{new})} = (\boldsymbol{\Phi}^{\top} \mathbf{R} \boldsymbol{\Phi})^{-1} \boldsymbol{\Phi}^{\top} \mathbf{R} \mathbf{z} \tag{4.99'} $$

　ここで、$\mathbf{z}$は$N$次元ベクトル

$$ \mathbf{z} = \boldsymbol{\Phi} \mathbf{w}_j^{(\mathrm{old})} - \mathbf{R}^{-1} (\mathbf{y}_i - \mathbf{t}_i) \tag{4.110'} $$

です。
　え、これ$\mathbf{w}_j$の更新式でいいんだよね？実装してみて確認します、、、

　ニュートン-ラフソン法による多クラスロジスティック回帰のパラメータの更新式が得られました。

参考文献

C.M.ビショップ著,元田浩・他訳『パターン認識と機械学習上下』,丸善出版,2012年.

おわりに

　難易度はロジスティック回帰と変わらないと思うんだけど、添字$k, i, j$の関係がややこしくててこずりました(三が日が溶けました)。
　あれこれ考えた末、本と添字が変わりました。しかし実装するまで自分の理解で合っているのか信用できない、、、

　というわけで、2022年一発目の記事です。昨年末に公開されたこの曲で楽しく新たな1年を始めましょう。

　今年は2人の曲をいっぱい聴けたらいいな。

【次節の内容】

www.anarchive-beta.com

【関連する内容】

　交差エントロピー誤差の微分の参考になるかもしれません。

www.anarchive-beta.com

　こうして見るとほとんどニューラルネットワークだな。最初の非線形変換の前に重みと掛け合わせたらまんま2層のNNだよね。