Q&A System Introduction (问答系统介绍)

Q：能否根据语料库搭建一个智能客服系统（问答系统）？

基于搜索的问答系统

基于搜索的问答系统的解决思路：根据用户输入问题，从语料库中找到相似度最高的问题，返回相对应的答案作为回答。

简单流程：

基于搜索的问答系统 vs 基于知识图谱的问答系统

基于搜索的问答系统的关键点：

• 文本的表示
• 相似度计算

基于知识图谱的问答系统的关键点：

• 实体抽取
• 关系抽取

两者的关键点不同。

Pipeline (流程)

NLP下项目的常规流程如下：

说明：标准化的意思是把多个不同形式表示的相同单词，改成用同一个单词进行表示，比如go/went/going统一用go进行表示。

Word Segmentation (分词)

Word Segmentation Tools

常用分词工具：

• Jieba分词 https://github.com/fxsjy/jieba

• SnowNLP https://github.com/isnowfy/snownlp

• LTP http://www.ltp-cloud.com/

• HanNLP https://github.com/hankcs/HanLP/

中文最常用分词工具为jieba分词。

Segmentation Method

最常用的分词方法主要有两个：

1. Max Matching(最⼤匹配)
2. Incorporate Semantic (考虑语义)

Segmentation Method 1: Max Matching (最⼤匹配)

最大匹配又可以分为：

• 前向最⼤匹配
• 后向最⼤匹配

说明：最大匹配算法一定要设置最大长度，最大长度可以通过统计单词长度的分布情况，得出一个最合适的值，中文大概是5-10，比如max-length=5。

接下来以下面的例子为例，讲解最大匹配的分词方法。

说明：分词一定是需要词典的，否则无法判断分割出来的单词是否合理。

前向最⼤匹配（forward-max matching）/ 后向最⼤匹配（backward-max matching）

前后向最大匹配原理相同，只是匹配顺序相反而已。

最⼤匹配的缺点？

• 无法考虑语义，上下文
• 局部最优，有时候继续细分才是更好的结果
• 效率不高，取决于最大长度的设置

Segmentation Method 2: Incorporate Semantic (考虑语义)

接下来以下面的例子为例，讲解考虑语义的分词方法。

考虑语义的分词方法，首先需要假设我们拥有一个工具：

graph LR A[分词结果] --> B(工具/语言模型) B --> C[概率值]

假如我们拥有这么一个工具，那么分词流程就变成了：

graph LR A[输入] --> B(生成所有可能的分割) B --> C[选择其中最好的/概率最大的]

上述方法的缺点？

在“生成所有可能的分割”步骤中，假如句子太长，那么就会生成非常多的组合，导致在计算每个组合的概率的时间复杂度太高。

怎么解决效率问题？

采用维特比算法（Viterbi algorithm），将“生成所有可能分割”和“计算概率”两个步骤合二为一。

我们要分析的例子如下：

说明：对于没在词库中出现的单词，我们初始化其概率为最小值，反之就是最大的\(-\log(x)\)，比如另\(-\log(x)=20\)。

为什么要采用\(-\log(x)\)的形式表达概率？

因为通常每个单词在语料库中出现的概率都是非常小的，所以在计算分词结果的概率时，连乘起来可能会得到一个非常小的接近于0的数值，有可能会出现精度问题，所以通过取对数进行放大。

又由于算法中通常求解最小值，所以在对数前面加上符号，更符合习惯。

我们可以根据例子中的信息，绘制如下的路径图：

说明：

• 单词上面对应的数字即为单词对应的概率\(-\log(x)\)。
• 图中每一条路径都对应着一种分词的结果。

这样，我们就把问题转化为求解最优路径，也就是找到概率最小的路径，可以通过动态规划的方法实现。

Word Segmentation Summary

知识点总结：

• 基于匹配规则的⽅法
• 基于概率统计⽅法（LM, HMM, CRF..)
• 分词可以认为是已经解决的问题

