IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 传统推荐算法Facebook的GBDT+LR模型深入理解 -> 正文阅读

[数据结构与算法]传统推荐算法Facebook的GBDT+LR模型深入理解

目标:

深入理解Facebook 2014年提出的的GBDT+LR模型。
CSDN上泛泛而谈的文章很多,真正讲解透彻的没几篇。争取我这篇能讲解透彻。
今晚又想了许久,想通了一些原理。也分享出来。


算法背景:

FaceBook一推出这一模型就引起了业内的轰动,因其设计的巧妙以及预测效果的精良,很多公司一度极力推广,在数据比赛KDD中也经常使用。尽管GBDT+LR依然存在其问题点,但是在当时数据量没有特别大的情况下,这一模型几乎处于横扫千军的状态。
后期模型被不停的优化,于是产出了:XGBoost/GBDT+LR/FM/FFM 等各种组合方式,阿里也在他的DIN模型中提出并弥补了GBDT+LR的缺点。

点击率预估模型(CTR)涉及的训练样本一般是上亿级别,样本量大,模型常采用速度较快的LR(logistic regression)。LR虽然是线性模型线性模型,但是在业界广泛使用。为什么呢?

  • LR虽然模型本身表达能力差,但是可以通过特征工程不断减少问题的非线性结构。
  • LR模型计算复杂度低,可以吞吐超大规模的特征空间和样本集合,这样就为效果优化打开了空间。但正因为LR学习能力有限,此时特征工程尤其重要。

在深度学习大行其道之前,一般采用人工或传统的方法进行特征工程,人工成本高,传统的方法像FM,FFM,只能挖掘两个特征间的特征交互关系,作用有限。GBDT是解决这个问题的一种不错方案。
GBDT有以下优点:

  • 弱分类器要求不高,树的层数一般较小,小数据可用,扩展到大数据也能方便处理。
  • 需要更少的特征工程,比如不用做特征标准化
  • 可以处理字段缺失的数据
  • 可以自动组合多个特征并且不用关心特征间是否依赖,可以自动处理特征间的交互,不用担心数据是否线性可分
  • 可以灵活处理多种类型的异构数据,这是决策树的天然特性
  • 损失函数选择灵活,可以选择具有鲁棒性的损失函数,对异常值有一定的鲁棒性

显而易见,GBDT对于处理特征有很多优点。而LR虽然是线性模型,但是Facebook探索出一种将GBDT和LR结合的方案,来预测广告的点击通过率(Click Trough Rate,CTR)的预测问题。结果显示融合方案比单个的GBDT或LR的性能高3%左右。
推荐系统整体流程:
在这里插入图片描述

算法原理:

点击通过问题,用户要么点击要么不点击,因此 y ∈ ( 0 , 1 ) y∈{(0,1)} y(0,1),是个二分类的问题。
GBDT与LR是如何结合的呢?论文上的一张图:
在这里插入图片描述
如上图所示, t r e e 1 tree1 tree1 t r e e 2 tree2 tree2两棵决策树,组成一个梯度提升树,称之为强学习器。这个强学习器由两个弱学习器前向加和组成。假设 x x x输入GBDT后,落到左边回归树的第一个节点,落到右边回归树的第一个节点。则GBDT对样本 x x x的特征进行工程处理得到的转换特征,就可以表示为: ( 1 , 0 , 0 ) (1,0,0) (1,0,0)串联 ( 1 , 0 ) (1,0) (1,0) => ( 1 , 0 , 0 , 1 , 0 ) (1,0,0,1,0) (1,0,0,1,0)。然后将拼接后的特征输入LR即可进行分类。

理解算法:

  • 树的叶子节点表示的是用户最终是点击(label:1)还是不点击(label:0),根节点表示一个特征判断。
    在这里插入图片描述
    可以看到,线性模型LR,就是学习所有通过不同特征进行预测结果 ( 0 / 1 ) (0/1) (0/1)的权重,也就是投票时各个判断标准所占的比重。
  • GBDT决策树是如何产生的呢?
    这里要结合Boosting的逻辑详细解释一下这个模型,论文的图形过于抽象。
    在这里插入图片描述
    上图中我们看到GBDT中每一次迭代产生的叶子节点都会被输入到LR中,假如每个弱学习器有10个叶子节点,同时循环60次,则输入到LR中的节点数量即为600个,这600个节点中既涵盖了低阶单维度的特征(通过某一个特征就进行了判断),也包含高阶复合维度的特征(通过某多层特征才进行了判断),越往下的学习器,特征融合效果越好。因为GBDT结合残差网络的思想,逐渐缩小预测误差。
    我们将boosting的结构划归到GBDT项下,得到更直观的图形为:

