AROW を Ruby で実装してみた

Machine Learning Advent Calendar 2012 の 14 日目の記事になります。気まぐれでこのカレンダー登録してみたものの、この日に至るまでの数々の記事のガチな高レベルさに登録してしまったことをかなり後悔している @komiya_atsushi です。

この記事では、オンライン学習アルゴリズムの AROW を Ruby で実装した (& gem として公開した) という、どこにでもよくある話を書いています。主に機械学習に馴染みのない or 取り組み始めたばかりの（自分を含めた）エンジニア向けの記事となっています。

AROW とオンライン学習

まずはじめに、この記事で取り上げている　AROW とその前提となる知識について軽く説明していきます。

AROW (Adaptive Regularization of Weight Vectors) というのは、「オンライン学習」ができる「教師あり」の「クラス分類（二値分類）」アルゴリズムです。ではこの AROW を使って何ができるのか？ というと、例えば「海賊船からかっぱらってきた金貨のようなものを、事前に明らかになっている数十枚のコインの真贋の情報をもとに、その体積と重さから真贋を見分ける」ことができるようになります。

AROW は 2009 年に提案されたアルゴリズムであるものの、後からよりよい手法が幾つか提案されているので state of the art な手法ではないですが、言い換えれば安定して使える「枯れた技術」として使うには十分ではないでしょうか。

オンライン学習

「オンライン学習」については、今回の Advent Calendar でも記事を書かれている kisa12012 さんの オンライン学習による線形識別器 などがありますので、詳しく知りたい方はこちらをご参照いただくのがいいかと思います。ここではざっくりな概要の説明に留めるとして、クラス分類での説明を簡単（雑？）にすると「次々と与えられるデータの『特徴』とそのデータに対するクラスを示す『ラベル』（Yes / No みたいなもの）をもとに、それらをラベルに従って分類してくれるモデルを作る・更新する（＝学習する）」となるでしょう。

オンライン学習の特徴としては、以下に示すものがあります。

• 大量のデータをもとにモデルを作る必要があっても、全データを同時にすべて取り扱う必要がない（主記憶装置にやさしい）。
• モデルの更新に利用したデータを不要となれば破棄することもできる（二次記憶装置にやさしい）。
• １回１回のモデルの更新にかかる計算量が小さい（演算装置にやさしい）。

教師あり学習

次に「教師あり学習」について。教師あり学習というのは「正解の状態が明らかになっているデータ（訓練データ）をもとにモデルを作成する」学習になります。具体例でいうと今回取り上げている「クラス分類」がそれにあたります。対する用語として「教師なし学習」がありますが、こちらは「クラスタリング」などが例に挙げられます。

クラス分類

最後は「クラス分類」について。これは「データの『特徴』とそのデータに対するクラスを示す『ラベル』（Yes / No みたいなもの）をもとに、それらをラベルに従って分類してくれるモデルを作る・更新する。またラベルが未知のデータを予測して分類してくれる」お仕事と表現できるかと思います。

AROW の論文を読んでみる

続いて、AROW のアルゴリズムを実装する観点で、AROW の 論文 を読んでいきましょう。…とは言え、私自身、数式がそれなりにふんだんに使われた論文をすらすらと読めるほど数学リテラシーが高いわけではないので、重要な部分だけをピックアップして軽く説明します。

AROW を実装するに当たって一番重要なのは、p.4 のページ上にある Fig.1 です。（下図参照）

ここにある式を頑張って実装すればいいわけです。Σ が summation としてではなく共分散行列を表す変数として使われていることと、ベクトル x が列ベクトルであることに注意をすれば比較的容易に数式を読み解けると思います。

実際にこのコア部分を Ruby で実装すると、高々 50 行弱のコードになります。とってもシンプルですね！ ¹

なお既存の他言語での実装を見てみると、Σ の更新式が、論文中の (9) 式ではなく、(8) 式をもとにした実装がほとんどになっているようです。tsubosaka 先生の Java 実装 や C++ 実装の AROWPP などなど。なぜみんな (8) 式を利用しているのか理由が分からなかったのと、(9) 式の方がより効率よく計算できて精度も向上するようなので、今回は (9) 式での実装をしました。 ²

gem 'arow'

今回は上記実装をもとに gem 化したものを RubyGems.org で公開 しています。ソースコードは github.com/komiya-atsushi/arow にて公開しています。突貫工事的に gem 化したので、テストケースはないしマニュアルはないし README からして適当と粗が目立ちますが、カジュアルに使えるクラス分類器を自分自身が欲していたので、（お仕事が落ち着いたら）もうちょっと使いやすくできるようにメンテナンスをしていく予定です。

利用例がないのもアレなので、先に挙げた Code IQ の問題に対する適用例を示します… としたかったのですが、12/14 現在、まだ挑戦者受付中とのことらしいので念の為にしばらくはコード公開を控えておきます。また後日で。 ³

2012.12.21 追記：公開しました。

おわりに・感想

久々に数式たっぷりな論文を読んで、改めて己の数学力の低さを悔やみました。数学力を鍛え直したい…

この Machine Learning Advent Calendar の企画を開催してくださいました @naoya_t さん、ありがとうございました！

---

1 : 今回の実装では、μ (@means) と Σ (@covariances) は時間・空間計算量を減らすために行列の対角要素をとったもので表現しています。既存の各種実装をみても、いずれもこの対角要素を利用する方式をとっているようです。

2 : 理由を御存知の方がいらしたら是非、教えていただけると幸いです。

3 : Advent Calendar に登録した当初は 12/14 時点で受付終了している予定でしたが、終了が延長されてしまったため、このタイミングでは公開できず、と。ぐぬぬ…