推荐系统 FM因式分解

reference：知乎 FM算法解析

• LR算法没有二阶交叉
  
  如果是id类特征，这里的x是0/1，raw的特征输入就是float，当然，在我的理解里，一般会把raw的特征进行分桶，还是映射到0/1特征，不然这个$w_i$的功能也太重了…?（想想其实是没有道理的）

其实为什么常把连续值的变量进行分桶，我也不是很清楚… 只是大家都这么干…似乎效果会更好

• poly2算法引入二阶交叉
  二阶交叉能提升模型的表达能力（辛普森悖论）
  先进行特征的笛卡尔积，然后在赋予这个笛卡尔积各值一个权重。举例：

  3个特征分别是：

  • f1国家( 候选集为{中国,美国,加拿大} )
  • f2性别( 候选集为{男,女} )
  • f3人群( 候选集为{青年,中年,老年} )

  poly2算法就是先对特征进行笛卡尔积获得交叉特征，然后在交叉特征的基础上做LR，所以在此时会生成三个新二阶特征：

  • f1f2国家x性别( 候选集为{中国男,中国女,美国男,美国女,加拿大男,加拿大女} )
  • f1f3国家x人群( 候选集为{中国青年,中国中年,中国老年,美国青年,美国中年,美国老年,加拿大青年,加拿大中年,加拿大老年} )
  • f2f3性别x人群( 候选集为{男青年,男中年,男老年,女青年,女中年,女老年} )。

  可以看到，此时二阶特征的候选集就一下子大了很多，每一个候选项都会对应一个权重（当特征为1的时候，该权重生效；特征为0的时候，权重就不生效，也不会得到反向传播的梯度进行自我更新），所以此时二阶交叉特征的权重变成了6+9+6=21个（一阶特征的权重有3+2+3=8个）。我举的例子中一阶特征候选集不大，但实际中一阶特征候选集是会比较大的（也就是常说的特征稀疏）,比如类目特征可能就有几百上千维，再和另一个比较稀疏的特征进行笛卡尔积，二阶交叉特征的权重数量就会陡增，同时也因为两个稀疏特征的共现概率更低了，所以训练收敛难度会更高。

• FM进行计算简化

  • 先将特征映射成稠密的隐向量，可以理解为one-hot的候选集映射到一个embedding-lookup table中
  • 复杂度分析
    • 参数量复杂度
    • 计算时间复杂度 $O(k{n}^2)$ --> $O(kn)$

• 其实现在大部分的W&D的模型里面，one-hot向量映射到embedding向量的过程，就是因式分解的一个过程；wide侧的手动特征交叉则是POLY2的思想

• 复杂度分析：