本文介紹FM（Factorization Machines）二分類器使用FTRL優化的算法原理，以及如何結合softmax改造成一個多分類器。我自己實現了該算法工具，取名為alphaFM，已經開源。
前言最近公司內部舉辦了一屆數據挖掘大賽，題目是根據用戶的一些屬性和行為數據來預測性別和年齡區間，屬於一個二分類問題（性別預測男女）和一個多分類問題（年齡分為7個區間），評判標準為logloss。共有五六十支隊伍提交，我們組的三名小夥伴最終取得第三名的好成績，跟前兩名只有千分之一二的差距。
賽後總結，發現前6名全部使用了DNN模型，而我們團隊比較特別的是，不只使用了DNN，還有FM，最終方案是六七個DNN模型和一個FM模型的ensembling。
其實比賽剛開始，他們使用的是XGBoost，因為XGBoost的名頭實在太響。但這次比賽的數據量規模較大，訓練樣本數達到千萬，XGBoost跑起來異常的慢，一個模型要跑一兩天。於是我把幾個月前寫的FM工具給他們用，效果非常好，二分類只需十幾分鐘，多分類也就半個多小時，logloss和XGBoost基本持平，甚至更低。最終他們拋棄了XGBoost，使用FM在快速驗證特徵和模型融合方面都起到了很好的作用。此外，我們組另外兩名實習生僅使用此FM工具就取得了第七名的成績。
最初寫此FM代碼時正值alphaGo完虐人類，因此隨手給這個工具起了個名字叫alphaFM，今天我就來分享一下這個工具是如何實現的。
alphaFM介紹 代碼地址在：
https://github.com/CastellanZhang/alphaFM
https://github.com/CastellanZhang/alphaFM_softmax
alphaFM是Factorization Machines的一個單機多線程版本實現，用於解決二分類問題，比如CTR預估，優化算法採用了FTRL。我其實把sgd和adagrad的方法也實現了，但最終發現還是FTRL的效果最好。
實現alphaFM的初衷是解決大規模數據的FM訓練，在我們真實的業務數據中，訓練樣本數常常是千萬到億級別，特徵維度是百萬到千萬級別甚至上億，這樣規模的數據完全加載到內存訓練已經不太現實，甚至下載到本地硬碟都很困難，一般都是經過spark生成樣本直接存儲在hdfs上。
alphaFM用於解決這樣的問題特別適合，一邊從hdfs下載，一邊計算，一個典型的使用方法是這樣：
訓練：10個線程計算，factorization的維度是8，最後得到模型文件fm_model.txt
hadoop fs -cat train_data_hdfs_path | ./fm_train -core 10 -dim 1,1,8 -m fm_model.txt
測試：10個線程計算，factorization的維度是8，加載模型文件fm_model.txt，最後輸出預測結果文件fm_pre.txt
hadoop fs -cat test_data_hdfs_path | ./fm_predict -core 10 -dim 8 -m fm_model.txt -out fm_pre.txt
當然，如果樣本文件不大，也可以先下載到本地，然後再運行alphaFM。
由於採用了FTRL，調好參數後，訓練樣本只需過一遍即可收斂，無需多次迭代，因此alphaFM讀取訓練樣本採用了管道的方式，這樣的好處除了節省內存，還可以通過管道對輸入數據做各種中間過程的轉換，比如採樣、格式變換等，無需重新生成訓練樣本，方便靈活做實驗。
alphaFM還支持加載上次的模型，繼續在新數據上訓練，理論上可以一直這樣增量式進行下去。
FTRL的好處之一是可以得到稀疏解，在LR上非常有效，但對於FM，模型參數v是個向量，對於每一個特徵，必須w為0且v的每一維都為0才算稀疏解，但這通常很難滿足，所以加了一個force_v_sparse的參數，在訓練過程中，每當w變成0時，就強制將對應的v變成0向量。這樣就可以得到很好的稀疏效果，且在我的實驗中發現最終對test樣本的logloss沒有什麼影響。
當將dim參數設置為1,1,0時，alphaFM就退化成標準的LR的FTRL訓練工具。不禁想起我們最早的LR的FTRL代碼還是勇保同學寫的，我現在的代碼基本上還是沿用了當初的多線程思路，感慨一下。
alphaFM能夠處理的特徵維度取決於內存大小，訓練樣本基本不佔內存，理論上可以處理任意多的數量。後續可以考慮基於ps框架把alphaFM改造成分布式版本，這樣就可以支持更大的特徵維度。
alphaFM_softmax是alphaFM的多分類版本。兩個工具的具體使用方法和參數說明見代碼的readme，這裡不再詳述。
接下來請各位打起精神，我們來推一推公式。詩云，萬丈高樓平地起，牛不牛逼靠地基。公式就是算法工具的地基，公式整明白了，像我們這種」精通」C++的（誰簡歷裡不是呢:-P），實現就是分分鐘的事（裝B中，勿擾：-）。
二分類問題對於二分類，最常見的模型是LR，搭配FTRL優化算法。LR的輸出會用到sigmoid函數，定義為：
LR預測輸入x是正樣本的概率：
可以看到，σ函數的參數部分是一個線性函數，這也就是LR被稱作線性模型的原因，模型參數只有一個w向量，相對簡單。如果我們把這部分弄複雜呢？比如這樣：
其中，
這其實就是一個2階FM，模型參數
如果直接將做輸出，採用平方損失函數便可解決回歸問題。而對於二分類問題，外面套一個sigmoid函數即可：
對於y∈{−1,1}，可統一成形式：
模型參數估計採用最大似然的方法，對於訓練數據S，最優化問題為：
即樣本(x,y) 的損失函數為：
此損失函數對求偏導會得到一個優雅簡單的形式：
再配合上對模型參數的偏導：
便可得到損失函數對所有模型參數的偏導，即：
此時，我們能夠很自然的想到用SGD的方法來求解模型參數，但我這裡採用了更加高效的FTRL優化算法。
讓我們來簡單回顧一下FTRL，Google在2013年放出這個優化方法，迅速火遍大江南北，原始論文裡只是用來解決LR問題，論文截圖如下：
但其實FTRL是一個online learning的框架，能解決的問題絕不僅僅是LR，已經成了一個通用的優化算子，比如TensorFlow的optimizer中都包含了FTRL。我們只要把截圖中的偽代碼修改，p_t的計算改為，對於每一輪的特徵向量x的每一維非0特徵x_i，都要相應的更新模型參數
更新公式不變和截圖一致，梯度g的計算即為損失函數對每個參數的偏導，前面已經給出。
σ,z,n的更新公式不變。偽代碼如下：
多分類問題
Softmax模型是LR在多分類上的推廣，大致就是如果有c個類別，則模型參數為c個向量：
其中任意。
樣本x屬於類別i的概率：
FM解決多分類的方法同樣是將線性部分替換成複雜的，不過不再是一個，而是每一類別對應一個，共c個：
樣本x屬於類別i的概率也變成：
模型參數一共c組，
，
其中類別i對應一組參數
我們定義一個示性函數1{⋅}，大括號中表達式為真則值為1，表達式為假則值為0。這樣就可以寫出最優化問題：
每條樣本(x,y)的損失函數：
梯度：
而
所以有
即求 對中所有參數
的偏導，這在二分類中我們已經給出。
最後，仍然是套用FTRL的框架，只是每條樣本更新的參數更多，不再細說，詳見代碼。
終於寫完了，不得不吐槽一下微信，不支持markdown數學公式簡直要人老命，只能大半夜把公式一個個截圖下來，和文字拼一塊醜到爆。對審美有要求的還是直接看我的博客吧：
http://castellanzhang.github.io/2016/10/16/fm_ftrl_softmax/
或者點擊最下面的閱讀原文。
張衛，8年多碼農生涯，先後在騰訊、搜狗混過些時日，目前在小米負責廣告算法。無甚特別，唯好數學物理，正所謂推公式無敵手，推妹子無得手的中二漢子。