FM 分解向量机

1.FM背景

在计算广告中，CTR预估(click-through rate)是非常重要的一个环节，因为DSP后面的出价要依赖于CTR预估的结果。在前面的相关博文中，我们已经提到了CTR中相关特征工程的做法。对于特征组合来说，业界现在通用的做法主要有两大类：FM系列与Tree系列。今天，我们就来讲讲FM算法。

2.one-hote编码带来的问题

FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：(本例来自美团技术团队分享的paper)

image.png

clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。

将上面的数据进行one-hot编码以后，就变成了下面这样

image.png

因为是categorical特征，所以经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。举个非常简单的例子，假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见，数据的稀疏性，是我们在实际应用场景中面临的一个非常常见的挑战与问题。

one-hot编码带来的另一个问题是特征空间变大。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的。

3.对特征进行组合

普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。

一般的线性模型为：

image.png

从上面的式子很容易看出，一般的线性模型压根没有考虑特征间的关联。为了表述特征间的相关性，我们采用多项式模型。在多项式模型中，特征xi与xj的组合用xixj表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下：

上式中，n表示样本的特征数量,xi表示第i个特征。
与线性模型相比，FM的模型就多了后面特征组合的部分。

FM求解

从上面的式子可以很容易看出，组合部分的特征相关参数共有n(n−1)/2个。但是如第二部分所分析，在数据很稀疏的情况下，满足x_i,x_j都不为0的情况非常少，这样将导致ω_ij无法通过训练得出。

为了求出ω_ij，我们对每一个特征分量x_i引入辅助向量V_i=(vi1,vi2,⋯,vik)。然后，利用vivj^T对ωij进行求解。

image.png
那么ω_ij组成的矩阵可以表示为: image.png

个人理解：由于一开始的特征进行笛卡尔积之后有n（n-1）/2个新的特征，那么就需要这么多个参数，但是如果当n很大的时候，参数就会过多，于是我们将原始的每一维特征对应为一个（n,k）的分解向量，这个向量可以想象成一个参数空间，描绘着这维特征和其他特征组合的相关信息，当我们需要计算两个特征的特征组合的时候我们就将其对应的分解向量做内积，得出来的值就是新特征对应的权重。那么这个K值就代表着FM模型的表达能力（原始特征比较多就大一点，较少的小一点，我感觉是这样的）

然后接下来我们就要找一个方式将原始的<Vi,Vj>，转换一下成为由V_i,k组成，推导公式如下：

image.png
上面的式子中有同学曾经问我第一步是怎么推导的，其实也不难，看下面的手写过程
image.png
经过这样的分解之后，我们就可以通过随机梯度下降SGD进行求解：
image.png

参考文献：
https://mp.weixin.qq.com/s/ZKgIpQFbWA0WnwBHvtYaBQ
http://blog.csdn.net/bitcarmanlee/article/details/52143909