Fork me on GitHub

推荐系统系列(二):FFM 算法理论与实践

背景

在 CTR/CVR 预估任务中,除了 FM 模型[2] 之外,后起之秀 FFM(Field-aware Factorization Machine)模型同样表现亮眼。FFM 可以看作是 FM 的升级版,Yuchi Juan 于 2016 年提出该模型,但其诞生是受启于 Rendle 在 2010 年发表的另一个模型 PITF [3](FM 也是 Rendle 在 2010 年发表的),其论文原文 [1] 中写道:

The idea of FFM originates from PITF proposed for recommender systems with personalized tags.

在各种深度推荐模型出来之前,FM/FFM 模型在各大推荐相关的竞赛中大放异彩。今天,我们就来好好梳理一下 FFM 的原理以及如何将理论转化为实践。

分析

1. FFM 公式定义

相较于 FM 模型,FFM 模型引入了域(Field)的概念(该想法来源于 PITF [3]),可看做是对特征进行分组。例如,对于性别特征而言,通常有两种取值 [公式][公式] 。对值进行 one-hot 编码之后性别特征会拆分为两个独立的特征 [公式][公式] 。显然,这两个特征具有共同的性质:都属于性别。所以可以将这两个特征归在同一个 Field 下,即有相同的 Field 编号。不同域的特征之间,往往具有明显的差异性。对比 FM 中的做法,每个特征有且仅有一个隐向量,在对特征 [公式] 与其他特征进行交叉时,始终使用同一个隐向量 [公式] 。 这种无差别式交叉方式,并没有考虑到不同特征之间的共性(同域)与差异性(异域)。

FFM 公式化定义如下:

[公式]

其中 [公式] 为域(Field)映射函数, [公式] 表示为 [公式] 特征对应的 Field 编号。

将公式(1)对比 FM 可以发现,二者之间的差异仅在于二阶交叉对应的隐向量。设数据集中 Field 的数目为 [公式] ,那么对于每个特征 [公式] 拥有 [公式] 个对应的隐向量,分别应用于与不同域特征进行交叉时。设隐向量维度为 [公式] ,FFM 二阶交叉项参数为 [公式]

2. 求解

由于引入了 Field,公式(1)不能像 FM 那样进行改写,所以 FFM 模型进行 推断 时的时间复杂度为 [公式]

为了方便推导各参数的梯度,隐向量表示为 [公式] 。公式(1)展开:

[公式]
当参数为 [公式] 时, [公式]
当参数为 [公式] 时, [公式]
当参数为 [公式] 时,其他参数视为常量,只考虑公式(2)交叉项。由于 Field 数量以及映射关系 [公式] 取决于数据集,这种情况参数梯度的数学统一表达式稍微复杂点(但当确定 [公式] 之后很好计算),所以这里就暂且按下不表。

3. 性能评估

上述小节并未得到统一的参数梯度表达式,但估计模型训练时的时间复杂度,仍需评估更新 [公式] 参数的时间复杂度。尽管没有梯度公式,但可以通过夹逼定理来确定该参数的更新时间复杂度。两种极端情况:1) [公式] ;2) [公式] ;参数更新时间复杂度位于二者之间。

  1. [公式] 时,所有特征均属于同一个 Field,此时 FFM 退化为 FM。可以将 [公式] 暂时省略,公式(2)可以表示为

[公式]
有,
[公式]
所以,更新参数 [公式] 所需时间复杂度为 [公式] 。这只是二阶项中 [公式] 个参数中的其中一个,所以更新二阶项参数总时间复杂度为 [公式]
2. [公式] 时,每个特征的 Field 都不相同。不失一般性,可以设 [公式] ,此时公式(2)可以表示为
[公式]
有,
[公式]
所以,更新参数 [公式] 所需时间复杂度为 [公式] 。这只是二阶项中 [公式] 个参数中的其中一个,所以更新二阶项参数总时间复杂度为 [公式]
综上,更新二阶项参数所需时间复杂度为 [公式] ,因为 [公式][公式] 参数更新时间复杂度为 [公式] ,所以 FFM 训练的时间复杂度为 [公式]
总结:FFM 训练/推断 时间复杂度都为 [公式]

4. 优缺点

优点:

  • 在高维稀疏性数据集中表现很好。
  • 相对 FM 模型精度更高,特征刻画更精细。

缺点:

  • 时间开销大。FFM 时间复杂度为 [公式] ,FM 时间复杂度为 [公式]
  • 参数多容易过拟合,必须设置正则化方法,以及早停的训练策略。

5. 注意事项

