【fm2018球员编号】点击率预估算法：FM与FFM

点击率预测算法：FFM

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

点击率预测算法FFM1FM1背景11线性模型12二项模型2 FM21 FM基本原理22数据分析23参数数24计算时间复杂性25斜率26训练时间复杂性2FFM1背景和基本原理2模型和优化问题21模型22优化问题23自适应学习率24 FFM算法的最终形式3整个算法过程31计算梯度32累计梯度平方和33更新隐藏变量34初始参数设置信息4小时复杂性41计算时间复杂性42训练时间复杂性5计算速度优化51 Openmp 52 SSE 353 Parameter Server 6模型优化61特征代码连续62次缺失影响63样本规范化64特征规范化完整代码参考：

1、调频

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}\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)为模型参数，(x

...x

)

(x1,x2...xn)为特征。

从(1)式可以看出来，模型的最终计算结果是各个特征的独立计算结果，并没有考虑特征之间的相互关系。举个例子，我们“USA”与”Thanksgiving”，”China”与“Chinese new year”这样的组合特征是很有意义的，在这样的组合特征下，会对某些商品表现出更强的购买意愿，而单独考虑国家及节日都是没有意义的。

1.1.2 二项式模型

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

f(x)=ω

+∑

i=1

+∑

i=1

n−1

∑

j=i+1

(2)

(2)f(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1nωijxixj

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

模型涉及的参数数量为：

1+n+n(n−1)

+n+2)

(3)

(3)1+n+n(n−1)2=12(n2+n+2)

对于参数ω

ωi的训练，只要这个样本中对应的x

xi不为0，则可以完成一次训练。

但对于参数ω

ωij的训练，需要这个样本中的x

xi和x

xj同时不为0，才可以完成一次训练。

在数据稀疏的实际应用场景中，二次项ω

ωij的训练是非常困难的。因为每个ω

ωij都需要大量x

xi和x

xj都不为0的样本。但在数据稀疏性比较明显的样本中，x

xi和x

xj都不为0的样本会非常稀少，这会导致ω

ωij不能得到足够的训练，从而不准确。

1.2 FM

1.2.1 FM基本原理

为了解决上述由于数据稀疏引起的训练不足的问题，我们为每个特征维度x

xi引入一个辅助向量：

=(v

,...,v

)

∈R

,i=1,2,3,...,n

(4)

(4)Vi=(vi1,vi2,vi3,...,vik)T∈Rk,i=1,2,3,...,n

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

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

W=⎛

⎝

⎜

⋮

...

⋱

...

⋮

⎞

⎠

⎟

n×n

(7)

(7)W=(ω11ω12...ω1nω21ω22...ω2n⋮⋮⋱⋮ωn1ωn2...ωnn)n×n

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

V=⎛

⎝

⎜

⋮

...

⋱

...

⋮

⎞

⎠

⎟

n×k

=⎛

⎝

⎜

⋯

⎞

⎠

⎟

(8)

(8)V=(v11v12...v1kv21v22...v2k⋮⋮⋱⋮vn1vn2...vnk)n×k=(V1TV2T⋯VnT)

令

(9)

(9)VVT=W

如果我们先得到V，则可以得到W了。

现在只剩下一个问题了，是否一个存在V，使得上述式（9）成立。

理论研究表明：当k足够大时，对于任意对称正定的实矩阵W∈R

n×n

W∈Rn×n，均存在实矩阵V∈R

n×k

V∈Rn×k，使得W=VV

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

1.2.3参数个数

假设样本中有n个特征，每个特征对应的隐变量维度为k，则参数个数为1+n+nk。

正如上面所言，对于特征维度足够多的样本，k<

1.2.4 计算时间复杂度

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

f(x)=ω

+∑

i=1

+∑

i=1

n−1

∑

j=i+1

(6)

(6)f(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1n(ViTVj)xixj

可以看出时间复杂度是O(kn

)

O(kn2)。但我们对上述式子的最后一项作变换后，可以得出一个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}\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}

上述式子中的∑

i=1

)

∑i=1n(vilxi)只需要计算一次就好，因此，可以看出上述模型的复杂度为O(kn)。

也就是说我们不要直接使用式（6）来计算预测结果，而应该使用式（10），这样的计算效率更高。1.2.5 梯度

FM有一个重要的性质：multilinearity：若记Θ=(ω

,ω

,...,ω

,...,v

)

Θ=(ω0,ω1,ω2,...,ωn,v11,v12,...,vnk)表示FM模型的所有参数，则对于任意的θ∈Θ

θ∈Θ，存在与θ

θ无关的g(x)

g(x)与h(x)

h(x)，使得式（6）可以表示为：

f(x)=g(x)+θh(x)

(11)

(11)f(x)=g(x)+θh(x)

从式（11）中可以看出，如果我们得到了g(x)

g(x)与h(x)

h(x)，则对于参数θ

θ的梯度为h(x)

h(x)。下面我们分情况讨论。

* 当 θ=ω

