FOBOSを実装してみた(理論編) - Goto

■概要
利用可能な言語資源(Wikipedia, GSK Corpus, Google N-gram Corpusなど)が急激に拡大してきており、これに伴ってより多くの言語データを扱えるようになったことで統計的機械翻訳の翻訳精度は急激に上昇してきています。一方で，大量に保存されてきた言語資源を利用するデータマイニングなどで機械学習と呼ばれる技術が扱われるようになってきました。このような分野において、シンプルな線形識別モデルと凸最適化を組み合わせたオンライン学習により、大量のデータを利用した高速な学習と識別が可能になることが分かり、近年になって注目されるようになってきました。
ここでは、オンライン凸最適化アルゴリズムとして有名なFOBOSについて説明していきたいと思います。

■はじめに
そもそもこのブログを書こうと思ったきっかけは、大学の講義で

「オンライン凸最適化アルゴリズムの最近の手法(FOBOSやPegasos)の概要をまとめよ」

とレポート課題が出されたことがきっかけで、実装が簡単な割に高速で性能が良いことで有名だったFOBOSについてちょうど知っておきたかったこともあって、今回実装してまとめてみることにしました。
(ちなみに、提出期限は去年の年末で、提出してすぐにブログに書きたかったのですが、今まで更新をサボっており、今に至っているという訳です…)

具体的な説明に入る前に、FOBOSを知るために必要な構成要素についてまとめると、この手法を特徴付けるキーワードとして以下の4つが挙げられると思います。

オンライン学習
凸関数
劣勾配法
正則化

少し細かい分類になってしまったかもしれませんが、今後の説明のためにそれぞれについてもう少し詳しく説明しておきます。

オンライン学習とバッチ学習
まず、オンライン学習とバッチ学習の違いについてですが、自分の中の定義では以下のようになっています。

・バッチ学習
　　訓練データを全部読み込んでから重みパラメータを更新する、という処理を繰り返す手法のこと
・オンライン学習
　　各訓練データ毎に重みパラメータを逐次更新する、という処理を繰り返す手法のこと

もちろん両方において長所と短所があります。
バッチ学習は、オンライン学習に比べて汎化性能は良いですが、欠点として蓄積した大量の訓練データを扱う必要があるため、処理が重く、使用するメモリ量も多くなります。また、オンライン学習は、先程も述べたように実装が簡単な場合が多く、訓練データを蓄積する必要がないので大量のメモリを必要とせず、新しいデータを入手した時にも再学習が容易になります。しかし、学習率を適切に設定しないと重みパラメータ収束が不安定になったり、訓練データの順番に偏りがあった場合に精度が不安定になります。

凸関数の性質
近年(？)になって、最適化問題を凸計画問題(convex programming problem)で表すことで比較的簡単に最適解を求められるということで注目が集まっていますが、それは凸計画問題の中で扱われる下に凸な凸関数(convex function)が以下のような性質を持っているからだと言えます。

凸関数の線形和は凸関数になる

アフィン合成後の関数も凸関数になる

凸関数の最大値は凸関数になる

1次条件が成立する

