脑洞科技栈

标签: | 发表时间:2018-05-18 08:47 | 作者:
出处:https://mp.weixin.qq.com

推荐阅读时间:10min~12min

主题:如何使用Bandit算法解决EE问题


生活中你可能会遇到类似的情况,你在网上购买了手机,淘宝之后会不断给你推送关于手机相关的商品;如果你看了关于NBA詹姆斯的相关新闻,今日头条之后会不断给你推送詹姆斯的新闻。时间长了,你会发现你的世界里只有手机和詹姆斯,天呐,世界越来越小,视野越来越窄怎么办?

别担心,上面的这种情况就属于EE问题的一种,更多的关于什么是推荐系统的EE问题可以参见: 推荐系统EE(exploit-explore)问题概述。针对 EE 问题,可以使用 Bandit 算法来解决。这里介绍一些常用的 Bandit 算法。

Naive


Naive 的核心就在于朴素,它的做法就是先进行 N 次尝试,然后统计每个臂的平均收益,接下来一直选择平均收益最大的臂。这个算法是人们在实际中最常采用的。

Epsilon-Greedy(ε-Greedy)


Epsilon-Greedy 通过生成一个 (0,1) 范围内的数字 ε ,用它来表示概率,表示以 ε 的概率去从所有候选臂中随机选择一个,也就是 explore,以 1- ε 的概率去选择平均收益最大的臂,也就是 exploit。

通过 ε 的值可以控制对 explore 和 exploit 的权衡程度, ε 值越小,表明 explore 越保守,会有更好的稳定性。

很明显 ε 数值的确定是一件不容易的事情。

Thompson Sampling(汤普森采样)


介绍汤普森采样之前,可以先来介绍一个分布:beta 分布。beta 分布可以看作一个概率的概率分布,当你不知道一个东西的具体概率是多少时,它可以给出了所有概率出现的可能性大小。

beta 分布有两个控制参数:α 和 β 。先来看下几个 beta 分布的概率密度函数的图形:

beta 分布图形中的 x 轴取值范围是 (0,1),可以看成是概率值,参数 α 和 β 可以控制图形的形状和位置:

  • α + β 的值越大,分布曲线越窄,也就是越集中。

  • α/(α + β) 的值是 beta 分布的均值(期望值),它的值越大, beta 分布的中心越靠近 1,否则越靠近 0 。


注意:当参数 α 和 β 确定后,使用 beta 分布生成的随机数有可能不一样,所以汤普森采样法是不确定算法。


beta 分布和 Bandit 算法有什么关联呢?实际上,每个臂是否产生收益的概率 p 的背后都对应一个 beta 分布。我们将 beta 分布的 α 参数看成是推荐后用户的点击次数, β 参数看成是推荐后用户未点击的次数。

来看下使用汤普森算法的流程:

  1. 每个臂都维护一个 beta 分布的参数,获取每个臂对应的参数 α 和 β,然后使用 beta 分布生成随机数。

  2. 选取生成随机数最大的那个臂作为本次结果

  3. 观察用户反馈,如果用户点击则将对应臂的 α 加 1,否则 β 加 1


在实际的推荐系统中,需要为每个用户保存一套参数,假设有 m 个用户, n 个臂(选项,可以是物品,可以是策略), 每个臂包含 α 和 β 两个参数,所以最后保存的参数的总个数是 2 m n。

可以直观的理解下为什么汤普森采样算法有效:

  • 当尝试的次数较多时,即每个臂的 α + β 的值都很大,这时候每个臂对应的 beta 分布都会很窄,也就是说,生成的随机数都非常接近中心位置,每个臂的收益基本确定了。

  • 当尝试的次数较少时,即每个臂的 α + β 的值都很小,这时候每个臂对应的 beta 分布都会很宽,生成的随机数有可能会比较大,增加被选中的机会。

  • 当一个臂的 α + β 的值很大,并且 α/(α + β) 的值也很大,那么这个臂对应的 beta 分布会很窄,并且中心位置接近 1 ,那么这个臂每次选择时都很占优势。


使用 python 来实现汤普森采样:

    import numpyasnp      

import pymc

# wins 和 trials 都是一个 N 维向量,N 是臂的个数

# wins 表示所有臂的 α 参数,loses 表示所有臂的 β 参数

choice = np.argmax(pymc.rbeta(1+ wins,1+ loses, len(wins)))

# wins[choice] += 1

# loses[choice] += 1


UCB(Upper Confidence Bound)


UCB 算法全称是 Upper Confidence Bound,即置信区间上界。它是计算每个臂的平均收益与该收益的不确定性来作为最终得分。公式如下;

i 表示当前的臂,t 表示目前的尝试次数,Ti,t 表示臂 i 被选中的次数。公式加号左边表示臂 i 当前的平均收益,右边表示该收益的 Bonus ,本质上是均值的标准差,反应了候选臂效果的不确定性,就是置信区间的上边界。

使用 UCB 算法的流程如下:

  1. 对所有臂先尝试一次

  2. 按照公式计算每个臂的最终得分

  3. 选择得分最高的臂作为本次结果

直观理解下 UCB 算法为什么有效?

  • 当一个臂的平均收益较大时,也就是公式左边较大,在每次选择时占有优势

  • 当一个臂被选中的次数较少时,即 Tit 较小,那么它的 Bonus 较大,在每次选择时占有优势

所以 UCB 算法倾向选择被选中次数较少以及平均收益较大的臂。

UCB 算法需要对所有的臂进行一次尝试,当臂比较多时,可能会比较耗时,如果 UCB 算法的参数是确定的,那么输出结果就是确定的,也就是说它本质上仍然是一个“确定性”的算法,这会导致它的 explore 能力受限。

总结


