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] 中的例子是用户对电影的评分

yRy \in \mathbb 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 个特征变量。

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

一个 2-way FM (d = 2)对单个特征和成对特征进行建模:

  • w0w_0 是 global bias (整体偏置量)
  • wiw_i 对第 i 个特征向量强度进行建模
  • \hat w_{i,j} := <\textbf v_i,="" \textbf="" v_j=""> 衡量第 i 个、第 j 个特征的交叉。关系进行建模。为什么不简单地用 wi,jw_{i,j} 做参数?可以在 d2d \ge 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,满足 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 的估计参数

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

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

{n+(n1)}+{n(n1)2[k+(k1)+2]+n(n1)21}+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 的乘法和加法操作数,第二个花括号对应 \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(kdnd)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]:

如果 Θ=(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_\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

λ0,λπ(i)w,λπ(i),jv,i1,2,...,n,j1,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

以回归为例,梯度

\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 ,更新 θ=ηg+θ\theta = \eta \cdot g + \theta ,以逐步逼近最优解。

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

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

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

实现过程中遇到了 loss / 准确率收敛后变大的问题。快速 debug 的技巧是通过注释,观察哪个参数的更新逻辑,使结果不收敛。最后定位到参数 wiw_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

则最小值点应满足

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

ALS 每轮迭代中,当 θ\theta 分别为 w0,wi,vi,jw_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

本文有帮助?