图神经网络实现结构化对话策略
论文原文链接：Structured Dialogue Policy with Graph Neural Networks
关于“论文”这个类别
我打算在这个类别放一些自己看过的论文的笔记（以及一些理解和延伸），以免时间长了忘记论文内容。记录内容会随个人需要有一定选择性，而不是全文做翻译。可能会使用一些论文中的插图，出处不注明的话默认为原文。
带有我个人推断的，非常主观性的内容，我会用删除线标识一下。
引言
这篇文章是所在实验室之前的成果，由于结果很有意义，之后可能要借鉴其思路所以提前拜读一下。该文主要讲解了对话策略中如何使用图结构重新组织决策的一种实现方式，使得学习（采样）过程更为高效，最后也取得显著超越基准（Pydial benchmark）的结果。
相关工作
为了进行高效的对话策略学习，之前比较好的方法是GPRL（Gaussian process reinforcement learning）用的是核方法那一套；最近DRL（deep reinforcement learning）比较火，包括使用值函数（value function）的DQN以及PG（policy gradient）的那套REINFORCE、A2C等等。但是这些DRL的方法和GPRL比，通病是采样不高效（not sample-efficient）不过没办法嘛，模型大了是会这样，所以相应的改进方法，比如eNAC啊BBQ啊也就应运而生。
然后18年早些时候陈露学长（也就是论文作者）先做了一个MADP，思路基本上是把本文里的图中节点看成sub-agent，所以本文可以看成那篇的一个推广。
把GNN用到对话领域这也不是第一次，其实之前对话状态追踪（DST）已经引入过类似技术了（BUDS等等），但是对话策略这边该论文claim是第一篇。
核心框架
这里我不严格按照原文的顺序说明了。
首先还是依照POMDP的大框架，整个系统输入是belief state，输出是一个具体的summary action。
整个的过程是：
belief state -> [输入模块] -> [通信模块] -> [输出模块] -> action对应的Q-value
输入模块
结构化一个比较基本的好处是可以把槽上的动作和槽的belief state之间建立比较直接的联系。我们新建两个名词S-node和I-node，每个S-node（slot-dependent node）对应一个可通知的（informable）槽，而唯一的一个I-node（slot-independent node）负责所有与槽信息（belief state对应的输入）无关的方面，各自负责对应的动作估值。
输入的原本是belief state，其实就是每个slot里都有一些候选的value（按概率），我们可以通过一种叫sorted K-max pooling的黑科技把他们都对齐成前K大概率的，这样的好处是，如果每个slot的输入规模都一样（对于S-node来说），那我们就可以参数共享啦（加速训练）。
输入模块最后会把按slot切块后的belief state放到对应的S-node里面，每个S-node输出一个状态向量。
通信模块
我们的S-node和I-node之间要建图（GNN引入），至于按什么结构建图呢？暂时先来个全连接好了，后面“关于图结构”的部分会详细讨论这个图。
通信分为三个步骤：
发消息 -> 合并收到的消息 -> 更新状态
整个流程会重复L次，使得沟通能够较为完全的进行。
- 发消息
我们假设每条边对应一个函数，函数的输入是一个状态向量，输出是一个消息。发消息阶段，我们会对每条边进行一次运算来生成消息。
【作为示例】我们可以假设这个函数只是一个变换矩阵W
- 合并收到的消息
每个点对应一个的函数，输入是所有出边是本节点的消息们，输出是一个合并好的消息。
【作为示例】提出两种合并方式，一种是直接取平均，另一种是像翻译任务中一样用Attention来合并。
- 更新状态
每个点对应一个的函数，输入是原来的状态向量以及合并好的消息，输出是一个新的状态。
【作为示例】先对原来的状态乘个变换矩阵，再和合并好的消息加一下，最后用个RELU之类的激活一下。
输出模块
每个槽分别把重复L次生成的最终状态，通过各自的函数映射成一个动作对应的Q值。
注意，虽然在输入模块我们进行了参数共享，但为了拟合各种槽的特殊性，在输出时我们不进行参数共享。
【作为示例】这个函数可以是一个多层感知机（MLP）
关于图结构
之前我们假定图是全连接的，但其实也可以不是全连接。
我们也可以通过引入对邻接矩阵（adjacency matrix）的优化来改变整个图的结构。通过一些采样以及梯度相关的方法，我们也可以在训练过程中改变图中的边权（从而在通信模块消息传递时直接给出一定的权重）。
具体的实现方式与推导原文中有详细叙述，此处略过。
实验结果
主要跑了四种结构化基于DRL的对话策略：
| 策略名称 | 使用全连接图 | 使用带优化的图结构（高级） |
|---|---|---|
| 使用基于平均的输入 | GNN-M | GNN-M-C |
| 使用基于注意力的输入（高级） | GNN-A | GNN-A-C |
分别在训练1000轮和训练4000轮的时候看结果（对话成功率、平均reward），具体结果参见原文第8页大表格。
总结一下的话：
- 带Attention的训练快（1000轮的时候表现好一些）
- 充足训练后，四种变体的效果都差不多，但是基本上吊打benchmark（尤其是LAP这个笔记本的复杂任务上）
效果不错，可喜可贺。
结语
原文最后还给出了一些对于通信内容的假设解释，比较有趣。
总得来说，只是使用全连接+平均来按照该文的核心框架改进策略，效果就已经很好了，有机会可以试一试。