写在前面
FM全称为factorization machine, 可以用解决回归、二分类问题
目的：解决高维稀疏数据中特征组合问题，适用于categorical feature。
参考文献
1、http://www.cnblogs.com/Matrix_Yao/p/4773221.html 梳理了ctr估计问题的大致流程，给出了一些工业界的方法，可以当做入门资料
2、https://blog.csdn.net/google19890102/article/details/45532745 针对于fm讲的很透彻，有些点没提到，程序很好懂
3、https://blog.csdn.net/g11d111/article/details/77430095 背景交代很清楚，我的背景介绍也是copy他的
4、关于fm与LR的比较，可以参看https://www.zhihu.com/question/27043630/answer/151138052最高赞的回答
5、https://blog.csdn.net/itplus/article/details/40536025 理论进阶
背景
1、稀疏数据
强调一点，FM的适用对象是稀疏数据。这一点之后会有更深入的介绍。
实际中，很多特征类型是categorical型，比如性别特征，有男、女两个选项，如果将男性标记为1，女性标记为2是不太合理的，因为数字是具有意义的，2是1的2倍，而不能说女性是男性的2倍，所以对于categorical feature都会使用独热编码one-hot encoding，将男性标记为[1,0]，女性标记为[0,1]。其他的categorical feature还有很多，比如文章类型，娱乐、运动、军事、科技等等，这些类别之间不具有数值意义的关系，同理需要使用one-hot encoding，关于one-hot encoding，如果你还不太了解，请看https://www.imooc.com/article/35900
categorical feature做完one-hot encoding之后是非常稀疏的，这在实际中十分常见，而许多方法对于稀疏数据都束手无策，比如SVM，它无法在非常稀疏的数据下学习复杂的非线性内核空间中的参数。
2、特征组合
在进行数据分析的过程中，特征工程是非常重要的一步，在特征工程这部分处理的好的话可以让模型的效果事半功倍。实际中有很多特征是相关联的，比如一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。FM就提供了一种这样特征组合的思路。
原理
我们还是先从线性模型说起好啦：）
一般的线性模型为
n表示n维特征
如果在线性模型中加入二阶特征的组合，那么会是这个样子的
这里存在一个问题，对于稀疏数据来说，xi 和xj同时不为0的情况非常少，这样会导致Wij无法通过训练获得。为了解决这个问题，FM诞生了，我们看一下FM是如何解决这个问题的：
这也解释了FM因式分解机名字的由来，它是将Wij进行了拆解。FM的模型为
求解
先不急着看如何求解的，这部分想解释下为什么将Wij拆解成vi和vj就能够求解了呢？这部分在作者的论文中有提到，下面的图片看着不太舒服的话，可以去看论文的第三部分：）
求解的话肯定需要一个优化目标，就是使损失函数最小
其中，
表示的是阶跃函数Sigmoid
基于随机梯度下降方式的求解：
这也解释了为什么FM的计算复杂度为O（kn）
FM优点
1、可以对稀疏数据中的特征进行组合
2、计算时间复杂度为O（kn）
3、FM是一种可以与任何实值特征向量一起使用的通用预测器。
缺点
你发现了没？在做特征组合的时候，我们不确定是同一域内的特征相组合（这不太合理，比如男性【1,0】两个维度数据，如果组合的是性别本身这两个维度，不太有意义），还是组合的是域间维度，比如性别和商品类别之间的组合是有意义的，对FM的一个改进是FFM, FFM是使得特征有自己的归属域，比如男性【1,0】是性别域，这两维数据不能拆开，下次我们再详细介绍一下FFM.
