けんごのお屋敷

2016-08-22

機械学習でパラメータ推定 - 最尤推定法 -

最尤推定法 (Maximum Likelyhood や Maximum Likelyhood Estimation と言われ、それぞれ頭文字を取って ML や MLE などとも言われる) は機械学習やコンピュータービジョンなどの分野で良く使われる推定法で、次のような条件付き同時確率を最大化することでパラメータの推定を行います。

$$ \hat{\theta} = \mathop{\mathrm{argmax}}\limits_{\theta} \mathrm{P}(x_1, x_2, \cdots, x_N|\theta) $$

これだけ見て「うん、アレね」と理解できる人はこの記事の対象読者ではなさそうですので、逆にいろいろ教えて下さい。この記事では理論の面から最尤推定法にアタックしてみます。数式成分が多めで、うっとなることもあるかもしれませんが、ゆっくり読んでいきましょう。

※この記事を読むにあたっては、確率論と微分の基礎知識程度は必要です。

尤度

いきなり応用問題から始めると必ず挫折するので、まずは一番簡単な問題設定から始めます。Wikipedia に 最尤推定 のページがありますので、この中で使われている例を参考に話を進めていきましょう。


見た目がまったく同じ 3 枚のコイン A, B, C があります。これらのコインはイカサマで、投げた時に表の出る確率がそれぞれ違います。

  • コイン A は 13 の確率で表が出る
  • コイン B は 12 の確率で表が出る
  • コイン C は 23 の確率で表が出る

この 3 枚のコインを箱の中に入れてシャッフルした後に 1 枚引きます。引いたコインを 10 回投げたら、表が 3 回、裏が 7 回出ました。あなたは A, B, C のどのコインを引いたでしょうか?


この問題設定は極めて単純です。単純すぎて最尤推定法を使わなくても解けるくらい簡単ですが、ここでは敢えて最尤推定法を使って解いてみます。最尤推定法は次の条件付き同時確率を最大化するパラメータ $\hat{\theta}$ を求めることでした。

$$ \hat{\theta} = \mathop{\mathrm{argmax}}\limits_{\theta} \mathrm{P}(x_1, x_2, \cdots, x_N|\ \theta) $$

$x_1$ は 1 回目に投げた時の結果、$x_2$ は 2 回目に投げた時の結果、$x_N$ は N 回目に投げた時の結果になります。コインは全部で 10 回投げることになっているので $N=10$ なのは自明ですよね?これらは、統計学や機械学習の文脈では観測データや学習データとも言われますが、先の問題設定では表が 3 回、裏が 7 回出たということなので、例えばですがこんな風に表せます。(表、裏、みたいな単語だと扱いにくいので、今後は表 = 1、裏 = 0 という風に数値に変換して扱います)

  • $x_1 = 0$ (裏)
  • $x_2 = 1$ (表)
  • $x_3 = 0$ (裏)
  • $x_4 = 0$ (裏)
  • $x_5 = 0$ (裏)
  • $x_6 = 0$ (裏)
  • $x_7 = 1$ (表)
  • $x_8 = 1$ (表)
  • $x_9 = 0$ (裏)
  • $x_{10} = 0$ (裏)

ここでちょっとコイントスについて考えます。問題ではコインを 10 回投げていますが、それぞれのコイントスは独立だと考えます。要するに 1 回目に表か裏かどちらが出ようが、2 回目のトスには何の影響も与えないと考えます (3 回目以降も同様) 。まあ普通そうですよね。各試行が独立だと考えると、同時確率は各試行の確率の積に分解できるので、こう書き換えることができます。

$$ \mathrm{P}(x_1, x_2, \cdots, x_{10}|\ \theta) = \prod_i^{10} \mathrm{P}(x_i|\ \theta) $$

じゃあ $\mathrm{P}$ と $\theta$ は何かというと、確率分布とそのパラメータです。確率分布はそれぞれ固有のパラメータを持っていて、そのパラメータが決まれば分布の形が決まります。たとえば…

  • 正規分布: 平均 $\mu$ と分散 $\sigma^2$ という 2 つのパラメータを持つ
  • t分布: 自由度 $\nu$ というパラメータを持つ
  • ベルヌーイ分布: $\lambda$ というパラメータを持つ

式中ではパラメータのことを $\theta$ と書いてはいますが、これを見てわかるようにパラメータは確率分布によって全然違うのでそれを何か 1 つの文字にまとめているというだけで、確率分布によって様々に変わります。

ここでは箱から引いたコインを投げた時にどれくらいの確率で表が出るのか、ということを知りたいので、確率 $\lambda$ で 1 が出て、確率 $1 - \lambda$ で 0 が出る、というベルヌーイ分布を考えます。たとえば $\lambda = 0.4$ だとすると、40% の確率で 1 が、60% の確率で 0 が出ることになります。ベルヌーイ分布はこのように数式で表すことができます。

$$ \mathrm{P}(x\ |\ \lambda) = \lambda^x (1-\lambda)^{1-x} \ \ \ \ (0 \le \lambda \le 1,\ \ x \in \{0,1\}) $$

これを最尤推定法の式に代入すると最終的にはこう書くことができます。

$$ \begin{eqnarray} \mathrm{P}(x_1, x_2, \cdots, x_{10}|\ \theta) & = & \prod_i^{10} \mathrm{P}(x_i|\ \theta) \\ & = & \prod_i^{10} \lambda^{x_i} (1-\lambda)^{1-x_i} \end{eqnarray} $$

この式がどういうことを意味しているのかをちょっと考えてみます。この式は 尤度 と呼ばれており、パラメータ $\lambda$ が与えられた時に、その $\lambda$ がどれくらい学習データを尤もらしく説明できているかという指標になります。尤度という概念はとてもわかりづらく、言葉だけでは少し理解しにくいので、実際に値を計算してみましょう。たとえば $\lambda$ を適当に 3 つ決めて、それぞれの $\lambda$ で式の値を求めてみます。

  • $\lambda = 0.05$ (5% の確率で表が出るコイン) の場合

$$ \begin{eqnarray} \prod_i^{10} 0.05^{x_i} (1-0.05)^{1-x_i} & = & 0.95 \cdot 0.05 \cdot 0.95 \cdot 0.95 \cdot 0.95 \cdot 0.95 \cdot 0.05 \cdot 0.05 \cdot 0.95 \cdot 0.95 \\ & = & 0.00008729216 \end{eqnarray} $$

  • $\lambda = 0.33$ (33% の確率で表が出るコイン) の場合

$$ \begin{eqnarray} \prod_i^{10} 0.33^{x_i} (1-0.33)^{1-x_i} & = & 0.67 \cdot 0.33 \cdot 0.67 \cdot 0.67 \cdot 0.67 \cdot 0.67 \cdot 0.33 \cdot 0.33 \cdot 0.67 \cdot 0.67 \\ & = & 0.00217803792 \end{eqnarray} $$

  • $\lambda = 0.91$ (91% の確率で表が出るコイン) の場合

$$ \begin{eqnarray} \prod_i^{10} 0.91^{x_i} (1-0.91)^{1-x_i} & = & 0.09 \cdot 0.91 \cdot 0.09 \cdot 0.09 \cdot 0.09 \cdot 0.09 \cdot 0.91 \cdot 0.91 \cdot 0.09 \cdot 0.09 \\ & = & 0.00000003604 \end{eqnarray} $$

これは、最初に学習データとして得られた $x_1, x_2, \cdots, x_{10}$ が どういうコインから生成されたものか という指標をしめしています。10 回中 3 回だけ表が出るという結果が、$\lambda = 0.91$ のコインから生成されることは稀でしょう。$\lambda = 0.91$ ということは表が出る確率が 91% もあるので、3 回とは言わずもっと表が出るはずです。逆に $\lambda = 0.05$ の場合は、表が出る確率は 5% ということなので、10 回中 3 回も表が出ているという結果はあまり納得のいく結果ではありません。結局は $\lambda = 0.33$ というコインが、一番うまく結果を説明しています。

これは、尤度の値を見てみれば一目瞭然です。3 つの尤度を比べてみると $\lambda = 0.33$ の尤度が最も大きく、続いて $\lambda = 0.05$、そして $\lambda = 0.91$ が最も小さくなっています。要するに尤度の値が大きければ大きいほど、うまくデータを説明してくれる尤もらしいパラメータであると言えます。

この辺りまで理解できるとゴールが見えてきます。最初に示した最尤推定法の式を覚えていますか?これは今考えているコインの問題に対しては、最終的にこのように変形できます。

$$ \begin{eqnarray} \hat{\theta} & = & \mathop{\mathrm{argmax}}\limits_{\theta} \mathrm{P}(x_1, x_2, \cdots, x_{10}|\ \theta) \\ & = & \mathop{\mathrm{argmax}}\limits_{\theta} \prod_i^{10} \mathrm{P}(x_i|\ \theta) \\ & = & \mathop{\mathrm{argmax}}\limits_{\lambda} \prod_i^{10} \lambda^{x_i} (1-\lambda)^{1-x_i} \end{eqnarray} $$

これは尤度を最大にする $\lambda$ を求める、という意味の式です。尤度が最大になる $\lambda$ がわかれば、観測された学習データ $x_1, x_2, \cdots, x_{10}$ がどういうコインを使って生成されたものなのか、言い換えればどういうコインを投げると $x_1, x_2, \cdots, x_{10}$ という結果が出てくるのか、ということがわかります。

尤度を最大化するパラメータを推定する、これが最尤推定です。

最適化問題

尤度を最大化するという最適化問題なので、あとは最適化問題を解くためのアルゴリズムに従って解いていくだけです。ここでは最大化したい尤度を $L$ として、このように表します。

$$ L(\lambda) = \prod_i^{10} \lambda^{x_i} (1-\lambda)^{1-x_i} $$

ただし、一般的にはこの $L$ をそのまま最大化するのではなく尤度の対数を取った対数尤度 $\log L$ を最大化します。

$$ \begin{eqnarray} \log L(\lambda) & = & \log \prod_i^{10} \lambda^{x_i} (1-\lambda)^{1-x_i} \\ & = & \sum_i^{10} \log \lambda^{x_i} (1-\lambda)^{1-x_i} \\ & = & \sum_i^{10} \left( x_i \log \lambda + (1 - x_i) \log (1 - \lambda) \right) \end{eqnarray} $$

対数を取る理由は主には、計算を簡単にするためとアンダーフローを防ぐためです。今計算しようとしている尤度は要するに同時確率なので確率の積になっていますが、対数を取ると積を和に変換できます。また、さっき具体的にパラメータを代入して尤度を計算してみてわかったと思いますが、同時確率の計算は値が急激に小さくなっていきます。これも対数を取ることで積が和に変換されるので、値が小さくなることを防げます。

さて、この $\log L(\lambda)$ が最大になるような $\lambda$ を探すことが目的でした。関数の最大値を探す時は微分した結果を = 0 と置いて、微分した変数について解けばよいですよね (関数が単純な凸関数である場合に限られますが)

$$ \begin{eqnarray} \frac{d \log L(\lambda)}{d \lambda} & = & \sum_i^{10} ( \frac{x_i}{\lambda} - \frac{1 - x_i}{1 - \lambda}) \\ & = & \frac{1}{\lambda(1 - \lambda)} \sum_i^{10} (x_i - \lambda) \end{eqnarray} $$

微分結果が求まったので、これを = 0 と置いて $\lambda$ について解きます。

$$ \begin{eqnarray} \frac{1}{\lambda(1 - \lambda)} \sum_i^{10} (x_i - \lambda) & = & 0 \\ \sum_i^{10} x_i - 10 \lambda & = & 0 \\ \lambda & = & \frac{1}{10} \sum_i^{10} x_i \end{eqnarray} $$

これで答えがでました。このような式で求めた $\lambda$ が尤度を最大にします。実際に $x_1, x_2, \cdots, x_{10}$ を代入して計算してみると

$$ \begin{eqnarray} \lambda & = & \frac{1}{10} \sum_i^{10} x_i \\ & = & \frac{1}{10} (0 + 1 + 0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) \\ & = & \frac{3}{10} \end{eqnarray} $$

これは 310 の確率で表が出るコインであれば尤度が最大になるということで、これに一番近いコインは A になり (A は 13 の確率で表が出るコイン)、観測された学習データから考えるとあなたが引いたコインは A だろうということが言えます。

気付いた人もいるかもしれませんが、10 回中 3 回表が出るんだったら、そりゃあ 310 になるのは直感的に当然だろうって思いますよね。これは問題設定が単純ってこともあるかもしれませんが、$x_1, x_2, \cdots, x_{10}$ というデータだけから判断した結果なのでそうなるのも分かる気がしますね。

正規分布のパラメータ推定

最後に正規分布についても例を見て終わりたいと思います。

ベルヌーイ分布のパラメータは $\lambda$ ひとつだけでしたが、正規分布は平均 $\mu$ と分散 $\sigma^2$ の 2 つのパラメータを持っていますので、尤度を最大化するためにそれぞれ $\mu$ と $\sigma^2$ をそれぞれ求めます。今回は確率分布 $\mathrm{P}$ に正規分布を使うので尤度はこうなります。

$$ \begin{eqnarray} L & = & \mathrm{P}(x_1, x_2, \cdots, x_N|\ \theta) \\ & = & \prod_i^N \mathrm{P}(x_i|\ \theta) \\ & = & \prod_i^N \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x_i - \mu)^2}{2\sigma^2} \right) \end{eqnarray} $$

同じようにこの尤度を $L$ として対数を取ると、このように変形できます。

$$ \begin{eqnarray} \log L & = & \log \prod_i^N \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x_i - \mu)^2}{2\sigma^2} \right) \\ & = & \sum_i^N \log \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x_i - \mu)^2}{2\sigma^2} \right) \\ & = & \sum_i^N \left( -\log \sqrt{2 \pi} -\frac{1}{2}\log \sigma^2 - \frac{(x_i - \mu)^2}{2\sigma^2} \right) \end{eqnarray} $$

ベルヌーイ分布を考えた時と同様に、この対数尤度関数を $\mu$ と $\sigma^2$ について微分して、それぞれ = 0 と置いて解いていきます。正規分布ではパラメータが 2 つある多変数関数なので偏微分になります。

まずは $\mu$ で偏微分をするところから。

$$ \begin{eqnarray} \frac{\partial \log L}{\partial \mu} & = & \sum_i^N \left(0 + 0 + \frac{(x_i - \mu)}{\sigma^2} \right) \\ & = & \frac{1}{\sigma^2} \sum_i^N (x_i - \mu) \end{eqnarray} $$

これを = 0 と置いて $\mu$ について解いていきます。

$$ \begin{eqnarray} \frac{1}{\sigma^2} \sum_i^N (x_i - \mu) & = & 0 \\ \sum_i^N x_i - N\mu & = & 0 \\ \mu & = & \frac{1}{N} \sum_i^N x_i \end{eqnarray} $$

これでまずは尤度を最大にする $\mu$ が見つかりました。次は $\sigma^2$ について解いていきます。まずは偏微分から。

$$ \begin{eqnarray} \frac{\partial \log L}{\partial \sigma^2} & = & \sum_i^N \left(0 - \frac{1}{2\sigma^2} + \frac{(x_i - \mu)^2}{2\sigma^4} \right) \\ & = & -\frac{N}{2\sigma^2} + \frac{1}{2\sigma^4}\sum_i^{N}(x_i-\mu)^2 \end{eqnarray} $$

同じようにこれを = 0 と置いて $\sigma^2$ について解きます。

$$ \begin{eqnarray} -\frac{N}{2\sigma^2} + \frac{1}{2\sigma^4}\sum_i^{N}(x_i-\mu)^2 & = & 0 \\ -N\sigma^2 + \sum_i^{N}(x_i-\mu)^2 & = & 0 \\ \sigma^2 & = & \frac{1}{N}\sum_i^{N}(x_i-\mu)^2 \end{eqnarray} $$

これで尤度を最大にする正規分布のパラメータ $\mu$ と $\sigma^2$ がわかりました。

$$ \begin{eqnarray} \mu & = & \frac{1}{N} \sum_i^N x_i \\ \sigma^2 & = & \frac{1}{N}\sum_i^{N}(x_i-\mu)^2 \end{eqnarray} $$

これは純粋なデータの平均と分散になっています。

まとめ

