我的推荐算法之路(3):从FM到FFM

一、为什么需要特征组合?

在仅利用单一特征而非交叉特征进行判断的情况下,有时不仅是信息损失的问题,甚至会得出错误的结论。著名的“辛普森悖论”用一个非常简单的例子,说明了进行多维度特征交叉的重要性。

辛普森悖论

在对样本集合进行分组研究时,在分组比较中都占优势的一方,在总评中有时反而是失势的一方,这种有悖常理的现象,被称为“辛普森悖论”。

假设表2-1和表2-2所示为某视频应用中男性用户和女性用户点击视频的数据。

表2-1 男性用户
视频 点击(次) 曝光(次) 点击率
视频A 8 530 1.51%
视频B 51 1520 3.36%
表2-2 女性用户
视频 点击(次) 曝光(次) 点击率
视频A 201 2510 8.01%
视频B 92 1010 9.11%

从以上数据中可以看出,无论男性用户还是女性用户,对视频B的点击率都高于视频A,显然推荐系统应该优先考虑向用户推荐视频B。

那么,如果忽略性别这个维度,将数据汇总(如表2-3所示)会得出什么结论呢?

表2-3 数据汇总
视频 点击(次) 总曝光(次) 点击率
视频A 209 3040 6.88%
视频B 143 2530 5.65%

在汇总结果中,视频A的点击率居然比视频B高。如果据此进行推荐,将得出与之前结果完全相反的结论,这就是所谓的“辛普森悖论”。

在辛普森悖论的例子中,分组实验相当于使用“性别”+“视频ID”的组合特征计算点击率,而汇总实验则使用“视频ID”这一单一特征计算点击率。汇总实验对高维特征进行了合并,损失了大量的有效信息,因此无法正确地刻画数据模式。

二、特征交叉的开始——POLY2模型

\[POLY2(w,x)=w_0+\sum_{i=1}^n w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n w_{ij}x_ix_j\]

可以看到,该模型对所有特征进行了两两交叉(特征 \(x_i\)\(x_j\)),并对所有特征组合赋予权重 \(w_{ij}\)\(POLY2\) 通过暴力组合特征的方式,在一定程度上解决了特征组合的问题。但该模型存在两个较大的缺陷:

  • 在处理数据时,经常采用 one-hot 编码的方法处理类别型数据,致使特征向量极度稀疏, \(POLY2\) 进行无选择的特征交叉,使原本就非常稀疏的特征向量更加稀疏,导致大部分交叉特征的权重缺乏有效的数据进行训练,无法收敛。
  • 权重参数的数量由 \(n\) 直接上升到 \(n^2\) ,极大的增加了训练复杂度。

三、因子分解机模型(Factorization Machine, FM)(2010年)

\[ FM(w,x)=w_0+\sum_{i=1}^n w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n (\vec{v_i}\cdot \vec{v_j})x_ix_j \]

\(POLY2\) 相比,其主要区别是用两个向量的内积 \((\vec{v_i}\cdot \vec{v_j})\) 取代了单一的权重系数 \(w_{ij}\) 。具体地说,\(FM\) 为每个特征学习了一个权重隐向量,在特征交叉时,使用两个特征隐向量的内积作为交叉特征的权重。

本质上,\(FM\) 引入隐向量的做法,与矩阵分解用隐向量代表用户和物品的做法异曲同工。可以说, \(FM\) 是将矩阵分解隐向量的思想进行了进一步扩展,从单纯的用户、物品隐向量扩展到了所有特征上。

\(FM\) 通过引入特征隐向量的方式,直接把 \(POLY2\) 模型 \(n^2\) 级别的权重参数数量减少到了 \(nk\)\(k\) 为隐向量维度, \(n>>k\)),极大地降低了训练开销;而且,隐向量的引入使 \(FM\) 能更好地解决数据稀疏性的问题。比如在 \(POLY2\) 模型中,只有当特征\(x_i,x_j\) 均非零时,才能训练与之对应的 \(w_{ij}\),而对于 \(FM\) ,每个特征都有其对应的隐向量,减少了训练条件的苛刻性,并且对于未出现的特征组合,只要模型之前分别学习过对应的隐向量,就具备了计算其特征组合权重的能力。

\(FM\) 公式二次项后继推导如下:

采用梯度下降法求解参数: \[ \frac{∂FM}{∂ \theta}=\begin{cases}1,&\theta=w_0 \cr x_i,&\theta=w_i \cr x_i\sum_{i=1}^n(v_{ik}x_i)-v_{ik}x_i^2,&\theta=v_{ik}\end{cases} \]

四、特征域感知因子分解机模型(Field-aware Factorization Machines,FFM)(2015年)