FFM 对于数据集的要求 [1]:

  1. FFMs should be effective for data sets that contain categorical features and are transformed to binary features.
  2. If the transformed set is not sparse enough, FFMs seem to bring less benefit.
  3. It is more difficult to apply FFMs on numerical data sets.
  1. 含有类别特征的数据集,且需要对特征进行二值化处理。
  2. 越是稀疏的数据集表现效果相较于其他模型更优。
  3. FFM 比较难应用于纯数值类型的数据集。

数据预处理 [4]:

与 FM 一样,最好先进行特征归一化,再进行样本归一化。

超参数对于模型的影响 [1]:

首先需要注意的是,FFM 的隐向量维度远小于 FM 的隐向量维度,即
[公式]

  1. 隐向量维度 [公式] 对于模型的影响不大。

2)正则化系数 [公式] 如果太大,容易导致模型欠拟合,反之,容易过拟合。

3)在论文中,使用的是 Adagrad 优化器,全局学习率 [公式] 也是超参数。如果 [公式] 在一个较小的水平,则可以表现最佳。过大,容易导致过拟合。过小,容易欠拟合。

模型训练加速 [1,4]:

  1. 梯度分布计算;2)自适应学习率;3)多核并行计算;4)SSE3 指令并行编程;

实验

与 FM 一致使用 [公式] 数据集,将评分大于 3 的样本置为正样本 1,其他置为负样本 0,构造一个二分类任务。使用 [公式] 损失函数,最后使用了 [公式] 优化算法。

论文中使用的 [公式] 将样本构造为-1、1 的二分类,同时使用的是 [公式] 优化算法 [1]

核心代码如下:

class FFM(object):
    def __init__(self, vec_dim, feat_num, field_num, lr, lamda):
        self.vec_dim = vec_dim
        self.feat_num = feat_num
        self.field_num = field_num
        self.lr = lr
        self.lamda = lamda

        self._build_graph()

    def _build_graph(self):
        self.add_input()
        self.inference()

    def add_input(self):
        self.x = tf.placeholder(tf.float32, shape=[None, self.feat_num], name='input_x')
        self.y = tf.placeholder(tf.float32, shape=[None], name='input_y')

    def inference(self):
        with tf.variable_scope('linear_part'):
            w0 = tf.get_variable(name='bias', shape=[1], dtype=tf.float32)
            self.W = tf.get_variable(name='linear_w', shape=[self.feat_num], dtype=tf.float32)
            self.linear_part = w0 + tf.reduce_sum(tf.multiply(self.x, self.W), axis=1)
        with tf.variable_scope('interaction_part'):
            self.V = tf.get_variable(name='interaction_w', shape=[self.feat_num, self.field_num, self.vec_dim], dtype=tf.float32)
            self.interaction_part = tf.constant(0, dtype=tf.float32)
            for i in range(self.feat_num):
                for j in range(i+1, self.feat_num):
                    self.interaction_part += \
                        tf.reduce_sum(tf.multiply(self.V[i, field_map[j]], self.V[j, field_map[i]])) * \
                        tf.multiply(self.x[:, i], self.x[:, j])

        self.y_logits = self.linear_part + self.interaction_part
        self.y_hat = tf.nn.sigmoid(self.y_logits)
        self.pred_label = tf.cast(self.y_hat > 0.5, tf.int32)
        self.loss = -tf.reduce_mean(self.y*tf.log(self.y_hat+1e-8) + (1-self.y)*tf.log(1-self.y_hat+1e-8))
        self.reg_loss = self.lamda*(tf.reduce_mean(tf.nn.l2_loss(self.W)) + tf.reduce_mean(tf.nn.l2_loss(self.V)))
        self.total_loss = self.loss + self.reg_loss

        self.train_op = tf.train.AdamOptimizer(self.lr).minimize(self.total_loss)

感想: FFM 训练速度真的很慢。

reference

[1] Juan, Yuchin, et al. "Field-aware factorization machines for CTR prediction." Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 2016.

[2] Rendle, S. (2010, December). Factorization machines. In 2010 IEEE International Conference on Data Mining (pp. 995-1000). IEEE.

[3] Rendle, Steffen, and Lars Schmidt-Thieme. "Pairwise interaction tensor factorization for personalized tag recommendation." Proceedings of the third ACM international conference on Web search and data mining. ACM, 2010.

[4] https://tech.meituan.com/2016/03/03/deep-understanding-of-ffm-principles-and-practices.html

[5] https://www.jianshu.com/p/781cde3d5f3d

[6] https://zhuanlan.zhihu.com/p/38241764

[7] https://zhuanlan.zhihu.com/p/64113429

[8] https://zhuanlan.zhihu.com/p/50692817

[9] https://blog.csdn.net/leadai/article/details/81713800


本文地址:https://www.6aiq.com/article/1590363925275
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出