在这里插入图片描述
在这里插入图片描述
参考资料:

  • 为什么要使用集成的决策树模型,而不是单棵的决策树模型?

    • 其一:一棵树的表达能力很弱,不足以表达多个有区分性的特征组合,多棵树的表达能力更强一些。

    • 其二:GBDT是Boosting的经典算法,因其不停的迭代,对数据特征有深度融合的效果,高效组合多个特征,比人工筛选特征组合更高效全面。思想类似于残差网络。

  • 为什么建树采用GBDT而非RandomForest?

    • 其一:RF也是多棵树,但从效果上有实践证明不如GBDT。RF思想是多棵树在最后投票的权重一样,如果LR再使得每个树结果的权重不一样,可能和训练RF的初衷相悖。

    • 其二:GBDT在迭代过程中,前面的树特征分裂主要体现对多数样本有区分度的特征,后面的树,主要体现的是经过前N颗树,残差仍然较大的少数样本,优先选用在整体上有区分度的特征,再选用针对少数样本有区分度的特征,思路更加合理。另外,GBDT本来每棵树的权重就不一样,然后用LR让每个树的叶子节点的权重都不一样,这样理论上增加了GBDT的区分度,感觉更加提升了GBDT的效果。粒度从一个树提升到一个叶子节点。这应该也是用GBDT的原因。
      实验也证明,RF效果和GBDT效果差。

  • 为什么要将GBDT与LR融合?而不是GBDT+MLP?

    • GBDT+LR融合是Stacking思想的成功应用,上文中描述了GBDT的优势,但是由于其树状特性,数据敏感度较高,部分数据的调整会引发整体类别的变化,可处理数据量有限,需要一个相对比较钝化的模型来提升泛化性能。LR模型被发觉出来,LR模型的并行能力很强,能够处理较大的数据集,同时只能处理一维的特征,学习能力有限,需要大量的特征工程。

这两个模型的优缺点整合后发现,两者刚好可以互补,因此,成就了这一经典。

  • 为什么不是GBDT+MLP?MLP拟合能力比较强,为啥不是强强联手?

    • 首先,经过GBDT产生的多棵树,然后把叶子节点进行拼接层一个长长的一维向量,极大的增大了特征值,也称为特征增广。比如包含3个特征的输入向量 x = [ x 1 , x 2 , x 3 ] x={[x_1,x_2,x_3]} x=[x1?,x2?,x3?],理论上产生一棵完全二叉树,能有8个叶子节点。如图:

    在这里插入图片描述
    而GBDT模型还要产生N棵这样的树组成一个决策树群,所以理论上,叶子节点树目为 2 i ? N 2^i*N 2i?N个叶子结点, i i i为特征的数目,也就是 X X X的维度,这个数量之多,想想就可怕。
    这么多叶子节点组成的一维向量,送去MLP,会有非常多的参数需要训练(单个神经元就需要训练一个k和b),而且叶子节点组成的一维向量非常稀疏,大部分都是0,少数1,甚至一些特征位上,一直都是0,导致该特征对应的权重都无法进行训练。所以送去MLP不可行。

  • MLP一般会进行特征工程进行特征压缩和特征值稠密化,比如embeding,PCA等等,目的就是减少特征值的维度,减小特征矩阵的稀疏性,而GBDT的操作过程是特征增广,和MLP的特征工程刚好相反,所以不适合MLP。


GBDT+LR缺点:

模型也有一定的缺点

