Press "Enter" to skip to content

推荐系统中的多臂老虎机,在探索和利用的权衡下,如何实现利益最大化?

引言

 

推荐系统中有两个经典问题:EE 问题和冷启动问题。

 

什幺是 EE 问题?又叫 exploit-explore 问题。exploit 就是:对用户比较确定的兴趣,当然要利用开采迎合,好比说已经挣到的钱,当然要花;explore 就是:光对着用户已知的兴趣使用,用户很快会腻,所以要不断探索用户新的兴趣才行,这就好比虽然有一点钱可以花了,但是还得继续搬砖挣钱,不然花完了就得喝西北风。

 

用户冷启动问题,也就是面对新用户时,如何通过快速试探以及短暂的若干次实验,快速挖掘用户大致兴趣。

 

Bandit 算法是一种简单的在线学习算法,主要为了平衡试探和利用问题。

 

选择困难户,你需要了解它

 

我们会遇到很多选择的场景。上哪个大学,学什幺专业,去哪家公司,中午吃什幺,等等。这些事情,都让选择困难症的我们头很大。那幺,有算法能够很好地对付这些问题吗?

 

当然有!那就是 bandit 算法!

 

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

 

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

 

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

 

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

 

 

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

 

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

 

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

 

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

 

 

这些问题本质上全都是关乎如何选择。只要是关于选择,都可以简化成一个多臂赌博机问题,毕竟小赌怡情嘛,人生何处不赌博。

 

积累遗憾

 

现在来介绍一下 bandit 算法怎幺解决这类问题的。bandit 算法需要量化一个核心问题:错误的选择到底有多大的遗憾?能不能遗憾少一些?

 

它顾名思义,是指 T 次选择,将每次选择的实际收益 WB_i 与此次选择最好的策略带来的最大收益差,将 T 次差的总和就得到累积遗憾。

 

 

这个公式就是计算 Bandit 算法的累积遗憾,解释一下:

 

首先,这里我们讨论的每个臂的收益非 0 即 1,也就是伯努利收益。

 

然后每次选择后,计算和最佳的选择差了多少,然后把差距累加起来就是总的遗憾。

 

假设用最简单的伯努利实验来模拟这个过程:我们有 K 个选择,其中每次选择时最优收益是 1,其余收益为 0,我们进行 T 次选择,则最差的情况下我们的累积遗憾是 T,而最好的情况下是每次都选择是 1,遗憾为 0。

 

这个公式可以用来对比不同 bandit 算法的效果:对同样的多臂问题,用不同的 bandit 算法试验相同次数,看看谁的 regret 增长得慢。

 

常见的 Bandit 算法之一:UCB 算法

 

 

Upper Confidence Bound,即置信区间上界。同样为每个臂评分,每次选择评分最高的候选臂输出,每次输出后观察用户反馈,然后更新候选臂参数。

 

问题假设:按下摇臂后的回报取值为 1 或 0,每个摇臂获得回报的概率服从不同的分布,但实现并不知道。

 

问题目标:按照某种策略来按压摇臂以获得最大的累积回报。

 

在这个问题中,就是探索和利用问题。

 

利用:按压之前获得回报最高的那个臂,以获得更高的累积回报。但是因为回报是随机的,对每个臂的回报概率估计并不准确,或许真实回报概率最高的那个臂并非当前估计的那个臂。

 

探索:随机地区按压不同的臂,得到每个臂更精确的回报概率估计,从而找到真实的那个最优的臂,但是要探索,就要去按压目前回报概率估计并不高的臂,意味着会损失一些按压高回报摇臂的机会。

 

窘境:因为尝试次数有限,所以探索和利用是矛盾的,加强乙方必然削弱另一方,要想回报最大,则必须在探索和利用之中达到较好的平衡。

 

那如何来平衡探索和利用呢?

 

已有的方法包括 ϵ – greedy 策略和 softmax 策略,这里重点讲解 UCB 策略和公式的理解。

 

 

公式中如果只有第一项,那就是一个纯利用,也就是贪婪策略,它很容易陷入局部极值,而第二项的意义在于,如果我们对一个臂的了解过于少,那它的平均回报在此时的置信度是很低的,不确定度就很高,置信区间就很大(我想也可以理解为方差很大),我们就非常不相信它此时的平均回报就是它真实的平均回报,所以我们需要选择这个臂来获取更多的信息。

 

