NLP|NLP训练营学习记录(一) 机器翻译|人工智能|自然语言处

文章目录

NLP训练营学习记录(一)
- 理解性小案例：机器翻译
- - 概率语言模型
  - 优化
  - 自然语言处理的四个维度
- 算法复杂度
- - 归并排序以及Master Theorem（主定理分析）
  - P、NP hard、NP complete问题
  - 斐波那契数的计算（介绍递归算法的时间复杂度）
  - - 递归实现
    - 循环实现（将递归问题转化为DP问题）
- 基于检索的问答系统的搭建（做NLP的流程介绍）
- - 问答系统介绍
  - 文本处理
  - - 切词
    - - 前向最大匹配（forward max matching）
      - 考虑语义的分词算法
    - 拼写纠错
    - - 遍历词表选择候选词法
      - 生成候选词法
    - 去停用词
    - - NLTK停用词库
      - 停用词过滤
    - 词干提取（词标准化）
    - 词的表示方法（word representation）
    - - 句子的表示方法
    - 计算相似度的方法
  - 问答系统搭建
  - - 层次过滤思想
    - 倒排表 Inverted Index（过滤器）
    - 简单问答系统实现
    - - 1.读取并处理语料库
      - 2.读取JSON数据
      - 3.构建倒排表
      - 4.根据我们的corpus训练词向量，使用word2vec
      - 5.通过倒排表进行过滤
      - 6.转换成句子向量
      - 7.计算相似度
      - 8.查找知识库中相似度最高的句子

学自贪心训练营

NLP训练营学习记录(一) 理解性小案例：机器翻译这个小案例是基于静态机器翻译的（也就是基于双语对应词表进行翻译的）
它的一个流程图为：

文章图片

首先对中文根据中文词典对中文文本进行切词
然后对照中英词表将每个单词转换成英文（这就是translate model做的事情）得到broken english
然后通过language model找到组合概率最大的那句英文，其为翻译后的英文。语言语言模型的作用是判断你的输入能不能构成依据人话（这不是深度学习的内容，而是机器学习的概率语言模型）

例如：今晚的课程很有意思 ↓ 今晚/的/课程/很有意思 ↓ tonight/of/the course/interesting（Translate Model） ↓ P(tonight,of,the course,interesting) = 0.1\ P(of,tonight,the course,interesting) = 0.2Language Model ... P(interesting,the course,of,tonight) = 0.7/ ↓ interesting the course of tonight

当然这只是举个例子，这个翻译并不正确。
概率语言模型
那么P是怎么计算的呢？这个P的计算模型就是概率语言模型。
马尔科夫假设：一个单词的出现与前面所有单词都相关。

那么： P(tonight,of,the course,interesting) = P(tonight) * P(of|tonight) * P(the course|tonight,of) * P(instersting|tonight,of,the course)

P(tonight)就是整个数据集中tonight单词出现的频率（当样本足够多时概率与频率相等）
P(of|tonight)这是一个条件概率，of前面是tonight出现的概率。也就是将所有of出现的地方找出来，前面是tonight的样本数占全of样本的多少。
P(the course|tonight,of)这个不好计算，但是可以使用贝叶斯公式将其转化为可计算的。P(the course|tonight,of) = (P(tonight,of|the course) * P(the course)) / P(tonight,of)。
然后就可以求出了。
但是这样求这样一句话的概率需要计算四个这样的参数，如果句子一长，并且还需要求好几个组合的概率这样效率太低。
所以进行一个假设，一个单词的出现和它前面n个单词相关。这就是n-gram。详细的，和前面0个相关就是Uni-gram，和前面一个相关就是Bi-gram，和前面两个相关就是Tri-gram。

Uni-gram

# unigram假设各个单词之间相互独立 P(a,b,c) = P(a) * P(b) * P(c)
Bi-gram

# Bi-gram假设一个单词的出现与前面一个单词相关 P(a,b,c) = P(a) * P(b|a) * P(c|b)
Tri-gram

# Tri-garm假设一个单词的出现与前面两个单词相关 P(a,b,c) = P(a) * P(b|a) * P(c|a,b)

实验表明n取3的时候最好。我也忘了哪个博客上看到过的。
优化
上面那个语言模型需要求 broken english 中的所有单词的排列组合，这样算法复杂度就是阶乘的。那有没有可能将它优化成多项式复杂度呢？如果将translate model与language model整合起来作为一个model会不会优化呢？

文章图片

使用的是Viterbi算法（是个DP算法）
所以P(e|c) = (P(c|e) * P(e)) / P(c)
将问题分解为两个子问题。
（这块我也没弄清是啥意思，视频课上就大概的讲了一下。以我有限的概率论知识只能模模糊糊的理解）
得到的结论是：max P(e|c) = max P(c|e) * P(e)
自然语言处理的四个维度

Semantic 语义
Syntax 句子结构（相关任务有：句法分析，依存分析，关系抽取）
Morphology 单词（相关任务有：分词，词性标注，命名实体识别NER）
Phonetics 声音（这个与硬件相关，不做重点学习）

算法复杂度归并排序以及Master Theorem（主定理分析）
归并排序是一种Divide and Conguer（分而治之）算法。
用二分一直分，直到将整个数组拆分成一个个的元素，然后再两两合并。在合并的过程中将左右两个部分按照规则（小、大）将元素放到新数组中（这样就排序了），然后返回新数组。直到返回到递归入口时就整体排序好了。
时间递归通式：

原问题左子问题右子问题 T(n) = T(n/2) + T(n/2) + n

主定理分析适用于复杂度为 T(n) = aT(n/b) + f(n) 的时间复杂度的分析。
说人话就是用于求分治这种大化小递归求解的复杂度。
T(n) = aT(n/b) + f(n)
其有三种情况的复杂度：

