什麼是稀疏資料?試想你要製作一個推薦系統,基於這個推薦系統你找了很多關於使用者的Feature ,還有內容相關的Feature 。而這些Feature都是類別變數,而且每個變數動輒有數十個不同的可能值。這時候你一定會想要使用one-hot encoding的方式來將這些類別變數轉換;然而這樣一轉換之後會發現,Feature中有一堆欄位全部都是0。這種很多欄位都是0的情況就稱之為稀疏。
這篇文章讀完《Factorization Machines》後的重點節錄加上一些個人的詮釋,若有理解不對的地方還請不吝整正。Factorization Machine 是一個用來學習Feature之間交互影響並解決資料稀疏性導致Feature交錯向難以估計的問題。這樣講肯定聽不懂是什麼意思,所以話不多說我們就進入論文的正題吧。
Prediction Under Sparsity
假設你正在做一個電影的推薦系統,你的feature如圖所示,你會發現這樣的Feature中充斥著0。我們不仿思考看看,如果使用SVM或者一般的線性模型我們要如何解這個問題,首先我們若想考慮變數的交錯向就一定會把模型設定成二階有交錯向的形式,然而在訓練模型的時候就會發現,由於Feature中存在大量的0導致,要讓交錯項位置同時不為0實在十分困難,而更新模型參數時的微分量也就經常性的沒有值,由於這個緣故,交錯項的參數會難以訓練到。
通常我們在表示變數的交錯關係時會用到W(n*n)對稱矩陣來表達變數之間的交錯關係。然而在Factorization Machines的模型設定中,變數的交互影響項被一個壓縮過的矩陣V(n*k)矩陣來生成。
其中這個V*V^T=W(因為W是對稱正定矩陣,因此一定可以做正交對角化),首先我們可以觀察到V的維度是n*k,其中n代表的是原本Feature的個數,k則是一個自己選取的量,用來表示分解的維度(或是隱藏的維度),因此可以透過分解矩陣的過程打破參數之間的獨立性,因此就算在Sparse Input的狀況下也能訓練到交錯影響項(詳見論文第三章第三小節)。
Computation (Linear runtime)
假如不使用FM直接使用一般線性模型的交錯項學習的話,因為在交錯項相乘的地方會有兩個與n有關的Sigma加總,因此在預測或者訓練的時候會是Quardratic Runtime,然而在FM的模型設定下,交錯項可以改寫成如下形式:
在這邊我們可以看到,等式的最後大層的Sigma與設定的壓縮維度k有關,內層的Sigma則與Feature個數n相關,因此總體的時間複雜度就是O(kn)因此會是Linear runtime。
其實FM Model還有許多的優點,但是礙於Medium中要使用數學式子實在不容易,因此難以直接寫明。以下將論文中列出的優點做整理:
- 就算在Input Data 有很高的Sparsity下 FM還是可以估計出變數的交錯影響
- 訓練、預測的時間都是O(nk),時間複雜度較低
因此在使用該模型應該注意到, FM Model的強項在於處理稀疏且有關聯性的Feature。