Press "Enter" to skip to content

EE和冷启动中的多臂老虎机问题

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

共发表: 第198篇

 

 

推荐系统中有两个很重要的问题:EE问题和冷启动。在实际的场景中很好的解决这两个问题又很难,比如冷启动,我们可以基于热门、用户、第三方等信息进行半个性化的推荐,但很难去获得用户的真实兴趣分布。那幺有没有一种算法可以很好的解决这个问题呢?答案就是:Bandit。

 

Bandit算法与推荐系统

 

在推荐系统领域里,有两个比较经典的问题常被人提起,一个是EE问题,另一个是用户冷启动问题。

 

EE问题又叫Exploit-Explore。

 

Exploit表示的是对于用户已经确定的兴趣当然要迎合。

 

Explore表示的如果仅对用户进行兴趣投放,很快就会看厌,所以要不断的探索用户的新兴趣

 

所以在进行物品推荐时,不仅要投其所好,还要进行适当的长尾物品挖掘。

 

用户冷启动问题,也就是面对新用户时,如何能够通过若干次实验,猜出用户的大致兴趣。

 

这两个问题本质上都是如何选择用户感兴趣的主题进行推荐,比较符合Bandit算法背后的MAB问题。

 

比如,用Bandit算法解决冷启动的大致思路如下:用分类或者Topic来表示每个用户兴趣,也就是MAB问题中的臂(Arm),我们可以通过几次试验,来刻画出新用户心目中对每个Topic的感兴趣概率。这里,如果用户对某个Topic感兴趣(提供了显式反馈或隐式反馈),就表示我们得到了收益,如果推给了它不感兴趣的Topic,推荐系统就表示很遗憾(regret)了。如此经历“选择-观察-更新-选择”的循环,理论上是越来越逼近用户真正感兴趣的Topic的。

 

Bandit算法来源

 

Bandit算法来源于历史悠久的赌博学,它要解决的问题是这样的:

 

一个赌徒,要去摇老虎机,走进赌场一看,一排老虎机,外表一模一样,但是每个老虎机吐钱的概率可不一样,他不知道每个老虎机吐钱的概率分布是什幺,那幺每次该选择哪个老虎机可以做到最大化收益呢?这就是多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)。

 

怎幺解决这个问题呢?最好的办法是去试一试,不是盲目地试,而是有策略地快速试一试,这些策略就是Bandit算法。

 

这个多臂问题,推荐系统里很多问题都与它类似:

 

假设一个用户对不同类别的内容感兴趣程度不同,那幺我们的推荐系统初次见到这个用户时,怎幺快速地知道他对每类内容的感兴趣程度?这就是推荐系统的冷启动。

 

假设我们有若干广告库存,怎幺知道该给每个用户展示哪个广告,从而获得最大的点击收益?是每次都挑效果最好那个幺?那幺新广告如何才有出头之日?

 

我们的算法工程师又想出了新的模型,有没有比A/B test更快的方法知道它和旧模型相比谁更靠谱?

 

如果只是推荐已知的用户感兴趣的物品,如何才能科学地冒险给他推荐一些新鲜的物品?

 

Bandit算法需要量化一个核心问题:错误的选择到底有多大的遗憾?能不能遗憾少一些?常见Bandit算法有哪些呢?往下看

 

Thompson sampling

 

1、Beta分布

 

Thompson Sampling是基于Beta分布进行的,所以首先看下什幺是Beta分布?

 

Beta分布可以看作是一个概率的概率分布,当你不知道一个东西的具体概率是多少时,他可以给出所有概率出现的可能性。Beta是一个非固定的公式,其表示的是一组分布(这一点和距离计算中的闵可夫斯基距离类似)。

 

比如:

 

二项分布(抛n次硬币,正面出现k次的概率)

 

 

几何分布(抛硬币,第一次抛出正面所需的次数的概率)

 

 

帕斯卡分布(抛硬币,第k次出现正面所需次数的概率)

 

 

去找一个统一的公式去描述这些分布,就是Beta分布:

 

其中是标准化函数,他的作用是使总概率和为1,
α
,
β 为形状参数,不同的参数对应的图像形状不同,他不但可以表示常见的二项分布、几何分布等,还有一个好处就是,不需要去关系某次实验结果服从什幺分布,而是利用
α
,

β

 

的值就可以计算出我们想要的统计量。

 

常见的参数对应的图形为:

Beta分布

的常见的统计量为:

 

众数为:

 

期望为:

 

方差为:

 

2、Beta分布的例子

 

网上资料中一个很常见的例子是棒球运动员的,这里进行借鉴。

 

