CTR学习笔记系列—— FM 和 FFM
一、为什么要用FM算法
在计算广告和推荐系统中，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。而在处理这类数据时，我们常常会使用one-hot编码（例如对用户ID、商品ID等），但这样就带了一个问题，数据太过稀疏。在面对如此稀疏的数据时，我们仅仅考虑每一个特征显然是不够的。这个时候，考虑特征之间的组合就显得尤为重要（其实就算不是CTR问题，平常在做特征处理的时候将特征组合起来也是特征工程的一个技巧）。
注意，下面所有的 和
都是指one-hot之后的特征：
one-hot前
one-hot后
二、算法主体
普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系（在理解的时候完全可以把 当成一个数来理解）：
线性回归
当我们考虑特征之间的组合时，我们稍微改动一下上面的公式就可以得到我们想要的算法：
考虑特征组合的回归
这个公式很好理解，就是把所有的特征都一一相乘再给予权值而已，但这个公式有个问题，对于稀疏数据来说， 和
都不为0的情况太少，这样将导致无法通过训练很好地得到
。
所以，将拆成两块来训练得到：
FM
向量和向量点乘（也就是 *
) 就是一个数，所以一个
拆成两个向量表示没什么问题。
其实就是指
的每一个元素，这里这个f不要和field这个概念联系起来。
通过下面的推导简化求解的难度：
这块的推导其实一点都不复杂，初高中的时候就在推这样的东西了吧。
第一步其实就是 如果想用
来表示（因为这样才好转化成向量和矩阵表示）的话，需要去掉一些重复的部分，所以先减去重复类似下标
ii这样的重复 ，然后发现还有类似下标
12 21 这样的重复，那么直接除以2就可以完美代替了。
第二步就是把向量表示直接拆出来，用每个元素相乘之后加和来表示（这就是我们在没学向量之前最喜欢的表示了，虽然学了之后还是习惯这种表示）
第三、四步就是结合律了
最后使用梯度下降求解（终于有个高级的了，不对，梯度下降其实就是求导，还是高中的）：
这样就得到了FM算法。
注：一开始看好多博客都是矩阵什么的，然后一直用矩阵向量理解上面的式子，结果真的是南辕北辙，再加上对f的错误理解，导致本来这么简单的推导反而纠结了不少时间，真的是满满的怨念。
三、FFM算法
FFM算法在FM算法的基础上引入了类别的概念，即field。例如下图，gender就是一个field（简单来说就是one-hot前的特征名）：
one-hot前
one-hot后
然后有人就想了，对每一个field我都用一样的v太奇怪了，那我干脆学习一个v不仅与特征相关，也与field相关好了：
由于隐向量与field相关，FFM二次项并不能够化简（额，所以FFM真的是一个拍脑门的想法）。
FFM通常只保留了的二次项，并且由于是CTR预测，所以经常会再加上sigmoid函数（为了防止混淆，使用z代替y，y用来表示最后sigmoid之后的值）：
求解梯度：
令label=0表示负样本，label=1表示正样本，C表示交叉熵损失函数:
当设label=-1表示负样本，label=1表示正样本时，梯度的形式会不同，可以参考原论文或者这篇博客