θ=ω0时，式（6）可以表示为：

f(x)=∑

i=1

+∑

i=1

n−1

∑

j=i+1

+ω

×1

(12)

(12)f(x)=∑i=1nωixi+∑i=1n−1∑j=i+1n(ViTVj)xixj+ω0×1

上述中的蓝色表示g(x)

g(x)，红色表示h(x)

h(x)。下同。

从上述式子可以看出此时的梯度为1.当θ=ω
l
,l∈(1,2,...,n)
θ=ωl,l∈(1,2,...,n)时，
f(x)=ω
0
+∑
i=1
i≠l
n
ω
i
x
i
+∑
i=1
n−1
∑
j=i+1
n
(V
T
i
V
j
)x
i
x
j
+ω
l
×x
l
(13)
(13)f(x)=ω0+∑i=1i≠lnωixi+∑i=1n−1∑j=i+1n(ViTVj)xixj+ωl×xl
此时梯度为x
l
xl。
当θ=v
lm
θ=vlm时
f(x)=ω
0
+∑
i=1
n
ω
i
x
i
+∑
i=1
n−1
∑
j=i+1
n
(∑
s=1
is≠lm
js≠lm
k
v
is
v
js
)x
i
x
j
+v
lm
×x
l
∑
i=1
i≠l
n
v
im
x
i
f(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1n(∑s=1is≠lmjs≠lmkvisvjs)xixj+vlm×xl∑i=1i≠lnvimxi
此时梯度为x
l
∑
i≠l
v
im
x
i
xl∑i≠lvimxi.

综合上述结论，f(x)

f(x)关于θ

θ的偏导数为：

∂f(x)

∂θ

=⎧

⎩

⎨

⎪

∑

i=1

i≠l

θ=ω

,l∈(1,2,...,n)

θ=v

(15)

(15)∂f(x)∂θ={1,θ=ω0xl,θ=ωl,l∈(1,2,...,n)xl∑i=1i≠lnvimxiθ=vlm

1.2.6 训练时间复杂度

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

∑

i=1

i≠l

∑

i=1

−v

(16)

(16)xl∑i=1i≠lnvimxi=xl∑i=1nvimxi−vlmxl2

对于上式中的前半部分∑

i=1

∑i=1nvimxi，对于每个样本只需要计算一次，所以时间复杂度为O(n)，对于k个隐变量的维度分别计算一次，则复杂度为O(kn)。其它项的时间复杂度都小于这一项，因此，模型训练的时间复杂度为O(kn)。详细一点解释：

（1）我们首先计算∑

i=1

∑i=1nvimxi，时间复杂度为n，这个值对于所有特征对应的隐变量的某一个维度是相同的。我们设这值为C。

（2）计算每一个特征对应的x

∑

i=1

−v

=Cx

−v

xl∑i=1nvimxi−vlmxl2=Cxl−vlmxl2，由于总共有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)=ω

+∑

i=1

+∑

j1=1

n−1

∑

j2=i+1

j1,f2

j2,f1

(17)

(17)f(x)=ω0+∑i=1nωixi+∑j1=1n−1∑j2=i+1n(Vj1,f2TVj2,f1)xj1xj2

其中j1,j2

j1,j2表示特征的索引。我们假设j1

j1特征属于f1

f1这个field，j2

j2特征属于f2

f2这个field，则V

j1,f2

Vj1,f2表示j1

j1这个特征对应f2

f2(j2

j2所属的field)的隐变量，同时V

j2,f1

Vj2,f1表示j2

j2这个特征对应f1

f1(j1

j1所属的field)的隐变量。事实上，在大多数情况下，FFM模型只保留了二次项，即：

ϕ(V,x)=∑

j1=1

n−1

∑

j2=i+1

j1,f2

j2,f1

(18)

(18)ϕ(V,x)=∑j1=1n−1∑j2=i+1n(Vj1,f2TVj2,f1)xj1xj2

2.2.2 最优化问题

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

minλ

||V||

+∑

i=1

log(1+exp(−y

ϕ(V,x)))

(19)

(19)minλ2||V||22+∑i=1mlog⁡(1+exp(−yiϕ(V,x)))

上面加号的前面部分使用了L2范式，后面部分是逻辑回归的损失函数。m表示样本的数量，y

yi表示训练样本的真实值（如是否点击的-1/1），ϕ(V,x)

ϕ(V,x)表示使用当前的V代入式（18）计算得到的值。注意，以上的损失函数适用于样本分布为{-1,1}的情况。

2.2.3 自适应学习率

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

j1,f2

−η

1+∑

j1,f2

)

−

√

j1,f2

(20)

(20)Vj1,f2=Vj1,f2−η1+∑t(gvj1,f2t)2gvj1,f2

其中g

j1,f2

gvj1,f2表示对于V

j1,f2

Vj1,f2这个变量的梯度向量，因为V

j1,f2

Vj1,f2是一个向量，因此g

j1,f2

gvj1,f2也是一个向量，尺寸为隐变量的维度大小，即k。

