看gbdt的时候突然看到人家对Facebook Ads的点击预测数据的一个实战论文。很多地方都蛮有通用性的,就记下来一些重点。

整体流程

整体流程大概就是这个样子,说白了也就是用Tree来做feature transform,然后用线性分类器处理。论文当中用的是probit regression,不过现在做CTR的好像Factorization Machine的更多一点。

Decision tree feature transforms

其实整体的方法很简单,用原始的特征训练GBDT,得到的N棵高度为H的树,N和H应该都是你可以设的参数。然后,再拿每一棵树去预测数据的时候,每个数据点,必然会掉到具体的一个叶子,这样就能得到一个二进制的编码了。这样维度变为\(N*2^H\)

比如

这里,就是3棵深度为2的树,所以就有12维,对于落到红色节点的数据就变成了,\(<1,0,0,0,0,0,0,1,0,0,1,0>\)

其实,决策树本来就是学习特征组合的策略,每一条从根节点到叶节点的路径都可以看做是一条复合规则,所以GBDT可以看做一种有监督的学习策略组合的方法。

平时我们在特征过少的时候,会选择手动组合特征,直接弄个加减乘除什么的。这里GBDT就从另外一个角度做了这件事。(恩,特征hash什么的也不是不可以)

GBDT with Regularization

论文里面采用的是带有正则的GBDT,常用的有shrinkagesubsampling这两种。其中subsampling是在各种学习方法都常见的策略,每次不用完整的数据,而是使用采样的部分数据学习。

至于shrinkage其实就是在计算当前模型的时候,为每棵树填入一个\(0 \lt \eta \lt1\)的权重因子,也称为学习率,其实这也很好理解,我之前写的关于GBDT的文章中提到我的理解,依靠每科决策树学习方向,然后通过拟合残差学习步长,这里就给步长一个惩罚项,以减少步长,从而减少过拟合的可能性。

Factorization Machine

一般来说,线性模型

\[\phi(w, x) = W^TX = \sum_{j }w_jx_j\]

如果我们手动把二阶的项构造出来

\[\phi(w, x) = w_0 + \sum_{i}w_ix_i + \sum_{j_1, j_2}w_{j_1, j_2}x_{j_1}x_{j_2}\]

但是这样其实也就是假设存在一个大的方阵W作为二阶项的权值。我们想处理稀疏的问题,于是就假设这个W是有一个k*N矩阵\(V\)通过\(V^T*V\)构成的。所以就变成了

\[\phi(w, x) = w_0 + \sum_{i}w_ix_i + \sum_{j_1, j_2}<w_{j_1,}w_{j_2}>x_{j_1}x_{j_2}\]

这个就是最常见的FM。

但是进一步,对于每一个特征,我们使用一个向量\(w_i\)来学习他的latent effect是不是足够呢?或者这么说,我们的特征向量X,本身不同列也有不同的类别的属性,比如作者在论文中的例子

这里作为出版社ESPN与作为广告商的Nike和性别Male这两者之前的latent effect应该是显然不同的。所以对此,把ESPN的一个向量变成\(w_{ESPN,A}\)\(w_{ESPN,G}\)两个向量,对不同类型的数据应该是有不同的向量成绩得到的。这里就应该是

\[w_{ESPN,A}*w_{Nike,P}+w_{ESPN,G}*w_{Male, P}+w_{Nike,G}*w_{Male, A}\]

这样,变量的大小有原来的nk变成了nfk

由于,FM本质上还是一个线性模型的一部分,所以我们可以把这部分扔到广义线性模型上面,比如FFM for Logistic Loss这种东西,顺便还能加上各种正则项。

不过,FFM容易过拟合也是真的,所以作者本身 也提供了early stopping这种方法来防止过拟合。




X