需要掌握什么？

• 可以⾃⾏实现基于最⼤匹配和Unigram LM的⽅法

Spell Correction (拼写纠错)

拼写错误有两种场景：

1. 错别字，即词典中不存在的单词。
2. 不是错别字，但是不符合当前上下文，即在LM（语言模型）中概率非常低。

接下来我们考虑如何实现拼写纠错。

Find the words with smallest edit distance

把一个单词编辑成另外一个单词，只需要3种基础操作：

• insert
• delete
• replace

注意：在这里我们假设每个操作的代价都是1.

编辑距离，指的就是把一个单词编辑成另外一个单词所需要的操作代价。

有了编辑距离，我们就可以通过便利词典中的所有单词，然后分别计算用户输入单词与词典中每个单词之间的编辑距离，最后返回编辑距离最短的单词作为结果。

这种方法的缺点在于需要对词典进行遍历，时间复杂度太高。

Better Way

更好的解决方法如下：

首先我们需要根据用户输入，分别采用3种编辑操作（replace/insert/delete），生成一系列编辑距离为1，2的字符串，然后通过过滤这些生成字符串的方法，找到最优的返回值。

为什么只生成编辑距离为1，2的字符串？

因为在实际应用场景中，编辑距离小于等于2已经可以满足绝大多数的拼写纠错场景。

How to Select? (怎么过滤)

先给出问题的数学定义：

接下来对定义的公式进行数学上的转换：

所以，我们只需要求出：

1. \(p(s|c)\): 对于一个正确的字符串\(c\)，有百分之多少的人写成了\(s\)的形式，可以通过历史数据统计出来；
2. \(p(c)\): Unigram probability，单词\(c\)在所有文章中出现的概率。

如何计算\(p(s|c)\)？

示例：

正确：apple
用户1: app
用户2: appl
用户3: appl
用户4: app
用户5: appla
用户6: appl

那么，根据上面的统计数据，可以得出：

\[p(appl | apple) = \frac{3}{6} = 50\% \\ p(app | apple) = \frac{2}{6} = 33.33\% \\ \]

---

补充知识：贝叶斯定理

\[p(x,y)=p(x|y)p(y)=p(y|x)p(x) \\ \implies p(x|y) = \frac{p(y|x)p(x)}{p(y)} \]

---

Filtering Words (过滤单词)

对于NLP的应⽤，我们通常先把停⽤词、出现频率很低的词汇过滤掉，这其实类似于特征筛选的过程。

Removing Stop Words

在英⽂⾥，⽐如 “the”, “an”, “their”这些都可以作为停⽤词来处理。但是，也需要考虑⾃⼰的应⽤场景。

比如，在通常的场景中，“好”，“很好”...这类词汇可以作为停用词进行过滤掉，但是，对于情感分析的应用场景，这些词汇反而成为了关键词汇。

通常我们可以对通用的停用词库进行删除和增加的操作，使其符合我们的应用场景。

Low Frequency Words

出现频率特别低的词汇对分析作⽤不⼤，所以⼀般也会去掉。把停⽤词、出现频率低的词过滤之后，即可以得到⼀个我们的词典库。

Words Normalization (单词规范化)

词干提取（stemming）和词形还原（lemmatization）

Porter Stemmer的java实现

最常用的两种normalization技术：

• Stemming (词干提取)
• lemmatization (词形还原)

注意：英文需要normalization，中文不需要。

Stemming: one way to normalize

Stemming最常用的方法就是：Porter Stemmer。

Porter Stemmer的实现思路，通过语言学家编写的一系列规则，对单词的形式进行转换，以达到词干提取的目的。

Text Representation (文本的表示)

主要介绍用向量表示文本的方法。

Word Representation (单词的表示)

最常用的表示方式：One-hot representation/encoding。

假设我们的词典⾥有7个单词：

[我们，去，爬⼭，今天，你们，昨天，运动]

