9.传统 CTR 预估模型 - 四、FFM模型 - 《AI算法工程师手册》

四、FFM模型

四、FFM模型

考虑一组特征：“性别、年龄、城市”。为简化讨论，假设：“年龄”取值集合为 [18,19,20]， “城市” 取值集合为 [北京,上海,广州,深圳] 。

把离散特征 one-hot 编码，设各 binary 特征分别记作：male,female,age18,age19,age20,bj,sh,gz,sz， y 表示样本标签（-1 表示不感兴趣，+1 表示感兴趣）。

记作：
- POLY2 模型为：
  
  参数个数为，计算复杂度为。
- FM 模型为：
  
  参数个数为，计算复杂度为。
  - FM 要优于 POLY2 ，原因是：交叉特征非零的样本过于稀疏使得无法很好的估计；但是在 FM 中，交叉特征的参数可以从很多其它交叉特征中学习，使得参数估计更准确。
    
    如：交叉特征从未出现过，因此在 POLY2 模型中参数根本无法学习。
    
    而在 FM 模型中 male=1 的 representation 向量可以从以下交叉特征的样本中学习：
    
    age19=1 的 representation 向量可以从交叉特征的样本中学习。
  - 另外 FM 还可以泛化到没有见过的交叉特征。
    
    如：交叉特征从未在训练样本中出现过，但是在预测阶段 FM 模型能够较好的预测该交叉特征的测试样本。
在 FM 模型中，每个特征的 representation 向量只有一个。如：计算用到的是同一个向量。

论文Field-aware Factorization Machines for CTR Prediction 提出的 FFM 算法认为：age=18 和 sh=1 之间的区别，远远大于 age=18 和 age=20 之间的区别。

因此，FFM 算法将特征划分为不同的域field。其中：
- 特征属于性别域 gender field 。
- 特征属于年龄域 age field 。
- 特征属于城市域 city field 。
FFM 中每个特征的 representation 向量有多个，用于捕捉该特征在不同field 中的含义。

如：特征 male=1 具有两个 representation 向量：
- 当用于计算 age field 域的交叉特征时，采用
- 当用于计算 city field 域的交叉特征时，采用
其它特征依次类推。

注意：male=1 没有 gender field 域的交叉特征。因为 one-hot 编码的原因，交叉特征male=1,female=1 一定不能同时存在，所以不用计算。

4.1 模型

FFM 模型用数学语言描述为：

其中：表示第个特征所属的 field ，一共有个field （）。

参数数量为，计算复杂度为，其中是样本中平均非零特征数。
和 FM 相比，通常 FFM 中 representation 向量的维度要低的多。即：
FFM 每个representation 向量的学习只需要特定 field 中的样本。

如：学习时，只需要考虑交叉特征的样本，而不需要考虑交叉特征的样本。

因为上面的示例中，交叉特征未出现；如果该交叉特征出现，则也需要考虑该交叉特征的样本。
和 FM 相同，FFM 模型也可以用于求解分类问题（预测各评级的概率），也可以用于求解回归问题（预测各评分大小）。
- 对于回归问题，其损失函数为MSE 均方误差：
- 对于二分类问题（分类标签为 -1,+1 ），其损失函数为交叉熵：
  
  .

4.2 优化算法

FFM 模型采用随机梯度下降算法来求解，使用 AdaGrad 优化算法。

在每个迭代步随机采样一个样本来更新参数，则退化为：

统一所有的，则有：

其中：表示field f 内的所有特征；表示：
- 对梯度的每个维度，计算累积平方：
  
  其中是的第个分量，；是的第个分量，。
- 更新参数：
  
  其中是用户指定的学习率，。
模型参数需要合适的初始化。论文推荐：
- 从均匀分布中随机初始化
- 初始值为1，这是为了防止在迭代开始时太大，从而导致前进方向较大的偏离损失函数降低的方向。
原始论文并没有的项，因此个人推荐采用零均值、方差为的正态分布来初始化它们。
论文推荐采用样本级别的归一化，这可以提升模型泛化能力。

注：如果采用 Batch normalization 效果可能会更好。论文未采用 BN，是因为论文发表时 BN 技术还没有诞生。
FFM 的 AdaGrad 优化算法：
- 输入：
  - 训练集
  - 学习率
  - 最大迭代步
  - 初始化的参数
- 输出：极值点参数
- 算法步骤：
  - 初始化参数和：
  - 迭代步，每一步的过程为：
    - 随机从中采样一个样本
    - 计算：
    - 计算，更新
    - 遍历所有的项：：
      - 计算，更新
      - 遍历所有的项：
        
        计算
        遍历所有的维度：：计算，并更新

4.3 field 分配

FFM 模型需要为每个特征分配一个 field 。
- 离散型特征 categorical ：通常对离散型特征进行 one-hot 编码，编码后的所有二元特征都属于同一个 field 。
- 数值型特征 numuerical：数值型特征有两种处理方式：
  - 不做任何处理，简单的每个特征分配一个field 。
    
    此时， FFM 退化为 POLY2 模型。
  - 数值特征离散化之后，按照离散型特征分配 field 。
    
    论文推荐采用这种方式，缺点是：
    - 难以确定合适的离散化方式。如：多少个分桶？桶的边界如何确定？
    - 离散化会丢失一些信息。
- 离散集合特征categorical set（论文中也称作 single-field 特征）：所有特征都属于同一个field，此时， FFM 退化为 FM 模型。
  
  如 NLP 情感分类任务中，特征就是单词序列。
  - 如果对整个sentence 赋一个field，则没有任何意义。
  - 如果对每个word 赋一个 field，则等于词典大小，计算复杂度无法接受。

