目录
- 从特征组合说起
- FM模型
- 1.原理
- 2.模型训练
- 3.预测阶段
- 4.一网打尽其他模型
- 5.FFM
- 总结
在上一篇文章中，我们讲到了使用逻辑回归和梯度提升决策树组合的模型融合办法，用于CTR预估，给这个组合起了个名字，叫“辑度组合”。这对组合中，梯度提升决策树GBDT，所起的作用就是对原始的特征做各种有效的组合，一颗树一个叶子节点就是一种特征组合。
从特征组合说起
从逻辑回归最朴素的特征组合就是二阶笛卡尔乘积，但是这种暴力组合存在如下问题：
1.两两组合导致特征维度灾难；
2.组合后的特征不见得都有效，事实上大部分可能无效；
3.组合后的特征样本非常稀疏，即组合容易，但是样本中可能不存在对应的组合，也就没办法在训练时更新参数。
如果把包含了特征两两组合的逻辑回归线性部分写出来，就是：
y
^
=
ω
0
+
∑
i
=
1
n
ω
i
x
i
+
∑
i
=
1
n
∑
j
=
j
+
1
n
ω
i
j
x
i
x
j
\hat{y} = ω_0 +\sum_{i=1}^n{ω_ix_i} +\sum_{i=1}^n\sum_{j=j+1}^n{ω_{ij}x_ix_j}
y^=ω0+i=1∑nωixi+i=1∑nj=j+1∑nωijxixj
这和原始的逻辑回归相比，多了后面的部分，特征两两组合，也需要去学习对应的参数权重。
问题是两两组合后可能没有样本能欧学习到$w_{ij}，在应用中，对于这些组合，也只能放弃，因为没有学到权重。
针对这个问题，就有了一个新的算法模型：因子分解机模型，也叫FM,即Factorization Machine。因子分解机也常常用来做模型融合。
FM模型
1.原理
因子分解机模型是在2010年被提出，因为逻辑回归在做特征组合时样本稀疏，无法学习到很多特征组合的权重，所以因子分解机的提出者就想，能否对上面那个公式中的 w i j w_{ij} wij做解耦，让每一个特征学习一个隐因子向量出来。
正如矩阵分解时，为每一个用户和每一个物品各自都学习一个隐因子向量，这样，任何两个特征需要组合时，只需隐因子变量做向量点积，就是两者组合特征的权重了。
针对逻辑回归的线性部分：
y
^
=
ω
0
+
∑
i
=
1
n
ω
i
x
i
+
∑
i
=
1
n
∑
j
=
i
+
1
n
<
v
i
,
v
j
>
x
i
x
j
\hat{y} =\omega_{0} + \sum_{i=1}^n{\omega_{i}x_{i}} + \sum_{i=1}^{n}{\sum_{j=i+1}^{n}}{<v_i,v_j>x_ix_j}
y^=ω0+i=1∑nωixi+i=1∑nj=i+1∑n<vi,vj>xixj
这个公式和前面特征组合的公式相比，不同之处就是原来有个\omega_{ij},变成了两个隐因子向量的点积<V_i,V_j>。
它认为两个特征之间，即便没有出现在一条样本中，也是有间接联系的。比如特征A和特征B,出现在一些样本中，特征B和特征C也出现在一些样本中，那么特征A和特征C无论是否出现在一些样本中，我们有理由认为两个特征仍然有些联系。
如果在实际预测CTR时，特征A和特征C真的同时出现在一些样本中，如果你用的是因子分解模型，你可以直接取特征A和特征C的隐因子向量，进行点积计算，就得到两者组合的权重。因子分解机的先进之处就在于此。
既然二阶组合特征可以学到隐因子向量，那么三阶、四阶、五阶呢？实际上，组合越多，计算复杂度就会陡增，一般在实际使用中，因子分解机多用在二阶特征组合中。
2.模型训练
因子分解机的参数学习并无特别之处，看目标函数，这里是把他当做融合模型来看的，用来做CTR预估，因预测目标是一个二分类，因子分解机的输出还需要经过sigmoid函数变换：
σ
(
y
^
)
=
1
1
+
e
−
y
^
\sigma(\hat{y}) =\frac{1}{1+ e^{-\hat{y}}}
σ(y^)=1+e−y^1
因此损失目标函数为：
l
o
s
s
(
θ
)
=
−
1
m
∑
i
=
1
m
[
y
(
i
)
l
o
g
(
σ
(
y
^
)
)
+
(
1
−
y
(
i
)
)
l
o
g
(
1
−
σ
(
y
^
)
]
loss(\theta) = - \frac{1}{m}\sum_{i=1}^m{[y^{(i)} log(\sigma(\hat{y})) + (1-y^{(i)})log(1-\sigma(\hat{y}) ]}
loss(θ)=−m1i=1∑m[y(i)log(σ(y^))+(1−y(i))log(1−σ(y^)]
公式中 σ ( y ^ ) \sigma(\hat{y}) σ(y^) 是因子分解机的预测输出后经过sigma函数变换得到的预估CTR, y ^ \hat{y} y^是真实样本的类别标记，正样本为1，负样本为0，m是样本总数。
对于这个损失目标函数使用梯度下降或者随机梯度下降，就可以得到模型的参数，注意函数实际上还需要加上正则项。
3.预测阶段
因子分解机中二阶特征组合那一部分，在实际计算时，复杂度有点高，如果隐因子向量的维度是k,特征维度是n,那么这个复杂度为O(kn^2),其中n方是特征要两两组合，k是每次组合都要对k维向量计算
点积。需稍微改造一下，改造过程如下:
loop1 begin: 循环k次，k就是隐因子向量的维度，其中，循环到第f次时做以下事情
loop2 begin:循环n个特征，第i次循环时做这样的事情
1. 从第i个特征的隐因子向量中拿出第f维的值
2. 计算两个值：A是特征值和f维的值相乘，B是A的平方
loop2 end
把n个A累加起来，并平方得到C，把n个B也累加起来，得到D
用C减D，得到E
loop1 end
把k次循环得到的k个E累加起来，除以2
这就是因子分解机中，二阶组合部分的实际计算方法，目前复杂度下降为O(kn)。
4.一网打尽其他模型
下面继续带你见识一些因子分解机的神奇之处。看下面这张图：
下面继续带你见识一些因子分解机的神奇之处。看下面这张图：
这张图中的每一条样本都记录了用户对电影的评分，最右边的y是评分，也就是预测目标；左边的特征有五种，用户ID、当前评分的电影ID、曾经评过的其他分、评分时间、上一次评分的电影。
现在我们来看因子分解机如何一网打尽其他模型的，这里说的打败是说模型可以变形成其他模型。
前面例子，因子分解机实现了带有特征组合的逻辑回归。
现在假设图中的样本特征只留下用户ID和电影ID,因子分解机模型就变成：
y
^
=
ω
0
+
ω
u
+
ω
i
+
<
V
u
,
V
i
>
\hat{y} =\omega_{0} + \omega_{u} + \omega_{i} + <V_{u},V_{i}>
y^=ω0+ωu+ωi+<Vu,Vi>
用户ID和电影ID，在一条样本中，各自都只有一个维度1，其他都是0。所以在一阶部分就没有了求和符号，直接是 w u w_u wu和 w i w_i wi,二阶部分乘积也只剩下了1，其他都为0，就转变为偏置信息的SVD。
继续，在SVD基础上把样本中的特征加上用户历史评分过的电影ID,再求隐因子向量，就转变为SVD++;再加上时间信息，就变成了time-SVD。
因子分解机把前面讲过的矩阵分解一网打尽了，顺便还干起了逻辑回归的工作。正因为如此，因子分解机常常用来做模型融合，在推荐系统的排序阶段肩负起对召回结果做重排序的任务。
5.FFM
在因子分解机基础上可以进行改进，改进思路是：不但认为特征和特征之间潜藏着一些关系，还认为特征和特征类型也有千丝万缕的关系。
这个特征类型，就是某些特征实际上来自数据的同一个字段。比如用户id，占据了很多维度，变成了很多特征，但他们都属于同一个类型，都叫做用户ID。这个特征类型就是字段，即Field.所以这种改进叫做Field-aware Factorization Machines ，简称FFM。
因子分解机模型如下：
KaTeX parse error: Expected group after '_' at position 42: …_{i=1}^n{\omega_̲}
总结
今天，我给你介绍了另一种常用来做CTR预估的模型，因子分解机。因子分解机最早提出在2010年，在一些数据挖掘比赛中取得了不错的成绩，后来被引入到工业界做模型融合，也表现不俗。
严格来说，因子分解机也算是矩阵分解算法的一种，因为它的学习结果也是隐因子向量，也是用隐因子向量的乘积来代替单个权重参数。