因此,第二项可以当做一个测量对臂了解多少的指标,了解越少,第二项越大。加入了第二项这个指标,我们可以说这个算法是有好奇心的,当对于一个臂的了解不够时,它会被选中,即使这个臂的平均回报很低。

 

UCB 的实现

 

import numpy as np
import matplotlib.pyplot as plt
import random
import math
# Implementing UCB
"""
建立UCB,每回合只投1个广告给1个用户
-N = 10000: 投10000次光改
-d = 8: 广告长度
-ads_selected = []: 记录器,记录每轮推哪个广告,其长度等于推送数,并且等于N
-numbers_of_selections = [0] * d: 每个广告总共被选择次数
-sums_of_rewards = [0] * d: 每个广告的总得分数
-total_reward = 0: 所有广告的得分数总合
"""
# 广告列表
userInterestStr = ["C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9", "C10"]
# 广告初始回报
userInterest = [300, 100, 50, 50, 300, 100, 50, 50, 0, 0]
N = 10000
d = len(userInterest)
ads_selected = []
numbers_of_selections = [0] * d
sums_of_rewards = [0] * d
total_reward = 0
upper_bound = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
selectArr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    # Step 1. 对每个广告的平均期望置信区间更新
    for i in range(0, d):
        if (numbers_of_selections[i] > 0):
            # Step 2. 广告i的平均期望值变量计算
            average_reward = sums_of_rewards[i] / numbers_of_selections[i]
            delta_i = math.sqrt(2 * math.log(n + 1) / numbers_of_selections[i])
            # Step 3 广告i的平均期望值更新
            upper_bound[i] = average_reward + delta_i
        else:
            # 一开始(第一轮)每个广告的置信区间很大
            upper_bound[i] = 1e400
        # 更新下一轮要推播的广告以及目前最高的天花板(UCB)
        if upper_bound[i] > max_upper_bound:
            max_upper_bound = upper_bound[i]
            ad = i
    # 更新记录器
    ads_selected.append(ad)
    selectArr[ad] += 1
    # 广告i被点击数+1
    numbers_of_selections[ad] = numbers_of_selections[ad] + 1
    prob = userInterest[ad]
    randValue = random.random() * 1000
    if randValue < prob:
        reward = 1
    else:
        reward = 0
    # 广告i得分数更新
    sums_of_rewards[ad] = sums_of_rewards[ad] + reward
    # 所有广告总得分更新
    total_reward = total_reward + reward
print(userInterest)
print(np.array(selectArr) * 100 / N)
# Visualising the results
"""
结果可视化
"""
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

 

摇臂结果

 

[300, 100, 50, 50, 300, 100, 50, 50, 0, 0]

 

可以看到我们初始的回报中,第二个和第一个与第5个相差并不大,但是最终摇臂的结果却是第5个被选择次数最多,利用较多,探索较少。

 

我们在期望,探索和收益的平衡能够与我们期望的分布相差不大。既然我们知道,初始的利用较多,那幺我们就要对利用进行惩罚,加大探索。

 

 

def get_max_list(rewards):
    max_ = max(rewards)
    res = []
    for idx, r in enumerate(rewards):
        if r == max_:
            res.append(i)
    return res
# Step 1. 对每个广告的平均期望置信区间更新
for i in range(0, d):
  if (numbers_of_selections[i] > 0):
    # Step 2. 广告i的平均期望值变量计算
    average_reward = sums_of_rewards[i] / numbers_of_selections[i]
    delta_i = math.sqrt(2 * math.log(n + 1) / numbers_of_selections[i])
    max_list = get_max_list(sums_of_rewards)
    if i in max_list:
      # Step 3 广告i的平均期望值更新
      upper_bound[i] = 0.5 * average_reward + 2 * delta_i
      else:
        upper_bound[i] = 3 * average_reward + 0.2 * delta_i
        else:
          # 一开始(第一轮)每个广告的置信区间很大
          upper_bound[i] = 1e400

 

这里,对每次收益最大的那个臂,将其探索程度加大,收益权重进行降权,对收益较小的臂,加大利用,减少试探。再次运行,结果与收益分布相当,满足预期结果。

 

Be First to Comment

发表回复

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