FM系列1-1 FM論文

1. FM模型

對(duì)于訓(xùn)練集 D={(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}), \cdots}。給定一個(gè)樣本 (x^{(j)},y^{(j)})，即對(duì)于特征向量 \mathbf{x^{(j)}} = [x_1, x_2, \cdots, x_n]，有如下模型：

1.1 線性回歸模型

\hat{y}(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i

  • n 代表樣本的特征數(shù)量，x_i 是第 i 個(gè)特征的值，w_0、w_i 是模型參數(shù)
  • x_i 和 x_j (i \neq j) 之間是相互獨(dú)立的，即 \hat{y}(\mathbf{x}) 中僅考慮單個(gè)特征，而沒(méi)有考慮特征之間的組合(interaction)。
1.2 多項(xiàng)式模型

y(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n w_{ij} x_i x_j

  • n 代表樣本的特征數(shù)量 ，x_i 是第 i 個(gè)特征的值，w_0、w_i、w_{ij} 是模型參數(shù)
  • x_ix_j：特征 x_i 和 x_j 的組合，當(dāng) x_i 和 x_j 都非零時(shí)，組合特征 x_ix_j 才有意義
  • w_{ij} 一共有 \frac {n(n?1)} 2 個(gè)，任意兩個(gè)參數(shù)都是獨(dú)立的
  • 缺陷
    在數(shù)據(jù)稀疏性普遍存在的實(shí)際應(yīng)用場(chǎng)景中，每個(gè) w_{ij} 參數(shù)的訓(xùn)練需要大量 x_i 和 x_j 都非零的樣本；由于樣本數(shù)據(jù)本來(lái)就比較稀疏，滿足“w_{ij} 和 x_j 都非零”的樣本將會(huì)非常少。訓(xùn)練樣本的不足，很容易導(dǎo)致參數(shù) w_{ij} 不準(zhǔn)確，最終將嚴(yán)重影響模型的性能。
1.3 因子分解機(jī)(FM)

為了解決稀疏數(shù)據(jù)下的特征組合問(wèn)題，Konstanz大學(xué)Steffen Rendle（現(xiàn)任職于Google）于2010年提出了FM（Factorization Machine）。即
\hat{y}(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j

  • w_0 \in \mathbb{R}：全局偏置項(xiàng)
  • w_i：第 i 個(gè)特征變量的權(quán)重，w \in \mathbb{R}^n
  • \hat{w}_{ij} = \langle \mathbf{v}_i, \mathbf{v}_j \rangle ，\mathbf{V} \in \mathbb{R}^{n \times k}
    v_i 是第 i 維特征的隱向量，隱向量的長(zhǎng)度為 k（k<<nk<<n），包含 k 個(gè)描述特征的因子。
    ??,?? 代表向量點(diǎn)積，\langle v_i,v_j \rangle=\sum_{f=1}^k{v_{if}v_{jf}}
  • 模型復(fù)雜度 O(kn^2)
1.3.1 公式推導(dǎo)

在數(shù)據(jù)非常稀疏的場(chǎng)景下，由于大部分特征 x_ix_j 的值為0，因此很難直接求解出 \hat{w}_{ij}，因此，通過(guò)引入輔助變量 V_{i}=(v_{i1},v_{i2},...,v_{ik})，即
\ \mathbf{V} = \begin{pmatrix} v_{11} & v_{12} & \cdots & v_{1k} \\ v_{21} & v_{22} & \cdots & v_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ v_{n1} & v_{n2} & \cdots & v_{nk} \\ \end{pmatrix}_{n \times k} = \begin{pmatrix} \mathbf{v}_1 \\ \mathbf{v}_2 \\ \\ \vdots \\ \mathbf{v}_n \\ \end{pmatrix}
因此，
\hat{w} = \mathbf{V} \cdot \mathbf{V}^T = \begin{pmatrix} \mathbf{v}_1 \\ \mathbf{v}_2 \\ \\ \vdots \\ \mathbf{v}_n \\ \end{pmatrix} \cdot \begin{pmatrix} \mathbf{v}_1^T & \mathbf{v}_2^T & \cdots & \mathbf{v}_n^T \end{pmatrix} = \begin{pmatrix} \mathbf{v}_1 \mathbf{v}_1^T & \mathbf{v}_1 \mathbf{v}_2^T & \cdots & \mathbf{v}_1 \mathbf{v}_n^T \\ \mathbf{v}_2 \mathbf{v}_2^T & \mathbf{v}_2 \mathbf{v}_2^T & \cdots & \mathbf{v}_2 \mathbf{v}_n^T \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{v}_n \mathbf{v}_1^T & \mathbf{v}_n \mathbf{v}_2^T & \cdots & \mathbf{v}_n \mathbf{v}_n^T \\ \end{pmatrix}
從而，特征組合項(xiàng)
\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle = \text{sum} \begin{pmatrix} 0 & \mathbf{v}_1 \mathbf{v}_2^T & \mathbf{v}_1 \mathbf{v}_3^T & \cdots & \mathbf{v}_1 \mathbf{v}_n^T \\ 0 & 0 & \mathbf{v}_2 \mathbf{v}_3^T & \cdots & \mathbf{v}_2 \mathbf{v}_n^T \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & \mathbf{v}_{n-1} \mathbf{v}_n^T \\ 0 & 0 & \cdots & 0 & 0\\ \end{pmatrix}
即 \sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle 是這個(gè)對(duì)稱(chēng)矩陣的上三角部分求和（不包含對(duì)角線），所以 \sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle 等于 \sum_{i=1}^n \sum_{j=1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle 減去對(duì)角線 \sum_{i=1}^n \langle \mathbf{v}_i, \mathbf{v}_i \rangle 再除以2。
因此，
\begin{align*} & \sum_{i=1}^n{\sum_{j=i+1}^n{<v_i,v_j>x_ix_j}}\\ = & \frac{1}{2}\sum_{i=1}^n{\sum_{j=1}^n{<v_i,v_j>x_ix_j}}-\frac{1}{2}\sum_{i=1}^n{<v_i,v_i>x_ix_i}\\ =& \frac{1}{2}\left(\sum_{i=1}^n{\sum_{j=1}^n{\sum_{f=1}^k{v_{if}v_{jf}x_ix_j}}}-\sum_{i=1}^n{\sum_{f=1}^k{v_{if}v_{if}x_ix_i}}\right) \\ =& \frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^n{v_{if}x_i}\right)\left(\sum_{j=1}^n{v_{jf}x_j}\right)-\sum_{i=1}^n{v_{if}^2x_i^2}\right)\\ =& \frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^n{v_{if}x_i}\right)^2-\sum_{i=1}^n{v_{if}^2x_i^2}\right) \end{align*}