n^logba > f(n) ：则复杂度为 O(n^logba)
n^logba = f(n) ：则复杂度为 O(n^logba * logk+1n)。f(n) = n^logba * logkn，使用这个等式求k
n^logba < f(n) ：则复杂度为 O(f(n))

例如： T(n) = 3T(n/2) + n^2n的log以b为底a的对数次方 n^log~b~a = n^log~2~3 = n^1.6f(n) = n^2n^log~b~a < f(n)，所以该算法复杂度为 O(f(n)) = O(n^2)

归并排序的时间复杂度： T(n) = 2 * T(n/2) + n a = 2, b = 2n^log~b~a = n^1 f(n) = nn^log~b~a = f(n), 所以复杂度为 O(n^log~b~a * log^k+1^n) n^log~2~2 * log^k^n = n, 所以k=0(0次方=1) 所以综上复杂度为O(nlogn)

另一种理解方式
拆分过程有logn次，合并过程有logn次，每次合并的排序时间为n。所以总时间复杂度为O(logn)+O(nlogn) = O(nlogn)
P、NP hard、NP complete问题
简单的理解如下。
P问题就是现有计算机能解决的问题，也就是 O(np) 时间复杂度的问题。P为常数。
NP hard问题就是现有计算机在有限时间内解决不了的。也就是时间复杂度大于等于 O(Pn)
NP complete问题就是出于P问题与NP hard问题之间的一种模糊区域的问题，是NP hard的一个子集。
那现有计算机如何解决NP hard问题：

如果n很小，还是可以用原算法解决。
使用近似算法可以解决。（但是近似算法只能逼近最优解，而不能得到最优解）
1. 提出近似算法
2. 指出时间复杂度
3. 计算误差值（也就是近似解距离最优解的距离）

斐波那契数的计算（介绍递归算法的时间复杂度）
斐波那契数列形式：1,1,2,3,5,8,13,21...，求第n个数。
特征为：第n个数为第n-1个数和第n-2个数之和。
递归实现

def fib(n): if n < 3: return 1 return fib(n-1) + fib(n-2)

如果使用表面的时间复杂度 T(n) = T(n-1) + T(n-2) + 1 这样不能转换成主定理分析的那种形式所以需要转换一下，我们可以想到return fib(n-1) + fib(n-2)是不是类似于一颗二叉树而二叉树的每个节点我们都需要计算一次，所以整个算法的复杂度是 2^n（n为树的高度）。所以整个算法复杂度跟树的高度相关。怎么计算树的高度呢？例如斐波那契数列，一个节点-2，所以树的高度是跟n线性相关的。而O可以表示成高于，所以复杂度可以表示为O(2^n)

文章图片

循环实现（将递归问题转化为DP问题）我们可以将斐波那契数列放到数组中例如

array = [f(1),f(2),f(3),f(4)...]

从3开始循环，array[i] = array[i-1] + array[i-2]，这样使用数组去保存子问题，然后父问题直接索引子问题的解就可以解决。

def fib(tmp=[1,1], n): for i in range(2, n): tmp[i] = tmp[i-1] + tmp[i-2] return tmp[n-1]

复杂度为O(n)
基于检索的问答系统的搭建（做NLP的流程介绍）问答系统介绍
例如一个简单的问答系统：

设计一套知识库（语料库）
- 语料库的内容是问与答，可以以字典形式存储
设计一个句子相似度算法
- 根据用户的输入与语料库中各个问题的相似度来确定会答用户什么答案
  
  文章图片

注意！这个问答系统并不是基于机器学习的，因为它并没有学习过程。它是一个基于检索的问答系统，可以解决问答任务。
问答系统的一个流程：

文章图片

其中的知识点补充：

对词进行预处理：
- 错词纠正（spell correct）：有的人输入有误，但是系统对错词要有一定的容错性
- 词干提取（stemming/lemmatisation）：有时候我们需要将有的词转换成它的原型。例如一个词的时态等对于理解这个句子没有用，那么我就可以将所有的时态都转换成同一个词。
- 去停用词（stop-words）：对于有些不再使用的词，或一些无关意义的词（a、the等）我们可以去掉
- 词过滤（words filter）：过滤掉一些垃圾。例如html的tag等
- 同义词：对一些单词可以使用同义词进行替换
将词映射到数学空间：
- 独热向量：使用独热向量进行转换
- 词频向量（count vector）：一个单词在语料库中出现了几次就在对应位置上为几（独热向量的升级版）
- tf-idf：对count vector的一个升级版，词频逆向文件频率来进行计算。
- word2vec：使用词向量对词进行映射

将词表示出来后，可以直接简单相加作为句子的向量！或者使用其他数学映射方法都可以。

相似度计算：
- 欧氏距离：使用欧氏距离进行计算
- cos距离：使用cos函数进行计算
- 等等

文本处理
我们在做一个NLP项目之前，都会需要进行文本处理，对文本进行分词、清洗、特征提取等操作。
所以这里有一个文本处理的 PIPline。

文章图片

特征提取就是将字符串转换为词向量的过程。
英文里常用标准化，中文里不常用！
切词分词常用工具：

Jieba
SnowNLP
LTP（哈工大建的工具）
HanNLP

【NLP|NLP训练营学习记录(一)】Jieba的教程在特征提取初识那篇文章里有写。下面介绍一下分词工具一些的底层算法。
前向最大匹配（forward max matching）向前最大匹配就是要匹配最长的一个子串。所以我们定义一个最大窗口，在其中寻找字典中存在的最长的子串作为一个词。向前最大匹配是个贪心算法。

文章图片

该算法的时间复杂度为 O(nm)。所以max_len根据高频词的长度选取。
该算法的缺点：

