一个正在进行的推荐系统系列
今天又一次，连续100…01天，我拿着尚未打开的晚餐盒子，一边浏览Netflix寻找一部剧集，一边咀嚼食物。我的推荐列表里充斥着太多亚洲浪漫和美国成长的建议，可能是基于我一个月或两个月前观看的一两部这些类型的剧集。”这里没什么好看的…”–我叹了口气，阅读完所有剧情梗概后，有信心预测剧情将如何展开。我拿出我的备用娱乐选择，Tiktok，同时下意识地想着我可能需要不感兴趣一些视频，并点赞、保存其他视频，以…推荐算法给我提供一些新的内容。
推荐系统（RecSys）可以被认为是一种广泛应用的算法，已经深入到我们的日常生活中，在从1到Chat-GPT的程度上，对学术界和非学术界来说，它几乎像是80年代的趋势。然而，它绝不是一个完美的算法。运营推荐应用程序涉及的伦理、社会、技术和法律挑战从未成为研究的重点（就像大多数其他技术产品一样）。选择性群体不公和隐私侵犯是围绕RecSys的一些热门关切的例子，这些关切仍然没有得到完全解决。此外，还存在许多更微妙的问题很少得到充分的探讨，其中之一是个体决策过程中的自主权丧失。”强大的”RecSys无疑会推动用户朝特定方向发展[2]，使他们购买、观看、思考、相信他们本不会这么做，如果他们没有受到这样的操纵。
因此，当我开始学习和深入研究RecSys的优点和缺点时，我想写一系列关于我研究生学习过程的文章…从零开始！我觉得可以从思考电影和…汤普森抽样开始！
汤普森抽样
汤普森抽样（TS）不仅是推荐系统文献中的基础算法之一，也是强化学习中的基础算法之一。正如Samuele Mazzanti在这篇令人惊叹的文章中清楚地解释的那样，它在在线学习环境中可以被认为是更好的A/B测试。简单来说，在电影推荐的背景下，TS尝试识别最适合推荐给我的电影，以最大程度地增加我点击观看的机会。它可以有效地使用相对较少的数据来更新参数，每次观察到我点击或不点击某部电影时。粗略地说，这种动态特性使得TS能够考虑到除了我的观看历史和书签系列之外的实时因素，例如我在使用应用程序时的浏览或搜索结果，以给我最合适的建议。然而，在这个针对初学者的友好教程中，让我们来看一下下面简化的分析。
让我们进一步拆分吧！
考虑这3部电影，它们都很精彩，我个人对它们有自己的评级。在这3部电影中，假设有一部电影，如果出现在我的推荐列表中，我会百分之百地重新观看它，还有一部我极有可能不会重新观看（5%），还有一部有70%的可能性我会在看到它时点击观看。TS显然在事先并不知道这些关于我的信息，它的目标是学习我的行为，以便像常见的直觉那样，推荐给我它知道我肯定会点击观看的电影。
在TS算法中，主要的工作流程如下：
- 行动：TS向我建议一部特定电影，从成百上千部电影中选择
- 结果：我认为这部电影听起来足够有趣，点击观看，或者我觉得无聊，在阅读简介后离开页面
- 奖励：可以理解为如果我点击观看某部电影，TS能够获得的“分数”，或者如果我不点击，TS会错失的分数。在基本的电影或广告推荐设置中，我们可以将奖励视为结果的等效，所以点击一次电影等于一分！
- 更新知识：TS记录下我的选择，并更新对我最喜欢的电影的信念。
- 重复步骤1（可以在我当前的浏览会话中进行，也可以在第二天的晚餐时间进行），但现在对我的喜好有了一些额外的了解。
探索/开发
这是这个领域中最常用的术语，也是TS和其他相关算法的区别所在。步骤5是这种逻辑发挥作用的地方。在TS的世界中，每件事情都有一定的不确定性。举个例子，我一周喝3次拿铁和5次抹茶，并不代表我比拿铁更喜欢抹茶，也许只是这一周（而且平均每周我其实喝的拿铁比抹茶多）？因此，在TS中，一切都由某种分布表示，而不仅仅是单个数字。
刚开始，TS对于我对电影的喜好充满了不确定性，所以它的优先任务是通过给我提供许多不同的电影建议来探索观察我的反应。经过一些点击和跳过后，TS可以大致了解我倾向于点击的电影和没有益处的电影，因此它对下次给我推荐什么电影更有信心。这时候，TS开始开发高度有益的选项，给我经常观看的电影，但仍给探索留有余地。随着观察的增加，信心会逐渐建立起来，在简单的情况下，探索工作现在已经非常小，因为TS已经对那些能够带来很多回报的推荐有很高的信心。
因此，探索与开发常常被称为权衡或者困境，因为过多的探索（即尽管已经有足够证据知道这样的选择不是最优的，但仍然很少排除低价值选择）会导致很大的损失，而过多的开发（即过快地排除太多选项）可能会错误地排除真正的最优行动。
分布：贝塔－伯努利
正如上述抹茶-拿铁图中，TS使用不同类型的分布来理解我们对不同选项的喜好。在最基本的电影（以及广告）情况下，我们通常使用贝塔－伯努利组合。
伯努利分布是一种离散分布，只有两种可能的结果：1和0。伯努利分布只有一个参数，表示某个变量（比如Y）取值为1的概率。例如，如果我们说Y~ Bern(p)，并且假设p=0.7，那意味着Y有70%的概率取值1，1-p=1-0.7=0.3的概率取值0。因此，伯努利分布适合用来建模奖励（也是我们的结果），因为我们的奖励只有两种二元结果：点击或未点击。
贝塔分布被用来模拟关于我的电影兴趣的TS信念。贝塔分布有两个参数，alpha和beta，通常被视为成功和失败的次数，两者都必须≥1。因此，适合使用贝塔分布来模拟我点击观看和跳过电影的次数。让我们来看一个例子。在这里，这些是表示3部电影的3个不同的贝塔分布，在10次观察中，所以所有3部电影的总点击和跳过次数是相同的（10次），但点击和跳过率是不同的。对于电影1，我点击观看2次（alpha = 2）和跳过8次（beta = 8）；对于电影2，我点击观看5次和跳过5次；对于电影3，我点击观看8次和跳过2次。
根据图表，我们可以看到我重新观看电影2的概率在50%左右达到峰值，而电影1的这个概率要低得多。我们可以把这些曲线看作是概率的概率（我重新观看电影的概率），因此贝塔分布非常适合表示TS对于我的电影偏好的信念。
算法
在本节中，我将帮助您对算法在实现和方法上有一个清晰的理解。首先，这是一个用伪代码和Python实现的Thompson Sampling算法的片段。伪代码来自一本关于TS的精彩书籍，名为《A tutorial on Thompson Sampling》[Russo, 2017]。
让我们逐步解析它！
样本模型
算法的第一步涉及“猜测”我对每部电影的喜好程度。如前一节所示，每部电影的我偏好可以使用贝塔曲线来表示，正如图2中的曲线那样，TS对此没有先验知识，并试图弄清楚这些贝塔曲线的样子。在t = 1（第一轮）中，TS可以假设我对所有3部电影有相同的喜好，即点击和跳过的初始次数相同（我的3个贝塔曲线将看起来相同）。
这里的三个分布是伪代码中p的含义。从每个分布中，TS将采样一个值，用theta表示，以帮助下一步的动作选择。
选择并执行动作
在这一步中，TS根据样本中最大的θ值选择要执行的动作（也就是选择要推荐的电影）。再次以图2为例。假设我们只有两部电影-只有电影1和电影3。使用最大的θ来选择动作的想法是，如果真实分布之间重叠很少，并且在我们的情况下我几乎确定地喜欢其中一个电影多于另一个电影，那么对于电影1的采样θ非常不可能比电影3的更大。同样，如果我们只考虑电影2和3，我们可以看到现在分布之间有更多的重叠。然而，如果我们继续在足够多的回合中采样更多的θ值，那么我们可以观察到电影3的θ比电影2的θ多，TS将有足够的信息来得出结论，即电影3是更好的“行动”选择。总的来说，这也是为什么未知真实分布越不相交，TS就需要更少的实验回合来确定最优动作或臂的原因。
选择并应用所选动作后，TS将从我这里收到一个响应，即我是否点击观看电影。如上所述，这个结果也被视为对应动作的奖励。TS将记录这个观察到的结果，并在下一步中用它来更新对我电影偏好的信念。
更新分布
在上面对Beta分布的描述中，我们确定了Beta分布由成功次数和失败次数所特征化。我点击观看给定电影的次数越多，它的Beta分布的最高点就越接近1；相反，我跳过推荐的次数越多，最高点就越接近于0。因此，在已经进行了推荐和记录了响应之后，对给定电影的信念的更新就是简单地将该电影的Beta分布的alpha或beta参数之一加一，取决于电影是否被点击或被跳过。
这种直观、可解释的参数更新方法是Beta伯努利模型非常常见的原因。
结果和讨论
回顾一下文章开头的场景。我们正在猜测3部电影中哪一部是最适合推荐给我，假设有一部我点击观看的概率是100%，一部是70%，而另一部只有5%的概率（再次强调，这个知识对TS来说是未知的）。第一行展示了模拟的两个不同起点，这将使我们观察到是否可以通过不同的初始先验信念达到相同的最终结果。
从图6中我们可以看到，我最终最喜欢的电影是电影1——《寄生虫》（抱歉，漫威粉丝们）！！
正如我们所见，这两种情况下的探索旅程有所不同，其中Beta(1, 1)的起始猜测结果更快地达到了被认为是我最喜欢的电影。只需进行10次回合，TS就明显地开始利用电影1，表明TS已经建议电影1并从我这里获得点击，从而使其Beta分布向右移动，因此从更新的分布中采样的θ击败了竞争对手，实现了利用行为。这种利用行为在5次回合时就已经出现，但根据对应的图表，电影1和电影3之间仍然存在很多重叠，它们的模态不完全不同，这意味着TS仍然不能完全确定电影1是否是最优动作。
另一方面，Beta(2, 3)的初始信念导致TS需要更多的轮次才能到达电影1（T=20）。即使在T=10，电影1和3之间仍存在很多不确定性，由于采样theta的随机性，电影3可能被作为最佳选择被开发。这个实验表明，关于每个动作的初始先验知识可以对最优臂的检测速度起到一定的作用，这个主题我们将在以后的文章中更加深入探讨。
需要注意的是，如果电影的实际分布几乎相同（比如电影1和3的点击率分别为100％和98％），TS很可能无法确定最优动作，因为从一个分布中采样的theta占比超过另一个分布的theta占比将被分割。因此，如果由于机会的原因电影3恰好拥有更多“更大的theta”，那么TS将更多地利用这个选项，导致将其错误地认定为最优动作。
从实验中可以得出的另一个结果是，TS只能告诉我们最佳动作是什么，但不能为我们提供关于其他选项的信息。这是因为在探索过程中，TS会快速排除那些被认为不是最优的选项，因此TS不再接收关于这些动作的进一步信息，因此它无法给出除最佳动作之外的动作之间的正确排序。
结论
在本文中，我们更深入地了解了汤普森采样算法，并通过电影推荐的模拟实施了一次实验。汤普森采样在提供预测方面主要涉及分布和先验知识，这是贝叶斯模型的核心概念，我计划在即将发表的文章中与大家进一步讨论。如果您读到了本文的结尾，感谢您花费时间阅读，希望本教程能够给您提供一个平衡的技术和直观的算法理解！如果您有任何进一步的问题，请随时通过我的LinkedIn找到我，我很愿意与您进行连接和回复！
参考资料：
[2] 推荐系统及其伦理挑战