尤度を最大化してパラメータを推定するための最尤推定法を紹介してきました。学習データからモデルのパラメータ $\theta$ を訓練することが目的ではなく、最終的にやりたいことは新しい未知データがどれだけモデルに適合しているのか推論することです。最尤推定は比較的簡単な手法だと思うので、試しに実装してみると面白いと思います。

  • このエントリーをはてなブックマークに追加

2016-06-16

やる夫で学ぶ機械学習 - 対数尤度関数 -

やる夫で学ぶ機械学習シリーズの第 6 回です。ロジスティック回帰の目的関数である尤度関数をもう少し詳しくみて、線形分離不可能な問題にどのように適用していくのかを見ていきます。

第 5 回はこちら。やる夫で学ぶ機械学習 - ロジスティック回帰 -

目次はこちら。やる夫で学ぶ機械学習シリーズ

対数尤度関数

やらない夫
尤度関数を微分してパラメータ $\boldsymbol{\theta}$ の更新式を求めてみようか。

やる夫
もう脳みそパンパンですお。

やらない夫
その前に、尤度関数はそのままだと扱いにくいから、少し変形しよう。

やる夫
扱いにくい?どういうことかお?

やらない夫
まず同時確率という点だ。確率なので 1 以下の数の掛け算の連続になることはわかるな?

やる夫
確かに、確率の値としては 0 より大きくて 1 より小さいものだお。

やらない夫
1 より小さい数を何度も掛け算すると、どんどん値が小さくなっていくだろう。コンピュータで計算する場合はそれは致命的な問題だ。

やる夫
あー、オーバーフローの逆かお。アンダーフロー。

やらない夫
次に掛け算という点だ。掛け算は足し算に比べて計算が面倒だ。

やる夫
小数点の計算とかあんまりやりたくないお。

やらない夫
そこで一般的には尤度関数の対数をとったもの、対数尤度関数を使う。

$$ \log L(\boldsymbol{\theta}) = \log \prod_{i=1}^n P(y^{(i)}=1|\boldsymbol{x})^{y^{(i)}} P(y^{(i)}=0|\boldsymbol{x})^{1-y^{(i)}} $$

やる夫
目的関数に対して勝手に対数をとったりして、答え変わらないのかお?

やらない夫
問題ない。対数関数は単調増加な関数だからだ。対数関数のグラフの形を覚えているか?

やる夫
確かこんな感じのグラフだお。

やらない夫
それで正解だ。グラフがずっと右上がりになってることがわかるだろう。つまり単調増加な関数ってのは $x_1 < x_2$ ならば $f(x_1) < f(x_2)$ となるような関数 $f(x)$ だということだ。

やる夫
なるほど、確かに $\log(x)$ はそういう風になっているお。

やらない夫
$\log$ は単調増加関数だから、今考えいてる対数尤度関数についても $L(\boldsymbol{\theta_1}) < L(\boldsymbol{\theta_2})$ であれば $\log L(\boldsymbol{\theta_1}) < \log L(\boldsymbol{\theta_2})$ ということが言えるだろう。要するに $L(\boldsymbol{\theta})$ を最大化することと $\log L(\boldsymbol{\theta})$ を最大化することは同じことなんだ。

やる夫
ふーん、よく考えられてるお。

やらない夫
では、対数尤度関数を少し変形して $f_{\boldsymbol{\theta}}$ を使って表してみよう。

$$ \begin{eqnarray} \log L(\boldsymbol{\theta}) & = & \log \prod_{i=1}^n P(y^{(i)}=1|\boldsymbol{x})^{y^{(i)}} P(y^{(i)}=0|\boldsymbol{x})^{1-y^{(i)}} \\ & = & \sum_{i=1}^n \left( \log P(y^{(i)}=1|\boldsymbol{x})^{y^{(i)}} + \log P(y^{(i)}=0|\boldsymbol{x})^{1-y^{(i)}} \right) \\ & = & \sum_{i=1}^n \left( y^{(i)} \log P(y^{(i)}=1|\boldsymbol{x}) + (1-y^{(i)}) \log P(y^{(i)}=0|\boldsymbol{x}) \right) \\ & = & \sum_{i=1}^n \left( y^{(i)} \log f_{\boldsymbol{\theta}}(\boldsymbol{x}) + (1-y^{(i)}) \log (1-f_{\boldsymbol{\theta}}(\boldsymbol{x}) \right) \end{eqnarray} $$

やる夫
うっ、ちょっと式変形を追うのが大変だお…

やらない夫
実際には 2 行目は $\log(ab) = \log a + \log b$ という性質を、3 行目は $\log a^b = b \log a$ という性質を使っているだけだ。

やる夫
$\log$ の性質は覚えてるけど、最後の行はなんでそうなるんだお。

やらない夫
確率の定義からだ。ここでは確率変数の取る値としては $y=1$ か $y=0$ かしかないから、$P(y^{(i)}=1|\boldsymbol{x}) = f_{\boldsymbol{\theta}}(\boldsymbol{x})$ ならば $P(y^{(i)}=0|\boldsymbol{x}) = 1 - f_{\boldsymbol{\theta}}(\boldsymbol{x})$ となる。

やる夫
あー、そうか。全部の確率を足すと 1 になるんだったお。

やらない夫
ここまでで俺たちは目的関数として対数尤度関数 $\log L(\boldsymbol{\theta})$ を定義した。次はどうする?

やる夫
$\log L(\boldsymbol{\theta})$ を $\boldsymbol{\theta}$ の各要素 $\theta_j$ で微分…かお?

やらない夫
ではこれを微分していこう。

$$ \frac{\partial}{\partial \theta_j} \sum_{i=1}^n \left( y^{(i)} \log f_{\boldsymbol{\theta}}(\boldsymbol{x}) + (1-y^{(i)}) \log (1-f_{\boldsymbol{\theta}}(\boldsymbol{x}) \right) $$

やる夫
ちょっと何言ってるかよくわからん式だお…

やらない夫
回帰の時にやったように、合成関数の微分を使うんだ。

やる夫
えーと、要するに…こうかお?

$$ \frac{\partial \log L(\boldsymbol{\theta})}{\partial f_{\boldsymbol{\theta}}} \cdot \frac{\partial f_{\boldsymbol{\theta}}}{\partial \theta_j} $$

やらない夫
それでいい。ひとつずつ微分していくんだ。まず第一項はどうなるだろう?

やる夫
第一項は $\log L(\boldsymbol{\theta})$ を $f_{\boldsymbol{\theta}}$ で微分するんだから…えーっと、$\log(x)$ の微分は $\frac{1}{x}$ でよかったかお?

$$ \begin{eqnarray} \frac{\partial \log L(\boldsymbol{\theta})}{\partial f_{\boldsymbol{\theta}}} & = & \frac{\partial}{\partial f_{\boldsymbol{\theta}}}\sum_{i=1}^n \left( y^{(i)} \log f_{\boldsymbol{\theta}}(\boldsymbol{x}) + (1-y^{(i)}) \log (1-f_{\boldsymbol{\theta}}(\boldsymbol{x}) \right) \\ & = & \sum_{i=1}^n \left( \frac{y^{(i)}}{f_{\boldsymbol{\theta}}(\boldsymbol{x})} - \frac{1-y^{(i)}}{1-f_{\boldsymbol{\theta}}(\boldsymbol{x})} \right) \\ \end{eqnarray} $$

やる夫
一気に第二項もやってしまうお。これも合成関数の微分を使うお。$z = 1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x})$ と置いて $f_{\boldsymbol{\theta}}(\boldsymbol{x}) = z^{-1}$ とすると

$$ \begin{eqnarray} \frac{\partial f_{\boldsymbol{\theta}}}{\partial \theta_j} & = & \frac{\partial f_{\boldsymbol{\theta}}}{\partial z} \cdot \frac{\partial z}{\partial \theta_j} \\ & = & -\frac{1}{z^2} \cdot -x_j \exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x}) \\ & = & \frac{x_j \exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})}{(1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x}))^2} \end{eqnarray} $$

やる夫
できたお!これが微分結果だお。

$$ \frac{\partial \log L(\boldsymbol{\theta})}{\partial \theta_j} = \sum_{i=1}^n \left( \frac{y^{(i)}}{f_{\boldsymbol{\theta}}(\boldsymbol{x})} - \frac{1-y^{(i)}}{1-f_{\boldsymbol{\theta}}(\boldsymbol{x})} \right) \frac{x_j \exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})}{(1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x}))^2} $$

やらない夫
そうだ、と言いたいところだが、ただ計算すればいいってもんじゃないだろ…やる夫はこれを見てどう思う?

やる夫
どう思うも何も、これでパラメータの更新式ができるお…まあ、二度と見たくもないような複雑な式ですお。

やらない夫
そう、実はまだ複雑なんだ。もう少し式変形を進めて綺麗な形にできるんだが…

やる夫
やる夫の計算力が足りないってことかお!

やらない夫
いや、ここまでできただけでも十分だ。一緒に考えよう。まず、後ろの方の $\exp$ が含まれている式の方を見てみようか。やる夫は全部まとめているが、そこをあえてこんな風に分けてみよう。

$$ \frac{x_j \exp(\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})}{(1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x}))^2} = \frac{1}{1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x})} \cdot \frac{\exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})}{1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x})} \cdot x_j $$

やる夫
えっ、わざわざ分解するのかお。

やらない夫
そうするとこういう風に $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ を使って書けるだろう。

$$ \frac{1}{1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x})} \cdot \frac{\exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})}{1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x})} \cdot x_j = f_{\boldsymbol{\theta}}(\boldsymbol{x}) \cdot (1 - f_{\boldsymbol{\theta}}(\boldsymbol{x})) \cdot x_j $$

やる夫
あーなるほど。確かにやらない夫の言う通りに変形できそうだお。でも、第二項が $1 - f_{\boldsymbol{\theta}}(\boldsymbol{x})$ になるのはわかるけど、そんなの気付けないお…

やらない夫
式を変形する作業は慣れの問題も大きいだろうから、できなかったといってヘコむことはない。ちなみにシグモイド関数、ここでは $\sigma(x)$ と置こう、これの微分が $\sigma(x)(1-\sigma(x))$ になるのは有名だな。

やる夫
確かに $f_{\boldsymbol{\theta}}$ はシグモイド関数で、それを微分した形はそうなってるお。

やらない夫
では、この式を微分結果に代入してみよう。約分した後に展開して整理すると最終的にはこんな形になる。

$$ \begin{eqnarray} \frac{\partial \log L(\boldsymbol{\theta})}{\partial \theta_j} & = & \sum_{i=1}^n \left( \frac{y^{(i)}}{f_{\boldsymbol{\theta}}(\boldsymbol{x})} - \frac{1-y^{(i)}}{1-f_{\boldsymbol{\theta}}(\boldsymbol{x})} \right) f_{\boldsymbol{\theta}}(\boldsymbol{x}) (1 - f_{\boldsymbol{\theta}}(\boldsymbol{x})) x_j \\ & = & \sum_{i=1}^n \left( y^{(i)}(1 - f_{\boldsymbol{\theta}}(\boldsymbol{x})) - (1-y^{(i)})f_{\boldsymbol{\theta}}(\boldsymbol{x}) \right) x_j \\ & = & \sum_{i=1}^n \left(y^{(i)} - f_{\boldsymbol{\theta}}(\boldsymbol{x}) \right) x_j \end{eqnarray} $$

やる夫
めちゃくちゃ単純な式になったお…やらない夫すごすぎるお。

やらない夫
あとはいつものように、この式からパラメータ更新式を導出するんだ。ただし、回帰の時は最小化すればよかったが、今回は最大化なので注意が必要だ。そこが違うので、ただ代入すればいいというわけじゃない。

やる夫
あ、確かにそうだお…もうすぐ終わりそうなのに、ここにきてまた壁がでてきたお。

やらない夫
そう難しく考えるな。最大化問題を最小化問題に置き換える簡単な方法がある。符号を反転させればいいだけだ。

やる夫
まじかお?

やらない夫
単純だろう。$f(x)$ を最大化させる問題と、その符号を反転させた $-f(x)$ を最小化させる問題はまったく同じ問題だ。

やる夫
希望が見えてきたお。要するにこれまでは $\log L(\boldsymbol{\theta})$ を最大化することを考えてきたけど、これからは $-\log L(\boldsymbol{\theta})$ を最小化することを考えればいいってことかお?

やらない夫
その通りだ。符号が反転したんだから、微分結果の符号も反転する。$L^{-}(\boldsymbol{\theta}) = -\log L(\boldsymbol{\theta})$ と置くと、こうなるな。

$$ \frac{\partial L^{-}(\boldsymbol{\theta})}{\partial \theta_j} = \sum_{i=1}^n \left(f_{\boldsymbol{\theta}}(\boldsymbol{x}) - y^{(i)} \right) x_j $$

やる夫
てことは、パラメータ更新式は、こうかお?

$$ \theta_j := \theta_j - \eta \sum_{i=1}^n \left(f_{\boldsymbol{\theta}}(\boldsymbol{x}) - y^{(i)} \right) x_j $$

やらない夫
よし、できたな。

線形分離不可能問題

やらない夫
では、いよいよ線形分離不可能な問題にも挑戦していこうか。

やる夫
待ってましたお。

やらない夫
これが線形分離不可能だということはもういいな?

やる夫
わかってるお。

やらない夫
線形分離不可能な問題は、すなわち直線では分離できないということだ。であれば、曲線で分離すればいいという発想に自然といきつく。

やる夫
お、もしかして多項式回帰の時にやったように、次数を増やしてみるってことかお?

やらない夫
勘がいいな。よし、これは 2 次元の話なので、素性としては $x_1$ と $x_2$ の 2 つがある。そこに 3 つ目の素性として $x_1^2$ を加える事を考えて見るんだ。

やる夫
こういうことかお?

$$ \boldsymbol{\theta} = \left[ \begin{array}{c} \theta_0 \\ \theta_1 \\ \theta_2 \\ \theta_3 \end{array} \right] \ \ \ \boldsymbol{x} = \left[ \begin{array}{c} 1 \\ x_1 \\ x_2 \\ x_1^2 \end{array} \right] $$

やらない夫
そうだな。つまり $\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x}$ はこうだ。大丈夫か?

$$ \boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x} = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_1^2 $$

やる夫
わかるお。

やらない夫
また適当に $\boldsymbol{\theta}$ を決めてみよう。そうだな、たとえば $\boldsymbol{\theta}$ がこうなった時、それぞれ $y=1$ と $y=0$ と分類される領域はどこになる?

$$ \boldsymbol{\theta} = \left[ \begin{array}{c} \theta_0 \\ \theta_1 \\ \theta_2 \\ \theta_3 \end{array} \right] = \left[ \begin{array}{c} 0 \\ 0 \\ 1 \\ -1 \end{array} \right] $$

やる夫
えーっと、要するに $\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x} \ge 0$ を考えればいいんだから…前と同じように変形してみるお。

$$ \begin{eqnarray} \boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x} = x_2 - x_1^2 & \ge & 0 \\ x_2 & \ge & x_1^2 \end{eqnarray} $$

やる夫
こんな感じかお?

やらない夫
その通りだ。以前は決定境界が直線だったが、今は曲線になっているのが見て取れるだろう。

やる夫
見た感じ、この決定境界だとまったく分類できてないように見えるけど、それはいつものようにやらない夫神が適当に $\boldsymbol{\theta}$ を決めたから、ってことでいいかお?

やらない夫
もう慣れてきたようだな。やる夫の言う通りだ。

やる夫
じゃ、これをさっき求めたパラメータ更新式を使って、$\boldsymbol{\theta}$ を学習していけばいいってことかお。

やらない夫
これで線形分離不可能な問題も解けるようになったな。

やる夫
楽勝だお!

やらない夫
あとは、好きなように次数を増やせば複雑な形の決定境界にすることができる。たとえばさっきは素性として $x_1^2$ を増やしたが $x_2^2$ も増やすと、円状の決定境界ができる。

やる夫
ロジスティック回帰のパラメータ更新って、最初に回帰で考えた時と同じように全データで学習してるけど、ここにも確率的勾配降下法って使えるのかお?

やらない夫
もちろん使えるぞ。

やる夫
ロジスティック回帰って万能だお。

やらない夫
やる夫はいつも結論を出すのが早すぎだな。どんな問題に対しても万能なアルゴリズムなんて存在しないんだから適材適所で使っていかなければならない。

