重要,重要,重要,Latex 显示失败务必重新刷新页面可以修复,博主也在定位原因修复中

ucb 一个简单的例子

106次阅读
没有评论

这篇文章关于ucb 探索的简介和代码实现,大部分来自网上的一个大佬的文章,然后我试着改了写代码备注,新增了一个自己业务的示例。

让我们忘记探索阶段和利用阶段,仔细想想如何充分利用历史信息,找到最值得被推荐的菜:

观测 1: 如果一道菜已经推荐了k遍(获取了k次反馈),我们就可以算出菜做的好吃的概率:

\overset{`} p=\frac{\sum rewards_{i}}{k}

当k趋近正无穷时,\overset{`} p会趋近于真实的菜做的好吃的概率 p

观测 2: 现实当中一道菜被试吃的次数k不可能无穷大,因此估计出的好吃的概率\overset{`} p和真实的好吃的概率 p 总会存在一个差值 \Delta

即 $$\overset{} p-\Delta \lt p \lt \overset{总是乐观地认为每道菜能够获得的回报是\overset{`} p+\Delta ,这便是著名的Upper **Confidence Bound (UCB) 算法,代码如下所示。

def UCB(t, N):
    upper_bound_probs = [avg_rewards[item] + calculate_delta(t, item) for item in range(N)]
    item = np.argmax(upper_bound_probs)
    reward = np.random.binomial(n=1, p=true_rewards[item])
    return item, reward

for t in range(1, T): # T个客人依次进入餐馆
   # 从N道菜中推荐一个,reward = 1 表示客人接受,reward = 0 表示客人拒绝并离开
   item, reward = UCB(t, N)
   total_reward += reward # 一共有多少客人接受了推荐

真实的概率和估计的概率之间的差值 \Delta

最后只需解决一个问题,真实的概率和估计的概率之间的差值 \Delta 到底怎么计算呢?

在进入公式之前,让我们直观的理解影响 \Delta 的因素:

  • 对于被选中的菜,多获得一次反馈会使\Delta变小,最终会小于其他没有被选中的菜
  • 对于没被选中的菜,\Delta 会随着轮数的增大而增大,最终会大于其他被选中的菜

下面我们正式介绍如何计算 \Delta ,首先介绍Chernoff-Hoeffding Bound:

[Chernoff-Hoeffding Bound] 假设 reward1….rewardn是在[0, 1]之间取值的独立同分布随机变量,用 \overset{`} p=\frac{\sum rewards_{i}}{k}表示样本均值,用 p 表示分布的均值,那么有

P{|\overset{`} p-p| \le \theta}\ge 1-2e^{-2n\theta^2}

\theta取值为 \sqrt{2lnT/n}时 (其中T表示有T个客人,n表示菜被吃过的次数),可以得到

P{|\overset{`} p-p| \le \sqrt{2lnT/n} }\ge 1-\frac{2}{T^4}

也就是说 $$\overset{} p-\sqrt{2lnT/n} \lt p \lt \overset{

  • 当T=2时,成立的概率为0.875
  • 当T=3时,成立的概率为0.975
  • 当T=4时,成立的概率为0.992

可以看出 \sqrt{2lnT/n} 是一个不错的选择。

最后,我们附上完整的代码,跟第一讲不一样的地方已经重点加粗标注。

import numpy as np

T = 1000 # T个客人
N = 10 # N道菜

true_rewards = np.random.uniform(low=0, high=1, size=N) # 每道菜好吃的概率
estimated_rewards = np.zeros(N) # 每道菜好吃的估计概率
chosen_count = np.zeros(N) #各个菜被选中的次数
total_reward = 0 

def calculate_delta(T, item):
    if chosen_count[item] == 0:
        return 1
    else:
        return np.sqrt(2 * np.log(T) / chosen_count[item])

def UCB(t, N):
    upper_bound_probs = [estimated_rewards[item] + calculate_delta(t, item) for item in range(N)]
    item = np.argmax(upper_bound_probs)
    # 生成奖励,这里为了验证算法使用的是 二项分布,如果是碰巧喜欢那么就是返回 1 否则 0 不喜欢
    # 对于推荐系统可以使用的点击或者不点击作为 reward 
    reward = np.random.binomial(n=1, p=true_rewards[item]) 
    return item, reward

for t in range(1, T): # T个客人依次进入餐馆
   # 从N道菜中推荐一个,reward = 1 表示客人接受,reward = 0 表示客人拒绝并离开
   item, reward = UCB(t, N)
   total_reward += reward # 一共有多少客人接受了推荐

   # 更新菜的平均成功概率
   estimated_rewards[item] = ((t - 1) * estimated_rewards[item] + reward) / t
   chosen_count[item] += 1

上面的描述是参考的一个大佬的文章,然后代码里有些备注我自己改了,然后我就自己现在做的视频探索画一个简单的示意图

ucb

admin
版权声明:本站原创文章,由 admin2022-01-09发表,共计2364字。
转载说明:Copyright © 2022 算法之道. All rights reserved.
评论(没有评论)