ML blog

備忘録を兼ねた IT 系のブログでございます。

(draft)FFM (Field-aware Factorization Machines)を理解したい

はじめに

FFM(Field-aware Factorization Machines)は、機械学習分野で比較的新出のアルゴリズムです。CTR(click-through rate)やCVR(conversion rate)の予測コンペにおいて、FM(Factorization Machines)と共に良い成績を収めているようです。

誰が作ったの?

Yu-Chin Juan(阮毓欽)さん等の台湾大学の出身者・在籍者により提起されたもので、論文『Field-aware Factorization Machines for CTR Prediction』台湾大学サイトにあります。私がこのアルゴリズムについて知ったのは、apache sparkのオンライン講座のCTR予測の演習問題で、とあるkaggleコンペ(criteo)のデータを使っていたのですが、そのコンペでFFMの提起者であるYu-Chin JuanらがFFMを駆使して優勝していたのを見たからでした。ちなみにFFM作者Yu-Chin Juanさんは現在はコンペ主催者criteo社に在籍のようです。Yu-Chin Juanさんらは、もう一つのkaggleコンペ(avazu)でもFFMを使って優勝しています。

由来は?

Yu-Chin Juanさんらは、PITFMichael Jahrer氏の論文でのFieldの概念を取り入れる形で、FM(Factorization Machines)の改良版としてFFM(Field-aware Factorization Machines)を提起しました。次章では、まずFMの概略を説明してから、FFMの変更点について述べます。

必要な知識

協調フィルタリングでよく言及されるMF(Matrix Factorization)を理解していると良いようです。特にk次元に削減された表現の部分です。MFの理解には、人気のCouseraのMachine Learning講座もおすすめです。FMはMFをより汎用化したものと言えます。

FM(Factorization Machines)

FMは現在googleに在籍するSteffen Rendle氏により2010年に提起されたとのことですが、論文PDFを見ると表題に大阪大学の名前があります。論文でも強調されていますが、SVM等とは異なり、FMは非常にスパース(sparse)なデータ、つまりスカスカで値がほとんど入っていないデータからも学習が可能な点が長所です。

スパースなデータ、One-Hot-Encoding

ここで言うスパースなデータが生じる原因の一つとして、One-Hot-Encodingという手法で、カテゴリカルデータから新たな特徴量を生成する過程が挙げられます。

One-Hot-Encoding前:

東京
沖縄
北海道
東京

One-Hot-Encoding後:

県:東京 県:沖縄 県:北海道
1 0 0
0 1 0
0 0 1
1 0 0

上記例では、3県のみなので、3列が特徴量として生成されていますが、47都道府県であれば、47の特徴量が生まれます。また、各行を見たとき、47の特徴量のうち、1つのみが有効(非ゼロ)である点で、スパースなデータ、すまりスカスカなデータとなります。

例えば、上記spark講座の演習例では、One-Hot-Encoding後に特徴量が20万に増加し、値が入っている割合(Sparsity)が0.02%といった具合でした。更に本番のより大規模なコンペデータ(criteo)ではこの20万が3000万以上に激増します。(注:このため上記演習では、ハッシュ法で特徴量を十分の一に減らす処理も紹介しています)。

特徴量の組み合わせ

上記のようなスパースデータにて、特徴量の間に関連性がある場合を考えます。

性別:男 性別:女 製品:スカート ... クリックあり
1 0 1 ... 0
0 1 1 ... 1

上記は女性はスカートと関連が強いことをイメージしました。このような関連性は男児と少年ジャンプ、バレンタインデーとチョコレート、東アジア地域とお箸など様々なものが想定されます。

この関連性を抽出するため、特徴量間の組み合わせもモデリングします。この際、特徴量の両方が有効(非ゼロ)の場合のみが対象となります。しかしながら、スパースなデータで生ずる困難として、データ内の値がスカスカなため、学習に使える十分なデータが揃わなく、学習の精度が上がらない問題があります。

つまり、以下数式モデルの第3項目のウェイト w_{ij}の学習のための充分な x_i y_jの組み合わせが揃わないことになります。

 \displaystyle
\hat{y}(\mathbf{x}):=w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^nw_{ij}x_ix_j

