簡介

本文要介紹的是S.Rendle在2010年提出的FM（Factorization Machine）模型，此模型的提出是為了解決在數(shù)據(jù)極其稀疏的情況下的特征組合問題。FM模型跟SVM模型類似，都是一個通用的預測器，但是FM模型可以在數(shù)據(jù)極其稀疏的情況下估計可靠的模型參數(shù)。FM模型對變量之間的嵌套交互進行建模（類似多項式核函數(shù)SVM），但是卻是用因子分解參數(shù)化的方式，而SVM中用的是稠密參數(shù)化的方式，這使得FM相比SVM的參數(shù)少了很多，更加容易計算，并且無需存儲額外的訓練數(shù)據(jù)（比如SVM中的支持向量）。

稀疏數(shù)據(jù)下的預測

通用的預測任務就是要估計一個函數(shù)：
$\hat y: \mathbb R^n → \mathbb T$ 該函數(shù)將一個 $n$ 維的實值特征向量 $x \in \mathbb R^n$ 映射到一個目標域 $T$ 。例如，對于回歸 $T = \mathbb R$ ，對于分類問題 $T = \{+, -\}$ 。在有監(jiān)督學習場景中，通常還有一個帶標簽的訓練數(shù)據(jù)集：
$D = \{ (x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}),...,(x^{(N)},y^{(N)}) \}$ 其中 $x^{(i) \in \mathbb R}$ 表示輸入數(shù)據(jù)，對應樣本的特征向量， $y^{(i)}$ 對應標簽， $N$ 為樣本的數(shù)量。
FM模型要處理的數(shù)據(jù) $x$ 是高度稀疏的。舉個例子，向量 $x$ 中的元素 $x_i$ 幾乎大多數(shù)都是0。令 $m(x)$ 為向量 $x$ 中所有非零元素的總和， $\overline m_D$ 是所有的向量 $x \in D$ 中非零元素 $m(x)$ 的平均值?，F(xiàn)實世界中的數(shù)據(jù)中存在著巨大的稀疏性，即( $\overline m_D <<n$ )。比如文本分析，推薦系統(tǒng)等。
下面以電影評分系統(tǒng)為例，給出一個關于高度稀疏數(shù)據(jù)的實例。

例1 考慮電影評分中的數(shù)據(jù)，每一條都包含了哪個用戶 $u \in U$ 在什么時候 $t \in \mathbb R$ 對哪部電影 $i \in I$ 打了多少分 $r \in \{1,2,3,4,5\}$ 這樣的信息。假定用戶集 $U$ 和電影集 $I$ 如下：

設觀察到的數(shù)據(jù)集

S

為：

利用觀測數(shù)據(jù)集

S

來進行預測任務的一個實例是：估計一個函數(shù)

\hat y

來預測某個用戶在某個時刻對某部電影的打分行為。根據(jù)這些數(shù)據(jù)，我們可以創(chuàng)建一個關于特征向量和標簽的表，如下：

圖1

圖1中的標簽部分比較簡單，就是把用戶對當前電影的評分數(shù)據(jù)當做標簽。比如

Alice

對電影TI的評分是5，因此第一行最后一列的數(shù)據(jù)為

y^{(1)}=5

。特征向量

x

包含5個部分，分別對應圖1中5個不同顏色的矩形框。

藍色矩形框表示為當前用戶信息，其維度為 $|U|$ ，該部分的分量中，當前用戶所在的位置為1，其余為0，即是one-hot向量的表示方法。
紅色矩形框表示當前評分電影信息，其維度為 $|I|$ 。當前被評分的電影所在的位置為1，其余為0，也是one-hot向量的表示方式。
黃色矩形框代表當前評分用戶評分過的所有電影信息，其維度為 $I$ 。該部分的分量中，被當前用戶評分過的所有電影（設個數(shù)為n）的位置為 $1/n$ ，其余位置為0。比如 $Alice$ 一共評價了3部電影TI，NH和SW，因此這3部電影所在的位置均為1/3=0.3。
綠色矩形框代表評分日期信息，其維度為1，表示當前用戶評分的時間。表示方式是將2009年1月作為基數(shù)1，以后每增加1個月就加1，如2009年5月可以換算為5。
綠色矩形框代表當前評分用戶最近評分過的一部電影的信息，其維度為 $I$ ，在該部分分量中，若當前用戶評價當前電影之前還評價過其他電影，則當前用戶評價的上一部電影的位置取1，其他為0。若當前用戶評價當前電影之前沒有評價過其他電影，則所有分量取0。

