前言
由於筆者一直以來都對認為推薦系統是一個非常有趣且富有商業價值的應用，因此決定來了解推薦系統中的明星演算法，Factorization Machine。
Factorization Machine在稀疏資料(sparse data)進行特徵交叉(feature interaction)並抽取出潛在因子(latent factor)，可在線性時間複雜度來進行訓練，且方便規模化，是各大商推薦系統中的常用算法，以下筆者會介紹這篇論文的主要想法，並描述一些個人閱讀後的感想。
Factorization Machine 相關理論發展
Factorization Machine在2010年於IEEE發表，以特徵交叉(feature interaction)以及Matrix Factorization兩招，在稀疏資料下取得亮眼的結果，並推動了一系列理論發展:
從以上網路圖及表格來看，Factorization Machine延伸出不少變種，像是像是Field-Aware Factorization Machines，Gradient Boosting Factorization Machines，也可以看到相同問題有另一組分支則以Neural Network Embedding的方式來解同樣的問題，並且也發展出一些變種與結合，像是，Attentional Factorization Machines，DeepFM，以及xDeepFM。
問題描述
從一個電影推薦系統來了解實務上怎麼表達一個稀疏矩陣的推薦問題，我們有 ：
使用者 u∈U
在某個時間點 t∈R
給了電影(item) i∈I
評分 r∈{1,2,3,4,5}
例如
Users : U= {Alice(A), Bob(B), Charlie(C), …}
Items : I= {Titanic(Ti), Notting Hill(NH), Star Wars (SW), Star Trek(ST), …}
因此資料集合 S(u,i,t,r) 長下面這個樣子:
{(A, TI, 2010–1, 5), (A, NH, 2010–2, 3), (A, SW, 2010–4, 1), (B, SW, 2009–5, 4), (B, ST, 2009–8, 5), (C, TI, 2009–9, 1), (C, SW, 2009–12, 5)}
我們可以將Users，Items做OneHotEncoding，並加入兩項隱式反饋特徵
1. 對其他電影的評分
2. 上一部電影是否有評分並且將目標定義為對當前電影的評分，如此一來我們就有下圖 :
- 關於對其他電影的評分，論文中表示做了一個normalization，將使用者對所有其他電影的評分scaling到0~1之間，筆者相信這種normalization會隨著每個給定任務的特徵權重而有所不同。
- 大家可以看到說，上圖的表格由於對Users和Items都做了OneHot-Encoding，資料的表示法和S(u,i,t,r)稍有不同，但基本上是在表達同樣的意義，我們將上圖的資料表格的x, y收集起來，並以D表示:
從以上表格我們也可以先定義:
3. m(x) : 每一筆紀錄非0的feature component個數
4. <m>— 在資料集D中，平均來說每一筆紀錄有多少個非0的feature component
Factorization Machine 專門處理這種超級稀疏的特徵矩陣X，並且可以適用在以下監督式學習任務(回歸、分類、排序)
如果任務是排序的話，則需要在對D做一些配對，來取得訓練資料。
並且有了以上的輸入資料，我們希望丟到一個模型，學習到一組權重，可以用來預測使用者 u 在其他沒選過的電影 i 上的評分會是多少，並排序來進行推薦。
Factorization Machine Model
Factorization Machine Model的主要想法是在以上的資料格式，把所有特徵做交叉(interaction)，接著取潛在因子(latent factor)，直接對此優化，以下我們先描述前半段特徵交叉的部分 ：
Feature component : xi
where i∈{1,2,…n}
- 其中w0是global bias
- wi是一次項的特徵權重
- wˆi,j是交叉項的特徵權重
- wˆi,j有對稱性，wˆi,j和wˆj,i是相同的，也就是我們只需要一半即可
眼尖的筆者應該會注意到，原先把Users和Items做OneHot-Encoding，就已經使得n超大了，做交差項不是n²嗎XD，特徵這麼多訓練得起來？
這也就是Factorization Machine的主要思想之一，特徵太多訓練不起來，那我來抽取latent factor，把他降維!
將所有的wˆi,j收集起來，我們有Interaction Matrix W，論文中巧妙的利用了W矩陣有著positive define的性質，將其做矩陣分解
因此wˆi,j可以改寫 ：
稀疏資料下的參數估計
定義好了模型，論文作者也稍微做了數學推導，估算Factorization Machine的訓練時間複雜度，主要透過了兩個trick將時間複雜度從O(kn²)降到了O(k<m>)
The math trick
上面共有5條式子，看起來有點可怕，實際推一下其實也還好，筆者這裡簡單說明每一條式子做了什麼事，以及該式子對應到的時間複雜度 :
- 原式，v向量內積的部分需要經過k個factor，時間複雜度O(kn²)
- 大家可以注意到左下角的Σ下標改變了(從j=i+1變成j=1)，這是在說明原本的interaction matrix W可以表示為整個Matrix扣掉對角項(也就是xixi)，再除以2(因為interaction matrix)是對稱矩陣，時間複雜度O(kn²)
- 沒幹嘛，把v向量的內積拆開，也就是大家高中數學和大學微積分的展開XD(展、哪一次不展!?)，時間複雜度O(kn²)
- 同樣地沒幹嘛，都有對latent factor 加總的∑，就搬出來，時間複雜度O(kn²)
- 在數學上沒什麼的一步，但是對計算來說產生重要意義，前項的 :
基本上完全是同一件事情，沒必要算兩次，算一次直接平方就好，因此我們得到了第5式
然而第5步這個動作在計算上直接少掉O(n)，原來有些內容重複算了，透過數學整理一下，時間複雜度在這個階段將為O(kn)
The computational trick
另一項trick則是針對稀疏資料的特別設計，主要理念是這樣的 ：
大部分的feature component基本上都是0，我幹嘛底層的for loop算得這麼累呢? 你直接告訴我哪裡不是0，我index取出來算一算就好啦!
所以其實每一筆資料不需要O(kn)，只需要O(km(x))，以整個資料集D來說，我們只需要O(k<m>)
而透過以上兩個trick，原本的計算複雜度O(kn²)(大量資料下會算超久)被論文作者變成了O(k<m>)，越稀疏，latent factor越少，訓練越快，線性時間複雜度!
模型比較
若有上過軒田老師的機器學習技法的讀者，可能會非常好奇，Matrix Factorization以及SVM做不好這件事嗎? Factorizaion Machine 憑什麼做得更好呢?
以下筆者也整理的論文作者的看法
Matrix Factorization
Matrix Factorization通常專注在將兩個類別變數所形成的矩陣拆解，例如Users U以及Items I
然而看圖2，Factorization Machine的特徵向量x基本上是可以無限擴張的，你爽加入幾種特徵，全部one hot，調整相對數值範圍(normalization)，都是可以的，並且在圖2中，若只看藍色(users)，橘色(movies)、以及目標(y)，就會發現交叉項取latent factor根本就是Matrix Factorization！
也就是說Matrix Factorization是Factorization Machine的一個子集。
Matrix Factorization可以解，但是Factorization Machine可以繼續加其他特徵，得到更好的效果。
SVM
大家可能都熟悉SVM可以做2階特徵交叉，並透過kernel function在dual space進行優化，稍作整理，能夠整理出與Factorization Machine相似的形式如下：
其中w²i,j表示的不是平方，而是交叉項矩陣W²中的(i,j)元素
SVM 訓練不起來的原因
筆者推測論文作者一開始也是拿SVM去訓練，但是訓練不起以來，才把腦筋動到交叉項的Factorization，論文作者認為SVM訓練不起來的原因是這樣的：
原因1 — FM中的二階權重互相相關，比起SVM容易訓練
SVM : 參數w²i,j是互相獨立的，因為xi,xj互相獨立
FM : 參數wˆi,j是互相相關的，因為交叉項矩陣W會被分解為VVT
也就是說，如果有4個參數wa,wb,wc,wd.
在SVM中，他們是獨立被訓練的，但在FM中，他們有有可能對應到同樣的v，所以縱使有n²個pair，但最後我只要訓練出k個factor，同樣latent factor的資料較多
原因2 — 由於SVM的二階權重互相獨立的特性，測試集和訓練集在稀疏資料下的分佈略有不同
這段筆者自己也沒有看得很懂，大致上應該是說二階權重互相獨立的特性對於support vector很難產生作用，若有讀者了解這一段的，拜託告訴一下筆者QQ。
小結來說，交叉項 + 稀疏特性使得SVM難以發揮，而將交叉項取latent factor的做法恰如其分地解決了問題，而且訓練也快(Linear Time Complexity)
Factorization Machine 可能隱含的意義
以下這段是筆者對於Factorization Machine的矩陣分解部分做的詮釋，如果有不恰當的地方，還請協助筆者修正，感謝!
Factorization Machine 是否具有物理意義呢? 在數學式中探索實務上可能意義，一直以來都是一件非常迷人的事情，而在Matrix Factorization和Factorization Machine的比較中我們也可以嗅出一些端倪
Factorization Machine對交叉項進行矩陣分解 ：
而以圖2舉例，現在假設W中僅含有，Users 以及 Items的One-Hot Encoding特徵，那麼交叉項的特徵就會是(使用者 — 電影名稱)來進行interaction，那麼在這個情況下抽取latent factor的意義也就是找到k個factor來表達W，這時候的Vn×k具有以下意義
n個User-Item interaction可以被k種風格(latent factor)表示
例如
喜歡浪漫電影的A群人屬於第1種風格，
喜歡英雄電影的B群人屬於第2種風格，
…. 一直到k種風格
此時Factorization Machine和Matrix Factorization的物理意義是一致的
然而我們在加入一組特徵 上一部評分的電影(圖一的棕色區塊) 呢？
那我們就有 (User-Item-LastItem)的三種交互關係，這時候的Vn×k具有以下意義:
n個User-Item-LastItem interaction可以被k種風格(latent factor)表示
例如
一直喜歡浪漫電影的A群人屬於第1種風格，
上個時間點喜歡英雄電影，接下來喜歡浪漫電影的B群人屬於第2種風格，
一直喜歡英雄電影的C群人屬於第3種風格，
…. 一直到k種風格
讀者們可以想像的是，有些交叉有可能無法被解釋出意義，抑或是這樣的交叉都只能全部一起表示嗎? 能不能換一種方法來歸納這些風格？
其中後者也就是Field-Awared Factorization Machine所進行的分析，將latent factor分組成多種field，但這又是另外一個故事了!
然而Factorization Machine事實上還有一次項及零次項
是否也代表一定意義呢？ 有的
- w0是一個和所有xi都無關的權重，可以理解為所有紀錄共享的平均喜好度
- wixi除了可以讓我們很輕易地看出是Linear Regression之外，也可以思考為User-Based Recommendation(圖二的藍色部分)以及Item-Based Recommendation(圖二的橘色部分)，甚至可以讓你加入任意特徵(圖二的黃、綠、褐色部分)
以上這段算是筆者自己的腦補，若讀者們發現有誤或是有更好的表示方法，歡迎一起貢獻出來XD
小結
本篇文章中筆者帶著大家了解了一遍Factorization Machine，我們再一起來複習一下Factorization Machine這篇論文所提到的幾個重點以及Factorization Machine的特色：
- 分析了SVM 二階交叉特徵為什麼訓練不起來，而對交叉項做Factorization使得latent factor更好訓練，並以實驗結果說明。
- 透過幾行數學式，抓出不需要算兩次的地方，成功將交叉項的計算時間複雜度從O(kn²)降至O(kn)，透過只找非零元素而不用對全部的feature component遍歷，再將交叉項的時間複雜度從O(kn)降到O(k<m>)，線性時間複雜度就可以訓練到有交叉項的模型，工業應用價值高。
- 可視為是一種Matrix Factorization的擴展，Matrix Factorization也能夠解此問題，但Factorization Machine 可以解得更好，更有彈性。
- 核心算法容易實作，在工業界規模化及普遍化具有優勢。
以上就是筆者在閱讀Factorization Machine所思考過的筆記，下一篇
初探Factorization Machine(II)
則會實際跑一些程式碼來感受一下FM的威力，希望以上文章有幫助到各位讀者一同揭開Facotrization Machine的神秘面紗，也希望讀者們有所啟發!
寫在最後
如果讀者們也覺得這篇文章不錯，請不吝嗇的給予筆者鼓勵，畢竟整理這些內容也挺花時間的嗚嗚，如果想持續看到筆者撰寫Machine Learning相關Project，論文筆記，甚至業界的Case Study，也且按下Follow。
若你有任何問題/建議，歡迎直接在下面留言，或是寄信到我的信箱yltsai0609@gmail.com ，我收到信之後會盡快回復給你!