每个单词在词典中出现的位置设置为1，其他位置设置为0.

每个向量的长度都等于词典的长度。

Sentence Representation (句子的表示)

假设我们的词典⾥有8个单词：

[我们，又，去，爬⼭，今天，你们，昨天，跑步]

注意：句子的表示需要先进行分词。

Boolean representation

根据词典中的单词是否在句子中出现，是则在相应的位置设置为1（按照词典的排列顺序），否则设置为0.

Count-based representation

根据词典中的单词在句子中出现的次数，在相应的位置设置为出现次数（按照词典的排列顺序），不出现则设置为0.

这种表示方法记录了单词的频率。

Sentence Similarity

在NLP中，要理解语义的一个重要方法就是如何计算两个文本之间的相似度，这里主要介绍了如何计算两个句子之间的相似度。

Euclidean distance (欧式距离)

计算距离第⼀种⽅法：欧式距离\(d = |s_1 - s_2|\)。

\[s_1 = (x_1, x_2, x_3) \\ s_2 = (y_1, y_2, y_3) \\ d = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + (x_3-y_3)^2} \]

欧式距离越小，意味着两个句子越接近，也就是越相似。

示例：

计算上面3个句子之间的欧式距离：

\[d(S_1,S_2) = \sqrt{1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2} = \sqrt{6} \\ d(S_1,S_3) = \sqrt{1^2 + 2^2 + 1^2 + 1^2 + 1^2} = \sqrt{8} \\ d(S_2,S_3) = \sqrt{2^2 + 2^2 + 1^2 + 1^2 } = \sqrt{10} \]

在这种表示下，\(S_1\)和\(S_2\)之间的欧式距离最小，也就是3个句子中“我们今天去爬山”和“你们昨天跑步”两个句子最接近。

欧式距离计算⽅法有什么缺点？

因为向量是既有方向又有大小的，而欧式距离显然只考虑了向量的大小，而没有考虑方向。

Cosine similarity (余弦相似度)

计算距离第⼀种⽅法：余弦相似度\(d = \frac{s_1 \cdot s_2}{|s_1|*|s_2|}\)。

分子的内积就考虑了方向，分母范数（向量长度）的相乘可以理解为normalization，同时也考虑了大小。

\[s_1 = (x_1, x_2, x_3) \\ s_2 = (y_1, y_2, y_3) \\ d = \frac{x_1y_1 + x_2y_2 + x_3y_3}{\sqrt{x_1^2 + x_2^2 + x_3^2}\sqrt{y_1^2 + y_2^2 + y_3^2}} \]

余弦相似度是在NLP中计算距离更常用的方法，因为他既考虑了大小，又考虑了方向。

余弦相似度越大，意味着两个句子越接近，也就是越相似。（和欧式距离相反）

示例：

计算上面3个句子之间的余弦相似度：

\[d(S_1,S_2) = 0 \\ d(S_1,S_3) = \frac{2+1}{\sqrt{3}\sqrt{11}} = \frac{3}{\sqrt{33}} \\ d(S_2,S_3) = \frac{2}{\sqrt{3}\sqrt{11}} = \frac{2}{\sqrt{33}} \]

在这种表示下，\(S_1\)和\(S_3\)之间的余弦相似度最大，也就是3个句子中“我们今天去爬山”和“你们又去爬山又去跑步”两个句子最接近。

回顾句⼦的表示⽅式

下面3个句子的所有单词组成了词典库：

采用Count-based representation表示3个句子如下：

句子2中“denied”一词的重要性明显是高于“he”的，但是用这种表示方式却权重更小。并不是出现的越多就越重要，并不是出现的越少就越不重要！

所以我们需要采用tf-idf文本表示。

Tf-idf Representation

Tf-idf的计算公式

\(tf(d,w)\)其实就是Count-based representation的表示方式，最重要的是\(idf(w)\)考虑了单词的重要性。

