777老虎机

 找回密码
 立即注册
查看: 624|回复: 0

小秃科普:"买定离手",多臂老虎机问题是什么?

[复制链接]

8271

主题

8271

帖子

2万

积分

等待验证会员

积分
24815
发表于 2020-11-14 18:11:29 | 显示全部楼层 |阅读模式
提到老虎机,你会想到什么呢?暴富?运气?失落?



今天小秃给大家介绍的是《多臂老虎机问题( multi-armed bandit)》——人工智能中强化学习算法的基础部分。

多臂老虎机是什么?

为了防止一些涉世未深的小朋友不明白什么是老虎机,也为了一些真正的老虎机玩家”误解“了我这里提到的老虎机(这里的老虎机机制比较简单,不要想太复杂),这里对多臂老虎机做一个解释。

远在澳门的小豪家里有一台多臂老虎机,这个老虎机有10个拉杆,拉下每一个拉杆,老虎机会吐出金额不定的钱。但经过小豪的精心调试,这10个拉杆中,每个拉杆吐出钱的金额是不同的,有的拉杆对应的金额大,有的拉杆吐出的金额少(例如拉杆1只能吐一元钱,拉杆2能吐10元钱)。同时,小豪为了防止玩家每个拉杆都拉一遍就知道每个拉杆能吐出多少钱,他还对机器做了一些手脚,他对机器加入了一定的随机性。这样,每个拉杆都有一个倾向,有的拉杆倾向于吐出较多的钱,有的拉杆向于吐出较少的钱,但由于随机性的存在,这种倾向需要大量的尝试才能发现。

多臂老虎机问题的相关算法能做什么?

简单说来,该算法能让我们合理地进行尝试获得最大的收益。具体可以用在以下场景下:

1) 可应用在本文中描述的多臂老虎机问题中;

2) 可应用在推荐系统中的冷启动相关问题中;

3) 可应用在计算广告中的新广告的选取中;

都有哪些方法可以解决多臂老虎机问题?

1) ϵ−greedy

2) Thompson Sampling

2) Upper Confidence Bounds(UCB)

3) LinUCB (Linear UCB)

由于本文只是简单介绍,所以这里选取最简单的一个算法(ϵ−greedy)进行介绍:

ϵ−greedy算法介绍:

一、 两个步骤:

该算法分成探索利用两个步骤,探索和利用步骤不断交替进行,如下:

探索->利用->探索->利用->探索->利用->.....

二、 探索和利用分别在做什么?

探索:随机地尝试多个臂,然后重新估计每个臂对应的收益的期望。具体的,可以在每次随机选择后,看看该臂有多少收益,计算这个臂的收益的平均值为多少,将这个值当做该臂的收益期望;

利用:看目前哪个臂能获取最大的期望收益,就选择该臂。具体的,看看哪个臂的平均收益最大,本次选择就选这个臂;

三、 探索和利用比例:

设置一个很小的参数ε(例如可以是0.1),该参数代表的10%的概率进行探索,90%的概率进行利用。设置成0.1意味着我能充分利用当前已有的信息,去获取当前我认为的最大收益。同时,保留一些希望,有10%的概率去探索,万一别的臂的收益更高呢,避免过于相信少部分经验,从而失去更大的可能。

注:

推荐系统:新闻推荐、商品推荐、影视剧推荐等等的推荐都属于推荐系统的一种;

冷启动:在推荐系统中,针对新用户的推荐策略,我们一般叫做冷启动。对于新用户,我们没有他们的行为以及标签数据,所以,相比老用户的推荐,冷启动是一个较难解决的问题;

计算广告:可以粗略地认为是现在互联网利用技术投放广告的方法;

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

发表回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


快速回复 返回顶部 返回列表