WSDM'22「微软+美团」探索与利用EE：HCB在整个商品空间探索

秋枫学习笔记

发布于 2022-09-19 11:10:07

4070

发布于 2022-09-19 11:10:07

文章被收录于专栏：秋枫学习笔记

关注我们，提升效率

title：Show Me the Whole World: Towards Entire Item Space Exploration for Interactive Personalized Recommendations
link：https://arxiv.org/pdf/2110.09905.pdf
from：WSDM 2022

1. 导读

EE是推荐系统中不变的话题，我们需要通过探索用户的兴趣来避免进入闭环，增加推荐系统的多样性和个性化，因此需要在探索和利用之间做权衡。

本文提出了两种简单高效的分层 Contextual bandit （CB）算法，使得经典的CB方法，如linUCB和汤普森采样可以用于整个商品空间，而不是小型商品集合。首先，通过自底向上的聚类来构建一颗分层树；然后，通过分层CB（HCB）算法来探索用户的兴趣。

总体思路：通过聚类将不同商品聚类，然后根据相似度构建树，最后通过经典的MAB算法进行树的遍历和参数跟新。通过聚类将大型商品空间缩小，从而使得整个算法可以在整个商品空间中应用。

2. 基础与问题

2.1 推荐系统中的UCB

推荐系统可以被看做是一个智能体，包含M个用户和N个商品。每一轮迭代t=1,2,...,T，给定用户u智能体根据策略π推荐一个商品

i_{\pi}(t)

，然后从用户那得到反馈，比如，如果用户对其进行点击，则

r_{\pi}(t)=1

，否则为0。最优策略表示为

\pi^*

，目标就是学习到一个策略使得累积遗憾最小，公式如下，由于现实中没有最优策略，因此将公式改写为最大化累积奖励

\sum_{t=1}^T{E[r_{\pi}(t)]}

。

\boldsymbol{R}(T)=\sum_{t=1}^{T}\left(E\left[r_{\pi^{*}}(t)\right]-E\left[r_{\pi}(t)\right]\right)

bandit算法的核心是在利用（完全基于从用户交互历史中学习的用户资料进行推荐）和探索（找出用户可能更喜欢的新项目）之间找到最佳权衡，从而使用户多样化新的兴趣有一定的机会暴露，同时系统不会在用户不感兴趣的项目上浪费太多资源。以用户为中心的算法LinUCB为例，每个商品看作是一个手臂，在第t轮，当接收到用户请求，智能体通过下式选择一个手臂

a_{\pi}(t)

，

a_{\pi}(t)=\underset{a \in \mathcal{A}_{t}}{\arg \max } R_{a}(t)+C_{a}(t)

LinUCB的策略π是特征向量

x_a

和可学习参数θ之间的线性函数，

R_a(t)=\theta_ux_a+\eta

，其中η是高斯随机变量，表示噪声。上界Ca衡量奖励估计的不确定性。参数θ和上界C的计算公式如下，其中Dt是直到t时，交互臂的特征矩阵，α是超参数，r_t是直到t时的用户响应向量。

\begin{aligned} \boldsymbol{\theta}_{u} &=\left(D_{t}^{T} D_{t}+I_{d}\right)^{-1} D_{t}^{T} \boldsymbol{r}_{t} \\ C_{a}(t) &=\alpha \sqrt{\boldsymbol{x}_{a}^{T}\left(D_{t}^{T} D_{t}+\boldsymbol{I}_{d}\right)^{-1} \boldsymbol{x}_{a}} \end{aligned}

2.2 挑战