4.4 实验效果

实验效果的评估指标是负的对数似然，该指标越小越好：

其中为训练集或者验证集的样本数。
论文研究了超参数（representation 向量维度）、（正则化项系数）、（学习率）的影响。所有结果都是在验证集上得到。
- 超参数的实验效果如下图所示。
  
  第一列为不同的取值（论文中用 k 这个不同的符号），第二列为平均每个epoch 的计算时间，第三列为验证集的 logloss 。
  
  可以看到：不同的representation 向量维度，对模型的预测能力影响不大，但是对计算代价影响较大。
  - 由于采用了 SSE 指令集，所以时每个 epoch 计算时间几乎相同。
  - 所以在 FFM 中，通常选择一个较小的值。
- 超参数的实验效果如下图所示。
  
  可以看到：
  - 如果正则化系数太小，则模型太复杂，容易陷入过拟合。
  - 如果正则化系数太大，则模型太简单，容易陷入欠拟合。
  一个合适的正则化系数不大不小，需要精心挑选。
- 学习率的实验效果如下图所示：
  
  可以看到：
  - 如果学习率较小，虽然模型可以获得一个较好的性能，但是收敛速度很慢。
  - 如果学习率较大，则目标函数很快下降，但是目标函数不会收敛到一个较低的水平。
FFM 对于训练 epoch 次数很敏感。为解决该问题，论文推荐对 FFM 执行早停策略：
- 首先将数据集拆分为训练集、验证集。
- 在通过训练集训练的每个 epoch 结束时，计算验证集的 logloss 。
- 如果验证集的 logloss 上升，则：
  - 记录当前已训练的 epoch 次数
  - 停止当前训练
  - 用全量训练数据重新训练模型个 epoch 。
该方案存在一个潜在的缺点：logloss 对 epoch 次数高度敏感，以及验证集上的最佳 epoch 不一定是测试集上的最佳 epoch。因此早停得到的模型无法保证在测试集上取得最小的 logloss 。
论文在 Criteo 和 Avazu 数据集上比较了不同算法、不同优化方式、不同参数的结果。

Criteo 和 Avazu 数据集是Kaggle 提供的，其中有两个测试集：
- public test：当提交模型时，模型在该测试集上的得分和排名立即计算出来。
- private test ：当提交模型时，模型在该测试集上的得分和排名必须等竞赛结束时刻才揭晓。
  
  这是为了防止选手的模型对 public test 过拟合。
论文选择了四种算法：LM 模型（线性模型）、POLY2 模型、FM 模型、FFM 模型；选择了三种优化算法：SG （随机梯度下降）、CD（坐标下降）、Newton（牛顿法）、ALS ；选择了不同参数。
- LIBFM 支持SG,ALS,MCMC 三种优化算法，但是论文发现 ALS 效果最好。因此这里 LIBFM 使用 ALS 优化算法。
- FM、FFM 都是论文基于 SG 优化算法来实现的。同时对于 SG 优化算法采取早停策略。
- 对于非 SG 优化算法，停止条件由各算法给出合适的停止条件。
从实验结果可以看到：
- FFM 模型效果最好，但是其训练时间要比 LM 和 FM 更长； LM 效果比其它模型都差，但是它的训练要快得多； FM 是一种较好的平衡了预测效果和训练速度的模型。
  
  因此这就是效果和速度的平衡。
- POLY2 比所有模型都慢，因为其计算代价太大。
- 从两种 FM 的优化方法可见，SG 要比 ALS 优化算法训练得快得多。
- 逻辑回归是凸优化问题，理论上 LM 和 POLY2 的不同优化算法应该收敛到同一个点，但实验表明并非如此。
  
  原因是：我们并没有设置合适的停止条件，这使得训练过程并没有到达目标函数极值点就提前终止了。
论文比较了其它数据集上不同模型的表现。其中：
- KDD2010-bridge,KDD2012,adult 数据集包含数值特征和离散特征，论文将数值特征执行了离散化。
- cod-rna,ijcnn 数据集仅仅包含数值特征，论文将数值特征进行两种处理从而形成对比：
  - 将数值特征离散化
  - 每个数值特征作为一个field （称作 dummy fields ）
- phishing 数据集仅仅包含离散特征。
实验结果表明：
- FFM 模型几乎在所有数据集上都占优。这些数据集的特点是：
  - 大多数特征都是离散的
  - 经过 one-hot 编码之后大多数特征都是稀疏的
- 在 phishing,adult 数据集上 FFM 几乎没有优势。原因可能是：这两个数据集不是稀疏的，导致 FFM,FM,POLY2 这几个模型都具有几乎相同的表现。
- 在 adult 数据集上LM 的表现和 FFM,FM,POLY2 几乎完全相同，这表明在该数据集上特征交叉几乎没有起到什么作用。
- 在 dummy fields 的两个数据集上 FFM 没有优势，说明 field 不包含任何有用的信息。
- 在数值特征离散化之后，尽管 FFM 比 FM 更有优势，但还是不如使用原始数值特征的 FM 模型。
  
  这说明数值特征的离散化会丢失一些信息。
从实验中总结的 FFM 应用场景：
- 数据集包含离散特征，且这些离散特征经过one-hot 编码。
- 经过编码后的数据集应该足够稀疏，否则 FFM 无法获取较大收益（相对于 FM ）。
- 不应该在连续特征的数据集上应用 FFM，此时最好使用 FM 。