无法细分，只能确定最长匹配词
算法的解是局部最优解
算法效率比较低
选择的词不是根据语义选择出来的

例如上面的例子：最终结果为：我们/经常/有意见/分歧但是这句话按照断句应该为：我们/经常/有/意见/分歧所以可以看大最大匹配算法不能解决细分问题，它的解只是局部最优解。它选择的词不是根据语义选择出来的。

def cut_word(content, dic, max_len = 3): words = []start = 0 while start < len(content): # 获取窗口 snippet = content[start: min(start + max_len, len(content))]# 从窗口中检查字典中的最长词 for tail in range(len(snippet), -1, -1): word = snippet[:tail] if word in dic: words.append(word) break# 对不在字典中的词直接添加进分词中作为陌生词 if not word: words.append(snippet) start += len(snippet) start += len(word)return wordscontent = "我们经常有意见分歧疑惑" dic = ["我", "们", "我们", "经", "常", "经常", "有", "意", "见", "有意见", "分", "歧", "分歧"] cut_word(content, dic)

result: ['我们', '经常', '有意见', '分歧', '疑惑']

考虑语义的分词算法可以通过在分词算法上方搭建一个语言模型，将字典中所有可能的分词结果传入模型中，判断哪种分词成话的概率更大。

文章图片

Language Model可以使用最简单的一个语言模型，就像上面将的N-gram模型，直接套个Uni-gram计算整句话的概率即可。

但是如果你使用这种简单的语言模型的话，会导致计算出来的句子的概率非常低，容易溢出因为语料库非常大，而出现的词可能非常小。P(经常) = num(经常) / num(所有词)例如： P(经常，有，意见，分歧) = P(经常) * P(有) * P(意见) * P(分歧) = 0.0002 * 0.00032 * 0.00001 * 0.000054但是如果加上一个log，则可以解决这个问题。 log P(经常，有，意见，分歧) = log P(经常) + log P(有) + log P(意见) + log P(分歧)我们的目的是比较P的大小，而log并不改变单调性。

这种方法和之前说的那个简单机器翻译一样，有组合性，所以时间复杂度非常高。
这种方法两步走：1. 组合所有的词，2. 选择最好的组合。
我们可以将两步合成一步吗？就像之前说的那个Viterbi算法。我们也可以使用Viterbi算法进行。

文章图片

如上图，我们可以将词典及其对应词的概率提前计算出来。然后我们可以将句子中的每个字符作为一条边，形成一个只有一条线的图，每个边都有对应的权重。根据词典中的多字符词形成另外的一些边。最终形成一个有向无环图，该图每条边代表词典中的一个词，然后我们可以根据最短路径找到概率最小（因为我们在log上加了个符号）的那个组合。
这样我们就把组合与概率模型组合在了一起。
不使用Viterbi算法的普通排列组合切词：

文章图片

import pandas as pd from tqdm import tqdm import mathdic = pd.read_excel("Dictionary/chinese_dictionary.xlsx") dic.columns = ["词", "词性", "词频"]# 获取所有词的频数 all_words_num = dic["词频"].sum() # 将词作为键值，词频作为值存在字典中 freq_dic = dict([(dic.iloc[i, 0], -math.log(int(dic.iloc[i, 2])/int(all_words_num))) for i in tqdm(range(len(dic)))])def cut_words(content): result = [] freq = [] def cut(tail, prefix = "", max_len = 3): if not tail: print(prefix, type(prefix)) result.append(prefix.split()) freq.append([freq_dic[name] for name in result[-1]]) # 前向最大匹配，只不过不需要外层递进循环了，递归就做了 for i in range(min(max_len, len(tail)), -1, -1): if tail[: i] in freq_dic: cut(tail[i : ], prefix + tail[: i] + " ", max_len) cut(content) return result, freqdef language_model(words, freq): mini, min_index = float('inf'), 0 for i in range(len(freq)): summ = sum(freq[i]) print(words[i], summ) if summ < mini: mini, min_index = summ, i return words[i]words, freq = cut_words("今晚的课程很有意思") true_words = language_model(words, freq)

今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思今晚的课程很有意思 ['今晚', '的', '课程', '很', '有意思'] 63.51556318075569 ['今晚', '的', '课程', '很', '有意', '思'] 74.7161258162291 ['今晚', '的', '课程', '很', '有', '意思'] 76.01133328502836 ['今晚', '的', '课程', '很', '有', '意', '思'] 86.79423093949796 ['今晚', '的', '课', '程', '很', '有意思'] 75.27876592923911 ['今晚', '的', '课', '程', '很', '有意', '思'] 86.47932856471252 ['今晚', '的', '课', '程', '很', '有', '意思'] 87.77453603351177 ['今晚', '的', '课', '程', '很', '有', '意', '思'] 98.55743368798139 ['今', '晚', '的', '课程', '很', '有意思'] 74.61091117362544 ['今', '晚', '的', '课程', '很', '有意', '思'] 85.81147380909886 ['今', '晚', '的', '课程', '很', '有', '意思'] 87.10668127789809 ['今', '晚', '的', '课程', '很', '有', '意', '思'] 97.8895789323677 ['今', '晚', '的', '课', '程', '很', '有意思'] 86.37411392210885 ['今', '晚', '的', '课', '程', '很', '有意', '思'] 97.57467655758225 ['今', '晚', '的', '课', '程', '很', '有', '意思'] 98.8698840263815 ['今', '晚', '的', '课', '程', '很', '有', '意', '思'] 109.65278168085112

使用Viterbi算法实现分词：

