文章目录

• 1 CTR简介
• 2 逻辑回归——融合多种特征的推荐模型
• • 2.1 基于逻辑回归的推荐流程
  • 2.2 LR的数学形式
  • 2.3 逻辑回归在推荐上的优劣分析
  • • 1 优势
    • 2 局限
• 3 从FM到FFM——特征自动交叉的解决方案
• • 3.1为什么需要特征交叉？——辛普森悖论
  • 3.2 POLY2模型——特征交叉的开始
  • 3.2 什么是FM
  • • 1 从LFM说起
    • 2 FM解决了POLY2的特征交叉计算问题
    • 3 隐变量的理解
    • 4 梯度下降求参
  • 3.3 FFM模型——引入特征域的概念
  • • 1 域
    • 2 FFM数学表达
    • 3 优缺点
    • 4 使用FFM的注意事项
  • 3.4 POLY2-FM-FFM的联系
• 4 GBDT+LR/FM/FFM

1 CTR简介

CTR(click through rate)，点击率。是用户点击链接的数量和该链接的展现量之比，通常用来衡量网站广告活动是否有效的依据。

CTR起源于计算广告，因为关系到真金白银的定价问题，因此要求预估出来的CTR必须“绝对准确”。这是因为，假如给一个用户准备了A/B/C三个广告，那么无论预测CTR是0.9、0.8、0.6，还是0.5、0.4、0.3都不影响三个广告的展现顺序，但是向客户的收费却有天壤之别。但是推荐系统只要求“相对准确”。（/一般在推荐系统中，2%以上的CTR就算效果不错了）

假如ABC换成了三篇文章，只要能够将用户最喜欢的A排在第1位，次喜欢的B排在第2位，无论我们预测的CTR是0.9、0.8、0.6，还是0.5、0.4、0.3，用户都能接受。看似要求“绝对准确”性，要比“相对准确”，难度更大一些：如果我们能够将用户对每个候选item的CTR都预测准确，那么排序的“相对准确性”自然能够得到保证。但是实际上，“预估CTR”和“排序准确”两个目标存在gap。

2 逻辑回归——融合多种特征的推荐模型

相比协同过滤模型仅利用用户与物品的相互行为信息进行推荐, 逻辑回归模型能够综合利用用户、物品、上下文等多种不同的特征, 生成较为 “全面” 的推荐结果。

通过对推荐问题转换成一个分类问题，预测正样本的概率进行对物品排序，这里正样本可以看作是用户点击物品的概率。

2.1 基于逻辑回归的推荐流程

基于逻辑回归的推荐过程如下。

• (1) 将用户年龄、性别、物品属性、物品描述、当前时间、当前地点等特征 转换成数值型特征向量。
• (2) 确定逻辑回旧模型的优化目标 ( 以优化 “点击率” 为例), 利用已有样本数据对逻辑回归模型进行训练, 确定逻辑回归模型的内部参数。
• (3) 在模型服务阶段, 将特征向量输人逻辑回归模型, 经过逻辑回归模型的 推断, 得到用户 “点击” (这里用点击作为推荐系统正反馈行为的例子) 物品的概率。
• (4) 利用 “点击” 概率对所有候选物品进行排序, 得到推荐列表。

基于逻辑回归的推荐过程的重点在于, 利用样本的特征向量进行模型训练和在线推断。下面着重介绍逻辑回归模型的数学形式、推断过程和训练方法。

2.2 LR的数学形式

关于LR总结

通过Logistic分布的密度函数，一般选用sigmoid函数，将输出映射到（0，1）区间。
f ( z ) = 1 1 + e − z f(z)=\frac{1}{1+\mathrm{e}^{-z}} f(z)=1+e−z1​
通过确定参数w，b就可以得到LR模型：
f ( x ) = 1 1 + e − ( w ⋅ x + b ) f(\boldsymbol{x})=\frac{1}{1+\mathrm{e}^{-(\boldsymbol{w} \cdot \boldsymbol{x}+b)}} f(x)=1+e−(w⋅x+b)1​

