ガンベル分布の離散選択モデルからsoftmaxの導出

昔よくやっていた変形を久しぶりに使おうとしたら忘れていたので、備忘録。

ガンベル分布

ガンベル分布（$${G}$$とする）は次の形：

累積確率分布

$$
F_G(x)=\exp \left(-\exp \left(-\frac{x-\mu}{\eta} \right) \right)
$$

確率密度関数

$$
f_G(x) = \frac{1}{\eta} \exp \left(-\frac{x-\mu}{\eta} \right) F_G(x)
$$

期待値、分散は

$$
E(G)=\mu+\gamma  \eta, V(G)=\frac{\pi^2 \eta^2}{6}
$$

但し、$${\gamma}$$ はオイラーの定数で、$${\gamma = 0.5772}$$。

離散選択モデル

離散選択モデル（最も簡単な場合）は、選択肢$${i \in \{1,…,n\}}$$ に対して効用 $${m_i}$$ が定まっていて、誤差項$${ = \varepsilon_i}$$ を何らかの分布に従う確率変数としたとき、$${m_i+\varepsilon_i}$$ が最大となるような$${i}$$ が選択されるというモデル。

$$
i を選択 \Leftrightarrow \argmax\{ m_i + \varepsilon_i\} \text{ s.t. } \varepsilon_i \sim X
$$

softmax

softmaxは、選択肢$${i \in \{1,…,n\}}$$ に対して効用 $${m_i}$$ が定まっていたとき、選択肢$${i}$$ の選択確率が

$$
p_i = \frac{ \exp\left( \alpha m_i \right)}{\sum_{j=1}^n \exp\left( \alpha m_j \right) }
$$

（但し$${\alpha}$$は定数）で定まるモデル。

ガンベル分布の離散選択モデルからsoftmaxの導出

選択確率の式

離散選択モデルの仕組みから（誤差項の累積確率分布関数を$${F(x)}$$、確率密度関数を$${f(x)}$$とする）

$$
p_i = \Pr \left( m_i + \varepsilon_i > m_j + \varepsilon_j  |  \forall j \ne i\right)
$$

書き換えると、

$$
p_i = \Pr \left( \varepsilon_i -(m_j - m_i) > \varepsilon_j  |  \forall j \ne i\right)
$$

で、$${\varepsilon_i }$$ を固定し（$${x_i = \varepsilon_i }$$ と書く）、$${m_j'=m_j - m_i}$$とすると

$$
p_i = \Pr \left( x_i - m_j' > \varepsilon_j  |  \forall j \ne i\right) 
= \prod_{j\ne i} F(x_i - m_j')
$$

となる。$${x_i}$$は$${-\infty}$$ から $${\infty}$$ までを渡って、$${x_i}$$ での確率密度は $${f(x_i)}$$ なので、

$$
p_i = \int_{-\infty}^{\infty} \left(
\prod_{j \ne i} F(x_i-m_j')
\right) f(x_i)dx_i
$$

を得た。

F(x)がガンベル分布の場合

$${F(x)}$$ がガンベル分布の場合、次のように式変形できる。なお、離散選択モデルにおける選択確率は定数の差で不変なので、$${\mu=0,  \varepsilon_i \sim G(0,\eta) }$$とする。

$$
\begin{aligned}
p_i &= \int_{-\infty}^{\infty} \left( \prod_{j \ne i} F_G(x_i-m_j') \right) f_G(x_i)dx_i \\
&= \int_{-\infty}^{\infty} \left( \prod_{j \ne i} F_G(x_i-m_j') \right) \frac{1}{\eta} \exp \left( -\frac{x_i}{\eta} \right) F_G(x_i)dx_i \\
&= \int_{-\infty}^{\infty} \frac{1}{\eta} \exp \left( -\frac{x_i}{\eta} \right)
\left( \prod_{j} F_G(x_i-m_j') \right) dx_i \\
\end{aligned}
$$

（$${m_i'=m_i-m_i=0}$$を使用した。）さて、$${ \prod}$$ の部分だけを見ると、

$$
\begin{aligned}
\prod_j F_G(x_i-m_j')
&= \prod_j \exp \left( -\exp \left( -\frac{x_i-m_j'}{\eta} \right) \right) \\
&= \exp \left( - \sum_j \exp \left( -\frac{x_i}{\eta} +\frac{m_j'}{\eta} \right) \right) \\
&= \exp \left( - \sum_j \exp \left( -\frac{x_i}{\eta} \right) \exp \left( \frac{m_j'}{\eta} \right) \right) \\
&= \exp \left( - \exp \left( -\frac{x_i}{\eta} \right)  \sum_j \exp \left( \frac{m_j'}{\eta} \right) \right) 
\end{aligned}
$$

そこで、$${z_j = x_i / \eta }$$、$${ \sum_j \exp (m_j' / \eta ) = c_i }$$ と置くと、

$$
\prod_j F_G(x_i-m_j') = \exp \left( -c_i \exp \left( -z_i \right)  \right) 
$$

なので、$${p_i}$$ は結局

$$
\begin{aligned}
p_i &= \int_{-\infty}^{\infty} \exp \left( -z_i \right)
 \exp \left( -c_i \exp \left( -z_i \right)  \right)  dz_i \\
&= \int_{-\infty}^{\infty}
 \exp \left( -z_i - c_i \exp \left( -z_i \right)  \right)  dz_i \\
&= [ \frac{1}{c_i} \exp \left( - c_i \exp \left( -z_i \right)  \right) ]_{-\infty}^{\infty} \\
&= \frac{1}{c_i}
\end{aligned}
$$

さらに、$${\alpha = 1/\eta}$$ とすれば

$$
p_i = \frac{1}{c_i} = \frac{1}{\sum_j \exp (\alpha m_j' )}
= \frac{1}{\sum_j \exp (\alpha m_j - \alpha m_i )}
= \frac{\exp(\alpha m_i ) }{ \sum_j \exp (\alpha m_j )}
$$

これは求める softmax の式になっている。