7.1 分解机简单介绍
分解机最早由Steffen Rendle于2010年在ICDM（Industrial Conference on Data Mining）上提出，它是一种通用的预测方法，即使在数据非常稀疏的情况下，依然能估计出可靠的参数，并能够进行预测。与传统的简单线性模型不同的是，因子分解机考虑了特征间的交叉，可对所有特征变量交互进行建模（类似于SVM中的核函数），因此在推荐系统和计算广告领域关注的点击率和转化率（ConVersion Rate，CVR）两项指标上有着良好的表现。此外，FM模型还具备可用线性时间来计算的特性，它可以整合多种信息，且能够与许多其他模型相融合。
我们常用的简单模型有线性回归模型及逻辑回归（LR）模型（见下面两个公式）两种，它们都是简单的线性模型，原理简单，易于理解，并且非常容易训练，对于一般的分类及预测问题，可以提供简单的解决方案。但是，在简单的线性模型中，要求特征之间是彼此独立的，因为它无法拟合特征之间的非线性关系，而现实生活中特征之间往往不是独立的，而是存在一定的内在联系。以新闻推荐为例，受众的性别与所浏览的新闻的类别有一定的关联性，如果能找出这类相关的特征，是非常有意义的，可以显著提升模型预测的准确度。
LR模型是CTR预估领域早期最成功的模型，也大量用于推荐算法排序阶段，大多工业推荐排序系统通过整合人工非线性特征，最终采用这种“线性模型+人工特征组合引入非线性”的模式来训练LR模型。因为LR模型具有简单、方便易用、解释性强、易于分布式实现等诸多好处，所以目前工业上仍然有不少算法系统采用这种模式。但是，LR模型最大的缺陷就是人工特征工程耗时费力，需要通过大量人力资源来筛选组合非线性特征，那么能否将特征组合的能力体现在模型层面呢？也即，是否有一种模型可以自动化地组合筛选交叉特征呢？答案是肯定的。
其实想做到这一点并不难，只要在线性模型的计算公式里加入二阶特征组合即可（见下面公式），任意两个特征进行两两组合，可以将这些组合出的特征看作一个新特征，加入线性模型中。而组合特征的权重和一阶特征的权重一样，都是在训练阶段学习获得的。其实这种二阶特征组合的使用方式和多项式核SVM是等价的（7.3.2节会介绍）。借助SVM中核函数的思路，我们可以在线性模型中整合二阶交叉特征，得到如下模型：
在上述模型中，任何两个特征之间两两交叉，其中，n代表样本的特征数量，xi是第i个特征的值，w0、wi、wij是模型参数，只有当xi与xj都不为0时，交叉项才有意义。
虽然这个模型看上去貌似解决了二阶特征组合问题，但是它有一个潜在的缺陷，即它对组合特征建模，泛化能力比较弱，尤其是在大规模稀疏特征存在的场景下，这个缺陷尤其明显。在数据稀疏的情况下，满足交叉项不为0的样本将非常少（非常少的主要原因包括有些特征本来就是稀疏的，很多样本在该特征上是无值的，有些是由于收集该特征成本过大或者由于监管、隐私等原因无法收集到），当训练样本不足时，很容易导致参数wij训练不充分而不准确，最终影响模型的效果。特别是对于推荐、广告等这类数据非常稀疏的业务场景来说（这些场景的最大特点就是特征非常稀疏，推荐方面是由于标的物是海量的，每个用户只对很少的标的物有操作，因此很稀疏，广告方面是由于很少有用户去点击广告，点击率很低，导致收集的数据量很少，因此也很稀疏），很多特征之间交叉是没有（或者没有足够多的）训练数据支撑的，因此无法很好地学习出对应的模型参数。因此上述整合二阶两两交叉特征的模型并未在工业界得到广泛采用。
那么我们有办法解决该问题吗？其实是有的，比如可以借助矩阵分解的思路，对二阶交叉特征的系数进行调整，让系数不再是独立无关的，从而减少模型独立系数的数量，进而解决由于数据稀疏导致无法训练出参数的问题，具体是将上面的模型修改为如下分解机模型：
其中，需要估计的模型参数是w0、w∈Rn、V∈Rn×k。这里的，是n维向量。
vi、vj是低维向量（k维），类似矩阵分解中的用户或者标的物特征向量表示。V是由vi组成的矩阵。“<>”是两个k维向量的内积：
vi就是FM模型核心的分解向量，k是超参数，一般取值较小（100左右）。
利用线性代数的知识，我们知道对于任意对称的半正定矩阵W，只要k足够大，一定存在矩阵V使得W=V·VT（Cholesky decomposition）。这说明，FM通过分解的方式基本可以拟合任意的二阶交叉特征，只要分解的维度k足够大（首先，W的每个元素都是两个向量的内积，所以一定是对称的，另外，分解机的公式中不包含xi与xi自身的交叉，这对应矩阵W的对角元素，所以我们可以自由选择W的对角元素，让对角元素足够大，保证W是半正定的）。由于在稀疏情况下，没有足够的训练数据来支撑模型训练，一般选择较小的k，虽然模型表达空间变小了，但是在稀疏情况下可以达到较好的效果，并且有很好的拓展性。
上面对分解机产生的背景、具体的模型公式及特点进行了简单介绍，下一节讲解怎么估计分解机的参数，并简单介绍一下分解机可以用于哪些机器学习任务。