LR模型的训练一般选用梯度下降，牛顿法和拟牛顿法。详细可以上面那个博客链接。

2.3 逻辑回归在推荐上的优劣分析

在深度模型兴起之前，逻辑回归模型曾是很长一段时间推荐系统和计算广告的主要选择之一。

1 优势

• 形式上适用多种特征融合
• 可解释性好
  对于不同特征施加权重进行组合，再通过sigmoid函数进行输出，使得每一种结果都可以用参数进行结束。
• 数学原理支撑
  LR作为广义线性模型的一种，假设在于y服从于伯努利分布，那么在 CTR 预估这个问题上, “点击”事件是否发生就是模型的因变量 y y y, 而用户是否点击广告是一个经典的抛硬币问题。因此, CTR 模型的因变量显然应该服从伯努利分布。所以, 采用逻辑回归作为 CTR 模型是符合 “点击” 这一事件的物理意义的。
  与之相比, 线性回归作为广义线性模型的另一个特例, 其假设是因变量 y y y 服从高斯分布, 这明显不是CTR的数学假设。
• 工程化的需要
  因为LR易于并行计算，模型简单，训练花销小，所以在GPU流行之前（2012）,LR在工程领域应用很广泛，即使现在没有其他的模型大大优于LR之前，也没有必要加大资源的投入升级推荐模型。

2 局限

正如其固有的缺陷一般，在推荐上，也具有以下局限

• 模型简单，表达能力不强
• 无法进行特征交叉，特征筛选等操作，因此造成信息的缺失。

为了解决这一问题，模型往复杂的方向进行衍生，诞生了因子分解机模型（FM），在深度学习时代之后，多层神经网络凭借其强大的表达能力也逐渐替代了LR。

3 从FM到FFM——特征自动交叉的解决方案

3.1为什么需要特征交叉？——辛普森悖论

通过特征交叉来面对LR信息丢失的情况，首先通过辛普森悖论来看为什么需要特征交叉组合。

辛普森悖论：对样本分组研究时，分组中占据优势的一方总在总评是失势，这就是辛普森悖论。

举例说明：
在A，B两个视频中，统计如下。
以上可以看出，无论男性还是女性，B的点击率都更高，所以男性女性都应该推荐B。但是如果忽略性别特征，统计如下：
发现汇总后的A视频的总点击率更高，如果根据这个进行推荐，就应该推荐A。这就是辛普森悖论的现象。

第一次计算采用了 性别+视频Id 两个特征计算，第二次采用了 视频id 单一特征计算，所以损失了很多信息，表达能力弱。

而在LR模型中，仅能通过对单一特征进行线性加权，而不能通过交叉组合为高维特征，所以需要特征组合。

3.2 POLY2模型——特征交叉的开始

为了实现特征交叉，在早期，算法工程师使用人工特征交叉，在进行筛选，效率低下，因此便出现了“暴力”的特征交叉，对特征进行两两组合，即PLOLY2.

∅ POLY2 ⁡ ( w , x ) = ∑ j 1 = 1 n − 1 ∑ j 2 = j 1 + 1 n w h ( j 1 , j 2 ) x j 1 x j 2 \emptyset \operatorname{POLY2}(w, x)=\sum_{j_{1}=1}^{n-1} \sum_{j_{2}=j_{1}+1}^{n} w_{h\left(j_{1}, j_{2}\right)} x_{j_{1}} x_{j_{2}} ∅POLY2(w,x)=j1​=1∑n−1​j2​=j1​+1∑n​wh(j1​,j2​)​xj1​​xj2​​

在一定程度上解决了特征交叉的问题，本质上依然是线性模型，有两个明显的缺陷：

• 面对本就稀疏的数据，这样的暴力组合导致数据更加稀疏，权重值不宜收敛
• 权重参数变为 n 2 n^2 n2，增加了训练复杂度。

为了解决POLY2的问题，在2010年，Rendle提出了FM模型

3.2 什么是FM

1 从LFM说起

FM（Factorization Mechine），因子分解机，提出于2010年，但真正的应用于大厂的推荐系统CTR预估问题也就是近几年的事情。

