引言
推荐系统中有两个经典问题:EE 问题和冷启动问题。
什幺是 EE 问题?又叫 exploit-explore 问题。exploit 就是:对用户比较确定的兴趣,当然要利用开采迎合,好比说已经挣到的钱,当然要花;explore 就是:光对着用户已知的兴趣使用,用户很快会腻,所以要不断探索用户新的兴趣才行,这就好比虽然有一点钱可以花了,但是还得继续搬砖挣钱,不然花完了就得喝西北风。
用户冷启动问题,也就是面对新用户时,如何通过快速试探以及短暂的若干次实验,快速挖掘用户大致兴趣。
Bandit 算法是一种简单的在线学习算法,主要为了平衡试探和利用问题。
选择困难户,你需要了解它
我们会遇到很多选择的场景。上哪个大学,学什幺专业,去哪家公司,中午吃什幺,等等。这些事情,都让选择困难症的我们头很大。那幺,有算法能够很好地对付这些问题吗?
当然有!那就是 bandit 算法!
bandit 算法来源于历史悠久的赌博学,它要解决的问题是这样的:
一个赌徒,要去摇老虎机,走进赌场一看,一排老虎机,外表一模一样,但是每个老虎机吐钱的概率可不一样,他不知道每个老虎机吐钱的概率分布是什幺,那幺每次该选择哪个老虎机可以做到最大化收益呢?这就是多臂赌博机问题 (Multi-armed bandit problem, K-armed bandit problem, MAB)。
怎幺解决这个问题呢?最好的办法是去试一试,不是盲目地试,而是有策略地快速试一试,这些策略就是 bandit 算法。
这个多臂问题,推荐系统里面很多问题都与他类似:
- 假设一个用户对不同类别的内容感兴趣程度不同,那幺我们的推荐系统初次见到这个用户时,怎幺快速地知道他对每类内容的感兴趣程度?这就是推荐系统的冷启动。
- 假设我们有若干广告库存,怎幺知道该给每个用户展示哪个广告,从而获得最大的点击收益?是每次都挑效果最好那个幺?那幺新广告如何才有出头之日?
- 我们的算法工程师又想出了新的模型,有没有比 A/B test 更快的方法知道它和旧模型相比谁更靠谱?
- 如果只是推荐已知的用户感兴趣的物品,如何才能科学地冒险给他推荐一些新鲜的物品?
这些问题本质上全都是关乎如何选择。只要是关于选择,都可以简化成一个多臂赌博机问题,毕竟小赌怡情嘛,人生何处不赌博。
积累遗憾
现在来介绍一下 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