推荐算法（1）FM算法
一、FM 算法
一文读懂FM模型：https://zhuanlan.zhihu.com/p/109980037
FM算法简单梳理🍈: https://zhuanlan.zhihu.com/p/73798236
准确得预估ctr，对于提高流量得价值，增加广告收入有重要作用。业界常用得方法：人工特征+LR，gbdt，LR,FM,FFM。这些模型中FM、FFM表现突出，今天我们就来看看学习FM，下一篇我们在学习FFM。
FM（factor Machine，因子分解机）算法是一种基于矩阵分解的机器学习算法，是为了解决大规模稀疏矩阵中特征组合问题。
作用：
特征组合是许多机器学习建模过程中遇到的问题，如果直接建模，可能忽略特征与特征之间的关联信息，因此，可通通过构建新的交叉特征 这一特征组合方式提高模型效果。其实就是增加特征交叉项。
在一般的线性模型中，是各个特征独立思考的，没有考虑到特征之间的相互关系。但是实际上，大量特征之间是关联。 一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。
高维的稀疏矩阵是实际工程中常见的问题，并直接会导致计算量过大，特征权重更新缓慢。
而FM的优势，就是在于这两方面问题的处理。首先是特征组合，通过两两特征组合，引入交叉特征，提高模型得分。其次是高维灾难，通过引入隐向量，对特征参数进行估计。
总结FM的优点：可以在非常稀疏的数据中进行合理的参数估计；FM模型的时间复杂度是线性的；FM是一个通用模型，它可以用于任何特征为实值的情况；同时解决了特征组合问题。
优势：
- 可以在非常稀疏的数据中，进行合理的参数估计
- FM模型的复杂度是线性的，优化效果好，不需要像svm一样依赖于支持向量
- FM是一个通用的模型，他咳哟用于任何特征为实值得情况。而其他得因式分解模型只能用于一些输入数据比较固定得情况。
1.1 FM 特征组合
实对称矩阵分解求解: \(F \mathrm{FM}\) 为每个特征 \(\mathrm{i}\) 引入隐向量 \(v_i\), 用两个特征隐向量的内积表示这两个特征的权重, 即 组合特征 \(x_i . x_j\) 的权重为 \(\left\langle v_i, v_j\right\rangle\) 。
在传统的线性模型中, 各个特征之间都是独立考虑的，并没有涉及到特征与特征之间的交互关系，但实际上大量的 特征之间是相互关联的。如何寻找相互关联的特征, 基于上述思想 \(F M\) 算法应运而生。传统的线性模型为： \[ y=w_0+\sum_{i=1}^n w_i x_i \] 在传统的线性模型的基础上中引入特征交叉项可得 \[ y=w_0+\sum_{i=1}^n w_i x_i+\sum_{i=1}^{n-1} \sum_{j=i+1}^n w_{i j} x_i x_j \] 在数据非常稀疏的情况下很难满足 \(x_i 、 x_j\) 都不为 0 , 这样将会导致 \(w_{i j}\) 不能够通过训练得到, 因此无法进行相 应的参数估计。可以发现参数矩阵 \(w\) 是一个实对称矩阵, \(w_{i j}\) 可以使用矩阵分解的方法求解，通过引入辅助向量 \(V\) 。 \[ V=\left[\begin{array}{ccccc} v_{11} & v_{12} & v_{13} & \cdots & v_{1 k} \\ v_{21} & v_{22} & v_{23} & \cdots & v_{2 k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ v_{n 1} & v_{n 2} & v_{n 3} & \cdots & v_{n k} \end{array}\right]=\left[\begin{array}{c} \mathbf{v}_1 \\ \mathbf{v}_2 \\ \vdots \\ \mathbf{v}_n \end{array}\right] \] 然后用 \(w_{i j}=\mathbf{v}_i \mathbf{v}_j^T\) 对 \(w\) 进行分解 \[ w=V V^T=\left[\begin{array}{c} \mathbf{v}_1 \\ \mathbf{v}_2 \\ \vdots \\ \mathbf{v}_n \end{array}\right]\left[\begin{array}{llll} \mathbf{v}_1^T & \mathbf{v}_2^T & \ldots & \mathbf{v}_n^T \end{array}\right] \] 综上可以发现原始模型的二项式参数为 \(\frac{n(n-1)}{2}\) 个, 现在减少为 \(k n(k \ll n)\) 个。引入辅助向量 \(V\) 最为重要的 一点是使得 \(x_t x_i\) 和 \(x_i x_j\) 的参数不再相互独立, 这样就能够在样本数据稀疏的情况下合理的估计模型交叉项的参 数 \[ \begin{aligned} \left\langle\mathbf{v}_t, \mathbf{v}_i\right\rangle & =\sum_{f=1}^k \mathbf{v}_{t f} \cdot \mathbf{v}_{i f} \\ \left\langle\mathbf{v}_i, \mathbf{v}_j\right\rangle & =\sum_{f=1}^k \mathbf{v}_{i f} \cdot \mathbf{v}_{j f} \end{aligned} \] \(x_t x_i\) 和 \(x_i x_j\) 的参数分别为 \(\left\langle\mathbf{v}_t, \mathbf{v}_i\right\rangle\) 和 \(\left\langle\mathbf{v}_i, \mathbf{v}_j\right\rangle\), 它们之间拥有共同项 \(\mathbf{v}_i\), 即所有包含 \(\mathbf{v}_i\) 的非零组合特征的 样本都可以用来学习隐向量 \(\mathbf{v}_i\), 而原始模型中 \(w_{t i}\) 和 \(w_{i j}\) 却是相互独立的, 这在很大程度上避免了数据稀疏造 成的参数估计不准确的影响。因此原始模型可以改写为最终的FM算法。 \[ y=w_0+\sum_{i=1}^n w_i x_i+\sum_{i=1}^{n-1} \sum_{j=i+1}^n\left\langle\mathbf{v}_i, \mathbf{v}_j\right\rangle x_i x_j \]
由于求解上述式子的时间复杂度为
，可以看出主要是最后一项计算比较复杂，因此从数学上对该式最后一项进行一些改写可以把时间复杂度降为
第一步：对称矩阵中上三角的内积之和等于 整个向量的乘积和减去对角线上元素的和。
至此, FM算法的公式推导结束了, 为了更直观的了解怎么计算的, 举下面一个例子: 例如 \[ V=\left[\begin{array}{l} V 1 \\ V 2 \\ V 3 \end{array}\right]=\left[\begin{array}{lll} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}\right] \Rightarrow W=V * V^T \Rightarrow W=\left[\begin{array}{ccc} 14 & 32 & 50 \\ 32 & 77 & 122 \\ 50 & 122 & 194 \end{array}\right] \Rightarrow W=V * V^T \] 可推出下面公式: \[ \begin{gathered} \sum_i^3 \sum_j^3 w_{i j} * x_i x_j= \\ 14 * x_1 x_1+32 * x_1 x_2+50 * x_1 * x_3 \\ 32 * x_2 x_1+77 * x_2 x_2+122 * x_2 * x_3 \\ 50 * x_3 x_1+122 * x_3 x_2+194 * x_3 * x_3 \end{gathered} \] 而FM公式的第二个因子就是以上展开式"上三角“的元素。
1.2 参数更新
采用随机梯度下降法SGD求解参数： \[ \begin{gathered} \frac{\partial y}{\partial w_0}=1 \\ \frac{\partial y}{\partial w_i}=x_i \\ \frac{\partial y}{\partial v_i f}=x_i \sum_{j=1}^n v_{j, f} x_j-v_{i, f} x_i^2 \end{gathered} \] 由上式可知: 参数 \(v_{i, f}\) 只需要样本的 \(x_i\) 特征非零即可, 因此FM算法适用于稀疏场景, 并且FM算法的训练和预测 都可以在线性时间内完成, FM是一个非常高效的算法。
1.3 FM算法小结
- FM算法提升了参数学习效率和特征交叉后模型预估的能力。
- FM算法降低了因数据稀疏，导致特征交叉项参数学习不充分的影响；
- 模型的组合特征的参数在nk级别，通过公式推导，模型复杂度为\(O(nk)\) ，因此模型可以非常高效的进行训练和预测。