Exact Soft Confidence-Weighted Learning (ICML2012) 読んだ

概要

オンラインでの分類学習の世界では，CWが非常に強力なアルゴリズムとして注目されています．特に，その圧倒的な分類精度及び収束速度は圧巻の一言であり，自然言語処理を中心に様々な分野で応用例や派生アルゴリズムが提案されています*1．
一方で，ノイズデータのが混入していた場合に精度がガタ落ちする性質がCWの重大な欠点として多くの人から指摘されていました．ノイズが予め取り除かれている実験設定ならば良いのですが，ノイズが含まれている可能性の高い実データにはCWは中々不便．この問題を解決するため，ノイズ耐性の強いCW系アルゴリズムの決定版（？）として，SCW (Soft Confidence-Weighted)アルゴリズムがICML2012という会議で提案されました．本エントリでは，SCWの紹介を行います．

Exact Soft Confidence-Weighted Learning, Wang et al., ICML2012
http://icml.cc/2012/papers/86.pdf

CW (Confidence-Weighted Algorithm) *2

CWをはじめに少し紹介します．CW等のアルゴリズムでは，入力として与えられるベクトル $\mathbf{x}$ と重みベクトル $\mathbf{w}$ との内積の符号 $sign(\mathbf{x} \cdot \mathbf{w})$ を用いて分類を行います*3．

オンライン学習では，データを一つ読むたび，重みベクトルの値 (分類器)をより良いパラメータに更新します．ただし，一般の分類器では，各素性の出現頻度や学習度合の情報を考慮していないので，最適な値が大体判明した素性も，学習が全くなされていない素性も等価に扱われます*4．
上記の問題を解決するため，パラメータへの信頼度(Confidence)を導入し，CWでは重みベクトルがただの点ではなくガウス分布に従うと仮定します．重みベクトルの更新に分布の概念を導入することで，信頼度の低い(素性に関する情報があまり無い)パラメータは大きく更新し，一方で信頼度の高いパラメータはあまり変化させない，adaptiveなアルゴリズムを導出します．

CWの重みベクトル

$\mathbf{w} \sim N(\mathbf{\mu}, \mathbf{\Sigma})$

データを一つ受け取る度(入力ベクトル $\mathbf{x}_t$ とラベル $y_t$ )，以下の更新式に従いパラメータを更新します．
$(\mathbf{\mu}_{t+1}, \mathbf{\Sigma}_{t+1}) = \arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) \quad \quad s.t. \quad {Pr}_{w} (y_t \mathbf{w} \cdot \mathbf{x}_t \geq 0) \geq \eta$
制約式の部分は，ガウス分布にしたがって重みベクトルをサンプリングした時に，受け取ったデータを上手く識別できる確率が $\eta$ 以上になる事を条件付けています．KLとかかれた関数はKL-divergenceを示しており，ガウス分布間の「距離」を測ります．制約式を満たすガウス分布の中で，前のガウス分布から一番形を変えずに済む（距離が最小となる）新しいガウス分布への更新を上記の最適化問題で実現できます．この更新式は $\mathbf{\mu}, \mathbf{\Sigma}$ ともに閉じた形で更新式を導出することができます．(Section 2.3の(3)式参照)

CWは線形分離可能なデータに対して，有限回の更新で必ず全てのデータを上手く識別出来るパラメータを求められる事が保証されています．

CWのノイズ耐性

ただし，前述のようにCWはノイズを多く含むデータから学習を行う時精度がガタ落ちすることが指摘されています．今受け取ったデータにノイズが含まれていたとしても，「必ず $\eta$ 以上の確率で分類できる」ようにパラメータを更新するためです． $\eta$ の値を小さくすればノイズ耐性は多少強くなるけれども，正確なデータから学習をする際にもガウス分布の更新が緩やかになるため，最適なパラメータへ収束する速度も遅くなります．
ラベル付を誤ったデータや全体と性質の大きく異なるデータが混入しているデータから学習を行う時に特に問題となり，ノイズ的なデータでの更新の際に，急にパラメータがあらぬ方向へぶっ飛ぶ可能性があります．CWの提案後にこの問題は数多くの分野から指摘されており，急なパラメータ変更を防ぐ方法として複数の改良型アルゴリズム(AROW, NAROW, NHERD etc...) が提案されてきました．

