[人工智能]【推荐系统论文精读系列】(六)--Field-aware Factorization Machines for CTR Prediction

Field-aware Factorization Machines for CTR Prediction

一、摘要

点击率预测发挥了很大的作用在计算广告领域。针对这个任务，POLY2和FMs被广泛的应用。最近一个FMs的变体FFM，它的表现已经超过了现有的一些模型。基于我们赢得了两次比赛的胜利，本篇论文我们已经建立了一个有效的方式对于阐述现有的大型稀疏矩阵。首先，我们提出一些FFMs的训练实现方式。然后我们深刻分析了FFMs并且对比了这个方法与其它模型。经验表明FFMs是非常有用的对于某些分类问题，最后，我们已经发布了开源的FFMs供大家使用。

二、介绍

点击率预测在广告领域发挥了重大的作用。对于这个任务，逻辑回归是最为广泛使用的模型，给定数据集 $(y_i,x_i),i=1,...,m$ ，其中 $y_i$ 是标签，而 $x_i$ 是一个 $n$ 维特征向量，模型的参数 $w$ 可以通过解决下面的优化方程获得：
$$mi{n}_w\frac{\lambda }{2}||w|{|}^2+\sum _{i=1}^{m}log(1+ex{p}^{?y_i?LM(w,x_i)})$$
在方程(1)中，$\lambda$ 是正则化参数，并且损失函数我们考虑使用的是线性模型：
$$?LM(w,x)=w?x$$
对于CTR预测来说，学习特征组合式非常关键的。传统线性模型只能够为各自特征学得相应得权重，这样获得的模型不能很好的拟合数据，为了解决这个问题，两种模型被使用去组合新的特征。

第一个模型为POLY2，它会学习一个专门的权重为新组合的特征，第二个模型是FMs，它会为每个特征学习一个隐向量。

• 他们都是用SG去解决优化问题，为了避免过拟合，他们仅仅只训练一个epoch
• 在他们尝试的六个模型中，FFM表现得最好

本片论文中，我们将会具体介绍FFM作为有效的一种方法用于CTR预测，我们的主要工作结果如下：

• 为了进一步展示FFMs在CRT预测的有效性，我们呈现了使用FFMs作为主要的模型赢得了两个大型CTR预测比赛
• 我们对比了FFMs和其他两个模型，分别是POLY2、FMs，我们首先从概念上讲为什么FFMs会好于他们，然后进行了一些实验就精度和训练时间来看它们的不同
• 我们呈现了训练FFMs的训练技术，它们包括一个有效的并行优化算法和使用提前停止为了防止过拟合
• 为了使得FFMs可以公开使用，我们开源了这个软件

三、POLY2 和 FM

POLY2通常能够有效的捕捉交互特征信息，进一步，它们展示了应用一个线性模型，训练和测试的时间都比使用核方法要更加的快。
$$?POLY2(w,x)=\sum _{j_1}^n\sum _{j_2=j_1+1}^n{w}_{h(j_1,j_2)}{x}_{j_1}{x}_{j2}$$
其中 $w_{h(j_1,j_2)}$ 代表两个不同特征之间的权重，这个模型的计算复杂度平均为 $O(n^2)$ 。

FMs会为每个特征学习一个隐向量，每个隐向量会包含k个元素，这个k是个超参数，可以进行调整。
$$?FM(w,x)=\sum _{j_1=1}^n\sum _{j_2=j_1+1}^n(w_{j_1}{w}_{j_2})x_{j_1}{x}_{j_2}$$
其中的权重变量的个数为 $n?k$ ，每个 $w$ 为一个k维向量。

四、FFM

FFM想法的起源来自PITF，在PITF中，它们假设了3个变量域，分别是User、Item、Tag，并且将他们进行分解（User、Item），（User，Tag），（Item，Tag）在特定的隐式空间。

由于我们的目标是推荐系统，所以三个特征域显示是受限的，并且缺乏详细的讨论在FFM，本部分，我们将会提供一个更加理解性的研究讲FFMs应用于CTR预测领域。

