先来看一下
一、前置
对于一个有m个样本的数据集：$(y_i, x_i)$，i=1,…,m，其中$y_i$是label，$x_i$是一个n维特征向量，模型w通过对下面问题进行最优化求解得到。
\[min \frac{\lambda}{2} \|w\|^2 + \sum_{i=1}^{m} log(1 + exp(-y_i \phi_{LM} (w, x_i)))\]…(1)
其中λ是正则参数，在loss function，如果是线性模型（LM: Linear Model），则：
\[\phi_{LM}(w,x) = w \cdot x\]另外，有两种其它的模型：Poly2和FM。
Poly2(二阶多项式）可以有效捕获特征交叉信息。通过在线性模型上使用二阶的mapping的显式形式，训练和测试时间可以比使用kernel方式更快。这种方法可以学到每个feature pair的weight：
\[\phi_{Poly2}(w,x) = \sum_{j_1=1}^{n} \sum_{j_2=j_1+1}^{n} w_{h(j_1,j_2)} x_{j_1} x_{j_2}\]…(2)
其中$ h(j_1, j_2) $是一个用于将j1和j2编码成一个自然数的函数。计算(2)的复杂度为 $O(\bar{n}^2)$，其中n是每个实例非零元素个数的平均值。
FM则可以为每个feature学到一个隐向量。每个隐向量包含着k个隐因子，其中k是一个用户指定的参数。接着，特征交叉的效果通过两个隐因子进行内积建模而成：
\[\phi_{FM}(w,x) = \sum_{j_1=1}^{n} \sum_{j_2=j_1+1}^{n} (w_{j_1} w_{j_2})\]…(3)
变量数为n x k，直接计算(3)的代价是 $O(\bar{n}^2 k)$。可以进行化简，得到：
\[\phi_{FM}(w,x) = \frac{1}{2} (s - w_j x_j) \cdot w_jx_j\]其中：
\[s = \sum_{j'=1}^{n} w_{j'} x_{j'}\]复杂度可以减少到$ O(\bar{n}k) $.
二、FFM
FFM的idea来自于带有个性化标签的推荐系统中提出的PITF(paper 7)。在PITF中，假设有三种fields：User，Item，Tag，在独立隐空间中对(User, Item), (User, Tag), (Item, Tag)进行因子分解。在paper[8]中，将PITF泛化到更多的fields（比如：AdID, AdvertiserID, UserID, QueryID），并有效地将它应用在CTR预估上。由于 paper[7]的目标是推荐系统，并受限于三个特定的fields（User, Item, Tag），paper[8]在FFM上缺乏详细讨论，在本节中，我们提供了一个更复杂的在CTR预测上的研究。对于大多数像表 1所示的CTR数据集，“features”可以被分组成”fields”中。在我们的示例中，有三个features：ESPN，Vogue，NBC，它们都属于Publisher field；而其它三个features：Nike，Gucci，Adidas，它们都属于Advertiser field。FFM是FM的一个变种，它会利用这些信息。为了解释FFM是如何工作的，我们来看下面的新样本：
1
2
Clicked Publisher(P) Advertiser(A) Gender(G)
Yes ESPN Nike Male
回顾下FM，$ \phi_{FM}(w,x) $ 等于：
\[w_{ESPN} \cdot w_{Nike} + w_{ESPN} \cdot w_{Male} + w_{Nike} \cdot w_{Male}\]在FM中，每个feature都只有一个隐向量（latent vector）来学到与其它任何features的隐式影响。以ESPN为例，$ w_{ESPN} $用于学到与Nike（\(w_{ESPN} \cdot w_{Nike}\)），以及Male（\(w_{ESPN} \cdot w_{Male}\)）的隐式影响（latent effects）。然而，由于Nike和Male属于不同的fields，(ESPN, Nike)和(ESPN, Male)的隐式影响可能是不同的。
在FFM中，每个features具有不同的隐向量（latent vectors）。这取决于其它features的fields，其中之一会被用于做内积。在我们的示例中，$ \phi_{FM}(w,x) $ 为：
\[w_{ESPN,A} \cdot w_{Nike,P} + w_{ESPN,G} \cdot w_{Male,P} + w_{Nike,G} \cdot w_{Male,A}\]我们看到，为了学到(ESPN, Nike)的隐式影响，\(w_{ESPN,A}\)会被使用，因为Nike属于field(Advertiser:A)，同理，\(w_{Nike,P}\) 会被使用，因为ESPN属于field(Publisher:P)。
同理，学了学到(EPSN, Male)的隐因子，\(w_{ESPN,G}\)会被使用，因为Male会属于field（Gender: G）；\(w_{Male,P}\)会被使用，因为ESPN属于field（Publisher: P）。 数学上：
\[\phi_{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}\]…(4)
其中$f_1$和$f_2$各表示$j_1$和$j_2$的fields。如果f是fields的数目，那么FFM的变量数目为$ \bar{n}fk $，计算公式(4)的复杂度为$ O(\bar{n}^2 k) $。在FFM中，由于每个隐向量只需要学到一个特定field的影响，通常：
\[k_{FFM} \ll k_{FM}\]表2比较了不同模型的变量数和计算复杂度。
三、求解最优化问题
FFM的最优化问题与LM相似。这里使用的是SG方法（stochastic gradient）。最近，一些adaptive learning-rate方法有提出：AdaGrad等。使用AdaGrad是因为它对于矩阵因子分解（包括FFM）很有效。
在SG的每一个step中，会抽样一个数据点(y,x) 来更新 $ w_{j_1,f_2}$和$ w_{j_2,f_1}$。注意，由于x在我们的应用中高度稀疏，我们只会使用非零值来更新维度（dimensions）。首先，子梯度（sub-gradients）为：
\[g_{j_1,f_2} \equiv \delta_{w_{j_1,f_2}} f(w)=\lambda \cdot w_{j_1,f_2} + k \cdot w_{j_2,f_1} x_{j_1} x_{j_2}\]…(5)
\[g_{j_2,f_1} \equiv \delta_{w_{j_2,f_1}} f(w)= \lambda \cdot w_{j_2,f_1} + k \cdot w_{j_1,f_2} x_{j_1} x_{j_2}\]…(6)
其中:
\[k = \frac {\partial log(1+exp(-y \phi_{FFM}(w,x)))}{\partial \phi_{FFM} (w,x)} = \frac{-y} {1+exp(y \phi_{FFM}(w,x))}\]接着，对于每个坐标 d=1,…,k，梯度平方和会进行如下累积：
\[(G_{j_1,f_2})_d \leftarrow (G_{j_1,f_2})_d + (g_{j_1,f_2})_d^2\]…(7)
\[(G_{j_2,f_1})_d \leftarrow (G_{j_2,f_1})_d + (g_{j_2,f_1})_d^2\]…(8)
最终，$ (w_{j_1,f_2})d$和$ (w{j_2,f_1})_d$会进行如下更新：
\[(w_{j_1,f_2})_d \leftarrow (w_{j_1,f_2})_d - \frac{\eta}{\sqrt{(G_{j_1,f_2})_d}} (g_{j_1,f_2})_d\]…(9)
\[(w_{j_2,f_1})_d \leftarrow (w_{j_2,f_1})_d - \frac{\eta}{\sqrt{(G_{j_2,f_1})_d}} (g_{j_2,f_1})_d\]…(10)
其中$\eta$是一个用户指定的learning-rate。w的初始值从一个在$[0, 1/\sqrt{k}]$间的均匀分布中进行随机抽样。G的初始值被设置成1以便于阻止一个关于$ (G_{j_1,f_2})_d^{\frac{1}{2}}$大值。整个过程如算法1所示。
经验中，我们发现归一化每个实例到单位长度上，可以让accuracy稍好，对参数更不敏感些。
3.2 共享内存系统上进行并行化
现代计算机基本都采用多核CPUs。如果这些核能被充分利用，训练时间可以极大缩短。许多SG的并行方法被提出。在这paper中，我们应用HOG-WILD!，它允许每个线程独立运行，没有任何锁。特别的，在算法1中的第3行的for循环是并行的。
3.3 增加Field信息
考虑到我们使用的是LIBSVM的数据格式：
1
label feat1:val1 feat2:val2 · · ·
其中每个(feat,val)pair 表示特征index和value。对于FFM，我们扩展了以上的格式：
1
label field1:feat1:val1 field2:feat2:val2 · · ·
也就是说，我们必须为每个feature分配一个对应的field。这种分配在某些类型的特征上很容易，但是在另外一些类型的特征上不太容易。这里讨论了三种类型。
Categorical Features
对于线性模型，一个categorical feature常以被转换成一些二值特征。对于一个数据实例：
1
Yes P:ESPN A:Nike G:Male
我们生成了它的Libsvm格式：
1
Yes P-ESPN:1 A-Nike:1 G-Male:1
注意，对应于在一个categorical feature中可能值的数目，会生成相同数目的二值特征，每次只有其中之一会具有值1。在Libsvm格式中，零值的features不会被存储。我们将这种setting应用到所有模型中。为了添加field信息，我们可以将每个category看成是一个field。以上的实例就变成了：
1
Yes P:P-ESPN:1 A:A-Nike:1 G:G-Male:1
Numerical Features
考虑到以下的示例是预测一个paper是否会被某会议接收。我们使用三种数值型特征：“会议接收率：accept rate of the conference (AR),”“作者的h-index：h-index of the author (Hidx),” and “作者的引用数：number of citations of the author (Cite):”.
1
2
3
Accepted AR Hidx Cite
Yes 45.73 2 3
No 1.04 100 50000
这里有两种可能的方式来分配fields。一种自然的方式是，将每个feature看成是一个dummy field，因而生成的数据是：
1
Yes AR:AR:45.73 Hidx:Hidx:2 Cite:Cite:3
然而，该dummy fields可能没有任何信息量，因为它们仅仅只是特征的复制。
另一个可能的方式是，对每个数值型特征离散化成一个类别型特征。接着我们使用和categorical features相同的setting来添加field信息。生成的数据如下：
1
Yes AR:45:1 Hidx:2:1 Cite:3:1
其中，AR特征被归整(round)为一个整数。主要的缺点是，通常决定最好的离散化设置并不容易。例如，我们可能将45.73转化成: 45.7, 45, 40, 或者 int(log(45.73))。另外，我们会在离散化后失去一些信息。
single-field features
在一些数据集上，所有的features都属于单个field，因而，为它分配一个field是无意义的。通常该情况发生在NLP数据集中。考虑到以下示例：预测一个句子表达是好心情，还是坏心情。
1
2
3
good mood sentence
Yes Hooray! Our paper is accepted!
No Well, our paper is rejected.
在该例中，只有一个field：“sentence”。如果我们为所有的words分配一个field，那么FFM就成了FM。读者们可能会问到可以分配类似numerical features的dummy field。回顾下FFM的model size为：O(nfk)。使用dummy fields不实际，因为f=n，n通常很大。
4.实验
详见paper。