为解决推荐系统 EE 问题,可以使用 Bandit 算法,这里介绍了常用的 Bandit 算法,如:Naive、Epsilon-Greedy(ε-Greedy)、UCB(Upper Confidence Bound)等,但是这些算法都没有考虑上下文信息,也就是环境,之后会介绍结合上下文信息的 LinUCB 算法。

相关 [科技] 推荐:

脑洞科技栈

- -
推荐阅读时间:10min~12min. 主题:如何使用Bandit算法解决EE问题. 生活中你可能会遇到类似的情况,你在网上购买了手机,淘宝之后会不断给你推送关于手机相关的商品;如果你看了关于NBA詹姆斯的相关新闻,今日头条之后会不断给你推送詹姆斯的新闻. 时间长了,你会发现你的世界里只有手机和詹姆斯,天呐,世界越来越小,视野越来越窄怎么办.

美国科技圈图谱

- zjk - 36氪
编者按:本文来自JohnTian的投稿,JohnTian曾经投过亚马逊是如何拯救Kindle的,点击这里关注他的新浪微博. 为什么全球的科技新闻、互联网新闻、创业新闻都被美国所占据. 为什么美国的互联网创业行业总吸引所有人的眼球. 为什么….?看了这张美国科技圈图谱,我想你应该有所眉目. 微软、亚马逊、迪斯尼、苹果、Facebook、Google、AOL、Twitter、Ebay….

新型科技睡衣

- Leaven - 设计|生活|发现新鲜
这款“科技睡衣”项目还在进行中,据设计师称,它可以支撑各种重量,变化各种造型. 为的只是在你需要睡眠,一个人独处,又或者想要自我保护的时候,它能满足你的要求. 小编觉得,公共场所,穿上这“睡衣”,反而更加引人注目啦吧,那回头率,老高呢. 「设计,生活,发现新鲜」在新浪微博,更即时地获读更新,更直接地交流沟通.

科技博客的价值

- - 月光博客
  编者按:本文作者程然,爱范儿、Techweb、长城会mobiSights专栏作者,文章继daidai和@范怿Ryan 对科技博客发展的探讨之后,对科技博客为何会火及其价值做出分析,指出科技博客引领整个行业的视线,促进行业发展. 如有读者要和作者联系,可在新浪微博@程然henry.   去年6月我对博客未来发展的有了一些想法,其中有关轻博客的,发表在爱范儿上;还有些是关于科技博客未来发展的.

再谈科技博客

- - 雷锋网
编者按:本文作者daidai,在爱范儿发了一篇《 当科技博客遇见知乎》后在雷锋网继续谈对科技博客发展的思考,谈到了科技博客的失控以及科技博客想要什么. 之所以再谈科技博客,是想把之前未能解释清楚的一些问题说的再透彻些. 专业的科技博客,是一种较难界定的媒体. 问题并不在于媒体性或是内容性的分类,而是如何摆正专业博客的地位.

全民科技时代,请注意自己的科技礼仪

- - TECH2IPO创见
古语有云,礼貌于人如温暖于蜡,礼貌让我们相处地更融洽. 对所有人来说,同行的乘客和旅人如果能够保持礼貌会使得旅途更加愉快. 就科技礼仪来说,投入的微小就会带来巨大的改变. 在旅途中呆目相视对面的人或大声播放刺耳的《爱情买卖》是非常不礼貌的. 例如,一些旅客在火车或飞机上毫不犹豫的掏出了iPad,礼仪专家认为这种行为是不符合礼仪规范的.

不,这跟高科技无关

- Alex Yu - Apple4.us
前两天在 Twitter 上提到乔布斯就苹果新总部大楼给美国加州库布提诺市政厅做的讲演. 这段视频里有一个细节很值得注意. 讲演开始后不久,乔布斯用幻灯打出地图,向众人说明旧总部和新总部的相对位置. 这时库布提诺的市长 Gilbert Wong 突然打断说(视频的 4’20” 处起):. 「乔布斯先生,你可以直接用手在上面画,我们很高科技的.

蓬灰,拉面的科技(上)

- Gong - 科学松鼠会
南京电视台“爆料”了拉面中使用“蓬灰”的“行业内幕”,果不其然吸引了全国公众的眼球. 被食品添加剂弄得风声鹤唳的公众立刻群情激愤,以至于南京的数百家拉面店几近停业. 后来的发展简直可以用“峰回路转”来形容——原来蓬灰是最正宗的拉面必用之物,“已有上百年历史”. 再加上它是一种“天然产物”,并非“化学工业品”,于是大多数人就放了心,事件也以电视台灰头土脸地道歉而告终.

蓬灰,拉面的科技(下)

- Gong - 科学松鼠会
所谓“操纵面粉里的面筋蛋白”,就是改变它所处的环境,使得它们自愿或者非自愿地听从人们的指令. 面筋蛋白跟其他蛋白质一样,属于意志不坚定、很容易受环境影响的“软骨头”. 只要周围的酸碱度、盐度、温度等发生变化,它们就会放弃“自我”. 比如说,当pH值升高(即碱性增加)时,面筋蛋白中巯基上的氢原子就更加容易离家出走,从而使得面筋蛋白之间的交联更加容易发生.

这次的科技泡沫不一样

- gounix - cnBeta.COM
编者按:本文来自彭博商业周刊,文章非常的有深度也很长. 科技泡沫会发生,但是我们通常都会受益于其留下的重大创新和突破. 而当前我们正在经历的这个科技泡沫,它由社交网络驱动,最后可能什么都不会给我们留下. 2006年,一个名叫Jeff Hammerbacher(数学天才)且才刚刚走出校门一年的哈佛大学小子来到了Facebook,那时Facebook还仍处在自己的婴儿发展期,急需招聘数据分析人员来研究人们对Facebook的使用情况.