首先我们回顾下隐语义LFM模型，用户u对物品i的喜好程度可以表示为:
R ( u , i ) = p u T q i = ∑ k = 1 K p u , k q i , k R(u, i)=p_{u}^{T} q_{i}=\sum_{k=1}^{K} p_{u, k} q_{i, k} R(u,i)=puT​qi​=∑k=1K​pu,k​qi,k​
如果对用户 u u u 的表征为
X u = [ p u 1 p u 2 ⋯ p u k ] = [ x u 1 x u 2 ⋯ x u k ] X_{u}=\left[\begin{array}{ll}p_{u 1} & p_{u 2} \cdots p_{u k}\end{array}\right]=\left[\begin{array}{ll}x_{u 1} & x_{u 2} \cdots x_{u k}\end{array}\right] Xu​=[pu1​​pu2​⋯puk​​]=[xu1​​xu2​⋯xuk​​]
那么 y u , i = R ( u , i ) = ∑ k = 1 K w k x u k . y_{u, i}=R(u, i)=\sum_{k=1}^{K} w_{k} x_{u k} . yu,i​=R(u,i)=∑k=1K​wk​xuk​.

如果加入截距 w 0 ∈ R w_{0} \in \mathbb{R} w0​∈R ，则有 y u , i = R ( u , i ) = w 0 + ∑ k = 1 K w k x u k . y_{u, i}=R(u, i)=w_{0}+\sum_{k=1}^{K} w_{k} x_{u k} . yu,i​=R(u,i)=w0​+∑k=1K​wk​xuk​.

可见，本质上LFM是一个线性回归模型 ( w 0 = 0 ) \left(w_{0}=0\right) (w0​=0). 与逻辑回归有些相似，不过不是使用可解释的语义描述参数。

2 FM解决了POLY2的特征交叉计算问题