缺点:
1、 无法获得物品和用户的ID类特征,也就是ID对应的embeding向量。

  • 怎么理解这句话?现代的推荐系统中,对物品或者用户的ID特征非常重要,它往往就能代表这个物品间的关联关系。而这个ID并不是直接作为数值进行模型训练,比如我们在常规的机器学习里面,基本就是简单的丢掉ID这一列,因为ID是随机分配的,和最终的label没有任何关系。
  • 物品ID应该怎样用呢?是利用用户的历史行为,通过类似Word2Vec的方式生成用户embeding,一定程度上能表示物品间的关系。比如,用户购买产品1后,基本都会购买产品2,这样产品ID=1的embeding向量,会非常接近产品ID=2的embeding向量。此时,我们通过物品的embeding向量相似度,就能进行相关物品推荐了,这个embeding就是通过产品ID得到的,蕴含了丰富的信息,如果直接丢弃掉ID,则直接摒弃掉了物品间的相互关系,显然模型的准确度会大大下降。

2、离线处理和在线处理都比较复杂。需要把多棵树丢到线上去,然后遍历,拼装特征,然后线性推断,比较麻烦。

3、 离线训练容易过拟合,因为GBDT本身就容易过拟合。

  • 怎么理解?链接里有说道:高维稀疏特征的时候,lr 的效果会比 gbdt 好,使用 gbdt 很容易过拟合。
    • 首先讲一个 case : 假设有1w 个样本, y y y类别0和1,100维特征,其中10个样本都是类别1,而特征 f 1 f_1 f1?的值为0,1,且刚好这10个样本的 f 1 f_1 f1?特征值都为1,其余9990样本都为0(在高维稀疏的情况下这种情况很常见)。在树模型的时候,很容易优化出含一个使用 f 1 f_1 f1?为分裂节点的树直接将数据划分的很好,但是当测试的时候,却会发现效果很差,因为这个特征只是刚好偶然间跟 y y y拟合到了这个规律,这也是我们常说的过拟合。但是当时我还是不太懂为什么线性模型就能对这种 case 处理的好?照理说 线性模型在优化之后不也会产生这样一个式子: y = W 1 ? f 1 + W i ? f i + . . . . y = W1*f1 + Wi*fi+.... y=W1?f1+Wi?fi+....,其中 W1特别大以拟合这十个样本吗,因为反正 f 1 f1 f1的值只有0和1,W1过大对其他9990样本不会有任何影响。 后来思考后发现原因是因为现在的模型普遍都会带着正则项,而 lr 等线性模型的正则项是对权重的惩罚,也就是 W 1 W1 W1一旦过大,惩罚就会很大,进一步压缩 W 1 W1 W1的值,使他不至于过大,而树模型则不一样,树模型的惩罚项通常为叶子节点数和深度等,而我们都知道,对于上面这种 case,树只需要一个节点就可以完美分割9990和10个样本,惩罚项极其之小,这也就是为什么在高维稀疏特征的时候,线性模型会比非线性模型好的原因了:带正则化的线性模型比较不容易对稀疏特征过拟合。

LR:

最简单的是逻辑回归(Logistic Regression),一个广义线性模型。

拿某user的用户画像(一个向量)比如 [ 3 , 1 ] [3, 1] [3,1],拼接上某item的物品画像比如 [ 4 , 0 ] [4, 0] [4,0],再加上代表context的向量 [ 0 , 1 , 1 ] [0, 1, 1] [0,1,1]后得到 x = [ 3 , 1 , 4 , 0 , 0 , 1 , 1 ] x=[3, 1, 4, 0, 0, 1, 1] x=[3,1,4,0,0,1,1],若该user曾与该item发生过联系则 l a b e l label label为1,这些加起来是一个正样本,同时可以将用户“跳过”的item或热门的却没有与用户产生过联系的item作为负样本, l a b e l label label为0,拟合如下方程:
y = 1 1 + e ? ( w T x + b ) y=\frac{1}{1+e^{-(w^{T}x+b)}} y=1+e?(wTx+b)1?

其中 x x x即为上述向量, w w w是与 x x x每个元素相对应的权重, b b b为截距。其损失函数为:在这里插入图片描述
其中为样本的 l a b e l = 0 或 1 label=0或1 label=01,是根据模型预测的0到1之间的数字。

通过降低此损失函数来拟合训练样本来完成模型的训练,利用模型对新的数据进行预测即完成了打分。训练过程参考sklearn的LogisticRegression很容易完成。

传统的LR只能在线下批量处理大量数据,无法有效处理大规模的在线数据流。模型更新可能要一天甚至更多,不够及时。

代码部分

代码部分下篇再说。此篇够长了。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-11-12 19:50:47  更:2021-11-12 19:52:25 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 10:26:02-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码