推荐系统三十六式
刑无刀
“贝壳找房”资深算法专家,8年推荐系统工程师
立即订阅
11436 人已学习
课程目录
已完结 39 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 用知识去对抗技术不平等
免费
第1章 概念篇 (3讲)
【概念篇】你真的需要个性化推荐系统吗?
【概念篇】个性化推荐系统那些绕不开的经典问题
【概念篇】这些你必须应该具备的思维模式
第2章 原理篇 (20讲)
【内容推荐】画鬼容易画人难:用户画像的“能”和“不能”
【内容推荐】从文本到用户画像有多远
【内容推荐】超越标签的内容推荐系统
【近邻推荐】人以群分,你是什么人就看到什么世界
【近邻推荐】解密“看了又看”和“买了又买”
【近邻推荐】协同过滤中的相似度计算方法有哪些
【矩阵分解】那些在Netflix Prize中大放异彩的推荐算法
【矩阵分解】Facebook是怎么为十亿人互相推荐好友的
【矩阵分解】如果关注排序效果,那么这个模型可以帮到你
【模型融合】经典模型融合办法:线性模型和树模型的组合拳
【模型融合】一网打尽协同过滤、矩阵分解和线性模型
【模型融合】深度和宽度兼具的融合模型 Wide and Deep
【MAB问题】简单却有效的Bandit算法
【MAB问题】结合上下文信息的Bandit算法
【MAB问题】如何将Bandit算法与协同过滤结合使用
【深度学习】深度学习在推荐系统中的应用有哪些?
【深度学习】用RNN构建个性化音乐播单
【其他应用算法】构建一个科学的排行榜体系
【其他应用算法】实用的加权采样算法
【其他应用算法】推荐候选池的去重策略
第3章 工程篇 (10讲)
【常见架构】典型的信息流架构是什么样的
【常见架构】Netflix个性化推荐架构
【常见架构】总览推荐架构和搜索、广告的关系
【关键模块】巧妇难为无米之炊:数据采集关键要素
【关键模块】让你的推荐系统反应更快:实时推荐
【关键模块】让数据驱动落地,你需要一个实验平台
【关键模块】 推荐系统服务化、存储选型及API设计
【效果保证】推荐系统的测试方法及常用指标介绍
【效果保证】道高一尺魔高一丈:推荐系统的攻防
【开源工具】和推荐系统有关的开源工具及框架介绍
第4章 产品篇 (3讲)
【产品篇】推荐系统在互联网产品商业链条中的地位
【产品篇】说说信息流的前世今生
【团队篇】组建推荐团队及工程师的学习路径
尾声与参考阅读 (2讲)
推荐系统的参考阅读
【尾声】遇“荐”之后,江湖再见
推荐系统三十六式
登录|注册

【MAB问题】结合上下文信息的Bandit算法

刑无刀 2018-04-11
上一篇文章我说到,Bandit 算法用的是一种走一步看一步的思路,这一点看上去非常佛系,似乎一点都不如机器学习深度学习那样厚德载物,但是且慢下结论,先看看我在前面介绍的那几个 Bandit 算法。

UCB 回顾

这些 Bandit 算法,都有一个特点:完全没有使用候选臂的特征信息。特征可是机器学习的核心要素,也是机器学习泛化推广的依赖要素。
没有使用特征信息的 Bandit 算法,问题就在于只能对当前已有的这些候选臂进行选择,对于新加入的候选只能从 0 开始积累数据,而不能借助已有的候选泛化作用。
举个例子,假如有一个用户是鹿晗的粉丝,通过 Bandit 算法有两个鹿晗的广告得到展示,并得到了较好的收益。
那么对于一个新的广告,如果具有鹿晗这个特征,直觉上前两个鹿晗广告的收益信息可以泛化到当前新广告上,新广告就不是完全从 0 开始积累数据,而是有了一定的基础,这样的收敛会更快。
UCB 和汤普森采样这两个 Bandit 算法在实际中表现很好。于是,前辈们就决定送 UCB 去深造一下,让它能够从候选臂的特征信息中学到一些知识。
UCB 就是置信上边界的简称,所以 UCB 这个名字就反映了它的全部思想。置信区间可以简单直观地理解为不确定性的程度,区间越宽,越不确定,反之就很确定。
每个候选的回报均值都有个置信区间,随着试验次数增加,置信区间会变窄,相当于逐渐确定了到底回报丰厚还是可怜。
每次选择前,都根据已经试验的结果重新估计每个候选的均值及置信区间。
选择置信区间上界最大的那个候选。
“选择置信区间上界最大的那个候选”,这句话反映了几个意思:
如果候选的收益置信区间很宽,相当于被选次数很少,还不确定,那么它会倾向于被多次选择,这个是算法冒风险的部分;
如果候选的置信区间很窄,相当于被选次数很多,比较确定其好坏了,那么均值大的倾向于被多次选择,这个是算法保守稳妥的部分;
UCB 是一种乐观冒险的算法,它每次选择前根据置信区间上界排序,反之如果是悲观保守的做法,可以选择置信区间下界排序。

LinUCB

