CTR预估模型演进笔记

一、理论

I、前深度学习时代

一、Logistic Regression，LR

1. 逻辑回归的数学基础

逻辑回归作为广义线性模型的一种，假设 $y$ 服从伯努利分布。

其概率质量函数为：
$f_{X}(x)=p^{x}(1-p)^{1-x}=\left\{\begin{array}{ll} p & \text { if } x=1 \\ q & \text { if } x=0 \end{array}\right.$

在点击率预估这个问题上，“点击”这个事件是否发生，就是模型的因变量 $y$ 。
$\cdot x+b=\sum_{i} w_{i} x_{i}+b$

$\sigma(z)=\frac{1}{1+\exp (-z)}$

其中 Sigmoid 函数如下图所示：

其中， $x$ 是输入向量， $w$ 是需要学习的参数。对于CTR模型而言， $x$ 就是输入的特征， $\sigma(z)$ 就是预估的点击率。

2. 逻辑回归的可解释性

直观而言，逻辑回归就是将各个特征加权求和，而后加上 Sigmoid 函数。各个权重 $w_i$ 表征不同特征的重要程度，Sigmoid 函数是为了将值映射到 0-1 之间，使其符合点击率预估的物理意义。

所以逻辑回归具有极强的可解释性，可以解释哪些特征比较重要，哪些比较次要，在CTR预估出现偏差的时候，能够找到影响结果的因素。

3. 工程化的需要

在GPU还未流行之时，LR 具有并行化、模型简单、训练开销小等特点。

二、POLY2——特征交叉的开始

由于LR仅仅使用了单一的特征，没有学到特征之间的联系。

比如“男性”和“体育用品”之间的联系更大，“女性”和“时尚用品”的联系更大。因此需要关注特征之间的交叉特征。最开始的时候，工程师使用手动组合特征的方法，但是人工经验是有局限性的。POLY2 采用了对特征进行二阶的 “暴力”组合：

$\phi_{\mathrm{Poly} 2}(\boldsymbol{w}, \boldsymbol{x})=\sum_{j_{1}=1}^{n} \sum_{j_{2}=j_{1}+1}^{n} w_{h\left(j_{1}, j_{2}\right)} x_{j_{1}} x_{j_{2}}$

在上面的POLY2的二阶部分的目标函数中（上式省略了一阶部分和sigmoid函数的部分），可以看到其对所有特征都进行了两两交叉，并对所有特征的组合，都赋予了新的权重 $w_{h\left(j_{1}, j_{2}\right)}$ 。

POLY2 通过暴力组合特征在一定程度上解决了特征组合的问题。而且由于本质上仍然是线性模型，训练方法和 LR 并无区别，便于工程上的兼容。

缺点：

1、互联网数据的特征用 one-hot 表达时，往往有千万甚至亿级别的维度，特征非常稀疏（就是one-hot 向量中仅有少数元素是 1，其余均为 0）。POLY2 进行无选择的特征交叉会使得交叉特征更加稀疏，使得大部分交叉特征的权重缺失，导致无法收敛。

关于此结论，是由于 LR 的更新公式中， $w_{i}:=w_{i}+\alpha(y-\hat{y}) x_{i}$ ，（这里的 $x_i$ 等价于特征交叉项 $x_{j_{1}}x_{j2}$ ）。可见，参数的更新和这个参数组合项的值直接相关。当这里的 $x_i$ 取值为0时，参数 $w_i$ （这里的 $w_i$ 等价于特征交叉项的参数 $w_{h\left(j_{1}, j_{2}\right)}$ ）就无法得到更新，而 $x_i$ 要非零就要求交叉特征的两项 $x_{j_{1}}$ 和 $x_{j2}$ 都要非零，但实际在数据高度稀疏，一旦两个特征只要有一个取 0，参数 $w_i$ 不能得到有效更新；

除此之外，对于训练集中没有出现的交叉特征，也没办法学习这类权重，泛化性能不够好。

比如：某一项 $w_{h\left(j_{1}, j_{2}\right)}x_{j_{1}}x_{j2}$ 中， $x_{j1}=[1,0,0,0...]$ ， $x_{j2}=[0,1,0,0...]$ ，这样乘起来以后，整项都变成了 0 ，那么权重参数 $w_{h\left(j_{1}, j_{2}\right)}$ 就无法更新了。

2、由上述公式，再加上一阶部分，总的权重参数的数量 $O(n)+O(n^2)=O(n^2)$ ，增加了训练的复杂度

三、FM——隐向量特征交叉

为了解决 POLY2 模型的缺点，2020年德国的 Steffen Rendle 提出了FM (Factorization Machine)。 FM的公式包含了一阶线性部分与二阶特征交叉部分：

$y_{\mathrm{FM}}(\boldsymbol{x}):=\operatorname{sigmoid}\left({ } w_{0}+\sum_{i=1}^{N} w_{i} x_{i}+\sum_{i=1}^{N} \sum_{j=i+1}^{N}\left\langle\boldsymbol{v}_{i}, \boldsymbol{v}_{j}\right\rangle x_{i} x_{j }\right)$

在这里，将上面POLY2的特征交叉项的权重参数 $w_{h\left(j_{1}, j_{2}\right)}$ 分解为了两个隐向量 $\boldsymbol{v}_{i}$ 和 $\boldsymbol{v}_{j}$ 的内积， $\left\langle\boldsymbol{v}_{i}, \boldsymbol{v}_{j}\right\rangle$ 。也就是说，每个特征 $x_i$ 除了需要训练一个一阶的权重参数 $w_i$ ，还需要额外训练一个隐向量 $\boldsymbol{v}_{i}$ ，这个向量长度为 $k$ 。

$\boldsymbol{v}_{i}$ 是第 $i$ 维特征的隐向量，长度 $k < < n$ ，包含 $k$ 个描述特征的因子。在交叉项*** $n$ 个特征，每个特征有一个隐向量，每个向量长度为 $k$ ，所以交叉部分参数个数为 $k * n$ 。

优点：

1. 打破了交叉特征权重间的隔离性

通过将特征隐射到 $k$ 维空间求内积的方式，打破了交叉特征权重间的隔离性（break the independence of the interaction parameters），增加模型在稀疏场景下学习交叉特征的能力。一个交叉特征参数的估计，可以帮助估计其他相关的交叉特征参数。

例如，假设我们有交叉特征 gender=male & movie_genre=war，我们需要估计这个交叉特征前的参数 $w_\text{male and war}$ ，FM通过将 $w_\text{male and war}$ 分解为 $\left\langle v_{\text {male}}, v_{\text {war}}\right\rangle$ 的方式进行估计，那么对于每次更新male或者war的隐向量 $v$ 时，都会影响其他与 male 或者 war 交叉的特征参数估计，使得特征权重的学习不再互相独立。这样做的好处是，对于 train data set 中没有出现过的交叉特征，FM仍然可以给到一个较好的非零预估值。

2. 隐向量的引入还使得FM比POLY2能够更好的解决数据稀疏性的问题 & 提高泛化能力

举例来说，我们有两个特征，分别是channel和brand，一个训练样本的feature组合是(ESPN, Adidas)，在POLY2中，只有当ESPN和Adidas同时出现在一个训练样本中时，模型才能学到这个组合特征对应的权重。而在FM中，ESPN的隐向量也可以通过(ESPN, Gucci)这个样本学到，Adidas的隐向量也可以通过(NBC, Adidas)学到，这大大降低了模型对于数据稀疏性的要求。甚至对于一个从未出现过的特征组合(NBC, Gucci)，由于模型之前已经分别学习过NBC和Gucci的隐向量，FM也具备了计算该特征组合权重的能力，这是POLY2无法实现的。也许FM相比POLY2丢失了某些信息的记忆能力，但是泛化能力大大提高，这对于互联网的数据特点是非常重要的。

3. 参数数量降低

$O (k * n)$

缺点：

2-way的FM仅枚举了所有特征的二阶交叉信息，没有考虑高阶特征的信息

四、FFM——引入特征域概念

FFM（Field-aware Factorization Machine）是Yuchin Juan等人在2015年的比赛中提出的一种对FM改进算法，主要是引入了field概念，即认为每个feature对于不同field的交叉都有不同的特征表达。FFM相比于FM的计算时间复杂度更高，但同时也提高了本身模型的表达能力。FM也可以看成只有一个field的FFM

$\phi_{\mathrm{FFM}}(\boldsymbol{w}, \boldsymbol{x})=\sum_{j_{1}=1}^{n} \sum_{j_{2}=j_{1}+1}^{n}\left(\boldsymbol{w}_{j_{1}, f_{2}} \cdot \boldsymbol{w}_{j_{2}, f_{1}}\right) x_{j_{1}} x_{j_{2}}$

上式是FFM的目标函数的二阶部分。其与 FM 目标函数的区别在于隐向量由原先的 $w_{j1}$ 变成了 $w_{j_{1}, f_{2}}$ ，这意味着，每个特征不仅仅对应一个隐向量，而是对应着一组隐向量，这个组的大小，等于域 $f$ 的数量。当 $x_{j1}$ 与特征 $x_{j2}$ 进行交叉时， $x_{j1}$ 特征会从一组隐向量中挑出与特征 $x_{j2}$ 的域 $f_2$ 相对应的隐向量 $w_{j_{1}, f_{2}}$ 进行交叉。同理，特征 $x_{j2}$ 也会用与 $x_{j1}$ 的域 $f_1$ 所对应的隐向量进行交叉。