crackcell's dustbin home projects
首页 > FM、FFM和DeepFM模型小结 > 正文

FM、FFM和DeepFM模型小结

1 从线性模型到FM1

线性模型的原始形式:

\begin{eqnarray} y=w_0 + \sum_{i=1}^{n}w_ix_i \end{eqnarray}

实际工作中,会人工进行特征组合,拿二维组合为例,可以写成:

\begin{eqnarray} y=w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}w_{i,j}x_ix_j \end{eqnarray}

这里的 \(w_{i,j}\) 的引入,会极大增加参数的个数,导致计算复杂度和过拟合风险的增加。

FM的核心思想,是为每个特征引入一个隐向量 \(V_i = [v_1,\cdots,v_k]\) ,组成一个矩阵:

\begin{eqnarray} V = \left[ \begin{matrix} v_{1,1} & \cdots & v_{1,k} \\ \vdots & & \vdots \\ v_{n,1} & \cdots & v_{n,k} \end{matrix} \right] \end{eqnarray}

矩阵中的每个行向量表示一个特征的隐向量。

然后用2个特征的隐向量的点积来表示特征组合的权重:

\begin{eqnarray} V_i \cdot V_j = [v_{i,1},\cdots,v_{i,k}] \left[ \begin{matrix} v_{j,1} \\ \vdots \\ v_{j,k} \end{matrix} \right] \end{eqnarray}

所以,式子(2)可以写成:

\begin{eqnarray} y = w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_ix_j \end{eqnarray}

这也就是FM模型的形式化表示。

1.1 FM模型的复杂度

如果直接求解式子(5),复杂度是 \(\mathcal{O}(kn^2)\) 。但因为通过因子分解,模型的参数并没有直接依赖于两个变量(下标是(i,j)的变量),可以降低成线性复杂度 \(\mathcal{O}(kn)\) :

\begin{eqnarray} && \sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle v_i,v_j \rangle x_ix_j \\ &=& \frac{1}{2} (\sum_{i=1}^{n}\sum_{j=1}^{n}\langle v_i,v_j \rangle - \sum{i=1}^{n}\langle v_i,v_i \rangle) \\ &=& \frac{1}{2} (\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{f=1}^{k}v_{i,f}v_{j,f}x_ix_j - \sum_{i=1}^{n}\sum_{f=1}^{n}v_{i,f}v_{i,f}x_ix_i) \\ &=& \frac{1}{2} \sum_{f=1}^{k} ((\sum_{i=1}^{n}v_{i,f}x_i)(\sum_{j=1}^{n}v_{j,f}x_j) - \sum_{i=1}^{n}v_{i,f}^2x_i^2) \\ &=& \frac{1}{2} \sum_{f=1}^{k} ((\sum_{i=1}^nv_{i,f}x_i)^2 - \sum_{i=1}^nv_{i,j}^2x_i^2) \end{eqnarray}
  • (7)式直观理解:想象成一个矩阵,(6)式是一个上三角矩阵,等于一个全矩阵减去对角线上的元素,再除以2
  • (10)式可以看出,整个计算的时间复杂度是 \(\mathcal{O}(kn)\)

1.2 FM模型的表达能力

FM的核心实际是将特征组合原来的权重矩阵 \(\hat{W}\) 表示成隐向量的乘积:

\begin{eqnarray} \hat{W} = VV^T = \left[ \begin{matrix} V_1 \\ \vdots \\ V_n \end{matrix} \right] [V_1^T, \cdots, V_n^T] \end{eqnarray}

每个V的维度是k,k越大,模型的表义能力越好,k越小,模型的泛化能力越好

1.3 在稀疏数据条件下的参数估计

FM在稀疏数据下,依然能保持比较好的参数学习能力。这是因为FM打破的参数之间的独立性,能复用更多数据。

1.4 FM模型的求解

FM模型参数的梯度信息:

\begin{equation} \frac{\partial{\hat{y}(x)}}{\partial{\theta}} = \left\{ \begin{array}{lr} 1, & \theta = w_0 \\ x_i, & \theta = w_i \\ x_i\sum_{j=1}^nv_{j,f}x_j-v_{i,f}x_i^2 & \theta = v_{i,f} \end{array} \right. \end{equation}
  • \(\sum_{j=1}^nv_{j,f}x_j\) 可以提前计算好
  • 使用这个梯度信息,就能使用梯度下降来求解
  • 由(12)式知道,迭代求解的时候只用关注特征值非0的情况,所以非常适用于稀疏数据

这里的梯度信息只是FM核心式子(5)的梯度信息,实际求解具体问题的时候,需要根据不同的损失函数,使用链式法则,加上完整的梯度信息。例如(未加正则化项):

  • 对于二分类问题: \(Loss(\hat{y}(x),y)=-\ln{sigmoid(\hat{y}(x)y)}\)
  • 对于回归问题: \(Loss(\hat{y}(x),y)=(\hat{y}(x)-y)^2\)

2 从FM到FFM2

Field-aware Factorization Machine是对FM的改进。

在实际工作中,有时候需要在指定的域的特征之间进行组合,例如,用户ID 和 商品ID 的组合,而避免用户ID之间的组合。FFM就是增加了这样的能力。

形式化表示:

\begin{eqnarray} y = w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle v_{i,f_1}v_{j,f_2} \rangle x_ix_j \end{eqnarray}
  • 这里的 \(f\) 指的是特征的域

3 从FFM到DeepFM3

DeepFM可以看做是在CTR预估领域对Wide & Deep的进一步发展,和WD不同,DeepFM可以做到完全的端到端,不需要在Wide部分做人工的特征组合。

3.1 模型结构

DeepFM包含FM部分和Deep部分,两部分共享同一个输入。

两个部分联合起来训练: \(\hat{y} = sigmoid(y_{FM} + y_{DNN})\)

3.1.1 FM部分

deepfm_fm_component.png

Figure 1: FM部分

  • FM部分就是一个完整的FM模型,图里面的Dense Embeddings对应的就是上文中FM的隐向量。

3.1.2 DNN部分

deepfm_dnn_component.png

Figure 2: DNN部分

  • CTR数据非常稀疏,直接输入神经网络,难以处理。需要现经过一个层Embedding,映射成低维稠密表示
  • 每个输入变量的Embedding向量长度一样,都是k

Footnotes:

1

Rendle, S. . (2011). Factorization Machines. IEEE International Conference on Data Mining. IEEE.

2

Juan, Y. , Zhuang, Y. , Chin, W. S. , & Lin, C. J. . (2016). [acm press the 10th acm conference - boston, massachusetts, usa (2016.09.15-2016.09.19)] proceedings of the 10th acm conference on recommender systems - recsys \"16 - field-aware factorization machines for ctr prediction. 43-50.

3

Guo, H. , Tang, R. , Ye, Y. , Li, Z. , & He, X. . (2017). Deepfm: a factorization-machine based neural network for ctr prediction.

Date: Mon Feb 18 13:51:02 2019

Author: Menglong TAN

Created: 2019-02-25 Mon 16:31

Validate

Modified theme and code from Tom Preston-Werner.