推荐系统EE(exploit-explore)问题概述

2018年4月23日09:27:49 发表评论 1,203

上一篇:矩阵分解如何解决隐式反馈(预测行为)

推荐系统中有一个经典的问题就是 EE (exploit-explore)问题,EE 问题有时也叫多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB),简单来说,EE 问题解决的是选择问题。

MAB 问题简介

先来介绍下 MAB(Multi-armed bandit problem,多臂赌博机) 问题,有一个赌博机,一共有 k 个摇臂,玩家每次投一个游戏币后可以按一个摇臂,每个摇臂按下后都有可能吐出硬币作为奖励,但是每个摇臂吐出硬币的概率分布是未知的,玩家的目标是获得最大化的累积奖赏。

MAB 中的每个摇臂都是一个选项,所以它其实是一个选择问题,如果想要获得最大化的累积奖赏,最好的办法就是试一试,但是不能盲目的去试,而是有策略的试一试,这些策略就是bandit算法。

推荐系统中的 EE 问题

将场景回到推荐系统上,推荐系统中也存在很多类似于 MAB 的问题,这些问题在推荐系统中叫做 EE(exploit-explore)问题,exploit 直译就是开采,利用已知的比较确定的用户的兴趣,然后推荐与之相关的内容,explore 直译就是探索,除了推荐已知的用户感兴趣的内容,还需要不断探索用户其他兴趣,否则推荐出的结果来来回回都差不多。

实际上,推荐系统中有很多与之类似的场景和问题:

  • 假设一个用户对不同类别的内容感兴趣程度不同,那么我们的推荐系统初次见到这个用户时,怎么快速地知道他对每类内容的感兴趣程度?这就是推荐系统的冷启动。
  • 假设我们有若干广告库存,怎么知道该给每个用户展示哪个广告,从而获得最大的点击收益?是每次都挑效果最好那个么?那么新广告如何才有出头之日?
  • 算法工程师开发了一个新模型,有没有比A/B test更快的方法知道它和旧模型相比谁更靠谱?
  • 如果一直推荐已知的用户感兴趣的物品,可能会造成用户的兴趣偏好范围(视野)越来越窄,如何才能科学地冒险给他推荐一些新鲜的物品?

Bandit 算法介绍

Bandit 算法并不是指某一个算法,而是指某一类算法,想要比较不同 Bandit 算法之间的优劣,可以使用累积遗憾来衡量。累积遗憾的计算公式如下:

R_{T} = \sum_{i=1}^{T}(w_{opt} - w_{B(i)})

T表示总共的选择次数,RT 表示经过 T 次选择后的累积遗憾,Wopt表示在每次选择时选择了最好的臂所获得的收益,WBi 表示每次选择时实际所选的臂所带来的收益,两者的差就是当次的遗憾。

为了简化 MAB 问题,每个臂的收益不是 0,就是 1,也就是伯努利收益。

所以如果想要比较不同的 Bandit 在同一个 MAB 问题上的表现,只需要收集每个算法经过 T 次后的累积遗憾,累积遗憾越少,表示该算法效果越好。

Bandit 算法的套路就是:小心翼翼地试,越确定某个选择好,就多选择它,越确定某个选择差,就越来越少选择它。

如果某个选择实验次数较少,导致不确定好坏,那么就多给一些被选择机会,直到确定了它是金子还是石头。简单说就是,把选择的机会给“确定好的”和“还不确定的”。

Bandit 算法中有几个关键元素:臂,回报,环境。

  • 臂:指每次选择的候选项,有几个选项就有几个臂。
  • 回报:就是选择一个臂之后得到的奖励,比如选择赌博机后吐出来的硬币。
  • 环境:就是决定每个臂不同的那些因素,统称为环境。

将以上的关键元素对应到推荐系统中。

  • 臂:指每次推荐的候选项,可以是具体物品,也可以是物品类别,也可以是推荐策略和算法。
  • 回报:指用户对推荐的结果是否满意。
  • 环境:指给当前用户推荐时的所有周边环境。

Bandit 算法需要注意的问题

想要解决 EE 问题,可以使用 Bbandit 算法,但是使用 Bandit 算法需要注意一些问题,如果不考虑这些问题,直接在一些场景中使用 Bandit 算法,得到的结果可能会很差。需要注意的问题主要有两个:

  1. 相对少量的优质物品
  2. 非常大的用户量

在使用 Bandit 算法时,如果物品的质量良莠不齐,并且物品的数量较多,在曝光位置非常有限的情况下,优质资源想要尽快展示出来的可能性不高,因为这时候系统还无法对大多数物品还是不确定的态度,还需要做更多的探索(explore)

用户量如果小的话,无法产生大量的用户交互行为,算法无法快速收敛到稳定方案。另外,如果物品的质量差的话,用户的体验可能会很差,这样也会减少用户与物品的交互行为。

无论使用哪种 Bandit 算法,在短期内都会对用户的体验有一定的影响,所以需要注意减少这种影响。

总结

这里先介绍了下推荐系统中 EE 问题的由来,然后介绍了解决该问题的 Bandit 算法,并且提出了在应用 Bandit 算法时需要注意的问题。实际上,Bandit 算法是一种不太常用在推荐系统的算法,究其原因,是它能同时处理的物品数量不能太多。但是,在冷启动和处理 EE 问题时,Bandit 算法简单好用,值得一试。

推荐系统百问百答

  • 个人微信号
  • 添加时请备注“脑洞大开读者”
  • weinxin
  • 微信公众号
  • 关注会有更多精彩内容!
  • weinxin

发表评论

您必须登录才能发表评论!