共计 1852 个字符，预计需要花费 5 分钟才能阅读完成。
一般情况下对于推荐输出的召回的候选集进行排序，ltr排序这个也是大家经常使用的。
lr+gbdt
这个组合在ctr预估中已经被广泛使用了，当然在推荐结果的重排序中也发挥着重要的作用。如果直接将构造的特征向量输入到lr模型当中，每个特征都是单独的特征，各自之间没有什么联系。其实很多时候特征之间的组合的意义大于特征自身，因此facebook使用了gbdt对原始输入特征进行特征组合，详见这篇文章有介绍以及代码实现，这种方法现在在业界内已经被广泛的使用了。。。
fm
fm就是因式分解的方式来实现特征的组合，在我们构造特征的时候会遇到很多的category类型的特征，但是我们需要对这些特征重新编码，那么常用的就是onehot编码，onehot编码很简单，但是带来的是超级稀疏的特征向量。假设我们有个category有1000种可能，那么我们就会产生1000维特征向量，其中只有一个值是有值的，其他都是0，如此如果这样的情出现的较多的化，那么我们最终构造的特征向量是非常稀疏的，那么现在介绍的FM就会解决稀疏特征的情况下特征的组合问题。
\(y(\mathbf{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 \label{eq:poly}\tag{1}\)
在上面的公式中需要学习的参数更多了，尤其是二次项参数学习起来更困难，首先你要保重\(x_i,x_j\)都是非0，否则对应的权重求解起来是个大问题，但是我们使用onehot编码的结果就是特征是稀疏特征向量，那么二次项特征权重的值更难训练了。。。
FM的思想就是要在二次项上面优化，假设有一个对称矩阵，上面提到的二次项权重就是矩阵中对应的数据，现在我们尝试将这个矩阵分解为两个矩阵相乘，公式如下：
\(\mathbf{W} = \mathbf{V}^T \mathbf{V}\)
那么上述\(w_ij\)可以如下表示
\(w_{ij}=V_i*V_j\)
这样可以解决\(w_ij\)学习的问题
在使用这种方式之后我们需要计算的未知变量的个数下降到kn个，k表示隐含变量的维度，n是样本的个数。因为任意\(w_ij\)都可以使用的隐含向量的点击乘积计算得到，所以未知的变量就减少很多了，现在是线性程度的变量个数。学习的复杂度在一定程度上下降了很多。
显而易见，前面描述的y(x)公式是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是 \(O(kn^2\)。但是，通过下述的等式，FM的二次项可以化简，其复杂度可以优化到 O(kn)。由此可见，FM可以在线性时间对新样本作出预测。
\(\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^k \left(\left( \sum_{i=1}^n v_{i, f} x_i \right)^2 – \sum_{i=1}^n v_{i, f}^2 x_i^2 \right) \label{eq:fm_conv}\tag{3} \)
我们再来看一下FM的训练复杂度，利用SGD（Stochastic Gradient Descent）训练模型。模型各个参数的梯度如下
\(\frac{\partial}{\partial\theta} y (\mathbf{x}) = \left\{\begin{array}{ll} 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{array}\right.\)
上述参数的更新的时间复杂度也是线性的。所以可以得知FM是一个高效的特征融合算法。
对于FM的改进有FFM，相比于传统的机器学习方法，google还提出了wide and deep神经网络来实现算法的改进。
后续在继续学习。。
