论文阅读 (77)：Abductive Learning with Ground Knowledge Base

1 概述

1.1 题目

2021：基础知识库反译学习 (Abductive learning with ground knowledge base)

1.2 摘要

反译学习 (Abductive learning) 利用一阶逻辑推理结合机器学习，其允许机器学习模型利用由一阶逻辑规则表示的复杂符号领域知识。然而在许多应用中，将真实领域知识明确地获取或表达为一阶逻辑规则是具有挑战性的。唯一可访问的知识库由基础事实 (Groundings) 隐含表示，即没有变量的命题或原子公式。

本文提出基础反译学习 (Grounded abductive learning, GABL) 以在基础领域知识库中通过反译推理增强机器学习模型，其通过一组逻辑命题提供不精确的监督。GABL被应用在两个弱监督领域，结果表明模型的初始准确率在学习中扮演至关重要的角色。光学字符识别 (Optical character recognition, OCR) 任务的结果表明GABL可以显著减少数据标记的工作量。

1.3 代码

Torch： (https://github.com/AbductiveLearning/GABL)

1.4 引用

@inproceedings{Cai:2021:18151821,
author		=	{Le-Wen Cai and Wang-Zhou Dai and Yu-Xuan Huang and Yu-Feng Li and Stephen H Muggleton and Yuan Jiang},
title		=	{Abductive learning with ground knowledge base},
booktitle	=	{{IJCAI}},
pages		=	{1815--1821},
year		=	{2021}
}
1
2
3
4
5
6
7

2 基础反译学习 (Grounded abductive learning)

本节介绍问题设置和说明GABL方法。

2.1 问题设置

本文的主要目标是利用1）一组未标记的实例；以及2）限制模型输出空间的基础知识库 (Ground knowledge base, GKB) 来改进预训练模型。换言之，有标记训练数据是不可用的。

令 D = { x 1 , … , x m } \mathcal{D}=\{\boldsymbol{x}_1,\dots,\boldsymbol{x}_m\} D={x1​,…,xm​}表示未标记数据的集合，$GKB$表示基础知识库。每一个${\mathbf{x}}_i\in \mathcal{X}$对应一个未知标签${\mathbf{y}}_i\in \mathcal{Y}$，其中$\mathcal{X}$是特征空间，$\mathcal{Y}$是标签空间，以及$GKB\subseteq \mathcal{Y}$。本文考虑分类问题，因此$\mathcal{Y}$是离散或者符号化的，即每个点${\mathbf{y}}_i$可以看作是Herbrand universe中的基础原子或者一个命题。例如，如图1所示的OCR任务中，$\mathbf{x}$是一张包含手写单词的图像，$\mathbf{y}$是由26个英文字符组成的字符串。理论上$\mathcal{Y}$是无限大的，因为有无数个可能的字符串。$GKB$是一个基础原子的集合，例举了所有合法的$y$，即英语中正确拼写的字典。因此，对于每一个${\mathbf{x}}_i\in \mathcal{D}$，有${\mathbf{y}}_i\in GKB\subseteq \mathcal{Y}$。从一阶逻辑的角度，GKB是未知一阶逻辑理论的答复集 (Answer set)。

令$M:\mathcal{X}\mapsto \mathcal{Y}$表示要改进的预训练机器学习模型。给定输入${\mathbf{x}}_i$，模型将输出预测${\hat{\mathbf{y}}}_i=M({\mathbf{x}}_i)$。

图1：OCR字典示意

2.2 反译学习 (Abductive learning, ABL)

在ABL中，机器学习可以将原始数据转换为原始逻辑事实 (Primitive logic facts)，其可以看作是用于逻辑推理的伪标签$\hat{\mathbf{y}}$。同时，反译可以根据一阶逻辑规则选择性地推断出特定的预测事实。推断的事实被认为是反译标签 (Abduced-labels) $\overline{\mathbf{y}}$，将被用作训练机器学习模型的真实标签。

反译是逻辑推理的一种基本形式，用于基于隐含知识 (Implication) 寻找观察结果的最佳解释。例如公式"$wet\_ground\leftarrow rain$" (雨导致地湿)，即当我们观察到地面潮湿时，可以猜测下雨了。

挑战：GABL的挑战是在只依赖基础知识库而非任何一阶推理规则下实现反译。基础事实库仅提供例如$\text{valid\_word}(\text{Y})$这样的判断，以确定$\text{Y}$是否属于知识库。然而，反译是需要一些一阶逻辑规则的。因此只有知识库是不肯恩那个实现反译的。

2.3 GABL的实现

为了在基础知识库上执行反译，提出了一个增强GKB，其包含一些一般假设构成的反译逻辑程序，其约束$\overline{\mathbf{y}}$的搜索—$M$预测的$\hat{y}$的修订后伪标签。

考虑到尝试将图像映射到字符串的OCR任务，假设每个标签${\mathbf{y}}_i$是一个序列$[y_{i,1},\dots ,y_{i,L_i}]$，其中$L_i$是序列长度，$y_{i,l}$是子标签。

对于该类问题，引入了一个一般反译程序，其使用GKB通过字符串距离，即编辑距离 (Edit distances) 来约束伪标签的搜索。该程序的一阶逻辑表示如下：
p r o g r a m ( y ^ , y ‾ , G K B ) ← b e t w e e n ( 1 , m , D ) ∧ d i s t a n c e ( y ^ , y ‾ , D ) ∧ y ‾ ∈ G K B ∧ c o n f i d e n c e ( y ‾ , C ) ∧ C ≥  threshold.  (1) \tag{1}

program(y^​,y​,GKB)​←between(1,m,D)∧distance(y^​,y​,D)∧y​∈GKB∧confidence(y​,C)∧C≥ threshold. ​(1)这里$m$约束了模型$M$的预测标签$\hat{\mathbf{y}}$与反译标签$\overline{\mathbf{y}}$之间的最大容忍距离 (Maximum allowed distance)；$threshold$用于排除低置信度的结果；$C$是$M$计算的$\overline{\mathbf{y}}$的置信度。根据该一阶逻辑规则，GABL能够自动找出$\overline{\mathbf{y}}$，其最接近$\hat{\mathbf{y}}$且有高置信度。当反译结束时，若存在多个解，GABL能够引用其他规律来指出最大置信度的那个。

事实上，$distance(\hat{\mathbf{y}},\overline{\mathbf{y}},D)$和$confidence(\overline{\mathbf{y}},C)$可以组合为模型预测结果与基础事实的相似程度。本文使用模型训练损失函数来表示相似性，因为该函数是针对学习任务精心设计的。换言之，当考虑反译中的置信度时，我们将直接根据损失函数来选择反译标签。反之将仅仅考虑距离来选择。

算法1描述了GABL算法。在每一个epoch中，GABL使用模型$M$来生成输入数据$\mathbf{x}$D 带置信度的标签$\hat{\mathbf{r}}$，然后基于公式1选择反译标签。当$\hat{\mathbf{y}}$存在时，GABL将其添加到$\overline{D}$中，并在当前epoch结束时用其来更新$M$。

3 综合研究

本节讨论为什么GABL可以通过权衡无标记数据和基础知识库来提升机器学习模型的性能。

3.1 GABL的机制

直观上，GABL与用于半监督学习的自学习方法类似。半监督学习是一种基于伪标签的方法，使用模型预测标签进行进一步的模型训练。此外，GABL能够排除非法伪标签并纠正不准确的伪子标签，这能够比自学习方法更有效地探索无标记数据。对于输入$\mathbf{x}$，当模型的预测标签$\hat{\mathbf{y}}$与基础知识库不一致时，反译需要修正$\hat{\mathbf{y}}$为$\overline{\mathbf{y}}$以符合基础知识库。反译需要假设只有一部分的预测标签是不正确的。伪标签$\hat{\mathbf{y}}$可能与属于$GKB$的相邻标签$\overline{\mathbf{y}}$失真。

图2展示了GABL的机制，$GKB$中的每个$\overline{\mathbf{y}}$在一些特殊的距离测量 (汉明距离或其他距离)下，像Vonoroi图一样覆盖了一部分空间。由于一些干扰，预测结果从点浮动到它们的邻域，例如，一个围绕它的球。球的半径取决于预训练模型的精度，高准确率将导向更小的半径。当干扰占据主动时，圆的半径将变大，导致更多的错误预测并可能损害模型性能。

  图2：反译中基于基础事实领域划分的标签空间$\mathcal{Y}$。红色点表示GKB中的基础事实。依据标签空间中的距离度量，空间被分为四个部分。预测结果，即黄色点将以更高的概率出现在蓝色圆。例如，标记为$\text{A}$的输入数据被预测为${\text{A}}^{\prime }$，依据反译方法可以重新标注${\text{A}}^{\prime }$为$\text{A}$，并微调模型。然而，当两个点在GKB中相近时，或者模型的预测误差很高时，反译结果可能是错误的。例如点$\text{C}$被预测为${\text{C}}^{\prime }$，但由于更接近$\text{D}$便被错误地反译为$\text{D}$

不确定性被用于解释以上现象。根据信息理论，基于伪标签的真实标签的不确定性可以分解为真实标签的熵和伪标签关于真实标签的互信息。当任务给定时，模型预测的不确定性依赖于模型的预测精度。因此，模型的预测精度在反译学习中扮演着关键角色。

此外，GBAL是一个multi-epoch方法。模型的性能将随着预测和反译的推进而强化。模型在每个epoch训练后的准确度取决于前一个epoch的准确度。可见，模型的初始精度至关重要。通过一些假设，发现在给定领域知识库时存在准确度阈值：

1. 首先假设经过训练，模型的泛化精度无限接近数据集的精度；
2. 其次假设模型的预测精度越高，反译结果的精度越高；
3. 再者假设所有类别的预测准确率几乎相同。

令${\hat{p}}_i^c$表示第$i$个epoch预测标签的准确率，${\overline{p}}_i^c$表示子标签的准确率。特别地，${\hat{p}}_0^c$表示由初始模型预测得到的子标签预测准确率，${\overline{p}}_0^c$则表示由初始模型得到的反译子标签预测准确率。这意味着如果${\hat{p}}_0^c<{\overline{p}}_0^c$，则${\hat{p}}_0^c<{\overline{p}}_0^c\approx {\hat{p}}_1^c<{\overline{p}}_1^c\cdots \approx {\hat{p}}_E^c<{\overline{p}}_E^c$。但如果${\hat{p}}_0^c>{\overline{p}}_0^c$，则${\hat{p}}_0^c>{\overline{p}}_0^c\approx {\hat{p}}_1^c>{\overline{p}}_1^c\cdots \approx {\hat{p}}_E^c>{\overline{p}}_E^c$。因此，这里由一个阈值$p_{t1}$，当${\hat{p}}_0^c>p_{t1}$时，GABL能够帮助模型提升性能。与此同时有另一个阈值$p_{t2}$，当${\hat{p}}_0^c<p_{t2}$时，GABL将损害模型性能。因此存在准确率阈值$p_{t1}$和$p_{t2}$，并记为$p_t$。

3.2 在合成数据上的实验

该实验用于核验是否存在一个初始的准确率阈值$p_t$，其能够基于公式1中的增强程序，以在反译学习中提升模型；同时探索能够影响准确率的阈值$p_t$。

3.2.1 准确率阈值是否存在

数据集：包含两个部分，一个由基础事实的集合构成的基础知识库$GKB$和一个无标签训练集 D u = { x 1 , x 2 , … , x n } \mathcal{D}_u=\{\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_n\} Du​={x1​,x2​,…,xn​}：

1. 基础事实通过包含$7$位hamming编码 (实验中表示为"hamming-*") 和$5$至$7$十进制加法方程 (“addition-*”) 的不同领域知识库生成；
2. 每个无标记数据${\mathbf{x}}_i$包含$L_{i}d$个特征，其中$L_i$表示标签${\mathbf{y}}_i=[y_{i,1},y_{i,2},y_{i,L_i}]\in GKB$的长度，$d$表示每个子标签的特征数，例如$[x_{i,(k-1)d+1},\dots ,x_{i,kd}]$是根据子标签$y_{i,k}$来自基础数据 (MNIST，CIFAR-10，或者如图5的合成数据集) 中的采样；
3. 加号和等号的图像被额外添加到MNIST图像和CIFAR-10图像中。

图5：合成数据的分布

 
实验设置：模仿NeSy和ABL模型的感知和推理管道，使用一个模型来预测子标签，然后将它们提供给GKB进行推理。特别地，如图3 (a)，模型$M$转换$[x_{i,(k-1)d+1},\dots ,x_{i,kd}]$为子标签$y_{i,k}$。理想情况下，最终结果${\hat{\mathbf{y}}}_i$，其包括$[{\hat{y}}_{i,1},{\hat{y}}_{i,2},\dots ,{\hat{y}}_{i,L}]$，是属于GKB的：

1. 基础模型是MNIST或者CIFAR-10，CNN被使用为$M$，实验结果被标记为"mnist"或者"cifar"；
2. 基础数据是合成数据，KNN或者决策树被使用，标记为"KNN"或者"DT"；
3. 模型的初始准确率通过噪声数据或者预训练数据的数量来控制；
4. 反译中考虑模型预测置信度与否均被测试；
5. 不考虑置信度时，GABL拒绝有多个解的样本；
6. KNN的$k=3$；
7. DT的最小节点数$=3$。

  图3：序列预测设置。当标签长度为$L$有以下两种设置：1) 共享分类模型；2）每个子标签都对应一个分类模型

