转载 https://www.jianshu.com/p/776598acc35a
1. 背景
在计算广告和推荐系统重，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。在进行CTR预估时，除了单特征外，往往要对特征进行组合。对于特征组合来说，业界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型。最近几年也出现了很多基于FM改进的方法，如deepFM，FNN，PNN，DCN，xDeepFM等。
2.动机（one-hot编码带来的问题）
FM（Factorization Machine）主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位对的一些特征，来预测用户是否会点击广告。数据如下
clicked 是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country，day，ad_type 则是对应对的特征。对于这种categories特征，一般都是进行one-hot编码处理。
将上面的数据进行one-hot编码后，就变成下面这样。
因为categories 特征，所有经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见，数据的稀疏性，是我们在实际应用场景中面临的一个非常常见的挑战与问题。
one-hot编码带来的另一个问题是特征空间变大。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的
3、对特征进行组合
普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。
一般的线性模型为：
表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下：
为了简单起见，我们只考虑二阶交叉的情况，具体的模型如下：
4.FM 求解
那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子中，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量的点积就是矩阵中user对item的打分。
我们再来看一下FM的训练复杂度，利用SGD（Stochastic Gradient Descent）训练模型。模型各个参数的梯度如下：
