浅析LinUCB算法的流程和优点
。今天的文章就来介绍一种结合上下文信息的bandit方法，linucb，它是contextual bandits算法框架的一种。
本文的原文是雅虎的新闻推荐算法，里面公式是真的挺多的，而且涉及到了两种linucb算法，本文只介绍第一种方法。感兴趣的同学可以阅读原文。
linucb浅析 这里只简单介绍一下linucb算法的流程，真的是浅析，浅析！
在推荐系统中，通常把待推荐的商品作为mab问题的arm。ucb是context-free类的算法，没有充分利用推荐场景的上下文信息，为所有用户的选择展现商品的策略都是相同的，忽略了用户作为一个个活生生的个性本身的兴趣点、偏好、购买力等因素，因而，同一个商品在不同的用户、不同的情景下接受程度是不同的。故在实际的推荐系统中，context-free的mab算法基本都不会被采用。
与context-free mab算法对应的是contextual bandit算法，顾名思义，这类算法在实现e&e时考虑了上下文信息，因而更加适合实际的个性化推荐场景。
在linucb中，每一个arm维护一组参数，用户和每一个arm的组合可以形成一个上下文特征（上下文特征的特征维度为d），那么对于一个用户来说，在每个arm上所能够获得的期望收益如下：
对于一个老虎机来说，假设手机到了m次反馈，特征向量可以写作da(维度为md)，假设我们收到的反馈为ca(维度为m1)，那么通过求解下面的loss，我们可以得到当前每个老虎机的参数的最优解：
这其实就是岭回归嘛，我们很容易得到最优解为：
既然是ucb方法的扩展，我们除了得到期望值外，我们还需要一个置信上界，但是，我们没法继续用chernoff-hoeffding bound的定理来量化这个上界，幸运的是，这个上界已经被人找到了：
因此，我们推荐的item就能够确定了：
可以看到，我们在计算参数及最后推荐结果的时候，用到了以下几部分的信息：上下文特征x，用户的反馈c。而这些信息都是可以每次都存储下来的，因此在收集到了一定的信息之后，参数都可以动态更新，因此我们说linucb是一种在线学习方法。
什么是在线学习？个人简单的理解就是模型的训练和更新是在线进行的，能够实时的根据在线上的反馈更新模型的参数。
好了，我们来看一下linucb算法的流程吧：
上面的ba可以理解为特征向量x和反馈r的乘积。
是否觉得一头雾水，不用着急，我们通过代码来一步步解析上面的流程。
2、linucb代码实战 本文的代码地址为：
https://github.com/princewen/tensorflow_practice/blob/master/recommendation/basic-bandit-demo/basic-linucb.py
设定超参数和矩阵 首先我们设定一些超参数，比如α，正反馈和负反馈的奖励程度r1，r0，上下文特征的长度d
self.alpha = 0.25self.r1 = 0.6self.r0 = -16self.d = 6# dimension of user features
接下来，我们设定我们的几个矩阵，比如a和a的逆矩阵，b(x和r的乘积），以及参数矩阵：
self.aa = {} # aa : collection of matrix to compute disjoint part for each article a, d*dself.aai = {} # aai : store the inverse of all aa matrixself.ba = {} # ba : collection of vectors to compute disjoin part, d*1self.theta = {}
初始化矩阵 初始化矩阵对应上面的4-7步，a设置为单位矩阵，b设置为0矩阵，参数也设置为0矩阵，注意的是，每个arm都有这么一套矩阵：
def set_articles(self,art): for key in art: self.aa[key] = np.identity(self.d) # 创建单位矩阵 self.ba[key] = np.zeros((self.d,1)) self.aai[key] = np.identity(self.d) self.theta[key] = np.zeros((self.d,1))
计算推荐结果 计算推荐结果对应于上面的8-11步，我们直接根据公式计算当前的最优参数和置信上界，并选择最大的arm作为推荐结果。代码中有个小trick，及对所有的arm来说，共同使用一个特征，而不是每一个arm单独使用不同的特征：
def recommend(self,timestamp,user_features,articles): xat = np.array([user_features]) # d * 1 xa = np.transpose(xat) aai_tmp = np.array([self.aai[article] for article in articles]) theta_tmp = np.array([self.theta[article] for article in articles]) art_max = articles[np.argmax(np.dot(xat,theta_tmp) + self.alpha * np.sqrt(np.dot(np.dot(xat,aai_tmp),xa)))] self.x = xa self.xt = xat self.a_max = art_max return self.a_max
更新矩阵信息 这对应于上面的12-13步，根据选择的最优arm，以及得到的用户反馈，我们更新a和b矩阵：
def update(self,reward): if reward == -1: pass elif reward == 1or reward == 0: if reward == 1: r = self.r1 else: r = self.r0 self.aa[self.a_max] += np.dot(self.x,self.xt) self.ba[self.a_max] += r * self.x self.aai[self.a_max] = np.linalg.inv(self.aa[self.a_max]) self.theta[self.a_max] = np.dot(self.aai[self.a_max],self.ba[self.a_max]) else: # error
写到这里，本来应该就要结束了，可是脑子里又想到一个问题，为什么可以直接通过加法来更新a矩阵？其实是个很简单的问题，试着写出a矩阵中每个元素的计算公式来，问题就迎刃而解了！
结语 总结一下linucb算法，有以下优点（来自参考文献3，自己又增加了一条）：1）由于加入了特征，所以收敛比ucb更快（论文有证明）；2）特征构建是效果的关键，也是工程上最麻烦和值的发挥的地方；3）由于参与计算的是特征，所以可以处理动态的推荐候选池，编辑可以增删文章；4）特征降维很有必要，关系到计算效率。5）是一种在线学习算法。
什么是Type-C？ USB有哪些接口形式？
运动控制行业深度：高端装备“大脑”，机器人孕育新空间
条纹投影相移三维形貌测量技术
中兴举行发布会：S30系列发布
自动驾驶技术的衍生：自动驾驶轮椅
浅析LinUCB算法的流程和优点
原汁机电机行星齿轮传动设计方案
关于电动车充电桩安装条件，电动车充电桩安装条件介绍
什么叫软包锂电池
格兰仕宣布推出两款家电芯片,与RISC-V芯片企业达成战略合作
ZXCT199 电流检测器用于精确的高侧/低侧电流测量
面对AMD的大爆发英特尔还有哪些处理器值得选
电子保护电路完整指南（图文详解）
电源芯片U6101S的特点
工商银行推出AR版年册红包，科技感爆棚
IBM 2nm芯片采用的GAA技术能否替代FinFET而延续摩尔定律的神话？
一文带你看懂“亚洲最大智能化制造车间” 三一造
畅游网络无界限，华为云连接CC服务打造全球级云网络
面向未来工程师教育，泰克助力坦普尔大学创造尖端工程设计空间
基于Motionchip的直流无刷伺服电机运动控制系统设计和
本文的原文是雅虎的新闻推荐算法，里面公式是真的挺多的，而且涉及到了两种linucb算法，本文只介绍第一种方法。感兴趣的同学可以阅读原文。
linucb浅析 这里只简单介绍一下linucb算法的流程，真的是浅析，浅析！
在推荐系统中，通常把待推荐的商品作为mab问题的arm。ucb是context-free类的算法，没有充分利用推荐场景的上下文信息，为所有用户的选择展现商品的策略都是相同的，忽略了用户作为一个个活生生的个性本身的兴趣点、偏好、购买力等因素，因而，同一个商品在不同的用户、不同的情景下接受程度是不同的。故在实际的推荐系统中，context-free的mab算法基本都不会被采用。
与context-free mab算法对应的是contextual bandit算法，顾名思义，这类算法在实现e&e时考虑了上下文信息，因而更加适合实际的个性化推荐场景。
在linucb中，每一个arm维护一组参数，用户和每一个arm的组合可以形成一个上下文特征（上下文特征的特征维度为d），那么对于一个用户来说，在每个arm上所能够获得的期望收益如下：
对于一个老虎机来说，假设手机到了m次反馈，特征向量可以写作da(维度为md)，假设我们收到的反馈为ca(维度为m1)，那么通过求解下面的loss，我们可以得到当前每个老虎机的参数的最优解：
这其实就是岭回归嘛，我们很容易得到最优解为：
既然是ucb方法的扩展，我们除了得到期望值外，我们还需要一个置信上界，但是，我们没法继续用chernoff-hoeffding bound的定理来量化这个上界，幸运的是，这个上界已经被人找到了：
因此，我们推荐的item就能够确定了：
可以看到，我们在计算参数及最后推荐结果的时候，用到了以下几部分的信息：上下文特征x，用户的反馈c。而这些信息都是可以每次都存储下来的，因此在收集到了一定的信息之后，参数都可以动态更新，因此我们说linucb是一种在线学习方法。
什么是在线学习？个人简单的理解就是模型的训练和更新是在线进行的，能够实时的根据在线上的反馈更新模型的参数。
好了，我们来看一下linucb算法的流程吧：
上面的ba可以理解为特征向量x和反馈r的乘积。
是否觉得一头雾水，不用着急，我们通过代码来一步步解析上面的流程。
2、linucb代码实战 本文的代码地址为：
https://github.com/princewen/tensorflow_practice/blob/master/recommendation/basic-bandit-demo/basic-linucb.py
设定超参数和矩阵 首先我们设定一些超参数，比如α，正反馈和负反馈的奖励程度r1，r0，上下文特征的长度d
self.alpha = 0.25self.r1 = 0.6self.r0 = -16self.d = 6# dimension of user features
接下来，我们设定我们的几个矩阵，比如a和a的逆矩阵，b(x和r的乘积），以及参数矩阵：
self.aa = {} # aa : collection of matrix to compute disjoint part for each article a, d*dself.aai = {} # aai : store the inverse of all aa matrixself.ba = {} # ba : collection of vectors to compute disjoin part, d*1self.theta = {}
初始化矩阵 初始化矩阵对应上面的4-7步，a设置为单位矩阵，b设置为0矩阵，参数也设置为0矩阵，注意的是，每个arm都有这么一套矩阵：
def set_articles(self,art): for key in art: self.aa[key] = np.identity(self.d) # 创建单位矩阵 self.ba[key] = np.zeros((self.d,1)) self.aai[key] = np.identity(self.d) self.theta[key] = np.zeros((self.d,1))
计算推荐结果 计算推荐结果对应于上面的8-11步，我们直接根据公式计算当前的最优参数和置信上界，并选择最大的arm作为推荐结果。代码中有个小trick，及对所有的arm来说，共同使用一个特征，而不是每一个arm单独使用不同的特征：
def recommend(self,timestamp,user_features,articles): xat = np.array([user_features]) # d * 1 xa = np.transpose(xat) aai_tmp = np.array([self.aai[article] for article in articles]) theta_tmp = np.array([self.theta[article] for article in articles]) art_max = articles[np.argmax(np.dot(xat,theta_tmp) + self.alpha * np.sqrt(np.dot(np.dot(xat,aai_tmp),xa)))] self.x = xa self.xt = xat self.a_max = art_max return self.a_max
更新矩阵信息 这对应于上面的12-13步，根据选择的最优arm，以及得到的用户反馈，我们更新a和b矩阵：
def update(self,reward): if reward == -1: pass elif reward == 1or reward == 0: if reward == 1: r = self.r1 else: r = self.r0 self.aa[self.a_max] += np.dot(self.x,self.xt) self.ba[self.a_max] += r * self.x self.aai[self.a_max] = np.linalg.inv(self.aa[self.a_max]) self.theta[self.a_max] = np.dot(self.aai[self.a_max],self.ba[self.a_max]) else: # error
写到这里，本来应该就要结束了，可是脑子里又想到一个问题，为什么可以直接通过加法来更新a矩阵？其实是个很简单的问题，试着写出a矩阵中每个元素的计算公式来，问题就迎刃而解了！
结语 总结一下linucb算法，有以下优点（来自参考文献3，自己又增加了一条）：1）由于加入了特征，所以收敛比ucb更快（论文有证明）；2）特征构建是效果的关键，也是工程上最麻烦和值的发挥的地方；3）由于参与计算的是特征，所以可以处理动态的推荐候选池，编辑可以增删文章；4）特征降维很有必要，关系到计算效率。5）是一种在线学习算法。
什么是Type-C？ USB有哪些接口形式？
运动控制行业深度：高端装备“大脑”，机器人孕育新空间
条纹投影相移三维形貌测量技术
中兴举行发布会：S30系列发布
自动驾驶技术的衍生：自动驾驶轮椅
浅析LinUCB算法的流程和优点
原汁机电机行星齿轮传动设计方案
关于电动车充电桩安装条件，电动车充电桩安装条件介绍
什么叫软包锂电池
格兰仕宣布推出两款家电芯片,与RISC-V芯片企业达成战略合作
ZXCT199 电流检测器用于精确的高侧/低侧电流测量
面对AMD的大爆发英特尔还有哪些处理器值得选
电子保护电路完整指南（图文详解）
电源芯片U6101S的特点
工商银行推出AR版年册红包，科技感爆棚
IBM 2nm芯片采用的GAA技术能否替代FinFET而延续摩尔定律的神话？
一文带你看懂“亚洲最大智能化制造车间” 三一造
畅游网络无界限，华为云连接CC服务打造全球级云网络
面向未来工程师教育，泰克助力坦普尔大学创造尖端工程设计空间
基于Motionchip的直流无刷伺服电机运动控制系统设计和