読者です 読者をやめる 読者になる 読者になる

データ分析エンジニアのブログ

日常のことからプログラミングや機械学習まで@六本木

オンライン学習とPassiveAggressiveアルゴリズム

アルゴリズム データ分析

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


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

オンライン学習

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


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

  • 訓練時にデータ全体をメモリに載せる必要がない
  • 1つの訓練データからの学習だけなら高速
  • ロバストでノイズに強い

PAアルゴリズム

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


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

Passive

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

Aggressive

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


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


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

参考サイト

機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう!〜 - EchizenBlog-Zwei
・数式は完全に省かれていますが、とてもわかりやすく書かれています。


テキストマイニングで始める実践Hadoop活用(最終回):Hadoopによるテキストマイニングの精度を上げる2つのアルゴリズム (1/3) - @IT
・こちらは数式もありますが、丁寧で簡単に説明されています。


オンライン学習による線形識別器 - kisa12012の日記
・数式による説明が詳しいです。