Pet Projects


Abstract

一些业余时间玩具项目的笔记。


arXiv 论文搜索推荐系统 Sparx

项目地址：Sparx

一个基于 arXiv 论文数据库的 paper 搜索、推荐以及分享的系统。主要实现搜索（Title | Author | Tags | Abstarct）、推荐（根据用户的收藏）、显示热门 paper、基于 paper 的简单社交功能（添加好友 | 分享 paper | 留言）

  • 流程： 需求 -> 收集数据 -> 分析数据 -> 确定目标 -> 选择算法 -> 实现

  • 主要困难（TODO）

  • 使用 Reinforcement Learning 对搜索结果改进

    首先要进行预训练，通过监督学习得到一个“还过得去”的 policy（keywords->paper）其中 paper 使用 tfidf 向量表示，训练数据是用户的搜索记录和原生系统的结果（或者随机地自我搜索）。这一步实际上可以看作是用神经网络去拟合原生系统。

    得到初始 policy 后有两种思路（使用用户的点击反馈进行系统改进：

    1. 监督学习的思路：对于用户点击的某条结果，在之后训练 policy 时给予更大的权重
    2. R 的思路：在 RL 的 context 下，用户的 feature 和搜索关键字是 state，引擎的搜索结果是 action，用户点击与否是 reward。动作空间是连续的，可以采用 DDPG 模型，这样经过训练，RL 系统会慢慢返回 reward 比较大的结果。



Toy models

项目地址：Toy models

Slither

使用 RL 中的 DDPG 模型玩在线游戏。使用的是 python 的 selenium 库与浏览器进行模拟交互，捕捉屏幕截图，直接作为状态输入。

  • 主要困难：

    在线游戏，如果不进行一定的处理，每一步的状态转移概率随着网络速度和计算时间等因素的变化而变化，即环境的动态特性会一直变化，导致网络更难收敛。

  • 解决思路：

    固定每一步的时常为 0.1s（每步计算和更新的时间不能超过 0.1s，因此网络不能太大）

DQN 玩 Text-based Game

  • 思路：使用 DQN 玩基于文本的交互游戏，状态和动作空间都是文本。主要需要解决的问题是对状态和动作进行 embedding。 embedding 有两种方法：一是直接使用词袋 BOW 模型将文本转化为向量（忽略了词语顺序等关系）；二是通过一个 LSTM 生成一个 representation，LSTM 每个时刻生成一个向量，最后对所有向量进行 mean polling

  • 主要困难：

    每个状态面临的动作数不一样，即动作数是变化的。按照标准 DQN 的做法，需要事先知道最大的动作数。

  • 解决思路：

    采用两个分开的网络分别输入状态和动作，在两个网络最后一层的输出结合到一起输出一个 Q 值，结合可以直接使用内积或再用一层神经网络连接起来。

Master Tic-Tac-Toe using MCTS

  • 思路：实现了蒙提卡罗搜索树(MCTS)算法，编写了一个玩井字棋变种游戏的 AI。在每回合 30s 时间限制的情况下，性能超过一般人类玩家（我）。

  • 未来需要改进的：

    1. 训练一个值函数对搜索树进行深度方向上的剪枝，使之在一定的时间内能够搜索更多的可能性。
    2. 改进交互方式（HTML 方式交互）



DDPG

Repo：DDPG

  • 一句话总结

    DDPG 算法是 policy gradient 的一种特殊情况，适用于解决大（连续）动作空间的 RL 问题。本质上还是 Actor-Critic 网络，Actor 是决策网络，直接输出动作（概率分布或者连续动作），Critic 对状态动作对进行估值 Q(s, a)。

  • 核心思想

    DDPG 最核心的思想就是 Actor 网络的策略梯度等于 Q 值的对于 Actor 网络参数的梯度。（调节 Actor 网络参数以最大化 Q 值

  • 算法流程

    对一个 experience(s,a_,r,s') (其中 a_表示动作是加了随机噪声的）
  计算 a = P_u(s) ,  q = Q_w(s, a)  （u 和 w 分别为 P 网络和 Q 网络的参数）
  策略梯度 = Q 值梯度 = d_q / d_u = ( d_q / d_a ) * ( d_a / d_u)
  Critic 也是通过计算 target Q value 和实际 Q value 的 MSE 得到梯度。
  计算 a' = P' * u_'(s') , q' = Q' * w_'(s', a')
  使用 SARSA，critic_loss = (r + gamma * Q' * w_'(s', a') - Q_w(s, a))

使用 target network 使得 DDPG 成为一种完全 off-policy 算法。



A3C

Repo：DDPG

  • 一句话总结

    • A3C 是目前 DRL 领域 state-ofthe-art 的一种模型。本质是 Actor-Critic 算法，采用了异步训练的思想。
    • 维护一个全局网络，多个子线程同时与多个环境进行交互，得到多个梯度对全局网络进行异步更新。
    • 优点是多个 agent 在同一时刻处于不同的状态，打破了训练数据的相关性，无须使用 experience replay，可以直接进行在线学习 on-line learning。

  • Actor-Critic 思想

    Actor-Critic 是 value-based 和 policy-based 两类 RL 方法的结合。其中 Actor 是决策网络，直接输出动作（概率分布），Critic 网络对状态 s 进行估值 V(s)（使用 critic 辅助计算策略梯度

    • Actor 网络的训练是通过计算策略梯度，即 Advantage（discounted_rewards - values）乘上-log(p)对于参数的偏导。
    • Critic 网络的训练通过计算 target value 和输出 value 的之间的 MSE 得到梯度。其中 target value 的计算使用了 n-step 的思想，即 target_value V’(t)= r(t+1) + gamma * r(t+2) + gamma^2 * r(t+3) + … + gamma^k * V(t+k)

    A3C 是使 Adavantage = TD(lambda) - V 来作为 policy gradient therom 中 Q 的估计

  • REINFORCE 思想

    • 作为比较，REINFORCE 是纯 policy-based 的方法，可以看作只有 Actor 网络。训练是直接通过 discounted rewards 乘上 -log(p) 对参数的偏导得到策略梯度。缺点是 variance 很高。
    • REINFORCE 中是使用 discounted reward 作为 policy gradient therom 中 Q 的估计（Monte-Carlo 的思想，整个 episode 走完得到 discounted rewards）