import pandas as pd import math from tqdm import tqdmdic = pd.read_excel("Dictionary/chinese_dictionary.xlsx") dic.columns = ["词", "词性", "词频"]all_freq = dic["词频"].sum() dic_freq = dict([(dic.iloc[i, 0], -math.log(int(dic.iloc[i, 2]) / int(all_freq))) for i in tqdm(range(len(dic)))])inf = float("inf")def create_matrix(content, max_len = 5): length = len(content) # 加一是因为，边作为一个字。而点比边要多一 m = [[0 for i in range(length + 1)] for i in range(length + 1)]for i in range(length + 1): for j in range(length + 1): if i < j: if content[i: j] in dic_freq: print("目前是" + str(i) + "到" + str(j) + "当前词是：" + content[i: j]) m[i][j] = dic_freq[content[i: j]] else: m[i][j] = inf elif i == j: m[i][j] = 0 else: if content[i-1: j-1: -1] in dic_freq: print("目前是" + str(i) + "到" + str(j) + "当前词是："+content[i-1: j-1: -1]) m[i][j] = dic_freq[content[i-1: j-1: -1]] else: m[i][j] = infreturn mdef dijkstra(e, source=0): dist = e[source] length = len(dist) book = [0 for i in range(length)] path = [0 for i in range(length)]current = source# 因为是一个一个遍历的所以得遍历n次 for i in range(length): # 标识当前节点被访问过 book[current] = 1# 对当前节点所连接的边进行松弛 for i in range(length): if e[current][i] != 0 and e[current][i] != inf: if dist[i] > dist[current] + e[current][i]: dist[i] = dist[current] + e[current][i] path[i] = current# 在为访问过的节点中寻找dist表中最小的那个作为当前节点 nex, mini = 0, inf for i in range(length): if not book[i] and dist[i] < mini: nex, mini = i, dist[i] current = nexreturn dist, path# 将句子中的词根据 -log词频作为边的权重，转换为邻接矩阵，然后使用单元最短路径求最适合的分词 matrix = create_matrix("今晚的课程很有意思") print(matrix) dist, path = dijkstra(matrix) print(dist, path)

目前是0到1当前词是：今目前是0到2当前词是：今晚目前是1到2当前词是：晚目前是2到1当前词是：晚目前是2到3当前词是：的目前是3到2当前词是：的目前是3到4当前词是：课目前是3到5当前词是：课程目前是4到3当前词是：课目前是4到5当前词是：程目前是5到4当前词是：程目前是5到6当前词是：很目前是6到5当前词是：很目前是6到7当前词是：有目前是6到8当前词是：有意目前是6到9当前词是：有意思目前是7到6当前词是：有目前是7到8当前词是：意目前是7到9当前词是：意思目前是8到7当前词是：意目前是8到9当前词是：思目前是9到7当前词是：思意目前是9到8当前词是：思 [[0, 11.918118109198849, 12.760601309734913, inf, inf, inf, inf, inf, inf, inf], [inf, 0, 11.9378311934058, inf, inf, inf, inf, inf, inf, inf], [inf, 11.9378311934058, 0, 13.685095778492528, inf, inf, inf, inf, inf, inf], [inf, inf, 13.685095778492528, 0, 12.157274337371875, 12.306479340993585, inf, inf, inf, inf], [inf, inf, inf, 12.157274337371875, 0, 11.912407752105128, inf, inf, inf, inf], [inf, inf, inf, inf, 11.912407752105128, 0, 12.003279294132273, inf, inf, inf], [inf, inf, inf, inf, inf, 12.003279294132273, 0, 12.21370441428447, 12.04848390203999, 12.760107457402396], [inf, inf, inf, inf, inf, inf, 12.21370441428447, 0, 11.912884611024374, 13.042173147390589], [inf, inf, inf, inf, inf, inf, inf, 11.912884611024374, 0, 11.912186190835818], [inf, inf, inf, inf, inf, inf, inf, 12.425332809548896, 11.912186190835818, 0]] [0, 11.918118109198849, 12.760601309734913, 26.44569708822744, 38.602971425599314, 38.752176429221024, 50.75545572335329, 62.969160137637765, 62.803939625393284, 63.51556318075569] [0, 0, 0, 2, 3, 3, 5, 6, 6, 6]

将路径[0, 0, 0, 2, 3, 3, 5, 6, 6, 6]手动回退一下就可以获得分词结果了。

i = len(path) - 1 words = [] while i != 0: words.append(content[path[i] : i]) i = path[i]print(words)

['有意思', '很', '课程', '的', '今晚']

我们写的算法并没有识别未知词的功能（字典中没有的词），但是jieba可以识别。
所以用户写错也需要对错词进行分词
拼写纠错用户可能会输入错误的词，但是我们的系统要推测这个错词的原词是什么，并作出正确的回应。
拼写纠错的两个场景：
1. 用户输入了错别词

用户输入错别字，可以判断词是否在词库中判断错别词。

2. 用户没有输入错别字但是根据上下文推断不是这个词。

用户词的上下文错误，可以根据语言模型判断是否词错误。

对于错别词纠错，可以根据错别词与词库中的词计算编辑距离来判断。
编辑距离有三种计算规则：insert、delete、replace

insert：插入多少个字能和候选词相同
delete：删除多少个字能和候选词相同
replace：替换多少个字能和候选词相同

将它们三种计算规则的值加起来就是编辑距离

文章图片

there:ther|r->ereplace=1 their:the|r->i|rreplace=1 thesis: the|rr->si,add sreplace=2,insert=1 theirs: the|r->i|r,add sreplace=1,insert=1 the:therr,delete rrdelete=2

从上述分析可以看出，there的编辑距离为1，their的编辑距离也是1，其他的编辑距离都要大于前两者。所以前两者是最优的纠错结果，选择哪一个根据语言模型来判断。
遍历词表选择候选词法遍历过滤候选词中的词也分为两部分。第一部分：错词检查，第二部分：错词纠正。