在FMs中，每个特征仅会学习一个隐向量和其它的特征，然后FFMs每个特征会学习多个隐向量，隐向量的个数就为特征域的个数，不同域的特征组合时使用针对不同域训练的隐向量。
$$?FFM(w,x)=\sum _{j_1=1}^n\sum _{j_2=j_1+1}^n(w_{j_1,f_2}{w}_{j_2,f_1})x_{j_1}{x}_{j_2}$$
其中的 $f$ 代表对应不同的特征域。

4.1 解决优化问题

FFM的优化问题是和LM的优化问题相似的，都是使用随机梯度下降，最近一些自适应学习率方法已经证明能够提升SG的训练过程，我们使用的是AdaGrad，因为现在已经证实这个方法在一些稀疏矩阵上的有效性，特别是对于FFMs的例子。

Trainning FFM using SG

Let G be a tensor of all ones
Run the following loop for t epochs
for i 1...m do
	Sample a data point(y,x)
    cacalate k
    for j1 in 1...n do 
    	for j2 in j1+1...n do
        	calcalate sub-gradient by 5 and 6
            for d in 1...k do 
            Update the gradient sum by 7 and 8
            Update model by 9 and 10

其中 $\eta$ 是用户指定的学习率，初始化的权重w是采用随机采样从一个服从 $【0，\frac{1}{\sqrt{k}}】$ 的均匀分布。

4.2 并行化内存系统

现在的计算是广泛的使用多核进行计算，如果这些和能够充分的利用，训练时间能够大幅度的减少，一些并行化的方法已经提出了使用于SG。本篇论文中，我们讲采用HogWILD方法，这将允许我们不使用任何锁然后使每个线程能够独立的运行。

五、实验

在这个部分，我们首先提供了关于实验的一些详细细节，然后我们研究了了参数对于模型的影响，我们发现FFM是更加敏感的对于epochs的数量比POLY2和LM。

我们又对比了FFMs和其它的模型比如POLY2和FMs，它们都被实现使用相同的SG方法，所以对比它们的训练时间是非常公平的。

5.1 训练设置

• Data Sets

我们主要考虑了两个来自Kaggle比赛中的数据集，分别是Criteo和Avazu，对于特征工程，我们仅仅应用我们获奖的方式，但是移除了一些复杂的部分，例如，我们对于Avazu获奖的策略是集成了超过20个模型，但是这里我们仅仅使用最简单的一个。

对于数据集，测试集的label是不公开的，所以我们将可用的数据集分成了两个部分，分别为训练集和验证集。

• Platform

所有的实验都是在Linux系统下进行，拥有12个物理和在两个Intel Xeon E5-2620 2.0 GHZ处理器和128GB的内存

• 评估指标

对于评估指标，我们使用的是逻辑损失
$$logloss=\frac{1}{m}\sum _{i=1}^{m}log(1+exp(?y_i?(w,x_i)))$$
其中 $m$ 是测试集的样本数

5.2 参数的影响

我们进行了一些实验，来比较参数 $k,\lambda ,\eta$ 对模型的影响。

对于参数k来说，他并不会影响模型效果太多。对于 $\lambda$ ，如果这个值太大，模型是不能获得好的表现得，如果太小的话，模型会得到较好的结果，但是它是极容易或你和的。

对于参数 $\eta$ ，一个较小的参数能够使得FFMs获得最好的表现，但是收敛速度较慢，如果参数过大，FFMs能够快速收敛，但是会产生过拟合的现象。

5.3 提前停止训练

提前停止训练就是当模型达到训练值中最好的效果时，模型停止训练，这样能够去防止过拟合。

1. 将数据分成训练集和验证集
2. 在每个epoch结束的时候，使用验证集去计算损失
3. 如果此时loss上升，那么记录下当时的epoch，停止训练或者执行步骤4
4. 如果需要，使用全部的数据集进行重新训练使用步骤3获得的epoch

使用提前停止最大的困难就是logloss对于epoch的数量是非常敏感的，然后就是在验证集上最好的epoch可能在测试集上表现得不好。

5.4 并行加速

