论文阅读笔记—Reasoning on Knowledge Graphs with Debate Dynamics（AAAI，2020）

这篇论文提出了一种基于博弈论的知识图谱推理模型，在知识图谱推理中引入了两个agent和一个judge模块。两个agent分别通过生成支持和反对证据链证明查询三元组的真伪，而judge则整合所有证据链给出最终结果。每个agent使用LSTM网络对历史路径进行编码，并通过策略采样生成证据链。Judge部分采用二分类器对证据链进行预测评分，并通过强化学习最大化累积奖赏对agent进行训练。该模型通过交替训练agent或judge的方式实现整体优化，并应用于知识图谱推理任务中。

这篇工作给人留下了深刻的印象，在阅读后令人耳目一新。

动机

在机器学习领域中，许多具体任务通常涉及通过将节点及其关联信息进行嵌入表示，并计算每个三元组的置信度得分来推导出最终的嵌入向量。然而，在这一过程中究竟哪些因素对最终的得分产生决定性影响尚不明确。本文所提出的模型包含三个核心模块：两个智能体和一个judge系统。对于任意待查询的三元组q=(s_q, p_q, o_q)，其中s_q、p_q和o_q分别代表查询中的实体、关系以及目标实体，在这里我们设计了一个基于知识库搜索路径验证该三元组是否成立的过程，并由judge系统综合评估结果。（虽然这一流程看似类似于生成对抗网络（GAN）的工作原理，但深入分析后会发现其内部机制的具体作用部分并非完全相同）

Agent模块

定义状态States： 记e_t^{(i)}为第i个agent在t时刻查询的位置，则目前的状态可记为：S_{t}^{(i)}=\left(e_{t}^{(i)}, q\right) \in \mathcal{S} = \mathcal{E}^{2} \times \mathcal{R} \times \mathcal{E}
定义行动Actions：从状态S_{t}^{(i)}=\left(e_{t}^{(i)}, q\right)出发，所有可能到达的节点集合（即e_t^{(i)}的邻居集），记做\mathcal{A}_{S_{t}^{(i)}}：
\mathcal{A}_{S_{t}^{(i)}}=\left\{(r, e) \in \mathcal{R} \times \mathcal{E}: S_{t}^{(i)}=\left(e_{t}^{(i)}, q\right) \wedge\left(e_{t}^{(i)}, r, e\right) \in \mathcal{K} \mathcal{G}\right\}
定义转移过程：若在状态S_{t}^{(i)}=\left(e_{t}^{(i)}, q\right)时选择行动A_{t}^{(i)}=\left(r, e_{t+1}^{(i)}\right),则转移过程为：
\delta_{t}^{(i)}\left(S_{t}^{(i)}, A_{t}^{(i)}\right):=\left(e_{t+1}^{(i)}, q\right)
将采取过的行动合并在一起得到历史路径：H_{t}^{(i)}=\left(H_{t-1}^{(i)}, A_{t-1}^{(i)}\right)，其中H_{0}^{(i)}=\left(s_{q}, p_{q}, o_{q}\right)

通过LSTM网络对上一时刻的信息进行编码：\boldsymbol{h}_{t}^{(i)}=\mathrm{LSTM}^{(i)}\left(\left[\boldsymbol{a}_{t-1}^{(i)}, \boldsymbol{q}^{(i)}\right]\right)
其中\boldsymbol{a}_{t-1}^{(i)}=\left[\boldsymbol{r}_{t-1}^{(i)}, \boldsymbol{e}_{t}^{(i)}\right] \in \mathbb{R}^{2 d}, \boldsymbol{q}^{(i)}=\left[\boldsymbol{e}_{s}^{(i)}, \boldsymbol{r}_{p}^{(i)}, \boldsymbol{o}_{}{(iii)}}{}\right]{}^{}\in{\mathbb R^{{3d}}}, 这里表明该LSTM模型的输入由五个长度为d的向量构成。值得注意的是，在本模型中，默认情况下两个参与者（agent和judge）所使用的嵌入向量是不同的

根据上一步编码的信息和这一步待选的行动空间计算每个行动的分数作为新选择策略：通过计算每个行动的分数来确定新的选择策略，在马尔科夫决策过程中仅考虑当前状态与下一状态之间的关系以实现最优决策目标：每个智能体在特定步数内生成一系列可能的行为序列，在此过程中动态调整行为选择的概率分布：每个智能体在特定步数内生成一系列可能的行为序列，在此过程中动态调整行为选择的概率分布：每个智能体在特定步数内生成一系列可能的行为序列，在此过程中动态调整行为选择的概率分布

其中策略\boldsymbol{d}_{t}^{(i)}中各个分量代表从动作空间中选取不同动作的概率值，在基于此概率分布进行动作采样时能够实现最优决策目标：其中策略\boldsymbol{d}_{t}^{(i)}中各个分量代表从动作空间中选取不同动作的概率值，在基于此概率分布进行动作采样时能够实现最优决策目标：其中策略\boldsymbol{d}_{t}^{(i)}中各个分量代表从动作空间中选取不同动作的概率值，在基于此概率分布进行动作采样时能够实现最优决策目标

Judge

Judge 实际上是一个二分类器系统，在该系统中将两个参与方 agent 所获取的证据链进行整合处理以得出最终的信任概率值：
\boldsymbol{y}_{n}^{(i)}=f\left(\left[\boldsymbol{\tau}_{n}^{(i)}, \boldsymbol{q}^{J}\right]\right)
其中 \boldsymbol{q^J} 表示在 Judge 系统中查询 q 所得的嵌入向量：\boldsymbol{q}^{J}=\left[\boldsymbol{r}_{p}^{J}, \boldsymbol{e}_{o}^{J}\right] \in \mathbb{R}^{2 d}。
随后计算最终分数：
t_{\tau}=\sigma\left(\boldsymbol{w}^{\top} \operatorname{ReLU}\left(\boldsymbol{W} \sum_{i=1}^{2} \sum_{n=1}^{N} \boldsymbol{y}_{n}^{(i)}\right)\right)
针对该模块设计的目标函数为：
\mathcal{L}_{q}=\phi(q) \log t_{\tau}+(1-\phi(q))\left(1-\log t_{\tau}\right)

Reward

为了展示两个agent的工作特性差异，在计算过程中分别对每个agent获得的证据进行得分为：

t_{n}^{(i)}=\boldsymbol{w}^{\top} \operatorname{ReL} \mathrm{U}\left(\boldsymbol{W} f\left(\left[\boldsymbol{\tau}_{n}^{(i)}, \boldsymbol{q}^{J}\right]\right)\right)

定义奖励函数：

R_{n}^{(i)}=\left\{ \begin{array}{ll} t_{n}^{(i)} & \text{当 } i=1\\ -t_{n}^{(i)} & \text{当 } i=2 \end{array} \right.

各agent的累计奖励值为：

G^{(i)}:=\sum_{n=1}^{N} R_{n}^{(i)}

基于强化学习框架下的优化目标是对agent进行系统性训练以最大化预期累积奖励：\underset{\theta(i)}{\arg \max } \mathbb{E}_{q \sim \mathcal{K} \mathcal{G}_{+}} \mathbb{E}_{\tau_{1}^{(i)}, \tau_{2}^{(i)}, ..., \tau_{N}^{(i)}\sim\pi_{\theta(i)}}[G^{(i)}|q]

该模型采用了交替训练策略，在每次迭代中仅更新agent或judge模块，并固定另一个模块的所有参数。

我叫码春儿，在 GitHub 上开设个人公众号「码春的学习笔记」 ，诚挚邀请关注者一起探索编程世界中的奥秘和技术之美！