错词检查只需要遍历词库然后计算输入词与词库词的编辑距离，选择正确且编辑距离最小的词。（过滤出来的词可能有好几个）
错词纠正则需要使用LM，也就是对这词计算条件概率。max P(c|w)，c∈过滤出来的这几个词。用户输入错误的条件下，用户想要输入的单词为c的概率。这个条件概率是计算不出来的，因为w是c的部分概率。画图如下：
可以看出，c1发生的条件下w发生的概率，而不能计算w发生的条件下c1发生的概率。

文章图片
- 这时就要使用贝叶斯公式对上述公式进行转换
  
  word = argmax P(c|w)，c∈set(c1,c2...)P(c|w) = P(w|c) * P(c) / P(w) # 而w是一个与c无关的变元，P(w)是个常数，而我们要求得是概率最大的即可，所以可以写成 P(c|w) = P(w|c) * P(c)∴word = argmax P(w|c) * P(c)P(c):整个语料库中单词c出现的频数/总单词频数 P(w|c):语料库中本意要写c而写成w的文本占总文本的百分比（概率），所以对于语料库需人为对其打标签。也就是说打标签是其他人的工作，我们的程序现已知本意要写c而写成w的概率了。P(c)叫做语言模型，P(w|c)叫做转换模型

但是遍历词库中的所有词计算编辑距离太耗时，可以在创建词典的时候就生成一个单词树，然后根据单词树寻找最优纠错结果。
编辑距离如下：