$\hspace{50}$ $f(\cdot)$ が凸 $\Leftrightarrow f({\bf y}) \geq f({\bf x}) + \nabla f({\bf x})^{T}({\bf y} - {\bf x)$ ， $\forall {\bf x}, {\bf y}$

2次条件が成立する(ヘシアンが正定値)

微分して勾配0になる局所最適解(停留点)は大域的最適解になる(SVMなどの目的関数の場合)

例えば、FOBOSでは最適化の目的関数として損失項(後述)と正則化項(後述)の和を最小化していく必要があるのですが、それらの両方が共に凸関数であれば、上述の性質により目的関数も凸関数になります。
このようにして凸関数は次に示す(劣)勾配法と組み合わせることによって最適解を求めることができます。

劣微分と劣勾配法
例えば、SVMの損失項として用いられるHinge-Lossの極値を求める場合、閉じた形で解を求めることができません。そこで、データから勾配を計算して次第に極値へと近づけていくこと(勾配法)を考えます。しかし、勾配法では目的関数が微分可能であるという前提条件があり、微分不可能な点では勾配は計算できないので、勾配法は使えません。そこで、劣微分や劣勾配法の考え方が必要になってきます。

・劣微分の定義
まず、凸関数の1次条件
$\hspace{50}$ $f({\bf x}) \geq f({\bf x}_{0}) + \nabla f({\bf x}_{0})^{T}({\bf x} - {\bf x}_{0})$
を元に劣微分の定義を考えると、ある凸関数 $f$ の ${\bf x}$ における劣微分(subdifferential)は、以下のように表されます。
$\hspace{50}$ $f({\bf x}) \geq f({\bf x}_{0}) + {\bf g}({\bf x}_{0})^{T}({\bf x} - {\bf x}_{0})$
ここで、 ${\bf g}$ はある凸関数 $f$ の ${\bf x}$ における劣勾配(subgradient)であり、上式を満たす ${\bf g}$ は関数 $f$ の ${\bf x}$ における劣勾配になります。(ちなみに、微分可能な点における劣微分の値は1つに定まり、その値は微分の値と一致します。)

・劣勾配法
重みパラメータを更新するためのオンライン学習アルゴリズムの例として確率的勾配降下法(Stochastic Gradient Descent:SGD)が挙げられますが、通常のSGDでは微分不可能な点があると最適化できないので、劣微分を使った劣勾配法で最適化を行う必要があります。劣勾配法は、微分不可能な場合でも勾配を定義しようとするもの(何か擬似逆行列と似てますね…)で、微分不可能な点がない場合にはSGDと同じであることから、使える適用範囲が広い手法と言えます。

過学習と正則化
最後に、過学習と正則化の定義について説明しておきます。
一般的に、自然言語処理では過学習が問題になることはないようですが、重みパラメータの次元数が膨大になります。そのため、正則化によりスパース(Sparse)な解にすることで、重みパラメータを保持するメモリ量が少なくなり、高速な計算も可能になります。

・過学習
　　訓練データに過剰に適合してしまい、訓練データは分類できる(経験損失は小さくできる)が、未知のテストデータは分類できなくなってしまう(期待損失は大きくなってしまう)状態のこと
・正則化
　　学習モデルの複雑さに対してペナルティを与えること
　　よく使われる正則化にはL1正則化(L1-norm)とL2正則化(L2-norm)があり、L0正則化(L0-norm)などもある。(数字が小さいほど重みパラメータベクトルの非0要素を減らそうとする力が働くが、最適化が困難になる。)

■従来のオンライン学習アルゴリズム
先程説明した微分不可能な点で効果のある劣勾配法ですが、損失項にL1正則化項を導入することで最適解では多くの重みパラメータが0になるはずですが、劣勾配法ではスパースな解が得られません。この現象は微分不可能な点で起こることが多く、さらに微分不可能な点が最適解であることが多いため、何とかしてL1正則化と劣勾配法を上手く組み合わせて最適解を求めることが必要になります。このような欠点を克服した手法としてFOBOSなどの手法が挙げられます。だいたいの話の流れは分かったでしょうか？

■FOBOS
まず、今回紹介しているFOBOSの論文についてですが、
http://jmlr.csail.mit.edu/papers/v10/duchi09a.html
で見ることができます。ただ、この論文はジャーナルで長いので2009年のNIPSに投稿された
http://www.cs.berkeley.edu/~jduchi/projects/DuchiSi09_folos.html
もあります。

FOBOSの特徴として、例えば目的関数 $J({\bf w}) = f({\bf w}) + r({\bf w})$ の損失項 $f({\bf w})$ (間違いに対して与えるペナルティ)と正則化項 $r({\bf w})$ (過学習という状態に対して与えるペナルティ)について

損失項 $f({\bf w})$ は微分可能
正則化項 $r({\bf w})$ は微分不可能

とした時に、 $J({\bf w})$ を最小にする ${\bf w}$ を確率的勾配法(SGD)で求めるという点で劣勾配法に似たオンライン学習アルゴリズムです。しかし、劣勾配法では損失項と正則化項の両方の勾配をまとめて計算していましたが、FOBOSでは最初に劣勾配法で重みパラメータを更新しながら損失項 $f({\bf w})$ のみを最小化し、次に更新した重みパラメータをなるべく動かさずに正則化項 $r({\bf w})$ を最小化する ${\bf w}$ を求めるようにして、重みパラメータの更新を2ステップに分けている点が従来の手法と異なります。

まず、損失項部分の処理に関しては、 $f({\bf x)$ の劣勾配を計算して最小になる方向に進みます。
次に、正則化項部分の処理に関しては、Proximal勾配法(Proximal作用素とかProximal最小化とか出てくるのですが、逐次最適化を行う方法のようです。これ以上詳しいことは知りません…)の式変形により正則化項を閉形式(closed-form)の重みパラメータ更新式に変形して最適な解を計算しています。ここでは、L1正則化とL2正則化の場合についてだけ示します。他にも論文では、L1正則化とL2正則化のハイブリッドであるBerhu正則化(0に近い部分ではL1正則化の影響でスパースな解が得られ、値が大きい部分ではL2正則化の影響で極端に大きな値はなくなります。)についても紹介しているのですが、今回は省略しますm(_ _)m

・L1正則化の場合
$\hspace{50}$ ${\bf v} = {\bf w}_{t} - \eta \nabla f({\bf w})$
$\hspace{50}$ ${\bf w}_{t+1} = {\rm argmin}_{w} \left( \frac{1}{2} ||{\bf x} - {\bf v}||^{2} + \lambda ||{\bf w}||_{1}\right)$
・L2正則化の場合
$\hspace{50}$ ${\bf v} = {\bf w}_{t} - \eta \nabla f({\bf w})$
$\hspace{100}$ $r({\bf w}) = \frac{\lambda}{2} ||{\bf w}||^{2}_{2}$ ，勾配降下，幾何減少
$\hspace{100}$ ${\bf w}_{t+1} = \frac{{\bf v}}{1 + \lambda \eta}$
$\hspace{100}$ $r({\bf w}) = \lambda ||{\bf w}||_{2}$ ，更新　有／無
$\hspace{100}$ ${\bf w}_{t+1} = \left( 1 - \frac{\lambda \eta}{||{\bf v}||_{2}} \right)_{+}{\bf v}$

ここで、 $\eta$ と $\lambda$ は学習率のことで、 ${\bf v}$ は勾配方向に少しだけ ${\bf w}_{t}$ を進めたものになります。例えばL1正則化では、 ${\bf w}_{t+1}$ を求める場合の目的関数の値は非負の数の和であり、それぞれの項は独立しています。また、Proximal勾配法の式変形により重みパラメータ更新式を閉形式にしたことで、勾配法などでラグランジュの未定乗数法を使って重みパラメータ更新式の最適値を計算できるようになります。