结合上下文信息的Bandit算法—LinUCB算法

2018年5月10日14:16:28 发表评论 848

上一篇:推荐系统EE问题与Bandit算法

前面介绍了很多种Bandit相关的算法,如:Naive、Epsilon-Greedy(ε-Greedy)、Thompson Sampling(汤普森采样)、UCB(Upper Confidence Bound)等,这些算法基本上都是采用走一步看一步的方式,这种方式有没有问题呢?

为什么要考虑臂的特征信息

如果通过 Bandit 算法发现某个用户喜欢购买京东的物品,那么对于一个新的物品,如果它也属于京东商城,从直觉上考虑,该用户很可能也喜欢这个新物品,但是使用之前的 Bandit 算法时,每次新增一个臂,只能从 0 开始累积数据。换句话说,之前的 Bandit 算法并没有考虑臂的特征信息,也就是说并没有考虑上下文信息。yahoo 在 2010 年发表了一篇论文:A Contextual-Bandit Approach to Personalized News Article Recommendation ,论文中介绍了一种结合上下文的 Bandit算法——LinUCB (linear UCB)算法。

岭回归

在介绍 LinUCB 算法之前,先来看下岭回归的介绍。传统的回归问题的优化目标如下:

\sum_{i}^{n}(y_{i} - x_{i}^{T}\hat{\theta})^{2}

其中,i 表示每个样本,yi 表示每个样本对应目标真实值,xiTθ 表示每个样本对应目标的估计值。

通过最小二乘法,可以解决求出 θ 的问题。最小二乘法的标准解如下:

\hat{\theta} = (X^{T}X) ^{-1}X^{T}Y

当 x 维度很高时,或者样本数小于特征数时,使用岭回归能得到更好的结果,岭回归的优化目标是:

\sum_{i}^{n}(y_{i} - x_{i}^{T}\hat{\theta})^{2} + \lambda \sum_{j}^{p}\hat{\theta}_{j}^{2}

岭回归的标准解如下:

\hat{\theta} = (X^{T}X + \lambda I) ^{-1}X^{T}Y

其中 I 表示单位矩阵。

LinUCB

LinUCB 算法假设一个物品推送给用户之后,获得的收益与相关特征呈线性关系,这里的相关特征就是指上下文信息。LinUCB 有两个版本:Disjoint 和 Hybrid,Disjoint 表示不同臂之间的不相关,也就是说参数不共享,Hybrid 表示臂之间共享一些参数。这里我们只介绍 Disjoint 模型,想了解 Hybrid 模型的可以查看原论文。

为了方便说明,假设每个臂包含一个物品,我们在每一次选择时,用户与物品的的特征构成了上下文信息,表示为 x,维度为 d,每个臂维护了一个 d 维的表示特征系数的向量 θ,使用 c 表示本次选择的收益,如果用户点击了就为 1,否则为 0。我们假定:

x^{T} \theta = c

我们的目标就是求出每个臂对应的特征系数向量 θ。如果我们知道多次选择时的上下文信息 x 及其对应的收益 c,那么我们就可通过岭回归的方式来求出每个臂对应的最优 θ。

我们以求解某个臂对应的 θ 为例(其他臂的方式一样),针对某个臂,假定我们收集了 m 次选择时的上下文信息 x 及其对应的收益 c(也就是 m 条训练样本),分别使用 D 和 C 来表示,D 是一个 mxd 的矩阵,表示这 m 次的上下文信息,C 是一个 mx1 的向量,表示这 m 次对应的收益。那么:

D \times \hat{\theta} = C

然后通过岭回归去求解出每个臂对应的最优的 θ 估计值。

\hat{\theta} = (D^{T}D + I) ^{-1}D^{T}C

求解出臂对应的 θ 的估计值之后,结合某次选择的上下文信息 x,就可以预测出收益 r:

\hat{r} = x^{T} \hat{\theta}

置信区间上边界为:

\alpha \sqrt{x^{T} (D^{T}D + I)^{-1}x}

将预期收益与置信区间上边界相加得到 p:

p=x^{T} \hat{\theta} + \alpha \sqrt{x^{T} A^{-1}x}

其中:

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

这样,在每次进行选择时,计算每个臂对应的 p,选择最大的 p 对应的臂。

整个算法的流程如下:

对照每一行解释一下 (编号从 1 开始):

  1. 设定一个参数 α,这个参数决定了我们 Explore 的程度
  2. 开始试验迭代
  3. 获取选择每一个臂时的上下文信息(也就是特征向量)x(t,a)
  4. 开始计算每一个臂的预估收益及其置信区间
  5. 如果这个臂还从没有被试验过,那么:
  6. 用 dxd 单位矩阵初始化作为 Aa
  7. 用 dx1 的零向量初始化作为 ba
  8. 处理完没被试验过的臂
  9. 使用 Aa 和 ba 来计算该臂对应的预估 θ
  10. 使用上一步计算出的预估 θ 和特征向量 x(a,t) 计算预估收益, 同时加上置信区间宽度来计算 p(t,a)
  11. 对每一个臂进行 4-10 步骤的过程
  12. 选择第 10 步计算出的最大的的 p(t,a)的值对应的臂,并观察其真实收益 rt
  13. 更新 Aat
  14. 跟新 bat
  15. 结束算法

构造特征

LinUCB 有一个重要的过程就是给用户和物品构造特征,也就是构造上下文信息(context),在原始论文中,物品是文章,下面是构造过程。

原始用户特征

  • 人口统计学:性别特征(2 类),年龄特征(离散成 10 个区间)
  • 地理信息:遍布全球的大都市,美国各个州
  • 行为类别:代表用户历史行为的 1000 个类别取值

原始文章特征

  • URL 类别:根据文章来源分成了几十个类别
  • 编辑打标签:编辑人工给内容从几十个话题标签中挑选出来的

将原始用户特征进行 one-hot 编码,构建的结果是一个 1000 多维的用户特征向量;将原始文章特征进行 one-hot 编码,构建的结果是一个 80 多维的文章特征向量。

为了减少特征维度以及能够刻画出一些非线性的关系,使用逻辑回归(Logistic Regression)拟合用户对文章的点击历史,将1000多维的用户特征向量作为 x,80多维的文章特征向量作为 y,这样就能够得到 x->y 的映射关系,也就能够将1000多维的用户特征向量映射到80多维的文章特征向量。

y = x^T\omega

这样,用户特征向量和文章特征向量维度都是80多维,对用户特征向量进行聚类,得到 5 个类簇,对文章特征向量也进行相同的操作,同样得到 5 个类簇,再加上常数 1,用户和文章各自被表示成 6 维向量。

选择 6 维的原因是因为数据表示它的效果最好。

实际上,构建特征时除了考虑用户与物品之外,还可以考虑推荐场景中的一些其他因素,例如:位置,时间等等。

总结

之前介绍的Bandit算法都没有考虑上下文信息,这会造成每次新增一个臂,只能从 0 开始累积数据。使用 LinUCB 算法可以将当前用户的特征、物品特征构成所有的相关特征,然后根据每个臂维护的特征系数,计算出预估收益。由于加入了特征,所以收敛速度比 UCB 更快。

LinUCB 以及所有的 Bandit 算法都有个缺点:同时处理的候选臂数量不能太多,不超过几百个最佳。因为每一次要计算每一个候选臂的期望收益和置信区间,一旦候选太多,计算代价将不可接受。

  • 个人微信号
  • 添加时请备注“脑洞大开读者”
  • weinxin
  • 微信公众号
  • 关注会有更多精彩内容!
  • weinxin

发表评论

您必须登录才能发表评论!