棒球运动有一个指标是棒球击球率(batting average),就是用一个运动员击中的球数除以击球的总数,我们一般认为0.266是正常水平的击球率,而如果击球率高达0.3就被认为是非常优秀的。

 

现在有一个棒球运动员,我们希望能够预测他在这一赛季中的棒球击球率是多少。你可能就会直接计算棒球击球率,用击中的数除以击球数,但是如果这个棒球运动员只打了一次,而且还命中了,那幺他就击球率就是100%了,这显然是不合理的,因为根据棒球的历史信息,我们知道这个击球率应该是0.215到0.36之间才对啊。

 

对于这个问题,我们可以用一个二项分布表示(一系列成功或失败),一个最好的方法来表示这些经验(在统计中称为先验信息)就是用beta分布,这表示在我们没有看到这个运动员打球之前,我们就有了一个大概的范围。beta分布的定义域是(0,1)这就跟概率的范围是一样的。

 

接下来我们将这些先验信息转换为beta分布的参数,我们知道一个击球率应该是平均0.27左右,而他的范围是0.21到0.35,那幺根据这个信息,我们可以 α =81, β =219

棒球运动员Beta分布例子

之所以取这两个参数是因为:

 

beta分布的均值是:

 

从图中可以看到这个分布主要落在了(0.2,0.35)间,这是从经验中得出的合理的范围。

 

在这个例子里,我们的x轴就表示各个击球率的取值,x对应的y值就是这个击球率所对应的概率。也就是说beta分布可以看作一个概率的概率分布。

 

有了这样的初始值,随着运动的进行,其表达式可以表示为:

 

 

其中是一开始的参数,值为81,219。当击中一次球是 hits + 1,misses不变,当未击中时,hits不变,misses+1。这样就可以在每次击球后求其最近的平均水平了。

 

3、Thompson Smapling

 

Thompson sampling算法简单实用,简单介绍一下它的原理,要点如下:

 

假设每个臂是否产生收益,其背后有一个概率分布,产生收益的概率为p。

 

我们不断地试验,去估计出一个置信度较高的“概率p的概率分布”就能近似解决这个问题了。

 

怎幺能估计“概率p的概率分布”呢?答案是假设概率p的概率分布符合beta(wins, lose),它有两个参数: wins, lose。

 

每个臂都维护一个beta分布的参数。每次试验后,选中一个臂,摇一下,有收益则该臂的wins增加1,否则该臂的lose增加1。

 

每次选择臂的方式是:计算每个臂现有的beta分布的平均水平,选择所有臂产生的随机数中最大的那个臂去摇。

 

4、TS的Python实现

 

import numpy as np
import random
def ThompsonSampling(wins, trials):
    pbeta = [0] * N
    for i in range(0, len(trials)):
        pbeta[i] = np.random.beta(wins[i] + 1, trials[i] - wins[i] + 1)
    choice = np.argmax(pbeta)
    trials[choice] += 1
    if random.random() > 0.5:
        wins[choice] += 1
T = 10000  # 实验次数
N = 10  # 类别个数
# 臂的选择总次数
trials = np.array([0] * N )
# 臂的收益
wins = np.array([0] * N )
for i in range(0, T):
    ThompsonSampling(wins, trials)
print(trials)
print(wins)
print(wins/trials)

 

UCB

 

1、UCB的原理

 

UCB(Upper Confidence Bound,置信区间上界)可以理解为不确定性的程度,区间越宽,越不确定,反之就越确定,其表达式如下:

 

 

其中 Ni 表示第i个臂收益为 1 的次数,T表示选择的总次数

 

公式分为左右两部分,左侧(+左侧部分)表示的是候选臂i到目前为止的平均收益,反应的是它的效果。右侧(+右侧部分)叫做Bonus,本质上是均值的标准差,反应的是候选臂效果的不确定性,就是置信区间的上边界。

 

统计学中的一些统计量表达的含义

 

如果一个臂的收益很少,即Ni很小,那幺他的不确定性就越大,在最后排序输出时就会有优势,bouns越大,候选臂的平均收益置信区间越宽,越不稳定,就需要更多的机会进行选择。反之如果平均收益很大,即+号左侧户数很大,在选择时也会有被选择的机会。

 

2、UCB的Python实现

 