通过将交叉特征加入到线性模型中，就构成了FM模型的基本形式:
y ^ ( x ) = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n w i j x i x j ⏟ Feature Crosses  . \hat{y}(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\underbrace{\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{i j} x_{i} x_{j}}_{\text {Feature Crosses }} . y^​(x)=w0​+i=1∑n​wi​xi​+Feature Crosses  i=1∑n​j=i+1∑n​wij​xi​xj​​​.

在POLY2中，我们解释了交叉特征的权重复杂度提升导致训练复杂，而且交叉特征过于稀疏导致交叉不充分。所以结合隐语义模型的思想，将权重分解为两个隐向量的内积形式：
w i j = ⟨ V i , V j ⟩ : = ∑ f = 1 k v i , f ⋅ v j , f w_{i j}=\left\langle\mathbf{V}_{i}, \mathbf{V}_{j}\right\rangle:=\sum_{f=1}^{k} v_{i, f} \cdot v_{j, f} wij​=⟨Vi​,Vj​⟩:=f=1∑k​vi,f​⋅vj,f​
这样就把 n × ( n − 1 ) n \times(n-1) n×(n−1) 个 w i j w_{i j} wij​ 参数的估计转换成 n n n 个长度为 k k k 个隐向量 V i = ( v i , 1 , v i , 2 , ⋯   , v i , k ) \mathbf{V}_{\mathbf{i}}=\left(v_{i, 1}, v_{i, 2}, \cdots, v_{i, k}\right) Vi​=(vi,1​,vi,2​,⋯,vi,k​) 的估计。这个k维隐向量也就是对应特征的隐向量表示。当然，这里 k < < n k<<n k<<n. 这对于推荐系统实际面对的稀疏数据 问题具有很大意义：我们能观测到的特定用户 u A u_{A} uA​ 的条目消费总是相对于整个网站条目极为有限 的，但是我们可以通过与 u A u_{A} uA​ 消费过同样条目的用户 集 { U A } \left\{U_{A}\right\} {UA​} 对 u A u_{A} uA​ 末消费的条目估计参数。

这种思想来自张量分解:

经过以上分解，得到FM的二阶表达式：
y ^ ( x ) = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n ⟨ V i , V j ⟩ x i x j \hat{y}(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{V}_{i}, \mathbf{V}_{j}\right\rangle x_{i} x_{j} y^​(x)=w0​+i=1∑n​wi​xi​+i=1∑n​j=i+1∑n​⟨Vi​,Vj​⟩xi​xj​

计算可以进一步化简：
∑ i = 1 n ∑ j = i + 1 n ⟨ V i , V j ⟩ x i x j R T = 1 2 ∑ i = 1 n ∑ j = 1 n ⟨ V i , V j ⟩ x i x j − 1 2 ∑ i = 1 n ⟨ V i , V i ⟩ x i x i = 1 2 ( ∑ i = 1 n ∑ j = 1 n ∑ f = 1 k v i , f , v j , f x i x j − ∑ i = 1 n ∑ f = 1 k v i , f , v i , f x i x i ) = 1 2 ∑ f = 1 k ( ( ∑ i = 1 n v i , f x i ) ( ∑ j = 1 n v j , f x j ) − ∑ i = 1 n v i , f 2 x i 2 ) = 1 2 ∑ f = 1 k ( ( ∑ i = 1 n v i , f x i ) 2 − ∑ i = 1 n v i , f 2 x i 2 ) \begin{aligned} & \sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{V}_{i}, \mathbf{V}_{j}\right\rangle x_{i} x_{j} \\RT =& \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n}\left\langle\mathbf{V}_{i}, \mathbf{V}_{j}\right\rangle x_{i} x_{j}-\frac{1}{2} \sum_{i=1}^{n}\left\langle\mathbf{V}_{i}, \mathbf{V}_{i}\right\rangle x_{i} x_{i} \\ =& \frac{1}{2}\left(\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i, f}, v_{j, f} x_{i} x_{j}-\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i, f}, v_{i, f} x_{i} x_{i}\right) \\ =& \frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right)\left(\sum_{j=1}^{n} v_{j, f} x_{j}\right)-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right) \\ =& \frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right) \end{aligned} RT====​i=1∑n​j=i+1∑n​⟨Vi​,Vj​⟩xi​xj​21​i=1∑n​j=1∑n​⟨Vi​,Vj​⟩xi​xj​−21​i=1∑n​⟨Vi​,Vi​⟩xi​xi​21​⎝⎛​i=1∑n​j=1∑n​f=1∑k​vi,f​,vj,f​xi​xj​−i=1∑n​f=1∑k​vi,f​,vi,f​xi​xi​⎠⎞​21​f=1∑k​((i=1∑n​vi,f​xi​)(j=1∑n​vj,f​xj​)−i=1∑n​vi,f2​xi2​)21​f=1∑k​⎝⎛​(i=1∑n​vi,f​xi​)2−i=1∑n​vi,f2​xi2​⎠⎞​​

上式第一行到第二行：对称阵中的上三角元素 与下三角元素相等，减去对角线元素；

3 隐变量的理解

隐向量的引人使 FM 能更好地解决数据稀疏性的问题。举例来说, 在某商品 推荐的场景下, 样本有两个特征, 分别是频道 (channel) 和品牌 (brand), 某训练样本的特征组合是(ESPN, Adidas)。

在 POLY2 中, 只有当 ESPN 和 Adidas 同时 出现在一个训练样本中时, 模型才能学到这个组合特征对应的权重; 而在 FM 中, ESPN 的隐向量也可以通过(ESPN, Gucci)样本进行更新, Adidas 的隐向量也可以通过(NBC, Adidas)样本进行更新, 这大幅降低了模型对数据稀疏性的要求。甚至 对于一个从末出现过的特征组合(NBC, Gucci), 由于模型之前已经分别学习过 N B C \mathrm{NBC} NBC 和 Gucci 的隐向量, 具备了计算该特征组合权重的能力, 这是 POLY2 无法 实现的。相比 POLY2, FM 虽然丢失了某些具体特征组合的精确记忆能力, 但是 泛化能力大大提高。

4 梯度下降求参

