Factorization Machine

Factorization Machine [1] 是一种预测模型，广泛用于推荐系统，优点有：

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

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

Factorization Machine

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

D=\{(\textbf x^{(1)}, y^{(1)}), (\textbf x^{(2)}, y^{(2)}), ...\}

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

\textbf x \in \mathbb R^n

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

y \in \mathbb Ry∈R

FM 模型定义

\hat y(\textbf x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^n <\textbf v_i,="" \textbf="" v_j=""> x_i x_j \tag{1}

估计参数

w_0 \in \mathbb R, \textbf w \in \mathbb R^n, \textbf V \in \mathbb R^{n \times k}

符号 <\cdot ,\cdot><⋅,⋅> 是两个长度为 kk 的向量的点积

<\textbf v_i,="" \textbf="" v_j=""> := \sum_{f=1}^{k} v_{i,f} \cdot v_{j,f}

其中 \textbf V 的行元素 \textbf v_i 描述了有 kk 个因子的第 ii 个特征变量。

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

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

• w_0w​0​​ 是 global bias （整体偏置量）
• w_iw​i​​ 对第 i 个特征向量强度进行建模
• \hat w_{i,j} := <\textbf v_i,="" \textbf="" v_j=""> 衡量第 i 个、第 j 个特征的交叉。关系进行建模。为什么不简单地用 w_{i,j}w​i,j​​ 做参数？可以在 d \ge 2d≥2 大大提高参数估计的质量。详见 Parameter Estimation Under Sparsity 章节。

Expressiveness

分解矩阵 \textbf V 的表达能力如何呢？

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

Parameter Estimation Under Sparsity

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

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

Computation

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

w_0 \in \mathbb R, \textbf w \in \mathbb R^n, \textbf V \in \mathbb R^{n \times k}

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

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

\sum_{i=1}^{n} \sum_{j=i+1}^n <\textbf v_i,="" \textbf="" v_j=""> 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(k_d n^d)O(k​d​​n​d​​)

Learning

Model

\hat y(\textbf x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^n <\textbf v_i,="" \textbf="" v_j=""> x_i x_j

Gradient

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

如果 \Theta =(w_0, w_1, w_2, ..., w_n, v_{11}, v_{12}, ..., v_{nk})^TΘ=(w​0​​,w​1​​,w​2​​,...,w​n​​,v​11​​,v​12​​,...,v​nk​​)​T​​ 表示 FM 的所有模型参数，则对任意的 \theta \in \Thetaθ∈Θ ，存在两个与 \thetaθ 的取值无关的函数 g_\theta(\textbf x) 和 h_\theta(\textbf x)^* 使得成立

\hat y(\textbf x) = g_\theta(\textbf x) + \theta h_\theta(\textbf x)

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

\frac{\partial}{\partial \theta} \hat y (\textbf x)=h_\theta(\textbf x) \frac{\partial}{\partial \theta} \hat y(\textbf 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

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

通常考虑 L2L2 正则，因此有

\Theta^*=\arg \min_{\Theta} \sum_{i=1}^{N} \bigg( loss(\hat y(\textbf x^{(i)}), y^{(i)} + \sum_{\theta \in \Theta} \lambda_{\theta} \theta^2) \bigg)

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

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

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

Loss Gradient

以回归为例，梯度

\frac{\partial loss^R(\hat y(\textbf x), y)}{\partial \theta}=(\hat y (\textbf x) - y) ^2=2(\hat y(\textbf x) - y) \frac{\partial \hat y(\textbf x)}{\partial \theta}

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

\frac{\partial loss^R(\hat y(\textbf x), y)}{\partial \theta} = \ \begin{cases} \ \begin{aligned} & 2(\hat y(\textbf x) - y) , &\text{ if } \theta \text{ is } w_0 \\ & 2(\hat y(\textbf x) - y) x_i , &\text{ if } \theta \text{ is } w_i \\\\ & 2(\hat y(\textbf 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}

加上正则项

\frac{\partial loss^R(\hat y(\textbf x), y)}{\partial \theta} = \ \begin{cases} \ \begin{aligned} & 2(\hat y(\textbf x) - y) + 2 \lambda^0 w_0, &\text{ if } \theta \text{ is } w_0 \\ & 2(\hat y(\textbf x) - y) x_i + 2 \lambda^w_{\pi_{(i)}} w_i, &\text{ if } \theta \text{ is } w_i \\\\ & 2(\hat y(\textbf 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 ，更新 \theta = \eta \cdot g + \thetaθ=η⋅g+θ ，以逐步逼近最优解。

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

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

本文 Python 实现了一个简单回归版本，用于预测 movielens 的评分，详见 https://github.com/liuslevis/FactorizationMachine

实现过程中遇到了 loss / 准确率收敛后变大的问题。快速 debug 的技巧是通过注释，观察哪个参数的更新逻辑，使结果不收敛。最后定位到参数 w_iw​i​​ 的更新代码写错。

ALS

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

\theta^*=\arg \min_{\theta} \bigg\{ \sum_{(\textbf x,y) \in D} [\hat y(\textbf x) - y]^2 + \sum_{\theta \in \Theta} \lambda_\theta \theta^2 \bigg\}

尝试求其解析解，记

T = \sum_{(\textbf x, y) \in D} [\hat y(\textbf x) - y]^2 + \sum_{\theta \in \Theta} \lambda_\theta \theta^2

则最小值点应满足

ALS 每轮迭代中，当 \thetaθ 分别为 w_0, w_i, v_{i,j}w​0​​,w​i​​,v​i,j​​ 时，利用上式可以求得 \thetaθ 的值。

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