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

2021-08-07 阅读量:

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

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

辛普森悖论

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

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

视频	点击（次）	曝光（次）	点击率
视频A	8	530	1.51%
视频B	51	1520	3.36%

视频	点击（次）	曝光（次）	点击率
视频A	201	2510	8.01%
视频B	92	1010	9.11%

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

那么，如果忽略性别这个维度，将数据汇总（如表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

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预估（代码，数据流动详细过程）

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))