Title
《Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases》
Abstract
现在对KBQA的研究都是假设在问题上的训练分布和测试分布是相同的（i.i.d)。但是在大规模数据集上很难实现：
- 真实的用户分布何难捕捉（覆盖面很大，组合也很多）
[^]: 即使迭代注释了所有的用户问题，没有泛化能力的模型在面对新的out-of distribution questions时依然会失败
- 从大空间中随机抽样训练样本效率低下
所以我们建立三个层次的内置泛化：i.i.d,compositional,zero-shot,为了增大泛化能力提出了GRAILQA数据集以及基于BERT的KBQA模型
[^i.i.d]: indenpendently and identically distributed独立同分布（有相同的概率分布且相互独立。
Introduction
As the scale and coverage of KBs increase,KBQA is becoming even more important due to the increasing difficulty of writing structured queries like SPARQL
随着KB规模和覆盖范围的增大，编写像SPARQL这样的结构化查询语句变得很难，所以KBQA越来越重要 。
KBQA模型有三个层次的泛化：i.i.d,compositional,zero-shot,所以KBQA可以在可见的模式项(relations,classes,function)中进行重新组合,能回答所有涉及模式项的问题，即使在训练中不包含这种特定组合。KBQA在遇到训练中完全没有的关于整个模式甚至整个作用域的问题时，需要在zero-shot进行泛化
一个理想的数据集应该是大规模，多样化，可以为KBQA捕捉其他的实际挑战，比如实体链接，复杂问题以及语言变异，但是现在的KBQA数据库通常被限制在1 or more维。大多数专注于i.i.d的设置，GRAPHQ,QALD可用来测试成分泛化但却不能测试zero-shot泛化,它们的规模都相对较小，对KB本体只有有限的覆盖。SIMPLEQ虽然规模很大，但是仅仅限于有限多样性的单关系问题。
[^language viriation]: 语言变异是指某一个语言现象在实际使用中的话语中的变化。语言现象可以是语音、音位、词汇、语义项目或语法范畴等。例如第二人称单数，在普通话里有“你”（ni）和“您”（nin）两种形式，这两种不同的变化，就是第二人称单数的变异。 –摘自《什么是社会语言学》游汝杰著，上海外语教育出版社，39页
GRAILQA支持三种层次的泛化，64331个中包括>=4个关系（counting,comparatives,superlatives)的众包问题,数据库覆盖了FREEBASE COMMONS的86个领域，我们数据集中的问题涉及的实体是从美国到酒店名的所有受欢迎的实体。
为了增加多样性和真实性，通过大规模的web mining和众包来收集实体的常见表现形式。
*”Obama”,”President Obama”for *Barack_Obama
还提出了一种基于BERT的新KBQA模型，数据库和模型的结合让我们能够测试KBQA的几种挑战search space pruning and language,ontology alignment。BERT在实现组合和零射泛化上有很大的作用。
BACKGROUND
a)从给定的KB到具体的复杂性生成典型的逻辑结构
b)专家为了典型逻辑形式注释权威问题，实体和文字包含在括号里以便简单替换
c)通过众包获取高质量以及有差异的注释
d)从每个由entity grounding构成的逻辑形式生成不同的逻辑形式(?)
e)采样不同的逻辑形式和注释的组合去生成最终的问题，还可以通过网络挖掘常见的实体表现形式，使用它们使得实体连接更加有真实性
2.1KB
KB包含两部分：
- ontology:O ⊆ C × R × C
- relational fact:M ⊆ E × R × (C ∪ E ∪ L)
[^C:class R:binary relation E:entity L:litral]:
2.2Three Levels of Generalization:Definition
3 Data
3.1Data collection
3步
1) generate logical forms from a KB
2) convert logical forms into canonical questions
3) paraphrase canonical questions into more natural forms via crowdsourcing
Canonical logical form generation
首先遍历KB本体生成仅包含class，relation,function的图形形状的模板，接着落地到兼容实体的节点上，去生成表示含义的逻辑形式，样板和实体生成了canonical logical form。
Canonical question annotation
Crowd-powered paraphrasing
Grouding and sampling
标准逻辑形式和兼容的实体生成更多的逻辑形式。同一标准逻辑形式相关的逻辑形式和注释会形成一个pool，每次从每个pool中采样生成一个问题。开始时权值统一，选择logical form or paraphrase时同时除 ρ1，ρp。ρ1 to 2，ρp to 10（diversity），最后随机替换entity form(task3).
3.2 Data Analyse
Entity linking
表面形式的基本类型有首字母缩写，姓/名，常识，口语vs书面语，这样挖掘的表面形式用更有代表性，口语化的方法表示KB中的实体，在现有的KBQA数据库中被忽略。
3.3Logical Form in S-expression
graph query to S-expression
更有可读性
4 MODEL
比较和zero-shot泛化相比于i.i.d有两个挑战：大搜索空间，语言-本体对齐。
search space:
i.i.d:ontology observed during training(词汇表主要来自训练数据)
zero-shot:entire ontology(Qusetion-specific search space pruning)
language-ontology alignment:
zero-shot:学习unseen-schema item为了解决可能出现的相关问题
组合泛化：生成新的组合而非在训练中记忆的，传统方法是利用数据挖掘建立自然语言到KB语义项的词典，可能会更偏向受欢迎的语义项
预训练的文本嵌入（BERT）为对齐提供可选择的方案，基于BERT的KBQA模型让我们能测量在非i.i.d泛化中文本嵌入的有效性。
4.1 Model Overview
目标是生成map:input question q=x1,x2,…,x|q| to logical form a=y1,y2,..ya
基于Seq2Seq2，输出token是在输入的条件下自回归生成的，V是解码词汇表。条件概率定义为：
编码和解码器是两个不同的有LSTM的RNN，LSTM根据下面的公式生成token
$$
h𝑡 = 𝐿𝑆𝑇𝑀(h𝑡-1, g𝑡),
$$
基于当前的ht和W计算的每个输出token的概率
$$
𝑝(𝑦𝑡 |𝑦<𝑡
, 𝑞) = [𝑆𝑜 𝑓 𝑡𝑚𝑎𝑥 (Wh𝑡)]𝑦𝑡 .
$$
我们使用Seq2seq中的W连接输入输出，从预训练的嵌入中分配语义，促进开放的词汇学习
4.2BERT Encoding
之前用文本表示学习text-to-SQL的对齐时，将question和所有vocabulary item连接起来作为BERT的输入，但是KBQA中的词汇太多了，超过的BERT的输入长度，vocabulary分成chunk，将chunk和question连接后进行处理。
Vocabulary construction
在处理zero-shot泛化时，可以将来自KB本体的所有模式项都包括进来。但是搜索空间太大并且很耗时.为了减少size of V，利用从question中识别的实体作为在KB中的anchor，并且仅选择距离（>=1个）anchor两跳之内的KB items。（Vocabulary pruning）我们对每个输入都有一个动态V，所有在S-expression中的被识别实体，函数以及语法常量也包含在其中，同理求出基于BERT的实体表示，表示与它的表面形式相关。
5.Experiment
正确率 = 提取出的正确信息条数 / 提取出的信息条数
召回率 = 提取出的正确信息条数 / 样本中的信息条数
F-Measure（综合评价指标，α=1时即为F-1）：
Reference
https://baike.baidu.com/item/%E8%87%AA%E5%9B%9E%E5%BD%92%E6%A8%A1%E5%9E%8B/1037587?fr=aladdin
