Reading Wikipedia to Answer Open

1. 背景

在2017年，自然语言处理已经达到了一个相当高的水平，尤其是机器理解领域，有非常多优秀的新兴算法。不过在问答系统领域，当时大部分系统和研究都是基于KBS的，这样的系统有共同的缺点（不完整，固定的格式），其他的问答系统要么不支持公开编辑，要么不能进行多任务训练，要么是需要冗余信息。总之当时的问答系统的构建都不够简单有效，因此有很大的空间去进行实践与优化。而作者希望构建一个基于维基百科（集合了所有人知识的公开编辑知识库）这样单一数据源就可以使用的问答系统。

2. 作者的主要入手点

作者主要是通过机器理解的方式完成对问题答案的发现。大概就是通过LSTM对输入的问题q和段落中的单词p进行处理，得到的向量相乘作为“该单词和问题相互匹配” 的概率。当然作者也做了一些很trick的特征工程对模型进行完善。但是训练起来尚且能完成，但是实际应用的话，对500万个维基百科的词条逐一匹配就太慢了，为此作者设计了一个检索模块，来进行初筛。这个有点分阶段排序的意思，先初筛再精排，跟目前主流推荐系统的设计非常神似。

总结来说就是两部分工作完成QA系统的目标：

1. 检索模块：通过倒排索引+向量的方式检索到和问题相关的段落，辅助一些本地排序和二元语法哈希提升效果。

2. 理解模块：通过机器理解模型对检索到的可能相关的段落进行逐一匹配，最终给出答案。

3. 作者的实现手法

那么下面我们来详细解读作者的实现手法。

3.1 检索模块

作者声称，利用他的模块，无需机器学习，也无需对维基百科事先进行词条关系的梳理，可以直接得到比维基百科自带的搜索引擎更棒的效果。网上关于这篇论文的解读都重点在机器理解那部分上，我阅读思考了作者在检索部分的实现，为跟我一样的小白读者做一下科普吧，大神或者机器学习爱好者可以直接跳到3.2。

作者首先采用倒排索引+向量的方式，进行检索，发现效果基本满意。然后辅以bigram hash提高效率。这里先解释一下倒排索引。

1. 什么是数据库索引

众所周知，在数据库中，如果没有索引的话，只能遍历去查找，这样的效率非常低下，复杂度是O(n)。一般来说对于结构化的数据，我们都是根据业务情况，以某一个经常作为筛选条件的列建立索引，索引是某一列的值作为key，列所在的地址作为value，排序之后储存起来，因为索引的多叉树结构（一般是B+树，这是一个类似跳跃表和二叉树的结合体），可以将查找key的效率提高至O(log n)，然后再根据value去取那一列数据就可以了。在N非常大的时候，索引的效果是非常明显的。

不过索引的代价就是每插入删除一条数据，都需要对索引进行修改，这就对开发人员设计索引提出了一些技巧性的要求，不过因为数据库的主要场景还是查询，所以这个代价是完全可以接受的。

2. 什么是倒排索引

那么有了索引为什么还有倒排索引的概念？因为很多时候，我们需要根据文本内容去匹配记录，这样索引就失去了用武之地。因为无论对文本那一列按照什么样的规则排序，都无法保证可以找到里面的内容匹配。只能去一个一个的遍历记录，取出文本所在的列，然后进行正则匹配，这个效率就变成了O(n)·O(m1+m2) ，其中n为数据库(也就是词汇表)长度，m1为查询字符串长度，m2为数据库字符串平均长度，这个效率低的可怕。

所以为了解决这个问题，有人提出了一个新的思路，就是把文本那一列单独打散，先进行分词，然后以分词结果作为key，把该单词在哪些文章中出现过、文章的地址作为value，重新建索引。这样，要查找的东西可以直接跟分词之后的一个个单词进行匹配，这样我们就又有了索引可以用了。效率又回到了O(log n )。

3. 什么是bigram+hash索引

关于这个问题，作者的思路并不是直接存储向量，而是跟倒排索引一样存储单词。得到短语之后但是不太一样的地方是，他存储的不是单词，而是所谓的bigram，就是存储两个单词组成的bigram短句，然后查询时也是用两个单词组成的bigram去查询。

那么如何快速的匹配呢？直接用hash，两个单词经过murmur3（一种hash算法）之后得到一串字符串，把这个字符串做索引的key，其查找速度理论上跟Java中的HashMap是一样的---O(1)。但是代价就是需要额外的存储空间。单词对越长，组合越多，需要的额外空间就越大，bigram来说的话，其空间复杂度应该是O(n²)。作者说这是经过他的实验得到的结论，bigram是坠吼的。

这是利用hash进行筛选，可以找到和问题相关的文章，怎么利用向量进行比较呢？作者把问题和得到的文章变成的词袋模型向量，然后用tf-idf进行加权，然后用这两个向量比较和排序。这样就完成了整个检索，检索会将top5的文章返回，作为下一个模块的待选文本。

4. 我自己的思考

如果在倒排索引的基础上再前进一步，在进行关键词的匹配时，不是死板的用问题中的单词逐一匹配数据库中倒排索引key的单词，而是把问题中的单词转化为glove词向量，数据库中倒排索引key的单词也转化为glove词向量，用词向量的距离判定是否匹配，这样就不单可以匹配到完全匹配的词，还可以匹配到近义词。这样不就可以得到比传统的倒排索引更棒的效果（因为利用词向量考虑近义词嘛）吗？

不过这样如果为了找近义词，不就不得不遍历所有单词了嘛，这样不是又回到了O (N )的时间复杂度了吗？如何存储向量，如何在大数据下对向量进行匹配，这部分我还没仔细研究过，听说有个kd-tree的数据结构，配合一个近似算法可以解决这个问题。

3.2 机器理解模块

1. 段落单词的编码

段落单词的处理可以分成四个部分，两 个步骤。如下图所示：

image.png 第一步是构造LSTM的输入 image.png

，包括四个部分：

A. 段落单词是否是问题的关键词
是就标记为1，否则标记为0
B. 段落单词本身的glove向量
用一个300维的向量来表示
C. 段落单词和问题单词的距离a_i,j（距离计算采用glove向量进行），具体的计算公式如下：

image.png
D. 单词本身的统计特征，包括词性、实体词识别、词频
image.png

第二步是进入LSTM训练并得到输出p_i。

2. 整个问题句子的编码

也是要把所有单词用glove表示出来之后进入另一个lstm得到q_j，然后把所有的q_j加权计算问题句子的编码：

image.png

注意这个权重w是需要训练的。

3. 构造训练样本（预测）

把p_{start i}作为开始单词，p_{end i}作为结束单词，概率表示如下：

image.png

然后把下式作为目标函数求解即可：

image.png

这种标记段落起终点的做法，在NLP领域还是蛮常见的，好像叫指针什么鬼，是一种常用的技巧。

4. 实验与结论

image.png

跟之前的一些不太给力的模型相比，效果挺好

image.png

但是跟yodaQA相比就不行，不过好在这个模型比YodaQA简单多了

image.png

做了下特征分析，可见手动添加的特征很有用

5. 总结

1. 这一套模型的思路可以说是对当时问答系统的改进，不但模型简单效果不错，而且可以完成多任务的学习。

2. 看完论文之后我就感觉这破模型真的能做QA吗？这个模型为啥能做啊？可能是我在LSTM方面的知识太少，不能理解LSTM部分的含义吧。

3. 谁说深度学习不能有人工特征？作者不就加了好几个么。特征工程任何时候都是人脑对机器学习模型能力的补充。