英文外贸网站设计,网站开发 不好 怎么说,外贸网站用什么空间,网站建设为什么学flash目录
1#xff09;什么是Bandit算法
为选择而生。
Bandit算法与推荐系统
怎么选择Bandit算法#xff1f;
2)常用Bandit算法
Thompson sampling算法
UCB算法
Epsilon-Greedy算法
Greedy算法
3#xff09;Bandit算法Python实战
参考资料#xff1a; 推荐系统里面有…目录
1什么是Bandit算法
为选择而生。
Bandit算法与推荐系统
怎么选择Bandit算法
2)常用Bandit算法
Thompson sampling算法
UCB算法
Epsilon-Greedy算法
Greedy算法
3Bandit算法Python实战
参考资料 推荐系统里面有两个经典问题EE和冷启动。Bandit算法是一种简单的在线学习算法常常用于尝试解决这两个问题本文为你介绍基础的Bandit算法原理及Python实战。
1什么是Bandit算法
为选择而生。
我们会遇到很多选择的场景。上哪个大学学什么专业去哪家公司中午吃什么等等。这些事情都让选择困难症的我们头很大。那么有算法能够很好地对付这些问题吗
当然有那就是Bandit算法。
Bandit算法来源于历史悠久的赌博学它要解决的问题是这样的
一个赌徒要去摇老虎机走进赌场一看一排老虎机外表一模一样但是每个老虎机吐钱的概率可不一样他不知道每个老虎机吐钱的概率分布是什么那么每次该选择哪个老虎机可以做到最大化收益呢这就是多臂赌博机问题Multi-armed bandit problem, K-armed bandit problem, MAB。如下图所示 怎么解决这个问题呢最好的办法是去试一试不是盲目地试而是有策略地快速试一试这些策略就是Bandit算法。
这个多臂问题推荐系统里很多问题都与它类似
假设一个用户对不同类别的内容感兴趣程度不同那么我们的推荐系统初次见到这个用户时怎么快速地知道他对每类内容的感兴趣程度这就是推荐系统的冷启动。假设我们有若干广告库存怎么知道该给每个用户展示哪个广告从而获得最大的点击收益是每次都挑效果最好那个么那么新广告如何才有出头之日我们的算法工程师又想出了新的模型有没有比A/B test更快的方法知道它和旧模型相比谁更靠谱如果只是推荐已知的用户感兴趣的物品如何才能科学地冒险给他推荐一些新鲜的物品
Bandit算法与推荐系统
在推荐系统领域里有两个比较经典的问题常被人提起一个是EE问题另一个是用户冷启动问题。
什么是EE问题又叫exploitexplore问题。exploit就是对用户比较确定的兴趣当然要利用开采迎合好比说已经挣到的钱当然要花explore就是光对着用户已知的兴趣使用用户很快会腻所以要不断探索用户新的兴趣才行这就好比虽然有一点钱可以花了但是还得继续搬砖挣钱不然花完了就得喝西北风。
用户冷启动问题也就是面对新用户时如何能够通过若干次实验猜出用户的大致兴趣。
我想屏幕前的你已经想到了推荐系统冷启动可以用Bandit算法来解决一部分。
这两个问题本质上都是如何选择用户感兴趣的主题进行推荐比较符合Bandit算法背后的MAB问题。
比如用Bandit算法解决冷启动的大致思路如下用分类或者Topic来表示每个用户兴趣也就是MAB问题中的臂Arm我们可以通过几次试验来刻画出新用户心目中对每个Topic的感兴趣概率。这里如果用户对某个Topic感兴趣提供了显式反馈或隐式反馈就表示我们得到了收益如果推给了它不感兴趣的Topic推荐系统就表示很遗憾regret了。如此经历“选择-观察-更新-选择”的循环理论上是越来越逼近用户真正感兴趣的Topic的
怎么选择Bandit算法
现在来介绍一下Bandit算法怎么解决这类问题的。Bandit算法需要量化一个核心问题错误的选择到底有多大的遗憾能不能遗憾少一些
王家卫在《一代宗师》里寄出一句台词
人生要是无憾那多无趣
而我说算法要是无憾那应该是过拟合了。
所以说怎么衡量不同Bandit算法在解决多臂问题上的效果首先介绍一个概念叫做累积遗憾regret 图2 积累遗憾
这个公式就是计算Bandit算法的累积遗憾解释一下
首先这里我们讨论的每个臂的收益非0即1也就是伯努利收益。
然后每次选择后计算和最佳的选择差了多少然后把差距累加起来就是总的遗憾。
wB(i)是第i次试验时被选中臂的期望收益 w*是所有臂中的最佳那个如果上帝提前告诉你我们当然每次试验都选它问题是上帝不告诉你所以就有了Bandit算法我们就有了这篇文章。
这个公式可以用来对比不同Bandit算法的效果对同样的多臂问题用不同的Bandit算法试验相同次数看看谁的regret增长得慢。
那么到底不同的Bandit算法有哪些呢
2)常用Bandit算法
Thompson sampling算法
Thompson sampling算法简单实用因为它只有一行代码就可以实现[3]。简单介绍一下它的原理要点如下
假设每个臂是否产生收益其背后有一个概率分布产生收益的概率为p。我们不断地试验去估计出一个置信度较高的“概率p的概率分布”就能近似解决这个问题了。怎么能估计“概率p的概率分布”呢 答案是假设概率p的概率分布符合beta(wins, lose)分布它有两个参数: wins, lose。每个臂都维护一个beta分布的参数。每次试验后选中一个臂摇一下有收益则该臂的wins增加1否则该臂的lose增加1。每次选择臂的方式是用每个臂现有的beta分布产生一个随机数b选择所有臂产生的随机数中最大的那个臂去摇。UCB算法
UCB算法全称是Upper Confidence Bound置信区间上界它的算法步骤如下[4]
初始化先对每一个臂都试一遍按照如下公式计算每个臂的分数然后选择分数最大的臂作为选择图3 UCB算法
观察选择结果更新t和Tjt。其中加号前面是这个臂到目前的收益均值后面的叫做bonus本质上是均值的标准差t是目前的试验次数Tjt是这个臂被试次数。
这个公式反映一个特点均值越大标准差越小被选中的概率会越来越大同时哪些被选次数较少的臂也会得到试验机会。 Epsilon-Greedy算法
这是一个朴素的Bandit算法有点类似模拟退火的思想
选一个0,1之间较小的数作为epsilon每次以概率epsilon做一件事所有臂中随机选一个每次以概率1-epsilon 选择截止到当前平均收益最大的那个臂。
是不是简单粗暴epsilon的值可以控制对Exploit和Explore的偏好程度。越接近0越保守只想花钱不想挣钱。 Greedy算法
先随机试若干次计算每个臂的平均收益一直选均值最大那个臂。这个算法是人类在实际中最常采用的不可否认它还是比随机乱猜要好。 3Bandit算法Python实战
下面是我们模拟10000次的实验各种算法对比可以看出Thompson算法效果是最好的。
import numpy as np
import matplotlib.pyplot as plt
import math#老虎机个数
number_of_bandits10
#每个老虎机的臂数
number_of_arms10
#尝试数
number_of_pulls10000
#eps
epsilon0.3
#最小的decay
min_temp 0.1
#衰减率
decay_rate0.999def pick_arm(q_values,counts,strategy,success,failure):global epsilon#随机返回一个臂if strategyrandom:return np.random.randint(0,len(q_values))#贪心算法,每次都选取收益最大的那个臂if strategygreedy:best_arms_value np.max(q_values)#返回收益最大的臂的位置best_arms np.argwhere(q_valuesbest_arms_value).flatten()#返回自身最大臂# 等价于return best_arms[0]return best_arms[np.random.randint(0,len(best_arms))]#加epsilon,egreedy中epsilon不变egreedy_decayepsilon变化if strategyegreedy or strategyegreedy_decay: if strategyegreedy_decay: epsilonmax(epsilon*decay_rate,min_temp)if np.random.random() epsilon:best_arms_value np.max(q_values)best_arms np.argwhere(q_valuesbest_arms_value).flatten()return best_arms[np.random.randint(0,len(best_arms))]else:#以epsilon的概率随机选取一个臂return np.random.randint(0,len(q_values))#ucb,按照ucb公式算每个臂的收益,取最大的收益的臂/1000次除以101000if strategyucb:total_counts np.sum(counts)q_values_ucb q_values np.sqrt(np.reciprocal(counts0.001)*2*math.log(total_counts1.0))best_arms_value np.max(q_values_ucb)best_arms np.argwhere(q_values_ucbbest_arms_value).flatten()return best_arms[np.random.randint(0,len(best_arms))]#thompson,利用beta分布选择臂if strategythompson:sample_means np.zeros(len(counts))for i in range(len(counts)):sample_means[i]np.random.beta(success[i]1,failure[i]1)return np.argmax(sample_means)fig plt.figure()
ax fig.add_subplot(111)
for st in [greedy,random,egreedy,egreedy_decay,ucb,thompson]:#定义 bandits个数*拉的次数的数组10,10000best_arm_counts np.zeros((number_of_bandits,number_of_pulls))#对于每个老虎机来说(0,10)for i in range(number_of_bandits):#随机一个老虎机10个臂的收益w保存最大收益arm_means np.random.rand(number_of_arms)best_arm np.argmax(arm_means)#初始化臂的收益(10)为零q_values np.zeros(number_of_arms)#初始化臂的拉动次数(10次)counts np.zeros(number_of_arms)#初始化臂的成功次数successnp.zeros(number_of_arms)#初始化臂的失败次数failurenp.zeros(number_of_arms)#对于每次拉动for j in range(number_of_pulls):#根据不同的策略选择臂aa pick_arm(q_values,counts,st,success,failure)#当前臂a的收益,二项分布收益为1或0reward np.random.binomial(1,arm_means[a])#臂的次数1counts[a]1.0#更新当前臂的收益(平均收益)q_values[a] (reward-q_values[a])/counts[a]#记录成功的收益success[a]reward#记录失败的收益failure[a](1-reward)#更新best_arm_counts[i][j]best_arm_counts[i][j] counts[best_arm]*100.0/(j1)epsilon0.3#横纵坐标ys np.mean(best_arm_counts,axis0)xs range(len(ys))ax.plot(xs, ys,label st)plt.xlabel(Steps)
plt.ylabel(Optimal pulls)plt.tight_layout()
plt.legend()
plt.ylim((0,110))
plt.show() 参考资料
[1] https://blog.csdn.net/heyc861221/article/details/80129310
[2] https://en.wikipedia.org/wiki/Thompson_sampling
[3] http://nbviewer.jupyter.org/github/CamDavidsonPilon/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers/blob/master/Chapter6_Priorities/Chapter6.ipynb#
[4] https://blog.csdn.net/a358463121/article/details/52562940
[5] https://blog.csdn.net/z1185196212/article/details/53374194