import numpy as np
# 定义 T = 1000 个用户,即总共进行1000次实现
T = 1000
# 定义 N = 10 个标签,即 N 个 
N = 10
# 保证结果可复现,设置随机数种子
np.random.seed(888)
# 每个物品的累积点击率(理论概率)
true_rewards = np.random.uniform(low=0, high=1, size= N)
# true_rewards = np.array([0.5] * N)
# 每个物品的当前点击率
now_rewards = np.zeros(N)
# 每个物品的点击次数
chosen_count = np.zeros(N)
total_reward = 0
# 计算ucb的置信区间宽度
def calculate_delta(T, item):
    if chosen_count[item] == 0:
        return 1
    else:
        return np.sqrt( 2 * np.log( T ) / chosen_count[item])
# 计算UCB
def ucb(t, N):
    # ucb得分
    upper_bound_probs = [ now_rewards[item] + calculate_delta(t,item) for item in range(N) ]
    item = np.argmax(upper_bound_probs)
    # 模拟伯努利收益
    # reward = sum(np.random.binomial(n =1, p = true_rewards[item], size=20000)==1 ) / 20000
    reward = np.random.binomial(n =1, p = true_rewards[item])
    return item, reward
for t in range(1,T+1):
    # 为第 t个用户推荐一个物品
    item, reward = ucb(t, N)
    # print("item is %s, reward is %s" % (item, reward))
    # 一共有多少用户接受了推荐的物品
    total_reward += reward
    chosen_count[item] += 1
    # 更新物品的当前点击率
    now_rewards[item] =  ( now_rewards[item] * (t-1) + reward) /  t
    # print("更新后的物品点击率为:%s" % (now_rewards[item]))
    # 输出当前点击率 / 累积点击率
    # print("当前点击率为: %s" % now_rewards)
    # print("累积点击率为: %s" % true_rewards)
    diff =  np.subtract( true_rewards, now_rewards)
    print(diff[0])
    print(total_reward)

 

3、UCB的推导

 

观测 1:假设一个物品被推荐了k次,获取了k次反馈(点击 or 不点击),可以计算出物品被点击的平均概率

 

当k 接近于正无穷时,p’ 会接近于真实的物品被点击的概率

 

 

观测 2:现实中物品被点击的次数不可能达到无穷大,因此估计出的被点击的概率 p’ 和真实的点击的概率 p 总会存在一个差值 d,即:

 

 

最后只需要解决差值 d 到底是怎幺计算的?

 

首先介绍霍夫丁不等式(Chernoff-Hoeffding Bound),霍夫丁不等式假设reward_1, … , reward_n 是在[0,1]之间取值的独立同分布随机变量,用p’ 表示样本的均值,用p表示分布的均值,那幺有:

 

 

当 δ 取值为 (其中 T 表示有物品被推荐的次数,n表示有物品被点击的次数),可以得到:

 

 

也就是说:

 

 

是以 1 – 2/T^4 的概率成立的,

 

当T=2时,成立的概率为0.875

 

当T=3时,成立的概率为0.975

 

当T=4时,成立的概率为0.992

 

 

是一个不错的选择。

 

Epsilon-Greedy

 

1、算法原理

 

这是一个朴素的Bandit算法,有点类似模拟退火的思想:

 

 

选一个(0,1)之间较小的数作为epsilon;

 

每次以概率epsilon做一件事:所有臂中随机选一个;

 

每次以概率1-epsilon 选择截止到当前,平均收益最大的那个臂。

 

 

是不是简单粗暴?epsilon的值可以控制对Exploit和Explore的偏好程度。越接近0,越保守,只选择收益最大的。

 

2、Python实现

 

import random
class EpsilonGreedy():
    def __init__(self, epsilon, counts, values):
        self.epsilon = epsilon
        self.counts = counts
        self.values = values
    def initialize(self, n_arms):
        self.counts = [0 for col in range(n_arms)]
        self.values = [0.0 for col in range(n_arms)]
    def select_arm(self):
        if random.random() > self.epsilon:
            return self.values.index( max(self.values) )
        else:
            # 随机返回 self.values 中的一个
            return random.randrange(len(self.values))
    def reward(self):
        return 1 if random.random() > 0.5 else 0
    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] = self.counts[chosen_arm] + 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        new_value = ((n - 1)  * value + reward ) / float(n)
        self.values[chosen_arm] = round(new_value,4)
n_arms = 10
algo = EpsilonGreedy(0.1, [], [])
algo.initialize(n_arms)
for t in range(100):
    chosen_arm = algo.select_arm()
    reward = algo.reward()
    algo.update(chosen_arm, reward)
print(algo.counts)
print(algo.values)

 

朴素Bandit算法

 

最朴素的Bandit算法就是:先随机试若干次,计算每个臂的平均收益,一直选均值最大那个臂。这个算法是人类在实际中最常采用的,不可否认,它还是比随机乱猜要好。

 

Python实现比较简单,这里就不做演示了。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注