3.4.1：確率的最適化と逐次学習【白トピックモデルのノート】

はじめに

　『トピックモデルによる統計的潜在意味解析』の学習時のメモです。基本的な内容は、数式の行間を読んで埋めたものになります。本と併せて読んでください。

　この記事では、3.4.1節の確率的勾配降下法について書いています。

　数学よく解らない自分が理解できるレベルまで落として数式を書き下していますので、分かる人にはかなりくどいです。

【前節の内容】

www.anarchive-beta.com

【他の節一覧】

www.anarchive-beta.com

【この節の内容】

3.4.1 確率的最適化と逐次学習

・勾配法

　目的関数$f(x)$が最小となる$x^{*}$について考える。微分して0となる$x$を求められればよいのだが、できないことが多い。そこで、ランダムに決めた初期値$x^{(1)}$から更新を繰り返して$x^{*}$に近づけていく。このような手法を反復法と呼ぶ。

　まず、$f(x^{(1)})$の微分係数(傾き)$\frac{\partial}{\partial x} f(x^{(1)})$を調べる。微分係数が正の値だったとき、$x^{(1)}$をマイナス方向に少し動かすことで$f(x^{(1)})$が小さくなることが分かる。逆に微分係数が負の値だったとき、$x^{(1)}$をプラスの方向に少し動かすことで、目的関数が小さくなる。
　微分係数の正負と逆方向に動かすために、$x^{(s-1)}$から微分係数$\frac{\partial}{\partial x} f(x^{(s-1)})$を引いた値をs回目の更新値$x^{(s)}$とする。

$$ x^{(s)} = x^{(s-1)} - \frac{\partial}{\partial x} f(x^{(s-1)}) $$

　次に、1回の更新でどれだけ$x$を動かすのかを調整する。大きすぎると$x^{*}$飛び越えてしまうなどの問題が生じる。逆に小さすぎると、必要な更新回数が増えてしまう。
　そこで、微分係数$\frac{\partial}{\partial x} f(x^{(s-1)})$にステップサイズ(学習率)$\nu^{(s)}$を移動量を調整するための重みとして掛けた値を引くことにする。

$$ x^{(s)} = x^{(s-1)} - \nu^{(s)} \frac{\partial}{\partial x} f(x^{(s-1)}) $$

　更に、多次元関数に一般化する。$\boldsymbol{x} = (x_1, x_2, \cdots, x_n)$としたとき、微分係数のベクトル

$$ \frac{\partial}{\partial \boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) = \left( \frac{\partial}{\partial x_1} f(x_1^{(s-1)}), \frac{\partial}{\partial x_2} f(x_2^{(s-1)}), \cdots, \frac{\partial}{\partial x_n} f(x_n^{(s-1)}) \right)^{\top} $$

を勾配と呼ぶ。すると、先ほどの式は

$$ \boldsymbol{x}^{(s)} = \boldsymbol{x}^{(s-1)} - \nu^{(s)} \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) \tag{3.133} $$

となる。ここで、$\nabla_{\boldsymbol{x}} = \frac{\partial}{\partial \boldsymbol{x}}$とおく。
　この手法を勾配法の中でも最急降下法と呼ぶ。

・確率的勾配法

　続いて、目的関数が

$$ f(\boldsymbol{x}) = \sum_{i=1}^n f_i(\boldsymbol{x}) $$

の形をしている場合を考える。
　このとき、勾配は$\nabla_{\boldsymbol{x}} f(\boldsymbol{x}) = \sum_{i=1}^n \nabla_{\boldsymbol{x}} f_i(\boldsymbol{x})$となる。この式は$\sum$を含み計算コストが高いため、近似することを考える。
　そこで、目的関数を

$$ f(\boldsymbol{x}) = \sum_{i=1}^n f_i(\boldsymbol{x}) = n \sum_{i=1}^n \frac{1}{n} f_i(\boldsymbol{x}) $$

と変形すると、確率$p(i) = \frac{1}{n}$による$f_i$の期待値とみることができる。