\[ FFM(w,x)=w_0+\sum_{i=1}^n w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n (\vec{v_{i,f_j}}\cdot \vec{v_{j,f_i}})x_ix_j \]

其与 \(FM\) 的区别在于隐向量由原来的 \(\vec{v_i}\) 变成了 \(\vec{v_{i,f_j}}\) ,这意味着每个特征对应的不是唯一一个隐向量,而是一组隐向量。当 \(x_i\) 特征与 \(x_j\) 特征进行交叉时, \(x_i\) 特征会从 \(x_i\) 的这一组隐向量中挑出与特征 \(x_j\) 的域 \(f_j\) 对应的隐向量 \(\vec{v_{i,f_j}}\) 进行交叉。同理, \(x_j\) 也会用与 \(x_i\) 的域 \(f_i\) 对应的隐向量 \(\vec{v_{j,f_i}}\) 进行交叉。

为什么引入Field?

如下表所示,其中性别和年龄同属于user维度特征,而tag属于item维度特征。在FM原理讲解中,“男性”与“篮球”、“男性”与“年龄”所起潜在作用是默认一样的,但实际上不一定。FM算法无法捕捉这个差异,因为它不区分更广泛类别field的概念,而会使用相同参数的点积来计算。

field user field(U) item field(I)
clicked userId Gender_男 Gender_女 Age_[20,30] Age_[30,40] Tag_篮球 Tag_化妆品
1 1 1 0 1 0 1 0
0 1 1 0 1 0 0 1
0 2 0 1 0 1 1 0
1 2 0 1 0 1 0 1

\(FFM\)(Field-aware Factorization Machines )中每一维特征(feature)都归属于一个特定的 \(field\)\(field\)\(feature\) 是一对多的关系。

\(FFM\) 模型认为 \(v_i\) 不仅跟 \(x_i\) 有关系,还跟与 \(x_i\) 相乘的 \(x_j\) 所属的Field有关系,即 \(v_i\) 成了一个二维向量 \(v_{f×k}\)\(k\) 是隐向量长度,\(f\) 是Field的总个数。设样本一共有 \(n\) 个特征, 那么 \(FFM\) 的二次项有 \(nf\) 个隐向量。而在 \(FM\) 模型中,每一维特征的隐向量只有一个。\(FM\) 可以看作 \(FFM\) 的特例,是把所有特征都归属到一个 \(field\) 时的 \(FFM\) 模型。

五、FM与FFM的代码实现

5.1 FM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class FM(nn.Module):
def __init__(self, n, k):
super().__init__()
self.n = n # 特征个数
self.k = k # 隐向量维度
self.linear = nn.Linear(n, 1, bias=True) # 一次项部分
self.v = nn.parameter(torch.randn(k, n)) # 隐向量

def forward(self, x):
# x: (batch, n)
part1 = self.linear(x)
ans1 = torch.pow(torch.mm(x, self.v.t()), 2)
ans2 = torch.mm(torch.pow(x, 2), torch.pow(self.v.t(), 2))
return part1 + 0.5 * torch.sum(ans1 - ans2)

5.2 FFM

代码详解参考:推荐系统——FFM模型点击率CTR预估(代码,数据流动详细过程)

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
import torch
import torch.nn as nn
import numpy as np

class FieldAwareFactorizationMachine(nn.Module):
def __init__(self, field_dims, embed_dim):
super().__init__()
self.num_fields = len(field_dims)
self.embeddings = torch.nn.ModuleList([
torch.nn.Embedding(sum(field_dims), embed_dim) for _ in range(self.num_fields)
])
self.offsets = np.array((0, *np.cumsum(field_dims)[:-1]), dtype=np.long)
for embedding in self.embeddings:
torch.nn.init.xavier_uniform_(embedding.weight.data) #初始化

def forward(self, x):
x = x + x.new_tensor(self.offsets, dtype=np.long).unsqueeze(0)
xs = [self.embeddings[i](x) for i in range(self.num_fields)]
ix = list()
for i in range(self.num_fields - 1):
for j in range(i + 1, self.num_fields):
ix.append(xs[j][:, i] * xs[i][:, j])
ix = torch.stack(ix, dim=1)

class FieldAwareFactorizationMachineModel(torch.nn.Module):
def __init__(self, field_dims, embed_dim):
# field_dims:[10, 20, 30] 共3个field,每个field下各多少特征
super().__init__()
self.linear = nn.Linear(sum(field_dims))
self.ffm = FieldAwareFactorizationMachine(field_dims, embed_dim)

def forward(self, x):
"""
:param x: Long tensor of size ``(batch_size, num_fields)``
"""
ffm_term = torch.sum(torch.sum(self.ffm(x), dim=1), dim=1, keepdim=True)
x = self.linear(x) + ffm_term
return torch.sigmoid(x.squeeze(1))