使用隨機(jī)梯度下降（Stochastic Gradient Descent）法學(xué)習(xí)模型參數(shù)。那么，模型各個(gè)參數(shù)的梯度如下：
\frac{\partial \hat{y}}{\partial \theta} = \left \{ \begin{array}{ll} 1, & \text{if}\; \theta\; \text{is}\; w_0 \qquad \text{(常數(shù)項(xiàng))} \\ x_i & \text{if}\; \theta\; \text{is}\; w_i \;\qquad \text{(線性項(xiàng))} \\ x_i \sum_{j=1}^{n} v_{j,f} x_j - v_{i,f} x_i^2, & \text{if}\; \theta\; \text{is}\; v_{i,f} \qquad \text{(交叉項(xiàng))} \end{array} \right.
其中，v_{j,f} 是隱向量 v_j 的第 f 個(gè)元素。由于 \sum_{j=1}^n v{j,f}x_j 只與 f 有關(guān)，而與 i 無(wú)關(guān)，在每次迭代過(guò)程中，只需計(jì)算一次所有 f 的 \sum_{j=1}^n v{j,f}x_j ，就能夠方便地得到所有 v_{i,f} 的梯度。顯然，計(jì)算所有 f 的 \sum_{j=1}^n v{j,f}x_j 的復(fù)雜度是 O(kn)；已知 \sum_{j=1}^n v{j,f}x_j 時(shí)，計(jì)算每個(gè)參數(shù)梯度的復(fù)雜度是 O(1)；得到梯度后，更新每個(gè)參數(shù)的復(fù)雜度是 O(1)；模型參數(shù)一共有 nk+n+1 個(gè)。因此，F(xiàn)M參數(shù)訓(xùn)練的復(fù)雜度也是 O(kn)。綜上可知，F(xiàn)M可以在線性時(shí)間訓(xùn)練和預(yù)測(cè)，是一種非常高效的模型。

1.3.2 論文中的示例

假設(shè)有一個(gè)電影評(píng)分系統(tǒng)，該系統(tǒng)記錄了用戶(hù) u \in U 在特定時(shí)間 t 對(duì)電影 i \in I 的評(píng)分 r \in {1,2,3,4,5} 數(shù)據(jù)。
對(duì)于用戶(hù) (users) U 和電影 (items) I ，可以假設(shè)

電影用戶(hù)集合

系統(tǒng)記錄的數(shù)據(jù) 為
樣本集合

需要根據(jù)這些數(shù)據(jù)來(lái)預(yù)測(cè)用戶(hù)對(duì)電影的評(píng)分。Steffen Rendle 在文中給了一個(gè)創(chuàng)建特征的例子，如下圖所示。


特征構(gòu)建
  1. User (藍(lán)色方框)：表示用戶(hù) ID (One-Hot編碼)，維度為 |U|
  2. Movie (紅色方框)：表示電影 ID (One-Hot編碼)，維度為 |I|
  3. Other Movies rated (黃色方框)：表示用戶(hù)評(píng)分過(guò)的所有電影，假設(shè)為電影集合 I_u，則特征分量 x_{i} = \frac 1 {|I_u|}
  4. Time (綠色方框)：表示用戶(hù)評(píng)價(jià)電影的時(shí)間，如(記錄中最早的日期) 2009年1月作為基數(shù)1，則2009年5月為5
  5. Last Movie rated (棕色方框)：表示用戶(hù)最近評(píng)分過(guò)的一部電影，若當(dāng)前用戶(hù)評(píng)價(jià)當(dāng)前電影之前還評(píng)價(jià)過(guò)其他電影，則用戶(hù)評(píng)價(jià)的上一部電影位置取1，其余為0；若當(dāng)前用戶(hù)評(píng)價(jià)當(dāng)前電影之前沒(méi)有評(píng)價(jià)過(guò)其他電影，則所有分量為0
  • x^{(i)}_j：表示第 i 個(gè)樣本的第 j 個(gè)特征分量

2. 總結(jié)、對(duì)比

2.1 FMs vs SVMs
  1. SVM的二元特征交叉參數(shù) w_{ij} 是相互獨(dú)立的，而FM的二元特征交叉參數(shù)是兩個(gè) k 維向量的乘積，即 \hat w_{i,j} = v_i \cdot v_j
  2. 多項(xiàng)式 SVM 每個(gè) w_{ij} 參數(shù)的訓(xùn)練需要大量 x_i 和 x_j 都非零的樣本，在數(shù)據(jù)稀疏場(chǎng)景中，由于樣本數(shù)據(jù)稀疏，滿足條件的訓(xùn)練樣本將會(huì)非常少，容易導(dǎo)致參數(shù) w_{ij} 不準(zhǔn)確，最終將嚴(yán)重影響模型的性能。而 FM 能夠在稀疏嚴(yán)重的情況下估計(jì)參數(shù)，即使某個(gè)交叉特征在訓(xùn)練集中從未出現(xiàn)過(guò)，但仍然可以通過(guò)對(duì)應(yīng)的兩個(gè)特征的內(nèi)積來(lái)估計(jì)其參數(shù)。
  3. FM可以在原始形式下進(jìn)行優(yōu)化學(xué)習(xí)，而基于kernel的非線性SVM通常需要在對(duì)偶形式下進(jìn)行
  4. FM的模型預(yù)測(cè)是與訓(xùn)練樣本獨(dú)立，而SVM則與部分訓(xùn)練樣本有關(guān)，即支持向量。
2.2 FMs vs MFs

分解模型包括 Matrix factorization (MF)、SVD++、PITF for Tag Recommendation、Factorized Personalized Markov Chains (FPMC)，這些模型都只在特定場(chǎng)景下使用，輸入形式也比較單一（比如MF只適用于categorical variables），而 FM通過(guò)對(duì)輸入特征進(jìn)行轉(zhuǎn)換，同樣可可以實(shí)現(xiàn)以上模型的功能，而且FM的輸入可以是任意實(shí)數(shù)域的數(shù)據(jù)，因此FM是一個(gè)更為泛化和通用的模型。

參考鏈接

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容