def editDistance(word1, word2): word1_len, word2_len = len(word1), len(word2) dp = [[0 for i in range(word2_len+1)] for i in range(word1_len+1)]for i in range(word2_len + 1): dp[0][i] = i for j in range(word1_len + 1): dp[i][0] = ifor i in range(1, word1_len + 1): for j in range(1, word2_len + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1return dp[word1_len][word2_len]

纠错算法如下：

import jieba import mathdic = ["今晚", "的", "课程", "很", "没有", "没得", "意思"] # 错词字典，统计后端用户输入信息，用户想写成"没有"而写成"没油"的概率为0.5 wrong_dic = {"没有": {"没油": 0.5, "没得": 0.3}, "没得": {"没油": 0.2, "没嘚": 0.7}} word_freq = {"没油": 0.1, "没得": 0.2, "没有":0.3}content = "今晚的课程很没油意思" # 切词 words = list(jieba.cut(content)) # 判断错词与字典中编辑距离最近的词 wrong = {} for word in words: if word not in dic: mini_list, mini = [], float("inf") for word2 in dic: dis = editDistance(word, word2) if dis == mini: mini_list.append(word2) elif dis < mini: mini = dis mini_list.clear() mini_list.append(word2) wrong[word] = mini_listprint(wrong)# P(没有|没油) = P(没油|没有) * P(没油) for wrong_word in wrong: mini, mini_word = float("inf"), "" for word in wrong[wrong_word]: p = -math.log(wrong_dic[word][wrong_word]) - math.log(word_freq[wrong_word]) if p < mini: mini = p mini_word = word words[words.index(wrong_word)] = mini_wordprint(words)

{'没油': ['没有', '没得']} ['今晚', '的', '课程', '很', '没有', '意思']

生成候选词法遍历词库选择候选词时间复杂度与词库的大小有关，通常情况下词库非常大，所以上一种方法并不适用。
而根据统计，用户输入错误一般都只有1-2个字符。所以我们可以生成所有编辑距离为1的词，然后过滤出候选词。
根据用户输入，生成编辑距离为1或2的字符串。再判断该字符串是否在词库中即可。因为日常中用户输入错误只可能是小范围错误。但是我还是认为单词树要比这些算法更快

applreplace： bppl,cppl,... aapl,abpl,... ... add: aappl,bappl,... aappl,abppl,... ... delete: ppl,apl,app

这种方法也分为两步：

生成过滤候选词
选择出符合语义的词

生成候选词方法的：

import jieba import mathdic = ["今晚", "的", "课程", "很", "没有", "没得", "意思"] # 错词字典，统计后端用户输入信息，用户想写成"没有"而写成"没油"的概率为0.5 wrong_dic = {"没有": {"没油": 0.5, "没得": 0.3}, "没得": {"没油": 0.2, "没嘚": 0.7}} word_freq = {"没油": 0.1, "没得": 0.2, "没有":0.3} # 字符集，用于生成编辑距离为1的词 character = ["没", "得", "有", "油", "今", "晚", "的", "嘚"]content = "今晚的课程很没油意思" words = list(jieba.cut(content)) # 存储生成的编辑距离的词，error_word: [edit_word1, edit_word2...] gen_words = {}def generate(word, charater): insert = [word[:i] + c + word[i:len(word)] for i in range(0, len(word) + 1) for c in character] replace = [word[:i] + c + word[i + 1: len(word)] for i in range(0, len(word)) for c in character] delete = [word[:i] + word[i + 1: len(word)] for i in range(0, len(word))] return list(set(insert + replace + delete))for word in words: if word not in dic: # 初始化edit表 gen_words[word] = [] edit_words = list(filter(lambda x: x in dic, generate("没油", character))) gen_words[word].extend(edit_words)print(gen_words)# 判断P(没有|没油)和P(没得|没油)的概率谁大，因为我们要预测的是在写错的时候，原正确的词是谁，转换成-log就是谁最小谁最有可能 # 但是这种部分计算全部的概率在概率论中没有计算公式，所以要用贝叶斯公式转换一下 for wrong_word in gen_words: mini, mini_word = float("inf"), "" for word in gen_words[wrong_word]: p = -math.log(wrong_dic[word][wrong_word]) - math.log(word_freq[wrong_word]) if p < mini: mini = p mini_word = word words[words.index(wrong_word)] = mini_wordprint(words)

{'没油': ['没得', '没有']} ['今晚', '的', '课程', '很', '没有', '意思']

去停用词我们可以将出现的频率很低的词作为停用词过滤掉，因为这些词是稀疏的会导致模型欠拟合。所以我们需要将这些词过滤掉（类似于特征筛选）。
我们拥有一个停用词库，其中的词就是现代不会使用的词。对于停用词有两部分：停用词库中的词；频率低的词；我们需要过滤这两类词。
停用词库的组成：

将一些无意义的词作为停用词。例如英文中的：“the”、“a”等。
但是，有没有意义是根据你的应用场景决定的，并不是一成不变的。
- 例如在问答系统中像：“好”，“很好”，就是无关紧要的事，所以可以作为停用词
- 但是在情感分析中并不可以作为停用词。

NLTK停用词库 NLTK中拥有已有的停用词库，我们可以根据应用场景删除其中的一些停用词，加一些停用词。
对于NLTK工具而言，它是处理NL的一个工具，其功能有分词、分句、停用词过滤、词性标注、词频统计等。但是对于分词、分句、停用词过滤、词性标注而言是需要语料库支持的，而对于NLTK的语料库都是英文的，所以我们做NL处理时，用到的只有词频统计。
对中文自然语言处理而言，我个人认为没啥用，还不如用jieba，jieba该有的功能都有。
停用词过滤所以中文停用词可以使用中文停用词表、哈工大停用词表、百度停用词表。

import jieba from tqdm import tqdm import datetimedef load_stopwords(filepath): ''' stopwprds返回成一个list ''' time = datetime.datetime.now() print("load stopwords...") with open(filepath, 'r', encoding='utf-8') as stopfile: stopwords = [line.strip().strip('\n') for line in tqdm(stopfile.readlines())] print("stopwords end. use time:{}".format((datetime.datetime.now()-time).microseconds) + "ms") return stopwordscontent = "我们今天确实非常的开心" # 加载stopwords stopwords = load_stopwords("StopWords/hit_stopwords.txt") # 使用jieba进行分词 words = list(jieba.cut(content)) # 使用filter过滤掉停用词库中的词 words = list(filter(lambda word: False if word in stopwords else True, words)) print(words)

100%|████████████████████████████████████████████████████████████████████████████| 767/767 [00:00<00:00, 384490.40it/s] load stopwords... stopwords end. use time:5985ms ['今天', '确实', '非常', '开心']

词干提取（词标准化）对于Stemming而言适用于英文，中文使用的。
对于英文而言，strmming可以使用NLTK库进行处理。
词的表示方法（word representation）

one hot
- 使用一个稀疏向量表示一个词。这个向量长度为词典大小，当前词位于词典中的位置为1，其他都为0。
- 优点：简单
- 缺点：
  - 太过于稀疏，不利于学习。
  - 维度爆炸（词典太大）。
  - 并且应用不了语义相似度算法，例如：cos相似度等。
词向量
词向量是一个分布式的表示方法，它与ont-hot具有本质区别。
- 词向量表示的优点：
  - 稀疏性降低，向量中的每个元素都不是0，利于学习
  - 词向量的维度远远小于ont-hot
  - 可以应用语义相似度算法，因为稀疏性小
- 词向量是使用深度学习的方法生成的

句子的表示方法

Boolean Representation
- 使用一个向量表示一句话。这个向量的大小为词典大小，当词典中有词出现在句子中，向量在词典中词的位置处为1。没出现的地方为0。
  
  dic = [我们，又，去，爬山，今天，你们，昨天，跑步] content = 我们/今天/去/跑步我们又去爬山今天你们昨天跑步 vector = [1, 0, 1, 0,1,0,0，1]boolean表示法只关心字典中的词在不在句子中。也就是说当一个词在句子中出现了两次，那么对应位置仍写1，因为只关心它出不出现。
Count-based Representation
- 使用一个向量表示一句话。这个向量的大小为词典大小，当词典中有词出现在句子中，向量在词典中词的位置处为这个词在句子中出现的频数。没出现的地方为0。
  
  dic = [我们，又，去，爬山，今天，你们，昨天，跑步] content = 你们/又/去/爬山/又/去/跑步vector = [0, 2, 2, 1, 0, 1, 0, 1]
- 缺点：
  - 不能使用余弦相似度计算。
  - 对于一些频率小的核心词，并不能很好的表示其重要性。
tf-idf（词频-逆向文件频率）
? 对于自然语言而言，并不是每个词出现的频率越大就越好。有的词是出现的越少越好，有的词是出现的越多越没用。所以我们可以使用tf-idf进行句子的向量化。

tf-idf(w) = tf(d, w) * idf(w)tf(d, w):文档d中的w的频数。（和count-based一样） idf(w): log(N / N(w))，它考虑的是单词w的重要性。N表示语料库中的文档数，N(w)表示单词w出现在语料库中的文档数。log是为了防止逆向文件频率过大。tf-idf越小说明单词越重要。文档是怎么样定义的呢？对于问答系统而言，是一句话为单位的，所以一句话就是一个文档对于文本生成而言，例如文章生成，我们是以一篇文章为单位的，所以一篇文章就是一个文档。所以在不同的任务中粒度是不同的

从上面可以看出，tf-idf考虑到了单词在文档中的重要性也考虑到了单词在整个语料库中的重要性。当文档中单词w出现的频数大，而单词的重要性越低tf-idf越大。当文档中单词w出现的频数越小，而单词的重要性越高tf-idf越小。

所以tf-idf表示的句子词向量为： [tf-idf(w1),tf-idf(w2),tf-idf(w3)...]w1,w2等是词典中的词
词向量
除了词向量表示，其他表示方法都是一个稀疏向量，并不好。
怎样使用词向量表示句子向量：
- 平均法
  
  “我们去运动” 我们：a = [0.1, 0.2, 0.1, 0.3] 去：b = [0.3, 0.2, 0.15, 0.2] 运动：c = [0.2, 0.15, 0.4, 0.7]average：(a+b+c)/3 = [0.6/3, 0.55/3, 0.65/3, 1.2/3]
- RNN/LSTM等模型表示句子向量

one-hot:

content = "我们想要去拉萨" # 这里我们使用jieba分词，但是jieba的词库太大了，为了简便，我们使用自定义的词库 # dic为{word: offset},通常我们的词典库都是txt形式的，在读取的时候获取行号就知道word的offset了 dic = {"我们": 0, "想要": 1, "去": 2, "拉萨": 3, "你们": 4, "是": 5, "什么": 6}words = jieba.cut(content) words = torch.tensor([dic[word] for word in words]) # 将词转换为词向量[[word1],[word2]]dic_length = len(dic) line = functional.one_hot(words, dic_length) print("词向量：") print(line) line = line.sum(dim = 0) print("句子向量：") print(line)

词向量： tensor([[1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0]]) 句子向量： tensor([1, 1, 1, 1, 0, 0, 0])

Count-based representation

from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizercorpus = ["我们我们想要去拉萨"] # 由于sklearn主要用于英文，所以用于中文时，需要手动对文本进行空格分词 def cut_words(corpus): result = [] for line in corpus: result.append(" ".join(jieba.cut(line))) return resultcorpus = cut_words(corpus) dic = {"我们": 0, "想要": 1, "去": 2, "拉萨": 3, "你们": 4, "是": 5, "什么": 6}# 定义一个CountVectorizer，并定义了规则。 # vocabulary：定义词典，定义了后就会根据词典生成向量。 # lowercase：大小写，默认为True，因为用于中文所以关闭。 # token_pattern：token解析规则，是个正则表达式，根据解析规则选择词是否被解析。默认正则会过滤掉单字符词，因为通常在英文中一个字符的词是不重要的，而中文不一定，所以我们需要重新定义正则。 vector = CountVectorizer(vocabulary=dic, lowercase=False, token_pattern="(?u)\\b\\w+\\b") # 解析文本 result = vector.fit_transform(corpus)# 输出向量 print(result.toarray()) # 输出特征 print(vector.get_feature_names())

[[2 1 1 1 0 0 0]] ['我们', '想要', '去', '拉萨', '你们', '是', '什么']

tf-idf

from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizercorpus = ["我们我们想要去拉萨", "我们是", "你们去"] def cut_words(corpus): result = [] for line in corpus: result.append(' '.join(jieba.cut(line))) return resultcorpus = cut_words(corpus) dic = {"我们": 0, "想要": 1, "去": 2, "拉萨": 3, "你们": 4, "是": 5, "什么": 6}vectorizer = TfidfVectorizer(vocabulary=dic, lowercase=False, token_pattern="(?u)\\b\\w+\\b") result = vectorizer.fit_transform(corpus) print(result.toarray())

[[0.68770286 0.45212331 0.34385143 0.45212331 0.0. 0.] [0.60534851 0.0.0.0.0.79596054 0.] [0.0.0.60534851 0.0.79596054 0. 0.]]

计算相似度的方法

欧式距离
- 使用欧氏距离表示两个词或两个向量表示
- distance = sqrt[(x1-y1)^2 + (x2-y2)^2 + (x3-y3)^2]。
- [x1,x2,x3]为一个词的向量表示，[y1,y2,y3]为另一个词的向量表示。
- 缺点：这种计算方法考虑不到方向。但是向量是有方向的。
余弦相似度
- distance = x1*y1+x2*y2+x3*y3 / (sqrt(x1^2+x2^2+x3^2)+sqrt(y1^2+y2^2+y3^2))
  
  x1*y1+x2*y2+x3*y3 为向量内积 (sqrt(x1^2+x2^2+x3^2)+sqrt(y1^2+y2^2+y3^2)) 为向量模相加向量模相加相当于normalization

欧式距离：

def distance(x1, x2): return ((x1 - x2) ** 2).sum().sqrt()x = torch.tensor([1,2,3], dtype=torch.float32) y = torch.tensor([1,1,5], dtype=torch.float32) distance(x, y)

cos距离：

def distance(x1, x2): return ((torch.matmul(x1, x2)) / (torch.matmul(x1, x1).sqrt() + torch.matmul(x2, x2).sqrt()))x = torch.tensor([1,2,3], dtype=torch.float32) y = torch.tensor([1,1,5], dtype=torch.float32) distance(x, y)

问答系统搭建
问答系统的复杂度：对于用户提出的一个问题，首先进行分词O(m^2)（m为问题长度），然后向量化O(1)（我们已经有词向量库直接检索就可以），最后与知识库中的问题进行相似度匹配O(n*相似度算法的时间复杂度)（n为知识库大小）
通常我们的知识库是非常大的，所以在检索的时候会消耗大量的时间，并不能实时进行回答。
层次过滤思想我们可以使用层次过滤的思想对知识库中的句条进行过滤，最后得到少量的词条后，我们再使用相似度算法进行匹配

文章图片

值得注意的是！我们过滤器1算法的复杂度要小，过滤器2算法的复杂度要比1大比相似度算法小。这样过滤器1进行简单初步筛选，过滤器2进行简单精细筛选。整个检索的时间复杂度会降低很多。
倒排表 Inverted Index（过滤器）我们的过滤器怎么设计呢？我们可以使用倒排表作为过滤器。
倒排表是搜索引擎中的一个核心，在这里我们将倒排表用于过滤句条。例如我们输入的问题是我们今天运动了吗?，那么就需要搜索 “我们” 在哪些句条中出现过。因为我们的简单过滤肯定是如果一个单词在句条中出现了，那么我们这个句条就与我们的问题具有一定的相关性，所以我们需要过滤出来。

句条1：我们今天运动了吗？句条2：我们昨天运动句条3：你们上课句条4：你们上什么课词典：[我们，你们，今天，昨天，运动，上，课，什么，吗]我们扫描所有句条，然后构成一个倒排表 { 我们:[句条1，句条2]，你们:[句条3，句条4] ....... }这样我们的输入：我们今天运动了吗过滤后句条 = set(倒排表[我们] + 倒排表[今天] + 倒排表[运动] + 倒排表[了] + 倒排表[吗]) = (句条1，句条2)

这里的倒排表只看一个词，所以我们得到的词条只与我们的问题有简易相关性（当知识库中的句条与我们的问题匹配的词越多说明相关性越强），假如第一步过滤得到的词还是太多，我们可以使用两个词作为倒排表的索引。这样过滤出来的句条更精确。
简单问答系统实现

import json from tqdm import tqdm import re from datetime import datetime import jieba from gensim.models import Word2Vec from gensim import utils import numpy as np

1.读取并处理语料库

QA_file = "Project1/data/train.txt" stop_words_path = "StopWords/baidu_stopwords.txt"# 加载停用词库，在构造QA数据的时候就将其过滤掉 def get_stop_words(file_path): with open(file_path, 'r', encoding='utf-8') as file: stop_words = [line.strip() for line in file.readlines()] return stop_words# 该文件中有跟多个json，每行一个。所以我们需要将每个json拿出来存到列表中。 def read_file_as_json(file_path): content = [] with open(QA_file, 'r', encoding='utf-8') as file: while True: line = file.readline() if not line: break line = line.replace(' ', '').replace('\r', '').replace('\n', '') dic = json.loads(line) content.append(dic)return content# 解析json，将对话存储起来，因为这个数据集有些内容并不需要，所以我们需要过滤出我们需要的东西 # 存储形式为 {Q:A, Q:A......} def parse_json(json_list, stop_words): QA = {} for j in json_list: QAS = j['conversation'] for i in range(len(QAS) - 1): if i % 2 == 0: k = re.sub('\[.*?\]', '', QAS[i]) v = re.sub('\[.*?\]', '', QAS[i + 1]) k_str, v_str = '', '' # 过滤停用词 for k_w in jieba.cut(k): if k_w not in stop_words: k_str += k_w for v_w in jieba.cut(v): if v_w not in stop_words: v_str += v_wQA[k_str] = v_strwith open('QA.json', 'w') as file: json.dump(QA, file)stop_words = get_stop_words(stop_words_path) json_list = read_file_as_json(QA_file) parse_json(json_list, stop_words_path)

2.读取JSON数据

def read_qa_json(file_path): with open(file_path, 'r') as file: qa = json.load(file) return qaQA = read_qa_json('QA.json')

3.构建倒排表

# 倒排表是一个{w:(Q1,Q2...), ...}的形式，因为我们的知识库是{Q:A, ...}的形式 def create_inverted_list(QA): print("开始构建倒排表...") start = datetime.now() inverted_list = {}for Q in tqdm(QA): q_words = jieba.cut(Q) for word in q_words: if word in inverted_list: inverted_list[word].add(Q) else: inverted_list[word] = set([Q])print("构建结束。耗时：{} ms".format((datetime.now() - start).seconds * 1000)) return inverted_listinverted_list = create_inverted_list(QA)

4.根据我们的corpus训练词向量，使用word2vec

# 对于word2vec而言，它的模型输入是一个 [[word1, word2...]->sentence1, []]->corpus # 并且由于我们的问答系统只需要看用户问题与知识库中的问题的相似度即可，并不需要关注答案的相似度，所以我们不需要对答案的语料进行词向量的训练 class MyCorpus(): def __init__(self, QA): self.QA = QAdef __iter__(self): for k in self.QA: yield list(jieba.cut(k))sentences = MyCorpus(QA) # model = Word2Vec.load('QA_word.model') model = Word2Vec(sentences, min_count=1, compute_loss=True, sg=1, hs=0, alpha=1e-2, iter=20, batch_words=100) print(model.get_latest_training_loss()) # 保存模型 # model.save("QA_word.model")

5.通过倒排表进行过滤

def inverted_filter(content, inverted_list, stop_words): words = jieba.cut(content) sentences = [] for word in words: if word not in stop_words: sentences.extend([*inverted_list[word]]) print("len sentences: {}".format(len(sentences))) return sentences

6.转换成句子向量

def sentence2vector(sentence, wv, stop_words): words = jieba.cut(sentence) sentence_v = 0 for i, word in enumerate(words): if word not in stop_words: sentence_v += wv[word] return sentence_v / (i + 1)

7.计算相似度

def cos_similary(vec1, vec2): return np.dot(vec1, vec2) / (np.sqrt((vec1 ** 2).sum()) + np.sqrt((vec2 ** 2).sum()))

8.查找知识库中相似度最高的句子

question = "好久没吃肉了呢" question_v = sentence2vector(question, model.wv, stop_words)# 通过倒排表过滤 sentences = inverted_filter(question, inverted_list, stop_words) print("过滤后有 {} 条数据".format(len(sentences)))mini_q, mini_v = "", float('inf') for sentence in sentences: vec2 = sentence2vector(sentence, model.wv, stop_words) similary = cos_similary(question_v, vec2) if mini_v > similary: mini_q, mini_v = sentence, similaryprint("最相似的问题是：" + mini_q) print("回答为：" + QA[mini_q])