而∑

j1,f2

)

∑t(gvj1,f2t)2表示从第一个样本到当前样本一直以来的累积梯度平方和。

2.2.4 FFM算法的最终形式

j1,f2

)

=(V

j1,f2

)

d−1

−η

j1,f2

)

−

√

⋅(g

j1,f2

)

j2,f1

)

=(V

j2,f1

)

d−1

−η

j2,f1

)

−

√

⋅(g

j2,f1

)

(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

其中G为累积梯度平方：

j1,f2

)

=(G

j1,f2

)

d−1

+(g

j1,f2

)

j2,f1

)

=(G

j2,f1

)

d−1

+(g

j2,f1

)

(Gj1,f2)d=(Gj1,f2)d−1+(gj1,f2)d2(Gj2,f1)d=(Gj2,f1)d−1+(gj2,f1)d2

g为梯度，比如g

j1,f2

gj1,f2为j1

j1这个特征对应f2

f2这个field的梯度向量：

ji,f2

=λ⋅V

ji,f2

+κ⋅V

j2,f1

=λ⋅V

j2,f1

+κ⋅V

j1,f2

gji,f2=λ⋅Vji,f2+κ⋅Vj2,f1gj2,f1=λ⋅Vj2,f1+κ⋅Vj1,f2

其中κ

κ为：

κ=∂log(1+exp(−y

ϕ(V,x)))

∂ϕ(V,x)

=−y

1+exp(yϕ(V,x))

κ=∂log⁡(1+exp(−yiϕ(V,x)))∂ϕ(V,x)=−y1+exp⁡(yϕ(V,x))

2.3完整算法流程

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

2.3.1 计算梯度

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

ji,f2

=λ⋅V

ji,f2

+κ⋅V

j2,f1

=λ⋅V

j2,f1

+κ⋅V

j1,f2

(21)

(21)gji,f2=λ⋅Vji,f2+κ⋅Vj2,f1gj2,f1=λ⋅Vj2,f1+κ⋅Vj1,f2

其中κ

κ为式(19)后半部分对应的梯度，即：

κ=∂log(1+exp(−y

ϕ(V,x)))

∂ϕ(V,x)

=−y

1+exp(yϕ(V,x))

(22)

(22)κ=∂log⁡(1+exp(−yiϕ(V,x)))∂ϕ(V,x)=−y1+exp⁡(yϕ(V,x))

再重申一次，g

g与V

V都是k维的向量，在python中可以作为一个向量计算，在java/c++等需要通过一个循环进行计算。详细推导（21）式如下：

（1）在SGD中，式（19）可以转化为：

minλ

||V||

+log(1+exp(−y

ϕ(V,x)))

(23)

(23)minλ2||V||22+log⁡(1+exp(−yiϕ(V,x)))

（2）上式对V

j1,f2

Vj1,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}\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}

2.3.2 计算累积梯度平方和

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

j1,f2

)

=(G

j1,f2

)

d−1

+(g

j1,f2

)

j2,f1

)

=(G

j2,f1

)

d−1

+(g

j2,f1

)

(25)

(25)(Gj1,f2)d=(Gj1,f2)d−1+(gj1,f2)d2(Gj2,f1)d=(Gj2,f1)d−1+(gj2,f1)d2

2.3.3 更新隐变量

j1,f2

)

=(V

j1,f2

)

d−1

−η

j1,f2

)

−

√

⋅(g

j1,f2

)

j2,f1

)

=(V

j2,f1

)

d−1

−η

j2,f1

)

−

√

⋅(g

j2,f1

)

(26)

(26)(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

2.3.4 关于初始参数的设定

文献1中如此建议：

（1）η

η：没有具体的建议，用户根据经验指定即可，一般会取0.1，0.01，0.001。

（2）V

V：在区间[0,1/k

−

√

]

[0,1/k]间的随机值，均匀分布即可。

（3）G

G：设置为1，以避免(G

j1,f2

)

−1

(Gj1,f2)d−12出现很大的值。

2.4 时间复杂度

2.4.1 计算时间复杂度

由于式(18)无法做类似于式（10）的简化，因此FFM的计算时间复杂度为O(kn

)

O(kn2)。

2.4.2 训练时间复杂度

由于训练时，需要先根据式（18）计算ϕ

ϕ，复杂度为O(kn

)

O(kn2)，计算得到ϕ

ϕ后，还需要按照式（22）计算1次，按照式（21）计算2k次，按照式（23）计算2k次，按照式（24）计算2k次，也就是说，总的训练时间复杂度为：

O(kn

)+1+2k+2k+2k=O(kn

)

O(kn2)+1+2k+2k+2k=O(kn2)

因此，训练时间复杂度为O(kn

)

O(kn2)。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模型是有用的。

但事实上，计算ϕ

ϕ是几乎无用，而这是最耗时间的部分。

2.5.3 ParameterServer

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]=1||X||

2.6.4 特征归一化

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

完整代码见：

关于作者: luda

热门推荐