实验结果：图6表明存在一个准确率阈值。实验基于不同的$GKB$在不同的初始准确率下进行。当模型的初始准确率足够高时，GABL通过无标记数据提升了模型性能。当利用置信度时，准确率阈值低于仅使用分类结果的。

  图6：模型训练准确率与初始准确率的关系。(a) 和 (b) 使用hamming编码作为$GKB$；© 和 (d)使用加法；(a) 和 © 使用分类结果；(b) 和 (d) 使用置信度。

3.2.2 领域知识如何影响阈值

数据集和设置：

1. 长度$L$的随机二进制固定长度编码作为$GKB$，$GKB$大小为$N$；
2. 基础数据采样自合成数据；
3. DT作为基础模型，节点数设置为$1$；
4. 反译仅使用分类结果；
5. 如图3 (b)，$L$固定后，使用$L$个分类器作为感知模型，即第$k$个分类器预测第$k$个子标签。这样可以避免一些特殊情况，例如当仅有一个模型用于预测所有子标签且 G K B = { ′ 10 1 ′ , ′ 10 0 ′ } GKB=\{'101','100'\} GKB={′101′,′100′}，训练过程是属于有监督的。

实验结果：图7展示了准确率阈值与实验参数$L$和$N$的关系。表明在相同的$N$下，不同的标签长度下有不同的阈值$p_t$。更长的$L$有更低的$p_t$。这类似于信息传输，其使用更长的编码来客服通道中的噪声问题。

