bandit 算法在推荐系统中的应用

《bandit 算法在推荐系统中的应用》 图片来源:Pexels; 摄影:Flickr;图片授权基于:CCO协议

个性化推荐

随着APP的流行,企业能收集更多更全的用户数据,如何利用这些数据提高收入是各企业都会面临的问题。最常见的方式就是个性化推荐,特别是在电商、视频网站或其它的内容平台。

个性化推荐大体上分为三类。

一是穿插推荐用户的历史行为数据中出现过的商品、转化率或GMV高的商品。这类算法实现起来成本低,能快速上线。

二是利用协同过滤,大致想法是找出与用户A相似度高的一批用户,然后推荐这批用户关注的商品给用户A。将用户和商品的互动行为转化为矩阵,通常来说这个矩阵是个稀疏阵,这会造成用户与用户之间的“距离”约等于0. 常见的方法是通过矩阵分解进行降维处理,这样解决了距离问题但却造成模型的解释性差。

三是利用用户或商品的显性特征,即用户标签或商品标签,直接通过标签来找出相似度高的用户。

Exploit-Explore问题及 bandit算法

个性化推荐确实能给大部分企业带来不少帮助,但有时会出现问题。比如在某些手机浏览器上,我看了一条新闻后,它就不停地给我推荐相关的新闻,也不会考虑到我是否是不小心点到的。这是一个极端情况,但也能说明个性化推荐带来的一个问题,就是推荐的内容类型趋向不变。

这就是推荐系统中的EE(exploit-explore)问题,exploit 指得是根据用户的历史记录推荐出用户的兴趣,然后推荐与之相关的内容,explore 就是指不断探索用户其他兴趣,否则推荐出的结果来来回回都差不多。

解决方法之一就是 Multi Armed Bandit(简记为bandit) 算法,该算法赋予商品(视频/文章)一个 Beta 分布,而不是单一的值。每次排序时通过采样随机获得一个排序值,通过这种随机性来加大商品排序的变动性。但同时beta分布的均值会跟着商品的表现而改变,这样就能对商品进行区分,让表现好的商品有更大的概率获得高排序值,而不会像均匀分布那样每个商品的曝光机率永远保持不变。

为了介绍这个算法,我们来看看必会提到的多臂赌博机问题: 一个赌徒,要去摇老虎机,走进赌场一看,一排老虎机,外表一模一样,但是每个老虎机吐钱的概率不一样,他不知道每个老虎机吐钱的概率分布是什么,那么每次该选择哪个老虎机可以做到最大化收益呢?

解决这个问题的方法就是有策略的快速试一试,而 bandit 算法就是一种有效的方法。

给每台老虎机初始化一个beta分布,其参数为(a=1, b=1),下面是不同参数下的beta分布图像。

由于beta分布的均值为 a/(a+b),所以直观上可以这么理解:相对 b 来说 a 越大,分布就越往1方向移动,即采样后越有可能接近最大值1.

每次先对每台老虑机进行采样,选择采样值最大的那台机器进行投币,每次投币后若获得奖励则让 a+1,否则让 b+1,后续反复进行同样的操作。

若累积足够的次数,你会发现其beta分布的均值实际上会趋近于老虎机吐钱的概率。由于每台机器获得的奖励不同,所以在对每台老虎机采样后,把采样值乘以奖励后得到的值做为选择机器的标准的效果会显著提高。

事实上,若每次获得奖励后让 a 加上奖励值而不是1可以达到类似的效果。理由如下:

我们假设奖励为 R,老虎机吐钱的概率为p,则第一种方式的奖励期望是aR/(a+b), 而第二种的期望是aR/(a*R+b).

由于a*R/(a*R+b)= a*R/(a+b) * (a+b)/(a*R+b).

由于投币次数足够大时 a/(a+b) -> p,我们可以简单的认为 b=a(1/p-1),代入上式即有

a*R/(a*R+b)= a*R/(a+b) * 1/(Rp-p+1)

由于 p、R 都是常数,且在实际生活中都是正数,所以以a*R/(a+b)a*R/(a*R+b)做为排序值,并不会对排序造成影响。

当然在前期,这两种方法会有不同,主要的原因是参数 a、b 值都比较小,采样的波动性也就更大。

bandit 算法在推荐系统中的应用

相比较老虎机,用户和“商品”之间的行为操作会更多,“商品”本身的属性也会更多,我们自行选择那种奖励方式。

我的一个建议是,所有与用户行为有关的数据,比如用户查看、分享、喜欢、下单等指标都以第二种奖励方式来更新beta分布,而商品本身的属性,比如价格则用第一种方式来影响排序值。

商品本身的属性比如价格是会变化的,若用它来影响beta分布本身则会对历史纪录造成影响,而上述方法可以快速适应商品本身的属性的变化。

    原文作者:学习之术
    原文地址: https://www.jianshu.com/p/ed4ce36a422a
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