前回の投稿では、ベイズ学習は以下の2ステップで行っていくことを述べた。
- 確率モデルの構築:グラフィカルモデルなどを利用しながら、事象の同時確率を定式化する。
- 推論:上で定式化した同時確率分布と、その未知のパラメータに対する周辺確率から事後確率を求める
前回の投稿では、ベイズ学習は以下の2ステップで行っていくことを述べた。
ベイズ学習は、観測できない未知の変数\(W\)の確率分布\(P(W)\)を、観測された事象(データ)\(D\)が得られたという条件のもとで推論するものです。すなわち事後分布\(P(W|D)\)を求める作業になります。
例えば、赤玉と白玉が入っている箱がありそれぞれの色の個数の割合\(\theta\)が未知である場合、その\(\theta\)の確率分布\(P(\theta)\)を箱から無作為に取り出した玉の色のデータ\(D\)を得られた事実をもとに推論する、すなわち\(P(\Theta|D)\)を計算するというようなものになります。
もう1つの例としては線形回帰\( y=\boldsymbol{w} \cdot \boldsymbol{x} +b\)の学習パラメータ\(\boldsymbol{w}\)、\(b\)を未知の変数としその確率分布\(P(\boldsymbol{w})\)、\(P(b)\)を観測データ\(D\)から求める、すなわち\(P(\boldsymbol{w}|D)\)、\(P(b|D)\)を計算するというものが挙げられます。
ベイズ学習は一般的に以下の2つのStepで行っていくといえます。
最近、ちょくちょくと人工生命(Artificial Life: ALife)というワードを聞くようになった。単語から読み取れるところなんとなくイメージできるけど、具体的にどういう研究なのか?どういう応用が期待できるか?人工知能(AI)と何が違うのか?などのイメージが沸かない。
こことここの記事がその疑問を少し解決してくれたので改めて整理したい。
データが逐次追加されていく際に、追加されるたびにその時点での「分散」や「標準偏差」を計算したい場合がある。その時点での全てのデータから毎度計算しても良いが、やはり計算量が馬鹿らしい。そこで欲しくなるのが、これらの量をオンライン(ストリーム処理)で計算できるアルゴリズムだ。
安心してください、ありますよ。「Welford アルゴリズム」というものです。
ここではそのWelfordアルゴリズムを紹介したい。
※以下、不偏分散を考えるが、標本分散の場合でも全く同じ考えが出来る。
データサンプルが\(x_i, \ldots, x_N\)で与えられる場合を考えられる。この時、データの不偏分散\(s^2\)の定義は
\[s^2 = \frac{\sum_{i=1}^N (x_i – \bar{x})^2}{N-1}\]
として与えられる。そして標準偏差\(s\)はその平方根\(s = \sqrt{s^2}\)だ。
ここで\(\bar{x}\)はサンプルの平均、すなわち\(\bar{x} = \frac{1}{N}\sum_{i=1}^N x_i\)である。
この定義通りに分散を計算する場合、以下の2ステップを辿る。
そこでWelfordアルゴリズムでは、サンプルが\(N\)個の時と\(N-1\)個の時の分散の差に着目して以下の計算を行う。
\begin{align} &(N-1)s_N^2 – (N-2)s_{N-1}^2 \\ &= \sum_{i=1}^N (x_i-\bar{x}_N)^2-\sum_{i=1}^{N-1} (x_i-\bar{x}_{N-1})^2 \\ &= (x_N-\bar{x}_N)^2 + \sum_{i=1}^{N-1}\left((x_i-\bar{x}_N)^2-(x_i-\bar{x}_{N-1})^2\right) \\ &= (x_N-\bar{x}_N)^2 + \sum_{i=1}^{N-1}(x_i-\bar{x}_N + x_i-\bar{x}_{N-1})(\bar{x}_{N-1} – \bar{x}_{N}) \\ &= (x_N-\bar{x}_N)^2 + (\bar{x}_N – x_N)(\bar{x}_{N-1} – \bar{x}_{N}) \\ &= (x_N-\bar{x}_N)(x_N-\bar{x}_N – \bar{x}_{N-1} + \bar{x}_{N}) \\ &= (x_N-\bar{x}_N)(x_N – \bar{x}_{N-1}) \\ \end{align}
この結果から、下式のようにデータが\(N\)個の時の分散を\(N-1\)個の時の分散から求められることがわかる。
\[ s_N^2 = \frac{N-2}{N-1} s_{N-1}^2 + \frac{1}{N-1} (x_N-\bar{x}_N)(x_N – \bar{x}_{N-1}) \]
この結果をもとに分散をオンラインで計算するアルゴリズムに落とすと、下の疑似コードのようになる。(forで各データを逐次回している部分がそれだ)
驚くほど簡単なアルゴリズムだ。
簡単なので必要に応じて自分で実装すれば良いが、Python用のライブラリを作ってPypiに登録してみたのでよければそれを使ってみてください。改良点があればGithubリポジトリにIssue投げて頂ければ嬉しいです。
■参考
最近、Kaggleだとかその周辺では、XGboostだとかcatboostだとか、Gradient Boosting(勾配ブースティング)の手法が流行っているらしい。最終的にcatboostを勉強する目的で、その前段階として勾配ブースティングをひととおり勉強したので、そのメモ。