图7：准确率阈值在参数设置下的变换。每个阈值展示的是10次实验的最大值

 
总结：

1. 模型的初始准确率大于$p_t$时，GABL能够提升模型性能；
2. $p_t$主要受$L$和$N$影响；
3. 稀疏空间在模型错误上有更高的容忍度且对任务的预训练模型精度要求较低。

4 OCR实验

本节描述GABL应用到手写光学字符识别 (OCR) 的实验，主要目的是验证GABL能否应用到带有噪声输入的现实应用上。

OCR是一个重要的应用，例如许多手写档案材料没有转录成文本。这对于业余者的阅读是很不友好的，不利于信息检索。因此，将这些手写文档转录成文本是有意义的。在实践中，存在两种手写识别任务，无词典和基于词典。基于词典的手写识别为模型推理提供了词典，这意味着它应该在词典中挑选单词。

数据集：使用IAM数据库作为测试基准。IAM数据库包含115,320个未预先分割的孤立单词级英文手写图像。图8显示了一个示例。此外，这是第一次将反译学习应用于具有未分段原始输入的任务：

1. 只保留长度大于3的词，因为短词太多，导致长尾问题，超出了本文的范围；
2. 将数据集分为标记数据、未标记数据，和实验中的测试数据。留下10%的数据进行测试，随机挑选出不同数量的数据作为标注数据；
3. 收集IAM数据库图像的所有标签作为基础知识库。