やる夫
今のやる夫はまだパーセプトロンとロジスティック回帰しか知らないんだから、ロジスティック回帰の方がやる夫にとっては有能な分類アルゴリズムだお。

やらない夫
それもそうだな。分類器はいろいろなアルゴリズムがあるから、勉強していくと楽しいぞ。

やる夫
自習なんて面倒くさいお…

やらない夫
本当に面倒くさがりなんだな、お前…

やる夫
天性だお。

やらない夫
自慢するところかよ。しかしこれまでだいぶ理論を説明してきたが、理論だけじゃなくて実際になにか作ってみることも大事だ。理解度が飛躍的に上がるぞ。

やる夫
じゃ、やっぱり前に言ってたアレ、作るお…

やらない夫
その熱意には負けるよ。


やる夫で学ぶ機械学習 - 過学習 - へ続く。

  • このエントリーをはてなブックマークに追加

2016-06-06

やる夫で学ぶ機械学習シリーズ

これは、機械学習に関する基礎知識をまとめたシリーズ記事の目次となる記事です。まとめることで知識を体系化できて自分自身の為にもなるので、こういうアウトプットをすることは大事だと思っています。ただ、普通にブログ記事を書くのも面白くないので、ちょっといつもとは違う方法でやってみようというのが今回のシリーズ記事。

2 ちゃんねるのキャラクターが登場人物として出てきて、彼らが会話して話が進んでいく「やる夫で学ぶシリーズ」という講義調の形式のものがあります。個人的にはやる夫で学ぶシリーズや 数学ガール のような会話形式で話が進んでいく読み物は読みやすいと思っています。さらに、先日みつけた やる夫で学ぶディジタル信号処理 という資料がとてつもなくわかりやすく、これの真似をして書いてみようと思い至りました。記事中のやる夫とやらない夫のアイコンは http://matsucon.net/material/mona/ こちらのサイトの素材を使わせていただきました。

第 2 回まで半年ほど前に公開していましたが、その後ブログ執筆の熱が冷めて放置されていました。が、実は下書きだけなら乱雑ながら第 5 回までは書いていて、周りにいる機械学習入門中の知り合い数名から下書きあるなら公開して欲しいと言われたので、お蔵入りさせるのも勿体ないし一気に清書して、この目次記事をつけて公開することにしました。今後、このシリーズ記事が増えるかどうかはわかりません。

まえがき

このシリーズでは実践的な内容というよりかは、基礎的で理論的な部分をまとめていきます。機械学習をやり始めるにあたってまず最初にやったほうが良いのは、こういった座学のような記事を頑張って読むよりかは、やってみた系の記事を読みながら実際に手を動かしてコーディングしてみることです。いきなり機械学習の本や数式を眺めて理論から理解し始めるのは、数学に自信がある人や素養がある人以外は難しく、挫折してしまう原因となります。

今は良い時代になっていて、フレームワークを基盤として少しのコードを書いて、公開されている無料の学習用データを使えば、それらしいものが出来てしまいます。そういうもので感覚を掴んでから、理論を理解するのでも遅くはないと思っています。

とはいえ、プログラマであれば中身を知らないものをアレコレ触るのは怖さがあるというもの。理論の方に手をだしてみたくなったりもします。座学系の記事は、このブログ以外にもたくさん転がっているのでイロイロ読み比べて知識を自分のものにしていくのが大事です。一晩でなんとかなるものでもないですし、じっくりやっていきましょう。

対象

  • 機械学習って最近よく聞くけど中身を良くしらない人
  • 中身しらないけど機械学習って楽しそうだしなんか勉強してみたい人
  • 数学が好きな人
  • ドヤ顔で機械学習のことを話したい人

※上級者向けではありません。どちらかというとむしろ初学者向けです。

目次

記事 1 つ 1 つが長く、分割していくうちに記事数が多くなってきたので、目次を作りました。

勉強すると楽しいと思うよ

  • SVM
  • オーバーフィッティング
  • k-means
  • GMM
  • ニューラルネットワーク

とかその辺。

  • このエントリーをはてなブックマークに追加

2016-06-04

やる夫で学ぶ機械学習 - ロジスティック回帰 -

やる夫で学ぶ機械学習シリーズの第 5 回です。分類問題を解くためのロジスティック回帰を見ていきます。

第 4 回はこちら。やる夫で学ぶ機械学習 - パーセプトロン -

目次はこちら。やる夫で学ぶ機械学習シリーズ

ロジスティック回帰

やる夫
分類問題を解くための素晴らしいアルゴリズムがあると聞きましたお。

やらない夫
今日は展開が早いな。

やる夫
回りくどいのは終わりだお。

やらない夫
では、今日はロジスティック回帰の話をしていこう。ロジスティック回帰は、パーセプトロンのように基本的には二値分類の分類器を構築するためのものだ。

やる夫
パーセプトロンよりは使い物になるのかお?

やらない夫
もちろんさ。ロジスティック回帰はいろんなところで使われているし、線形分離不可能な問題も解ける。

やる夫
それはナイスだお。

やらない夫
いつものように最初は簡単な具体例を示して概要を見ていこうか。

やる夫
よろしくお願いしますお。

やらない夫
問題設定はパーセプトロンの時と同じものを使おう。つまり、色を暖色か寒色に分類することを考えるんだ。

やる夫
それ、線形分離可能な問題だお?線形分離不可能な問題やらないのかお?

やらない夫
物事には順序ってものがあるだろう。先に基礎からやるんだよ。ロジスティック回帰も、もちろん線形分離可能な問題は解ける。まずそこから入って、その応用で最後に線形分離不可能な問題を見ていこう。

やる夫
基礎力つけるの面倒くさいけど、わかったお…

やらない夫
ロジスティック回帰は分類を確率として考えるんだ。

やる夫
確率?暖色である確率が 80%、寒色である確率が 20%、みたいな話ってことかお?

やらない夫
そうだ、いつもとぼけた顔してる割には冴えてるじゃないか。

やる夫
顔は生まれつきだお。文句いうなお。

やらない夫
暖色、寒色のままでは扱いにくいのはパーセプトロンと同じだから、ここでは暖色を $1$、寒色を $0$ と置くとしよう。

やる夫
あれ、寒色は $-1$ じゃないのかお?

やらない夫
クラス毎の値が異なっていれば別になんでもいいんだが、パーセプトロンの時に暖色が $1$ で寒色が $-1$ にしたのは、そうした方が重みの更新式が簡潔に書けるからだ。

やる夫
なるほど。ロジスティック回帰の場合は暖色を $1$ で寒色を $0$ にした方が、重みの更新式が簡潔に書き表せるってことかお?

やらない夫
そういうことだな。話を進めよう。回帰の時に、未知のデータ $\boldsymbol{x}$ に対応する値を求めるためにこういう関数を定義したのを覚えているか?

$$ f_{\boldsymbol{\theta}}(\boldsymbol{x}) = \boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x} $$

やる夫
覚えてるお。学習用データに最も良くフィットするパラメータ $\boldsymbol{\theta}$ を求めた時だお。あの時は最急降下法か確率的勾配降下法を使ってパラメータ $\boldsymbol{\theta}$ の更新式を導出したんだったお。

やらない夫
ロジスティック回帰でも考え方は同じだ。未知のデータがどのクラスに分類されるかを求めたい時に、それを分類してくれるための関数が必要になるな。

やる夫
パーセプトロンでやった時の識別関数 $f_{\boldsymbol{w}}$ みたいなもんかお?

やらない夫
そうだな。今回も回帰の時と同じように $\boldsymbol{\theta}$ を使うことにして、ロジスティック回帰の関数をこのように定義しよう。

$$ f_{\boldsymbol{\theta}}(\boldsymbol{x}) = \frac{1}{1 + \exp(-\boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{x})} $$

やる夫
急に難易度が上がるのは、このシリーズのセオリーかお。

やらない夫
ぱっと見て難しそうだと感じるのはわかるが、落ち着いて考えるんだ。第一印象で無理かどうかを決めるのは良くないぞ。

やる夫
$\exp(x)$ ってのは $\mathrm{e}^x$ ってことかお?

やらない夫
そうだ。この関数は一般的にシグモイド関数と呼ばれるんだが、$\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x}$ を横軸、$f_{\boldsymbol{\theta}}$ を縦軸だとすると、グラフの形はこんな風になっている。

やる夫
お、ものすごくなめらかな形をしているお。

やらない夫
特徴としては、$\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} = 0$ の時に $f_{\boldsymbol{\theta}} = 0.5$ になっている。それから、グラフを見ればすぐわかると思うが $0 \le f_{\boldsymbol{\theta}} \le 1$ だ。

やる夫
グラフの形なんか示してどうするんだお。

やらない夫
目に見えるように表現すると見えないモノが見えてくる。今は、分類を確率で考えようとしているんだ。覚えているか?

やる夫
覚えてるお。あ…そうか、シグモイド関数は $0 \le f_{\boldsymbol{\theta}} \le 1$ だから確率として扱える、ってことかお。

やらない夫
その通りだ。ここからは、未知のデータ $\boldsymbol{x}$ が暖色、つまり $y=1$ である確率を $f_{\boldsymbol{\theta}}$ とするんだ。

$$ P(y=1|\boldsymbol{x}) = f_{\boldsymbol{\theta}}(\boldsymbol{x}) $$

やらない夫
具体例を見てみようか。そうだな、$f_{\boldsymbol{\theta}}(\boldsymbol{x})$ を計算すると $0.7$ になったとしよう。これはどういう状態だ?

やる夫
あ、えーっと…$f_{\boldsymbol{\theta}}(\boldsymbol{x}) = 0.7$ ってことは、暖色である確率が 70% ってことかお?逆に寒色である確率は 30%。普通に考えて $\boldsymbol{x}$ は暖色ってことになるお。

やらない夫
では今度は、$f_{\boldsymbol{\theta}}(\boldsymbol{x}) = 0.2$ の時はどうだろう。

やる夫
暖色が 20% で、寒色が 80% だから $\boldsymbol{x}$ は寒色だお。

やらない夫
やる夫は今おそらく、$f_{\boldsymbol{\theta}}(\boldsymbol{x})$ の閾値を $0.5$ としてクラスを振り分けているはずだ。

\begin{eqnarray} y = \begin{cases} 1 & (f_{\boldsymbol{\theta}}(\boldsymbol{x}) \ge 0.5) \\[5pt] 0 & (f_{\boldsymbol{\theta}}(\boldsymbol{x}) < 0.5) \end{cases} \end{eqnarray}

やる夫
あぁ、別に意識はしてなかったけど、確かにそうだお。$f_{\boldsymbol{\theta}}(\boldsymbol{x}) \ge 0.5$ なら暖色だと思うし、逆は寒色だお。

やらない夫
$f_{\boldsymbol{\theta}}(\boldsymbol{x}) \ge 0.5$ というのは、もっと詳しく見るとどういう状態だ?シグモイド関数のグラフを思い出して考えてみるんだ。

やる夫
んー…?シグモイド関数は $\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} = 0$ の時に $f_{\boldsymbol{\theta}}(\boldsymbol{x}) = 0.5$ だったお…あっ、要するに $f_{\boldsymbol{\theta}}(\boldsymbol{x}) \ge 0.5$ ってことは $\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} \ge 0$ ってことかお?

やらない夫
正解だ。さっきの場合分けの条件式の部分を書き直すとこうだな。

\begin{eqnarray} y = \begin{cases} 1 & (\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} \ge 0) \\[5pt] 0 & (\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} < 0) \end{cases} \end{eqnarray}

やらない夫
シグモイド関数のグラフをみると、こんな風に分類される感じだな。

やる夫
なるほど、わかりやすいお。でも、条件式の部分って $f_{\boldsymbol{\theta}}(\boldsymbol{x}) \ge 0.5$ でも $\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} \ge 0$ でも同じ意味ならなんでわざわざ書き直すんだお?

やらない夫
では、今度はパーセプトロンの時に見たような、横軸が赤($x_1$)、縦軸が青($x_2$) のグラフを考えてみようか。

やる夫
あぁ、色をプロットしていたアレかお。

やらない夫
今回の問題、素性としては赤 ($x_1$) と青 ($x_2$) の 2 次元だが、回帰の時と同じように $\theta_0$ と $x_0$ も含めて、全体としては 3 次元ベクトルで考えるぞ。いいか?

やる夫
大丈夫だお。$x_0 = 1$ は固定だったお。

やらない夫
具体的に考えるために、適当にパラメータ $\boldsymbol{\theta}$ を決めよう。そうだな、こういう $\boldsymbol{\theta}$ があった時、暖色である場合の条件式 $\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} \ge 0$ をグラフに表すとどうなる?

$$ \boldsymbol{\theta} = \left[ \begin{array}{c} \theta_0 \\ \theta_1 \\ \theta_2 \end{array} \right] = \left[ \begin{array}{c} -100 \\ 2 \\ 1 \end{array} \right] $$

やる夫
ん、条件式をグラフに…とりあえず $\boldsymbol{\theta}$ を代入して、わかりやすいように変形してみるお…

$$ \begin{eqnarray} \boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} = -100 + 2 x_1 + x_2 & \ge & 0 \\ x_2 & \ge & - 2 x_1 + 100 \end{eqnarray} $$

やる夫
これをグラフに…こうかお?

やらない夫
ここまでくれば $\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} < 0$ の場合がどうなるかも想像できるな?

やる夫
今度はさっきの反対側ってことかお。

やらない夫
つまり $\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} = 0$ という直線を境界線として、一方が暖色($y=1$)、もう一方が寒色($y=0$)、とクラス分けできるというわけだ。

やる夫
これは直感的でわかりやすいお!パーセプトロンの時にも $\boldsymbol{w} \cdot \boldsymbol{x} = 0$ というクラスを分類するための線が出てきたけど、それと同じものってことかお。

やらない夫
そうだな。このようなクラスを分割する線を決定境界、英語では Decision Boundary と呼ぶ。

やる夫
この決定境界、暖色と寒色を分類する線としては全く正しくなさそうだけど、それはやらない夫が適当にパラメータの $\boldsymbol{\theta}$ を決めたから、ってことかお?

やらない夫
そういうことだ。ということは、これから何をやっていくのかは、想像つくだろう?

やる夫
正しいパラメータ $\boldsymbol{\theta}$ を求めるために、目的関数を定義して、微分して、パラメータの更新式を求める、であってるかお?

やらない夫
よくわかってるじゃないか。

尤度関数

やる夫
あとは回帰と同じなら楽勝だお。今日はもう帰ってオンラインゲームでもやるお。

やらない夫
そうだったら良かったんだが、世の中そんなに甘くないぞ。

やる夫
はっ…そういえば今日は週 1 のメンテナンス日だったお…

やらない夫
お前、そういうことじゃないだろ、常識的に考えて…。ロジスティック回帰は、二乗誤差の目的関数だとうまくいかないから別の目的関数を定義するんだ。最初にやった回帰と同じ手法ではやらない。

やる夫
そうなのかお…帰ってもやることないから、やらない夫の講義に付き合ってやるお。

やらない夫
その上から目線、癪に障るが…ロジスティック回帰の目的関数を考えよう。パーセプトロンの時に準備した学習用データについて、さっき俺が適当に決めたパラメータ $\boldsymbol{\theta}$ を使って、実際に $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ を計算してみよう。ここで示す $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ の計算結果は全く厳密ではないが、イメージをつかむにはそれで十分だろう。

クラス $y$ $f_{\boldsymbol{\theta}}(\boldsymbol{x})$
      #d80055 暖色 1 0.00005
      #c80027 暖色 1 0.00004
      #9c0019 暖色 1 0.00002
      #2c00c8 寒色 0 0.99991
      #120078 寒色 0 0.99971
      #40009f 寒色 0 0.99953

やらない夫
$f_{\boldsymbol{\theta}}(\boldsymbol{x})$ は $\boldsymbol{x}$ が暖色である確率だと定義した。これは覚えているな。

やる夫
大丈夫だお。

やらない夫
では、それを踏まえた上で、$y$ と $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ はどういう関係にあるのが理想的だと思う?

やる夫
えっ、えーっと… $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ は $\boldsymbol{x}$ が暖色である確率なんだから…正しく分類されるためには、$y=1$ の時に $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ が $1$ に近くて、$y=0$ の時に $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ が $0$ に近い方がいい、ってことかお?

