機械学習 はじめよう

第16回 最適化のための勾配法

この記事を読むのに必要な時間:およそ 1 分

確率的勾配降下法

そのような勾配法ですが,機械学習の問題にいざ使おうとすると計算が結構大変なことがわかります。

というのも,機械学習の目的関数のほとんどは次のような形をしています。

fwはモデルによって一つの点に対する誤差であったり,確率の関数(負の対数尤度)であったりしますが,⁠各点ごとの値をデータ点の分だけ和をとる」という大枠は共通です。

これを勾配法で解くためにwでの微分を求めても,やはり「データ点の分だけ和をとる」形になっています。

勾配法でパラメータを更新するには,この微分を毎回求めるわけですが,データ点が多いとその個数だけを計算しなくてはいけません。データは10個とか100個ではなく,10,000個,100万個とあったりしますから,とても大変です。

なにかいい方法はないものでしょうか。nで和をとるのが大変なのだから,上の式から単純にΣがなくなったら,次のように簡単になりそうです。

これならデータ点がいくらたくさんあっても一回の計算は超簡単でとてもハッピー……いやいやさすがに,これはまずいでしょう。本当にただΣを取っただけではないですか。残ったnもどうしろというのでしょう。まさかランダムに選ぶとか,いくらなんでもそんなひどい話はあり得ませんよね……?

ところが実はそんなひどい話がまかり通っていまして,一見うまくいくようにはとても見えないこの式が「正しい勾配法」よりもうまくいく場合も珍しくなく,もちろん計算はものすごく速い,というのですから本当に困ってしまいます。

というわけで名前も付いていて,⁠確率的勾配降下法」と呼びます。一方,Σが残っている「一番素直な勾配法」「最急降下法」と呼びます。

nはやはりすべての値をぐるっと一周するのですが,順番は本当にランダムで,むしろその方がいいことが知られています。名前に「確率的」とついているのは,実行する度に結果が変わることを表しています。

ちなみに「確率的~」という名称は,いわゆる確率を組み込んだモデルを表す場合と,乱数を使っていて実行する度に結果が異なるアルゴリズムを表す場合があり,ややこしいです(名前を分けて欲しいですよね)⁠

話を元に戻して,nをぐるっと一周回しただけでうまく行くなんてことはさすがになく,データ全体を何周か計算させる必要はどうしてもあります。それでも最急降下法の1回分と同じ計算量でN回移動できるおかげで,非常に速く局所解の周りにたどり着くことが期待できるのです。

データ点xnごとにfw(xn)のwに関する最小点は異なりますから,確率的勾配降下法では点を動かす度に異なる目標に近づこうとするようなものです。それでも全体を平均すればだいたいうまくいくというのが確率的勾配降下法の主張です。それだけではなく,毎回目標が異なるおかげで,局所解に引っかかりやすいという勾配法最大の弱点をそこそこ回避できる(可能性がある)という特徴も備えています。

一方,毎回目標が異なるおかげで,いつまでたっても点がうろうろと動き続けて「収束」しないという振る舞いもになります。そこで一般には,データを一周回す度に学習率ηを適当に小さくしてあげるという対策が必要になります。

確率的勾配降下法の性質について,いくつかの限定的なケースについては理論的に確かめられている部分もあるのですが,ほとんどは「経験的によい性質を持つことが知られている」という範囲にとどまります。便利で強力な手法ですが,決して最適解を求めているわけではないことは念頭に置いて使うべきでしょう。

ちなみに,このようにデータ全体をまとめて使うのではなく,一件ずつ使って学習することを「オンライン学習」と呼びます。コンピュータ業界で使われる「オンライン」という言葉とは意味がかなり違うので,⁠最適化」に引き続き注意しなくてはいけませんね。

パーセプトロンの場合

さて,前回紹介したパーセプトロンの解き方を勾配法から見直してみましょう。

パーセプトロンでは,xnでの誤差を次のように仮定しました。

:予測が間違っているとき

:予測が正しいとき

したがって誤差関数は次のようになります。

ただし Mはパラメータa,b,cの元で不正解になるデータ(xn,yn,tn)を与えるnの集合とします。

この誤差関数Eを目的関数とした最適化問題を確率的勾配降下法で解いてみましょう。

確率的勾配降下法ですから,和をとる前のE(xn;a,b,c)をa,b,cで偏微分する必要があります。

予測が正解していればE(xn;a,b,c)=0であり,その偏微分も0ですから,不正解の場合のみ考えればよいことになります。

このことから,確率的勾配降下法による更新式は次のようになります。

この式のηを1にすれば,前回紹介したパーセプトロンの学習式が得られます。

先ほど,確率的勾配降下法では一般的に学習率ηは小さくしていくという話をしたばかりですが,パーセプトロンの場合は特別にη=1に固定します。というのも,⁠データが線形分離可能ならば,η=1で固定のときにこのアルゴリズムは有限回で停止する(すべての予測が正解する)⁠ことが示されているからです(パーセプトロンの収束定理)⁠

これはパーセプトロンのこのアルゴリズムに特化したアプローチで示されているもので,一般の問題について確率的勾配降下法が収束を保証されることはまずありません。

パーセプトロンの学習アルゴリズムは,いろんな意味で確率的勾配降下法の特殊例ということなのです。

今回紹介した確率的勾配降下法は,このあとロジスティック回帰の学習にて活躍する予定ですが,その前に次回は実践編としてパーセプトロンを実装してみることにします。お楽しみに。

著者プロフィール

中谷秀洋(なかたにしゅうよう)

サイボウズ・ラボ(株)にてWebアプリ連携や自然言語処理を中心に研究開発を行いながら,英単語タイピングゲーム iVocaをサービス提供している。

URLhttp://d.hatena.ne.jp/n_shuyo/
Twitterhttp://twitter.com/shuyo