提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Bandit算法学习与总结（二）：Disjoint LinUCB、Hybrid LinUCB

算法学习 总结 hybrid
2023-06-13 09:12:48 时间

关注我们，一起学习~

1. 导读

在网上找了一些相关的博客，感觉写的多多少少不是很全，所以简单总结了一下笔记。

LinUCB是UCB的升级版，上一篇文章Bandit算法学习与总结（一）介绍的贪心方法，汤普森采样和UCB都是context-free的方法，即都是埋头苦干类型的，其他特征跟咱都没关系。而LinUCB是contextual bandit方法，即利用现有的相关特征（包括用户的特征，商品的特征等）对UCB的均值和上界进行估计，提升了整体的性能。

LinUCB的基本假设：商品被推荐给用户后，其期望收益和特征（context）线性相关。LinUCB主要包含两类：Disjoint LinUCB，Hybrid LinUCB。

2. Disjoint LinUCB

先上伪代码，伪代码中主要涉及了A，b，x等符号，将在下面内容中进行解释。

disjoint LinUCB的每个臂的参数不共享，即每条臂预测自己的，互不干扰。基于LinUCB的基本假设，可以得到一个基本的公式如下，其中E为期望收益，x为第t次第a条臂对应的特征，θ为第a条臂的参数。

E(r_{t,a}|x_{t,a})=x^T_{t,a}\theta_a

上面公式中的x为一次实验中对应的特征，那么如果实验m次，则可以得到一个特征矩阵

D_a \in \mathbb{R}^{m \times d}

，并且m次实验中可以得到m次反馈，例如点击和未点击，可以表示为一个向量

c_a

。像常见的推荐方法或者机器学习模型一样，将反馈视为监督信息，有了参数和特征，就可以构建损失函数来更新对应的参数θ了，损失函数如下，

loss=(c_a-D_a\theta_a)^2+\lambda \theta_a^2

Q：为什么用这样一个损失函数

A：

  • 可以基于岭回归得到参数，其作用是当样本数少于特征数时，可以对回归参数进行修正；
  • 从形式上看，可以反映出bandit算法中遗憾的概念，即希望减小每个臂的遗憾或者说误差

对于这样的loss，可以直接计算得到对应的参数θ。

Q：我们的目标是要最小化该loss，那么对于这样的二次式，如何才能得到最小化的loss呢？

A：基于岭回归进行参数估计，通过对θ求导，使导数为0得到下式，

\hat{\theta}_a = (D_a^TD_a+I)^{-1}D_a^Tc_a

令

A=(D_a^TD_a+I)

，

b=D_a^Tc_a

这就得到了伪代码中对应的A和b。有了A和b，则可以得到θ，则可以根据θ和对应的特征计算出每一条臂对应的期望收益，有了期望收益，还需要一个上界，来反映其不确定性。上界公式为

\alpha \sqrt{x_{t,a}^TA^{-1}_ax_{t,a}}

，其中

\alpha=\sqrt{\ln(2/\delta)/2}

，δ为超参数。最后，选择所有臂中分数

x_{t,a}^T\hat{\theta}_a+\alpha \sqrt{x_{t,a}^TA_a^{-1}x_{t,a}}

最大的臂进行推荐。

3. Hybrid LinUCB

混合LinUCB相对于上述LinUCB的区别在于，臂与臂之间是相关的，不是完全独立的。则其每条臂的期望收益公式为下式，其中z为用户/商品的组合特征，β为所有臂的参数，公式整体相当于加号右边考虑局部的单独的臂，加号右边考虑臂之间的关系。

E(r_{t,a}|x_{t,a})=z_{t,a}^T\beta^*+x_{t,a}^T\theta_a^*

伪代码如下，其中除了A和b之外多了矩阵B，根据岭回归进行计算得到θ的计算方式（12行），A和b还是原来的含义，B表示和β相关的系数。其上界计算方式为13,14行。

4. 参考

https://blog.csdn.net/Gamer_gyt/article/details/103604188

以下两篇博客中有对应的代码，感兴趣的小伙伴可以查阅

https://zhuanlan.zhihu.com/p/38875273

https://zhuanlan.zhihu.com/p/21404922

相关文章