\(idf(w)\)项考虑单词重要性的思路

一个单词如果在更多的文档中出现，则意味着该单词的重要性不高，e.g. he/the/a...；反之则意味着该单词的重要性很高。

例子

通过下面3个例句，演示如何计算tf-idf。

句子1: 今天 上 NLP 课程
句子2: 今天 的 课程 有 意思
句子3: 数据 课程 也 有 意思

计算步骤如下：

1. 定义词典：|词典|=9

   [今天，上，NLP，课程，的，有，意思，数据，也]
   

2. 分别把每个句子用tf-idf向量表示

   句子1:

   \[\begin{aligned} S1 &= (1*\log\frac{3}{2}, 1*\log\frac{3}{1}, 1*\log\frac{3}{1}, 1*\log\frac{3}{3}, 0, 0, 0, 0, 0) \\ &= (\log\frac{3}{2}, \log3, \log3, \log1, 0, 0, 0, 0, 0) \end{aligned} \]

   句子2:

   \[\begin{aligned} S2 &= (1*\log\frac{3}{2}, 0, 0, 1*\log\frac{3}{3}, 1*\log\frac{3}{1}, 1*\log\frac{3}{2}, 1*\log\frac{3}{2}, 0, 0) \\ &= (\log\frac{3}{2}, 0, 0, \log1, \log3, \log\frac{3}{2}, \log\frac{3}{2}, 0, 0) \end{aligned} \]

   句子3:

   \[\begin{aligned} S3 &= (0, 0, 0, 1*\log\frac{3}{3}, 0, 1*\log\frac{3}{2}, 1*\log\frac{3}{2}, 1*\log\frac{3}{1}, 1*\log\frac{3}{2}) \\ &= (0, 0, 0, \log1, 0, \log\frac{3}{2}, \log\frac{3}{2}, \log3, \log\frac{3}{2}) \end{aligned} \]

我们目前讲解了3种One-hot representation表示句子：

• boolean-based
• count-based
• tfidf-based

同时也讲解了如何衡量句子之间的相似度。

Measure Similarity Between Words

通过计算语义相似度引出词向量。

下面哪些单词之间的语义相似度更高？

我们，爬山，运动，昨天

从语义的角度来说，sim(我们, 爬山) < sim(运动, 爬山)，但是我们应该如何表示单词，才能实现这种比较呢。

利⽤ One-hot 表示法表达单词之间相似度？

计算每两个单词之间的欧式距离，会发现都等于\(\sqrt{2}\)；如果是计算余弦相似度，那么则都等于0。这就说明了用One-hot表示法无法计算单词之间的相似度。

Another Issue: Sparsity

用One-hot表示单词/句子的另外一个问题就是稀疏性，每个单词/句子的向量长度都等于词典的长度，而向量的大多数位置都是为0，只有极少数位置有值。

总结起来，One-hot表示法的两个问题：

1. 不能表示语义相似度
2. 稀疏性

From One-hot Representation to Distributed Representation

为了解决上面的两个问题，所以提出了分布式表示法：

分布式表示法每个位置都有值，向量的长度是自定义的，通常100、200，顶多300，相比于One-hot表示法节省了非常多的空间。

先暂时不考虑分布式表示法的向量是如何生成的，先来计算一下单词之间的相似度。

计算欧式距离：

\[\begin{aligned} d(我们, 爬山) &= \sqrt{0.1^2 + 0.1^2 + 0.3^2 + 0.1^2} \\ &= \sqrt{0.01 + 0.01 + 0.309 + 0.01} \\ &= \sqrt{0.12} \end{aligned} \\ \begin{aligned} d(运动, 爬山) &= \sqrt{0.1^2 + 0.1^2} \\ &= \sqrt{0.02} \end{aligned} \]

显然，\(d(运动, 爬山) \lt d(我们, 爬山)\)，即\(sim(运动, 爬山) \gt sim(我们, 爬山)\)。

