# 在CTR预估中，把类别型特征进行one-hot编码会带来哪些问题？
假设一个广告分类的问题，根据用户和广告位相关的特征，预测用户是否点击了广告。元数据如下：
| Clicked? | Country | Day | Ad_type |
|---|---|---|---|
| 1 | USA | 26/11/15 | Movie |
| 0 | China | 1/7/14 | Game |
| 1 | China | 19/2/15 | Game |
“Clicked？”是label，Country、Day、Ad_type是特征。由于三种特征都是categorical类型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征。
| Clicked? | Country=USA | Country=China | Day=26/11/15 | Day=1/7/14 | Day=19/2/15 | Ad_type=Movie | Ad_type=Game |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
由上表可以看出，经过One-Hot编码之后，大部分样本数据特征是比较稀疏的。CTR/CVR预测时，用户的性别、职业、教育水平、品类偏好、商品的品类等，经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征，如商品的末级品类约有550个，采用One-Hot编码生成550个数值特征，但每个样本的这550个特征，有且仅有一个是有效的（非零）。
One-Hot编码的另一个特点就是导致特征空间大。例如，商品品类有550维特征，一个categorical特征转换为550维数值特征，特征空间剧增。
# 多项式模型也即对所有的特征进行两两交叉赋予权重的方法存在什么缺陷？
多项式模型的公式为：
从这个公式可以看出，组合特征的参数一共有
# FM的原理是什么？与矩阵分解有什么联系？
FM为每个特征学习了一个隐权重向量，在特征交叉时，使用特征隐向量的内积作为交叉特征的的权重。
本质上，FM引入隐向量的做法，与矩阵分解用隐向量代表用户和物品的做法异曲同工。FM是对矩阵分解隐向量的思想做了进一步分扩展，从单纯的用户、物品隐向量扩展到了所有特征上。
# 为什么FM模型的泛化能力强？
FM是学习单个特征的embedding，并不依赖某个特定的特征组合是否出现过，所以只要特征 [公式] 和其它任意特征组合出现过，那么就可以学习自己对应的embedding向量。
比如样本中没有没有<男性，化妆品>交叉特征，即没有男性看化妆品广告的数据。如果多项式模型来建模，对应的交叉项参数w_{男性，化妆品}是学不出来的，因为数据中没有对应的共现交叉特征。那么多项式模型就不能对出现的男性看化妆品广告场景给出准确地预估。
而FM模型是把交叉项参数用对应的特征隐向量内积表示，这里表示为w_{男性，化妆品}=<v_{男性}，v_{化妆品}>，即用男性特征隐向量v_{男性}和化妆品特征隐向量v_{化妆品}的内积表示交叉项参数w_{男性，化妆品}由于FM学习的参数就是单特征的隐向量，那么男性看化妆品广告的预估结果可以用<v_{男性}，v_{化妆品}>得到。这样，即便训练集中没有出现男性看化妆品广告的样本，可以通过内积算出这个新特征组合的权重，FM模型仍然可以用来预估，提升了预估的能力，这就是为什么说FM模型繁华能力强的根本原因。
# FM相较于POLY2为什么泛化能力更好？在工程上有什么优势？
在某商品推荐的场景下，样本有两个特征，分别是频道和品牌，某条训练样本的特征组合是(ESPN，Adidas)。在POLY2算法中，只有当ESPN和Adidas同时出现在同一个训练样本中，模型才能学到这个组合特征对应的权重；
而在FM中，ESPN的隐向量也可以通过（ESPN,Gucci）样本进行更新，Adidas的隐向量也可以通过（NBC,Adidas）进行更新，大幅降低了模型对于数据稀疏性的要求，甚至对于一个从来没有出现过的特征组合（NBC,Gucci），由于模型之间已经分别学习过NBC和Gucci的隐向量，具备了计算该特征组合权重的能力，但是泛化能力大大提高。
在工程上，FM同样可以用梯度下降法进行学习，使其不失实时性和灵活性。相比之后深度学习模型复杂的网络结构导致难以部署和线上服务，FM较容易实现的模型结构使其线上推断的过程相对简单，也更容易进行线上部署和服务。
# FM的训练复杂度是多少？怎么推导？
直观上看，FM的复杂度是
解读第一步到第二部，这里用A表示系数矩阵V的上三角元素，B表示对角线上的交叉项系数。由于系数矩阵V是一个对称阵，所以下三角和上三角相等，有下式成立：
其中，
由于
# 请简述FM的优势。
FM算法可以在线性时间内完成模型训练，以及对新样本作出预测，所以说FM是一个非常高效的模型。FM模型的核心作用可以概括为以下三个：
1）FM降低了交叉项参数学习不充分的影响：one-hot编码后的样本数据非常稀疏，组合特征更是如此。为了解决交叉项参数学习不充分、导致模型有偏或不稳定的问题。作者借鉴矩阵分解的思路：每一维特征用k维的隐向量表示，交叉项的参数
| 共现交叉特征 | 样本数 | 注 |
|---|---|---|
| <女性，汽车> | 500 | 同时出现<女性，汽车>的样本数 |
| <女性，化妆品> | 1000 | 同时出现<女性，化妆品>的样本数 |
| <男性，汽车> | 1500 | 同时出现<男性，汽车>的样本数 |
| <男性，化妆品> | 0 | 样本中无此特征组合项 |
<女性，汽车>的含义是女性看汽车广告。可以看到，但特征对应的样本数远大于组合特征对应的样本数。训练时，但特征参数相比交叉项特征参数会学习地更充分。因此，可以说FM降低了因数据稀疏，导致交叉项参数学习不充分的影响。
2）FM提升了模型预估能力。依然看上面的示例，样本中没有没有<男性，化妆品>交叉特征，即没有男性看化妆品广告的数据。如果yoga多项式模型来建模，对应的交叉项参数w_{男性，化妆品}是学不出来的，因为数据中没有对应的共现交叉特征。那么多项式模型就不能对出现的男性看化妆品广告场景给出准确地预估。 FM模型是否能得到交叉项参数w_{男性，化妆品}呢？答案是肯定的。由于FM模型是把交叉项参数用对应的特征隐向量内积表示，这里表示为w_{男性，化妆品}=<v_{男性}，v_{化妆品}>，即用男性特征隐向量v_{男性}和化妆品特征隐向量v_{化妆品}的内积表示交叉项参数w_{男性，化妆品}由于FM学习的参数就是单特征的隐向量，那么男性看化妆品广告的预估结果可以用<v_{男性}，v_{化妆品}>得到。这样，即便训练集中没有出现男性看化妆品广告的样本，FM模型仍然可以用来预估，提升了预估的能力。
3）FM提升了参数学习效率：这个显而易见，参数个数由
最后一句话总结，FM最大特点和优势：FM模型对稀疏数据有更好的学习能力，通过交互项可以学习特征之间的关联关系，并且保证了学习效率和预估能力。
与其他模型相比，它的优势如下：
- FM是一种比较灵活的模型，通过合适的特征变换方式，FM可以模拟二阶多项式核的SVM模型、MF模型、SVD++模型等；
- 相比SVM的二阶多项式核而言，FM在样本稀疏的情况下是有优势的；而且，FM的训练/预测复杂度是线性的，而二项多项式核SVM需要计算核矩阵，核矩阵复杂度就是N平方。
- 相比MF而言，我们把MF中每一项的rating分改写为 r_{ui}∼β_u+γ_i+x^T_uy_i，从公式(2)中可以看出，这相当于只有两类特征
# FFM相较于FM有什么改进？
相比FM模型，FFM模型引入了特征域的概念，其数学形式的二阶部分如下：
其与FM的区别在于隐向量由原来的
其中的域指的是特征域，比如性别、品牌、广告分类就是三个不同的特征域。