做网站需要板块,学软件工程培训就业机构,网页系统,科技公司建设网站本文主要介绍发表在SIGIR2018上的论文From Greedy Selection to Exploratory Decision-Making: Diverse Ranking with Policy-Value Networkswww.bigdatalab.ac.cn这篇论文利用强化学习来解决多样性排序问题#xff0c;整体思路和AlphaGo类似。Motivation在信息检索领域一个…本文主要介绍发表在SIGIR2018上的论文From Greedy Selection to Exploratory Decision-Making: Diverse Ranking with Policy-Value Networkswww.bigdatalab.ac.cn这篇论文利用强化学习来解决多样性排序问题整体思路和AlphaGo类似。Motivation在信息检索领域一个重要的目标是提供可以覆盖很多topic的检索结果也就是检索结果的多样性。简单来说就是选择候选文档的一个最小子集这个子集能够尽可能多的包含subtopic。因为文档是否新颖取决于已经选择的文档因此这是个NP-hard的问题。一些传统的方法都是把检索多样性看成是基于相关性和新颖性的一个排序问题这些方法的核心是利用贪心来选择文档每一次从候选集合中选择一个文档。贪心方法虽然可以加速在线排序但是可想而知这种方法不可避免的会陷入次优解因为它每次选择只考虑局部信息而文档的“贡献(utility)并不是独立的是与其他文档相关联的每次选择一个文档后都会改变候选集合中的剩余文档的utility理想的解决方法是探索所有文档的排序但在实际应用中这显然无法实现。得益于AlphaGo的成功作者提出利用蒙特卡洛树搜索(Monte Carlo tree search-MCTS)来改善MDP模型。新的模型 (MCTS enhanced MDP for Diverse ranking)利用一个MDP来对序列文档的选择进行建模在每次进行选择时将query和已有文档送给RNN来产生policy和valuepolicy用来进行文档的选择而value用来估计整体文档排序的质量比如 。为了防止次优解作者使用MCTS来探索每个位置的可能的文档排序由此产生一个对于当前选择的更好的policy。因为MCTS探索了更多未来可能的文档它给出的policy有更大的概率产生全局最优解。当有了更好的policy后模型通过最小化loss function来进行调整。2. MDP和MCTS马尔可夫决策过程(MDP)是建模序列决策的一个框架关键部分为StatesAction Policy Transition和Value。具体的States 是状态的集合在文章中作者定义状态为query、已有文档排序和候选文档的三元组Action 是agent可以执行的离散动作集合可选的动作会依赖于状态s记为 ; Policy 描述agent的行为它是所有可能动作的一个概率分布通过最大化长期回报进行优化Transition 是状态转移函数 也就是根据动作 将状态 映射为 Value 是状态值函数 ,用来预测当前基于policy p下状态s的长期回报。MDP模型中agent和环境在每个时刻 进行交互在每个时间步 agent接收环境的状态 然后选择一个动作 ,之后 agent进入一个新的状态 强化学习的目标是最大化长期回报也就是最大化Value 。通过MDP做的决策(根据policy选择置信度最大的动作)可能会陷入次优解理论上我们应该探索所有的决策空间来得到全局最优解但是这是不现实的。MCTS就是在决策空间中进行启发式的搜索这样更容易产生比贪心更好的决策序列。给定时刻 ,policy 以及值函数 MCTS的目标是找到一个“加强版”的策略来进行更好的决策。MCTS包含四个过程分别是SelectionExpansionSimulation/Evaluation 和 Back-propagation。Selection是从根节点开始递归的选择一个最优子节点直到到达叶子节点Expansion 指如果 不是一个终止节点那么为 创建子节点并且根据policy选择一个子节点 Simulation/Evaluation 是从 进行一次模拟直到结束。在AlphaGo Zero中使用值函数代替模拟来加速树的搜索。Back-propagation来更新当前序列中的每个节点里的数值。MCTS最终输出一个policy ,这个策略用来在 时刻选择动作。MCTS会持续的进行直到完整的episode生成为止。3. Algorithm这一部分介绍 模型模型整体如图可以看出在每个时间步模型选择一个文档首先模型通过LSTM来产生 和 然后进行搜索产生加强版的策略之后根据策略选择动作并进入下一个状态。3.1定义文档排序的MDP定义候选文档全集为 每个文档通过doc2vec模型转化为向量在时刻 状态为 其中 为query 是已选择的文档 是候选文档在初始状态( ), , 为空集动作 是可以选择的动作集合也就是对应每一个候选文档状态转移 为 其中 为将 添加到 中 为将 从 去除。每次选择新的文档query是保持不变的新文档添加到 的末尾值函数 用来估计整体排序的质量通过学习 来近似评价指标比如 。具体的值函数 的计算如下 的输入为query和已有文档的向量表示输出为cell state向量与output vector的concatenate也就是 有了值函数可以计算policy 计算方法如下 其中 为参数最终的策略函数 为 。3.2 MCTS有了值函数和策略函数后作者提出使用MCTS来进行改进也就是在每个时刻 根据值函数 和策略函数 进行MCTS搜索得到更好的策略 。因为MCTS探索整体的排序空间所以 比上式得到的 会选择更好的动作。具体算法为在Selection阶段( line 3 - line 7)每次搜索都从根节点 开始选择最大化upper confidence bound的文档。注意这个根节点并不是树的根节点而是 时刻的状态。最大化upper confidence bound的标准为 由 的定义可以看出 是动作值函数可以看做选择某个动作的回报考虑的是“利用”而 更倾向于“探索”也就是更喜欢访问次数少的节点 是平衡因子 定义为 是策略函数 的预测概率 是节点的被访问次数。上式是PUCT算法的一个变体。在Evaluation and expansion阶段( line8 - line 19)当到达一个叶节点 时如果是episode的结尾那么可以用已有的评价指标进行评估比如 否则可以用值函数来评估 。如果 可以展开那么对每个动作构建新的节点并且初始化也就是 line 11- line 16。在Back-propagation and update( line 20 - line 28)中我们更新 和 本质上 是每次从状态 选择动作 的对应的值函数的相加再求平均也就是 ,文中的公式是增量更新的形式。在Algorithm 1的 line 29 - line 32根据已有的 来计算 3.3 利用强化学习训练网络有了更好的策略 后在每个时刻 都使用 进行文档选择。当候选集合为空或者已经满足挑选文档个数时不再进行文档的排序此时利用已有的文档排序可以和真实的文档计算评价指标用 表示。所有时刻的状态和MCTS的策略组成 我们要优化的目标为 第一项为平方误差希望值函数在每个状态的值都和 接近而第二项是为了让LSTM输出的策略与MCTS得到的策略更接近。loss function形象化表示如下图整体算法如下可以看出针对每个query在每个时刻选择文档时利用MCTS来进行选择。当结束排序后根据排序结果以及每个时刻的策略 和 进行模型的更新最终得到一个训练好的LSTM模型。3.4 Online rankingMCTS是比较耗时的在线上进行排序的时候可能会对服务有不小的压力。作者提出了Online ranking的方法就是在排序时不再进行MCTS直接用LSTM输出的策略。作者用实验验证了不使用MCTS的时候模型仍然会高于baseline。这得益于训练时MCTS的贡献MCTS使模型能够输出更精确的策略。3.4 与AlphaGo Zero的不同虽然受到了AlphaGo Zeor的启发但 与之还是有不同的。作者总结了三点第一使任务的形式化不同。围棋是两人进行博弈状态是棋盘以及落子位置而多样性排序只需要每次挑选一个文档。第二是监督信息不同在围棋中监督信息是最后的输赢而在多样性排序中监督信息是各种多样性的评价指标。第三是网络模型不同AlphaGo Zero使用了残差网络而排序使用了LSTM这也是由于任务不同而有不同的选择。4. Experiment作者与其他算法进行了对比实验结果如下可以看出在测试阶段使用MCTS的效果最好。除此之外作者还对比了在没有MCTS的排序中使用策略还是使用值函数随着训练迭代的增多使用策略效果会更好一个可能的原因是 的优化相对困难尤其是在训练的初期。5. 结束语这篇文章利用强化学习来进行多样性排序与已有方法相比效果由明显的提升。用AlphaGo算法的整体框架来解决序列排序问题确实也比较自然尤其是文档之间还会互相的影响。这种方法也可以应用到其他序列生成的任务中最直接的比如导航时路线生成理想状况下是可以根据路况来选择道路的。强化学习应用很广期待能在更多的场景下发挥作用。原文https://zhuanlan.zhihu.com/p/56053546