如LinUCB选择商品的公式所示，LinUCB 需要枚举和计算每个臂的分数，然后选择最好的一个。在现代推荐系统中，商品的数量通常非常大（数百万甚至数十亿），这使得无法计算所有商品的分数。因此，现有的典型设置是在时间𝑡从整个𝑁臂中随机抽取少量𝐾（例如50个）臂，并在这个小臂集A𝑡上执行LinUCB；在行业中，bandit算法只能应用于候选池较小的场景，例如推荐系统的post-ranking阶段、首页热门item排名、广告创意排名等。为了充分挖掘用户潜在的兴趣，最好将bandit模块放在推荐系统的项目检索阶段（也称为召回阶段），其中候选池是整个商品集。否则，在推荐系统的排名后阶段，候选者实际上是由推荐模型提出的，并且与用户过去的行为密切相关。因此，在推荐系统的后期阶段探索用户的兴趣意义不大。

为了解决上述问题，本文作者提出HCB在整个商品空间中做探索。所提的框架1的总体思路：基于树的探索。整个商品集可以组织为一个层次树结构 H，其中节点链接到共享一些共同主题或用户兴趣的商品子集，并且从上到下移动的节点反映了主题/兴趣分区正在从粗到细。在基于树的探索过程中，首先根据某种机制选择一个节点，然后从链接到该节点的候选中选择一个商品。用户对所选项目的反馈不仅会更新item-wise的用户偏好估计，还会沿着层次路径更新node-wise的用户偏好估计。

3. 方法

3.1 树的构建

由于不同类别下的商品数不平衡，并且缺乏对用户集体行为的利用，简单地使用类别分类法可能会导致性能不理想。因此，首先基于物品内容和用户点击行为学习商品的embedding，然后设计一种基于K-Means聚类算法的自下而上的聚类方法，形成用于对物品之间的依赖关系进行建模的层次树。具体来说，为了构建具有 𝐿 层的树结构，

首先，根据商品embedding的相似性，将 𝑁 个商品聚类为

k_L

个不同的子集。将每个子集视为树上的一个新节点，节点的embedding是属于该节点的所有商品embedding的均值。

之后，这些

k_L

个节点将使用 K-Means 进一步聚类为

k_{L-1}

个不同的子集，每个子集将被视为树上的一个新节点，形成父子关系。

此步骤将重复多次，直到树结构的深度达到𝐿。
最后，构建的树结构，用 H 表示，在每一层都包含 {𝑘0, 𝑘1, 𝑘2, · · · , 𝑘𝐿} 个节点，其中𝑘0 = 1，因为只有一个根节点出现在第一层。直观上，同一节点内的商品彼此之间的相似度更高，因此聚类结果反映了商品之间的依赖关系。在H中，只有根节点没有父节点，叶节点没有子节点。

3.2 HCB

本文所提方法可以与原有的经典bandit算法相结合的，使其可以在整个商品空间中进行探索，这里以LinUCB为例。

HCB有两种类型的臂：层次树 H 上的节点和叶节点的商品。H 上的每个节点代表一组商品。叶节点的特征向量是其上的商品的平均池化，非叶节点的特征向量是其子节点特征向量的平均池化。HCB 算法按顺序做出决策，从根节点开始到叶节点。在第 𝑙 层的任何非叶节点

n^{(l)}(t)

，策略 𝜋 通过假设手臂的预期回报是线性的，从

Ch(n^{(l)}(t))

中选择一个子节点它的特征向量是

{\theta_{u}^{(l)}}^TX_n

，θ是可学习参数，𝑫 是由在第 𝑙 层交互的商品组成的矩阵，𝑫的每一行代表一个商品的特征向量。θ的计算公式如下，其中

是单位阵，r是在第

层的历史奖励。

\theta_{u}^{(l)}=\left(D^{(l)^{T}} D^{(l)}+I\right)^{-1} D^{(l)^{T}} r^{l}

令

A^{(l)}=D^{(l)^{T}} D^{(l)}+I

，则其上界计算方式如下，可以发现整体的公式和原始的LinUCB是类似的。

n^{(l+1)}(t)=\underset{n \in C h\left(n^{(l)}(t)\right)}{\arg \max }\left(\theta_{u}^{(l)^{T}} X_{n}+\alpha \sqrt{X_{n}^{T} A^{(l)^{-1}} X_{n}}\right)

