はじめに

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さんらは、PITFやMichael 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

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

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

特徴量の組み合わせ

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

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

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

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

つまり、以下数式モデルの第３項目のウェイト $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)は１つであり、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次元ベクトルは１つしか存在しません。そのため、(商品=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の場合、モデル式の第３項(組み合わせ項)は以下のように展開されます。

  <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の場合、モデル式の第３項(組み合わせ項)は以下のように展開されます。

  <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研究所のひとつとして、どんなところか見に行きたい。

ML blog

IT 系のブログ

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