在本例中，特征向量 $x$ 的維度為 $|U|+|I|+|I|+1+|I| = |U| + 3|I| + 1$ 。在真實的電影評分系統(tǒng)中，用戶數(shù)量 $|U|$ 和電影數(shù)目 $|I|$ 都非常大，而每個用戶參與評分的電影數(shù)目則相對很小，于是，可想而知，每一條記錄對應的特征向量會是多么的稀疏。

模型方程

1.線性回歸模型

介紹FM模型方程之前，先回顧一下線性回歸方程。對于一個給定的特征向量 $x = (x_1,x_1,...,x_n)^T$ ，線性回歸的建模方程為：

其中 $w_0$ 和 $w=(w_1,w_2,...,w_n)^T$ 為模型參數(shù)。其中 $w_i$ 分別對應不同特征分量的權重，即代替了不同特征分量的重要程度。線性回歸的優(yōu)點在于可解釋性強，易擴展，效率高，因而在CTR領域還有著較為廣泛的運用。不過從上式中也可以很容易地看出它的缺陷，每個特征分量 $x_i$ 和 $x_j(i \ne j)$ 之間是相互獨立的，即 $\hat y(x)$ 中僅僅考慮單個特征分量，而沒有考慮特征分量之間的相互關系。

2.二階多項式回歸模型

在實際應用中，組合特征是很有意義的。比如在新聞推薦系統(tǒng)中, 喜歡軍事新聞的也很可能喜歡國際新聞, 喜歡時尚新聞的也很可能喜歡娛樂新聞。因此，我們把特征的兩兩組合加到線性回歸模型中，就可以得到二階多項式回歸模型：

其中 $n$ 代表樣本特征維度，截距 $w_0 \in \mathbb R$ ， $w = {w_1, w_2,...,w_n} \in \mathbb R^n, w_{ij} \in \mathbb R^n$ 為模型參數(shù)。這樣一來，就可以將任意兩個互異的特征分量之間的關系也考慮進來了。
但是從上式中可以發(fā)現(xiàn)，交叉項的系數(shù) $w_{ij}$ 一共有 $C_n^2 = \frac {n(n-1)}{2}$ 個，并且彼此之間是互相獨立的，在數(shù)據(jù)高度稀疏的情況下，這會導致交叉項系數(shù)學習困難。原因如下：
我們知道，回歸模型的參數(shù) $w$ 的學習結果就是從訓練樣本中計算充分統(tǒng)計量（凡是符合指數(shù)簇分布的模型都具有此性質），而在這里交叉項的每一個參數(shù) $w_{ij}$ 的學習過程都需要大量的 $x_i$ 、 $x_j$ 同時非零的訓練樣本數(shù)據(jù)。由于樣本數(shù)據(jù)本來就很稀疏，能夠滿足" $x_i \ne 0 \ and \ x_j \ne 0$ "的樣本數(shù)據(jù)就更少。訓練樣本不充分，學到的參數(shù) $w_{ij}$ 就不是充分統(tǒng)計的結果，導致參數(shù) $w_{ij}$ 不準確，而這會嚴重影響模型預測的結果和穩(wěn)定性。

為什么參數(shù) $w_{ij}$ 的更新依賴于滿足" $x_i \ne 0 \ and \ x_j \ne 0$ "條件的的樣本數(shù)據(jù)？
其實只需要自己動手計算 $\hat y(x)$ 對 $w_{ij}$ 的偏導數(shù)就能知道為什么了，留給讀者自己思考。

