特征交叉系列：完全理解FM因子分解机原理和代码实战
关键词：特征交叉，推荐算法，FM
内容摘要
- 特征交叉和FM背景介绍
- FM原理提要
- 二阶交互作用的稀疏性
- FM对学习参数的优化
- FM的优缺点总结
- FM在Pytorch下的实践
- 没有特征交叉的LR训练
- 带有特征交叉的FM训练
特征交叉和FM背景介绍
推荐算法中将用户特征，商品特征，以及上下文的特征输入给一个模型函数进行打分预测用户的交互意愿，而用户兴趣的高低往往不是单一一个独立特征就可以挖掘的，通常多个特征的组合形成的一个特征组更容易发现用户兴趣的一般规律，比如对<user年龄，user性别>做特征组合让模型学习历史行为日志中这个局部人群的兴趣爱好，再如<user性别， item类目>做特征组合让模型学习是否某一类的商品在用户性别上有明显的兴趣区分度，这种将一对或者多维特征进行组合形成新的特征输入模型的方式叫做特征交叉，特征交叉自然可以增强模型的非线性能力，提高模型的拟合能力。
特征交叉可以从特征入手，比如模型输入时就添加用户和商品的交互特征，类似A用户过去一段滑动窗口下对B商品所属类目的点击次，也可以从模型入手，即设计一个网络结构能够对原始输入特征进行自动交叉和组合，让模型能够学习到这种特征交之间互关联的模式，在传统机器学习领域能够自动特征交叉的算法包括GBDT提升树和FM因子分解机。
FM提出于2010年，旨在解决稀疏数据下的特征交叉问题，相比于线性的逻辑回归，FM引入和二阶交互项。
FM原理提要
二阶交互作用的稀疏性
传统的逻辑回归仅仅是给每个特征单独分配了一个权重，FM在此基础上加入特征两两之间的二阶相乘的特征，公式如下
FM公式1
举例A用户是一个女青年，包含性别和年龄段两个特征，做onehot之后一阶特征的表达是[0, 1, 1, 0, 0]，所有特征交叉之后形成5×5=25个新特征，其中只取上三角不连对角线还剩10个特征，因此二阶特征之后还需要加入一个类似[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]的所有二阶组合的全集，其中唯一的一个1是性别女和年龄青年对角线命中的组合情况，FM对每一对特征进行交叉，只有两个特征都是1交叉才有意义，否则交叉结果为0，由此可见数据是极度稀疏的，而这种以离散变量为主的数据在推荐算法场景很常见。
特征交叉举例
设onehot之后的特征数量为n，一阶特征模型需要学习参数有n+1个(wx+b)，而二阶模型需要学习的参数有n+1+n(n-1)/2个，参数个数随着n的扩大呈平方增长。另一方面由于二阶特征里面绝大多数都是0，在进行神经网络反向链式求导的时候是包含特征值这个因子的，因此计算出的梯度为0二阶特征的权重无法更新，因此暴力求解所有二阶参数不可取。
FM对学习参数的优化
FM的精髓是不直接求解特征交叉权重，而是将一对特征交叉进行拆解，拆解为两个底层的特征属性的求解，即将二阶特征的权重计算转化为该对一阶特征对应的向量的内积，如下图所示
该对一阶特征对应的向量的内积
其中vi代表第i个一阶特征对应的隐向量，它是一个一维向量，长度为k(k << n)，这时FM模型方程如下
FM公式2
因此只要计算出每个一阶特征对应的隐向量即可，这些隐向量组成一个n × k的矩阵，模型从求解n+1+n(n-1)/2个二阶参数优化为只要求解n × k参数即可，参数的数量随着特征数量n是线性的，优化前是平方级别。
FM的计算公式可以进一步计算如下
FM公式3
上图是最终梯度的公式，其中红色框内的f代表隐向量的某个k位置上的分量，注意红色框内是和xi中的i无关的，也就是说xi和xi+1是共用这个红色框的，因此所有特征x1->n的梯度计算可以只求一次红色框内部分即可，单个i单个f需要计算n次，则单个i所有f的复杂度是O(kn)，由于红色框内共享，因此计算所有i的复杂度也是O(kn)，因此FM可以在特征数量的线性时间内完成训练。
FM的优缺点总结
- 优势
1.照顾到所有特征和二阶交互项，而不是像GBDT只对部分特征做选择交叉，FM能够很好的挖掘所有特征的二阶交叉组合
2.适合高维稀疏特征，通过引入隐向量解决二阶参数难以训练的问题
3.FM不论训练还是预测，复杂度随着特征增长都是线性的
FM的缺点
- 虽然考虑了特征的交叉，但是表达能力仍然有限，只能对二阶进行交叉，不能高阶交叉
- FM会对所有特征做两两交叉，从业务上某些交叉是没有必要的，存在冗余
- 由第2点进一步衍生，因为过多的两两交叉容易导致特征之间互相拉扯，形成矛盾，特征的隐向量不能做到对特征交叉表达的全局适配，因此引出下一篇特征交叉系列：Field-aware FM 场感知因子分解机原理和实践中的FFM算法，FFM引入场的概念，为每一个特征准备多套隐向量，通过场来隔离不同对特征的交叉，解决单一隐向量导致的特征拉扯问题
FM在Pytorch下的实践
样本特征交叉数据分析
采用用户的购买记录流水作为训练数据，用户侧特征是年龄，性别，会员年限等离散特征，商品侧特征采用商品的二级类目，产地，品牌三个离散特征，随机构造负样本，使用LR和FM分别进行训练，期望模型能够学习到用户特征和商品特征的匹配程度。
没有特征交叉的LR训练
采用Pytorch构建一个Linear层即可
class LR(nn.Module):
def __init__(self, feature_size, k_dim=4):
super(FM, self).__init__()
self.linear = nn.Linear(feature_size, 1)
def forward(self, x):
linear_part = self.linear(x) # [None, 1]
output = t.sigmoid(linear_part)
return output.squeeze(dim=1)
训练日志如下，多次测试验证集AUC在0.608左右
epoch: 10 step: 598 loss: 0.680474042892456 auc: 0.5920163571046396
epoch: 10 step: 600 loss: 0.665024995803833 auc: 0.6218916768547087
[evaluation] loss: 0.6739967465400696 auc: 0.6048385095987285
本轮auc比之前最大auc下降：0.00019671459790582269, 当前最大auc: 0.6050352241966344
---------early stop!----------
带有特征交叉的FM训练
在原有LR的网络基础上增加FM中的特征交叉层，网络层代码如下
class Cross(nn.Module):
def __init__(self, feature_size, k_dim=4):
super(Cross, self).__init__()
self.v = nn.Parameter(t.randn(feature_size, k_dim))
nn.init.xavier_normal_(self.v)
def forward(self, x):
inter_part1 = t.mm(x, self.v) # [None, k]
inter_part2 = t.mm(t.pow(x, 2), t.pow(self.v, 2)) # [None, k]
inter = 0.5 * t.sum(t.sub(t.pow(inter_part1, 2), inter_part2), 1, keepdim=True) # [None, 1]
return inter
class FM(nn.Module):
def __init__(self, feature_size, k_dim=4):
super(FM, self).__init__()
self.linear = nn.Linear(feature_size, 1)
self.cross = Cross(feature_size, k_dim)
def forward(self, x):
linear_part = self.linear(x) # [None, 1]
inter = self.cross(x) # [None, 1]
output = linear_part + inter # [None, 1]
output = t.sigmoid(output)
return output.squeeze(dim=1)
观察模型需要训练的参数，一共1 + n + kn个参数
for i, j in model.named_parameters():
print(i, j.numel())
>>> linear.weight 72
>>> linear.bias 1
>>> cross.v 288
部分训练代码如下
model = FM(feature_size=72, k_dim=4)
criterion = nn.BCELoss(reduction="mean")
optimizer = t.optim.Adam(model.parameters(), lr=0.002, weight_decay=0)
step = 0
val_auc_list = []
early_stop_flag = False
for epoch in range(10):
for index, (batch_x, batch_y) in enumerate(train_loader):
model.train()
batch_x, batch_y = batch_x.to(device).float(), batch_y.to(device).float()
optimizer.zero_grad()
output = model(batch_x)
loss = criterion(output, batch_y)
loss.backward()
optimizer.step()
step += 1
if step % 2 == 0:
auc = roc_auc_score(batch_y.detach().numpy(), output.detach().numpy())
print("epoch: {} step: {} loss: {} auc: {}".format(epoch + 1, step, loss.item(), auc))
if step % 10 == 0:
pred, target = [], []
model.eval()
with t.no_grad():
for _, (batch_x_test, batch_y_test) in enumerate(test_loader):
batch_x_test, batch_y_test = batch_x_test.to(device).float(), batch_y_test.to(device).float()
output = model(batch_x_test)
loss = criterion(output, batch_y_test)
pred += list(output.numpy())
target += list(batch_y_test.numpy())
auc = roc_auc_score(target, pred)
print("[evaluation] loss: {} auc: {}".format(loss.item(), auc))
diff_auc = (auc - max(val_auc_list)) if len(val_auc_list) else 0
val_auc_list.append(auc)
print("本轮auc比之前最大auc{}：{}, 当前最大auc: {}\n".format("上升" if diff_auc > 0 else "下降", abs(diff_auc),
max(val_auc_list)))
if early_stop_auc(val_auc_list, windows=5):
print("{:-^30}".format("early stop!"))
early_stop_flag = True
break
if early_stop_flag:
break
训练日志如下，多次训练模型在验证集的AUC在0.622
epoch: 6 step: 346 loss: 0.664692759513855 auc: 0.6302039327137261
epoch: 6 step: 348 loss: 0.6743635535240173 auc: 0.622337320437246
epoch: 6 step: 350 loss: 0.6726325750350952 auc: 0.6081947108823269
[evaluation] loss: 0.6761345267295837 auc: 0.6189907086416703
本轮auc比之前最大auc下降：1.6331192310703457e-05, 当前最大auc: 0.619007039833981
---------early stop!----------
FM的验证集AUC比LR上升了2个百分点左右，说明了FM捕捉交叉特征的有效性。