$$ f(\boldsymbol{x}) = n \sum_{i=1}^n \frac{1}{n} f_i(\boldsymbol{x}) = n \mathbb{E}_{p(i)} [f_i(\boldsymbol{x})] $$

　従って、$\{f_i\}_{i=1}^n$から確率$p(i) = \frac{1}{n}$でサンプリングした$f_i$を用いて 　

$$ f(\boldsymbol{x}) = n \mathbb{E}_{p(i)} [f_i(\boldsymbol{x})] \approx n f_i(\boldsymbol{x}), \quad i \sim p(i) $$

とすれば、更新式は

$$ \boldsymbol{x}^{(s)} = \boldsymbol{x}^{(s-1)} - \nu^{(s)} n \nabla_{\boldsymbol{x}} f_i(\boldsymbol{x}^{(s-1)}) \tag{3.134} $$

となる。この式で逐次的に更新を行うことができる。
　この手法はアルゴリズムに乱数を含むことから確率的勾配降下法と呼ばれる。

　ではこれを用いて、ある確率変数$\theta$による期待値計算を含む目的関数

$$ f(\boldsymbol{x}) = \int p(\theta) f_{\theta}(\boldsymbol{x}) d\theta = \mathbb{E}_{p(\theta)}[f_{\theta}(\boldsymbol{x})] $$

について考える。
　この関数の勾配は$\nabla_{\boldsymbol{x}} \mathbb{E}_{p(\theta)}[f_{\theta}(\boldsymbol{x})]$である。これを、$\theta_i \sim p(\theta)$として確率的勾配$\nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x})$によりサンプル近似すると、更新式は

$$ \boldsymbol{x}^{(s)} = \boldsymbol{x}^{(s-1)} - \nu^{(s)} \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) $$

である。
　ここから更に、$\nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) - \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) = 0$を加えて

$$ \begin{align*} \boldsymbol{x}^{(s)} &= \boldsymbol{x}^{(s-1)} - \nu^{(s)} \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) \\ &= \boldsymbol{x}^{(s-1)} - \nu^{(s)} \Bigl( \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) + \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) - \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) \Bigr) \\ &= \boldsymbol{x}^{(s-1)} - \nu^{(s)} \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) - \nu^{(s)} \Bigl( \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) - \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) \Bigr) \\ &= \boldsymbol{x}^{(s-1)} - \nu^{(s)} \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) - \nu^{(s)} \boldsymbol{\epsilon}^{(s)} \tag{3.135} \end{align*} $$

と変形する。ここで、$\boldsymbol{\epsilon}^{(s)} = \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) - \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)})$とおく。

　$\boldsymbol{\epsilon}^{(s)}$は確率的勾配$\nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)})$と真の勾配$\nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)})$との差であるため

$$ \begin{align*} \boldsymbol{\epsilon}^{(s)} &= \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) - \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^{(s-1)}) \\ &= \nabla_{\boldsymbol{x}} f_{\theta_i}(\boldsymbol{x}^{(s-1)}) - \nabla_{\boldsymbol{x}} \mathbb{E}_{p(\theta)}[f_{\theta}(\boldsymbol{x}^{(s-1)})] \tag{3.136} \end{align*} $$

平均からのサンプル誤差を示す。
　従って、式(1.135)は、真の勾配による勾配法(3.133)に確率的なノイズ$\boldsymbol{\epsilon}^{(s)}$を組み込んだと見ることができる。

参考文献

• 佐藤一誠『トピックモデルによる統計的潜在意味解析』(自然言語処理シリーズ 8)奥村学監修,コロナ社,2015年.
• 中谷秀洋『わけがわかる機械学習』技術評論社,2019年.

おわりに

　明けましておめでとうございます。
　特に年末年始だったからという訳ではなく、初めて触れる内容だったため更新に日が空いてしまいました。
　今後もマイペースでやっていくので、宜しくお願い致します。

【次節の内容】

www.anarchive-beta.com