Confidence Weighted Linear Classificationを読んだ

　ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。
　Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。
　こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類に失敗した場合、パーセプトロンではI, liked, this, authorの4つの単語(素性)に大してプラスの重みが足される。また、否定的な評価のサンプルとして、"I liked this author, but found the book is dull."というものがあったとすると、それぞれの単語に対し、均等に重みが引かれる。この均等というところが問題で、例えば、"liked"という単語はよく出てくるので安定した値の推定が可能であり、しかも肯定的な評価を表している場合が多いので、否定的なサンプルがあったからといって、それによってあまり重みを減らしたくない。一方、"dull"という単語は珍しいので、一回の更新で大きく重みを変更したい。
　これを実現するために、重みパラメータの確率分布を考える。重みパラメータは多次元正規分布に従って分布すると仮定し、重みパラメータの分散をパラメータとして追加する。ベクトルを多次元正規分布で扱うということでその分散は分散共分散行列となるが、計算機資源の観点から、これは対角行列に制限する。パラメータの分散とはつまりパラメータに関する確信度であり、分散が大きいということはそのパラメータの推定にあまり自信が持てない、つまり確信度が低いということになる。
　i番目のラウンドでの確率分布をP_iとすると、Confidence Weightedでは、P_iとP_(i-1)のKL-Divergence、つまり確率分布間の距離みたいなものを、「η以上の確率でi番目のサンプルの分類に成功する」という制約の元で最小化する。P_iというのは多次元正規分布であり、距離を最小化するというのは要するにパラメータをうまく更新するということである。
　これはいくつかの式変形を行うと凸最適化問題に変形することができる（ただし、凸最適化問題にするために、少しだけ問題を変形している）。凸最適化問題になれば、さまざまな最適化ソルバで解く事ができる。しかし、1つのサンプルを見る度に最適化ソルバが走るのでは重いので、閉じた形でパラメータを更新するための近似解法を考案する。これを論文ではVarianceアルゴリズムと呼んでいる。
　近似解法では分散を対角行列には制限せず、それを後で対角行列に射影する。その他の部分はオーソドックスにラグランジュの未定乗数法を用いており、特筆すべき点はなさそうに見える。
　実験結果であるが、同じデータセットを何回か学習に使った場合、Confidence Weightedは1回目で学習がほぼ収束しており、それ以降はほとんど性能が変わらない。つまり、収束がとても速い。
　性能自体も、他の手法と比べ遜色ないどころかとても良い性能を示した。バッチ学習型アルゴリズムであるSVMや最大エントロピー分類器などと比べても、ほとんどの実験データでConfidence Weightedの方が良い性能であった。（ただし、たぶんこのSVMは、カーネルを使ってない。）
　また、大規模データの学習のためにデータセットを分割して学習した場合、出来上がったパラメータを一つの分類器に統合する際、単純に平均をとるのか、それともKL-Divergenceの和を最小化するように統合するかで、性能がどれぐらい変化するか実験をしている。（結果はデータセットによって少し傾向が違うが、まぁそれほど性能が変わるというほどの物でもなかった。）
　論文を読んだ感想としては、特に変な事は書いておらず、式変形もちょっと考えればそれほど飛躍なく追いかけられて読みやすかった。オンライン学習で学習時間が短く性能も良いとなると、実用的にもかなり便利に使うことができそうだ。オンライン学習も最近は性能がよくなっている、という話は何度か聞いたことがあったが、実際にバッチ学習型アルゴリズムと遜色ないどころか上回るような性能を示している実験結果をみると、驚きであると言うしかない。
　まとめとしては、パラメータを多次元正規分布から生成されたものと考え、その分散を信頼度として扱うことで、収束の早い線形識別器の学習アルゴリズムを考案した、という感じかな。
　最後にちょっと余談を書いておくと、この論文のLast AuthorであるFernando Pereiraは機械学習などの分野では有名人(らしい)で、これまではずっとペンシルバニア大学に在籍していたのだが、2008年からGoogleに所属が移っているみたいだ。なんとまー。