下面再舉個例子實際說明上面描述的問題。
仍以上文的電影評分數(shù)據(jù)為例，在觀測集 $S$ 中， $Alice$ 沒有對電影 $Stark Trek$ 的評分記錄，如果要直接估計 $Alice(A)$ 和 $Stark Trek(ST)$ 之間，或者說特征分類 $x_A$ 和 $x_{ST}$ 之間的相互關系，顯然會得到系數(shù) $w_{A,ST}=0$ 。即對于觀察樣本數(shù)據(jù)中未出現(xiàn)過交互的特征分量，不能對相應的參數(shù)進行估計。在高度稀疏的數(shù)據(jù)場景中，由于數(shù)據(jù)量的不足，樣本中出現(xiàn)未交互的特征分類是很常見的。

3.FM模型

為了解決這個問題，我們對系數(shù) $w_{ij}$ 做文章，將其表示成其他形式。為此，針對每個維度的特征分量 $x_i$ ，引入輔助向量：
$v_i = (v_{i1}, v_{i2},...,v_{ik})^T, i = 1,2,...,n$ 其中 $k \in \mathbb N^{+}$ 為超參數(shù)，并將 $w_{ij}$ 改寫成：
$\hat w_{i,j} = \Bbb v_i^T \Bbb v := \sum_{l=1}^k v_{il}v_{jl}$ 于是，函數(shù) $\hat y(x)$ 可以被寫成：

從數(shù)學的角度來看，這樣做的好處在哪里呢？對于交叉項系數(shù)，二階多項式回歸模型使用的是參數(shù)

w_{ij}

，而后者用的是

\hat w_{ij}

，為了更好地看清它們之間的關系，引入幾個矩陣：

將 $\{v_i\}_{i=1}^n$ 按行拼成的長方陣 $V$
交互矩陣 $W$
交互矩陣 $\hat W$

由此可見，二階多項式回歸模型和改進后的模型分別采用了交互矩陣 $W$ 和 $\hat W$ 的非對角線元素作為 $x_ix_j$ 的系數(shù)。由于 $\hat W = VV^T$ 對應一種矩陣分解。因此，我們把這種改進二階多項式模型的方法叫做因子分解機(Factorization Machines)方法。
讀者可能要問了， $VV^T$ 的表達能力怎么樣呢？即任意給定一個交互矩陣 $\hat W$ ，能否找到相應的(分解)矩陣 $V$ 呢？答案是肯定的，這里需要用到一個結論“當 $k$ 足夠大時，對于任意對稱正定的實矩陣 $\hat W \in \mathbb R^{n \times n}$ ，均存在實矩陣 $V \in \mathbb R^{n \times k}$ ,使得 $\hat W = VV^T$ 成立”。

將每個交叉項系數(shù) $w_{ij}$ 用隱向量的內積<v_i,v_j>表示，是FM模型的核心思想。具體地說，F(xiàn)M為每個特征學習了一個隱權重向量，在特征交叉時，使用兩個特征隱向量的內積作為交叉特征的權重。
下面給出論文中的FM方程的形式：

其中

v_i

代表第

i

個特征的隱向量，

<.,.>

代表的是兩個長度為

k

的向量的內積，計算公式為：

隱向量的長度

k

是一個超參數(shù)

(k \in \mathbb N^+, k<<n)

，隱向量

v_i = (v_{i,1}, v_{i,2},...,v_{i,k})

的含義是用

k

個描述特征的因子來描述第

i

維特征。這樣做之后，交叉項的參數(shù)由原來的

\frac {n(n-1)}{2}

降低為

nk

個，遠少于二階多項式模型中的參數(shù)數(shù)量。
此外，參數(shù)因子化表示后，使得 $x_hx_i$ 的參數(shù)與 $x_ix_j$ 的參數(shù)不再相互獨立。這樣我們就可以在樣本稀疏的情況下相對合理地估計FM交叉項的參數(shù)。

FM復雜度分析

先列出FM的方程：

其中需要估計的參數(shù)包括：

1+n+nk

個，其中

w_0

是整體的偏移量，

w

是對特征向量的各個分量的強度進行建模，

V

是對特征向量中任意兩個分量之間的關系進行建模。那么根據(jù)公式來看，其計算復雜度為：

其中第一個花括號對應

\sum_{i=1}^{n} w_{i} x_{i}

的加法和乘法操作數(shù)，第二個花括號對應

\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}\left(\mathbf{v}_{i}^{\top} \mathbf{v}_{j}\right) x_{i} x_{j}