如果给用户推荐

i_{\pi}(t)

后获得奖励

r_{\pi}(t)

，那么从root到

n^{(L)}(t)

路径上的所有节点都获得奖励r，然后可以给每一层的节点对应的参数

\{\theta_u^{(0)},\theta_u^{(1)},...,\theta_u^{(L)}\}

进行更新，其中

\theta_u^{(0)}

表示商品臂，其他的

\theta_u^{(*)}

表示节点臂。更新方式可以写成下式，其中A被初始化为单位阵，b被初始化为0向量，X是embedding。

\begin{array}{l} A^{(l)} \leftarrow A^{(l)}+X^{(l)} X^{(l)^{T}} \\ b^{(l)} \leftarrow b^{(l)}+r_{\pi}(t) X^{(l)} \\ \theta_{u}^{(l)} \leftarrow A^{(l)^{-1}} b^{(l)} \end{array}

伪代码如下，以图1为例，它在层次结构树中有三层。agent依次做出三个决策，最后选择路径{𝐴,𝐶,𝐼,𝑃}。然后agent将在叶节点𝑃的商品中启动另一个多臂老虎机选出需要的商品。所选的商品对应的奖励将通过更新奖励历史

r^{(*)}

影响层次树上的参数θ估计和交互历史

D^{(*)}

。

3.3 pHCB

HCB通过顺序决策过程了解每个用户的兴趣，并且总是从到达的叶子节点中选择项目，这可能会导致两个问题：

（1）上层做出的决策严重影响下层节点的范围。一旦策略在某个级别做出了错误的决定，其余的选择都是次优的。当树层次结构更深时，问题尤其如此。这种现象为错误传播；
(2) 用户可能对多个子节点感兴趣，贪心选择可能无法捕捉到用户的综合兴趣。因此，进一步提出了一种渐进式分层CB（pHCB）算法，用于在树上以另一种方式进行探索。主要思想是根据历史探索获得的反馈，从上到下不断扩大感受野。

感受野定义：感受野是一组个性化的节点，代表每个用户探索的当前潜在兴趣。在第一轮，感受野只包含根节点（或者根据先验知识得到的集合），随着探索过程的进行，当以自适应自上而下的方式满足预定条件时，感受野将扩大（和缩小）。感受野中的节点称为可见节点。

在 HCB 中，只有叶节点与一组商品相关联。相比之下，在 pHCB 中，允许策略选择一个非叶节点，然后从与该非叶节点关联的商品集中推荐一个商品。以下定义来定义每个非叶子节点包含的商品集合。

定义：给定非叶子节点n和其子节点ch(n)，n的商品集合是所有子节点的商品集合的并集。

在第 𝑡 轮，智能体对用户 𝑢，其感受野表示为 V𝑢 (𝑡)。pHCB 算法将 V𝑢 (𝑡) 中的每个节点视为一个臂，并选择具有最高估计奖励的臂(n(t))。然后使用 LinUCB 算法从选定的𝐼(𝑛(𝑡))（n(t)包含的商品集合）中选择一个商品 𝑖𝜋 (𝑡) 并收集用户的反馈。pHCB 直接从感受野中选择一个手臂，无需执行顺序决策过程，避免了上述 HCB 的担忧。

伪代码如下所示，以图2为例，假设在

T_a

轮，用户𝑢的感受野由三个节点组成：𝐵、𝐶和𝐷。在接下来的几轮中，如果节点𝐶被多次选中并获得多个正奖励，使其满足扩展条件，则其子节点𝐺，𝐻，𝐼将被添加到感受野中以替换𝐶。结果，在回合

T_b

，感受野包括节点𝐵，𝐷，𝐺，𝐻，𝐼。通过这种方式，pHCB 将感受野从粗到细扩展，逐步发现用户的兴趣。