やらない夫
そうだな。理想の状態はやる夫の言った通りで正解だが、以下のようにも言い換えることができる。

  • $y=1$ の時は $P(y=1|\boldsymbol{x})$ が最大になって欲しい
  • $y=0$ の時は $P(y=0|\boldsymbol{x})$ が最大になって欲しい

やる夫
$P(y=1|\boldsymbol{x})$ は $\boldsymbol{x}$ が暖色である確率、逆に $P(y=0|\boldsymbol{x})$ が $\boldsymbol{x}$ が寒色である確率、という理解であってるかお?

やらない夫
それでいい。これを全ての学習用データについて考えるんだ。すると目的関数は以下のような同時確率として考えることができる。これを最大化する $\boldsymbol{\theta}$ を見つけることが目的だ。

$$ L(\boldsymbol{\theta}) = \prod_{i=1}^n P(y^{(i)}=1|\boldsymbol{x})^{y^{(i)}} P(y^{(i)}=0|\boldsymbol{x})^{1-y^{(i)}} $$

やる夫
さて、帰るお。

やらない夫
期待通りの反応をありがとう。

やる夫
どうやったらこんな意味不明な式が思いつくんだお…。

やらない夫
確かに、式を簡潔にするために多少トリックを使ってはいるが、やる夫でも理解できるはずだ。1 つずつ考えよう。

やる夫
やらない夫の丁寧な説明をお待ちしておりますお。

やらない夫
$y^{(i)}$ が $1$ と $0$ の場合をそれぞれ考えてみよう。$y^{(i)}=1$ のデータの場合は後ろ側の $P(y^{(i)}=0|\boldsymbol{x})^{1-y^{(i)}}$ が $1$ になる。逆に $y^{(i)}=0$ のデータの場合は前の $P(y^{(i)}=1|\boldsymbol{x})^{y^{(i)}}$ が $1$ になる。

やる夫
ん、なんでだお?

やらない夫
両方とも 0 乗になるだろう。$P(y^{(i)}=1|\boldsymbol{x})$ や $P(y^{(i)}=0|\boldsymbol{x})$ がどんな数だったとしても、べき乗のところが 0 になるからだ。$P(y^{(i)}=1|\boldsymbol{x})^0$ も $P(y^{(i)}=0|\boldsymbol{x})^0$ も両方とも 0 乗なんだから、1 になるのは明確だ。

やる夫
あ、なるほど。確かに、言われてみればそうだお。

やらない夫
まとめるとこうだ。

  • $y^{(i)}=1$ の時は $P(y^{(i)}=1|\boldsymbol{x})$ の項が残る
  • $y^{(i)}=0$ の時は $P(y^{(i)}=0|\boldsymbol{x})$ の項が残る

やらない夫
つまり全ての学習用データにおいて、正解ラベルと同じラベルに分類される確率が最大になるような同時確率を考えているということだ。

やる夫
うーん、わかったようなわかってないような…前の回帰の時は目的関数の最小化だったけど、今回は最大化するのかお。

やらない夫
そうだな。二乗誤差はその名の通り “誤差” なので小さいほうが理想的だ。だが、今回は同時確率だ。その同時確率が最も高くなるようなパラメータ $\boldsymbol{\theta}$ こそ、学習用データにフィットしていると言える。そういった、尤もらしいパラメータを求めたいんだ。

やる夫
国語のお勉強も足りてないお…それなんて読むんだお。

やらない夫
“尤もらしい” は “もっともらしい” と読む。さっき定義した関数も、尤度関数とも呼ばれる。これは “ゆうどかんすう” だな。目的関数に使った文字 $L$ も、尤度を英語で表した時の $Likelihood$ の頭文字から取った。

やる夫
やっぱり、ここにきて難易度あがってるお。面倒くさいけど、あとで復習するお…

やらない夫
そうだな。どうせ家に帰ってやることがないんだろう。

やる夫
バカにするなお…


やる夫で学ぶ機械学習 - 対数尤度関数 - へ続く。

  • このエントリーをはてなブックマークに追加

2016-06-03

やる夫で学ぶ機械学習 - パーセプトロン -

やる夫で学ぶ機械学習シリーズの第 4 回です。分類問題を解くための基礎、パーセプトロンを図形的な側面から覗いてみます。

第 3 回はこちら。やる夫で学ぶ機械学習 - 多項式回帰と重回帰 -

目次はこちら。やる夫で学ぶ機械学習シリーズ

問題設定

やらない夫
今日は分類問題について詳しく見ていく。

やる夫
分類問題かお。やる夫は、女の子が巨乳か貧乳かを分類して、想像を膨らませたいお。

やらない夫
そんなものは深夜に一人でニヤニヤしながらやるか、いつも引きこもってないで外に出て本物の女の子を見ることだな。

やる夫
冗談きついお、やらない夫。

やらない夫
分類の場合も、回帰の時と同じように具体例を示して、それを元に話を進めていったほうがわかりやすいな。

やる夫
それが良いお。具体例は、やる夫の将来の嫁さんくらい大事だお。

やらない夫
また意味のわからないたとえをありがとう。今回は分類の話なので、そうだな、色を分類することを考えてみよう。

やる夫
おっぱいじゃなくて、色を分類、するのかお?

やらない夫
おっぱいは忘れろ。たとえば、適当に与えられた色が、暖色系なのか寒色系なのかに分類する、という問題はどうだ?

やる夫
二値分類の問題かお。分類は確か教師あり学習だったから、つまりラベル付きの学習用データが要るってことかお?

やらない夫
そうだな、具体的には、色の情報と、その色が暖色なのか寒色なのか、というラベルを学習用データとして用意してやる必要がある。

やる夫
なるほど。

やらない夫
ところで、色と言えば RGB の三色を考えることができるが、最初は簡単な問題の方がいいから、緑のことは考えずに、赤と青だけに注目していこう。緑の要素は 0 に固定しようか。その方が図にもプロットできてわかりやすいしな。

やる夫
簡単になるなら歓迎だお。

やらない夫
たとえば、この色は暖色系、寒色系、どっちに見える?

      #d80055

やる夫
んー、暖色系だお。

やらない夫
では、これはどうだ?

      #2c00c8

やる夫
寒色系だお。

やらない夫
ということは、今 2 つの学習用データができた。緑の要素を 0 に固定しているから、#RRGGBB の GG の部分が 00 になっていることに注目だ。

クラス
      #d80055 暖色
      #2c00c8 寒色

やる夫
うん、分類問題の場合の学習用データのイメージつかめたお。

やらない夫
横軸を赤、縦軸を青、とすると、今の学習用データはこんな風にプロットできる。大丈夫か?

やる夫
楽勝だお。

やらない夫
さすがに、学習用データが 2 つしかないと足りないので、もう少し増やしておこう。

クラス
      #d80055 暖色
      #c80027 暖色
      #9c0019 暖色
      #2c00c8 寒色
      #120078 寒色
      #40009f 寒色

やる夫
プロットしてみたお。

やらない夫
よし、OK だ。この図を見て、このデータ点を分類するために 1 本だけ線を引くとしたら、やる夫はどんな風に線を引く?

やる夫
ん、そんなの、誰でもこんな風に線を引くと思うお。

やらない夫
よし。今回の目的はその線を見つけること、それが二値分類だ。

内積

やる夫
線をみつけるって、つまり回帰の時と同じように一次関数の傾きと切片を求めるのかお?

やらない夫
いや、今回はベクトルを見つけるのが目的だ。

やる夫
ベクトルを見つける…。やらない夫、意味がわからんお…。

やらない夫
さっきの線は、重みベクトルを法線とする直線なんだ。重みベクトルを $\boldsymbol{w}$ とすると、直線の方程式はこのように表せる。

$$ \boldsymbol{w}\cdot\boldsymbol{x} = 0 $$

やる夫
うーん、重みベクトルって一体なんなんだお…、その方程式の意味もよくわからんお。

やらない夫
重みベクトルは俺たちが知りたい未知のパラメータだ。回帰の時に $\boldsymbol{\theta}$ という未知のパラメータを求めるために色々と頑張ったが、それと同じものだな。$w$ という文字は weight(重み) の頭文字だ。

やる夫
$\boldsymbol{w}\cdot\boldsymbol{x}$ って、ベクトルの内積のことかお?

やらない夫
そう、内積のことだ。実ベクトル空間の内積は、各要素の積を足し上げたものなので、こんな風にも書ける。$n$ は次元数だ。

$$ \boldsymbol{w}\cdot\boldsymbol{x} = \sum_{i=1}^n w_i x_i = 0 $$

やる夫
ふむ。今回は赤と青の二次元を考えているので、$n = 2$ ってことでいいのかお。

やらない夫
そういうことだ。

やる夫
うーん、内積は覚えてるけど、でも、さっきの方程式…、なんなんだお。

やらない夫
わからない時はいつでも、具体的な値を代入して計算してみよう。イメージがわくかもしれないぞ。やる夫が言ったように、今回の問題は $\mathbb{R}^2$ の実ベクトル空間上で考えているので、そうだな、重みベクトルを $\boldsymbol{w} = (1, 1)$ とした時、$\boldsymbol{x}$ はどうなる?

やる夫
とりあえず、代入してみるお。

\begin{eqnarray} \boldsymbol{w}\cdot\boldsymbol{x} & = & w_1 x_1 + w_2 x_2 \\ & = & 1\cdot x_1 + 1\cdot x_2 \\ & = & x_1 + x_2 = 0 \end{eqnarray}

やる夫
ん、これって要するに $x_2 = -x_1$ だから、$\boldsymbol{x} = (1, -1)$ とか $\boldsymbol{x} = (2, -2)$ とか、解は無限にありそうだけど…、あー、つまり、傾き -1 のグラフってことかお?

やらない夫
よく閃いたな。その図に、重みベクトル $\boldsymbol{w} = (1, 1)$ を書き加えてみると、もっとわかりやすいかもしれないな。

やる夫
えっと、$(1, 1)$ だから…

やる夫
あっ、重みベクトル $\boldsymbol{w}$ が、さっきやる夫が書いた直線と、直角になってるお。

やらない夫
つまり重みベクトル $\boldsymbol{w}$ が、やる夫が書いた直線に対する法線になっているというわけだ。最初に俺が言ったように、$\boldsymbol{w}\cdot\boldsymbol{x} = 0$ という式は、重みベクトル $\boldsymbol{w}$ を法線とする直線の方程式になっている。

やる夫
そういうことかお。そういえば、内積の計算って $\cos$ が含まれてなかったかお?ベクトル同士の成す角 $\theta$ を使って..

$$ \boldsymbol{w}\cdot\boldsymbol{x} = |\boldsymbol{w}|\cdot|\boldsymbol{x}|\cdot\cos\theta $$

やらない夫
それでも問題ない。さっき、やる夫はベクトル方程式から代数的に解いたが、幾何的にはベクトル同士が直角になっている時に内積が 0 になる。$\theta = 90^{\circ}, 270^{\circ}$ の時には $\cos\theta = 0$ になるからな。

やる夫
あーなるほど。そういう直角になってるベクトルがたくさんあって、それ全体が直線になってるのかお。

やらない夫
いろんな側面から覗いてみると、より理解も深まる。

やる夫
じゃ、話は戻るけど、さっきの色分類の問題に関するグラフで言うと、こんな風にやる夫が引いた直線に対する法線を見つける、ってことかお。

やらない夫
そういうことだ。まあ正確にはもちろん最初に直線があるわけではなく、最初に法線、つまり重みベクトルを見つけると、そのベクトルに対して直角な直線がわかり、その直線によってデータが分類される、というわけだな。

やる夫
把握したお。

パーセプトロン

やる夫
で、具体的にはどうやって、その重みベクトルとやらを求めるのかお?

やらない夫
回帰でやった時のように、重みベクトルをパラメータとして、パラメータを更新していくんだ。これから見ていくのは、パーセプトロンと呼ばれるモデルだ。

やる夫
なんか突然かっこいい単語が出てきたお。

やらない夫
パーセプトロンは脳の機能を参考にモデル化したものだと言われることが多いな。ローゼンブラットという人物が考案したモデルなんだ。

やる夫
今度は RPG の主人公キャラの名前かお。

やらない夫
パーセプトロンは複数の入力を受け取り、その入力に対する重みとの線形結合が一定の閾値を超えていた場合に活性化し、そうでない場合は非活性となるような単純な関数だ。

やる夫
線形結合とか活性化とか非活性とか、一体やらない夫は何を言ってるんだお。中二病なのかお。

やらない夫
いや、そういうわけではないが…。そうだな、つまらない形式的な話はよしておこう。形式的な話より直感的な話をしていこうか。やる夫もそっちの方が好きだろう。

やる夫
それでいいんだお。ところで、パラメータの更新っていうと、また微分とか出てくるのかお。

やらない夫
あの時は目的関数があって、それを最小化したいがために微分したんだった。だが、今回は目的関数は不要なので、微分もしない。

やる夫
なるほど。分類も回帰と同じ流れかと思ったけど、そうでもないのかお。

やらない夫
分類問題でも、もちろん目的関数を使うこともあって、その場合には目的関数を最小化する手順は同じようにある。ただ、パーセプトロンのように目的関数が必要ないような場合もある。

やる夫
ふーん。じゃ、今回のパラメータの更新式は、どんなものになるんだお?

やらない夫
その前に、パラメータ更新に必要になるものを、いくつか準備をしておこう。

やる夫
うっ、前準備って、面倒くさくてあんまり好きじゃないお…

やらない夫
このまま先に進んでも、どうせやる夫はわからないだろうからな。まあ、そんなにたくさん準備がいるわけじゃないから安心しろ。

やる夫
やらない夫、いま、しれっとやる夫のこと馬鹿にしたお…

やらない夫
まず、最初に用意した学習用データの、暖色と寒色。このままだと扱いにくいから、暖色を 1、寒色を -1 として、$y$ で表すことにする。そして、横軸を赤、縦軸を青、としていたが、それぞれ $x_1$ と $x_2$ としよう。

クラス $x_1$ $x_2$ $y$
      #d80055 暖色 216 85 1
      #c80027 暖色 200 39 1
      #9c0019 暖色 156 25 1
      #2c00c8 寒色 44 200 -1
      #120078 寒色 18 120 -1
      #40009f 寒色 64 159 -1

やらない夫
そして、ベクトル $\boldsymbol{x}$ を与えると、暖色か寒色を判定する関数、つまり 1 または -1 を返す関数 $f_{\boldsymbol{w}}$ をこのように定義する。このような関数を「識別関数」と呼ぶ。

\begin{eqnarray} f_{\boldsymbol{w}}(\boldsymbol{x}) = \begin{cases} 1 & (\boldsymbol{w}\cdot\boldsymbol{x} \geq 0) \\[5pt] -1 & (\boldsymbol{w}\cdot\boldsymbol{x} \lt 0) \end{cases} \end{eqnarray}

やる夫
ん、要するに内積の符号によって返す値が違うってことかお。こんなんで、暖色か寒色が判定できるのかお?

やらない夫
内積の図形的なイメージを思い出すんだ。例えば、重みベクトル $\boldsymbol{w}$ に対して、内積が負になるベクトルってどんなベクトルだ?$\cos$ が含まれた方の式で考えてみるんだ。

やる夫
ん、$\cos$ を使った内積は $|\boldsymbol{w}|\cdot|\boldsymbol{x}|\cdot\cos\theta$ だから…、ベクトルの大きさは必ず正になるから、符号は $\cos\theta$ の値で決まることになるお…、これが負になるってことは、$90^{\circ} \lt \theta \lt 270^{\circ}$ の場合、ってことかお?

やらない夫
正解だ。そういうベクトル $\boldsymbol{x}$ は、図形的にはどんな位置にあると思う?

やる夫
重みベクトル $\boldsymbol{w}$ との成す角が $90^{\circ} \lt \theta \lt 270^{\circ}$ の範囲内にあるベクトルってことだから…、あー、なるほど、直線を挟んで重みベクトルとは反対側の部分、ってことかお。

やらない夫
その通り。と、いうことは、内積が正のベクトルは、重みベクトルと同じ側の部分ってことだな。

やる夫
なるほど!内積が正か負かで、直線を挟んで分割できてるお。

