17 | 结合上下文信息的Bandit算法
刑无刀
该思维导图由 AI 生成，仅供参考
上一篇文章我说到，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/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
LinUCB算法是一种上下文相关的Bandit算法，通过加入候选臂的特征信息，使得算法能够更快地收敛，处理动态的推荐候选池，并且能够独立更新参数。文章介绍了LinUCB算法的构建特征过程，包括对用户和物品特征的工程化处理和降维方法。该算法的优点包括收敛速度快、参数独立更新、处理动态推荐候选池，适用于推荐框架、广告投放和兴趣标签选择等应用场景。然而，LinUCB算法也存在缺点，即不能同时处理过多的候选臂，因为计算代价会变得不可接受。总的来说，LinUCB算法为Bandit算法在实际应用中提供了重要思路，是一个值得关注和应用的推荐算法。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《推荐系统三十六式》，新⼈⾸单¥59
《推荐系统三十六式》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(12)
- 最新
- 精选
cyrilliang真是越能看到后面的人越少。老师讲得不错，赞一个作者回复: 你真相了。
2018-07-0925
范深Bandit 的精髓之一就是在没有特征，没有状态的情况下进行选择。如果LinUCB引进来了，说明U-I的特征也有了，这时候能用的算法就很多了，包括DQN等。我理解的对吗？2018-06-065
林彦简单搜索了下，除了典型的商品和内容推荐，也有人在非工业领域用于搜索更好的游戏策略(蒙特卡罗模拟)，更好的短信交互策略提高用户互动目标的完成度。如果更幻想一些，理论上有足够多的数据也可以协助更好地诊断疾病标签和推荐可能更有效的治疗方案(如果医疗机构有意愿积极协作)。2018-04-1114
在西伯利亚森林养猫ψu=ϕuT W 这个公式可以详细讲讲吗，构建特征工程哪儿没有明白2020-10-261
Austin感觉就是矩阵分解呀2019-12-171- 星老师好。看完您的视频，就能找份推荐的工作了吗？谢谢2018-08-0641
- dtttt老师好，如何从 LinUCB 的置信区间上边界的公式得出 m 越大，其置信区间越小的呢？2021-06-27
全利用context 特征，并且将用户和臂的特征进行相似性计算(这里可以有很多方式，线性，双线性，cos，模型）作为最后的收益。2021-03-27- 全感觉linucb 也可以做用户粗粒度画像2021-03-23
- Austin没讲清楚，都有这么多数据积累了，干嘛不直接用LR2019-12-172
收起评论
