赞
踩
考虑以下数据集:
其中:Publisher、Advertiser、Gender表示特征域(field),EPSN、NBC、NIKE、Adidas、Male、Female表示one-hot编码的特征(feature)
对于第一条数据来说,FM模型的二次项为:
w
E
P
S
N
⋅
w
N
i
k
e
+
w
E
P
S
N
⋅
w
M
a
l
e
+
w
N
i
k
e
⋅
w
M
a
l
e
w_{EPSN}⋅w_{Nike}+w_{EPSN}⋅w_{Male}+w_{Nike}⋅w_{Male}
wEPSN⋅wNike+wEPSN⋅wMale+wNike⋅wMale。(这里只是把上面的v符合改成了w)每个特征只用一个隐向量来学习和其它特征的潜在影响。对于上面的例子中,Nike是广告主,Male是用户的性别,描述(EPSN,Nike)和(EPSN,Male)特征组合,FM模型都用同一个
w
E
S
P
N
w_{ESPN}
wESPN,而实际上,ESPN作为广告商,其对广告主和用户性别的潜在影响可能是不同的。
field是什么?简单的说,同一个类别特征进行one-hot编码后生成的数值特征都可以放在同一个field中,比如Male,Famale可以放于同一个field中。如果是数值特征而非类别,可以直接作为一个field。
引入了field后,对于刚才的例子来说,二次项变为:
因此,FFM的数学公式表示为:
y
^
=
w
0
+
∑
i
=
1
n
w
i
x
i
+
∑
i
=
1
n
∑
j
=
i
+
1
n
(
w
i
,
f
j
,
w
j
,
f
i
)
x
i
x
j
\hat{y}=w_{0}+\sum_{i=1}^{n}{w_{i}x_{i}}+\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{(w_{i,f_{j}},w_{j,f_{i}})x_{i}x_{j}}}
y^=w0+i=1∑nwixi+i=1∑nj=i+1∑n(wi,fj,wj,fi)xixj
其中
f
i
f_{i}
fi和
f
j
f_{j}
fj分别代表第
i
i
i个特征和第
j
j
j个特征所属的field。若field有
f
f
f个,隐向量的长度为
k
k
k,则二次项系数共有
d
f
k
dfk
dfk个,远多于FM模型的
d
k
dk
dk个。此外,隐向量和field相关,并不能像FM模型一样将二次项化简,计算的复杂度是
d
2
k
d^2k
d2k。
通常情况下,每个隐向量只需要学习特定field的表示,所以有
k
F
F
M
≪
k
F
M
k_{FFM}≪k_{FM}
kFFM≪kFM。
为了方便推导,这里省略FFM的一次项和常数项,公式为:
f
(
w
,
x
)
=
∑
i
=
1
n
∑
j
=
i
+
1
n
(
w
i
,
f
j
,
w
j
,
f
i
)
x
i
x
j
f(w,x)=\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{(w_{i,f_{j}},w_{j,f_{i}})x_{i}x_{j}}}
f(w,x)=i=1∑nj=i+1∑n(wi,fj,wj,fi)xixj
FFM模型使用logistic loss作为损失函数,并加上L2正则项:
L
o
s
s
=
∑
i
=
1
M
l
o
g
(
1
+
e
(
−
y
i
f
(
w
,
x
i
)
)
+
λ
2
∣
∣
w
∣
∣
2
Loss=\sum_{i=1}^{M}{log(1+e^{(-y_{i}f(w,x_{i}))}}+\frac{\lambda}{2}||w||^2
Loss=i=1∑Mlog(1+e(−yif(w,xi))+2λ∣∣w∣∣2
采用随机梯度下降来(SGD)来优化损失函数,因此,损失函数只采用单个样本的损失:
L
o
s
s
=
l
o
g
(
1
+
e
(
−
y
i
f
(
w
,
x
i
)
)
+
λ
2
∣
∣
w
∣
∣
2
Loss={log(1+e^{(-y_{i}f(w,x_{i}))}}+\frac{\lambda}{2}||w||^2
Loss=log(1+e(−yif(w,xi))+2λ∣∣w∣∣2
对于每次迭代,选取一条数据
(
x
,
y
)
(x,y)
(x,y)
,然后让
L
o
s
s
Loss
Loss对
w
i
,
f
j
w_{i,f_{j}}
wi,fj
和
w
j
,
f
i
w_{j,f_{i}}
wj,fi求偏导(注意,采用SGD上面的求和项就去掉了,只采用单个样本的损失),得:
g
i
,
f
j
=
∂
L
o
s
s
∂
w
i
,
f
j
=
k
∗
w
j
,
f
i
∗
x
i
x
j
+
λ
∗
w
i
,
f
j
g_{i,f_{j}}=\frac{\partial Loss}{\partial w_{i,f_{j}}}=k *w_{j,f_{i}}*x_{i}x_{j}+\lambda*w_{i,f_{j}}
gi,fj=∂wi,fj∂Loss=k∗wj,fi∗xixj+λ∗wi,fj
g
j
,
f
i
=
∂
L
o
s
s
∂
w
j
,
f
i
=
k
∗
w
i
,
f
j
∗
x
i
x
j
+
λ
∗
w
j
,
f
i
g_{j,f_{i}}=\frac{\partial Loss}{\partial w_{j,f_{i}}}=k *w_{i,f_{j}}*x_{i}x_{j}+\lambda*w_{j,f_{i}}
gj,fi=∂wj,fi∂Loss=k∗wi,fj∗xixj+λ∗wj,fi
其中:
k
=
−
y
1
+
e
y
f
(
w
,
x
)
k=\frac{-y}{1+e^{yf(w,x)}}
k=1+eyf(w,x)−y
Adagrad算法能够在训练中自动的调整学习率,对于稀疏的参数增加学习率,而稠密的参数则降低学习率。因此,Adagrad非常适合处理稀疏数据。
设
g
t
,
j
g_{t,j}
gt,j为第t轮第j个参数的梯度,则SGD和采用Adagrad的参数更新公式分别如下:
S
G
D
:
w
t
+
1
,
j
=
w
t
,
j
−
α
∗
g
t
,
j
SGD:w_{t+1,j}=w_{t,j} - \alpha*g_{t,j}
SGD:wt+1,j=wt,j−α∗gt,j
A
d
a
g
r
a
d
:
w
t
+
1
,
j
=
w
t
,
j
−
α
G
t
,
j
j
+
ϵ
∗
g
t
,
j
Adagrad:w_{t+1,j}=w_{t,j} - \frac{\alpha}{\sqrt{G_{t,jj}+\epsilon}}*g_{t,j}
Adagrad:wt+1,j=wt,j−Gt,jj+ϵ
α∗gt,j
可以看出,Adagrad在学习率ηη上还除以一项
G
t
,
j
j
+
ϵ
\sqrt{G_{t,jj}+\epsilon}
Gt,jj+ϵ
,这是什么意思呢?
ϵ
ϵ
ϵ为平滑项,防止分母为0,
G
t
,
j
j
=
∑
j
=
1
t
g
t
,
j
j
2
G_{t,jj}=\sum_{j=1}^{t}{g_{t,jj}^2}
Gt,jj=∑j=1tgt,jj2即
G
t
,
j
j
G_{t,jj}
Gt,jj为对角矩阵,每个对角线位置的值
j
,
j
j,j
j,j为参数
w
j
w_{j}
wj每一轮的平方和,可以看出,随着迭代的进行,每个参数的历史梯度累加到一起,使得每个参数的学习率逐渐减小。
因此,计算完梯度后,下一步就是更新分母的对角矩阵。
G
i
,
f
j
=
G
i
,
f
j
+
(
g
i
,
f
j
)
2
G_{i,f_{j}} = G_{i,f_{j}} +(g_{i,f_{j}})^2
Gi,fj=Gi,fj+(gi,fj)2
G
j
,
f
i
=
G
j
,
f
i
+
(
g
j
,
f
i
)
2
G_{j,f_{i}} = G_{j,f_{i}} +(g_{j,f_{i}})^2
Gj,fi=Gj,fi+(gj,fi)2
最后,更新模型参数:
w
i
,
f
j
=
w
i
,
f
j
−
α
G
i
,
f
j
+
ϵ
∗
g
i
,
f
j
w_{i,f_{j}} = w_{i,f_{j}} - \frac{\alpha}{\sqrt{G_{i,f_{j}}+\epsilon}}*g_{i,f_{j}}
wi,fj=wi,fj−Gi,fj+ϵ
α∗gi,fj
w
j
,
f
i
=
w
j
,
f
i
−
α
G
j
,
f
i
+
ϵ
∗
g
j
,
f
i
w_{j,f_{i}} = w_{j,f_{i}} - \frac{\alpha}{\sqrt{G_{j,f_{i}}+\epsilon}}*g_{j,f_{i}}
wj,fi=wj,fi−Gj,fi+ϵ
α∗gj,fi
在FFM原论文中,作者指出,FFM模型对于one-hot后类别特征十分有效,但是如果数据不够稀疏,可能相比其它模型提升没有稀疏的时候那么大,此外,对于数值型的数据效果不是特别的好。
使用FFM模型,特征需要转化为“field_id:feature_id:value”格式,相比LibSVM的格式多了field_id,即特征所属的field的编号,feature_id是特征编号,value为特征的值。
此外,美团点评的文章中,提到了训练FFM时的一些注意事项:
第一,样本归一化。FFM默认是进行样本数据的归一化的 。若不进行归一化,很容易造成数据inf溢出,进而引起梯度计算的nan错误。因此,样本层面的数据是推荐进行归一化的。
第二,特征归一化。CTR/CVR模型采用了多种类型的源特征,包括数值型和categorical类型等。但是,categorical类编码后的特征取值只有0或1,较大的数值型特征会造成样本归一化后categorical类生成特征的值非常小,没有区分性。例如,一条用户-商品记录,用户为“男”性,商品的销量是5000个(假设其它特征的值为零),那么归一化后特征“sex=male”(性别为男)的值略小于0.0002,而“volume”(销量)的值近似为1。特征“sex=male”在这个样本中的作用几乎可以忽略不计,这是相当不合理的。因此,将源数值型特征的值归一化到[0,1]是非常必要的。
第三,省略零值特征。从FFM模型的表达式(3-1)可以看出,零值特征对模型完全没有贡献。包含零值特征的一次项和组合项均为零,对于训练模型参数或者目标值预估是没有作用的。因此,可以省去零值特征,提高FFM模型训练和预测的速度,这也是稀疏样本采用FFM的显著优势。
import numpy as np import math import time # 将预测值映射到0~1区间,解决指数函数的溢出问题 def sigmoid(x): if x >= 0: return 1 / (1 + np.exp(-x)) else: return np.exp(x) / (1 + np.exp(x)) # 计算logit损失函数 def logit(y, y_hat): z = y * y_hat if z >= 0: return np.log(1 + np.exp(-z)) else: return np.log(1 + np.exp(z)) - z # 计算logit损失函数的外层偏导数(不对y_hat本身求导) def df_logit(y, y_hat): return sigmoid(-y * y_hat) * (-y) # 该类表示一个样本的一个特征 class FFM_Node(object): ''' 通常x是高维稀疏向量,所以用链表来表示一个x,链表上的每个节点是个3元组(j,f,v),表示一个样本x的一个非0特征 ''' # 按元组(而不是字典)的方式来存储类的成员属性 __slots__ = ['j', 'f', 'v'] def __init__(self, j, f, v): ''' :param j: Feature index (0 to n-1) :param f: Field index (0 to m-1) :param v: value ''' self.j = j self.f = f self.v = v class FFM(object): def __init__(self, m, n, k, alpha, Lambda): # m:域个数 n:特征个数 k:隐向量维度 alpha:学习率 Lambda:正则化权重系数 self.m = m self.n = n self.k = k # 超参数 self.alpha = alpha self.Lambda = Lambda # 初始化三维权重矩阵w~U(0,1/sqrt(k)) self.w = np.random.rand(n, m, k) / math.sqrt(k) # 初始化累积梯度平方和为,AdaGrad时要用到,防止除0异常 self.G = np.ones(shape=(n, m, k), dtype=np.float64) # 特征组合式的线性加权求和 def phi(self, node_list): # node_list: 一个样本,用链表存储x中的非0值 z = 0.0 for i in range(len(node_list)): node_i = node_list[i] j_i = node_i.j f_i = node_i.f v_i = node_i.v for d in range(i+1, len(node_list)): node_d = node_list[d] j_d = node_d.j f_d = node_d.f v_d = node_d.v w_i = self.w[j_i, f_d] w_d = self.w[j_d, f_i] z += np.dot(w_i, w_d) * v_i * v_d return z # 输出x, 预测y的值 def predict(self, node_list): ''' :param node_list: 用链表存储x中的非0值。 :return: 预测值y ''' z = self.phi(node_list) pre_y = sigmoid(z) return pre_y # 根据一个样本来更新模型参数、 def SGD_FFM(self, node_list, y): ''' :param node_list: 用链表存储x中的非0值。 :param y: 正样本1, 负样本-1 ''' y_hat = self.phi(node_list) loss = logit(y, y_hat) df_loss = df_logit(y, y_hat) for i in range(len(node_list)): node_i = node_list[i] j_i = node_i.j f_i = node_i.f v_i = node_i.v for d in range(i + 1, len(node_list)): node_d = node_list[d] j_d = node_d.j f_d = node_d.f v_d = node_d.v c = df_loss * v_i * v_d # 计算对w[j_i, f_d],w[j_d, f_i]的梯度 # self.w[j_i, f_d]和self.w[j_d, f_i]均是k维向量,故得到的g_ji_fd, g_jd_fi均是向量 g_ji_fd = c * self.w[j_i, f_d] + self.Lambda * self.w[j_i, f_d] g_jd_fi = c * self.w[j_d, f_i] + self.Lambda * self.w[j_d, f_i] # 计算各位维度上的梯度累积平方和 # s所有的G肯定是大于0的正数,因为初始化时G都为1 self.G[j_i, f_d] += g_ji_fd ** 2 self.G[j_d, f_i] += g_jd_fi ** 2 # Adagrad # np.sqrt(G)作为分母,所以G必须是大于0的正数 self.w[j_i, f_d] -= self.alpha / np.sqrt(self.G[j_i, f_d]) * g_ji_fd # math.sqrt()只能接收一个数字作为参数,而np.sqrt()可以接收一个array作为参数,表示对array中每个元素分别开方 self.w[j_d, f_i] -= self.alpha / np.sqrt(self.G(j_d, f_i)) * g_jd_fi return loss def train(self, sample_generator, max_echo): ''' :param sample_generator: 样本产生器,每次yeild(node_list, y), node_list中储存的是x的非0值。通常x要事先做好一次归一化,即模长为1, 这样精度会略高一些 :param max_echo: 最大迭代次数 :param max_r2: :return: ''' # 训练结束的标识 flag = 1 # 前一次迭代的总损失 loss_total_old = 0 # SGD开始时间 st = time.time() for step in range(max_echo): # 本次迭代的总损失 loss_total_new = 0 for node_list, y in sample_generator: loss_total_new += self.SGD_FFM(node_list, y) # SGD结束条件2:损失值过小,跳出 if loss_total_new < 1e-2: flag = 2 print("the total step:%d\n the loss is:%.6f" % ((step + 1), loss_total_new)) break # 第一次迭代,不计算前后损失值之差 if step == 0: loss_total_old = loss_total_new continue # SGD结束条件3:前后损失值之差过小,跳出 if (loss_total_old - loss_total_new) < 1e-5: flag = 3 print("the total step:%d\n the loss is:%.6f" % ((step + 1), loss_total_new)) break else: loss_total_old = loss_total_new if step % 10 == 0: print("the step is :%d\t the loss is:%.6f" % ((step + 1), loss_total_new)) # SGD结束时间 et = time.time() print("the total time:%.4f\nthe type of jump out:%d" % ((et - st), flag))
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。