オンライン凸最適化と線形識別モデル学習の最前線

岡野原です。

今日まで奈良女子大で行われていたIBIS2011で表題についての講演をしてきました。

内容は線形識別モデルの学習について（Perceptron, PA, CW, AROW, NHELDとNLP2010のtutorial + 最新のアップデート. 更新式が整理されています）、オンライン凸最適化のregret解析、sublinearなSVMの学習の話です。最近公開したjubatusの中の学習アルゴリズムの解説でもあります。
コスト関数が凸である場合のOnline Gradient Descentのregret解析の証明は美しかったので、普通はこういうのはプレゼンではやらないとおもうのですが紹介しました。

Sublinearの学習の話は今後いろいろ発展しそうです。各学習例に動的に重みをつけて優先的に学習する方法は直感的にはできそうだと昔考えてたのですが、こういう形できれいに定式化できるのだと感心しました。

IBISはそこそこ参加していますが、毎年新しい分野の問題が登場してきて面白いです。今年は最適化、関係データ、バイオ、物理、オンライン、コンピュータビジョンなどの話でした。どの分野でも使える道具はベイズであれLassoであれいろいろ活用されているようです。