的加法和乘法操作數(shù)，最后那個2代表整體的兩次加法。
這樣指數(shù)級的復雜度顯然是不能夠運用到大規(guī)模的實際應用中的，不過好在通過對上式改寫，可以將計算復雜度降低為線性的

O(kn)

，論文給出了具體過程:

分析一下改進后的時間復雜度，為：

注意，在高度稀疏數(shù)據(jù)場景中，特征向量

x

中絕大部分分量為0，即

m(x)

很小，而上式中關于

i

的求和只需要對非零元素進行。于是，計算復雜度變成

\mathcal{O} \left(k m( \mathbf{ x }) \right) \

了。

這里需要講一下這個公式的第（1）步到第（2）步的過程，其他的推導由于篇幅原因略過，如果讀者想深入了解，請參考https://zhuanlan.zhihu.com/p/58160982。
先計算一下：

將結果寫成矩陣的形式：

其中紅色的上三角部分就是我們要求的。
設該上三角為 $A$ ，則可推導如下：

其實也可以用排列組合的角度來思考這個問題， $\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j}$ 一共有 $C_n^2 = \frac {n(n-1)}{2} = \frac {1}{2} n^2 - \frac {1}{2} n$ 種組合方式，而
$\sum_{i=1}^{n} \sum_{j=1}^{n}\left\langle\mathbf{v}_{i} \mathbf{v}_{j}\right\rangle x_{i} x_{j} \$
一共有 $n^2$ 種組合方式。
$\sum_{i=1}^{n} \left \langle \mathbf{v}_{i}, \mathbf{v}_{i} \right \rangle x_{i} x_{i}$
一共有 $n$ 種組合方式，故從排列組合的方式來看，上式也是成立的。

如果用隨機梯度下降的方式來學習模型參數(shù)。那么，模型各個參數(shù)的梯度如下：

其中，

v_{j,f}

是隱向量

v_j

的第

f

個元素。

最優(yōu)化問題

FM的優(yōu)化目標是整體損失函數(shù)：

其中，對于回歸問題，loss取最小平方誤差：

對于二分類問題，loss取logit函數(shù)：

于是，F(xiàn)M的最優(yōu)化問題變成了：

我們通常還需要加上

L2

正則來防止過擬合，因此最優(yōu)化問題變成了：

其中

\lambda_0

表示參數(shù)

\theta

的正則化系數(shù)。

代碼實踐

雖然FM的公式看起來很復雜，但是代碼實現(xiàn)起來其實很簡單，模型部分代碼如下：

import torch
import torch.nn as nn
from BaseModel.basemodel import BaseModel

class FM(BaseModel):
    def __init__(self, config):
        super(FM, self).__init__(config)
        # 特征的個數(shù)
        self.p = 13 #config['num_features']
        # 隱向量的維度
        self.k = config['latent_dim']
        # FM的線性部分，即∑WiXi
        self.linear = nn.Linear(self.p, 1, bias=True)
        # 隱向量的大小為nxk,即為每個特征學習一個維度為k的隱向量
        self.v = nn.Parameter(torch.randn(self.k, self.p))
        # nn.init.uniform_(self.v, -0.1, 0.1)

    def forward(self, x):
        x = x[:, :13]
        # 線性部分
        linear_part = self.linear(x)
        # 矩陣相乘 (batch*p) * (p*k)
        inter_part1 = torch.mm(x, self.v.t())
        # 矩陣相乘 (batch*p)^2 * (p*k)^2
        inter_part2 = torch.mm(torch.pow(x, 2), torch.pow(self.v, 2).t())
        output = linear_part + 0.5 * torch.sum(torch.pow(inter_part1, 2) - inter_part2)
        return output

使用criteo數(shù)據(jù)集來做訓練，但是對于類別數(shù)據(jù)要先轉成one-hot向量編碼的形式，criteo數(shù)據(jù)集的一條記錄包含39個特征，其中前13個是連續(xù)特征，后26個是類別特征。13個連續(xù)特征進行歸一化處理之后保持不動，將26個類別特征先轉換成one-hot向量形式，然從concatenate起來，組成一個高維的稀疏向量輸入到FM模型中去訓練。采用SGD優(yōu)化器，MSE損失函數(shù)來訓練。

