Logistic Regression vs. Softmax Regression

logistic regressionとsoftmax regressionの関係について、知っている人にとってはごく当たり前だと思うのですが両者の関係性について書いてある日本語記事が少ないかと思ったので書いておきます。

## 簡単に復習
### Logistic Regression
logistic regressionは二値分類の際に用いられる回帰モデルで、standard logistic function (sigmoid function) を分類器として使用してloss functionを小さくするように訓練することによって分類器のパラメータを推定します。

```math
h_{\boldsymbol{\theta}}(\boldsymbol{x}) = \frac{1}{1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})}
```

上の$h_{\boldsymbol{\theta}}$がsigmoid functionで、$\boldsymbol{x}$が説明変数、$\boldsymbol{\theta}$が推定したいパラメータのベクトルです。これに対してloss functionはcross entropy errorと呼ばれるものが用いられ、サンプルサイズを$m$、目的変数(の確率変数)$Y \in \\{0, 1\\}$とすると、cross entropy errorは以下のように書けます。

```math
J(\boldsymbol{\theta}) = - \sum_{i=1}^{m} y^{(i)}\log h_{\boldsymbol{\theta}}(\boldsymbol{x}^{(i)}) + (1-y^{(i)})\log (1 - h_{\boldsymbol{\theta}}(\boldsymbol{x}^{(i)})) \tag{1}
```

このcross entropy errorを足し合わせた関数の値を小さくするようにパラメータを変化させていくことで、サンプルに適合したモデルを手に入れることができます。


### Softmax Regression
softmax regressionは多値分類で使われる回帰モデルで、logistic regressionを多クラス分類へ一般化したものになります。この分類器のモデル内で使用されるsoftmax functionはDeep系のモデルでscoringされたベクトルを確率分布に正規化するために出力層でよく用いられるイメージが強いのではないでしょうか。

```math
P(y^{(i)} = k |\boldsymbol{x}^{(i)};\boldsymbol{\theta}) = \frac{\exp\left(\boldsymbol{\theta}^{(k)\top}\boldsymbol{x}^{(i)}\right)}{\sum_{j=1}^{K}\exp\left(\boldsymbol{\theta}^{(j)\top}\boldsymbol{x}^{(i)}\right)}
```

上の関数がsoftmax functionで、カテゴリ数$K$で、目的変数の値が$k$となるときの確率の値を返します ($
\boldsymbol{x}$の長さを$n$とすると$
\boldsymbol{\theta}$は$n \times K$の行列で、$\boldsymbol{\theta}^{(i)}$は$\boldsymbol{\theta}$の$i$番目の列ベクトル)。loss functionは以下のように書けます。

```math
J(\boldsymbol{\theta}) = - \sum_{i=1}^{m} \sum_{k=1}^{K} \mathbb{1}(y^{(i)} = k)\log \frac{\exp\left(\boldsymbol{\theta}^{(k)\top}\boldsymbol{x}^{(i)}\right)}{\sum_{j=1}^{K}\exp\left(\boldsymbol{\theta}^{(j)\top}\boldsymbol{x}^{(i)}\right)}
```

ここで、$\mathbb{1}(\text{cond})$は指示関数 (indicator function) と呼ばれる関数で、条件式$\text{cond}$が真のときに$1$を、そうでないときに$0$を返します。


## 両者の関係について
さて、一見すると両者はあまり関係がないようにも見えますが、$K=2$のときのsoftmax regressionを考えると両者のloss functionが一致することを細かく式展開して見てみましょう。(ただし、$k=0$ or $1$とします)

```math
\begin{align*}
J(\boldsymbol{\theta}) &= - \sum_{i=1}^{m} \sum_{k=0}^{1} \mathbb{1}(y^{(i)} = k)\log \frac{\exp\left(\boldsymbol{\theta}^{(k)\top}\boldsymbol{x}^{(i)}\right)}{\exp\left(\boldsymbol{\theta}^{(0)\top}\boldsymbol{x}^{(i)}\right) + \exp\left(\boldsymbol{\theta}^{(1)\top}\boldsymbol{x}^{(i)}\right)}\\
&= - \sum_{i=1}^{m}\mathbb{1}(y^{(i)} = 0)\log \frac{1}{1 + \exp (\boldsymbol{\theta}^{(1)} - \boldsymbol{\theta}^{(0)})^{\top}\boldsymbol{x}^{(i)}} + \mathbb{1}(y^{(i)} = 1)\log \frac{1}{1 + \exp (\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^{(1)})^{\top}\boldsymbol{x}^{(i)}}\\
&= - \sum_{i=1}^{m}(1-y^{(i)})\log \frac{1}{1 + \exp (\boldsymbol{\theta}^{(1)} - \boldsymbol{\theta}^{(0)})^{\top}\boldsymbol{x}^{(i)}} + y^{(i)}\log \frac{1}{1 + \exp (\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^{(1)})^{\top}\boldsymbol{x}^{(i)}}\\
&= - \sum_{i=1}^{m}(1-y^{(i)})\log \frac{1}{1 + \exp (\boldsymbol{\theta}^{(1)} - \boldsymbol{\theta}^{(0)})^{\top}\boldsymbol{x}^{(i)}} + y^{(i)}\log \left (1 - \frac{1}{1 + \exp (\boldsymbol{\theta}^{(1)} - \boldsymbol{\theta}^{(0)})^{\top}\boldsymbol{x}^{(i)}}\right )\\
&= - \sum_{i=1}^{m}(1-y^{(i)})\log \frac{1}{1 + \exp \boldsymbol{\theta}'^{\top}\boldsymbol{x}^{(i)}} + y^{(i)}\log \left (1 - \frac{1}{1 + \exp \boldsymbol{\theta}'^{\top}\boldsymbol{x}^{(i)}}\right )\\
&= - \sum_{i=1}^{m}(1-y^{(i)})\log h_{\boldsymbol{\theta}'}(\boldsymbol{x}^{(i)}) + y^{(i)}\log \left (1 - h_{\boldsymbol{\theta}'}(\boldsymbol{x}^{(i)}) \right ) \tag{2}
\end{align*}
```

