2. it
  3. LinUCB算法理解

LinUCB算法理解

mac2025-12-02  9

解决的问题

1、UCB的算法context-free：

没有充分利用推荐场景的上下文信息，为所有用户的选择展现商品的策略都是相同的，忽略了用户作为一个个活生生的个性本身的兴趣点、偏好、购买力等因素都是不同的，因而，同一个商品在不同的用户、不同的情景下接受程度是不同的

原理

1、每个arm维护一个特征向量： θ α \theta_{\alpha} θα​

2、假设 : 每个arm的期望收益为arm特征向量的线性函数： E [ r t , a ∣ x t , a ] = x t , a T θ a E[r_{t,a}|x_{t,a}] = x_{t,a}^{T}\theta_{a} E[rt,a​∣xt,a​]=xt,aT​θa​

3、这里考虑单个arm上多次实验的总的损失函数：

m次实验，用户总特征矩阵称为：(D_a), 维度为m * n(用户特征维度)m次实验，这个arm前m次的收益为：(c_a)，维度为m*1

采用平方损失函数: l o s s = ( c a − D a θ a ) 2 + λ θ a 2 loss = (c_a - D_a\theta_a)^2 + \lambda\theta_a^2 loss=(ca​−Da​θa​)2+λθa2​

4、求损失函数的最小值，使损失函数对 (\theta_a) 求导，并且使导数为0，得到： θ a = ( D a T D a + I ) − 1 D a T c a \theta_a = (D_a^TD_a + I)^{-1}D_a^Tc_a θa​=(DaT​Da​+I)−1DaT​ca​

5、为了简洁+选取臂后方便更新数据，将两个乘积分别用A和b表示： A = ( D a T D a + I ) − 1 b = D a T c a A = (D_a^TD_a + I)^{-1} \\ b = D_a^Tc_a A=(DaT​Da​+I)−1b=DaT​ca​

6、上面得到了单个arm使loss最小的参数更新规则，对于多个 arm而言，需要计算每个arm的最大上界，选择最大的arm（老实说，这块公式推导比较麻烦，后期再深入研究）： x t , a T θ a + α x t , a T A a − 1 x t , a 其 中 α 控 制 选 择 倾 向 于 E x p l o r e 还 是 E x p l o i t α 越 小 ， a r m 的 期 望 收 益 所 占 权 重 越 大 ， 选 择 越 倾 向 于 E x p l o i t x_{t,a}^T\theta_a + \alpha\sqrt{x_{t,a}^TA_a^{-1}x_{t,a}} \\ 其中\alpha控制选择倾向于Explore还是Exploit\\ \alpha越小，arm的期望收益所占权重越大，选择越倾向于Exploit xt,aT​θa​+αxt,aT​Aa−1​xt,a​ ​其中α控制选择倾向于Explore还是Exploitα越小，arm的期望收益所占权重越大，选择越倾向于Exploit

实现流程

优点

解决了UCB等MAB算法context-free的问题，考虑到用户的特征和物品的特征计算复杂度同arm的数量成线性关系支持动态变化的候选arm集合，有新的arm出来时，实时支持对新的arm进行初始化，并添加到分数选取中在线学习：在计算arm的参数和recommend的时候，用到了上下文的特征+用户反馈，每次信息 都进行了保存更新到A和b中。A和b可以异步增量更新

引用

http://xudongyang.coding.me/linucb/

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

最新回复(0)