この記事ではパーセプトロンを使って文書分類器を学習し、学習済みの分類器を使って文書を分類する流れをご紹介します。パーセプトロンはシンプルな分類アルゴリズムの一つである一方で、これを理解していると他の分類アルゴリズムを理解する助けになるため、初めて機械学習を学ぶ初学者の方にとってよい題材といえます。 この記事に載せているプログラムはここにまとまっています。
(Structured Perceptron with Inexact Search, NAACL 2012) を読んだ。
構造化パーセプトロンは構造を持つ出力を予測するパーセプトロンであり、自然言語処理では品詞タグ付けなどに用いられる。出力を予測する際には効率的に出力を探索するために、ビームサーチが用いられることが多いが、一般的な構造化パーセプトロンに対してビームサーチを適用すると、パーセプトロンの収束性が保証されない。
構造化パーセプトロンを効率的に学習する手法として、early updateというヒューリスティクスな手法が提案されている。early updateは出力を予測する途中で正解でないとわかった段階で場合に重みを更新するヒューリスティクスな手法である。しかしながら、early updateはラベル列を最後まで見ずに重みを更新するのにも関わらず、violation fixingという枠組みで収束が保証される。
AdaBoostはKaggleなどのコンペで良い成績を出しているアンサンブル学習手法の一つである。このエントリはまずAdaBoostの概要および、なぜAdaBoostが高い汎化能力を示しやすいのかをまとめる。汎化能力が出やすい理由を調査することで、Large Margin Distribution Machineへと発展していった、という経緯を俯瞰することを目的とする。
具体的にはZhi-Hua Zhou先生のスライド (From AdaBoost to LDM) を眺めて、自分の理解のためにメモとして残したものになっている。
概要
- パーセプトロンは学習事例を受け取り重みベクトルを更新する、という処理を反復した後に重みベクトルを出力する
- 平均化パーセプトロンは過去の反復で学習した重みベクトルの平均を出力する
- 平均化パーセプトロンは実装が簡単でありながら、良い予測精度が出ることが多い
- 素直に平均化パーセプトロンの出力を計算しようとすると各反復における重みベクトルを保持する必要がありメモリ的に学習が非効率であるため、実際には今回メモする方法で実装されることが多い
拙作のgonlineに並列での学習もサポートするようにした。 分散環境での学習は手間がかかりそうだったので並列での学習のみとしている。 並列での学習にはIterative Parameter Mixture (pdf)を提供している。
シングルコアで学習するよりは速いんだけど、モデルの平均を取る時のボトルネックが大きくて、学習データの量がそれほど多くない場合はあまり効果がなさそう (以下の実験では人工的に学習データを増やしている)。CPU数を増やすと、平均を計算するコストが大きくなるので単純に学習が速くなるわけではない 。平均を取るときも、二分木にして並列化をしているが O(N)がO(log N)になるくらいなので、CPUの数が少なければ平均の計算がとても速くなるわけでもない。 CPUは、1.7 GHz Intel Core i5を利用して、4コア利用時の学習速度とシングルコア利用時の学習速度をと比較してみる。
$wc -l news20.scale 15935 news20.scale $touch news20.scale.big $for i in 1 2 3 4 5; do cat news20.scale >> news20.scale.big; done $wc -l news20.scale.big 79675 news20.scale.big $time ./gonline train -a arow -m model -i 10 -t ./news20.t.scale -withoutshuffle -p 4 -s ipm ./news20.scale.big ./gonline train -a arow -m model -i 10 -t ./news20.t.scale -withoutshuffle -p 272.
最近はNLPなデモをgolangで実装して人に見せることが多くなってきた。 その時に、さっと使える機械学習ライブラリが欲しかったので、勉強がてら実装した。 実装が簡単で学習が速いオンライン学習手法を実装した。
gonline
パーセプトロンから、Confidence WeightedやAROWまでを提供している。各アルゴリズムは多値分類が可能なように拡張している。 news20 を使って評価はしたのだけど こちらの論文 と比べると精度が低めになっているので、もしかしたら 実装が怪しいかもしれない (パラメータチューニングをしていないだけの問題かもしれない)。 SCWはいつか実装する。
golangらしく？github releaseでバイナリの配布もしている (今回初めてやってみた)。 これを使えば、とりあえず何も考えずに分類器を学習させて予測することができる。