同理计算余弦相似度也能得出同样的结论。

说明这种分布式的表示方法是可以计算单词之间的相似度的。单词的分布式表示法也称之为词向量（word vectors）。

Comparing the Capacities

Q: 100 维的 One-Hot 表示法最多可以表达多少个不同的单词？

A: 说明向量的大小=100，即仅仅只能表示100个单词。

Q: 100 维的 分布式 表示法最多可以表达多少个不同的单词？

A: 即使每一维都是binary的形式，也就是只能用0/1表示，那么也能表示\(2^{100}\)个单词；而实际上每一维并不只是binary的形式，所以理论上是可以表示无穷多个单词的。

Learn Word Embeddings

主要介绍如何训练词向量，以及句子向量的简单计算。

输入：大量的文本字符串，通常需要\(10^9\)量级以上的训练数据。

学习模型包含：Skip-Graw、Glove、CBOW、RNN/LSTM、MF、Gaussian Embedding...

训练之前需要定义好的最重要的参数就是词向量的维数，\(d=50/100/200/300...\)，通常维数不超过30。

通常情况下，我们并不需要自己去训练词向量，只需要使用别人训练好的即可，因为训练词向量是一个非常耗费资源的事情。但是如果做的是垂直领域的NLP问题，比如金融、医疗等，那么如果要达到比较好的效果，则需要自己训练词向量。

Essence of Word Embedding

理想中的情况，词向量代表单词的意思（我们的目标），从某种意义上，我们可以把词向量理解成词的意思。

假如把词向量映射到二维空间，那么我们希望呈现出如下特征：

即相近的单词聚集到一起。

同时，我们也希望呈现出如下的数学特征：

\[woman - man \approx girl - boy \]

这也是我们用来判断学习出来的词向量的效果如何的方法。

From Word Embedding to Sentence Embedding

计算句子向量的方法：

1. 平均法则——把组成句子的单词对应的词向量取均值。

   比如“我们去运动”表示为：

2. LSTM/RNN

Inverted Index (倒排表)

通过回顾问答系统，引出到排表。

Recap: Retrieval-based QA System

假设知识库中有N个问题，那么时间复杂度大概是：

\[O(N) \cdot 每次相似度计算复杂度 \]

如果知识库非常大，那么复杂度其实是非常高的，完全无法满足实时性的要求。

How to Reduce Time Complexity?

这里只讲解核心思路，不讲解具体解决方法。

核心思路：”层次过滤思想“

所谓的“层次过滤思想”，指的是在接受到输入问题的时候，不是直接去知识库中对比问题相似度，而是通过层层过滤的方法，把知识库中的问题规模不断地缩小，最后才进行相似度计算。

graph TD A[输入问题] --> B(知识库问题规模: 10^6) B --过滤1--> C(知识库问题规模: 10^3) C --过滤2--> D(知识库问题规模: 10^2) D --Cosine similarity--> E[知识库问题规模: 5]

注意：复杂度(过滤器1) < 复杂度(过滤器2) < 复杂度(相似度)，否则达不到减小时间复杂度的效果。

问答系统变成：

Introducing Inverted Index

倒排表来源于搜索引擎，也是搜索引擎的重要技术。

假设搜索引擎爬虫从网上爬取了4个文档，那么我们就可以存储倒排表如下：

这样假如用户在搜索引擎中输入“运动”，那么我们很容易就可以找到“运动”出现在Doc1和Doc2中，然后再通过Page rank对Doc1和Doc2进行排序返回即可。

接下来看一下如何把倒排表应用到问答系统中：

1. 对输入问题进行分词。

2. 过滤1: 选择至少包含一个单词的问题，如果一个单词都不包含，那么我们大概可以认为该问题与用户问题相似度较低。

3. 过滤2: 选择至少包含两个单词的问题，假如第一层过滤之后还剩下很多问题，那么我们可以继续进行过滤。

4. 过滤到问题数量合适，再计算相似度。