Factorization Machine

Posted on

对 LR 最朴素的特征组合就是二阶笛卡尔乘机，但是特征组合存在如下问题：

  1. 两两组合导致特征维度灾难
  2. 组合后的特征不见得都有效，事实上大部分可能无效
  3. 组合后的特征样本非常稀疏，意思就是组合容易，但是并不能在样本中找到对应的组合出现，也就没有办法在训练时更新参数。

Factorization Machine [1] 应运而生，优点有：

  1. 适用于稀疏数据
  2. FM (2-way) 比 LR 多了二阶 kernel，适用于大数据，线性复杂度，可以用 primal objective 而不是 dual objective 优化（如 SVM）
  3. 通用的预测模型，适用于任何实数特征。

下面是 [1] 的学习笔记。

Factorization Machine

假设训练数据集 DD 是高度稀疏的

D={(x1,y1),(x2,y2),...}D=\{ (x_1, y_1), (x_2, y_2), ...\}

特征向量 xx，在 [1] 中 MovieLen 的例子是用户 ID + 电影 ID + 用户特征 + 电影热编码 + 其他特征

x∈Rnx \in \mathbb R^n

预测结果 yy，在 [1] 中的例子是用户对电影的评分

y∈Ry \in \mathbb R

FM 模型定义（多项式拟合 logit）