SCW (Soft Confidence-Weighted Learning)

SCWもノイズ耐性に着目してCWに改良を施したアルゴリズムです．SCWは，「確率 $\eta$ 以上で正しく分類する」という絶対条件を緩めます．ガウス分布を大きく変更せざるを得ない場合には， $1-\eta$ 以上の誤分類率を許容し，急激なガウス分布の変化を防ぐ事が可能になります．

さて，最適化問題を変形します．Passive Aggressiveのソフトマージン化(PA-I,II)をご存知の方は見覚えがある変形になるかもしれません．
ガウス分布の定義に基づき，CWの制約式の部分を変形します*5．
$y_t (\mathbf{\mu} \cdot \mathbf{x}_t) \geq \phi \sqrt{\mathbf{x}_t^{T} \mathbf{\Sigma} \mathbf{x}_t}$
ここで， $\phi$ はガウス分布の累積密度関数の逆関数を $\eta$ で評価した値です．
この式を用いて，「 $\eta$ 以上の確率で正しく識別する識別平面からみた信頼度による重み付けマージン」を評価する，新たな損失関数を定義します．
$\ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t)) = max(0, \phi \sqrt{ \mathbf{x}_t^{T} \mathbf{\Sigma} \mathbf{x}_{t} }-y_{t} (\mathbf{\mu}_{t} \cdot \mathbf{x}_t))$
信頼度の高いパラメータを重視し，信頼度の低いパラメータはいくら平均値が大きくてもあまり重視しないように損失関数が定義されており，CWの長所が上手く保持されています(ルートの中身の値が大きくなる)．

この損失関数を用いて，CWおよびSCW-I,IIの最適化問題を以下のように定義します．

CW *6

$\arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) + \infty( \ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t)))$

SCW-I

$\arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) + C ( \ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t)))$

SCW-II

$\arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) + C ( \ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t))^2)$

上記の式から，SCWは損失関数を厳密に解くことなく，パラメータ $C$ を用いて上手くガウス分布の急激な変化と損失関数値を調節するように変形されていることが確認できます．SCWはCWと同じく閉じた形での更新式が記述できます．更新式は3章のProposition1 (SCW-I), Proposition2 (SCW-II)にて記載されています．更新式の導出は込み入った式変形が必要で，Appendixでゴリゴリと計算がされています．

また，SCWは

「ガウス分布間の距離」と「信頼度重み付けマージン」以外の補助的な項を一切導入しない

点で，その他のノイズ耐性を持つCW系アルゴリズムと一線を画しています．SCWの最適化問題は，ソフトマージンSVMの最適化問題を元にしており，

信頼度(Confidence)に応じて重み付けが変化する，マージン基準でのパラメータ更新を実現

している点がAROWやNHERD等と異なり，"Adaptive margin"を満たしている，と著者は書いています．また，CWと同じくSCWでも損失上限値の評価がされており，一定の条件下では損失の総和が爆発しないことが示されています．論文中の実験でも，AROW等のアルゴリズムと比べ非常に高速に収束する事が示されています．より少ないデータで高精度な分類器が導出されるのは，この"Adaptive margin"の性質ゆえであると著者は主張しています．

実装

せっかくなので，SCWを実装してみました．コードは汚いので参考にならないと思います．

classifier/src/confidence_weighted kisa12012/classifier GitHub https://github.com/kisa12012/classifier/tree/master/src/confidence_weighted

実装上の工夫として，上記のアルゴリズムから２点変更を施しています．

共分散行列の非対角項の零化

共分散行列の非対角項の零化ですが，共分散行列の非対角項を厳密に計算して精度が上がることはかなり稀です．CWおよびSCWの計算速度およびメモリ使用量のボトルネックになっているのは共分散行列の非対角項成分なので，ここの更新をどうサボるか重要になります．CWの論文でも計算量の削減のため，対角項のみを扱ったアルゴリズムが提案されています．
実現方法は単純で，共分散行列 $\mathbf{\Sigma}$ の更新時に， $\mathbf{x}_t \mathbf{x}_t^T$ *7の非対角項を0にするだけです．

多クラスへの拡張

Multi-ClassCWと同様の多クラス拡張をSCWに施し，3クラス以上の場合もSCWで学習可能な形にしています．