論文PDFでは次のような例を挙げていました: 典型的な協調フィルタリングでは、トレーニングデータ内の組み合わせはせいぜい一度しか出現せず、テストデータ内の組み合わせは通常トレーニングデータでは全く現れない。例えば、Aliceさんが映画Titanicを見た組み合わせ(Alice, Titanic)は1つであり、Aliceさんが映画Star Trekを見た組み合わせ(Alice, Star Trek)は存在しない。

行列分解

この問題を解決するために、各特徴量に k 次元のベクトルを持たせておいて、そのベクトルの内積で組み合わせのウェイトを表現します。  <\mathbf{v}_i ,\mathbf{v}_j> の部分です。このあたりはMF(Matrix Factorization)を把握していると理解しやすそうです。

 \displaystyle
\hat{y}(\mathbf{x}):=w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_i ,\mathbf{v}_j>x_ix_j
 \displaystyle
<\mathbf{v}_i ,\mathbf{v}_j>:=\sum_{c=1}^kv_{i,c}\cdot v_{j,c}

 \mathbf{v}_i x_iの k 次元ベクトルで、  \mathbf{v}_j x_jの k 次元ベクトルです。

これで何が良いかというと、例えば <\mathbf{v}_i ,\mathbf{v}_j> <\mathbf{v}_i ,\mathbf{v}_l>とでは、お互いに \mathbf{v}_iを共有しているため、 \mathbf{v}_iをより多くのサンプルから学習することができます。もともとの w_{ij} w_{il}形式の場合、それぞれが全く独立なものとして取り扱われます。

AliceさんがStar Trekを見た組み合わせ(Alice, Star Trek)が存在しないケースでも、 \mathbf{v}_{alice} \mathbf{v}_{startrek}を活用できるため、相互作用を推定することができます。

FFM(Field-aware Factorization Machines)

次に、FMに対してFFMが拡張された箇所を説明します。

Field-aware

FMでの各特徴量に対するK次元ベクトルは1つしか存在しません。そのため、(商品=A, 日付=1/1)と(商品=A, 性別=男)の組み合わせでは、商品AのK次元ベクトルが、日付と性別という異なる対象に対して共有されます。FFMでは、商品、日付、性別などのくくりをFieldと捉え、Fieldごとに異なるk次元ベクトルを使用します。例えば、日付Fieldの組み合わせ対象に対する商品AのK次元ベクトル、性別Fieldの組み合わせ対象に対する商品AのK次元ベクトルといったように、各特徴量ごとに使い分けて学習します。

 \displaystyle
\hat{y}(\mathbf{x}):=w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_{if(j)} ,\mathbf{v}_{if(i)}>x_ix_j

jが属するフィールドとiが属するフィールドを表す f(j) f(i)が追加されており、組み合わされる対象のFieldごとにベクトルを使い分けていることが分かります。

展開例

ユーザ 映画 ジャンル 価格
太郎 影武者 コメディ、アクション 999
ユーザ:太郎 映画:影武者 ジャンル:コメディ ジャンル:アクション 価格
1 1 1 1 999
FMの場合

FMの場合、モデル式の第3項(組み合わせ項)は以下のように展開されます。

  <Vユーザ:太郎, V映画:影武者> · xユーザ:太郎 · x映画:影武者 
+ <Vユーザ:太郎, Vジャンル:コメディ> · xユーザ:太郎 · xジャンル:コメディ 
+ <Vユーザ:太郎, Vジャンル:アクション> · xユーザ:太郎 · xジャンル:アクション 
+ <Vユーザ:太郎, V価格> · xユーザ:太郎 · x価格

+ <V映画:影武者, Vジャンル:コメディ> · x映画:影武者 · xジャンル:コメディ 
+ <V映画:影武者, Vジャンル:アクション> · x映画:影武者 · xジャンル:アクション 
+ <V映画:影武者, V価格> · x映画:影武者 · x価格

+ <Vジャンル:コメディ, Vジャンル:アクションi> · xジャンル:コメディ · xジャンル:アクション 
+ <Vジャンル:コメディ, V価格> · xジャンル:コメディ · x価格

+ <Vジャンル:アクション, V価格> · xジャンル:アクション · x価格

  <Vユーザ:太郎, V映画:影武者> · 1 · 1 
