はじめに
こんにちは。皆さんD言語使っていますか？
今回は liblinear のような教師あり線形分類器のライブラリ, libarowを作ったので紹介します。
特長
- 収束が早い
- 精度が良い(liblinearより良い)
- パラメータが少ない（1個）
- そのパラメータもデフォルトの値を使っておけば大抵OK
- オンライン学習（すべてのデータを一度に読む必要がなく、省メモリ）
アルゴリズム
以下の更新式にしたがって、各特徴の分散を小さくしつつ、与えられた教師データを正しく分類できるようにし、かつなるべく今までの分布に近い形で更新していきます。
(\mathbf{\mu}_{t+1}, \Sigma_{t+1}) =
arg~min_{\mathbf{\mu}, \Sigma}
D_{KL} (\rm N(\mathbf{\mu}, \Sigma) || \rm N(\mathbf{\mu}, \Sigma))
+ \frac{1}{2 \gamma} L(\mathbf{x}, y, \mu)
+ \frac{1}{2 \gamma} L(\mathbf{x}^T \Sigma \mathbf{x})
詳しくはここを参照してください。オンライン線形分類器とSCW
パフォーマンス
news20.binaryの約2万のデータのうち、15000件を教師データ、残りをテストデータにして、正答率 (accuracy) = 97.2% くらい。
これはデフォルトでの結果なので、AROWに渡すハイパーパラメータを変えるともっと良くなると思います。
あと1回だけデータを読ませるのではなく何周かさせるとわずかですが良くなるので、ちゃんとチューニングすれば98%くらいまではいけるんじゃないでしょうか。
実行時間はデータの読み込み時間を除くと1秒未満です。SVMと比べるとさすがに早いですね。
ただ、特徴ベクトルを連想配列で扱っているので、ベクトルが高次元かつ密だと遅いかもしれません。
おわりに
パラメータが少なく、またパラメータ変化に敏感でもなく、オンライン学習が可能で精度が良い、となると利用できるシーンは多いかと思います。上記は自然言語処理系のタスクでしたが、特徴量がもっと dense な画像処理にもこの AROW を使って良い感じの成果が得られたりしているので、もっと流行ってもいいアルゴリズムなのではないでしょうか。
今後の予定としては以下の様なものを考えています。
- 生テキストを食わせてN-gramや形態素解析を通して素性を作る機能
- 画像を食わせられるようにする
- 多値分類
- 並列化
- 正則化オプション