最後に簡単な実験結果を記載します．実験設定は，CW/SCW-I/SCW-IIに対して，Libsvm Datasetのrcv1.binary, rcv1.multiclassに適用してみました．ハイパーパラメータ $C, \eta$ の設定は適当．反復回数は1回(ワンパス)です．時間の方は正確に測ってはいませんが，更新式から分かる通り大きな差異はありません．
結果は以下のとおり．テストデータ中の正答数で比較しています．

rcv1.binary
CW
correct : 651136 / 677399
SCW-I
correct : 651462 / 677399
SCW-II
correct : 651085 / 677399

rcv1.multiclass
CW
correct : 456018 / 518571 
SCW-I
correct : 456634 / 518571
SCW-II
correct : 456399 / 518571

あまりノイズの多くないデータセットでの実験のためかそれほど大差は付きませんでした．が，SCWがコンスタントに強い事は示されています．ワンパスでほぼ収束し，反復回数を増やしてもそれ程精度は向上しません．流石CW，SCWです．ハイパーパラメータ設定を適当にやってこの結果なので，もう少し頑張ってパラメータチューニングすればSCWはさらなる精度向上が可能なんじゃないかなと推測しています．ただ，ハイパーパラメータが2つあるのでチューニングにはかなり手間がかかるため，適当にパラメータを設定しても良い識別器が導出できるSCWは安心して利用できます．
実データに関しては，まずはSCWから試してみる，で始めて問題ないのかなと思っています．

まとめ

SCWは，CWの弱点，ノイズや直前のデータへの脆弱性を緩和
AROW / NAROW / NHERDとの違いは，信頼度重み付けソフトマージン最大化を追求している点
CWと同じく損失上限値の証明もあり
もう線形識別器はSCWでいいんじゃないかな (他の問題が発見されるまで)

最後に

CWを実装されている方は，もし時間があればSCWを実装してみて試すことをおすすめします．また，更新式の導出方法や理論解析の詳細を追いたい方は，原論文を辿ってみる事を推奨します．特に2章のRelated Workでは，PA->CW->AROW->SCWの一連の流れが簡潔に纏められているため，オンライン学習系に興味がある方は必読と言ってもいいかも……？
上記の説明に誤りや勘違い等あれば指摘頂ければ幸いです．

参考文献

Exact Convex Confidence-Weighted Learning, Crammer et al., NIPS2008
Multi-Class Confidence Weighted Algorithms, Crammer et al., EMNLP2009
Adaptive Regularization of Weight Vectors, Crammer et al., NIPS2009
New Adaptive Algorithms for Online Classification, Orabona et al., NIPS2010

*1:SVMやPerceptronは全て捨てて，CWに移行してしまうのも良いと主張する研究者もいます．http://nlpers.blogspot.jp/2009/08/classifier-performance-alternative.html

*2:CWは様々なところで紹介されており，日本語の資料も充実しているため，そちらを参照されるのが良いかと思います．

*3:例として，レビュー文書のポジティブ・ネガティブ判定の場合，入力ベクトル x はレビュー文書中の各単語の出現回数を並べたベクトルとして表せます．この時，内積の値が0より小さければ，その文書をネガティブなレビューとして判定するようにタスク設定できます．レビュー文書を正確に分類できる，最適な重みベクトルの値を求めるために学習を行います．

*4:”I like the author, but this book is dull.”といったレビュー文書が与えられた時，”like”がレビュー文書をポジティブであると判定する上でとても有用な素性であると分かっていたとしても，その情報を扱うことが出来ず，”dull”と”like”に対しパラメータの更新は等価に施されます．

*5:ここの式変形を追いたい方は，CWの原論文を辿ると良いです．SCWの論文中には記載されていません．こちらの勉強会資料でもざっくり説明しています．http://www.r.dl.itc.u-tokyo.ac.jp/~oiwa/upload/AROW.pdf

*6:この定義は厳密ではなく，損失関数が制約の形で表現されるのが本来のCW

*7:論文中の $\Sigma_t \mathbf{x}_t^T \mathbf{x}_t \Sigma_t$ は， $\Sigma_t \mathbf{x}_t \mathbf{x}_t^T \Sigma_t$ の誤りと思われます．