確率単体上で勾配法をしようと思ったことはありませんか?僕はあります.

確率単体とは

確率単体とは次のように定義されます.

このような性質があるため, は離散分布の確率分布と考えることができます.ある目的関数があり,最適な分布を勾配法を用いて求めることを考えます.
上で勾配法をする上で,にパラメーターが制限された状態で勾配法をしなければなりません.
この記事では,パラメーターが確率単体に制限された上での勾配法を考えてみます.

そういえば勾配法については,Qiita AdventCalendarでこんな記事も書いたのでよかったら読んでみてください.
確率的勾配降下法の理論入門(実験編)
確率的勾配降下法の理論入門(証明編)

勾配降下法振り返り

最小化する目的関数をとします.勾配降下法とは次のような更新式でした.

はステップ幅と呼ばれるパラメーターです.ところで,この更新式は次のように修正できます.

ここで,はベクトルの内積です.
第1項は,目的関数 を線形近似したものに対応します.第2項は,前の時刻のパラメーターから離れすぎることに対するペナルティの項であると解釈できます.

証明

とおいて,極小値をとるを求めれば良いです.

移項すると,が得られます.(証明終わり)

これをもとにして,パラメーターをに制限した場合を考えると,次のように拡張できます.

ここのargminは次のように陽に計算することができます.

証明

ラグランジュの未定乗数法に基づいて,ラグランジュ関数を次のように定義します.

から,を求めると,がわかります.
であり,なので,

これをに代入すると,目的の更新式が得られます.(証明終わり)

指数勾配降下法

さて,パラメーターのずれに関するペナルティですが,必ずしも二乗ノルムでなくとも良いです.
特に確率単体 上のパラメーターに関しては,二乗ノルムではなく,KLダイバージェンスが自然であると考えることができます.KLダイバージェンスは次のような式で表されます.

これを用いると.パラメーターの更新式は次のように拡張できます.

ところで,この argmin はラグランジュの未定乗数法を用いると,次のように陽に書くことができます.

この更新式を,指数勾配降下法 (Exponentiated Gradient Descent)といいます.

証明

ラグランジュの未定乗数法に基づいて,ラグランジュ関数を次のように定義します.

から,を求めると,がわかります.
変形して整理すると,となります.
を用いて,がわかります.
これを再びに代入すれば,目的の更新式が得られます.(証明終わり)

比較(GD vs EGD)

確率単体上の勾配降下法(GD)と指数勾配降下法(EGD)を比較しましょう.
更新式を見るとGD,EGDはともに,が満たされているのはわかります.
しかし,GDの方は,が大きすぎると,負の値を取り得てしまう問題があります.一方で,EGDはexpで構成されているため,負の値は取り得ないことがわかります.
ただし,EGDはの計算が必要で,の場合はになってしまうので,計算機上では,この辺りに工夫が必要でしょう.

計算機実験

を目的関数として勾配法を計算機上で実行してみます. が最適解となります.
下の図は,目的関数の等高線と,GD, EGDによるパラメーターの推移をプロットしたものです.

egd_vs_gd

この図を見ると,EGDの方が最適解に向かって,GDより早く向かってることがわかります.
もちろんこのような現象は目的関数に依存するのだと思いますが,先述のペナルティー項を二乗誤差にとるのが常に良いというわけではないということがわかります.

まとめ

  • 確率単体の上では指数勾配法を用いると,パラメーターが負の値になるのを防ぐことができる.
  • 指数勾配法の方が有利である目的関数もある.

参考文献

鈴木大慈 『確率的最適化』