由于并行化SG可能造成一个不同的收敛行为，所以我们进行了实验使用不同数量的线程。

结果表明当线程数目小的时候会有小的加速对于模型训练，但是如果使用太多的进程，模型的训练效率没有提高太多，一个解释就是如果两个或者更多的线程尝试去进入相同的内存，其中一个必须要等待，这就导致了当使用多线程会造成线程之间的冲突。

REFERENCES

[1] O. Chapelle, E. Manavoglu, and R. Rosales, “Simple and scalable response prediction for display advertising,” ACM Transactions on Intelligent Systems and Technology, vol. 5, no. 4, pp. 61:1–61:34, 2015.

[2] H. B. McMahan, G. Holt, D. Sculley, M. Young, D. Ebner, J. Grady, L. Nie, T. Phillips, E. Davydov, D. Golovin, S. Chikkerur, D. Liu, M. Wattenberg, A. M. Hrafnkelsson, T. Boulos, and J. Kubica, “Ad click prediction: a view from the trenches,” in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2013.

[3] M. Richardson, E. Dominowska, and R. Ragno, “Predicting clicks: estimating the click-through rate for new ADs,” in Proceedings of the 16th international conference on World Wide Web, 2007.

[4] Y.-W. Chang, C.-J. Hsieh, K.-W. Chang, M. Ringgaard, and C.-J. Lin, “Training and testing low-degree polynomial data mappings via linear SVM,” Journal of Machine Learning Research, vol. 11, pp. 1471–1490, 2010.

[5] T. Kudo and Y. Matsumoto, “Fast methods for kernel-based text analysis,” in Proceedings of the 41st Annual Meeting of the Association of Computational Linguistics (ACL), 2003.

[6] S. Rendle, “Factorization machines,” in Proceedings of IEEE International Conference on Data Mining (ICDM), pp. 995–1000, 2010.

[7] S. Rendle and L. Schmidt-Thieme, “Pairwise interaction tensor factorization for personalized tag recommendation,” in Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM), pp. 81–90, 2010.

[8] M. Jahrer, A. T¨oscher, J.-Y. Lee, J. Deng, H. Zhang, and J. Spoelstra, “Ensemble of collaborative filtering and feature engineered model for click through rate prediction,” in KDD Cup 2012 Workshop, ACM, 2012.

[9] J. Langford, L. Li, and A. Strehl, “Vowpal Wabbit,” 2007. https: //github.com/JohnLangford/vowpal wabbit/wiki.

[10] J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization,” Journal of Machine Learning Research, vol. 12, pp. 2121–2159, 2011.

[11] H. B. McMahan, “Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization,” in Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS), 2011.

[12] W.-S. Chin, Y. Zhuang, Y.-C. Juan, and C.-J. Lin, “A learning-rate schedule for stochastic gradient methods to matrix factorization,” in Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2015.

[13] F. Niu, B. Recht, C. R′e, and S. J. Wright, “HOGWILD!: a lock-free approach to parallelizing stochastic gradient descent,” in Advances in Neural Information Processing Systems 24 (J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, eds.), pp. 693–701, 2011.

[14] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin, “LIBLINEAR: a library for large linear classification,” Journal of Machine Learning Research, vol. 9, pp. 1871–1874, 2008.

[15] S. Rendle, “Factorization machines with libFM,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 3, no. 3, p. 57, 2012.

[16] L. Dagum and R. Menon, “OpenMP: an industry standard API for shared-memory programming,” IEEE Computational Science and Engineering, vol. 5, pp. 46–55, 1998.

[17] C. M. Bishop, Pattern Recognition and Machine Learning. Springer-Verlag New York, Inc., 2006.

[18] G. Raskutti, M. J. Wainwright, and B. Yu, “Early stopping and non-parametric regression: An optimal data-dependent stopping rule,” Journal of Machine Learning Research, vol. 15, pp. 335–366, 2014.

[19] T. Zhang and B. Yu, “Boosting with early stopping: convergence and consistency,” The Annals of Statistics, vol. 33, no. 4, pp. 1538–1579, 2005.