FM模型在LTR類問題中的應用

04-20

由於工作原因，去年有段時間鼓搗了陣FM在排序類問題的應用。排序和分類、回歸一樣是機器學習中的基本任務。排序問題在工業界應用場景也非常常見，比如電商網站推薦列表中商品的排序，搜索引擎中網頁的排序。雖然不同的業務中排序問題涉及到的實體不同，問題的本質其實都很類似。排序系統一般可分為兩個階段，召回(recall)和排序(rank)，有時候也稱作粗排和細排。16年Recsys上谷歌發表了篇介紹youtube的視頻推薦的文章，裡面使用到了深度學習的方法，但深度學習在工業界中落地稍微困難一些，所以本文想介紹下傳統機器學習模型在排序問題中的應用。

整體的思路其實和RankSVM類似。SVM模型在海量數據場景只能使用線性核，模型表達能力有限，所以我們選擇使用FM模型。FM模型引入了高階特徵交叉，而且在稀疏場景下模型參數學習更為準確。FM模型由於複雜度原因一般只用二階，對應的計算公式如下：

$ilde{y}(x)=w_{0}+sum_{i=1}^{n}{w_ix_i}+sum_{i=1}^{n}{sum_{j=i+1}^{n}{<v_i,v_j>x_ix_j}}$

上式中的最後一項可以化簡成如下式子使得計算複雜度從 $o(kn^{2})$ 降到 $o(kn)$ ，其中k為隱向量長度， $n$ 為特徵數目。值的注意的是，真實業務場景中往往是海量特徵，一般只有幾十或百量級的特徵非空，此時計算特徵複雜度時要考慮是非空特徵數目，而不再是特徵數目。由該式子可以看出，模型參數主要是偏置 $w_0$ ，一次項係數 $w_i$ 和隱向量係數 $v_{if}$ ，總共參數規模為1+n+kn個。後續計算梯度的時候是直接基於該式子。

$ilde{y}(x)=w_0+sum_{i=0}^{n}{w_ix_i}+frac{1}{2}sum_{f=1}^{k}{((sum_{i=1}^{n}{v_{i,f}x_i})^{2}}-sum_{i=1}^{n}{{v_{i,f}^2{x_i}^2})}$

我們知道，pairwise類方法要比pointwise類方法（直接看做分類或者回歸）要更適合排序類場景。pairwise loss里構造樣本時我們同時考慮兩個item比如 $x^i$ 和 $x^j$ 。這兩個item是有順序的，比如用戶在在排序列表裡點擊了 $x^i$ ，而未點擊 $x^j$ ，我們可以看做 $x^i$ 要優於 $x^j$ ，這樣兩者構造的樣本其標籤為 $y_{ij}=1$ 。我們要去擬合 $ilde{y}_{ij}$ 的表達式為：

$ilde{y}_{ij}=sigmoid( ilde{y}(x_i)- ilde{y}(x_j))=frac{1}{1+exp(-( ilde{y}(x_i)- ilde{y}(x_j)))}$

類似於邏輯回歸，這裡使用最大似然進行參數估計。設S為所有有序pair對的集合。針對任一有序對，我們可以調換順序使得 $y_{ij}=1$ ，所以可以進一步化簡。

$argmax prod_{<i,j>in S}^{}{ ilde{y}_{ij}}^{y_{ij}}(1- ilde{y}_{ij})^{1-y_{ij}}=argmin- prod_{<i,j>in S}^{}{ ilde{y}_{ij}}^{y_{ij}}(1- ilde{y}_{ij})^{1-y_{ij}}$

= $argmin- prod_{<i,j>in S}^{}{ ilde{y}_{ij}}$

這樣考慮這一對pair的話，可以定義損失函數，如下式：

$L=-log( ilde{y}_{ij})=log(1+exp(-( ilde{y}(x_i)- ilde{y}(x_j)))$

損失函數對參數 $heta$ 求導的話可得 $frac{partial L}{partial heta}=frac{partial L}{partial ( ilde{y}(x_i)- ilde{y}(x_j))}(frac{partial ilde{y}(x_i)}{partial heta}-frac{partial ilde{y}(x_j)}{partial heta})$

如果定義 $lambda_{ij}=frac{partial L}{partial( ilde{y}(x_i)- ilde{y}(x_j))}=-frac{1}{1+exp( ilde{y}(x_i)- ilde{y}(x_j))}$ ，則 $frac{partial L}{partial heta}$ 可以簡化為：

$frac{partial L}{partial heta}=lambda_{ij}(frac{partial ilde{y}(x_i)}{partial heta}-frac{partial ilde{y}(x_j)}{partial heta})$

前面我們提到，總共有偏置項、一次項係數和隱變數係數三類參數，通過前面 $ilde{y}(x)$ 的公式可以得到：

1、當 $heta$ 是偏置項時，相減時消去，故不用考慮；

2、當 $heta$ 是一次項 $w_{i}$ 時， $frac{partial ilde{y}(x_i)}{partial heta}=x_i$

3、當 $heta$ 是隱變數參數 $v_{i,f}$ 時， $frac{partial ilde{y}(x_i)}{partial heta}=x_isum_{j=1}^{n}{v_{j,f}x_j}-v_{i,f}x_i^2$ ，這裡求導涉及求和公式稍微麻煩點。

這樣就求出了導數，後面可以直接利用sgd之類的優化演算法進行參數的學習。

整個模型我們可以稱之為RankFM。在我們的業務場景中，RankFM比直接看做分類問題使用FM模型有一定提升。但RankFM這類pairwise方法也有不足的地方，把列表裡不同的item對都平等看待，並沒有考慮item的位置信息，比如排在前面的item明顯要比排在後面的item重要。

參考文獻

1.Exploiting ranking factorization machines for microblog retrieval.

2.LambdaFM: Learning Optimal Ranking with Factorization Machines Using Lambda Surrogates.