オンライン学習とPassiveAggressiveアルゴリズム - データ分析エンジニアのブログ

今回はオンライン学習と呼ばれる機械学習の学習方法についてです。

PassiveAggressiveというオンライン学習のアルゴリズム（以下PA アルゴリズム）はGmailの優先トレイにも使われているのですが、2006年に発表された比較的新しい手法だからでしょうか、、ネットで検索しても情報がそんなにありませんでした。

まずはオンライン学習（逐次学習）について説明します。
オンライン学習とは訓練データを1つずつ読み込み、モデルを更新する学習方法です。

特徴としては以下のようなことが挙げられます。

そして本題のPA アルゴリズムですが、これはオンライン線形分類器のアルゴリズムの1種で、オンライン学習という名のごとく、訓練データが1つ与えられるごとに重みを更新していきます。

その際、常に重みを更新するのではなく、下記の通りAggressiveの時のみ、重みを更新します。

訓練事例を正しく分類できた → 重みは更新しない

訓練事例を正しく分類できなかった → 重みを更新

f:id:ishitsukajun:20141130223341p:plain:w400
こちらが重みの更新式です。

Lは損失関数なので、制約条件は新しく与えた訓練データを正しく分類することです。
その制約を満たしつつ、元の重みベクトルW(old)に最も近いWを新しい重みベクトルW(new)とするというのがこの数式の意味です。