Hatena::ブログ(Diary)

EchizenBlog-Zwei このページをアンテナに追加 RSSフィード

2011-01-20

機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう!〜

最近の論文

The Learning Behind Gmail Priority Inbox D.Aberdeen, O.Pacovsky & A.Slater

というのがある。これはGmailの優先トレイで使っている機械学習アルゴリズムについて解説したもの。というと難しそうな印象があるが、この論文で紹介されているPassive-Aggressiveという手法は実装がとても簡単。なので今回はこれについて解説するよ。

参考資料:


前回の復習

さて前回の機械学習超入門で線形識別器の話をした。簡単に復習すると学習モデルの単語の重みと、識別したいデータの重みを対応する素性(単語)同士で掛けたものの合計がスコアだよ。という話だった。以降、この考えを基本に考えるので単純な記号で表す。具体的には

学習モデル: w
データ    : x
スコア    : wx

とする。

Passive-Aggressiveについて

Passive-Aggressiveにはいくつかの種類がある。Gmailの優先トレイ学習で用いているのはPA-II regressionというもの。これは線形識別ではなく線形回帰とよばれる学習をする。といっても難しいものではない。どういうものかというと、前回は学習データに○(非スパム)か×(スパム)かという情報がついていた。今回はスパム/非スパムではなく、メールのスコアそのものを学習する。つまり新しいデータ(メール)に対して、このメールはXXX点ですね、というようにスコアを教えてくれる(線形識別でもスコアを返すけど、これは大きければ良いというものであって値自体には意味がなかった)。このように学習時に与えた数値自体を学習させるものを回帰(regression)という。Gmailの優先トレイ学習では回帰による学習をして新しいメールにスコア付けをして、あるスコア以上のメールを優先トレイに入れるよ、というしくみ。

オンライン学習

Passive-Aggressiveはオンライン学習をする。オンライン学習とは何かというと、学習データがひとつずつ与えられて、学習データが一つ来るごとに学習モデルの重みがちょっとずつ変わっていく学習方法。前回の線形識別の例で言うと、データが一つ来るごとにそのデータが持っている単語の重みが学習モデルの重みに足されていく、というイメージ。これを整理すると

w = f(x, w')

という感じ。これは何かと言うと、データxと現在の学習モデルの重みw'から次の重みを計算している。これを全データについて繰り返す。つまり

foreach (x in X) {
  w = f(x, w')
}

ということをやる。このループが終わったときのwがPassive-Aggressiveによって学習された重み。これがオンライン学習のイメージ。

重みの更新式

結論から言ってしまうと

f(x, w') = w' + sign(wx - y) * max(0, |wx - y| - ε) * x / (|x|^2 - 1/2C)

というのが上で述べたデータxとモデルの重みw'があるときに、次の重みwを求める更新式。幾つか新しい記号があるので解説。

y : データxの正解スコア
ε: 正解スコアとPA-IIが返すスコアの差の下限
C : パラメータ

ちょっと補足。yは事前に学習データと一緒に用意してあげる人手で与えた正解スコア。εとCはユーザが自由に決められる値(パラメータ)。PA-IIは学習データに対する正解スコアPA-IIが返すスコアの差がε以下になるように学習してくれる。Cはどれくらい分類の失敗を許すかというパラメータで大きいほど間違いにおおらかになる。

更新式の意味

上で説明した更新式は突然出てきたので何をやっているのか、と混乱したかもしれない。のでちょっと解説。PA-IIでは更新の前後の重みが最小になるように学習する。それだけ。

何もしないをしよう

とはくまのプーさんの名言であるが、上で説明した「更新の前後の重みが最小になる」というのは単純に考えると「何もしない」とき。ってこれじゃ学習とか意味無いじゃん、となるのだが、ここで制約条件というのが登場する。制約条件とはなにかというと先ほど少し述べた「学習データに対する正解スコアPA-IIが返すスコアの差がε以下になるように学習してくれる」というやつ。この制約をアグレッシブ(積極的)に満たしつつ、できるだけ重みを変えない(パッシブ、受身)ようにするのがPassive-Aggressive(II regression)というわけ。

SVMとのアヤシイ☆関係

重みを変えないように、というのはわかった。でもなんで重みを変えないほうがいいの?という疑問があると思う。これはSVMとも密接に関係している。SVMでは機械学習によって

f(w) = 1/|w|^2

という関数を最大化する。この関数マージンと呼ばれていて、マージンを最大化することで新しいデータに対する分類の失敗が少なくなるよ、というのが言われている(と私もあまり詳しくないのでお茶を濁した。詳しく知りたい人は学習理論を勉強しよう)。

で。マージンを最大化するにはどうすればいいかというと分母のwを小さくしてあげれば良い。なのでwを全部重みがゼロの状態で学習をはじめて、できるだけ重みを動かさないようにすればwが小さいままで制約条件(スコアの誤差がε以下)を満たすことができるね。というのがPA-IIの主な考え方。

最後に

今回は数学が苦手な方に配慮して数式の導出法は思い切りカットした。詳しく知りたい方は是非論文を読もう!後で読む☆とか言っちゃだめだよ!

sleepy_yoshisleepy_yoshi 2011/01/21 04:00 PAの匂いがしたのでやってきました.


> なのでwを全部重みがゼロの状態で学習をはじめて、できるだけ重みを動
> かさないようにすればwが小さいままで制約条件(スコアの誤差がε以下)を
> 満たすことができるね。
先日のTwitter上での (PAがマージン最大化学習をしているという)レスの答えがまさにこれだと思います.今晩ちょうどこのことについて考えていて,この記事がupされたので軽く運命を感じました (*´Д`*)


既にご存じかもしれませんが,PAの資料は以下の元論文の解説資料がかなりわかりやすかったです.

MIRA (Margin Infused Relaxed Algorithm)
http://nlp.kuee.kyoto-u.ac.jp/~nakazawa/pubdb/other/MIRA.pdf

echizen_tmechizen_tm 2011/01/23 21:35 コメントありがとうございます。
風邪引いてブログ放置してました。。。

PAに関しては本文でも書いたように
マージンが大きくなるように学習していると思うので
large margin classifierだとは思うんですけれど
全学習事例がhinge損失ゼロになるようなマージンのうち
最大のものを必ず得られるのか?
と言われると、そうはなっていないような気もしています。
(= max margin classifierにはなっていないのではないか、と)

MIRAの資料は気になっていて
手元に印刷してあるんですがまだちゃんと読んでないです。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証