0.摘要
在计算广告领域点击率预测发挥了重要作用。针对CTR预估任务，POLY2和FMs被广泛的应用。最近一个FMs的变体FFM，在全球的CTR预测比赛中的表现已经超过了现有的一些模型。基于我们使用FFMs模型赢得了两次比赛的经验，本篇论文我们建立了一个对于现有的大型稀疏数据(包括CTR预估)的有效处理方法。首先，我们提出一些FFMs的训练方法。在训练方法上，FFMs对比其它模型的优劣势。实验表明FFMs对于某些分类问题是非常有效的，最后，我们已经发布了开源的FFMs供大家使用。
对于现有的大型稀疏数据(包括CTR预估)的有效处理方法。在训练方法上，FFMs对比其它模型的优劣势。实验表明FFMs对于某些分类问题是非常有效的开源的FFMs
1.引言
点击率预测在广告领域发挥了重大的作用。对于这个任务，逻辑回归是最为广泛使用的模型，给定
m
m
m个样本的数据
(
y
i
,
x
i
)
,
i
=
1
,
.
.
.
,
m
(y_i, \bold x_i), i=1,...,m
(yi,xi),i=1,...,m ,其中
y
i
y_i
yi是标签，而
x
i
x_i
xi是一个n维的特征向量，通过求解下面的优化问题可得到模型的参数
w
\bold w
w。
min
w
λ
2
∥
w
∥
2
2
+
∑
i
=
1
m
log
(
1
+
exp
(
−
y
i
ϕ
L
M
(
w
,
x
i
)
)
)
(
1
)
\min_{w} \qquad \frac{\lambda}{2} \begin{Vmatrix}\bold w \end{Vmatrix}^2_2 + \sum^m_{i=1}\log(1 + \exp(-y_i\phi_{LM}(\bold w, \bold x_i))) \qquad \qquad (1)
wmin2λ∥
∥w∥
∥22+i=1∑mlog(1+exp(−yiϕLM(w,xi)))(1) 在方程(1)中，
λ
\lambda
λ 是正则化参数，并且损失函数使用的是线性模型：
ϕ
L
M
(
w
,
x
i
)
=
w
⋅
x
\phi_{LM}(\bold w, \bold x_i) = \bold w · \bold x
ϕLM(w,xi)=w⋅x 对于CTR预测来说，学习特征组合非常关键的。 我们使用表 1 中的人工数据集，以便更好地理解特征组合。Gucci 的一则广告在 Vogue 上的点击率特别高。然而，线性模型很难学习这些信息，因为它们分别学习了 Gucci 和 Vogue 两个权重。这样获得的模型不能很好的拟合数据，为了解决这个问题，两种模型被评估特征组合的效果。 第一个模型为POLY2(多项式模型)，它会为每个新组合特征学习一个专门的权重，第二个模型是FMs，它会为每个特征学习一个隐向量。 我们将在第 2 节中讨论有关 Poly2 和 FM 的详细信息。
图1为CTR数据集，曝光点击(未点击)的数量第一个模型为POLY2(多项式模型)，它会为每个新组合特征学习一个专门的权重第二个模型是FMs，它会为每个特征学习一个隐向量
在个性化标签推荐中，提出了一种成对交互张量分解 (PITF) 的 FM 变体。在 KDD Cup 2012 比赛中，“Team Opera Solutions”提出了一种称为“因子模型”的 PITF 泛化。由于这个术语过于笼统，很容易与分解机混淆，我们在本文中将其称为“场感知分解机”(FFM)。PITF 和 FFM 的区别在于，PITF 考虑了“user”、“item”和“tag”三个特殊字段，而 FFM 更通用。因为[8]是关于比赛的整体解决方案，所以它对FFM的讨论是有限的。我们可以在[8]中得出以下结果：
他们都是用SG去解决优化问题，为了避免过拟合，他们仅仅只训练一个epoch在他们尝试的六个模型中，FFM表现得最好
本片论文中，我们将会具体介绍FFM作为有效的一种方法用于CTR预测，我们的主要工作结果如下：
为了进一步展示FFMs在CTR预测的有效性，我们提出的 FFM 模型，赢得了由 Criteo 和 Avazu 主办的两项全球 CTR 竞赛。 我们对比了FFMs和POLY2、FMs模型，我们首先从概念上讲为什么FFMs会优于他们加粗样式，然后进行了一些实验说明FFM的效果 我们介绍了FFMs的训练方法，为了防止过拟合 , 还包括一个有效的并行优化算法 开源了FFM框架
2.POLY2 和 FM
POLY2通常能够有效的捕捉交互特征信息，通过在2次多项式上应用一个线性模型，训练和测试的时间都比使用核方法要更加的快。 这种称为 Poly2 的方法为每个特征对学习一个权重：
ϕ
P
o
l
y
2
(
w
,
x
)
=
∑
j
1
=
1
n
∑
j
2
=
j
1
+
1
n
w
h
(
j
1
,
j
2
)
x
j
1
x
j
2
,
(
2
)
\phi_{Poly2}(\bold w, \bold x) = \sum^n_{j_1=1}\sum^n_{j_2=j_1+1}w_{h_(j_1,j_2)}x_{j_1}x_{j_2}, \qquad\qquad\qquad(2)
ϕPoly2(w,x)=j1=1∑nj2=j1+1∑nwh(j1,j2)xj1xj2,(2) 其中
h
(
j
1
,
j
2
)
h(j_1,j_2)
h(j1,j2)是一个将
j
1
j_1
j1和
j
2
j_2
j2编码成自然数的函数。计算的复杂度为
O
(
n
‾
2
)
O(\overline{n}^2)
O(n2)，其中
n
n
n代表每个样本中非零元素数量的平均值。
POLY2通常能够有效的捕捉交互特征信息，通过在2次多项式上应用一个线性模型，训练和测试的时间都比使用核方法要更加的快
FMs会为每个特征学习一个隐向量，每个隐向量会包含k个元素，k是超参数，可以进行调整。通过两个隐向量的内积对交叉特征进行建模:
ϕ
F
M
(
w
,
x
)
=
∑
j
1
=
1
n
∑
j
2
=
j
1
+
1
n
(
w
j
1
⋅
w
j
2
)
x
j
1
x
j
2
,
(
3
)
\phi_{FM}(\bold w, \bold x) = \sum^n_{j_1=1}\sum^n_{j_2=j_1+1}(\bold w_{j_1} ·\bold w_{j_2})x_{j_1}x_{j_2}, \qquad\qquad\qquad(3)
ϕFM(w,x)=j1=1∑nj2=j1+1∑n(wj1⋅wj2)xj1xj2,(3) 变量数量为
n
×
k
n×k
n×k, 因此直接计算的时间复杂度为
O
(
n
‾
2
k
)
O(\overline{n}^2k)
O(n2k)。上述公式可改写为:
ϕ
F
M
(
w
,
x
)
=
1
2
∑
j
=
1
n
(
s
−
w
j
x
j
)
⋅
w
j
x
j
其中
s
=
∑
j
‘
=
1
n
w
j
‘
x
j
‘
\phi_{FM}(\bold w, \bold x) =\frac{1}{2} \sum^n_{j=1}(\bold s - \bold w_jx_j)·\bold w_jx_j \\ 其中 \qquad \bold s = \sum^n_{j^`=1}\bold w_{j^`}x_{j^`}
ϕFM(w,x)=21j=1∑n(s−wjxj)⋅wjxj其中s=j‘=1∑nwj‘xj‘ 时间复杂度降低到
O
(
n
‾
k
)
O(\overline nk)
O(nk)
FMs会为每个特征学习一个隐向量，每个隐向量会包含k个元素，k是超参数，可以进行调整。通过两个隐向量的内积对交叉特征进行建模
在数据高度稀疏的情况下，Rendle说明了 FM 会比 Poly2 表现更好。通过表1的数据也说明了类似的结论,例如(ESPN，Adidas)只是训练数据的一个负样本。对于Poly2模型而言，可能会为整个组合特征学习一个负值权重
w
E
S
P
N
,
A
d
i
d
a
s
\bold w_{ESPN,Adidas}
wESPN,Adidas。对于FMs模型而言，(ESPN, Adidas) 的预测是由
w
E
S
P
N
⋅
w
A
d
i
d
a
s
\bold w_{ESPN} ·\bold w_{Adidas}
wESPN⋅wAdidas 确定，且
w
E
S
P
N
\bold w_{ESPN}
wESPN和
w
A
d
i
d
a
s
\bold w_{Adidas}
wAdidas可以由其他组合特征求得(例如(ESPN, Nike), (NBC, Adidas)), 使得预测更为准确。另外(NBC, Gucci)训练数据缺失。对于Poly2模型仅仅从一对数据中预测是不可靠的, 但对于FMs，因为
w
N
B
C
和
w
G
u
c
c
i
\bold w_{NBC} 和\bold w_{Gucci}
wNBC和wGucci 可以从其他组合特征中学习，所以其预测结果的可解释性更强。
注意在Poly2 模型中, 实现
h
(
j
1
,
j
2
)
h(j_1,j_2)
h(j1,j2)最简单的方法就是将两两特征组合成一个新的特征, 计算的复杂度为
O
(
n
2
)
O(n^2)
O(n2)，在数据量很大的时候,这种方式是不可取的。可以对
j
1
,
j
2
j_1,j_2
j1,j2进行哈希解决这个问题。我们的解决方法也和哈希类似:
h
(
j
1
,
j
2
)
=
(
1
2
(
j
1
+
j
2
)
(
j
1
+
j
2
+
1
)
+
j
2
)
m
o
d
B
h(j_1,j_2) = (\frac{1}{2}(j_1+j_2)(j_1+j_2+1)+j_2)\ mod\ B
h(j1,j2)=(21(j1+j2)(j1+j2+1)+j2) mod B 其中模型大小B为用户指定的参数。
在本文中，为了公式的简单性，我们不包括线性项和偏置项。 但是，在第 4 节中，我们将它们包括在一些实验中。
3.FFM
FFM的思想起源于在个性化标签的推荐系统提出的 PITF模型。 在PITF中，它们假设了3个变量域，分别是User、Item、Tag，并且将他们在特定的隐式空间。 进行分解(User、Item)，(User，Tag)，(Item，Tag)。vowpal_wabbit 在“Team Opera Solutions”提出的PITF的基础上,将 PITF 推广到更多字段（例如，AdID、AdvertiserID、UserID、QueryID）并有效地将其应用于 CTR 预测。 Rendle针对推荐系统并且仅限于三个特定字段（用户、物品和标签），并且vowpal_wabbit缺乏对FFM的详细讨论，所以在本节中，我们对FFMs在CTR预测方面进行了更全面的研究。在大部分CTR数据集中，特征可以分组为字段。在表1数据中,ESPN、Vogue 和 NBC 三个特征属于Publisher字段，而Nike,Gucci和 Adidas属于Advertiser字段。FFM 是利用此信息的 FM 的变体。为了解释 FFM 的工作原理，我们考虑以下新示例：
对于FM而言,
ϕ
F
M
(
w
,
x
)
\phi_{FM}(\bold w, \bold x)
ϕFM(w,x)是
w
E
S
P
N
⋅
w
N
i
k
e
+
w
E
S
P
N
⋅
w
M
a
l
e
+
w
N
i
k
e
⋅
w
M
a
l
e
\bold w_{ESPN}·\bold w_{Nike}+\bold w_{ESPN}·\bold w_{Male}+\bold w_{Nike}·\bold w_{Male}
wESPN⋅wNike+wESPN⋅wMale+wNike⋅wMale
在
F
M
s
FMs
FMs中, 每一个特征和其他特征组合学习只会学习一个隐向量。以
E
S
P
N
ESPN
ESPN为例,
w
E
S
P
N
w_{ESPN}
wESPN用来学习Nike
(
w
E
S
P
N
⋅
w
N
i
k
e
)
{(w_{ESPN}·w_{Nike})}
(wESPN⋅wNike)和Male
(
w
E
S
P
N
⋅
w
M
a
l
e
)
{(w_{ESPN}· w_{Male})}
(wESPN⋅wMale)之间潜在关系。但是Nike和Male属于不同的字段,因此(EPSN, Nike) 和 (EPSN, Male) 的潜在关系可能不同。
在FFMs中,每个特征有几个隐向量, 根据其他不同字段,取其中一个做内积。
ϕ
F
F
M
(
w
,
x
)
\phi_{FFM}(\bold w, \bold x)
ϕFFM(w,x)是
w
E
S
P
N
,
A
⋅
w
N
i
k
e
,
P
+
w
E
S
P
N
,
G
⋅
w
M
a
l
e
,
P
+
w
N
i
k
e
,
G
⋅
w
M
a
l
e
,
A
\bold w_{ESPN,A}·\bold w_{Nike,P}+\bold w_{ESPN,G}·\bold w_{Male,P}+\bold w_{Nike,G}·\bold w_{Male, A}
wESPN,A⋅wNike,P+wESPN,G⋅wMale,P+wNike,G⋅wMale,A
可以看出为了学习(ESPN, NIKE)的潜在关系,
w
E
S
P
N
,
A
\bold w_{ESPN,A}
wESPN,A被使用,因为Nike属于Advertiser字段,
w
N
i
k
e
,
P
\bold w_{Nike,P}
wNike,P被使用, 是因为ESPN属于Publisher字段。同样为了学习(ESPN, Male)的潜在关系,
w
E
S
P
N
,
G
\bold w_{ESPN,G}
wESPN,G被使用, 是因为Male属于Gender字段,
w
M
a
l
e
,
P
\bold w_{Male,P}
wMale,P被使用, 是因为ESPN属于Publisher字段。
ϕ
F
F
M
(
w
,
x
)
=
∑
j
1
=
1
n
∑
j
2
=
j
1
+
1
n
(
w
j
1
,
f
2
⋅
w
j
2
,
f
1
)
x
j
1
x
j
2
,
(
4
)
\phi_{FFM}(\bold w, \bold x) = \sum^n_{j_1=1}\sum^n_{j_2=j_1+1}(\bold w_{j_1,f_2} ·\bold w_{j_2,f_1})x_{j_1}x_{j_2}, \qquad\qquad\qquad(4)
ϕFFM(w,x)=j1=1∑nj2=j1+1∑n(wj1,f2⋅wj2,f1)xj1xj2,(4) 其中
f
1
f_1
f1和
f
2
f_2
f2分别属于字段
j
1
j_1
j1和
j
2
j_2
j2。如果f是字段数量, 那么FFMs的变量数量为
n
f
k
nfk
nfk, 复杂度为
O
(
n
‾
2
k
)
O(\overline{n}^2k)
O(n2k)。在FFMs中不同字段的特征组合时使用针对不同字段训练的隐向量。通常
k
F
F
M
≪
k
F
M
k_{FFM} \ll k_{FM}
kFFM≪kFM
3.1 解决优化问题
优化问题与公式 (1) 相同，只是将
ϕ
L
M
(
w
,
x
)
\phi_{LM}(\bold w,\bold x)
ϕLM(w,x) 替换为
ϕ
F
F
M
(
w
,
x
)
\phi_{FFM}(\bold w,\bold x)
ϕFFM(w,x)。在 PITFh和vowpal_wabbit 之后，我们使用随机梯度方法 (SG)。 最近提出了一些自适应学习率的优化方法，以促进 SG 的训练过程。我们使用的是AdaGrad，因为现在已经证实这个方法在一些稀疏矩阵上的有效性，特别是对于FFMs的例子。
在每一步SG中, 对数据
(
y
,
x
)
(y, \bold x)
(y,x)取样更新公式(4)中的
w
j
1
,
f
2
\bold w_{j_1,f_2}
wj1,f2和
w
j
2
,
f
1
\bold w_{j_2,f_1}
wj2,f1。由于数据
x
\bold x
x高度稀疏, 故仅仅更新非零的特征的权重值。首先子梯度是:
g
j
1
,
f
2
=
▽
j
1
,
f
2
f
(
w
)
=
λ
⋅
w
j
1
,
f
2
+
κ
⋅
w
j
2
,
f
1
x
j
1
x
j
2
,
(
5
)
g
j
2
,
f
1
=
▽
j
2
,
f
1
f
(
w
)
=
λ
⋅
w
j
2
,
f
1
+
κ
⋅
w
j
1
,
f
2
x
j
1
x
j
2
,
(
6
)
\bold \ g_{j_1,f_2} = \bigtriangledown_{j_1,f_2}f(\bold w)=\lambda·\bold w_{j_1,f_2}+\kappa·\bold w_{j_2,f_1}x_{j_1}x_{j_2}, \qquad\qquad\qquad (5)\\ \bold \ g_{j_2,f_1} = \bigtriangledown_{j_2,f_1}f(\bold w)=\lambda·\bold w_{j_2,f_1}+\kappa·\bold w_{j_1,f_2}x_{j_1}x_{j_2}, \qquad\qquad\qquad (6)
gj1,f2=▽j1,f2f(w)=λ⋅wj1,f2+κ⋅wj2,f1xj1xj2,(5) gj2,f1=▽j2,f1f(w)=λ⋅wj2,f1+κ⋅wj1,f2xj1xj2,(6) 其中:
κ
=
∂
log
(
1
+
e
x
p
(
−
y
ϕ
F
F
M
(
w
,
x
)
)
)
∂
ϕ
F
F
M
(
w
,
x
)
)
=
−
y
1
+
e
x
p
(
−
y
ϕ
F
F
M
(
w
,
x
)
)
\kappa = \frac{\partial\log(1+exp(-y_{\phi FFM}(\bold w, \bold x)))}{\partial_{\phi FFM}(\bold w, \bold x))}=\frac{-y}{1+exp(-y_{\phi FFM}(\bold w, \bold x))}
κ=∂ϕFFM(w,x))∂log(1+exp(−yϕFFM(w,x)))=1+exp(−yϕFFM(w,x))−y 其次，对于每个坐标
d
=
1
,
.
.
.
,
k
d = 1,...,k
d=1,...,k，累积梯度平方和
(
G
j
1
,
f
2
)
d
←
(
G
j
1
,
f
2
)
d
+
(
g
j
1
,
f
2
)
d
2
(
7
)
(
G
j
2
,
f
1
)
d
←
(
G
j
2
,
f
1
)
d
+
(
g
j
2
,
f
1
)
d
2
(
8
)
(G_{j_1,f_2})_d \leftarrow (G_{j_1,f_2})_d +(g_{j_1,f_2})^2_d \qquad\qquad\qquad (7)\\ (G_{j_2,f_1})_d \leftarrow (G_{j_2,f_1})_d +(g_{j_2,f_1})^2_d \qquad\qquad\qquad (8)
(Gj1,f2)d←(Gj1,f2)d+(gj1,f2)d2(7)(Gj2,f1)d←(Gj2,f1)d+(gj2,f1)d2(8) 最终
(
w
j
1
,
f
2
)
d
(w_{j_1,f_2})_d
(wj1,f2)d和
(
w
j
2
,
f
1
)
d
(w_{j_2,f_1})_d
(wj2,f1)d更新为:
(
w
j
1
,
f
2
)
d
←
(
w
j
1
,
f
2
)
d
+
η
(
G
j
1
,
f
2
)
d
(
g
j
1
,
f
2
)
d
(
9
)
(
w
j
2
,
f
1
)
d
←
(
w
j
2
,
f
1
)
d
+
η
(
G
j
2
,
f
1
)
d
(
g
j
2
,
f
1
)
d
(
10
)
(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 \qquad\qquad\qquad (9) \\[2ex] (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 \qquad\qquad\qquad (10)
(wj1,f2)d←(wj1,f2)d+(Gj1,f2)d
η(gj1,f2)d(9)(wj2,f1)d←(wj2,f1)d+(Gj2,f1)d
η(gj2,f1)d(10) 其中
η
\eta
η为学习率。
w
\bold w
w初始值在区间
[
1
,
1
k
]
[1,\frac{1}{\sqrt k}]
[1,k
1]的正态分布中随机选取。
G
G
G的初始值设置为1(防止
(
G
j
1
,
f
2
)
d
−
1
2
(G_{j_1,f_2})^{-\frac{1}{2}}_d
(Gj1,f2)d−21过大)。
对数据进行归一化可以提高精度,同时不会影响参数。
3.2 并行化内存系统
现在的计算是广泛的使用多核进行计算，如果这些和能够充分的利用，训练时间能够大幅度的减少，一些并行化的方法已经提出了使用于SG。本篇论文中，采用HogWILD方法，这将允许我们不使用任何锁然后使每个线程能够独立的运行。
在第 4.4 节中，我们进行了实验来研究并行化的有效性。
3.2.1 Adding Field Information
考虑最通用的LIBSVM数据格式:
l
a
b
e
l
f
e
a
t
1
:
v
a
l
1
f
e
a
t
2
:
v
a
l
2
⋅
⋅
⋅
,
label \quad feat1:val1 \quad feat2:val2 ···,
labelfeat1:val1feat2:val2⋅⋅⋅,
其中每个 (feat, val) 对表示特征索引和值。
我们扩展以上格式:
l
a
b
e
l
f
i
e
l
d
1
:
f
e
a
t
1
:
v
a
l
1
f
i
e
l
d
2
:
f
e
a
t
2
:
v
a
l
2
⋅
⋅
⋅
label \quad field1:feat1:val1 \quad field2:feat2:val2 ···
labelfield1:feat1:val1field2:feat2:val2⋅⋅⋅也就是说，我们必须为每个特征分配相应的字段。 在某些类型的特征上分配很容易，但对于其他一些特征可能无法完成。 我们在三类典型的特征上讨论这个问题。
类别型特征
对于线性模型，一个分类特征通常被转换为几个二元特征。对于数据格式:
Y
e
s
P
:
E
S
P
N
A
:
N
i
k
e
G
:
M
a
l
e
,
Yes \quad P:ESPN \quad A:Nike \quad G:Male,
YesP:ESPNA:NikeG:Male,我们生成以下LIBSVM格式数据:
Y
e
s
P
−
E
S
P
N
:
1
A
−
N
i
k
e
:
1
G
−
M
a
l
e
:
1
Yes \quad P-ESPN:1 \quad A-Nike:1 \quad G-Male:1
YesP−ESPN:1A−Nike:1G−Male:1 注意:根据分类特征可能取值的数目, 每次生成相同数量的二值特征, 且只有一个值为1。在LIBSVM格式中, 我们只存储非零值。我们对所有模型应用相同的设置，因此在本文中，每个分类特征都转换为几个二元特征。要添加字段信息，我们可以将每个类别视为一个字段。 那么上面的数据就变成了:
Y
e
s
P
:
P
−
E
S
P
N
:
1
A
:
A
−
N
i
k
e
:
1
G
:
G
−
M
a
l
e
:
1
Yes \quad P:P-ESPN:1\quad A:A-Nike:1 \quad G:G-Male:1
YesP:P−ESPN:1A:A−Nike:1G:G−Male:1 数值型特征
考虑以下样本数据来预测一篇论文是否会被会议接受。 我们使用三个数字特征“会议接受率 (AR)”、“作者的 h-index (Hidx)”和“作者的引用次数 (Cite)”：
有两种方式来处理字段。 一种简单的方法是将每个特征视为一个虚拟字段，因此生成的数据为：
Y
e
s
A
R
:
A
R
:
45.73
H
i
d
x
:
H
i
d
x
:
2
C
i
t
e
:
C
i
t
e
:
3
Yes\quad AR:AR:45.73\quad Hidx:Hidx:2\quad Cite:Cite:3
YesAR:AR:45.73Hidx:Hidx:2Cite:Cite:3 但是，虚拟字段可能无法提供信息，因为它们只是特征的副本。
另一种处理方法是将数值化特征离散化为类别型特征, 然后，我们可以对分类特征使用相同的设置来添加字段信息。 生成的数据如下所示：
Y
e
s
A
R
:
45
:
1
H
i
d
x
:
2
:
1
C
i
t
e
:
3
:
1
,
Yes\quad AR:45:1\quad Hidx:2:1\quad Cite:3:1,
YesAR:45:1Hidx:2:1Cite:3:1, 其中 AR 特征四舍五入为整数。 主要缺点是通常不容易确定最佳离散化设置。 例如，我们可以将 45.73 转换为“45.7”、“45”、“40”甚至“int(log(45.73))”。 另外，离散化后我们可能会丢失一些信息。
Single-field Features
在某些数据集上，所有特征都属于一个字段，因此将字段分配给特征是没有意义的。 这种情况通常发生在 NLP 数据集上。 考虑以下预测句子是否表达好心情的示例： 在本例中，唯一的字段是“句子”。 如果我们将此字段分配给所有单词，则 FFM 将简化为 FM。读者可能会问关于分配虚拟字段的问题，就像我们对数字特征所做的那样。回想一下，FFM 的模型大小为
O
(
n
f
k
)
O(nfk)
O(nfk)。使用虚拟字段是不切实际的，因为
f
=
n
f = n
f=n 并且
n
n
n 通常很大。
4.实验
在本节中，我们首先提供有关实验设置的详细信息。然后研究参数的影响。 发现，与 LM 或 Poly2 不同，FFM 对 epoch 的数量很敏感。因此，我们在提出提前收敛技巧。接下来研究了并行化的加速。将 FFM 与包括 Poly2 和 FM 在内的其他模型进行了比较。它们都是通过相同的 SG 方法实现的，因此除了准确性之外，我们还可以地比较它们的训练间。在比较中，我们使用了最先进的 LIBLINEAR 和 LIBFM 包，分别用于训练 LM/Poly2 和 FM。
4.1 实验设置
数据集
我们主要考虑来自 Kaggle 比赛的两个 CTR 集 Criteo 和 Avazu，尽管在第 4.6 节中考虑了更多数据集。对于特征工程，我们主要应用我们的获胜解决方案，但删除复杂部分。例如，我们为 Avazu 赢得的解决方案包括 20 个模型的集合，但这里我们只使用最简单的一个。有关其他详细信息，请查看我们的实验代码。应用哈希技巧来生成
1
0
6
10^6
106 个特征。 两个数据集的统计数据为： 对于这两个数据集，测试集中的label是不公开的，因此我们将可用数据分成两组进行训练和验证。 数据拆分遵循以下规则：对于 Criteo，最后 6,040,618 行用作验证集； 对于 Avazu，我们选择最后 4,218,938 行。 我们使用以下术语来表示不同的问题集。
Va 验证集Tr 从原始训练数据中去除验证集后的新训练集。TrVa 原始训练集。Te 原始测试集。标签没有发布，因此我们必须将我们的预测提交给原始评估系统才能获得分数。 为了避免对测试集的过度拟合，比赛组织者将这个数据集分为两个子集：“公共集”，在比赛期间可以看到分数，“私人集”，在比赛结束后可以看到分数。最终排名由私有集决定。
例如，CriteoVa 表示来自 Criteo 的验证集。
Platform
所有的实验都是在Linux系统下进行，拥有12个物理和在两个Intel Xeon E5-2620 2.0 GHZ处理器和128GB的内存
评估指标
对于评估标准，我们考虑 logistic 损失定义为
l
o
g
l
o
s
s
=
1
m
∑
i
=
1
m
l
o
g
(
1
+
e
x
p
(
−
y
i
ϕ
(
w
,
x
i
)
)
)
logloss = \frac{1}{m}\sum^m_{i=1}log(1+exp(-y_i\phi(\bold w, \bold x_i)))
logloss=m1i=1∑mlog(1+exp(−yiϕ(w,xi))) 其中m为样本数
实现
我们在 C++ 中实现了 LM、Poly2、FM 和 FFM。对于 FM 和 FFM，我们使用 SSE 指令来提高内积的效率。在3.2 节中讨论的并行化由 OpenMP 实现。我们的实现包括线性项和偏差项，因为它们提高了某些数据集的性能。 请注意，为了代码可扩展性，字段信息的存储与使用的模型无关。对于非 FFM 模型，通过没有字段信息的更简单的数据结构，实现可能会稍微快一些，但我们的实验结论应该保持不变。
4.2 参数影响
我们进行了一些实验，来比较参数
κ
,
λ
,
η
\kappa, \lambda, \eta
κ,λ,η 对模型的影响。对于关于参数
κ
\kappa
κ，图 1a 中的结果表明它对 logloss 的影响不大。如果
λ
\lambda
λ太大，模型表现不佳，如果
λ
\lambda
λ太小的话，模型表现较好，但是它是极容易过拟合。对于参数
η
\eta
η ，一个较小的参数能够使得FFMs获得最好的表现，但是收敛速度较慢，如果参数
η
\eta
η过大，FFMs能够快速收敛，但是会产生过拟合。从图 1b 和 1c 的结果来看，需要提前停止训练，这将在第 4.3 节中讨论。
4.3 提前停止训练
提前停止，即在训练数据达到最佳结果之前终止训练过程，可用于避免许多机器学习问题的过度拟合。对于 FFM，我们使用的策略是：
将数据集拆分为训练集和验证集。在每个 epoch 结束时，使用验证集计算损失。如果loss上升，记录epoch数。 停止或转到步骤 4。如果需要，使用完整的数据集以步骤 3 中获得的 epoch 数重新训练模型。
使用提前停止训练最大的困难就是logloss对于epoch的数量是非常敏感的，然后就是在验证集上最好的epoch可能在测试集上表现得不好。 我们尝试了其他方法来避免过度拟合，例如延迟更新和基于 ALS 的优化方法。 然而，结果并不像提前停止使用验证集那样成功。
4.4 加速
因为 SG 的并行化可能会导致不同的收敛行为，所以在图 2 中尝试了不同数量的线程。结果表明，我们的并行化仍然会导致类似的收敛行为。 有了这个属性，我们可以将加速定义为：
R
u
n
n
i
n
g
t
i
m
e
o
f
o
n
e
e
p
o
c
h
w
i
t
h
a
s
i
n
g
l
e
t
h
r
e
a
d
R
u
n
n
i
n
g
t
i
m
e
o
f
o
n
e
e
p
o
c
h
w
i
t
h
m
u
l
t
i
p
l
e
t
h
r
e
a
d
s
\frac{Running\ time\ of\ one\ epoch\ with\ a\ single\ thread}{Running\ time\ of\ one\ epoch\ with\ multiple\ threads }
Running time of one epoch with multiple threadsRunning time of one epoch with a single thread 图 3 中的结果显示，当线程数量较少时，加速效果很好。但是，如果使用多个线程，加速并不会提高多少。 一种解释是，如果两个或多个线程试图访问同一个内存地址，求中一个必须等待。当使用更多线程时，这种冲突会更频繁地发生。
4.5 在两个 CTR 竞赛数据集上与 LM、Poly2 和 FM 进行比较
我们对 LM、Poly2、FM 和 FFM 实现了相同的 SG 方法。 此外，我们比较了两个最先进的软件包：
LIBLINEAR：广泛使用的线性模型包。对于 L2 正则化逻辑回归，它实现了两种优化方法：牛顿法解决原始问题，坐标下降法（CD）解决对偶问题。我们研究了两种优化方法如何影响模型的性能； 请参阅本小节末尾的讨论。 此外，LIBLINEAR 的现有 Poly2 扩展不支持哈希技巧，因此我们进行了适当的修改，并在本文中将其表示为 LIBLINEAR-Hash。LIBFM：作为一个广泛使用的分解机库，它支持三种优化方法，包括随机梯度法（SG）、交替最小二乘法（ALS）和马尔可夫链蒙特卡罗（MCMC）。我们尝试了所有这些方法，发现 ALS 在 logloss 方面明显优于其他两种。 因此，我们在实验中考虑 ALS。
对于所有模型中的参数，我们从网格搜索中选择那些在验证集上具有最佳性能的点。每个优化算法都需要一个停止条件；我们使用 LIBLINEAR 的牛顿法和坐标下降 (CD) 法的默认设置。对于其他每个模型，我们需要一个验证集来验证哪个迭代导致最佳验证分数。在我们获得最佳迭代次数后，我们重新训练模型直到该迭代次数。在表 3 中可以找到 Criteo 和 Avazu 的结果以及使用的参数列表。显然，FFM 在 logloss 方面优于其他模型，但它也需要比 LM 和 FM 更长的训练时间。另一方面，虽然 LM 的 logloss 比其他模型差，但它明显更快。这些结果显示了对数损失和速度之间的明确权衡。 Poly2 是所有模型中最慢的。原因可能是（2）的昂贵计算。FM 在 logloss 和速度之间取得了很好的平衡。
对于 LIBFM，它在 Criteo 上的 logloss 方面与 FM 实现非常接近。 但是，我们看到我们的实现速度明显更快。 我们提供了三个可能的原因：
LIBFM 使用的 ALS 算法比我们使用的 SG 算法复杂。我们在SG 中使用自适应学习率策略。我们使用SSE指令来促进内积运算。
因为逻辑回归是一个凸问题，理想情况下，对于 LM 或 Poly2，如果三种优化方法（SG、Newton 和 CD）收敛到全局最优值，它们应该生成完全相同的模型。然而，实际结果略有不同。特别是，SG 的 LM 优于 Avazu 上的两个基于 LIBLINEAR 的模型。在我们的实现中，LM via SG 只是松散地解决了优化问题。 因此，我们的实验表明，即使问题是凸的，不同的优化方法也会影响结果模型的性能。
4.6 在更多的数据集上作比较
在上一节中，我们关注了两个比赛的数据集，但重要的是要了解 FFM 在其他数据集上的表现。 为了回答这个问题，我们考察了更多的数据集进行比较，其中大多数不是 CTR 数据。 请注意，在第 3.3 节的讨论之后，我们不考虑具有单字段特征的数据集。原因在于，根据我们分配字段的方式，FFM 要么变得等同于 FM，要么生成一个巨大的模型。 这里我们简单介绍一下使用的数据集。
KDD2010-bridge：该数据集包括数值和分类特征。 KDD2012：该集合包含数字和分类特征。 因为我们的评估是对数损失，所以我们将原始目标 值“点击次数”转换为二进制值“点击与否”。 cod-rna：这个集合只包含数字特征。 ijcnn：该集合仅包含数字特征。 phishing:此集合仅包含分类特征。 adult:该数据集包括数字和分类特征。
对于 KDD2010-bridge、KDD2012 和adult，我们简单地将所有数值特征分别离散为 29、13 和 94 个 bin。 对于 cod-rna 和 ijcnn，特征都是数字的，我们尝试 3.3 节中提到的两种方法来获取字段信息：应用虚拟字段和离散化。
对于参数选择，我们遵循第 4.5 节中的相同程序。 我们将每个集合分为训练、验证和测试集； 然后为了预测测试集，我们使用经过参数训练的模型，这些参数在验证集上实现了最佳对数损失。
每个数据集的基本统计信息和实验结果如表 4 所示。FFM 在 KDD2010-bridge 和 KDD2012 上显着优于其他模型。 这些数据集的共同特点是：
大部分特征是类别型特征在将分类特征转换为许多二元特征后，结果集是高度稀疏的。
然而在 phishing and adult数据集上, FFM并没有表现较好。对于phishing数据集, 原因可能是数据不稀疏，因此 FFM、FM 和 Poly2 性能接近；对于adult数据集, 特征组合似乎没有用，因为所有模型的性能都与线性模型相似。
当数据集仅包含数字特征时，FFM 可能没有明显的优势。如果我们使用虚拟字段，则 FFM 的性能不会优于 FM，这表明字段信息没有帮助。另一方面，如果我们对数值特征进行离散化，虽然 FFMs 是所有模型中最好的，但模型性能不佳。 我们总结了在不同类型的数据集上应用 FFM 的指南：
FFM 应该对包含分类特征并转换为二元特征的数据集有效。如果变换后的集合不够稀疏，FFM 似乎带来的好处更少。在数值数据集上应用FFM 更加困难。
5.结论与未来工作
在本文中，我们讨论了 FFM 的有效实现。我们证明，对于某些类型的数据集，FFM 在 logloss 方面优于 LM、Poly2 和 FM模型，但训练时间更长。
对于未来的工作，4.3 节中讨论的过拟合问题是我们计划研究的问题。 此外，为了便于实施，我们使用 SG 作为优化方法。 看看其他优化方法（例如牛顿法）如何在 FFM 上工作很有趣。
好文阅读
发表评论