ここで、$\boldsymbol{\theta}' := \boldsymbol{\theta}^{(1)} - \boldsymbol{\theta}^{(0)}$と置いたので少し形が異なっていますが、$\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^{(1)}$を$\boldsymbol{\theta}'$と置けば$(1)$式と$(2)$式の形が一致することがわかると思います。

## 冗長性とパラメータ削減

さて、上の式展開で$\boldsymbol{\theta}' := \boldsymbol{\theta}^{(1)} - \boldsymbol{\theta}^{(0)}$とした際に、2つの$\boldsymbol{\theta}$が一つにまとまったことでパラメータが一つ減ったことにお気づきでしょうか。softmax functionのパラメータは「冗長な」パラメータを持っています。実際、適当なベクトル$\boldsymbol{\psi}$を用いて、

```math
\begin{aligned} P \left( y ^ { ( i ) } = k | \boldsymbol{x}^ { ( i ) } ; \boldsymbol{\theta} \right) & = \frac { \exp \left( \left( \boldsymbol{\theta} ^ { ( k ) } - \boldsymbol{\psi} \right) ^ { \top } \boldsymbol{x} ^ { ( i ) } \right) } { \sum _ { j = 1 } ^ { K } \exp \left( \left( \boldsymbol{\theta} ^ { ( j ) } - \boldsymbol{\psi} \right) ^ { \top } \boldsymbol{x} ^ { ( i ) } \right) } \\ & = \frac { \exp \left( \boldsymbol{\theta} ^ { ( k ) \top } \boldsymbol{x} ^ { ( i ) } \right) \exp \left( - \boldsymbol{\psi} ^ { \top } \boldsymbol{x} ^ { ( i ) } \right) } { \sum _ { j = 1 } ^ { K } \exp \left( \boldsymbol{\theta} ^ { ( j ) \top } \boldsymbol{x} ^ { ( i ) } \right) \exp \left( - \boldsymbol{\psi} ^ { \top } \boldsymbol{x} ^ { ( i ) } \right) } \\ & = \frac { \exp \left( \boldsymbol{\theta} ^ { ( k ) \top } \boldsymbol{x} ^ { ( i ) } \right) } { \sum _ { j = 1 } ^ { K } \exp \left( \boldsymbol{\theta} ^ { ( j ) \top } \boldsymbol{x} ^ { ( i ) } \right) } \end{aligned}
```

と変形できます。上の式から、全てのパラメータベクトルから適当な$\boldsymbol{\psi}$を引いても予測には全く影響しない、ということが分かります。別の言い方をすれば、あるサンプルから訓練されたモデルで、異なるパラメータを持ちながら全く同じ予測を行う分類器が無数に存在するということです。このようなモデルはoverparameterized modelといい、この状態でも学習はできますが、lossのパラメータに関するhessianが逆行列を持たなくなるために直接的なニュートン法の適用ができなくなる問題があるようです。[^1]

そのため(どのくらい一般的なのかはわからないですが)、 $\boldsymbol{\psi} = \boldsymbol{\theta^{(K)}}$として$\boldsymbol{\theta^{(K)}}$を削除することでパラメータベクトルを一つ減らすという方法があります。これが今回$(2)$式の導出で使った方法です。


## 参考文献
[Unsupervised Feature Learning and Deep Learning Tutorial](http://ufldl.stanford.edu/tutorial/supervised/SoftmaxRegression/)
[Is the softmax loss the same as the cross-entropy loss? - Quora](https://www.quora.com/Is-the-softmax-loss-the-same-as-the-cross-entropy-loss)
[Multinomial Logistic Loss vs (Cross Entropy vs Square Error) - Cross Validated](https://stats.stackexchange.com/questions/166958/multinomial-logistic-loss-vs-cross-entropy-vs-square-error)

[^1]: [Unsupervised Feature Learning and Deep Learning Tutorial](http://ufldl.stanford.edu/tutorial/supervised/SoftmaxRegression/) (参考文献と同じ)