推荐系统之FFM模型及python实现_ffm模型python

)

FFM模型的基本原理

FFM模型引入

考虑以下数据集：
其中：Publisher、Advertiser、Gender表示特征域(field),EPSN、NBC、NIKE、Adidas、Male、Female表示one-hot编码的特征(feature)
对于第一条数据来说，FM模型的二次项为：
$w_{EPSN}\cdot w_{Nike}+w_{EPSN}\cdot w_{Male}+w_{Nike}\cdot w_{Male}$。（这里只是把上面的v符合改成了w）每个特征只用一个隐向量来学习和其它特征的潜在影响。对于上面的例子中，Nike是广告主，Male是用户的性别，描述（EPSN，Nike）和（EPSN，Male）特征组合，FM模型都用同一个$w_{ESPN}$，而实际上，ESPN作为广告商，其对广告主和用户性别的潜在影响可能是不同的。
field是什么？简单的说，同一个类别特征进行one-hot编码后生成的数值特征都可以放在同一个field中，比如Male，Famale可以放于同一个field中。如果是数值特征而非类别，可以直接作为一个field。
引入了field后，对于刚才的例子来说，二次项变为：

• 对于特征组合（EPSN，Nike）来说，其隐向量采用的是$w_{EPSN,A}$和$w_{Nike,P}$,对于$w_{EPSN,A}$这是因为Nike属于广告主（Advertiser）的field，而第二项$w_{Nike,P}$则是EPSN是广告商（Publisher）的field。
• 再举个例子，对于特征组合（EPSN，Male）来说，$w_{EPSN,G}$,G是因为Male是用户性别(Gender)的field，而第二项$w_{Male,P}$,P是因为EPSN是广告商（Publisher）的field。

FFM模型数学公式

因此，FFM的数学公式表示为：
$$\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$$
其中$f_i$和$f_j$分别代表第$i$个特征和第$j$个特征所属的field。若field有$f$个，隐向量的长度为$k$，则二次项系数共有$dfk$个，远多于FM模型的$dk$个。此外，隐向量和field相关，并不能像FM模型一样将二次项化简，计算的复杂度是$d^{2}k$。
通常情况下，每个隐向量只需要学习特定field的表示，所以有$k_{FFM}\ll k_{FM}$。

FFM模型学习

为了方便推导，这里省略FFM的一次项和常数项，公式为：
$$f(w,x)=\sum _{i=1}^n\sum _{j=i+1}^n(w_{i,f_j},w_{j,f_i})x_i{x}_j$$

FFM模型使用logistic loss作为损失函数，并加上L2正则项：
$$Loss=\sum _{i=1}^{M}log(1+e^{(-y_{i}f(w,x_i))}+\frac{\lambda }{2}||w|{|}^2$$
采用随机梯度下降来（SGD）来优化损失函数，因此，损失函数只采用单个样本的损失：
$$Loss=log(1+e^{(-y_{i}f(w,x_i))}+\frac{\lambda }{2}||w|{|}^2$$
对于每次迭代，选取一条数据$(x,y)$
，然后让$Loss$对$w_{i,f_j}$
和$w_{j,f_i}$求偏导（注意，采用SGD上面的求和项就去掉了，只采用单个样本的损失），得：
$$g_{i,f_j}=\frac{\partial Loss}{\partial w_{i,f_j}}=k\ast w_{j,f_i}\ast x_i{x}_j+\lambda \ast w_{i,f_j}$$
$$g_{j,f_i}=\frac{\partial Loss}{\partial w_{j,f_i}}=k\ast w_{i,f_j}\ast x_i{x}_j+\lambda \ast w_{j,f_i}$$
其中：$k=\frac{-y}{1+e^{yf(w,x)}}$

Adagrad算法更新学习率

Adagrad算法能够在训练中自动的调整学习率，对于稀疏的参数增加学习率，而稠密的参数则降低学习率。因此，Adagrad非常适合处理稀疏数据。
设$g_{t,j}$为第t轮第j个参数的梯度，则SGD和采用Adagrad的参数更新公式分别如下：
$$SGD:w_{t+1,j}=w_{t,j}-\alpha \ast g_{t,j}$$
$$Adagrad:w_{t+1,j}=w_{t,j}-\frac{\alpha }{\sqrt{G_{t,jj}+ϵ}}\ast g_{t,j}$$
可以看出，Adagrad在学习率ηη上还除以一项$\sqrt{G_{t,jj}+ϵ}$，这是什么意思呢？$ϵ$为平滑项，防止分母为0，$G_{t,jj}={\sum }_{j=1}^t{g}_{t,jj}^2$即$G_{t,jj}$为对角矩阵，每个对角线位置的值$j,j$为参数$w_j$每一轮的平方和，可以看出，随着迭代的进行，每个参数的历史梯度累加到一起，使得每个参数的学习率逐渐减小。
因此，计算完梯度后，下一步就是更新分母的对角矩阵。
$$G_{i,f_j}=G_{i,f_j}+(g_{i,f_j}{)}^2$$
$$G_{j,f_i}=G_{j,f_i}+(g_{j,f_i}{)}^2$$
最后，更新模型参数：
$$w_{i,f_j}=w_{i,f_j}-\frac{\alpha }{\sqrt{G_{i,f_j}+ϵ}}\ast g_{i,f_j}$$
$$w_{j,f_i}=w_{j,f_i}-\frac{\alpha }{\sqrt{G_{j,f_i}+ϵ}}\ast g_{j,f_i}$$

适用范围和使用技巧

在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的显著优势。

FFM模型python代码实现

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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
'
运行
运行

参考

1.『我爱机器学习』FM、FFM与DeepFM
2.CTR/CVR中的FM、FFM算法