点击率预估算法：FM与FFM

点击率预估算法：FFM

@(计算广告)[计算广告]

• 点击率预估算法FFM
• 1FM
  • 1 背景
    • 11 线性模型
  • 12 二项式模型
  • 2 FM
    • 21 FM基本原理
    • 22 数据分析
    • 23参数个数
    • 24 计算时间复杂度
    • 25 梯度
    • 26 训练时间复杂度
• 2FFM
  • 1 背景及基本原理
  • 2模型与最优化问题
    • 21 模型
    • 22 最优化问题
    • 23 自适应学习率
    • 24 FFM算法的最终形式
  • 3完整算法流程
    • 31 计算梯度
    • 32 计算累积梯度平方和
    • 33 更新隐变量
    • 34 关于初始参数的设定
  • 4 时间复杂度
    • 41 计算时间复杂度
    • 42 训练时间复杂度
  • 5 计算速度优化
    • 51 openMP
    • 52 SSE3
    • 53 ParameterServer
  • 6模型优化
    • 61 特征编码连续
    • 62 一次项缺失的影响
    • 63 样本归一化
    • 64 特征归一化

完整代码见：https://github.com/lujinhong/ffm

1、FM

1.1 背景

1.1.1 线性模型

常见的线性模型，比如线性回归、逻辑回归等，它只考虑了每个特征对结果的单独影响，而没有考虑特征间的组合对结果的影响。

对于一个有n维特征的模型，线性回归的形式如下：

\begin{aligned}
f(x) &= \omega_0 + \omega_1x_1+\omega_2x_2+...+\omega_nx_n  \\
&=\omega_0+\sum_{i=1}^n{\omega_ix_i}
\tag{1}
\end{aligned}$$\text{begin{aligned}f(x) \&= omega\_0 + omega\_1x\_1+omega\_2x\_2+...+omega\_nx\_n \&=omega\_0+sum\_{i=1}^n{omega\_ix\_i}tag{1}end{aligned}}$$

其中(ω0,ω1...ωn)$({\omega }_0,{\omega }_1...{\omega }_n)$为模型参数，(x1,x2...xn)$(x_1,x_2...x_n)$为特征。
从(1)式可以看出来，模型的最终计算结果是各个特征的独立计算结果，并没有考虑特征之间的相互关系。

举个例子，我们“USA”与”Thanksgiving”，”China”与“Chinese new year”这样的组合特征是很有意义的，在这样的组合特征下，会对某些商品表现出更强的购买意愿，而单独考虑国家及节日都是没有意义的。

1.1.2 二项式模型

我们在（1）式的基础上，考虑任意2个特征分量之间的关系，得出以下模型：

