21.9. 分解机¶ 在 SageMaker Studio Lab 中打开 Notebook
由 Rendle (2010) 提出的分解机（factorization machine，FM）是一种可用于分类、回归和排序任务的监督学习算法。它很快就受到了关注，成为一种流行的、有影响力的预测和推荐方法。特别是，它是线性回归模型和矩阵分解模型的推广。此外，它让人联想到带有多项式核的支持向量机。分解机相比于线性回归和矩阵分解的优势在于：（1）它可以对 \(\chi\) 阶变量的交互进行建模，其中 \(\chi\) 是多项式的阶数，通常设置为 2。（2）与分解机相关的一种快速优化算法可以将多项式计算时间减少到线性复杂度，使其在处理高维稀疏输入时非常高效。由于这些原因，分解机在现代广告和产品推荐中得到了广泛应用。下面将介绍技术细节和实现。
21.9.1. 二阶分解机¶
形式上，令 \(x \in \mathbb{R}^d\) 表示一个样本的特征向量，\(y\) 表示相应的标签，可以是实数值标签或类别标签（如“点击/未点击”的二元类别）。二阶分解机的模型定义为
其中 \(\mathbf{w}_0 \in \mathbb{R}\) 是全局偏置；\(\mathbf{w} \in \mathbb{R}^d\) 表示第 i 个变量的权重；\(\mathbf{V} \in \mathbb{R}^{d\times k}\) 表示特征嵌入；\(\mathbf{v}_i\) 表示 \(\mathbf{V}\) 的第 \(i^\textrm{th}\) 行；\(k\) 是隐因子的维度；\(\langle\cdot, \cdot \rangle\) 是两个向量的点积。\(\langle \mathbf{v}_i, \mathbf{v}_j \rangle\) 对第 \(i^\textrm{th}\) 个和第 \(j^\textrm{th}\) 个特征之间的交互进行建模。一些特征交互很容易理解，因此可以由专家设计。然而，大多数其他特征交互都隐藏在数据中，难以识别。因此，自动建模特征交互可以大大减少特征工程的工作量。很明显，前两项对应于线性回归模型，最后一项是矩阵分解模型的扩展。如果特征 \(i\) 代表一个物品，特征 \(j\) 代表一个用户，那么第三项正是用户和物品嵌入之间的点积。值得注意的是，分解机也可以推广到更高阶（阶数 > 2）。然而，数值稳定性可能会削弱其泛化能力。
21.9.2. 高效的优化准则¶
直接优化分解机会导致 \(\mathcal{O}(kd^2)\) 的复杂度，因为需要计算所有成对的交互。为了解决这个低效问题，我们可以重新组织分解机的第三项，这可以大大降低计算成本，从而实现线性时间复杂度（\(\mathcal{O}(kd)\)）。成对交互项的重构如下：
通过这种重构，模型的复杂度大大降低。此外，对于稀疏特征，只需要计算非零元素，因此总体复杂度与非零特征的数量呈线性关系。
为了学习分解机模型，我们可以对回归任务使用均方误差（MSE）损失，对分类任务使用交叉熵损失，对排序任务使用 BPR 损失。标准的优化器如随机梯度下降（SGD）和 Adam 都可以用于优化。
import os
from mxnet import gluon, init, np, npx
from mxnet.gluon import nn
from d2l import mxnet as d2l
npx.set_np()
21.9.3. 模型实现¶
以下代码实现了分解机。可以清楚地看到，分解机由一个线性回归模块和一个高效的特征交互模块组成。我们将最终得分通过一个 sigmoid 函数，因为我们把点击率预测看作一个分类任务。
class FM(nn.Block):
def __init__(self, field_dims, num_factors):
super(FM, self).__init__()
num_inputs = int(sum(field_dims))
self.embedding = nn.Embedding(num_inputs, num_factors)
self.fc = nn.Embedding(num_inputs, 1)
self.linear_layer = nn.Dense(1, use_bias=True)
def forward(self, x):
square_of_sum = np.sum(self.embedding(x), axis=1) ** 2
sum_of_square = np.sum(self.embedding(x) ** 2, axis=1)
x = self.linear_layer(self.fc(x).sum(1)) \
+ 0.5 * (square_of_sum - sum_of_square).sum(1, keepdims=True)
x = npx.sigmoid(x)
return x
21.9.4. 加载广告数据集¶
我们使用上一节中的点击率数据包装器来加载在线广告数据集。
batch_size = 2048
data_dir = d2l.download_extract('ctr')
train_data = d2l.CTRDataset(os.path.join(data_dir, 'train.csv'))
test_data = d2l.CTRDataset(os.path.join(data_dir, 'test.csv'),
feat_mapper=train_data.feat_mapper,
defaults=train_data.defaults)
train_iter = gluon.data.DataLoader(
train_data, shuffle=True, last_batch='rollover', batch_size=batch_size,
num_workers=d2l.get_dataloader_workers())
test_iter = gluon.data.DataLoader(
test_data, shuffle=False, last_batch='rollover', batch_size=batch_size,
num_workers=d2l.get_dataloader_workers())
[22:12:53] ../src/storage/storage.cc:196: Using Pooled (Naive) StorageManager for CPU
21.9.5. 训练模型¶
然后，我们训练模型。学习率设置为 0.02，嵌入大小默认为 20。使用 Adam 优化器和 SigmoidBinaryCrossEntropyLoss 损失函数进行模型训练。
devices = d2l.try_all_gpus()
net = FM(train_data.field_dims, num_factors=20)
net.initialize(init.Xavier(), ctx=devices)
lr, num_epochs, optimizer = 0.02, 30, 'adam'
trainer = gluon.Trainer(net.collect_params(), optimizer,
{'learning_rate': lr})
loss = gluon.loss.SigmoidBinaryCrossEntropyLoss()
d2l.train_ch13(net, train_iter, test_iter, loss, trainer, num_epochs, devices)
loss 0.504, train acc 0.283, test acc 0.277
44217.6 examples/sec on [gpu(0), gpu(1)]
21.9.6. 小结¶
分解机是一个通用框架，可以应用于回归、分类和排序等多种任务。
特征交互/交叉对于预测任务很重要，二阶交互可以通过分解机高效地建模。