在工程方面, FM 同样可以用梯度下降法进行学习, 使其不失实时性和灵活 性。相比之后深度学习模型复杂的网络结构导致难以部署和线上服务, FM 较容 易实现的模型结构使其线上推断的过程相对简单, 也更容易进行线上部署和服 务。因此, FM 在 2012-2014 年前后, 成为业界主流的推荐模型之一。

上述是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，

比如可以采用MSE (Mean Square Error) 损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy 损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。

采用随机梯度下降法SGD求解参数

∂ y ^ ( x ) ∂ θ = { 1 , θ = w 0 x i , θ = w i x i ∑ j = 1 n v i , f x j − v i , f x i 2 , θ = v i , f \frac{\partial \hat{y}(x)}{\partial \theta}=\left\{\begin{array}{c} 1, \theta=w_{0} \\ x_{i}, \theta=w_{i} \\ x_{i} \sum_{j=1}^{n} v_{i, f} x_{j}-v_{i, f} x_{i}^{2}, \theta=v_{i, f} \end{array}\right. ∂θ∂y^​(x)​=⎩⎨⎧​1,θ=w0​xi​,θ=wi​xi​∑j=1n​vi,f​xj​−vi,f​xi2​,θ=vi,f​​

3.3 FFM模型——引入特征域的概念

在FM模型中，特征xi只对应唯一一个隐向量vi，这样在进行计算交叉特征权重时，只使用vi与其他特征的隐向量进行内积。这样导致了一部分信息的丢失，原因在于，假设x1：天气，x2：地点，x3：时间。x1,x2和x1,x3的程度是不同的，只是用同样的v1进行内积导致明显的信息丢失。所以就引出了FFM（Field Factorization Machine）。

1 域

简单理解就是对特征进行分组，每个组就是一个特征域。

例如图1中的例子，这是一个人工的ctr数据集， + 表示展示点击次数， - 表示展示未点击次数，特征值ESPN，Vogue，NBC属于名为Publisher的field，特征值Nike，Gucci，Adidas属于名为Advertiser的filed。为了说明FFM是如何有效work的，我们考虑下面的例子：

在FM中，特征交叉部分的隐向量内积为：

在FFM中，上面公式表达为：
FFM每个特征隐含量都变成一个多维的，与不同域的特征交叉时选择不同的隐含量。

2 FFM数学表达

结合特征域的概念，隐含量进一步表示为：
∑ i = 1 n ∑ j = i + 1 n ⟨ V i , V j ⟩ x i x j → ∑ i = 1 n ∑ j = i + 1 n ⟨ V i , f j , V j , f i ⟩ x i x j \sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{V}_{i}, \mathbf{V}_{j}\right\rangle x_{i} x_{j}\to \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle V_{i, f_{j}}, V_{j, f_{i}}\rangle x_{i} x_{j} i=1∑n​j=i+1∑n​⟨Vi​,Vj​⟩xi​xj​→i=1∑n​j=i+1∑n​⟨Vi,fj​​,Vj,fi​​⟩xi​xj​

FFM总体表达式就是：
y ^ ( x ) = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n ⟨ V i , f j , V j , f i ⟩ x i x j \hat{y}(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle V_{i, f_{j}}, V_{j, f_{i}}\rangle x_{i} x_{j} y^​(x)=w0​+i=1∑n​wi​xi​+i=1∑n​j=i+1∑n​⟨Vi,fj​​,Vj,fi​​⟩xi​xj​

3 优缺点

• FFM优点
  增加field的概念，同一特征针对不同field使用不同隐向量，模型建模更加准确

• FFM缺点：
  计算复杂度比较高，参数个数为 n f k nfk nfk ，计算复杂度为 k n 2 kn^2 kn2

4 使用FFM的注意事项

• 样本归一化，否则容易造成数据溢出
• 特征归一化，消去特征的量纲影响
• early stopping，设置早停策略，不然容易过拟合
• 省略0值特征，即稀疏值，可以提高FFM的训练速度。

3.4 POLY2-FM-FFM的联系

4 GBDT+LR/FM/FFM

首先复习一下GBDT：DT和GBDT