“Yahoo!”的科学家们在 2010 年基于 UCB 提出了 LinUCB 算法,它和传统的 UCB 算法相比,最大的改进就是加入了特征信息,每次估算每个候选的置信区间,不再仅仅是根据实验,而是根据特征信息来估算,这一点就非常的“机器学习”了。
在广告推荐领域,每一个选择的样本,由用户和物品一起构成,用户特征,物品特征,其他上下文特征共同表示出这个选择,把这些特征用来估计这个选择的预期收益和预期收益的置信区间,就是 LinUCB 要做的事情。
LinUCB 算法做了一个假设:一个物品被选择后推送给一个用户,其收益和特征之间呈线性关系。在具体原理上,LinUCB 有一个简单版本以及一个高级版本。简单版本其实就是让每一个候选臂之间完全互相无关,参数不共享。高级版本就是候选臂之间共享一部分参数。
先从简单版本讲起。
还是举个例子,假设现在两个用户,用户有一个特征就是性别,性别特征有两个维度,男,女。现在有四个商品要推荐给这两个用户,示意如下。
两个用户就是 Bandit 算法要面对的上下文,表示成特征就是下面的样子。
每一次推荐时,用特征和每一个候选臂的参数去预估它的预期收益和置信区间。
,这就是给男性用户推荐剃须刀,给女性用户推荐口红,即使是新用户,也可以作出比随机猜测好的推荐,再观察用户是否会点击,用点击信息去更新那个被推荐了的候选臂的参数。
这里的例子还简化了一个地方,就是没有计算置信区间,这是 UCB 的精髓。下面来补上。
假如 D 是候选臂是候选臂在 m 次被选择中积累的特征,相当于就是 m 条样本,特征维度是 d,所以 D 是一个矩阵,维度是 m x d。
这 m 次被选择,每次得到用户的点击或者没点击,把这个反馈信息记录为一个 m x 1 的向量,叫做 C。所以这个候选臂对应的参数就是 d x 1 的向量,d 就是特征维度数,记录为一个戴帽子的西塔,
按照 LinUCB 认为,参数和特征之间线性相乘就应该得到收益:
你看 D 也知道,C 也知道,要求 ,这就很简单了。
但是由于数据稀疏,实际上求参数西塔时不会这样简单粗暴,而是采用岭回归的方法,给原始特征矩阵加上一个单位对角矩阵后再参与计算:
每一个候选臂都像这样去更新它的参数,同时,得到参数后,在真正做选择时,用面对上下文的特征和候选臂的参数一起。
除了估算期望收益,还要计算置信区间的上边界,如果 x 是上下文特征,则期望收益和置信上边界的计算方法分别是下面的样子。
期望收益:
置信区间上边界:
这两个计算结果都是标量数值。置信区间计算公式虽然看起来复杂,实际上反应的思想也很直观,随着被选择次数的增加,也就是 m 增加,这个置信上边界是越来越小的。
每一次选择时给每一个候选臂都计算这两个值,相加之后选择最大那个候选臂输出,就是 LinUCB 了。
刚才说到了岭回归(ridge regression),这里多说一句,岭回归主要用于当样本数小于特征数时,对回归参数进行修正。对于加了特征的 Bandit 问题,正好符合这个特点:试验次数(样本)少于特征数。
信息量有点大,我在这里再一次列出 LinUCB 的重点。
LinUCB 不再是上下文无关地,像盲人摸象一样从候选臂中去选择了,而是要考虑上下文因素,比如是用户特征、物品特征和场景特征一起考虑。
每一个候选臂针对这些特征各自维护一个参数向量,各自更新,互不干扰。
每次选择时用各自的参数去计算期望收益和置信区间,然后按照置信区间上边界最大的输出结果。
观察用户的反馈,简单说就是“是否点击”,将观察的结果返回,结合对应的特征,按照刚才给出的公式,去重新计算这个候选臂的参数。
当 LinUCB 的特征向量始终取 1,每个候选臂的参数是收益均值的时候,LinUCB 就是 UCB。
说完简单版的 LinUCB,再看看高级版的 LinUCB。与简单版的相比,就是认为有一部分特征对应的参数是在所有候选臂之间共享的,所谓共享,也就是无论是哪个候选臂被选中,都会去更新这部分参数。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《推荐系统三十六式》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(6)

  • cyrilliang
    真是越能看到后面的人越少。老师讲得不错,赞一个

    作者回复: 你真相了。

    2018-07-09
    4
  • 范深
    Bandit 的精髓之一就是在没有特征,没有状态的情况下进行选择。如果LinUCB引进来了,说明U-I的特征也有了,这时候能用的算法就很多了,包括DQN等。我理解的对吗?
    2018-06-06
    3
  • 林彦
    简单搜索了下,除了典型的商品和内容推荐,也有人在非工业领域用于搜索更好的游戏策略(蒙特卡罗模拟),更好的短信交互策略提高用户互动目标的完成度。如果更幻想一些,理论上有足够多的数据也可以协助更好地诊断疾病标签和推荐可能更有效的治疗方案(如果医疗机构有意愿积极协作)。
    2018-04-11
    1
    2
  • 老师好。看完您的视频,就能找份推荐的工作了吗?谢谢
    2018-08-06
    1
  • qingyunhe
    哈哈,放心,我会学完的~~ 只不过学到这儿,是我第一个需要课下再消化一下的小节,光那篇论文需要细细研读一遍~~~
    2019-06-12
  • shangqiu86
    讲的很好,就是后面的linUCB感觉是个大工程,需要不断优化不断累积修正特征
    2019-05-05
收起评论
6
返回
顶部