やらない夫
内積は、ベクトル同士がどれだけ似ているかという指標にも使われる。符号が正だとある程度似ていて、0 で直角になり、そして負になると、だんだん元のベクトルから離れていく。

やる夫
内積にはそういう意味もあったのかお。

やらない夫
さて、準備はこれで終わりだ。話を戻すと、パラメータの更新式はこのように定義する。$i$ は学習用データのインデックスだ。このパラメータ更新を全ての学習用データについて行っていく。

\begin{eqnarray} \boldsymbol{w} := \begin{cases} \boldsymbol{w} + y^{(i)}\boldsymbol{x}^{(i)} & (f_{\boldsymbol{w}}(\boldsymbol{x}^{(i)}) \neq y^{(i)}) \\[5pt] \boldsymbol{w} & (f_{\boldsymbol{w}}(\boldsymbol{x}^{(i)}) = y^{(i)}) \end{cases} \end{eqnarray}

やる夫
んー、なんかまた、ごちゃごちゃした式だお…

やらない夫
意味がわからない数式を見た時は、いったん落ち着くんだ。難しそうな式がごちゃごちゃしているのは確かだが、その式の文字を 1 つずつ読み解いていき、ボトムアップで全体像を把握していけばいい。

やる夫
んっと、じゃ、まずは $f_{\boldsymbol{w}}(\boldsymbol{x}^{(i)}) \neq y^{(i)}$ の方から見ていくお…

やらない夫
それがいい。その条件は、どういうことを表していると思う?

やる夫
$i$ 番目の学習用データを識別関数に通して分類した結果と、同じく $i$ 番目の学習用データのラベル $y$ が異なっている、ってことだお。あ、ということは、識別関数による分類に失敗した、ってことなのかお?

やらない夫
やるじゃないか、やる夫の言う通りだ。

やる夫
もう一つの $f_{\boldsymbol{w}}(\boldsymbol{x}^{(i)}) = y^{(i)}$ の方は、逆に分類に成功した、って意味だお。

やらない夫
そういうことだ。つまり、先のパラメータ更新式は、識別関数による分類が失敗した時だけ新しいパラメータに更新されるという意味だ。分類に成功した場合は、パラメータの重みベクトルは正しいはずだと捉えて更新をしない。そこ、大丈夫か?

やる夫
わかるお。分類が成功した時、つまり $f_{\boldsymbol{w}}(\boldsymbol{x}^{(i)}) = y^{(i)}$ の時は $\boldsymbol{w}$ がそのまま代入されて、元と何も変わってないから、そういうことだお。

やらない夫
では今度は、識別関数による分類が失敗した時の更新式を見てみようか。

やる夫
$\boldsymbol{w} + y^{(i)}\boldsymbol{x}^{(i)}$ の方かお。うーん…、さっきから考えてるけど、未だにまったく意味がわからんお…。

やらない夫
式だけ眺めてても難しいかもしれないな。こちらも図形的に考えてみるといい。

やる夫
グラフに書いてみるってことかお。ん、でも、そんな式どうやって図に書けばいいのかお?

やらない夫
具体例を考えるんだよ。まずは、以下の図にあるような適当な重みベクトルがあったとして、その状態でラベルが $y = 1$、つまり暖色系の学習用データを与えた場合にどうなるかを考えてみよう。

やる夫
上の図の場合、重みベクトル $\boldsymbol{w}$ と学習用データ $\boldsymbol{x}^{(1)}$ との成す角は $90^{\circ}$ 以上だから内積が負になって、識別関数 $f_{\boldsymbol{w}}$ は -1 を返すはずだお。そして、与えられた学習用データのラベルは $y = 1$ だから、識別関数による分類に失敗しているお。

やらない夫
パラメータ更新式の $f_{\boldsymbol{w}}(\boldsymbol{x}^{(1)}) \neq y^{(1)}$ という状況だな。つまり、パラメータが更新されるというわけだ。

やる夫
なるほど。いま、$y^{(1)} = 1$ だから、更新式は $\boldsymbol{w} + \boldsymbol{x}^{(1)}$ になるわけだお。んー、普通のベクトルの足し算だから、さっきの図に書き足してみるお…

やる夫
重みベクトル $\boldsymbol{w}$ が更新されて、最初に引いてた直線が回転したお!

やらない夫
新しい重みベクトルの元で識別関数に通すと、今度はちゃんと分類に成功することもわかるだろう。

やる夫
さっきは、$\boldsymbol{x}^{(1)}$ が直線を挟んで重みベクトルと反対側にあったけど、新しい重みベクトルで見た場合、$\boldsymbol{x}^{(1)}$ は重みベクトルと同じ側にあるから確かに良さそうだお。

やらない夫
学習用データのラベルが $y = -1$ の場合は、今度はパラメータ更新がベクトルの引き算になるわけだな。

やる夫
足し算と引き算の違いはあるけど、同じように新しい重みベクトルに更新されて、その分だけ直線が回転するってことかお。

やらない夫
この繰り返しによってパラメータを更新していくのがパーセプトロンの学習だ。

やる夫
とてもよくわかりましたお。顔画像を準備して、巨乳なら 1、そうじゃないなら -1 ってラベルをつけていけば、未知の女の子をパーセプトロンで分類できそうだお。

やらない夫
お前、まだそれ諦めてなかったのかよ…そんなものはおそらくパーセプトロンでは分類できないだろうな。

線形分離可能

やる夫
またやる夫のことバカにしてるのかお?

やらない夫
パーセプトロンによる学習はとてもシンプルでわかりやすいが、その分デメリットも大きい。

やる夫
えっ…。やらない夫は、いつも最後に残念な想いをさせるから、そういうのやめて欲しいお。終わり良ければ全て良しだお。

やらない夫
最初に嫌な話をしても、それはそれでその後のモチベーションが下がるだろ。それに、デメリットを知っておくことは大事だぞ。

やる夫
そのデメリットによってやる夫の夢は打ち砕かれるのかお…

やらない夫
パーセプトロンの最たるデメリットは線形分離可能な問題しか解けないということだ。

やる夫
線形分離可能?

やらない夫
たとえば、こんな学習用データがあったとしよう。赤い点が 1 で、青いバツが -1 とするんだ。これを分類するために 1 本だけ直線を引くとしたら、やる夫はどんな風に線を引く?

やる夫
いや、こんなのどうやっても直線 1 本じゃ分類できないお。

やらない夫
そうだ、この例のように直線 1 本では分類できないようなものは線形分離可能ではない。つまり、パーセプトロンでは分類できない。

やる夫
やる夫が作ろうとしている分類器も線形分離可能ではない、って言いたいのかお?

やらない夫
画像を扱う場合、入力がかなりの高次元になるため可視化はできないが、顔の特徴を掴んで分類しようとするタスクはそんなに単純じゃない。確実に線形分離不可能だろうな。

やる夫
パーセプトロンなんて使い物にならんお。

やらない夫
確かに、パーセプトロンは現場で使われることはほとんど無い。実際に解きたい問題が線形分離可能であることはほぼありえないからな。ほとんどが線形分離不可能な問題だ。でも安心しろ。ちゃんと実用的な分類器を構築するためのアルゴリズムもあるんだぞ。

やる夫
一旦落としておいて、その後に希望を見せるそのやり方、クセになるお。解決策があるって素晴らしいお。

やらない夫
偉大な先人たちのおかげだな。

やる夫
ところで、やらない夫は大きいのと小さいのはどっちが好きなんだお?

やらない夫
お前、ほんと好きだな、それ…


やる夫で学ぶ機械学習 - ロジスティック回帰 - へ続く。

  • このエントリーをはてなブックマークに追加

2016-06-02

やる夫で学ぶ機械学習 - 多項式回帰と重回帰 -

やる夫で学ぶ機械学習シリーズの第 3 回です。多項式回帰と重回帰について見ていきます。

第 2 回はこちら。やる夫で学ぶ機械学習 - 単回帰問題 -

目次はこちら。やる夫で学ぶ機械学習シリーズ

多項式回帰

やらない夫
さて、回帰の話にはもう少し続きがあるんだが。

やる夫
あんまり難しすぎるのは勘弁だお。

やらない夫
前回の延長だから、回帰が理解できていれば、そう難しい話ではないだろう。

やる夫
その前に、ちょっとおしっこいってくるお。

やらない夫
お前、そういうのは休憩中にやっとけよ…

やる夫
わかったお!仕方ないから我慢するお!!

やらない夫
意外と根性あるな…、ではこれから、前回の回帰の話をもう少し発展させていく。

やる夫
(あっ、ほんとに話を進めるのかお…)

やらない夫
前回、俺たちは、求めたい関数をこのように定義して、パラメータである $\theta$ を求めた。

$$ f_{\theta}(x) = \theta_0 + \theta_1 x $$

やる夫
覚えてるお。$f_{\theta}(x)$ を使った目的関数を定義して、最急降下法でパラメータの $\theta$ を求めたんだお。

やらない夫
$f_{\theta}(x)$ は一次関数だから、関数の形は当然のことながら直線になる。そこは大丈夫だよな。

やる夫
なんか回りくどいお。前回やったことはちゃんと覚えてるから、復習ならしなくていいお。

やらない夫
そうか。では、本題に入るが、最初に示したプロットは、実は直線より曲線の方がよりフィットするんだ。

やる夫
お、なるほど。確かに、曲線のグラフの方が、よりフィットしているように見えるお。

やらない夫
これは、関数 $f_\theta(x)$ を二次式として定義することで実現できる。

$$ f_{\theta}(x) = \theta_0 + \theta_1 x + \theta_2 x^2 $$

やらない夫
あるいは、それ以上の次数の式として定義すれば、より複雑な曲線にも対応できる。

$$ f_{\theta}(x) = \theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3 + \cdots + \theta_n x^n $$

やる夫
どういう式にするのかは、勝手に自分で決めていいのかお?

やらない夫
そうだな、解きたい問題に対して、どの式が一番フィットするのかを見極めながら、いろいろ試してみる必要はあるがな。

やる夫
う、なんか面倒くさそうだお…

やらない夫
経験と勘がモノを言う部分だな。どれが最適なのかは、俺にもわからないからな。

やる夫
やらない夫にもわからないなら、仕方ないお…

やらない夫
さっきの二次式を見返してみると、新しいパラメータ $\theta_2$ が増えているな。このあと、どうすればいいかわかるか?

やる夫
ん、前と同じように偏微分して、パラメータ更新していけばいいのかお?こんな風に…

\begin{eqnarray} \theta_0 & := & \theta_0 - \eta\sum_{i=1}^n (f_{\theta} (x^{(i)}) - y^{(i)}) \\ \theta_1 & := & \theta_1 - \eta\sum_{i=1}^n (f_{\theta} (x^{(i)}) - y^{(i)})x^{(i)} \\ \theta_2 & := & \theta_2 - \eta\sum_{i=1}^n (f_{\theta} (x^{(i)}) - y^{(i)}){x^{(i)}}^2 \end{eqnarray}

やらない夫
そうだな。この式を使って $\theta_0, \theta_1, \theta_2$ を更新していけば、よりデータにフィットした $f_{\theta}(x)$ が得られる。当然だが、前にも言ったようにそれぞれの $\theta$ は同時に更新していく必要がある。

やる夫
これって、パラメータが $\theta_3, \theta_4, \cdots$ って増えていっても、同じことを繰り返せばいいのかお?

やらない夫
そういうことだ。こんな風に多項式の次数を増やした関数を使うものを多項式回帰と言うんだ。

やる夫
次数が高ければ高いほど、より正確に未知のデータを予測できる関数になるってことかお。

やらない夫
いや、そこはそうとも限らない。

やる夫
えっ、なんでだお…

やらない夫
過剰適合、またはオーバーフィッティング (Overfitting) と呼ばれる問題があってな。もちろん、オーバーフィッティングに対する解決策はある。が、それはまたの機会にとっておこう。

やる夫
もったいぶらないで説明してほしいお。

やらない夫
回帰の話にもう少し続きがあるから、先にそっちを説明したいんだ。それに、一度になんでもかんでも詰め込んでも、頭がパンクしてしまうぞ。

やる夫
そうかお…、やらない夫は言いくるめるのが上手だお。

やらない夫
言い方に悪意を感じるな、お前…

重回帰

やる夫
おしっこ行ってきたお。

やらない夫
多項式回帰の話の続き、いくぞ。

やる夫
よろしくお願いしますお。

やらない夫
今までは学習用データの変数は 1 つしかなった。

やる夫
学習用データの変数?攻撃力 $x$ のことかお?

やらない夫
そうだ。先の例では、攻撃力という 1 つの変数で、ダメージが決まっていた。ただ、実際は変数が 2 つ以上の複雑な問題なことが多い。

やる夫
さっきの多項式回帰で $x$ に加えて $x^2$ や $x^3$ を使う場合ってことかお。

やらない夫
いや、そうじゃない。確かに多項式回帰には別々の次数を持った複数の項があるが、実際に俺たちが使った変数は「攻撃力」のみだ。そうだろ?

やる夫
「攻撃力」と「攻撃力の 2 乗」と「攻撃力の 3 乗」の 3 つを使った、ってことじゃないのかお?

やらない夫
まあそうだが、本質的な変数は「攻撃力」のみだ。

やる夫
言ってることがよくわからんお。

やらない夫
今考えている問題設定を少し拡張するぞ。最初は、攻撃力が決まればダメージが決まる、という設定だったが、ダメージを決める要素は「攻撃力」の他に、実は「Lv」と「体力」という要素があるとしよう。

やる夫
あー、なるほど。変数が 2 つ以上って、そういうことかお。

やらない夫
そういうことだな。ところで、これまでは「変数」という言い方をしてきたが、機械学習の現場では「素性」と言ったりする。

やる夫
あぁ、なんか聞いたことがあるお。

やらない夫
素性が 1 つの時はグラフにプロットできたが、素性が 3 つとなると可視化することはできない。これからは図は省略することになるが…

やる夫
なんか先が思いやられる展開だお…

やらない夫
まぁ、これまでの話が理解できているのであれば大丈夫なはずだ。

やる夫
やらない夫の説明力を信じて、ついていくお…

やらない夫
今までは攻撃力を $x$ と置いていたが、これからは攻撃力を $x_1$、Lvを $x_2$、体力を $x_3$ と置くとすると、$f_{\theta}$ はどうなるかわかるか?

やる夫
ん、こんなんでいいのかお…?

$$ f_{\theta}(x_1, x_2, x_3) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3 $$

やらない夫
正解だ。この時のパラメータ $\theta_0, \cdots, \theta_3$ を求めるにはどうすればいいかは、もうわかるな?

やる夫
目的関数を $\theta_0, \cdots, \theta_3$ についてそれぞれ偏微分して、パラメータを更新していけばいいお。

やらない夫
そうだな。では、実際のパラメータの更新式はどうなる?と聞きたいところだが、その前に式の表記をより簡単にしておこう。

やる夫
ん、どういうことかお?

やらない夫
素性が一般に $n$ 個ある場合のことを考えよう。$x_1, \cdots, x_n$ までの素性があるときの $f_{\theta}$ はどうなる?

やる夫
こうなるお。

$$ f_{\theta}(x_1, \cdots, x_n) = \theta_0 + \theta_1 x_1 + \cdots + \theta_n x_n $$

やらない夫
毎回そんな風に $n$ 個の $x$ を書いていくのは大変だから、パラメータ $\theta$ と素性 $x$ をベクトルとみなすんだ。

やる夫
ベクトルって、大きさと向きがある、矢印で表すアレかお?

やらない夫
それだな。まあ、今回は矢印というイメージは出てこないが…、むしろ列ベクトルだな。$\theta$ と $x$ をベクトルとして定義するとは、どういうことだと思う?

やる夫
んー、列ベクトルなんだったら、こういうことかお?

$$ \boldsymbol{\theta} = \left[ \begin{array}{c} \theta_0 \\ \theta_1 \\ \theta_2 \\ \vdots \\ \theta_n \end{array} \right] \ \ \ \boldsymbol{x} = \left[ \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right] $$

やらない夫
おしいな。そのままだと、それぞれで次元が違うだろ。$\boldsymbol{\theta}$ は添字が 0 から始まるから $n+1$ 次元で、$\boldsymbol{x}$ の方は $n$ 次元だ。それだと扱いにくい。

やる夫
いや、そんなこと言われても、文字はもうこれだけしかないんだお…