\begin{align} \hat y(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 \\ &= w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^n \langle v_i , v_j \rangle x_i x_j \\ &= w_0 + \sum_{i=1}^{n} w_i x_i + \frac{1}{2} \sum_{f=1}^{k} \bigg( \bigg(\sum_{i=1}^{n} v_{i,f} x_i \bigg)^2-\sum_{i=1}^{n} v_{i,f}^2 x_i^2 \bigg) \end{align}

其中

w0∈R,w∈Rn,V∈Rn×k,vi∈R1×kw_0 \in \mathbb R, w \in \mathbb R^n, V \in \mathbb R^{n \times k},v_i \in \mathbb R^{1 \times k}

符号 ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle 是两个长度为 kk 的向量的内积

⟨vi,vj⟩:=∑f=1kvi,fvj,f\langle v_i, v_j \rangle := \sum_{f=1}^{k} v_{i,f} v_{j,f}

对于任意正定矩阵 WW，如果 kk 足够大，存在可逆矩阵 VV 使得 W=VVTW=VV^T。

其中 VV 的行元素 viv_i 描述了有 kk 个因子的第 ii 个特征变量。

k∈N0+k\in \mathbb N_0^+ 是一个超参数，定义了 factorization 的维度。

一个 2-way FM （d = 2）对单个特征和成对特征进行建模：

  • w0w_0 是 global bias （整体偏置量）
  • wiw_i 对第 i 个特征向量强度进行建模
  • w^i,j:=<vi,vj>\hat w_{i,j} := <v_i, v_j> 衡量第 i 个、第 j 个特征的交叉。关系进行建模。为什么不简单地用 wi,jw_{i,j} 做参数？因为数据稀疏难以训练，且可以在 d≥2d \ge 2 大大提高参数估计的质量。详见 Parameter Estimation Under Sparsity 章节。

Expressiveness

分解矩阵 VV 的表达能力如何呢？

众所周知，给定正有限矩阵 WW （交互矩阵），如果 kk 足够大，存在矩阵 VV （分解矩阵）使得 W=VVTW= VV^T。因此，当 kk 足够大时，一个 FM 可以表达任何矩阵 WW。通常限制 kk —— 即 FM 的 expressiveness，使模型又更好的泛化能力。

而且隐向量可以表示之前没有出现过的交叉特征，假如在数据集中经常出现 <男，篮球> ，<女，化妆品>，但是没有出现过<男，化妆品>，<女，篮球>，这时候如果用 wijw_{ij} 表示<男，化妆品> 的系数，就会得到0。但是有了男特征和化妆品特征的隐向量之后，就可以通过来求解 < v 男， v 化妆品> 来求解。

Parameter Estimation Under Sparsity

对观察样本中未出现过交互的特征分量，FM 能通过 factorizing 的方法，对相应的参数进行估计。

例如，假设需要估计 Alice 对 Star Trek 的评分 yy。训练集中没有这样的特征项 xx，满足 xAx_A 非零且  x_{ST} 非零，因此线性模型参数是 wA,ST=0w_{A,ST}=0。但是 FM 的二阶参数 <VA,VST><V_A, V_{ST}> 可以估计。

Computation

在 2-way FM，即 d=2d=2 时，FM 的估计参数

w0∈R,w∈Rn,V∈Rn×kw_0 \in \mathbb R, w \in \mathbb R^n, V \in \mathbb R^{n \times k}

模型方程 (1)(1) 的计算复杂度为

{n+(n−1)}+{n(n−1)2[k+(k−1)+2]+n(n−1)2−1}+2=O(kn2)\{n+(n-1)\} + \bigg\{ \frac{n(n-1)}{2} [k+(k-1)+2] + \frac{n(n-1)}{2} - 1 \bigg\} + 2 = O(kn^2)

其中第一个花括号对应 ∑i=1nwixi\sum_{i=1}^n w_i x_i 的乘法和加法操作数，第二个花括号对应 ∑i=1n−1∑j=i+1n(viTvj)xixj\sum_{i=1}^{n-1} \sum_{j=i+1}^n( v_i^T v_j) x_i x_j 的加法和乘法操作数。对 (1)(1) 进行改写，可以降低复杂度至 O(kn)O(kn)，详见论文 [1]：

∑i=1n∑j=i+1n⟨vi,vj⟩xixj=12∑f=1k((∑i=1nvi,fxi)2−∑i=1nvi,f2xi2)\sum_{i=1}^{n} \sum_{j=i+1}^n \langle v_i , v_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^{k} \bigg( \bigg(\sum_{i=1}^{n} v_{i,f} x_i \bigg)^2-\sum_{i=1}^{n} v_{i,f}^2 x_i^2 \bigg)

推广到多阶， d=nd = n 时，计算复杂度为 O(kdnd)O(k_d n^d)

Learning

Model

y^(x)=w0+∑i=1nwixi+∑i=1n∑j=i+1n⟨vi,vj⟩xixj\hat y(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^n \langle v_i , v_j \rangle x_i x_j

Gradient

利用 FM 公式的 Multilinearity 性质 [4]：

如果 Θ=(w0,w1,w2,...,wn,v11,v12,...,vnk)T\Theta =(w_0, w_1, w_2, ..., w_n, v_{11}, v_{12}, ..., v_{nk})^T 表示 FM 的所有模型参数，则对任意的 θ∈Θ\theta \in \Theta ，存在两个与 θ\theta 的取值无关的函数 gθ(x)g_\theta(x) 和 hθ(x)∗h_\theta(x)^* 使得成立

y^(x)=gθ(x)+θhθ(x)\hat y(x) = g_\theta(x) + \theta h_\theta(x)

对任意的 θ∈Θ\theta \in \Theta 求导，有：

∂∂θy^(x)=hθ(x)\frac{\partial}{\partial \theta} \hat y (x)=h_\theta(x)

∂∂θy^(x)={1, if θ is w0xi, if θ is wixi∑j=1nvj,fxj−vi,fxi2, if θ is vi,f\frac{\partial}{\partial \theta} \hat y(x) = \begin{cases} \begin{aligned} & 1, &\text{ if } \theta \text{ is } w_0 \\ & x_i, &\text{ if } \theta \text{ is } w_i \\\\ & 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} \\ \end{aligned} \end{cases}

Loss

  • 回归：
    • lossR=(y^(x)−y)2loss^{R}=(\hat y(x) - y)^2
  • 二分类：
    • HingeLoss=lossC=max(0,1−y^(x)∗y)HingeLoss=loss^{C}=max(0, 1-\hat y(x) * y)
    • LogitLoss=lossC=lnσ(yy^(x))LogitLoss=loss^{C}=\ln \sigma (y \hat y(x))，其中 σ\sigma 是 sigmoid 函数
  • Ranking
    • pairwise classification loss [6]

通常考虑 L2L2 正则，因此有

Θ∗=argminΘ∑i=1N(loss(y^(x(i)),y(i)+∑θ∈Θλθθ2))\Theta^*=\arg \min_{\Theta} \sum_{i=1}^{N} \bigg( loss(\hat y(x^{(i)}), y^{(i)} + \sum_{\theta \in \Theta} \lambda_{\theta} \theta^2) \bigg)

其中 λθ\lambda_\theta 是参数 θ\theta 的正则化系数。

由于 FM 参数通常较大，因此考虑分组策略，按特征分量的意义分成 Π\Pi 组（如人口统计学特征分成一组），从而得到正则化系数集 λ\lambda

λ0,λπ(i)w,λπ(i),jv,i∈1,2,...,n,j∈1,2,...,k\lambda^0, \lambda_{\pi(i)}^w, \lambda_{\pi(i),j}^{v},i \in {1,2,...,n}, j \in {1,2,...,k}

正则化 (regulization) 系数通常在单独的 holdout set 通过 grid search [8] 方法来获取，

Loss Gradient

以回归为例，梯度

∂lossR(y^(x),y)∂θ=(y^(x)−y)2=2(y^(x)−y)∂y^(x)∂θ\frac{\partial loss^R(\hat y(x), y)}{\partial \theta}=(\hat y (x) - y) ^2=2(\hat y(x) - y) \frac{\partial \hat y(x)}{\partial \theta}

当 θ\theta 取不同值时，梯度为

∂lossR(y^(x),y)∂θ={2(y^(x)−y), if θ is w02(y^(x)−y)xi, if θ is wi2(y^(x)−y)(xi∑j=1nvj,fxj−vi,fxi2), if θ is vi,f\frac{\partial loss^R(\hat y(x), y)}{\partial \theta} = \begin{cases} \begin{aligned} & 2(\hat y(x) - y) , &\text{ if } \theta \text{ is } w_0 \\ & 2(\hat y(x) - y) x_i , &\text{ if } \theta \text{ is } w_i \\\\ & 2(\hat y(x) - y) (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} \\ \end{aligned} \end{cases}

加上正则项

∂lossR(y^(x),y)∂θ={2(y^(x)−y)+2λ0w0, if θ is w02(y^(x)−y)xi+2λπ(i)wwi, if θ is wi2(y^(x)−y)(xi∑j=1nvj,fxj−vi,fxi2)+2λπ(i)vvi,j, if θ is vi,f\frac{\partial loss^R(\hat y(x), y)}{\partial \theta} = \begin{cases} \begin{aligned} & 2(\hat y(x) - y) + 2 \lambda^0 w_0, &\text{ if } \theta \text{ is } w_0 \\ & 2(\hat y(x) - y) x_i + 2 \lambda^w_{\pi_{(i)}} w_i, &\text{ if } \theta \text{ is } w_i \\\\ & 2(\hat y(x) - y) (x_i \sum_{j=1}^{n} v_{j,f} x_j - v_{i,f} x_i^2) + 2 \lambda^v_{\pi_{(i)}} v_{i,j}, & \text{ if } \theta \text{ is } v_{i,f} \\ \end{aligned} \end{cases}

Training

SGD

随机梯度下降的思想，是每个迭代从样本中取部分样本，计算参数 θ\theta 对于 loss 的梯度 gg ，更新 θ=θ+η⋅g\theta = \theta + \eta \cdot g ，以逐步逼近最优解。

求导数，有三种方法 [9]

  • 数值微分，f′(x)=limdx→0f(x+dx)−f(x−dx)2dxf'(x)=\lim_{d x \rightarrow 0} \frac{f(x + dx) - f(x - dx)}{2dx}
  • 符号微分，通过推导公式求导，本文使用方法
  • 自动微分，常见于 Deep Learning 框架如 TesnsorFlow

本文 Python 实现了一个简单回归版本，用于预测 movielens 的评分，详见 github。实现过程中遇到了 loss / 准确率收敛后变大的问题。快速 debug 的技巧是通过注释，观察哪个参数的更新逻辑，使结果不收敛。最后定位到参数 wiw_i 的更新代码写错。

ALS

学习过程中，解决单个参数的最优化问题

θ∗=argminθ{∑(x,y)∈D[y^(x)−y]2+∑θ∈Θλθθ2}\theta^*=\arg \min_{\theta} \bigg\{ \sum_{(x,y) \in D} [\hat y(x) - y]^2 + \sum_{\theta \in \Theta} \lambda_\theta \theta^2 \bigg\}

尝试求其解析解，记

T=∑(x,y)∈D[y^(x)−y]2+∑θ∈Θλθθ2T = \sum_{(x, y) \in D} [\hat y(x) - y]^2 + \sum_{\theta \in \Theta} \lambda_\theta \theta^2

则最小值点应满足

∂T∂θ∣θ∗=0\frac{\partial T}{\partial \theta} \bigg|_{\theta^*}=0

ALS 每轮迭代中，当 θ\theta 分别为 w0,wi,vi,jw_0, w_i, v_{i,j} 时，利用上式可以求得 θ\theta 的值。

FFM

假设样本的 nn 个特征属于 ff 个 field，那么 FFM 的二次项有 nfknfk 个隐向量。而在 FM 模型中，每一维特征的隐向量只有一个。

y^(x)=w0+∑i=1nwixi+∑i=1n∑j=i+1n⟨vi,fj,vj,fi⟩xixj\hat y(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^n \langle v_{i,f_j}, v_{j,f_i}\rangle x_i x_j

在 FFM 中 V∈Rn×k×fV \in \mathbb R^{n \times k \times f}， fif_i 是第 ii 个特征所属的 field，

在 FM 中 V∈Rn×kV \in \mathbb R^{n \times k}

Reference

[1] Rendle, Steffen. “Factorization machines.” Data Mining (ICDM), 2010. PDF

[2] Factorization Machines 学习笔记（二）模型方程 http://blog.csdn.net/itplus/article/details/40534923

[3] Factorization Machines 学习笔记（三）回归和分类 http://blog.csdn.net/itplus/article/details/40534951

[4] Factorization Machines 学习笔记（四）学习算法 http://blog.csdn.net/itplus/article/details/40536025

[5] 知乎：factorization machine和logistic regression的区别？https://www.zhihu.com/question/27043630

[6] T. Joachims, “Optimizing search engines using clickthrough data,” in

[7] KDD ’02: Proceedings of the eighth ACM SIGKDD international confer-ence on Knowledge discovery and data mining. New York, NY, USA:ACM, 2002, pp. 133–142. PDF

[8] Rendle, Steffen. “Learning recommender systems with adaptive regularization.” Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012.

[9] 自动求导–Deep Learning框架必备技术二三事 http://www.pengfoo.com/machine-learning/2017-04-17

[10] FM算法解析, 王子姬 https://zhuanlan.zhihu.com/p/37963267

[11] 深入FFM 原理与时间, 美团技术团队 https://tech.meituan.com/2016/03/03/deep-understanding-of-ffm-principles-and-practices.html

本文有帮助？