LinUCB算法

回到推荐列表的场景，推荐系统为用户推荐物品。user和item都可以用一系列特征表示。用户特征包括用户的统计历史行为、人口学属性信息；物品特征包括描述信息、类别信息等等。在这种场景下，探索和利用也必须是个体用户级别上实施，因为不同用户看到相同的物品的反馈差异较大。

LinUCB算法是一种基于上下文特征（用户特征、物品特征）的UCB算法，基于特征进行探索和利用。该算法结合上下文特征，选择给用户的推荐物品，同时利用用户反馈及时修正选择策略，以达到最大化收益（提升点击率）的目标。

使用互斥线性模型的LinUCB

LinUCB算法假设推荐item的每次展现收益（是否点击）是和上下文特征成线性关系的，即：

E [r t, a | x t, a] = x T t, a θ * a

$Eleftlbrack r_{t,a}|x_{t,a} rightrbrack = x_{t,a}^{T}theta_{a}^{*}$

其中 $x_{t,a}$ 表示用户特征和物品特征的合集， $r_{t,a}$ 表示第t次尝试的收益，a表示item， $theta_{a}^{*}$ 表示物品a的位置系数向量。可以看出各个item的模型参数是相互独立的（互斥）。

设 $D_{a}$ （d*m）表示为m个训练上下文， $c_{a}$ 表示每个上下文的实际收益，对训练数据 $(D_{a},c_{a})$ 使用岭回归训练出的物品a的参数为：

θ ̂ a = (D T a D a + I d) - 1 * D T a * c a

${hat{theta}}_{a} = {(D_{a}^{T}D_{a} + I_{d})}^{- 1}*D_{a}^{T}*c_{a}$

其中 $I_{d}$ 表示d*d的单位矩阵。其中在置信度 $1 - delta$ 下，模型收益与期望收益满足：

∣ ∣ x T t, a θ ̂ a - E [r t, a | x t, a] ∣ ∣ \leq α x T t, a (D T a D a + I d) - 1 x t, a ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt

$left| x_{t,a}^{T}{hat{theta}}_{a} - Eleftlbrack r_{t,a}|x_{t,a} rightrbrack right| leq alphasqrt{x_{t,a}^{T}{(D_{a}^{T}D_{a} + I_{d})}^{- 1}x_{t,a}}$

其中 $delta > 0$ ， $alpha = 1 + sqrt{lnleft( frac{2}{delta} right)/2}$ 。

上述等式给出了物品a期望收益的一个UCB，因此也就引申出了UCB的选择策略，对于第t次试验，选择以下式中最大值的物品，

a t = a r g max a \in A (x T t, a θ ̂ a + α x T t, a (A a) - 1 x t, a ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt)

$a_{t} = argbegin{matrix} max \ a in A \ end{matrix}(x_{t,a}^{T}{hat{theta}}_{a} + alphasqrt{x_{t,a}^{T}{(A_{a})}^{- 1}x_{t,a}})$

其中 $A_{a} = D_{a}^{T}D_{a} + I_{d}$ 。上述模型中预期收益 $x_{t,a}^{T}theta_{a}^{*}$ 的方差为 $x_{t,a}^{T}{(A_{a})}^{- 1}x_{t,a}$ ，即 $sqrt{x_{t,a}^{T}{(A_{a})}^{- 1}x_{t,a}})$ 为标准差。

linucb

以上为互斥线性模型LinUCB的基本算法流程，其中结合上述内容，第一行 $alpha$ 参数控制了explore的程度，即 $alpha$ 越大，置信区间上限也就越大，也就加大了explore的程度；4-7行对于新物品，使用单位阵和01向量进行参数初始化；8-9行计算item a的置信区间上限；11行选择最优item；12-13行更新选择item的模型参数。

思想上LinUCB算法类似于对召回结果重排序的方法，也是考虑用户和item的特征，来计算出收益最大的item，不同的是LinUCB借鉴了UCB的置信区间的方法来平衡exploit和explore问题，同时从LinUCB算法是一个在线的学习算法，与一般离线算法需要离线训练不同，LinUCB随着每次展示和反馈会不断优化我们的模型参数和收益。

关于LinUCB算法的介绍请参考论文

CLUB算法

CLUB(online clustering bandits)算法假设将全部用户划分成若干个用户群，每个用户群对相同推荐内容的反馈是一致的，同时自适应的调整用户群。与liner bandit一样，CLUB算法也是根据特征计算收益，不同的是CLUB算法中相同群体用户共享相同的参数向量，即第i个用户对item a的收益为：

a i (x) = u T j (i) x + \in j (i) (x)

$a_{i}left( x right) = u_{j(i)}^{T}x + in_{jleft( i right)}(x)$

其中i表示第i个user， $j(i)$ 表示第i个user所属的用户群编号， $u$ 表示每个用户群的参数向量，x表示上文下特征， $in$ 表示噪声项。

该算法在时刻t，对于用户i，维护一个向量 $u_{i}$ 的估计值 $w_{i,t}$ 。与liner bandit算法相似， $w_{i,t}$ 根据收益反馈不断更新。与LinUCB算法类似的， $w_{i,t - 1}$ 可以根据协方差矩阵 $M_{i,t - 1}$ （d*d维，初始化为单位阵）的逆和向量 $b_{i,t - 1}$ （d维向量，初始化为0向量）计算得出。

除此之外，算法需要维护一个无向图 $G_{t} = (V,E_{t})$ ，每个节点表示一个user。算法首先从完全图开始，根据 $w_{i,t}$ 的演化逐步移除节点之间的边。定义第t时刻的用户群个数为 $m_{t}$ ， ${hat{v}}_{1,t},{hat{v}}_{2,t}$ ，…… ${hat{v}}_{1,mt}$ 表示时刻t的用户划分群。显然初始状态下 $m_{1}$ =1， ${hat{v}}_{1,1} = V$ (全部用户)。

在每个时刻t $(1,2,...)$ ，用户 $i_{t}$ ，相关上下文特征向量集合为 $(x_{t,1},x_{t,2},ldotsldots x_{t,ct})$ ，用户 $i_{t}$ 所属的群为 ${hat{v}}_{hat{text{jt}},t}$ 。CLUB算法根据收益选择item的式如下：

k t = arg min k = 1, 2, \dots, c t (w ⎯ T jt^, t - 1 * x t, k + CB jt^, t - 1 * x t, k)

$begin{equation} k_{t} = mathop{argmin}_{k=1,2,ldots,ct} {({overset{overline{}}{w}}_{hat{text{jt}},t-1}^{T}*x_{t,k} + text{CB}_{hat{text{jt}},t - 1}*x_{t,k})} end{equation}$

其中 ${overset{overline{}}{w}}_{hat{text{jt}},t-1}$ 是通过同用户群内各个节点通过最小方差逼近拟合计算得出的聚合权重向量，CB为 ${overset{overline{}}{w}}_{hat{text{jt}},t-1}$ 向量的置信区间上限。

CLUB算法观察到item的收益 $a_{t}$ 后，更新协方差矩阵 $M_{it,t - 1} rightarrow M_{it,t}$ ，更新 $b_{it,t - 1} rightarrow b_{it,t}$ ；虽然不会更新其他节点的M和b，但是会隐式的影响下一轮的聚合权重向量 ${overset{overline{}}{w}}_{hat{text{jt}},t + 1}$ ；接下来判断节点 $i_{t}$ 与相邻节点的参数向量（ $w_{i,t - 1}$ ）距离，如果足够大，则将该边移除。