やらない夫
何もベクトルの要素が全て文字じゃなくてもいい。こんな風に書きなおしてみよう。

$$ \boldsymbol{\theta} = \left[ \begin{array}{c} \theta_0 \\ \theta_1 \\ \theta_2 \\ \vdots \\ \theta_n \end{array} \right] \ \ \ \boldsymbol{x} = \left[ \begin{array}{c} 1 \\ x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right] $$

やる夫
勝手に 1 を足していいのかお?

やらない夫
むしろ、こうやって最初に 1 を置くほうが自然なんだ。$\boldsymbol{\theta}$ の方と合わせるために $x_0 = 1$ として、最初の要素に $x_0$ を置いてもいいな。

$$ \boldsymbol{\theta} = \left[ \begin{array}{c} \theta_0 \\ \theta_1 \\ \theta_2 \\ \vdots \\ \theta_n \end{array} \right] \ \ \ \boldsymbol{x} = \left[ \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right] \ \ \ (x_0 = 1) $$

やらない夫
さて、ここで、$\boldsymbol{\theta}$ を転置したものと $\boldsymbol{x}$ を掛けてやると、どうなると思う?

やる夫
ん、ベクトルの各要素を掛けあわせて、それを全部足せばいいんだから、ちょっと面倒くさいけど、えっと…、こうかお。

$$ \boldsymbol{\theta}^{\rm{T}}\boldsymbol{x} = \theta_0 x_0 + \theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_n x_n $$

やる夫
あ、$x_0 = 1$ だから、これって $f_{\theta}$ だお。

やらない夫
そういうことだ。つまり多項式で表していた $f_{\theta}$ は、ベクトルを使うと以下のように表せる。

$$ f_{\boldsymbol{\theta}}(\boldsymbol{x}) = \boldsymbol{\theta}^{\rm{T}}\boldsymbol{x} $$

やる夫
ずいぶんと簡潔になったお。

やらない夫
そして、$\boldsymbol{\theta}$ の $j$ 番目の要素を $\theta_j$ とすると、$E$ を $\theta_j$ で偏微分した時の式は、こんな風に書ける。ベクトルとスカラー値で、太字かそうでないかをちゃんと使い分けてるから、気をつけろよ。

$$ \frac{\partial E}{\partial \theta_j} = \sum_{i=1}^n (f_{\boldsymbol{\theta}} (\boldsymbol{x}^{(i)}) - y^{(i)}){x_j}^{(i)} $$

やる夫
なるほど。前から思ってたけど、やっぱりこの偏微分には規則性があったのかお。$j=0$ の時、つまり $\theta_0$ で偏微分する時も、後ろについてる $x_j$ は $x_0 = 1$ なので、結局は最初にやる夫が自分で微分した式と一致するお。

やらない夫
要するにパラメータの更新式は、こうだな。各 $\theta_j$ は同時更新する必要があるのは相変わらずだから気をつけろよ。

$$ \theta_j := \theta_j - \eta\sum_{i=1}^n (f_{\boldsymbol{\theta}} (\boldsymbol{x}^{(i)}) - y^{(i)}){x_j}^{(i)} $$

やる夫
ミッション・コンプリートだお!!

やらない夫
な、今までの話が理解できていれば、素性が増えたとしても大したことは無いだろう。

やる夫
やる夫が優秀だからだお。

やらない夫
突然どこから出てくるんだよ、その自信。こんな風に素性を 2 つ以上使ったものを重回帰と言うんだ。逆に、最初にやった例のように素性が 1 つの場合は、単回帰と言うな。

やる夫
単回帰に、多項式回帰に、重回帰。覚えたお。

やらない夫
回帰の話はこの辺で終わりだな。

やる夫
最後のベクトル化から続く怒涛の一般化ラッシュ、気持よかったお。

やらない夫
一般化して考えられるのは、数学のいいところだな。

やる夫
ところで、これまでやってきた最急降下法、パラメータの更新にシグマが含まれてるから、全学習データ分だけループすることになるんだお。学習用データが大量にあった場合、for ループの回数が増えて、時間がかかってしまわないかお?

やらない夫
さすがプログラミングが得意なだけあって、効率云々を気にするんだな。そうだ、やる夫の言うとおり、計算量が多くて遅いことが最急降下法の欠点の 1 つだ。

やる夫
まあ、性能の良いマシンを買えば解決するかお。

やらない夫
金に物を言わせるなよ…、そこはプログラマっぽくないな、お前。ちゃんと、もっと速いアルゴリズムがあるんだよ。むしろ、最急降下法よりも、そっちの速いアルゴリズムの方が好んで使われるな。

やる夫
じゃ、最初からそっちの速いアルゴリズムの方を教えてくれればよかったお…

やらない夫
速いアルゴリズムの方は最急降下法をベースにしてるんだよ。先に速いアルゴリズムを説明しても、どうせ最急降下法から説明することになるんだから、結局は同じことだ。それに、こういうことは基礎からちゃんとやっといたほうが、後で応用が聞くんだぞ?

やる夫
うっ、やっぱりやらない夫には言いくるめられてしまうお…

やらない夫
お前、言い方…

確率的勾配降下法

やらない夫
最後に確率的勾配降下法というアルゴリズムを見ていこう。

やる夫
それが、さっき言った速いアルゴリズムのことかお?

やらない夫
そうだな。最急降下法には、さっきやる夫がいった計算に時間がかかること以外にも、収束が遅かったり、それから局所解に捕まってしまう、というデメリットもある。

やる夫
局所解につかまるって、どういうことかお?

やらない夫
最急降下法を説明する時に使った関数の例は $g(x) = (x - 1)^2$ という二次関数だったから問題なかったが、もっと複雑な形の関数を考えてみよう。この関数の最小値は、赤い点で示してある位置だな。

やる夫
ぐにゃぐにゃしてるグラフだお…

やらない夫
最急降下法で関数の最小値を見つけるにしても、まず最初に初期値を決める必要がある。

やる夫
あー、確かにやったお。例の時は $x = 3$ からはじめたお。あれは、なんで 3 からスタートさせたのかお?

やらない夫
俺が適当に選んだ値だ。

やる夫
やらない夫神に導かれるままについていきますお。

やらない夫
そうじゃなくて、初期値は適当に決めていいって意味だ。ただ、そのせいで局所解に捕まるという問題が発生するんだ。たとえば、この図の青い点が初期値だったとしたら、どうだ?

やる夫
あー、なんとなくわかってきたお。その青い点が初期値だったら、最急降下法でちゃんと赤い点の最小値が求まるお。

やらない夫
では、赤い点の最小値が求まらないのは、どういう場合だ?

やる夫
たとえば、今度はこっちの青い点が初期値だった場合、赤い点まで移動せずに、たぶんオレンジの点で止まってしまうお。

やらない夫
それが局所解に捕まるということだ。

やる夫
アルゴリズムがシンプルな分、いろいろな問題があるってことかお。

やらない夫
そこで、そういった最急降下法のデメリットを克服したアルゴリズムが、確率的勾配降下法だ。

やる夫
ふむ。具体的にはどういうアルゴリズムなんだお?

やらない夫
最急降下法のパラメータ更新の式は覚えてるか?

やる夫
覚えてるお。

$$ \theta_j := \theta_j - \eta\sum_{i=1}^n (f_{\boldsymbol{\theta}} (\boldsymbol{x}^{(i)}) - y^{(i)}){x_j}^{(i)} $$

やらない夫
よし。その式では、パラメータの更新に全ての学習用データの誤差を使っているが、確率的勾配降下法ではランダムに学習用データを 1 つ選んで、それをパラメータの更新に使うんだ。式中の $k$ は、パラメータ更新毎にランダムに選ばれたインデックスだ。

$$ \theta_j := \theta_j - \eta(f_{\boldsymbol{\theta}} (\boldsymbol{x}^{(k)}) - y^{(k)}){x_j}^{(k)} $$

やる夫
お、シグマがなくなってるお。

やらない夫
そうだな。最急降下法で 1 回パラメータを更新する間に、確率的勾配降下法では $n$ 回パラメータを更新できる。また、学習用データをランダムに選んで、その時点での勾配でパラメータを更新していくので、目的関数の局所解に捕まりにくい。

やる夫
そんなに適当なやり方で、ちゃんとした答えが得られるのかお?

やらない夫
この方法でも、実際に最適解に収束するということがわかっている。

やる夫
うーん、なんか不思議だお。

やらない夫
もちろん、学習率 $\eta$ を適切に設定することは大事だ。特に、学習する度に $\eta$ を小さくしていく、という手法も存在する。

やる夫
そうだ、最急降下法の時も思ってたけど、$\eta$ の適切な値って、どうやって見つければいいのかお?

やらない夫
難しい問題だな。解決のためのアイデアは、興味があれば探してみるといい。

やる夫
やらない夫、実は知らないのかお。

やらない夫
これ以上続けると、話が長くなりすぎるからな。

やる夫
あっ、はぐらかしたお。読者のことを考えてるふりをするなんて、ずるいお。

やらない夫
まあ、そういうところは、実際に実装しはじめて困ったときに探すので十分だ。やり始める前から、なんでもかんでも一気に詰め込むのはよくないぞ。

やる夫
はいはいですお。


やる夫で学ぶ機械学習 - パーセプトロン - へ続く。

  • このエントリーをはてなブックマークに追加

2016-05-09

Word2Vec のニューラルネットワーク学習過程を理解する

Word2Vec というと、文字通り単語をベクトルとして表現することで単語の意味をとらえることができる手法として有名なものですが、最近だと Word2Vec を協調フィルタリングに応用する研究 (Item2Vec と呼ばれる) などもあるようで、この Word2Vec というツールは自然言語処理の分野の壁を超えて活躍しています。

実は Item2Vec を実装してみたくて Word2Vec の仕組みを理解しようとしていたのですが、Word2Vec の内部の詳細に踏み込んで解説した日本語記事を見かけることがなかったので、今更感はありますが自分の知識の整理のためにもブログに残しておきます。なお、この記事は Word2Vec のソースコードといくつかのペーパーを読んで自力で理解した内容になります。間違いが含まれている可能性もありますのでご了承ください。もし間違いを見つけた場合は指摘してもらえると修正します。

※この記事を読むにあたっては、ニューラルネットワーク及び確率的勾配降下法に関する基礎知識程度は必要です。

Word2Vec

Word2Vec の正体は、隠れ層と出力層の 2 層からなる単純なニューラルネットワークです。このニューラルネットワークに次々に単語を読み込ませて重みを学習させていくのですが、Word2Vec で獲得できる単語のベクトル表現というのは実はネットワークの重みそのものです。入力データに対する “良い表現” を獲得するという意味では自己符号化器 (オートエンコーダ) に近いものがあると思います。

Word2Vec のネットワークのアーキテクチャとしては CBoW 及び Skip-gram と呼ばれる 2 種類があり、また学習を高速化するテクニックとして Hierarchical Softmax 及び Negative Sampling の 2 種類が提案されています。Word2Vec 論文の著者が公開しているオリジナルの C のソースコードでは両方のアーキテクチャ及び高速化テクニックが実装されていますが、この記事では Skip-gram と Negative Sampling について書いていきます。CBoW 及び Hierarchical Softmax については機会があれば別途記事を書きます。

Skip-gram でモデル化する

Skip-gram とは、ある単語が与えられた時、その周辺の単語を予測するためのモデルです。たとえば以下のような単語の集合があったとしましょう。このようなものはボキャブラリと呼ばれます。

{ I, am, a, programmer, like, dog, cat }

これらの単語を使って文章を作ってください、と言われたら I am a programmerI like a dog などの文章がすぐに思い浮かぶでしょう。ここで作った文章中の I という単語に注目すると、その次には amlike が現れて、さらにその次には a があって、それに続いて programmerdog があります。しかし、I の次にいきなり programmerdog といった単語はあまり現れないでしょう。つまり I という単語の周辺にはどういった単語が出現しやすいか、という確率を考えることができます。

さて、このような確率を、以下のような条件付き確率として softmax 関数を使ってモデル化します。

$$ p(w_O|w_I) = \frac{\exp(\boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I})}{\sum_{w_v \in V} \exp(\boldsymbol{v’}_{w_v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I})} $$

※$\exp(x) = \mathrm{e}^x$ です。また $\boldsymbol{v}^{\mathrm{T}}$ は $\boldsymbol{v}$ の転置、$\boldsymbol{v}^{\mathrm{T}} \cdot \boldsymbol{v}$ はベクトルの内積です。

$w_I$ は注目する単語 (添字の $I$ は Input の $I$)、$w_O$ は $w_I$ の周辺の単語 (添字の $O$ は Output の $O$)、$V$ はボキャブラリ、$\boldsymbol{v}_{w_I}$ と $\boldsymbol{v’}_{w_O}$ は単語を表すベクトルです。$\boldsymbol{v}$ と $\boldsymbol{v’}$ は別物で、$\boldsymbol{v}$ は入力ベクトル、$\boldsymbol{v’}$ は出力ベクトルと呼ばれます。さて、この式を計算することで $w_I$ と $w_O$ が共起する確率を計算できます。

たとえば $w_I$ が I であるとした時、いくつかの $w_O$ ついて例を挙げてみると

  • $w_O$ が am ならば $p(am|I)$ は高くなって欲しい。I am ... は自然な文章だから。
  • $w_O$ が like ならば $p(like|I)$ は高くなって欲しい。I like ... も自然な文章だから。
  • $w_O$ が dog ならば $p(dog|I)$ は低くなって欲しい。I dog ... はなんかおかしいから。

ここにコンテキスト $C$ というものを導入して、以下のような同時確率を考えます。

$$ p(w_{O,1},w_{O,2},\cdots,w_{O,C}|w_I) = \prod_{c=1}^C \frac{\exp(\boldsymbol{v’}_{w_{O,c}}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I})}{\sum_{w_v \in V} \exp(\boldsymbol{v’}_{w_v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I})} $$

ここでのコンテキスト $C$ は注目する単語の前後にある単語です。たとえば I am a programmer という文章で、前後 1 単語ずつを考える場合は以下のようになります。(このような前後の単語数をコンテキストサイズと言います。つまり以下の例ではコンテキストサイズは 1 となります)

  • $w_I$ が I の時、$C$ は { am }
  • $w_I$ が am の時、$C$ は { I, a }
  • $w_I$ が a の時、$C$ は { am, programmer }
  • $w_I$ が programmer の時、$C$ は { a }

このように前後のコンテキストまで含めた確率 $p(w_{O,1},w_{O,2},\cdots,w_{O,C}|w_I)$ を考えた時、その確率が最大となるようなベクトル $\boldsymbol{v}$ が、単語の “良い表現” になるであろうという仮定を置きます。それこそが Word2Vec が出力する単語ベクトルとなります。

$$ \mathop{\mathrm{argmax}}\limits_{\boldsymbol{W},\boldsymbol{W’}} p(w_{O,1},w_{O,2},\cdots,w_{O,C}|w_I) $$

※ボキャブラリの全単語に対する $\boldsymbol{v}$、$\boldsymbol{v'}$ を並べたものをそれぞれ $\boldsymbol{W}$、$\boldsymbol{W'}$ としています。

ニューラルネットワークを構築する

それでは、先ほど考えた Skip-gram のモデルに対して、以下のようなニューラルネットワークを考えます。全て全結合層になっています。$V$ はボキャブラリの単語数、$N$ は単語ベクトルの次元、$C$ はコンテキストサイズです。

ひとつ注意ですが、これからネットワークを考えるにあたって $w_I$ や $w_O$ は実際の単語そのものではなく、ボキャブラリ内でのインデックスとして考えます。今後も最初に例として挙げた以下のようなボキャブラリを使って記事を書き進めていきますが、$w_I = 1$ だと I、$w_I = 2$ だと am、$w_I = 3$ だと a、がそれぞれ入力されたという意味になります。

{ I, am, a, programmer, like, dog, cat }

入力層

入力層のベクトル $\boldsymbol{x}$ は $V$ 次元です。ボキャブラリは一般的には $10^5$ 〜 $10^7$ 程度の語彙数になるので、$\boldsymbol{x}$ の次元もそれくらい大きなものになります。$\boldsymbol{x}$ は $w_I$ の単語に対応する要素 $x_{w_I}$ が 1 で、他はすべて 0 という、いわゆる one-hot-vector です。