+ <Vユーザ:太郎, Vジャンル:コメディ> · 1 · 1 
+ <Vユーザ:太郎, Vジャンル:アクション> · 1 · 1 
+ <Vユーザ:太郎, V価格> · 1 · 999

+ <V映画:影武者, Vジャンル:コメディ> · 1 · 1 
+ <V映画:影武者, Vジャンル:アクション> · 1 · 1 
+ <V映画:影武者, V価格> · 1 · 999

+ <Vジャンル:コメディ, Vジャンル:アクションi> · 1 · 1 
+ <Vジャンル:コメディ, V価格> · 1 · 999

+ <Vジャンル:アクション, V価格> · 1 · 999
FFMの場合

FFMの場合、モデル式の第3項(組み合わせ項)は以下のように展開されます。

  <Vユーザ:太郎|映画, V映画:影武者|ユーザ> · xユーザ:太郎 · x映画:影武者 
+ <Vユーザ:太郎|ジャンル, Vジャンル:コメディ|ユーザ> · xユーザ:太郎 · xジャンル:コメディ 
+ <Vユーザ:太郎|ジャンル, Vジャンル:アクション|ユーザ> · xユーザ:太郎 · xジャンル:アクション 
+ <Vユーザ:太郎|価格, V価格|ユーザ> · xユーザ:太郎 · x価格

+ <V映画:影武者|ジャンル, Vジャンル:コメディ|映画> · x映画:影武者 · xジャンル:コメディ 
+ <V映画:影武者|ジャンル, Vジャンル:アクション|映画> · x映画:影武者 · xジャンル:アクション 
+ <V映画:影武者|価格, V価格|映画> · x映画:影武者 · x価格

+ <Vジャンル:コメディ|ジャンル, Vジャンル:アクション|ジャンル> · xジャンル:コメディ · xジャンル:アクション 
+ <Vジャンル:コメディ|価格, V価格|ジャンル> · xジャンル:コメディ · x価格

+ <Vジャンル:アクション|価格, V価格|ジャンル> · xジャンル:アクション · x価格

  <Vユーザ:太郎,映画, V映画:影武者|ユーザ> · 1 · 1
+ <Vユーザ:太郎|ジャンル, Vジャンル:コメディ|ユーザ> · 1 · 1
+ <Vユーザ:太郎|ジャンル, Vジャンル:アクション|ユーザ> · 1 · 1
+ <Vユーザ:太郎|価格, V価格|ユーザ> · 1 · 999

+ <V映画:影武者|ジャンル, Vジャンル:コメディ|映画> · 1 · 1
+ <V映画:影武者|ジャンル, Vジャンル:アクション|映画> · 1 · 1
+ <V映画:影武者|価格, V価格|映画> · 1 · 999

+ <Vジャンル:コメディ|ジャンル, Vジャンル:アクション|ジャンル> · 1 · 1
+ <Vジャンル:コメディ|価格, V価格|ジャンル> · 1 · 999

+ <Vジャンル:アクション|価格, V価格|ジャンル> · 1 · 999

実装

FFMが広く使われるようになって欲しいということで、Yu-Chin Juanさんら作者によりオープンソース実装であるLIBFFMが公開されています。

論文PDFには、SG(Stochastic Gradient)の簡易アルゴリズムが掲載されています。実装面で気になった点について、幾つか記します:

  • AdaGradを学習率の調整に使用している。XGBoostの開発者Tianqi Chen(陈天奇)さんが"Interesting!"と詳細を質問していた。
  • 過学習を避けるためにEarly Stoppingを採用している。epoch(学習ループ)毎にValidationセットのロスを計算し、上昇した時点で中断する。
  • SGをパラレルで実行している。並列化で収束の振る舞いが異なる可能性があるものの、同様な収束が見られたとのこと。

おわりに

FFMの論文では、Chih-Jen Lin(林智仁、國立台灣大學資訊工程學系)さんの名前もありますが、この方がYu-Chin Juanさんらの指導教官だったようです。Chih-Jen LinさんはLIBSVMの作者として有名らしく、背後にいるラスボスにみたいな方でしょうか。ホームページにはさりげなく2017/2までmicrosoft訪問中とあり、研究室メンバーのページには、googleとかmicrosoftなどの名前が並んでいます。今度台北に行ったら、アジア最高のML研究所のひとつとして、どんなところか見に行きたい。