推荐系统

Factorization Machines

1. 论文提出了 Factorization Machine （因子分解机模型）来解决稀疏数据问题。并与支持向量机和矩阵分解算法（如SVD++）进行对比。

   FM模型在稀疏数据下可以同时训练一次项参数和二次项参数。设输入向量 (mathbf{x} = (x_0, x_1, ..., x_n))，则

   [widehat{y}(mathbf{x}) := omega_0 + sum_{i=1}^{n} omega_i x_i + sum_{i=1}^{n} sum_{j=i+1}^{n} left langlemathbf{v_i}, mathbf{v_j} ight angle x_i x_j ]

   其中，(omega_0) 是偏置，(omega_i) 是特征的一次项参数，共有 (n) 个。(mathbf{v_i}) 是长度为 (k) （超参数）的向量。二次项参数 (widehat{omega}_{i,j}) 是 (mathbf{v_i}) 和 (mathbf{v_j}) 的内积，因此二次项参数共有 (k cdot n) 个。总的参数为 (1 + n + k cdot n)

   此外，(sum_{i=1}^{n} sum_{j=i+1}^{n} left langlemathbf{v_i}, mathbf{v_j} ight angle x_i x_j) 的计算可以推导为

   [frac{1}{2} sum_{f=1}^{k}((sum_{i=1}^{n} v_{i,f} x_i)^2 - sum_{i=1}^{n} v_{i,f}^2 x_i^2) ]

   因此，对一个样本进行一次预测的时间复杂度为 (O(nk))。

   • FM模型可以加入正则项，如L2正则；也可以扩展为 d-way FM。每增加一维的交叉特征，就会增加 (k_d cdot n) 个参数，计算的时间复杂度也会乘以 (O(n))。

   • FM模型可以应用在一系列的预测问题中，比如回归问题，二分类问题和排序问题。二分类问题中可以选择 Hinge Loss 或者 Log Loss 作为损失函数。

2. 关于超参数k

   超参数 k 越大，模型的假设空间越大，表达能力越强；超参数 k 越小，模型的泛化效果越强。

   可以把所有的二次项系数 (widehat{omega}_{i,j}) 看做是一个 N x N 的实对称矩阵 W（对角线元素可以看做是 (mathbf{v_i}) 的 L2 范数，则均为非负数）。那么，当 k 足够大时，$ W = V^T cdot V$。但是，在稀疏问题下，由于没有足够的样本来估计复杂的交叉特征矩阵 W，因此 k 取较小值，提高模型的泛化能力。

3. 对于稀疏问题，Logistic Regression 学习每一个特征对于问题影响程度的“权重”，在推断时仅考虑数值不为0的特征，计算效率高，但无法学习到交叉特征（interactions between two features）对问题的影响。运用核技巧的对偶形式的 SVM 可以将交叉特征的影响引入到模型中。此时，支持向量定义SVM模型，确定了支持向量后，可以忽略其他数据以及所有支持向量中没有出现过的特征，同时适合处理稀疏问题。

   但 SVM 有几个缺点。

   1. 模型中需要存储支持向量，尽管支持向量仅在所有数据集中占有一小部分。

   2. SVM 学习稀疏特征的超平面参数（即引入非线性核函数）的能力不强。如果在训练集中某两个特征从来同时同时出现过，则SVM无法很好地估计其参数。

   3. 对偶形式的 SVM 的参数与训练数据的数量有关，而推荐系统中的数据量很大。

   Matrix Factorization 即矩阵分解方法（如SVD++）也有几个缺点。

   1. 只适合稀疏的类别特征矩阵，不适合处理标准的数值特征。

   2. 对于每一个特定的任务都需要单独地推导实现（derived individually for a specific task）

   FM的训练和预测的时间复杂度是线性的，可以在非常稀疏的数据集下实现参数的估计。对模型的存储过程中，只需要存储参数，不需要像 SVM 一样存储训练数据。同时，其输入即可以是类别特征，也可以是数值特征。在稀疏特征中，即使存在某个交叉特征在训练集中从来没有出现，但仍然可以通过对应的两个特征的 latent variables 的内积来估计其参数。

<br >
<br >

Field-aware Factorization Machines for CTR Prediction

1. 在 FM 模型中，引入了 Field 的概念。即 FFM 把相同性质的特征归类为同一个 Field。比如，对于一个类别特征，经过独热编码后变为 m 维特征，其中只有一维值为1，剩下 m-1 维的值为0。这 m 维特征属于同一个 Field。对于一个数值特征，可以归一化后不做处理，也可以现将连续的数值离散化后再做独热处理。处理过后的特征（要么使用前者得到1维特征，要么使用后者得到m维特征）属于同一个 Field。

   假设模型一定有 n 维特征，f 个 Field，latent variables 的长度为 k （超参数），那么其二次项参数共有 $ n cdot f cdot k$ 个，计算的时间复杂度为 $O(n^2 k) $。由于一个特征对应的 latent variable 只需要学习某个 Field 的特征对该特征的影响，因此 (k_{FFM} << k_{FM})。如果数据中只有 1 个 Field，那么 FFM 模型退化为 FM。

   [widehat{y}(mathbf{x}) := omega_0 + sum_{i=1}^{n} omega_i x_i + sum_{i=1}^{n} sum_{j=i+1}^{n} left langlemathbf{omega}_{i, f_j}, mathbf{omega}_{j, f_i} ight angle x_i x_j ]

2. FFM的实现

   [min_{mathbf{omega}} frac{lambda}{2}||omega||_2^2 + sum_{i=1}^{m} log(1+exp(-y_i phi_{FFM}(mathbf{omega}, mathbf{x_i}))) ]

   默认使用 AdaGrad 方法进行训练优化。在训练过程中，省略零值特征，提高训练和预测的速度。
   【也可以使用交替最小二乘法，也叫坐标下降法】

   根据经验，对于每一个实例，对其样本归一化可以使得预测精度轻微地提升，对参数的敏感性降低。

<br >
<br >

DeepFM: A Factorization-Machine based Neural Network for CTR Prediction

1. DeepFM 集成了 FM 和 DNN 两个模型，两个模型共用同一 Dense Embedding 层，模型最终的输出结果取决于 FM 和 DNN 输出的结果之和。DeepFM 同时对 low-order 的交叉特征（如 FM 的任意两个特征的交叉特征）和 high-order 的交叉特征（通过 DNN 学习得到）进行建模。因此，在不需要特征工程的情况下完成 end-to-end 的训练。

2. FM 部分
   输入为 d 维的稀疏向量(共有 (m_{field}) 个领域)，然后经过 Dense Embedding 层，得到 $ m_{field} cdot k$ 维向量，相当于输入的每一个 Field 对应的长度不一的向量，都对应着 Dense Embedding 的 k 维向量。然后，FM 同时以输入层和 Dense Embedding 层为输入

   [y_{FM} := left langle omega, x ight angle + sum_{i=1}^{d} sum_{j=i+1}^{d} left langlemathbf{v_i}, mathbf{v_j} ight angle x_i x_j ]

3. DNN 部分
   输入为 Dense Embedding 层， 然后经过两个 Hidden Layers，输出。

4. 总体

   [widehat{y} = sigmoid(y_{FM} + y_{DNN}) ]

5. embedding层的设计

   • 对于不同长度的输入 field 向量，得到的embedding长度都是 k
   • FM中的隐含向量 V 现在作为神经网络的权重，被学习来压缩输入 field 向量到 embedding 向量。