f(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1nωijxixj(2)$$\begin{array}{}\text{(2)}& f(x)={\omega }_0+\sum _{i=1}^n{\omega }_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n{\omega }_{ij}{x}_i{x}_j\end{array}$$

这个模型考虑了任意2个特征分量之间的关系，但并未考虑更高阶的关系。
模型涉及的参数数量为：

1+n+n(n−1)2=12(n2+n+2)(3)$$\begin{array}{}\text{(3)}& 1+n+\frac{n(n-1)}{2}=\frac{1}{2}(n^2+n+2)\end{array}$$

对于参数ωi${\omega }_i$的训练，只要这个样本中对应的xi$x_i$不为0，则可以完成一次训练。
但对于参数ωij${\omega }_{ij}$的训练，需要这个样本中的xi$x_i$和xj$x_j$同时不为0，才可以完成一次训练。
在数据稀疏的实际应用场景中，二次项ωij${\omega }_{ij}$的训练是非常困难的。因为每个ωij${\omega }_{ij}$都需要大量xi$x_i$和xj$x_j$都不为0的样本。但在数据稀疏性比较明显的样本中，xi$x_i$和xj$x_j$都不为0的样本会非常稀少，这会导致ωij${\omega }_{ij}$不能得到足够的训练，从而不准确。

1.2 FM

1.2.1 FM基本原理

为了解决上述由于数据稀疏引起的训练不足的问题，我们为每个特征维度xi$x_i$引入一个辅助向量：

Vi=(vi1,vi2,vi3,...,vik)T∈ℝk,i=1,2,3,...,n(4)$$\begin{array}{}\text{(4)}& V_i=(v_{i1},v_{i2},v_{i3},...,v_{ik}{)}^T\in {\mathbb{R}}^k,i=1,2,3,...,n\end{array}$$

其中k为辅助变量的维度，依经验而定，一般而言，对于特征维度足够多的样本，k<

1.2.2 数据分析

我们的目标是要求得以下交互矩阵W：

W=⎛⎝⎜⎜⎜⎜ω11ω21⋮ωn1ω12ω22⋮ωn2......⋱...ω1nω2n⋮ωnn⎞⎠⎟⎟⎟⎟n×n(7)$$\begin{array}{}\text{(7)}& W={\left(\begin{array}{cccc}{\omega }_{11}& {\omega }_{12}& ...& {\omega }_{1n}\\ {\omega }_{21}& {\omega }_{22}& ...& {\omega }_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ {\omega }_{n1}& {\omega }_{n2}& ...& {\omega }_{nn}\end{array}\right)}_{n\times n}\end{array}$$

由于直接求解W不方便，因此我们引入隐变量V：

V=⎛⎝⎜⎜⎜⎜v11v21⋮vn1v12v22⋮vn2......⋱...v1kv2k⋮vnk⎞⎠⎟⎟⎟⎟n×k=⎛⎝⎜⎜⎜⎜VT1VT2⋯VTn⎞⎠⎟⎟⎟⎟(8)$$\begin{array}{}\text{(8)}& V={\left(\begin{array}{cccc}{v}_{11}& v_{12}& ...& v_{1k}\\ v_{21}& v_{22}& ...& v_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ v_{n1}& v_{n2}& ...& v_{nk}\end{array}\right)}_{n\times k}=\left(\begin{array}{c}{V}_1^T\\ V_2^T\\ \cdots \\ V_n^T\end{array}\right)\end{array}$$

令

VVT=W(9)$$\begin{array}{}\text{(9)}& V{V}^T=W\end{array}$$

如果我们先得到V，则可以得到W了。
现在只剩下一个问题了，是否一个存在V，使得上述式（9）成立。
理论研究表明：当k足够大时，对于任意对称正定的实矩阵W∈ℝn×n$W\in {\mathbb{R}}^{n\times n}$，均存在实矩阵V∈ℝn×k$V\in {\mathbb{R}}^{n\times k}$，使得W=VVT$W=V{V}^T$。

理论分析中要求参数k足够的大，但在高度稀疏数据的场景中，由于 没有足够的样本，因此k通常取较小的值。事实上，对参数k的限制，在一定程度上可以提高模型的泛化能力。

1.2.3参数个数

假设样本中有n个特征，每个特征对应的隐变量维度为k，则参数个数为1+n+nk。
正如上面所言，对于特征维度足够多的样本，k<

1.2.4 计算时间复杂度

下面我们分析一下已经知道所有参数，代入式（6）计算预测值时的时间复杂度。从式（6）中一看，

f(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1n(VTiVj)xixj(6)$$\begin{array}{}\text{(6)}& f(x)={\omega }_0+\sum _{i=1}^n{\omega }_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n(V_i^T{V}_j)x_i{x}_j\end{array}$$

可以看出时间复杂度是O(kn2)$O(k{n}^2)$。但我们对上述式子的最后一项作变换后，可以得出一个O(kn)的时间复杂度表达式。

\begin{aligned}
\sum_{i=1}^{n-1}\sum_{j=i+1}^n(V_i^TV_j)x_ix_j 
&= \frac{1}{2}\left(\sum_{i=1}^n\sum_{j=1}^n(V_i^TV_j)x_ix_j-\sum_{i=1}^n(V_i^TV_i)x_ix_i\right)\\
&=\frac{1}{2}\left(\sum_{i=1}^n\sum_{j=1}^n\sum_{l=1}^kv_{il}v_{jl}x_ix_j-\sum_{i=1}^n\sum_{l=1}^k v_{il}^2x_i^2\right)\\\
&=\frac{1}{2}\sum_{l=1}^k\left(\sum_{i=1}^n(v_{il}x_i)\sum_{j=1}^n(v_{jl}x_j)-\sum_{i=1}^nv_{il}^2x_i^2\right)\\
&=\frac{1}{2}\sum_{l=1}^k\left(\left(\sum_{i=1}^n(v_{il}x_i)\right)^2-\sum_{i=1}^nv_{il}^2x_i^2\right)\\
\tag{10}
\end{aligned}$$\text{begin{aligned}sum\_{i=1}^{n-1}sum\_{j=i+1}^n(V\_i^TV\_j)x\_ix\_j \&= frac{1}{2}left(sum\_{i=1}^nsum\_{j=1}^n(V\_i^TV\_j)x\_ix\_j-sum\_{i=1}^n(V\_i^TV\_i)x\_ix\_iright)\&=frac{1}{2}left(sum\_{i=1}^nsum\_{j=1}^nsum\_{l=1}^kv\_{il}v\_{jl}x\_ix\_j-sum\_{i=1}^nsum\_{l=1}^k v\_{il}^2x\_i^2right)\&=frac{1}{2}sum\_{l=1}^kleft(sum\_{i=1}^n(v\_{il}x\_i)sum\_{j=1}^n(v\_{jl}x\_j)-sum\_{i=1}^nv\_{il}^2x\_i^2right)\&=frac{1}{2}sum\_{l=1}^kleft(left(sum\_{i=1}^n(v\_{il}x\_i)right)^2-sum\_{i=1}^nv\_{il}^2x\_i^2right)tag{10}end{aligned}}$$

上述式子中的∑ni=1(vilxi)$\sum _{i=1}^n(v_{il}{x}_i)$只需要计算一次就好，因此，可以看出上述模型的复杂度为O(kn)。
也就是说我们不要直接使用式（6）来计算预测结果，而应该使用式（10），这样的计算效率更高。

1.2.5 梯度

FM有一个重要的性质：multilinearity：若记Θ=(ω0,ω1,ω2,...,ωn,v11,v12,...,vnk)$\mathrm{\Theta }=({\omega }_0,{\omega }_1,{\omega }_2,...,{\omega }_n,v_{11},v_{12},...,v_{nk})$表示FM模型的所有参数，则对于任意的θ∈Θ$\theta \in \mathrm{\Theta }$，存在与θ$\theta$无关的g(x)$g(x)$与h(x)$h(x)$，使得式（6）可以表示为：

f(x)=g(x)+θh(x)(11)$$\begin{array}{}\text{(11)}& f(x)=g(x)+\theta h(x)\end{array}$$

从式（11）中可以看出，如果我们得到了g(x)$g(x)$与h(x)$h(x)$，则对于参数θ$\theta$的梯度为h(x)$h(x)$。下面我们分情况讨论。
* 当 θ=ω0$\theta ={\omega }_0$时，式（6）可以表示为：

f(x)=∑i=1nωixi+∑i=1n−1∑j=i+1n(VTiVj)xixj+ω0×1(12)$$\begin{array}{}\text{(12)}& f(x)=\sum _{i=1}^n{\omega }_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n(V_i^T{V}_j)x_i{x}_j+{\omega }_0\times 1\end{array}$$

上述中的蓝色表示g(x)$g(x)$，红色表示h(x)$h(x)$。下同。
从上述式子可以看出此时的梯度为1.

• 当θ=ωl,l∈(1,2,...,n)$\theta ={\omega }_l,l\in (1,2,...,n)$时，
  

  f(x)=ω0+∑i=1i≠lnωixi+∑i=1n−1∑j=i+1n(VTiVj)xixj+ωl×xl(13)$$\begin{array}{}\text{(13)}& f(x)={\omega }_0+\sum _{\begin{array}{c}i=1\\ i\ne l\end{array}}^n{\omega }_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n(V_i^T{V}_j)x_i{x}_j+{\omega }_l\times x_l\end{array}$$
  
  此时梯度为xl$x_l$。

• 当θ=vlm$\theta =v_{lm}$时
  

  f(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1n(∑s=1is≠lmjs≠lmkvisvjs)xixj+vlm×xl∑i=1i≠lnvimxi$$f(x)={\omega }_0+\sum _{i=1}^n{\omega }_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n(\sum _{\begin{array}{c}s=1\\ is\ne lm\\ js\ne lm\end{array}}^k{v}_{is}{v}_{js})x_i{x}_j+v_{lm}\times x_l\sum _{\begin{array}{c}i=1\\ i\ne l\end{array}}^n{v}_{im}{x}_i$$
  
  此时梯度为xl∑i≠lvimxi$x_l\sum _{i\ne l}{v}_{im}{x}_i$.

综合上述结论，f(x)$f(x)$关于θ$\theta$的偏导数为：

∂f(x)∂θ=⎧⎩⎨⎪⎪1,xl,xl∑ni=1i≠lvimxiθ=ω0θ=ωl,l∈(1,2,...,n)θ=vlm(15)$$\begin{array}{}\text{(15)}& \frac{\mathrm{\partial }f(x)}{\mathrm{\partial }\theta }=\{\begin{array}{ll}1,& \theta ={\omega }_0\\ x_l,& \theta ={\omega }_l,l\in (1,2,...,n)\\ x_l\sum _{\begin{array}{c}i=1\\ i\ne l\end{array}}^n{v}_{im}{x}_i& \theta =v_{lm}\end{array}\end{array}$$

1.2.6 训练时间复杂度

由上述式（15）可以得到：

xl∑i=1i≠lnvimxi=xl∑i=1nvimxi−vlmx2l(16)$$\begin{array}{}\text{(16)}& x_l\sum _{\begin{array}{c}i=1\\ i\ne l\end{array}}^n{v}_{im}{x}_i=x_l\sum _{i=1}^n{v}_{im}{x}_i-v_{lm}{x}_l^2\end{array}$$

对于上式中的前半部分∑ni=1vimxi$\sum _{i=1}^n{v}_{im}{x}_i$，对于每个样本只需要计算一次，所以时间复杂度为O(n)，对于k个隐变量的维度分别计算一次，则复杂度为O(kn)。其它项的时间复杂度都小于这一项，因此，模型训练的时间复杂度为O(kn)。

详细一点解释：
（1）我们首先计算∑ni=1vimxi$\sum _{i=1}^n{v}_{im}{x}_i$，时间复杂度为n，这个值对于所有特征对应的隐变量的某一个维度是相同的。我们设这值为C。
（2）计算每一个特征对应的xl∑ni=1vimxi−vlmx2l=Cxl−vlmx2l$x_l\sum _{i=1}^n{v}_{im}{x}_i-v_{lm}{x}_l^2=C{x}_l-v_{lm}{x}_l^2$，由于总共有n个特征，因此时间复杂度为n，至此，总的时间复杂度为n+n。
（3）上述只是计算了隐变量的其中一个维度，我们总共有k个维度，因此总的时间复杂度为k(n+n)=O(kn)$k(n+n)=O(kn)$.

2、FFM

2.1 背景及基本原理

在FM模型中，每一个特征会对应一个隐变量，但在FFM模型中，认为应该将特征分为多个field，每个特征对应每个field分别有一个隐变量。

举个例子，我们的样本有3种类型的字段：publisher, advertiser, gender，分别可以代表媒体，广告主或者是具体的商品，性别。其中publisher有5种数据，advertiser有10种数据，gender有男女2种，经过one-hot编码以后，每个样本有17个特征，其中只有3个特征非空。

如果使用FM模型，则17个特征，每个特征对应一个隐变量。
如果使用FFM模型，则17个特征，每个特征对应3个隐变量，即每个类型对应一个隐变量，具体而言，就是对应publisher, advertiser, gender三个field各有一个隐变量。

2.2模型与最优化问题

2.2.1 模型

根据上面的描述，可以得出FFM的模型为：

f(x)=ω0+∑i=1nωixi+∑j1=1n−1∑j2=i+1n(VTj1,f2Vj2,f1)xj1xj2(17)$$\begin{array}{}\text{(17)}& f(x)={\omega }_0+\sum _{i=1}^n{\omega }_i{x}_i+\sum _{j1=1}^{n-1}\sum _{j2=i+1}^n(V_{j1,f2}^T{V}_{j2,f1})x_{j1}{x}_{j2}\end{array}$$

其中j1,j2$j1,j2$表示特征的索引。我们假设j1$j1$特征属于f1$f1$这个field，j2$j2$特征属于f2$f2$这个field，则Vj1,f2$V_{j1,f2}$表示j1$j1$这个特征对应f2$f2$(j2$j2$所属的field)的隐变量，同时Vj2,f1$V_{j2,f1}$表示j2$j2$这个特征对应f1$f1$(j1$j1$所属的field)的隐变量。

事实上，在大多数情况下，FFM模型只保留了二次项，即：

ϕ(V,x)=∑j1=1n−1∑j2=i+1n(VTj1,f2Vj2,f1)xj1xj2(18)$$\begin{array}{}\text{(18)}& \varphi (V,x)=\sum _{j1=1}^{n-1}\sum _{j2=i+1}^n(V_{j1,f2}^T{V}_{j2,f1})x_{j1}{x}_{j2}\end{array}$$

2.2.2 最优化问题

根据逻辑回归的损失函数及分析，可以得出FFM的最优化问题为：

minλ2||V||22+∑i=1mlog(1+exp(−yiϕ(V,x)))(19)$$\begin{array}{}\text{(19)}& min\frac{\lambda }{2}||V|{|}_2^2+\sum _{i=1}^m\log (1+exp(-y_i\varphi (V,x)))\end{array}$$

上面加号的前面部分使用了L2范式，后面部分是逻辑回归的损失函数。m表示样本的数量，yi$y_i$表示训练样本的真实值（如是否点击的-1/1），ϕ(V,x)$\varphi (V,x)$表示使用当前的V代入式（18）计算得到的值。

注意，以上的损失函数适用于样本分布为{-1,1}的情况。

2.2.3 自适应学习率

与FTRL一样，FFM也使用了累积梯度作为学习率的一部分，即：

Vj1,f2=Vj1,f2−η1+∑t(gtvj1,f2)2‾‾‾‾‾‾‾‾‾‾‾‾‾√gvj1,f2(20)$$\begin{array}{}\text{(20)}& V_{j1,f2}=V_{j1,f2}-\frac{\eta }{\sqrt{1+\sum _t(g_{v_{j1,f2}}^t{)}^2}}{g}_{v_{j1,f2}}\end{array}$$

其中gvj1,f2$g_{v_{j1,f2}}$表示对于Vj1,f2$V_{j1,f2}$这个变量的梯度向量，因为Vj1,f2$V_{j1,f2}$是一个向量，因此gvj1,f2$g_{v_{j1,f2}}$也是一个向量，尺寸为隐变量的维度大小，即k。
而∑t(gtvj1,f2)2$\sum _t(g_{v_{j1,f2}}^t{)}^2$表示从第一个样本到当前样本一直以来的累积梯度平方和。

2.2.4 FFM算法的最终形式

(Vj1,f2)d=(Vj1,f2)d−1−η(Gj1,f2)d‾‾‾‾‾‾‾‾√⋅(gj1,f2)d(Vj2,f1)d=(Vj2,f1)d−1−η(Gj2,f1)d‾‾‾‾‾‾‾‾√⋅(gj2,f1)d$$\begin{gathered} (V_{j1,f2}{)}_d=(V_{j1,f2}{)}_{d-1}-\frac{\eta }{\sqrt{(G_{j1,f2}{)}_d}}\cdot (g_{j1,f2}{)}_d \\ (V_{j2,f1}{)}_d=(V_{j2,f1}{)}_{d-1}-\frac{\eta }{\sqrt{(G_{j2,f1}{)}_d}}\cdot (g_{j2,f1}{)}_d \end{gathered}$$

其中G为累积梯度平方：

(Gj1,f2)d=(Gj1,f2)d−1+(gj1,f2)2d(Gj2,f1)d=(Gj2,f1)d−1+(gj2,f1)2d$$\begin{gathered} (G_{j1,f2}{)}_d=(G_{j1,f2}{)}_{d-1}+(g_{j1,f2}{)}_d^2 \\ (G_{j2,f1}{)}_d=(G_{j2,f1}{)}_{d-1}+(g_{j2,f1}{)}_d^2 \end{gathered}$$

g为梯度，比如gj1,f2$g_{j1,f2}$为j1$j1$这个特征对应f2$f2$这个field的梯度向量：

gji,f2=λ⋅Vji,f2+κ⋅Vj2,f1gj2,f1=λ⋅Vj2,f1+κ⋅Vj1,f2$$\begin{gathered} g_{ji,f2}=\lambda \cdot V_{ji,f2}+\kappa \cdot V_{j2,f1} \\ {g}_{j2,f1}=\lambda \cdot V_{j2,f1}+\kappa \cdot V_{j1,f2} \end{gathered}$$

其中κ$\kappa$为：

κ=∂log(1+exp(−yiϕ(V,x)))∂ϕ(V,x)=−y1+exp(yϕ(V,x))$$\kappa =\frac{\mathrm{\partial }\log (1+exp(-y_i\varphi (V,x)))}{\mathrm{\partial }\varphi (V,x)}=\frac{-y}{1+\exp (y\varphi (V,x))}$$

2.3完整算法流程

使用随机梯度下降（SGD）训练FFM模型的完整过程如下：

2.3.1 计算梯度

对于每一个样本的每一对特征组合都要计算以下梯度向量。

gji,f2=λ⋅Vji,f2+κ⋅Vj2,f1gj2,f1=λ⋅Vj2,f1+κ⋅Vj1,f2(21)$$\begin{gathered} \begin{array}{}\text{(21)}& g_{ji,f2}=\lambda \cdot V_{ji,f2}+\kappa \cdot V_{j2,f1} \\ {g}_{j2,f1}=\lambda \cdot V_{j2,f1}+\kappa \cdot V_{j1,f2}\end{array} \end{gathered}$$

其中κ$\kappa$为式(19)后半部分对应的梯度，即：

κ=∂log(1+exp(−yiϕ(V,x)))∂ϕ(V,x)=−y1+exp(yϕ(V,x))(22)$$\begin{array}{}\text{(22)}& \kappa =\frac{\mathrm{\partial }\log (1+exp(-y_i\varphi (V,x)))}{\mathrm{\partial }\varphi (V,x)}=\frac{-y}{1+\exp (y\varphi (V,x))}\end{array}$$

再重申一次，g$g$与V$V$都是k维的向量，在python中可以作为一个向量计算，在java/c++等需要通过一个循环进行计算。

详细推导（21）式如下：
（1）在SGD中，式（19）可以转化为：

minλ2||V||22+log(1+exp(−yiϕ(V,x)))(23)$$\begin{array}{}\text{(23)}& min\frac{\lambda }{2}||V|{|}_2^2+\log (1+exp(-y_i\varphi (V,x)))\end{array}$$

（2）上式对Vj1,f2$V_{j1,f2}$求偏导，可得：

\begin{aligned}
&\frac{\partial \frac{\lambda}{2}||V||_2^2+\log(1+exp(-y_i\phi(V,x)))}{\partial V_{j1,f2}} \\
&=\lambda \cdot V_{j1,f2} + \frac{\partial \log(1+exp(-y_i\phi(V,x)))}{\partial V_{j1,f2}}\\
&=\lambda \cdot V_{j1,f2} + \frac{\partial \log(1+exp(-y_i\phi(V,x)))}{\partial \phi} \cdot  \frac{\partial \phi}{V_{j1,f2}}\\
&=\lambda \cdot V_{j1,f2} + \frac{-y}{1+\exp(y\phi(V,x) )}  \cdot V_{j2,f1}
\tag{24}
\end{aligned}$$\text{begin{aligned}\&frac{partial frac{lambda}{2}||V||\_2^2+log(1+exp(-y\_iphi(V,x)))}{partial V\_{j1,f2}} \&=lambda cdot V\_{j1,f2} + frac{partial log(1+exp(-y\_iphi(V,x)))}{partial V\_{j1,f2}}\&=lambda cdot V\_{j1,f2} + frac{partial log(1+exp(-y\_iphi(V,x)))}{partial phi} cdot frac{partial phi}{V\_{j1,f2}}\&=lambda cdot V\_{j1,f2} + frac{-y}{1+exp(yphi(V,x) )} cdot V\_{j2,f1}tag{24}end{aligned}}$$

2.3.2 计算累积梯度平方和

计算从第一个样本，到当前样本（第d个）以来的累积梯度平方和：

(Gj1,f2)d=(Gj1,f2)d−1+(gj1,f2)2d(Gj2,f1)d=(Gj2,f1)d−1+(gj2,f1)2d(25)$$\begin{gathered} \begin{array}{}\text{(25)}& (G_{j1,f2}{)}_d=(G_{j1,f2}{)}_{d-1}+(g_{j1,f2}{)}_d^2 \\ (G_{j2,f1}{)}_d=(G_{j2,f1}{)}_{d-1}+(g_{j2,f1}{)}_d^2\end{array} \end{gathered}$$

2.3.3 更新隐变量

(Vj1,f2)d=(Vj1,f2)d−1−η(Gj1,f2)d‾‾‾‾‾‾‾‾√⋅(gj1,f2)d(Vj2,f1)d=(Vj2,f1)d−1−η(Gj2,f1)d‾‾‾‾‾‾‾‾√⋅(gj2,f1)d(26)$$\begin{gathered} \begin{array}{}\text{(26)}& (V_{j1,f2}{)}_d=(V_{j1,f2}{)}_{d-1}-\frac{\eta }{\sqrt{(G_{j1,f2}{)}_d}}\cdot (g_{j1,f2}{)}_d \\ (V_{j2,f1}{)}_d=(V_{j2,f1}{)}_{d-1}-\frac{\eta }{\sqrt{(G_{j2,f1}{)}_d}}\cdot (g_{j2,f1}{)}_d\end{array} \end{gathered}$$

2.3.4 关于初始参数的设定

文献1中如此建议：
（1）η$\eta$：没有具体的建议，用户根据经验指定即可，一般会取0.1，0.01，0.001。
（2）V$V$：在区间[0,1/k√]$[0,1/\sqrt{k}]$间的随机值，均匀分布即可。
（3）G$G$：设置为1，以避免(Gj1,f2)−12d$(G_{j1,f2}{)}_d^{-\frac{1}{2}}$出现很大的值。

2.4 时间复杂度

2.4.1 计算时间复杂度

由于式(18)无法做类似于式（10）的简化，因此FFM的计算时间复杂度为O(kn2)$O(k{n}^2)$。

2.4.2 训练时间复杂度

由于训练时，需要先根据式（18）计算ϕ$\varphi$，复杂度为O(kn2)$O(k{n}^2)$，计算得到ϕ$\varphi$后，还需要按照式（22）计算1次，按照式（21）计算2k次，按照式（23）计算2k次，按照式（24）计算2k次，也就是说，总的训练时间复杂度为：

O(kn2)+1+2k+2k+2k=O(kn2)$$O(k{n}^2)+1+2k+2k+2k=O(k{n}^2)$$

因此，训练时间复杂度为O(kn2)$O(k{n}^2)$。

2.5 计算速度优化

2.5.1 openMP

OpenMP提供的这种对于并行描述的高层抽象降低了并行编程的难度和复杂度，这样程序员可以把更多的精力投入到并行算法本身，而非其具体实现细节。对基于数据分集的多线程程序设计，OpenMP是一个很好的选择。同时，使用OpenMP也提供了更强的灵活性，可以较容易的适应不同的并行系统配置。线程粒度和负载平衡等是传统多线程程序设计中的难题，但在OpenMP中，OpenMP库从程序员手中接管了部分这两方面的工作。

openPM原生支持C/C++/Fortran，但java可以通过jomp等引入，未测试。

2.5.2 SSE3

。SSE3 中13个新指令的主要目的是改进线程同步和特定应用程序领域，例如媒体和游戏。这些新增指令强化了处理器在浮点转换至整数、复杂算法、视频编码、SIMD浮点寄存器操作以及线程同步等五个方面的表现，最终达到提升多媒体和游戏性能的目的。Intel是从Prescott核心的Pentium 4开始支持SSE3指令集的，而AMD则是从2005年下半年Troy核心的Opteron开始才支持SSE3的。但是需要注意的是，AMD所支持的SSE3与Intel的SSE3并不完全相同，主要是删除了针对Intel超线程技术优化的部分指令。
SSE3指令采用128位的寄存器，可以同时操作4个单精度浮点数或者整数，因此非常类似于向量运算。这对于有大量向量计算的的FFM模型是有用的。
但事实上，计算ϕ$\varphi$是几乎无用，而这是最耗时间的部分。

2.5.3 ParameterServer

https://www./Dounm/note/517675
Paraeter Server框架中，每个server都只负责分到的部分参数（server共同维持一个全局共享参数）。server节点可以和其他server节点通信，每个server负责自己分到的参数，server group共同维持所有参数的更新。server manage node负责维护一些元数据的一致性，例如各个节点的状态，参数的分配情况。

2.6模型优化

2.6.1 特征编码连续

如果特征的编码不连续，比如编码是有意义的，或者预留空间给之后的编码。如果直接使用最大编码值的作为参数数据尺寸，则会导致大量内存空间的浪费，因此有2种解决方案：
（1）使用hashmap，而非数组。
（2）将有意义的编码映射到一个连续的编码空间。
目前我们使用方式（1），理论上方式（2）的计算速度会更快。

2.6.2 一次项缺失的影响

正如上面式（18）所言，我们经常会忽略了一次项的影响，因此我们可以为每个样本加上一个辅助特征，这相特征的值恒为1，这相当于引入了一次项。

另一种更常规的方法是直接作为一次项的逻辑回归来作训练。

2.6.3 样本归一化

文献1还建议，将样本向量的长度归一化后，性能有少量的提升。

R[i]=1||X||$$R[i]=\frac{1}{||X||}$$

2.6.4 特征归一化

某些特征（如购买个数）有可能很大，而一些类别参数则恒为1，这将导致不同特征最终对模型的影响相关很大，这很不合理。

完整代码见：https://github.com/lujinhong/ffm