在訓練的時候，發(fā)現(xiàn)訓練一兩次，loss就變成了nan。這是由于loss數(shù)值太大，已經(jīng)無法使用float或者double來表示了。主要可能是數(shù)據(jù)本身有問題，學習率設置過大等。我自己降低了學習率后，模型可以優(yōu)化訓練。但是不保證代碼本身沒有問題，僅供參考。

測試部分代碼：

import torch
from FM.trainer import Trainer
from FM.network import FM
from Utils.criteo_loader import getTestData, getTrainData
import torch.utils.data as Data

fm_config = \
{
    'latent_dim': 10,
    'num_dense_features': 13, # for criteo data set
    'num_epoch': 10,
    'batch_size': 64,
    'lr': 1e-6,
    'l2_regularization': 1e-3,
    'device_id': 0,
    'use_cuda': False,
    'train_file': '../Data/criteo/processed_data/train_set.csv',
    'fea_file': '../Data/criteo/processed_data/fea_col.npy',
    'validate_file': '../Data/criteo/processed_data/val_set.csv',
    'test_file': '../Data/criteo/processed_data/test_set.csv',
    'model_name': '../TrainedModels/fm.model'
}

def toOneHot(x, MaxList):
    res = []
    for i in range(len(x)):
        t = torch.zeros(MaxList[i])
        t[int(x[i])] = 1
        res.append(t)
    return torch.cat(res, -1)

if __name__ == "__main__":
    ####################################################################################
    # FM 模型
    ####################################################################################
    training_data, training_label, dense_features_col, sparse_features_col = getTrainData(fm_config['train_file'], fm_config['fea_file'])
    p = sum(sparse_features_col) + fm_config['num_dense_features']

    rows, cols = training_data.shape
    train_x = torch.zeros((rows, p))
    for row in range(rows):
        dense = torch.Tensor(training_data[row][:fm_config['num_dense_features']])
        sparse = training_data[row][fm_config['num_dense_features']:]
        sparse = toOneHot(sparse, sparse_features_col)
        train_x[row] = torch.cat((dense, sparse),0)

    train_dataset = Data.TensorDataset(train_x.float().clone().detach().requires_grad_(True), torch.tensor(training_label).float())
    test_data = getTestData(fm_config['test_file'])
    test_dataset = Data.TensorDataset(torch.tensor(test_data).float())

    fm = FM(fm_config, p)

    ####################################################################################
    # 模型訓練階段
    ####################################################################################
    # # 實例化模型訓練器
    trainer = Trainer(model=fm, config=fm_config)
    # 訓練
    trainer.train(train_dataset)
    # 保存模型
    trainer.save()

完整代碼見https://github.com/HeartbreakSurvivor/RsAlgorithms/tree/main/FM。

參考

S. Rendle. Factorization machines. In ICDM, 2010.
《深度學習推薦系統(tǒng)》-- 王喆
https://www.cnblogs.com/pinard/p/6370127.html
http://www.52caml.com/head_first_ml/ml-chapter9-factorization-family/
http://www.itdecent.cn/p/25f0139637b7
http://stackbox.cn/2018-12-factorization-machine/
https://zhuanlan.zhihu.com/p/58160982
https://zhuanlan.zhihu.com/p/72586223
https://zhuanlan.zhihu.com/p/91151350
https://www.cnblogs.com/wyhluckdog/p/12168087.html
http://shomy.top/2018/12/31/factorization-machine/
https://github.com/1JasonZhang/FM-by-pytorch/blob/master/fm_model.py

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

推薦系統(tǒng)之FM（因子分解機）模型原理以及代碼實踐

推薦系統(tǒng)之FM（因子分解機）模型原理以及代碼實踐

簡介

稀疏數(shù)據(jù)下的預測

模型方程

1.線性回歸模型

2.二階多項式回歸模型

3.FM模型

FM復雜度分析

最優(yōu)化問題

代碼實踐

參考

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

推薦系統(tǒng)之FM（因子分解機）模型原理以及代碼實踐

簡介

稀疏數(shù)據(jù)下的預測

模型方程

1.線性回歸模型

2.二階多項式回歸模型

3.FM模型

FM復雜度分析

最優(yōu)化問題

代碼實踐

參考

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av