图8：OCR示意

 
实验设置：如图3 (a)，使用同样的模型预测每一个子标签：

1. CRNN作为基础模型，在预测时，CRNN贪婪选择每个未知具有最高概率的字母，然后合并重复字母；
2. Burkhard-Keller树 (BK-tree) 用于在$GKB$中选择相近候选，并使用编辑距离来度量BK-tree中候选者的相似性；
3. 通过排序CTC损失来选择伪标签；
4. 在半监督场景下测试，即使用有标签数据训练模型，然后结合于模型中结合有标签数据和反译数据；
5. 对比三种半监督方法，其均使用CRNN作为基准模型：a) ST：自训练方法；b) Tri：三重训练；以及c) VAT：虚拟对抗训练；
6. 在有监督下测试了CRNN的性能。

实验结果：使用模型在测试集上的最佳性能作为实验结果。因为比较方法的性能会随着训练epoch数量的增加而迅速恶化，很难通过训练epoch的数量来确定最优性能。如表1所示，GABL在OCR中取得了最佳性能。虽然这不是一个公平的比较，但GABL利用基础知识库来提高模型性能并减少标记数据的数量。

由于模型在反译过程中训练数据不足时会过度拟合，未标记数据不足可能会限制GABL的性能。在一个epoch内使用所有未标记的数据可能会使模型陷入局部最优。当在每个epoch中对一批数据进行二次采样以进行训练时，模型在OCR中取得了更好的性能。实验在单个V100S GPU上运行。GABL大约需要48小时来训练一个CRNN模型。在每个epoch中，GABL花费的时间是自训练时间的两倍。GABL比Tri-training快，比VAT慢。

表1：OCR准确率