たとえば $w_I = 1$ の場合、入力層のベクトル $\boldsymbol{x}$ はこのようになります。

$$ \boldsymbol{x} = \left[ \begin{array}{l} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right] = \left[ \begin{array}{l} \color{red}1 \cdots I \\ 0 \cdots am \\ 0 \cdots a \\ 0 \cdots programmer \\ 0 \cdots like \\ 0 \cdots dog \\ 0 \cdots cat \end{array} \right] $$

それでは $w_I = 2$ の場合はどうでしょうか?その場合、入力層のベクトル $\boldsymbol{x}$ がこうなるのはすぐにわかるでしょう。

$$ \boldsymbol{x} = \left[ \begin{array}{l} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right] = \left[ \begin{array}{l} 0 \cdots I \\ \color{red}1 \cdots am \\ 0 \cdots a \\ 0 \cdots programmer \\ 0 \cdots like \\ 0 \cdots dog \\ 0 \cdots cat \end{array} \right] $$

隠れ層

入力層から隠れ層への重み $\boldsymbol{W}$ は単語ベクトル $\boldsymbol{v}$ を並べたものです。具体的には、ボキャブラリの全単語の単語ベクトルを横に並べた行列です。$N$ 次元の単語ベクトルが $V$ 個並んだものなので行列のサイズは $N \times V$ です。ベクトルについている添字がボキャブラリの単語のインデックスに対応しています。$\boldsymbol{v}_1$ は I に対するベクトルですし、$\boldsymbol{v}_2$ は am に対するベクトルになります。

$$ \begin{eqnarray} \boldsymbol{W} & = & \left[ \begin{array}{lllllll} \boldsymbol{v}_1 & \boldsymbol{v}_2 & \boldsymbol{v}_3 & \boldsymbol{v}_4 & \boldsymbol{v}_5 & \boldsymbol{v}_6 & \boldsymbol{v}_7 \end{array} \right] \\ & = & \left[ \begin{array}{cccc} v_{11} & v_{21} & v_{31} & v_{41} & v_{51} & v_{61} & v_{71} \\ v_{12} & v_{22} & v_{32} & v_{42} & v_{52} & v_{62} & v_{72} \\ v_{13} & v_{23} & v_{33} & v_{43} & v_{53} & v_{63} & v_{73} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ v_{1N} & v_{2N} & v_{3N} & v_{4N} & v_{5N} & v_{6N} & v_{7N} \end{array} \right] \end{eqnarray} $$

これが入力層から隠れ層への重み $\boldsymbol{W}$ です。隠れ層は全結合層なので、重み $\boldsymbol{W}$ と入力データ $\boldsymbol{x}$ を掛けたものが隠れ層のユニット $\boldsymbol{h}$ になります。

$$ \boldsymbol{h} = \boldsymbol{Wx} $$

さて $\boldsymbol{x}$ は one-hot-vector だったことを思い出してください。たとえば $w_I = 2$ の場合を考えてみると、以下のように結局は 2 番目の単語ベクトルがそのまま出力されることがわかります。

$$ \boldsymbol{Wx} = \left[ \begin{array}{lllllll} \boldsymbol{v}_1 & \boldsymbol{v}_2 & \boldsymbol{v}_3 & \boldsymbol{v}_4 & \boldsymbol{v}_5 & \boldsymbol{v}_6 & \boldsymbol{v}_7 \end{array} \right]\left[ \begin{array}{l} 0 \\ \color{red}1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right] = \boldsymbol{v}_2 $$

つまり、隠れ層のユニットは重み行列の $w_I$ 列目の単語ベクトルそのものとなることがわかります。このネットワークでは隠れ層に活性化関数は使いませんので、隠れ層の出力はそのまま $\boldsymbol{v}_{w_I}$ となります。

$$ \boldsymbol{h} = \boldsymbol{Wx}_{w_I} = \boldsymbol{v}_{w_I} $$

出力層

隠れ層から出力層への重み $\boldsymbol{W’}$ も同じように単語ベクトル $\boldsymbol{v’}$ を並べたものです。$\boldsymbol{W}$ と同じように、ボキャブラリの全単語の単語ベクトルを並べます。ただし今度は各単語ベクトルを転置したものを縦に並べた行列です。こちらは $V \times N$ のサイズになります。

$$ \boldsymbol{W’} = \left[ \begin{array}{l} \boldsymbol{v’}_1^{\mathrm{T}} \\ \boldsymbol{v’}_2^{\mathrm{T}} \\ \boldsymbol{v’}_3^{\mathrm{T}} \\ \boldsymbol{v’}_4^{\mathrm{T}} \\ \boldsymbol{v’}_5^{\mathrm{T}} \\ \boldsymbol{v’}_6^{\mathrm{T}} \\ \boldsymbol{v’}_7^{\mathrm{T}} \end{array} \right] = \left[ \begin{array}{ccccc} v’_{11} & v’_{12} & v’_{13} & \cdots & v’_{1N} \\ v’_{21} & v’_{22} & v’_{23} & \cdots & v’_{2N} \\ v’_{31} & v’_{32} & v’_{33} & \cdots & v’_{3N} \\ v’_{41} & v’_{42} & v’_{43} & \cdots & v’_{4N} \\ v’_{51} & v’_{52} & v’_{53} & \cdots & v’_{5N} \\ v’_{61} & v’_{62} & v’_{63} & \cdots & v’_{6N} \\ v’_{71} & v’_{72} & v’_{73} & \cdots & v’_{7N} \end{array} \right] $$

出力層にはコンテキストサイズ $C$ の分だけユニットがあり、各コンテキストでは重み $\boldsymbol{W’}$ を共有します。出力層も各コンテキスト毎に全結合されているので、重み $\boldsymbol{W’}$ と隠れ層の出力値 $\boldsymbol{v}_{w_I}$ を掛けたものが、出力層の各コンテキストのユニット $\boldsymbol{u}_c$ になります。

$$ \boldsymbol{u}_c = \boldsymbol{W’v}_{w_I} $$

出力層での活性化関数は softmax 関数を使いますので、最終的な出力値 $y_{c,i}$ は以下のようになります。この $y_{c,i}$ は、最初に Skip-gram でモデル化した時の確率になることは既にお分かりでしょう。

$$ y_{c,i} = \frac{\exp(u_{c,i})}{\sum_{v=1}^V \exp(u_{c,v})} = \frac{\exp(\boldsymbol{v’}_i \cdot \boldsymbol{v}_{w_I})}{\sum_{v=1}^V \exp(\boldsymbol{v’}_v \cdot \boldsymbol{v}_{w_I})} = p(w_{i}|w_I) $$

最適なパラメータを見つける

ネットワークの全貌が把握できたところで、重みを最適化する作業に入っていきましょう。ニューラルネットワークの最適化で最も良く使われるのは確率的勾配降下法 (SGD) ですので、ここでも SGD を使って最適化していきます。目標としているのは $w_I$ の周辺コンテキストにおいて各単語の出現確率を考えた同時確率 $p(w_1,w_2,\cdots,w_C|w_I)$ を最大化するような単語のベクトル表現を見つけることです。

SGD の目的関数として、以下のものを使います。

$$ E = - \log p(w_1,w_2,\cdots,w_C|w_I) \tag{1} $$

※ここでの対数は自然対数です。つまり底は $\mathrm{e}$ です。

先頭にマイナスをつけたのは、最大化問題を最小化問題に置き換えるためです。$f(x)$ を最大化する問題と、$-f(x)$ を最小化する問題は同じだということですね。

また、対数をとったのはアンダーフローを防ぎつつ計算を楽にするためです。今回、最適化の対象となる関数は前述の通り同時確率であり、同時確率の計算は 1 以下の数字を何度もかけることになりますので、値がどんどん小さくなっていきます。対数をとると、掛け算を足し算に変換できますので値が小さくなることを防げると共により簡単な足し算として計算できるようになります。

では、今考えているネットワークに対応させるために (1) を、ネットワークの出力 $y$ を使って表します。$p(w_1,w_2,\cdots,w_C|w_I)$ は、最初の方にも出てきましたが softmax の掛け算なので $y$ を使って以下のように表すことができます。

$$ p(w_1,w_2,\cdots,w_C|w_I) = \prod_{c=1}^C y_{c,w_c} \tag{2} $$

この (2)(1) に代入して変形を繰り返していくと、最終的には目的関数は以下のような形になります。

$$ E = - \sum_{c=1}^C \left( u_{c,w_c} - \log \sum_{v=1}^V \exp(u_{c,v}) \right) \tag{3} $$

最小化すべき目的関数 $E$ がわかったところで、$E$ を出力層と隠れ層の重み $\boldsymbol{W’}, \boldsymbol{W}$ の各要素で偏微分し、以下のような重みの更新式を得ることができます。

$$ \begin{eqnarray} v’_{ij} & := & v’_{ij} - \eta \sum_{c=1}^C (y_{c,i} - t_{c,i}) v_{w_Ij} \\ v_{w_Ii} & := & v_{w_Ii} - \eta \sum_{c=1}^C \sum_{v=1}^V (y_{c,v} - t_{c,v}) v’_{vi} \end{eqnarray} $$

※目的関数の変形及び偏微分の計算は省略しているので、興味のある人は補填を参照。
目的関数の導出, $v'_{ij}$ での偏微分, $v_{w_I}$ での偏微分

Negative Sampling

ニューラルネットワークを構築し、重みの更新式も手に入れたのであとは実装するのみになりました。さて、実装できたので学習するぞー、と意気込んで学習を始めてみたところ 1 つの問題にぶち当たります。それは計算量が爆発しすぎて学習がなかなか終わらない問題です。ネットワークの出力値である $y_{c,i}$ について思い出してみてください。

$$ y_{c,i} = \frac{\exp(\boldsymbol{v’}_i \cdot \boldsymbol{v}_{w_I})}{\sum_{v=1}^V \exp(\boldsymbol{v’}_v \cdot \boldsymbol{v}_{w_I})} $$

この式の分母に $V$ 回の繰り返しがあります。これまで使用してきたサンプルボキャブラリでは 7 個しか単語がなかったため問題ありませんが、先にも書いたように一般的に $V$ の語彙数は $10^5$ 〜 $10^7$ オーダーであるため、この部分の計算コストが高くつきます。しかもこれは、学習のイテレーション毎に計算しなおさなければなりませんので、なかなか学習が終わりません。そこで使われる高速化のテクニックが Negative Sampling です。

ある単語のペア $(w_I, w_O)$ が学習データから生成されたかどうかの確率を考え、それを $p(D=1|w_I,w_O)$ として、また逆に学習データから生成されて “いない” 確率を $p(D=0|w_I,w_O)$ とします。$D=1$ の方はシグモイド関数とし、$D=0$ の方は確率の定義から以下のようになります。

$$ \begin{eqnarray} p(D=1|w_I,w_O) & = & \sigma(\boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) \\ p(D=0|w_I,w_O) & = & 1 - p(D=1|w_I,w_O) \end{eqnarray} $$

上の 2 式から以下のような新しい目的関数を考えます。

$$ E = - \log p(D=1|w_I,w_O) \prod_{v \in V_{Neg}} p(D=0|w_I,v) \tag{4} $$

新しく $V_{Neg}$ という集合が出てきましたが、これは元々のボキャブラリの集合から適当に $k$ 個だけサンプリングしてきたものです。この $k$ 個のサンプルはランダムに選ばれるわけではなく、とある $P_n(w)$ という確率分布から生成されるサンプルを集めます。この $P_n(w)$ をノイズ分布と言い、Word2Vec では以下の様な確率分布をノイズ分布 $P_n(w)$ として使っています。式中の $U(w)$ は学習データ中に単語 $w$ が出現する回数です。

$$ P_n(w) = \frac{U(w)^{\frac{3}{4}}}{\sum_{v=1}^V U(w_v)^{\frac{3}{4}}} $$

このように学習に $k$ 個程度のサンプルを不正解データとして混ぜ込むことから Negative Sampling という名前がついています。この $k$ という値は、論文によると通常 5 〜 20 程度で十分であり、またデータセットが十分に大きければ 2 〜 5 個程度でも良い性能を発揮してくれるとのことです。

(4) の目的関数を最小化することで、正解単語には高い確率が割り当てられ、不正解単語 (ノイズ) には低い確率が割り当てられるような動きになり、それを元に単語ベクトルが学習されていきますが、この目的関数の意味するところは本質的には softmax 関数の近似です。元々は softmax の式を求めるためには $V$ 回の繰り返し計算が不可欠でしたが、これはたかだか $k+1$ 回の計算で softmax を近似できているため計算量的にかなり楽になっています。Noise Contrastive Estimation (NCE) と呼ばれる手法で別途論文が書かれており、それを参考にしているようです。

さて、(4) の目的関数を変形していくと最終的に以下のような式が得られます。

