使用Python实现UCB算法进行广告选择优化

在推荐系统和在线学习领域，广告点击率优化（CTR Optimization）是一个非常重要的课题。本文将详细介绍如何使用上置信界算法（UCB，Upper Confidence Bound）来优化广告选择，并通过Python代码实现整个过程。

一、UCB算法简介

UCB算法是一种用于解决多臂老虎机问题（Multi-Armed Bandit Problem）的策略，其核心思想是平衡探索（Exploration）和利用（Exploitation）。

• 探索：尝试新的选项，以发现潜在的高回报广告。
• 利用：根据已有数据选择当前最优广告。

公式定义如下：

​ $$UC{B}_i(n)={\bar{r}}_i(n)+\sqrt{\frac{2\ln n}{N_i(n)}}$$

含义：

1. ${\bar{r}}_i(n)$：拉杆 $i$ 的平均奖励（当前已知的部分）。

2. $\sqrt{\frac{2\ln n}{N_i(n)}}$

   ：置信区间宽度，表示探索的程度（未知的部分）。

   • $n$：当前轮次。
   • $N_i(n)$：拉杆 $i$ 被选择的次数。

两部分的作用：

• 平均奖励 ${\bar{r}}_i(n)$：代表拉杆的已知表现，用于利用。
• 置信区间 $\sqrt{\frac{2\ln n}{N_i(n)}}$：代表拉杆的不确定性，用于探索。

二、代码实现

数据集示例

以下是基于UCB算法实现广告选择的Python代码。

# -*- coding: utf-8 -*-
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
matplotlib.use('TkAgg')
import math

# 加载数据集
datasets = pd.read_csv('../Python/Ads_CTR_Optimisation.csv')

# 初始化参数
N = 10000                           # 总行数（用户访问次数）
d = 10                              # 广告数量
ads_selected = []                   # 被选择的广告索引列表
numbers_of_selections = [0] * d     # 每个广告被选择的次数
sums_of_rewards = [0] * d           # 每个广告的奖励总和
total_reward = 0                    # 总奖励

# UCB算法核心实现
for n in range(0, N):
    ad = 0
    max_upper_conf = 0
    for i in range(0, d):
        if numbers_of_selections[i] > 0:
            r_i = sums_of_rewards[i] / numbers_of_selections[i]  # 平均奖励
            delta_i = math.sqrt((3 * math.log(n + 1)) / (2 * numbers_of_selections[i]))  # 置信区间
            upper_conf_bound = r_i + delta_i
        else:
            upper_conf_bound = 1e400  # 如果广告未被选择过，设为无穷大，确保优先选择
        if upper_conf_bound > max_upper_conf:
            max_upper_conf = upper_conf_bound
            ad = i

    ads_selected.append(ad)  # 记录选择的广告
    numbers_of_selections[ad] += 1
    reward = datasets.values[n, ad]  # 选择的广告的奖励值
    sums_of_rewards[ad] += reward
    total_reward += reward

# 输出结果
print("ads_selected:", ads_selected)
print("numbers_of_selections:", numbers_of_selections)
print("sums_of_rewards:", sums_of_rewards)

三、代码解析

1. 参数初始化

   • (N)：用户访问次数（即数据集总行数）。
   • (d)：广告数量。
   • numbers_of_selections：记录每个广告被选择的次数，用于计算置信区间。
   • sums_of_rewards：记录每个广告的奖励总和，用于计算平均奖励。

2. UCB计算逻辑

   • 对于每个广告，如果已经被选择过，计算其平均奖励和置信区间；如果未被选择过，设为无穷大，确保广告被选择一次。
   • 更新广告的UCB值并记录具有最大UCB值的广告。

3. 更新选择结果

   • 每轮选择后，将广告索引添加到ads_selected中，并更新numbers_of_selections和total_reward。

四、运行结果分析

运行代码后，输出了如下结果：

numbers_of_selections: [705, 387, 186, 345, 6323, 150, 292, 1170, 256, 186]
sums_of_rewards: [120, 47, 7, 38, 1675, 1, 27, 236, 20, 7]

从结果可以看出：

• 广告5（索引从0开始的第4个广告）被选择了最多次（6323次），表明它的平均奖励和置信区间较优。
• 其他广告的选择次数相对较少，表明它们的潜在收益不如广告5。

五、结果可视化

为了更直观地展示广告选择的分布，我们可以绘制直方图。

plt.hist(ads_selected, bins=np.arange(d + 1) - 0.5, rwidth=0.8)
plt.title("Histogram of Ads Selection")
plt.xlabel("Ads")
plt.ylabel("Number of Selections")
plt.show()

输出的直方图显示了每个广告被选择的次数分布。

六、总结

通过本文，我们使用UCB算法成功实现了广告选择的优化，解决了多臂老虎机问题。UCB算法不仅在广告优化中有重要应用，还被广泛用于推荐系统、A/B测试等场景。

核心优势：

1. 平衡探索和利用，避免只集中在高回报选项。
2. 简单高效，适合实时决策。

改进方向：

1. 可以尝试其他算法（如Thompson Sampling）进行对比。
2. 适配更多实际场景，如动态广告CTR变化。

笔者总结

假设广告数量为 AD_COUNT，总数据条数为 N_COUNT，最大 UCB 值为 max_upper_conf，被选择的广告索引为 ad。

• 被选择广告列表：numbers_of_selections
• 每个广告对应的奖励值列表：sums_of_rewards

流程说明：

1. 前 2 × AD_COUNT 数据：

   • 用于初始化每条广告，确保其被选中。
   • 这样可以确保其平均奖励和置信区间有意义，因此需要将最大上限设为最大值。

2. 根据每个广告实际的 UCB 值计算：

   • 动态更新 max_upper_conf 为当前选择的 UCB 值。
   • ad 更新为当前 UCB 最大值的索引。
   • 如果这一轮广告中没有 UCB > max_upper_conf，则选择该广告。

3. 更新操作：

   • 对应的在 numbers_of_selections 增加。
   • 增加其对应的 datasets 中的奖励值。

希望这篇博客对你理解线性回归和其应用有所帮助！
如有错误或笔误，请及时指出！😄
一起交流，一起学习，enjoy machine learning！🚀💡