Field-aware Factorization Machines for CTR Prediction
简介
强烈建议在阅读本文之前阅读一下上一篇FM的介绍，因为FFM（Field-aware Factorization Machines）就是在FM的基础之上改进了联合特征分解方法。
在FM方法中每一个特征都会学习得到一个向量，该向量用于和其他特征的向量运算得到两个特征的联合的权重，那么这个向量可以理解为特征在一个稠密空间中的映射，或者说是一种包含语义信息的映射。那么很容易的，我们会想到一个问题：
假设存在三个特征性别，年龄和购物商品，每个特征都对应与一个向量。那么我们可以得知对于特征性别的向量，其会和年龄与购买商品两个特征的向量分别做点积运算，但是后两者之间在人类的认知中是非常迥异且不可比较的，那么实际上我们是要求特征性别的向量可以同时的兼顾其在年龄和购买商品两个不同空间中的特性，这会对性别这个特征的向量的学习造成一定的麻烦。而且从另一个角度上说，性别这个特征的向量里就会包含了购买商品相关的信息，带着这个信息和年龄特征进行运算的时候，很难说是好还是坏。
面对以上这个问题，很容易想到一种方案：假设我们可以按照人类的逻辑来分类输入的特征，譬如将所有特征分类为：性别、年龄、购买、差评等等，同时不再使用一个向量来表示一个特征，而是对于一个特征在不同领域内都会训练一个独立的向量来表示。对于上面这个例子，性别=男这个特征最后会训练得到4个向量：性别=男->性别，性别=男->年龄，性别=男->购买，性别=男->差评。因此当我们计算性别和年龄这两个特征的联合权重时，实际上使用的是：性别=男->年龄点乘年龄=18->性别，这样我们就避免了上述问题中要求一个向量可以同时精确表达其在不同领域中的意义造成的困难。
以上这个方法的一个具体的算法就是本文要讲的：FFM
方法
从以上的分析中，可以非常直观的得到FFM组合项的公式：
\[FFM(w, x) = \sum_{j_1=1}^{N} \sum_{j_2=j_1 + 1}^{N} (w_{j_1, f_2} \cdot w_{j_2, f_1})x_{j_1}x_{j_2}\]其中$f_1$表示$x_{j_1}$的领域，$f_2$表示$x_{j_2}$的领域，$w$是一个K维的向量。由此可以看到FFM和FM的方法非常类似，只是对特征向量根据人们的先验知识进行了再次分解。相比较于化简之前的FM算法，FFM并没有在时间复杂度上有所增加，对于空间复杂度来说FFM是$O(nfk)$，不过考虑到FFM已经将向量按照不同的领域进行拆分相应的向量的维度可以所有降低。
不幸的是由于对于不同的$x$使用了不同的$w$，FM中的化简方法并不能应用在FFM中，因此FFM仍然是一个时间复杂度为$O(n^2kf)$的算法，其中$n$是样本平均非零特征数量。
得到以上定义之后接下来就是对损失函数进行求导然后使用梯度下降方法更新参数即可。对于原文这里有个疑问，原文中定义的拟合函数实际上只包含了上文中的特征交叉的部分，并不包含单特征和常量项，如果是这样的话我倒是对这个模型的效果存疑，暂且认为是论文的作者这里疏忽了：）。以下我擅自将单特征和常量项加入：
\[F(x) = w_0 + \sum_{i=1}^{N} w_ix_i + \sum_{j_1=1}^{N} \sum_{j_2=j_1 + 1}^{N} (w_{j_1, f_2} \cdot w_{j_2, f_1})x_{j_1}x_{j_2}\]无论是使用什么输出激活函数以及损失函数最后都会涉及到对上式求偏导，论文中引用的是sigmoid输出之后交叉熵的损失函数的偏导，我这里就不重复了。
PS：这里说明一下，论文中给出的损失函数的化简形式是基于$y \in {1, -1}$的，而我们习惯的用法是$y \in {1, 0}$的，这两个的化简结果是不一样的，没有谁对谁错习惯而已。
- $\frac {\partial F(x)} {\partial w_0} = 1$
- $\frac {\partial F(x)} {\partial w_i} = x_i$
- $\frac {\partial F(x)} {\partial w_{j_1,f_2}} = x_{j_1}x_{j_2}w_{j_2,f_1}$
- $\frac {\partial F(x)} {\partial w_{j_2,f_1}} = x_{j_1}x_{j_2}w_{j_1,f_2}$
讨论
领域知识
以下是本人YY：
对于引入领域知识我是赞成也不赞成，一方面我认为用多个向量来表示一个特征的不同领域是合理的，但是另一方面人为加入的因素越多，对模型自身的普适性和鲁棒性都有一定的影响。
那么换个角度来思考这个问题，本文的出发点是使用多个向量来表示一个特征，那么是否可以让模型自我学习这个目标尼？那么我们可以考虑如果人们先验的提供了一个$F$值表示领域数量但是并不明确的指定某个特征是什么领域的，那么我们可以学习（数学公式写起来太麻烦，直接用tf的函数了）：
1
2
3
4
attMatrix = tf.matmul(wf1, wf2, transpose_b=True)
attWV1 = tf.reduce_sum(tf.softmax(tf.reduce_sum(attMatrix, axis=1, keep_dims=True)) * wv1, axis=0)
attWV2 = tf.reduce_sum(tf.softmax(tf.reduce_sum(attMatrix, axis=0, keep_dims=True)) * wv2, axis=0)
return tf.matmul(attWV1, attWV2, transpose_b=True)
以上方法定义了四个权重：wf1, wf2, wv1, wv2，这四个权重都是一个$F * K$的矩阵其中$F$表示人工指定的领域数量，$K$表示一个领域向量的长度。wf1, wf2两个矩阵用于计算两个输入特征的注意力矩阵，注意这个注意力是有方向的。计算出注意力矩阵之后，根据不同的方向求和然后Softmax分别得到了在wv1, wv2上各个领域的权重。把这个权重member-wise的乘上wv1, wv2然后求和就得到了两个分别融合了所有领域特征的向量。这两个向量再次求点积就得到了一个权重。
注意：以上只是一个表达方式，并非实际的代码，其表示是一对$j_1, j_2$的权重是如何计算的。如果要运行需要用slice或者gather方法来选择正确的部分。
以上方法相当于增加了一倍的权重数量，那么我们可以考虑减少第一步的计算量，也就是减少wf1, wf2的大小。首先其$K$值必须要和wv1, wv2一样。第二，可以考虑用其他的方法而非矩阵相乘的方法来计算注意力矩阵。
Embedding
FFM走到这一步……实际上我觉得应用Feature Embedding之后效果会更好。特征向量化之后两个特征的交集就能非常好的计算了（某种程度上，FM/FFM求出的特征向量已经是一个Embedding结果了）。Embedding的结果经过Dot Product Attention之后求和就可以作为输出的向量，然后再加上一个全联通的输出层就可以了。
深度学习做多了之后思想经常会向这方面拐，深度学习目前看来应用在非常大规模的产品上我认为有两个重要问题需要思考：
- 运行效率，比较深层网络的时间复杂度一般都会比较高的
- 效果稳定性，就我自己的经验来说，对于一些非常特别的输入，偶尔会有不稳定的情况（输出的结果很离谱、又难以追查原因）
但是我认为这仍然是一条值得尝试的道路。之前Youtube发表的那篇论文就挺好的，我接下来有时间写一写那个以及思考一下如何把这个方法应用在实际的工作中。