$$ E = - \log \sigma(\boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - \sum_{v \in V_{Neg}} \log \sigma(-\boldsymbol{v’}_{v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) $$

Skip-gram でやったのと同じように重みの更新式を導出するために $E$ を偏微分すると、最終的には以下のような重みの更新式が得られます。

$$ \begin{eqnarray} v’_{ij} & := & v’_{ij} - \eta (\sigma(\boldsymbol{v’}_i^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - t_i) v_{w_Ij} \\ v_{w_Ii} & := & v_{w_Ii} - \eta \sum_{v \in \{w_O\} \cup V_{Neg}} (\sigma(\boldsymbol{v’}_{v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - t_{v}) v’_{vi} \end{eqnarray} $$

※目的関数の変形及び偏微分の計算は省略しているので、興味のある人は補填を参照。
目的関数の導出, $v'_{ij}$ での偏微分, $v_{w_I}$ での偏微分

まとめ

Word2Vec の内部構造について書いてみました。中身がわからないうちはどうやって動いているんだろうと不思議でしたが、ちゃんと調べてみると自分でも理解できるような単純なニューラルネットワークだったので意外でした。結局やっているのは単純な 2 層ネットワークの重みの最適化ですしね。Negative Sampling の紹介もしましたが、こちらは高速化テクニックになるので不要であれば必ず実装する必要はありません。実際 Negative Sampling は Skip-gram が発表されてからしばらく後に提案されたもののようですし、時間がかかりながらも頑張って (3) の目的関数を最適化すればうまくいくのでしょう (やったことないけど)。

もしこれを読んでおおまかな流れがわかったのであれば、Word2Vec のソースコードを読む、または自分で実装してみるのも面白いと思います。私が読んだことがあるのはオリジナルの C での実装だけですが、世の中には他にも Python (gensim) や Java (Deepleaning4j) での実装があり、また Chainer や TensorFlow などのフレームワークを使った実装もあるようなので、学習環境には事欠かないのではないでしょうか。

最後に面白かったのが、とある論文の最後に「なぜこれが良い単語表現を見つけてくれるのか」という章があり、その内容が「良い質問だ。我々もまったく知らない」だったことです。ニューラルネットワーク界隈は経験則的にそれが良い結果を生み出すことはわかっていても、理論的になぜそうなるのかはわかっていないような問題が多く、Word2Vec もその典型なのでしょう。

参考リンク

論文集

実装

補填

本記事中で式の導出について省略した部分を、途中の式を示しながら導出していきます。

Skip-gram の目的関数

(2)(1) に代入すると Skip-gram の目的関数は以下の形をしています。

$$ \begin{eqnarray} E & = & - \log \prod_{c=1}^C y_{c,w_c} \\ & = & - \log \prod_{c=1}^C \frac{\exp(u_{c,w_c})}{\sum_{v=1}^V \exp(u_{c,v})} \end{eqnarray} $$

$\log$ の中身を掛け算から足し算に変換できる $\log(a \cdot b) = \log a + \log b$ という性質を利用すると、掛け算 $\prod$ は全部足し算 $\sum$ に変換できます。

$$ E = - \sum_{c=1}^C \log \frac{\exp(u_{c,w_c})}{\sum_{v=1}^V \exp(u_{c,v})} $$

今度は $\log$ の中身を割り算から引き算に変換できる $\log \frac{a}{b} = \log a - \log b$ という性質を利用すると、softmax 関数の部分を以下のように変換できます。

$$ E = - \sum_{c=1}^C \left( \log \exp(u_{c,w_c}) - \log \sum_{v=1}^V \exp(u_{c,v}) \right) $$

$\log \exp(x) = x$ なので、第一項の $\log \exp$ の部分がなくなります。

$$ E = - \sum_{c=1}^C \left( u_{c,w_c} - \log \sum_{v=1}^V \exp(u_{c,v}) \right) $$

これで (3) が導出できました。

Skip-gram の重み更新 (出力層)

出力層の重み $\boldsymbol{W’}$ の各要素で $E$ を偏微分するので以下を求めることになります。

$$ \frac{\partial E}{\partial v’_{ij}} $$

このままだと少しイメージし難いのでまず 1 つ具体的に、たとえば $v’_{11}$ で偏微分することを考えてみます。$v’_{11}$ は $\boldsymbol{W’}$ の 1 行目 1 列目の要素です。これが目的関数 $E$ の中のどこに出てくるかというと、出力層の各コンテキストのユニット $\boldsymbol{u}_c$ の 1 つ目の要素に含まれることになります。$\boldsymbol{u}_c$ の定義は以下のようなベクトルでした。

$$ \boldsymbol{u}_c= \boldsymbol{W’v}_{w_I} = \left[ \begin{array}{c} u_{c,1} \\ u_{c,2} \\ \vdots \\ u_{c,7} \end{array} \right] = \left[ \begin{array}{c} \color{red}v’_{11}v_{w_I1}\color{black} + v’_{12}v_{w_I2} + \cdots + v’_{1N}v_{w_IN} \\ v’_{21}v_{w_I1} + v’_{22}v_{w_I2} + \cdots + v’_{2N}v_{w_IN} \\ \vdots \\ v’_{71}v_{w_I1} + v’_{72}v_{w_I2} + \cdots + v’_{7N}v_{w_IN} \\ \end{array} \right] \tag{5} $$

これを一般化すると $v’_{ij}$ は $\boldsymbol{u}_c$ の $i$ 番目の要素 $u_{c,i}$ に含まれていると言えます。コンテキストは $C$ 個あるので偏微分は連鎖率を使って次のように分割できます。

$$ \frac{\partial E}{\partial v’_{ij}} = \sum_{c=1}^C \frac{\partial E}{\partial u_{c,i}} \frac{\partial u_{c,i}}{\partial v’_{ij}} \tag{6} $$

これをさらに計算していきます。項が 2 つあるので、まず最初に第一項、つまり $E$ を $u_{c,i}$ で偏微分するところから計算していきます。(3) の $E$ の $\sum$ を展開して以下のようにします。

$$ \begin{eqnarray} E & = & - \sum_{c’=1}^C \left( u_{c’,w_{c’}} - \log \sum_{v=1}^V \exp(u_{c’,v}) \right) \\ & = & - \sum_{c’=1}^C u_{c’,w_{c’}} + \sum_{c’=1}^C \log \sum_{v=1}^V \exp(u_{c’,v}) \end{eqnarray} $$

※$C$ に対する $\sum$ の変数が $c'$ になっているのは、既に (6) で $c$ を使っており、それとは区別したいためです。

これを $u_{c,i}$ で微分することを考えるのですが、さらにまた 第一項と第二項で分けて考えます。はじめに第一項についてですが、わかりやすくするために $\sum$ をはずしてみます。

$$ \sum_{c’=1}^C u_{c’,w_{c’}} = u_{1,w_1} + u_{2,w_2} + \cdots + u_{C,w_C} $$

たとえば偏微分する変数が $u_{1,i}$ だとすると $i = w_1$ であれば $u_{1,w_1}$ が微分されて 1 になるのがわかります。$u_{2,i}$ の場合も同じですね、$i = w_2$ であれば $u_{2,w_2}$ が微分されて結果は 1 になります。一般的に述べると偏微分する変数が $u_{c,i}$ の場合、$i = w_c$ であれば 1、それ以外であれば 0 ということになります。場合分けが入ると面倒なのでこれを $t_{c,i}$ という文字で表します。

$$ t_{c,i} = \begin{cases} 1 & (i = w_c) \\ 0 & (otherwise) \end{cases} $$

さらに第二項については、以下のように置き換えて連鎖率を使って微分します。

$$ \begin{eqnarray} g & = & \sum_{v=1}^V \exp(u_{c,v}) \\ f & = & \log g \\ \\ \frac{df}{dg} \frac{dg}{du_{c,i}} & = & \frac{1}{g} \exp(u_{c,i}) = \frac{\exp(u_{c,i})}{\sum_{v=1}^V \exp(u_{c,v})} = y_{c,i} \end{eqnarray} $$

これでようやく (6) の第一項が求まったことになり、最終的には以下のような形になります。

$$ \frac{\partial E}{\partial u_{c,i}} = y_{c,i} - t_{c,i} \tag{7} $$

また、(6) の第二項は

$$ u_{c,i} = v’_{i1} v_{w_I1} + v’_{i2} v_{w_I2} + \cdots + \color{red} v’_{ij} v_{w_Ij} \color{black} + \cdots + v’_{iN} v_{w_IN} $$

となるので、以下のように簡単に求められます。

$$ \frac{\partial u_{c,i}}{\partial v’_{ij}} = v_{w_Ij} \tag{8} $$

(6) (7) (8) を合わせると最終的に出力層の重みでの偏微分の結果が得られます。

$$ \frac{\partial E}{\partial v’_{ij}} = \sum_{c=1}^C (y_{c,i} - t_{c,i}) v_{w_Ij} $$

Skip-gram の重み更新 (隠れ層)

同じようにして今度は隠れ層の重み $\boldsymbol{W}$ の更新を考えていきます。ただし $\boldsymbol{W}$ は $\boldsymbol{W’}$ と違って、1 回の更新ですべての要素 $v_{ij}$ を更新することができません。どういうことかというと、今考えているニューラルネットワークでは $\boldsymbol{v}_{w_I}$ の重みしか伝搬していかないからです。

たとえば $w_I = 1$ の時を考えてみます。入力層のベクトル $\boldsymbol{x}$ は one-hot-vector だったために、隠れ層のユニットは $\boldsymbol{v}_1$ になるということを思い出してください。すると、その後の $\boldsymbol{u}_c$ や $\boldsymbol{y}_c$ には $\boldsymbol{v}_1$ の重みしか含まれておらず、他の $\boldsymbol{v}_2, \boldsymbol{v}_3, \cdots, \boldsymbol{v}_7$ は出てきません。このような状態で $\boldsymbol{v}_1$ 以外で偏微分したとしても全て 0 になってしまうので重みの更新ができません。

結局、ネットワークの入力となる $w_I$ に対応する重み $\boldsymbol{v}_{w_I}$ のみが更新できて、他は計算するだけ無駄になるため、ここでは $\boldsymbol{v}_{w_I}$ で偏微分することだけを考えます。出力層の重みを求めた時と同じように目的関数 $E$ のどこに $v_{w_Ii}$ が出てくるのかを探してみます。(5) を見てみると $v_{w_Ii}$ は $\boldsymbol{u}_c$ のどの要素にも含まれているのがわかります。$\boldsymbol{u}_c$ の要素数は $V$ 個、そしてコンテキストは $C$ 個あって、その全てに $v_{w_Ii}$ が含まれているので、偏微分は以下のようになります。

$$ \frac{\partial E}{\partial v_{w_Ii}} = \sum_{c=1}^C \sum_{v=1}^V \frac{\partial E}{\partial u_{c,v}} \frac{\partial u_{c,v}}{\partial v_{w_Ii}} \tag{9} $$

項が 2 つあるのでこちらもそれぞれで計算していくのですが、第一項は既に (7) で求めているので計算の必要はありません。また、第二項の方は (5) を見れば

$$ u_{c,v} = v’_{v1} v_{w_I1} + v’_{v2} v_{w_I2} + \cdots + \color{red} v’_{vi} v_{w_Ii} \color{black} + \cdots + v’_{vN} v_{w_IN} $$

となるので、以下のように簡単に求められます。

$$ \frac{\partial u_{c,v}}{\partial v_{w_Ii}} = v’_{vi} \tag{10} $$

(9) (7) (10) を合わせると最終的に隠れ層の重みでの偏微分の結果が得られます。

$$ \frac{\partial E}{\partial v_{w_Ii}} = \sum_{c=1}^C \sum_{v=1}^V (y_{c,v} - t_{c,v}) v’_{vi} $$

Negative Sampling の目的関数

以下の Negative Sampling の目的関数の最終的な形を導出していきます。

$$ E = - \log p(D=1|w_I,w_O) \prod_{v \in V_{Neg}} p(D=0|w_I,v) $$

まず $D=1$ の場合と $D=0$ の場合を、それぞれシグモイド関数 $\sigma$ を使って表せるので、それを求めてみます。$D=1$ の場合は 定義 より $\sigma$ そのものなのでこれはよいでしょう。$D=0$ の場合は以下のように計算して求めることができます。表記の簡単のために $u = \boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}$ と置いて計算を進めてみます。

$$ \begin{eqnarray} p(D=0|w_I,w_O) & = & 1 - p(D=1|w_I,w_O) \\ & = & 1 - \sigma(u) \\ & = & 1 - \frac{1}{1 + \exp(-u)} \\ & = & \frac{\exp(-u)}{1 + \exp(-u)} \\ & = & \frac{1}{(1 + \exp(-u))\exp(u)} \\ & = & \frac{1}{1 + \exp(u)} \\ & = & \sigma(-u) \end{eqnarray} $$

3, 4 行目は通分しており、4,5 行目は $\exp(-u) = \frac{1}{\exp(u)}$ を使いました。つまり目的関数 $E$ は $\sigma$ を使って以下のように書き直せます。

$$ E = - \log \sigma(\boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) \prod_{v \in V_{Neg}} \sigma(-\boldsymbol{v’}_{v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) $$

あとは Skip-gram の時と同じように $\log$ の中身を掛け算から足し算に変換できる $\log(a \cdot b) = \log a + \log b$ という性質を利用して、最終的な形に持っていくことができます。

$$ E = - \log \sigma(\boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - \sum_{v \in V_{Neg}} \log \sigma(-\boldsymbol{v’}_{v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) $$

Negative Sampling の重み更新 (出力層)

出力層の重み $\boldsymbol{W′}$ の各要素で $E$ を偏微分するので以下を求めることになります。

$$ \frac{\partial E}{\partial v’_{ij}} $$

前提として、Skip-gram と違って 1 回の更新で $\boldsymbol{W’}$ の全ての要素 $v_{ij}$ を更新することはできません。なぜなら目的関数 $E$ には $w_O$ 及び $v \in V_{Neg}$ の単語に対応する単語ベクトル $\boldsymbol{v’}$ しか含まれていないため、その他の要素での偏微分は全て 0 になり、そのような要素については重みの更新はできないからです。という注意書きをしておいて、それでは計算に進みます。

さて、目的関数 $E$ を以下のように置き換えて、連鎖率を使って微分するようにしてみます。

$$ \begin{eqnarray} u_k & = & \boldsymbol{v’}_k^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I} \\ E & = & - \log \sigma(u_{w_O}) - \sum_{v \in V_{Neg}} \log \sigma(-u_{v}) \\ \frac{\partial E}{\partial v’_{ij}} & = & \frac{\partial E}{\partial u_i} \frac{\partial u_i}{\partial v’_{ij}} \tag{11} \end{eqnarray} $$

まずは (11) の第一項から、つまり $E$ を $u_i$ で偏微分するところから考えてみます。これは $u_i$ の $i$ が $w_O$ なのか、それ以外なのかで微分結果が変わってくるため場合分けをします。まず $i = w_O$ の場合、$u_i$ は $E$ の第一項にだけ含まれているので、その部分を以下のように連鎖率を使って微分します。

$$ \begin{eqnarray} f & = & \sigma(u_i) \\ E & = & - \log f - \sum_{v \in V_{Neg}} \log \sigma(-u_{v}) \\ \frac{\partial E}{\partial f} \frac{\partial f}{\partial u_i} & = & - \frac{1}{f} \sigma’(u_i) \\ & = & - \frac{(1 - \sigma(u_i))\sigma(u_i)}{\sigma(u_i)} \\ & = & \sigma(u_i) - 1 \tag{12} \end{eqnarray} $$

※$\sigma'(x) = (1 - \sigma(x))\sigma(x)$ という式を利用しています。

次に $i \in V_{Neg}$ の場合について、こちらもまた連鎖率を使って以下のように微分していきます。

$$ \begin{eqnarray} f_i & = & \sigma(-u_i) \\ E & = & - \log \sigma(u_{w_O}) - \sum_{v \in V_{Neg}} \log f_{v} \\ \frac{\partial E}{\partial f_i} \frac{\partial f_i}{\partial u_i} & = & - \frac{1}{f_i} \sigma’(-u_i) \\ & = & \frac{(1 - \sigma(-u_i))\sigma(-u_i)}{\sigma(-u_i)} \\ & = & 1 - (1 - \sigma(u_i)) \\ & = & \sigma(u_i) \tag{13} \end{eqnarray} $$

※$\sigma'(-x) = -(1 - \sigma(-x))\sigma(-x)$ と $\sigma(-x) = 1 - \sigma(x)$ という式を利用しています。

(12)(13) を見比べると -1 がついているかいないかの違いしかないので、場合分けについて $t_i$ という変数を用意して隠すと、結局 $E$ を $u_i$ で偏微分した結果は以下のようになります。

$$ t_i = \begin{cases} 1 & (i = w_O) \\ 0 & (otherwise) \end{cases} $$

$$ \frac{\partial E}{\partial u_i} = \sigma(u_i) - t_i \tag{14} $$

ここまで来るとあとは (11) の第二項を求めれば良いだけですが、これは

$$ u_i = v’_{i1} v_{w_I1} + v’_{i2} v_{w_I2} + \cdots + \color{red} v’_{ij} v_{w_Ij} \color{black} + \cdots + v’_{w_iN} v_{w_IN} $$

なので、以下のように簡単に求められます。

$$ \frac{\partial u_i}{\partial v’_{ij}} = v_{w_Ij} $$

ということで、出力層の重み $\boldsymbol{W’}$ の各要素での偏微分結果については以下のような式が得られます。

$$ \frac{\partial E}{\partial v’_{ij}} = (\sigma(\boldsymbol{v’}_i^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - t_i) v_{w_Ij} $$

Negative Sampling の重み更新 (隠れ層)

隠れ層の重み $\boldsymbol{W}$ の各要素での偏微分を見ていきます。Skip-gram の時と同じように $\boldsymbol{W}$ については $\boldsymbol{v}_{w_I}$ の重みしか伝搬しないため $v_{w_Ii}$ の偏微分のみ計算すれば十分です。まず始めに $\boldsymbol{v}_{w_I}$ が $E$ の中のどこに含まれているかを探してみます。

$$ E = - \log \sigma(\boldsymbol{v’}_{w_O}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - \sum_{v \in V_{Neg}} \log \sigma(-\boldsymbol{v’}_{v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) $$

これを見て分かる通り $\boldsymbol{v}_{w_I}$ は全ての項に含まれていることがわかるので、連鎖率を使うと以下のように表すことができます。

$$ \begin{eqnarray} u_k & = & \boldsymbol{v’}_k^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I} \\ E & = & - \log \sigma(u_{w_O}) - \sum_{v \in V_{Neg}} \log \sigma(-u_{v}) \\ \frac{\partial E}{\partial v_{w_Ii}} & = & \sum_{v \in \{w_O\} \cup V_{Neg}} \frac{\partial E}{\partial u_{v}} \frac{\partial u_{v}}{\partial v_{w_Ij}} \end{eqnarray} $$

これの第一項については既に (14) で求めているため計算する必要はありません。そして第二項については

$$ u_{v} = v’_{v1} v_{w_I1} + v’_{v2} v_{w_I2} + \cdots + \color{red} v’_{vi} v_{w_Ii} \color{black} + \cdots + v’_{vN} v_{w_IN} $$

なので、以下のように簡単に求められます。

$$ \frac{\partial u_{v}}{\partial v_{w_Ii}} = v’_{vi} $$

よって偏微分は以下のようになります。

$$ \frac{\partial E}{\partial v_{w_Ii}} = \sum_{v \in \{w_O\} \cup V_{Neg}} (\sigma(\boldsymbol{v’}_{v}^{\mathrm{T}} \cdot \boldsymbol{v}_{w_I}) - t_{v}) v’_{vi} $$

  • このエントリーをはてなブックマークに追加
Archives