贪心NLP刷课笔记(一)

基础概念

自然语言处理技术

四个维度

  • Semantic 语义
  • Syntax 句子结构
  • Morphology 单词
  • Phonetics 声音

上面四个维度是自订而底的,核心为前三类:Morphology关注的是分词,pos(词性)和NER等基础技术,我们要做到顶层的可用性,其底层至少需要达到某个阈值;Syntax关注的是句法分析(提取特征;有一个算法为CYK,是一个根据动态规划的算法)、依存分析(Dependence,分析每个词之间有什么关系,可以分析单词之间潜在的联系,可作为特征);语义分析为最终的目标,是最上层的生态。

基本问题

NLP的问题可以分为三大类:第一类是基本解决的问题:Spam detection, 命名实体识别等为简单的问题,基本可以保证准确率95%以上,第二类是比较难的算法,比如:Coreference resolution, Word sense disambiguation, Parsing, Machine Translation, Information Translation,第三类是很难的且需要花费较多时间的工作,比如文本摘要与对话系统。

4P

咳这个不是多人运动,这里讲的是P, NP, NP Hard和NP Complete,我们一般来说,可以将算法复杂度分为指数级复杂度$O(p^n)$与多项式级复杂度$O(n^p)$,只要是多项式级复杂度,我们都可以将其理解为可解决的问题,而指数级复杂度我们一般认为是不可解决的问题(量级很小仍可以解决),但我们可以提出一个近似算法,其复杂度为$O(n^p)$可以得到一个近似解(不能保证得到精确解),我们仍可以认为其是近似可以解决的(当然未来也可以使用量子计算机)。

上面的多项式级的复杂度我们称为P问题,指数级复杂度为NP Hard或者NP Complete问题,其中NP Complete问题是NP Hard问题的子集(这两者较难区分这里不详述),NP的意思是可以在多项式复杂度内能验证的问题。

基于搜索的问答系统

首先我们有一个知识库(问题答案对),预处理环节我们对用户提出的问题先做分词处理,然后做拼写纠错,然后将所有的语态转化为相同的语态(比如went和going转为go),这是Stemming环节,然后就是停用词过滤以及无用单词的过滤(Word Filtering),最后还可以考虑同义词替换。接着我们可以将用户提出的问题转换为向量表示(boolen vector——>count vector——> tf-idf——>Word2Vector——> Seq2Seq),转换完向量后我们就需要计算相似度(可以使用欧氏距离,Cosine距离或其他距离公式),然后按照相似度距离排序,获得最终结果,排序完之后也可能再进行最后一轮的过滤。如果文本数量太多可以通过建立倒排表降低时间复杂度加速过程。

NLP项目Pipeline

下图为NLP项目的Pipeline:

下面介绍的前两个流程涉及的算法较多,后两个算法较少。下面分别进行介绍:

预处理

Word Segmentation

常见的分词工具有Jieba分词,SnowNLP,LTP,HanNLP,目前较常用的是Jieba分词工具,Python调用直接impor jieba即可,可以通过cut语句切分,可以通过add_word函数加入希望其识别的专有名词,此时不会对其做切分。

前向最大匹配(forward-max matching)

首先我们举例:我们经常有意见分歧。我们第一步建立词典:[“我们”,”经常”,”有”,”有意见”,”意见”,”分歧”],我们匹配方式是将整个句子不断剪掉后面的单词,然后匹配词典中的单词,最终得到的分词结果是:[“我们”,”经常”,”有意见”,”分歧”],这种匹配法会尽量匹配更多的字符。这是一个贪心的算法。

顺便提一句,算法分为贪心算法和DP算法,其中贪心算法是寻找当前最优的,DP算法近似寻找全局最优,可以考虑全局信息。

后向最大匹配(backward-max matching)

过程与前向最大匹配类似,首先设置max-len=5,先考虑”有意见分歧“,发现不在词典里,我们缩减单词为“意见分歧”,逐步这样炒粉得到”分歧“为词典中的单词,最终这个例子我们得到的结果与前向最大匹配得到的结果一样,当然有时候这两个匹配方式得到的结果不一样(但机率很低)。结合这两个匹配方式就得到了双向匹配,也就是结合前向最大匹配和后向最大匹配 。

上面的分词方法的缺点:

  1. 无法对词进行细分,当我们遇到细分后单词可能为更好的单词时就不太准确;
  2. 考虑的是局部最优而不是全局最优;
  3. 效率受到Max-len影响
  4. 不能考虑到语义信息

最大匹配算法只能看到我们前面说到的单词信息,是最简单的模型,而考虑不到语义和句子结构的信息。但我们考虑到这两个信息之后当然我们的复杂度也会随之提高。因此我们可以先试验简单地分词方法,效果还不错的话我们可以再提升为更复杂的模型(考虑到语义信息)。

Incorporate Semantic(考虑语义)

我们希望有一个工具,能够将句子传入,返回一个语义的概率(不同分词法的概率),然后选取概率高的分法即可。也就是我们输入句子,根据词典库生成所有可能的分割,在其中选择最好的。

我们有一个工具(Language Model),最简单的算法就是根据条件概率假设(所有词出现概率不相关),将句子概率分解成单词的概率乘积,也就是:

由于上面的计算中每个概率值都很低(在一个语料库中每个单词出现的次数都比较少),我们计算乘积时一般会计算$\text{log}P(\text{经常,有,意见,分歧})$,然后将取log之后的结果累加即可。由于$\text{log}$函数时严格递增的,因此可以保证比较是等同的,有时候我们也会加平滑项,这里先不讲。上面的计算方法是Unigram方法,我们当然还可以考虑两个或更多单词的联合概率分布。

我们前面考虑的是先列出所有可能,然后找到其中最好的(概率最高的),我们可以将这两个步骤合并起来做优化,也就是我们常说的维特比算法(也是DP算法)。首先我们计算出每个分词的负log概率,如下:

词典 经常 有意见 意见 分歧 见分歧
概率 0.1 0.05 0.1 0.1 0.2 0.2 0.05 0.05 0.05 0.1
-log(x) 2.3 3 2.3 2.3 1.6 1.6 3 3 3 2.3

可以转化为下图:

我们可以将分词目标转化为最小路径(路径为-log(x)),我们只需要找到最短的从第一个单词经过所有单词(按次序)直到最后一个单词的路径即可。我们定义$f(n)=\text{从节点1到节点n的最短路径的值}$,这个过程我们完全可以通过递归实现,但我们可以想道斐波那契数列用这种方法来计算的话会很浪费计算资源,我们可以维护一个$f(n)$数组来简化运算。其中$f(1)=0,f(2)=3,f(3)=2.3$等等得到第一个节点到最后一个节点的最短路径值,同时也可以得到其路径(需要反推 ),读者不妨自己推一下,最终我们得到最优路径为1——>3——>6——>8(上面的概率是随意取的不代表真实概率 )。具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys
import numpy as np

sys.setrecursionlimit(9000000)
## 请编写word_segment_viterbi函数来实现对输入字符串的分词

def word_segment_viterbi(input_str):
"""
1. 基于输入字符串,词典,以及给定的unigram概率来创建DAG(有向图)。
2. 编写维特比算法来寻找最优的PATH
3. 返回分词结果
"""
if len(input_str) == 0:
return 0

# 第一步: 构建图
n = len(input_str)
path = np.zeros([n+1,n+1])

for i in range(n):
if input_str[i] in word_prob:
path[i,i+1] = word_prob[input_str[i]]
elif input_str[i] in dic_words:
path[i,i+1] = 0.00001
for j in range(i+1,n+1):
if input_str[i:j] in word_prob:
path[i,j] = word_prob[input_str[i:j]]
elif input_str[i:j] in dic_words:
path[i,i+1] = 0.00001


# 第二步: 利用维特比算法来找出最好的PATH, 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。
# hint: 思考为什么不用相乘: p(w1)p(w2)...而是使用negative log sum: -log(w1)-log(w2)-...
minPath = np.zeros(n+1)
score = [sys.maxsize]*(n+1)
score[0] = 0
seg = []
for i in range(1,n+1):
p = 0
for j in range(0,n):
if path[j,i] != 0:
if score[i] > -np.log(path[j,i])+score[j]:
score[i] = -np.log(path[j,i])+score[j]
minPath[i] = j

# 第三步: 根据最好的PATH, 返回最好的切分

i = n
while i > 0:
seg.append(input_str[int(minPath[i]):i])
i = int(minPath[i])
seg = seg[::-1]
return seg

Spell Correction

由于用户输入内容可能错误,我们需要有一个算法可以将错误的输入修改为正确的,这里有一个重要的概念是编辑距离。错误的输入可能是错别字,而有些则可能是输入的词不适合,这里可以使用语言模型来纠正。

编辑距离是两个字符串的距离有多长(要多少个操作才能转换为目标字符串),我们以therr这个错误拼写为例求得以下编辑距离:

目标单词 there their thesis theirs the
编辑距离 1 1 3 2 2

而我们具体要返回哪个词需要根据上下文(结合语义)来判断,而计算编辑距离我们会使用DP算法。

最笨的选择方法就是遍历词典库的所有单词,然后选择其中编辑距离最小的(实际上就是ASM近似串匹配算法),编辑距离的DP算法如下 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def normal_leven(str1, str2):
len_str1 = len(str1) + 1
len_str2 = len(str2) + 1
# 创建矩阵
matrix = [0 for n in range(len_str1 * len_str2)]
# 矩阵的第一行
for i in range(len_str1):
matrix[i] = i
# 矩阵的第一列
for j in range(0, len(matrix), len_str1):
if j % len_str1 == 0:
matrix[j] = j // len_str1
# 根据状态转移方程逐步得到编辑距离
for i in range(1, len_str1):
for j in range(1, len_str2):
if str1[i - 1] == str2[j - 1]:
cost = 0
else:
cost = 1
matrix[j * len_str1 + i] = min(matrix[(j - 1) * len_str1 + i] + 1,
matrix[j * len_str1 + (i - 1)] + 1,
matrix[(j - 1) * len_str1 + (i - 1)] + cost)

return matrix[-1] # 返回矩阵的最后一个值,也就是编辑距离

str1='谁是谁的谁的谁'
str2='你爱我们谁的是'

a=normal_leven(str1, str2)
print(a)

另外一种简洁写法:

1
2
3
4
5
6
7
8
9
10
11
def edit(str1, str2):
matrix = [[i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]
for i in range(1, len(str1) + 1):
for j in range(1, len(str2) + 1):
if str1[i - 1] == str2[j - 1]:
d = 0
else:
d = 1
matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + d)

return matrix[len(str1)][len(str2)]

a=edit(‘谁是谁的谁的谁’,’你爱我们谁的是’)
print(a)

我们可以直接调包:import Levenshtein,使用包中的distance函数计算编辑距离,

实际上我们不必遍历词典选择编辑距离最小的,我们可以反过来,使用用户输入字符串生成编辑距离为1或2的字符串(Replace,Add,Delete),然后过滤后返回结果(不会依赖于词典库大小)。

我们得到了一个备选较小编辑距离字符串集合后,可以通过计算$\hat c=argmax_{c\in condidates}p(c|s)$计算得到最可能成为正确的字符串c。上式可以通过贝叶斯定理稍作转换:

其中$p(s|c)$应理解为对于apple这个正确的单词,有多少用户将apple写程appla(或者之类的),此数据我们可以从历史数据统计得到,而第二项$p(c)$是一个Unigram的概率,可以通过直接统计apple这个单词在所有文章中出现的次数计算得到(偏向于选择更常用的单词)。

Stop Words Removal

对于NLP的应用,我们通常先把停用词、出现频率低的词汇过滤掉,这其实类似于特征筛选的过程。在英文里,“the“,”an“,”their“这些都可以作为停用词来处理(不绝对),需要考虑把自己的应用场景。一般做法是拿别人做好的停用词库然后做一些删改,对于很大文本的项目我们可以将出现次数低于10或20之类的词去掉。

Stemming

词的标准化操作(主要针对英文)有两种常用技术:Stemming和Lemmazation。Stemming不能保证转换出来的单词是正常的英文单词,需要进一步转换,而Lemmazation则比Stemming更严格,可以保证转换出来的单词是一个出现在词库的单词。目前最广泛使用的Stemming操作时Porter Stemmer,其主要分为四个模块:

  • 制定规则,可以将后缀改为我们希望的后缀形式,如sses改为ss,ies改为i,ss改为ss,s直接去掉
  • 修改时态:(v)ing的ing去掉,(v)ed的ed去掉,有些需要特殊处理的,比如sing
  • for long stems:ational改为ate,izer改为ize,ator改为ate
  • for longers stems:去掉al,able,ate等

此过程需要依赖语言学家的经验,由程序员实现。

句子表示

发展

  • boolean:构建词典库通过one-hot表示,向量长度与词典库大小一样。
  • tf-idf:核心方法论为单词并不是出现的越多就越重要,并不是出现的越少就越不重要。计算公式为$tfidf(w)=tf(d,w)*idf(w)$,其中$tf(d,w)$为文档$d$中$w$的词频,$idf(w)=\text{log}\frac{N}{N(w)}$,$N$为语料库中的文档总数,$N(w)$为词语$w$ 出现在多少个文档。 也就是一个单词如果每个文档都出现了,tfidf值会很低,相反一个单词只出现少数几个文档中,在这里个文档中这些个单词的重要性一定是比较高的。
    • 但无论是Boolean方法还是tf-idf均无法通过欧氏距离体现单词的相似性,计算余弦相似度很多都是0,也无法体现单词相似性
    • 上面两个方法的稀疏性(Sparsity)很高
  • Word2Vec:分布式表示法,能体现单词语义,稀疏度低

Word2Vec

训练时输入为一个很长的字符串,当我们有一篇文章时可以直接将其拼接起来得到一个字符串进行训练,一般需要10亿或100亿个单词的语料库,数据很少时训练出来的结果不准确。训练词向量的主要方法有Skip-Gram,Glove,CBOW,RNN,LSTM,MF,Gaussian Embedding等,训练时最重要的参数为希望训练得到词向量的维度。

实际上我们不需要自己训练词向量,可以直接调用。但有些垂直领域需要自己训练词向量,比如金融领域和医疗领域等等,需要根据特定的语料库进行训练。

词向量某种程度上代表了单词的意思,那么当我们训练得到了一个词向量,对于一个句子我们该如何得到他的意思呢?这里主要有两种方法:

  • 平均法
  • LSTM/RNN

加速方式(倒排表)

用户输入了一个问题,我们首先要匹配到知识库中的问题集,计算其相似度,返回其中最匹配的问题,其时间复杂度为$O(n)$,计算量很大。我们先讨论解决这个问题的思路——”层次过滤思想“

我们不需要计算所有问题集与用户输入的问题的余弦相似度,可以通过简单的方法层层过滤,最终得到较低数量级的备选问题得到较少的新备选问题集。我们需要保证:复杂度(过滤器1)<复杂度(过滤器2)<…….<复杂度(过滤器N)。过滤的方式我们通常会使用倒排表来做。

比如我们文档中有如下关键词:

文档 Doc1 Doc2 Doc3 Doc4
关键词 我们,今天,运动 我们,昨天,运动 你们,上,课 你们上什么课

我们可以构建以下词典:[我们,今天,运动,昨天,上,课,什么],然后给每个词标注所在的文档:

单词 文档
我们 Doc1,Doc2
今天 Doc1
运动 Doc1,Doc2
昨天 Doc2
Doc3,Doc4
Doc3,Doc4
什么 Doc4

当我们输入我们”运动“,就可以直接返回Doc1与Doc2,我们输入“我们上课”时,由于两个单词没有交集,我们就可以采用并集操作得出结果。我们的过滤器就可以由倒排表的一系列规则组合而成,比如最低层的倒排表过滤结果可以是包含问句中所有单词中任意一个的返回结果,而层数越高则需要的规则也就越苛刻,比如需要包含更多的单词。

语言模型

Noisy Channel Model

上面这个公式只需要简单地应用贝叶斯公式就可以得到,这个公式看起来简单,应用场景却很多,语音识别、机器翻译、拼写纠错、OCR、密码破解等领域都用到了这个公式。其共同点都是要将一段信号转换为一个文本。

机器翻译:$\text{P(中文|英文)}\text{~}\text{P(英文|中文)}*\text{P(中文)}$,其中$\text{P(英文|中文)}$为Translation模型,$P(\text{中文})$为语言模型

拼写纠错:$\text{P(正确的写法|错误的写法)}\text{~}\text{P(错误的写法|正确的写法)}*\text{P(正确的写法)}$

语音识别:输入为波形,希望将波形转为文本。$\text{P(文本|语音信息)}\text{~}\text{P(语音信息|文本)}*\text{P(文本)}$

密码破解:输入encrypted string,转为可读的字符串。$\text{P(明文|暗文)}\text{~}\text{P(暗文|明文)}*\text{P(明文)}$

语言模型的作用就是保证转化后的信号是符合常理的,将判断一句话从语法上是否通顺(是否是人话)。

Markov Assumption

我们在计算一个语言模型的时候,首先考虑到的就是使用整个句子除了最后一个单词的所有单词来预测这个句子发生的概率,举个例子我们要预测今天是春节,我们都休息这句话的概率,那么我们会计算$P(休息|今天,是,春节,我们,都)$,我们可以想到在一个语料库中出现这样句子的概率肯定是极低的,因此我们会使用到Markov假设, 将上面这个条件概率简化为$P(休息|都)$这里使用的是1st order markov assumption,我们当然也可以使用2rd order……,根据自己的需要调整即可,但需要注意到的是随着加入单词的长度越多概率会越低。再举个例子:

比较今天是周日与今天周日是这两个句子的概率:

我们使用不同的order,就可以得到N-gram的语言模型,其中Unigram就是不考虑前后文信息,无法分析单词依赖性,我们最常用的还是Bigram的语言模型。

平滑项

往往我们的概率值某一项是0,此时会导致整个句子的概率为0,为了避免这种情况发生,我们需要在每次计算概率的时候加一个平滑项,一般来说,语言模型的平滑处理可分为以下三类:

1
2
3
Discounting(折扣):通过给概率不为0的项打折扣,来提高概率为0的项的概率;
Interpolation(插值):在使用N-gram模型计算某一项的概率时,同时结合低阶的模型所计算出的概率;
Back‐off:approximate counts of unobserved N‐gram based on the proportion of back‐off events (e.g., N‐1 gram)。

Discounting

Discounting 包括 Add‐One Smoothing、Add‐K Smoothing、Good-Turing Smoothing等。

Add‐One Smoothing

假设N为语料中的单词个数,V为词典中单词的个数,那么对于Unigram和Bigram模型,平滑处理后计算每一项概率的公式为:

  • Unigram case:$P_{L}(w_i) = \frac{count(w_i)+1}{N+V}$
  • Bigram case:$P_L(w_i|w_{i-1})=\frac{count(w_iw_{i-1})+1}{count(w_{i-1})+V}$

举例来说,假设使用Bigram模型,$V=20,count(我们)=3,count(我们,是)=0$。若不使用平滑处理,则$P(是|我们)=0$;若使用上述处理,则$P(是|我们)=(0+1)/(3+20)=1/23$。

Add‐K Smoothing(Laplace Smoothing)

对于这种方式,有$P_L(w_i|w_{i-1})=\frac{count(w_iw_{i-1})+K}{count(w_{i-1})+KV}$。可以看出,Add‐One Smoothing就是$K=1$的情况。
在使用Add‐K Smoothing的时候,可以使用优化的方法来寻找最佳的$K$。具体来说,先计算文本的perplexity,由于perplexity是关于$K$的函数,因此通过优化得到最小的perplexity时也同时得到了最佳的$K$。

Good-Turing

Good-Turing技术是在1953年由古德(I.J.Good)引用图灵(Turing)的方法而提出来的,其基本思想是用观察计数较高的N元语法数重新估计概率量的大小,并把它指派给那些具有零计数或者较低计数的N元语法,具体使用公式如下:

其中,$c$代表某个单词出现的频数,$N_c$代表出现$c$次的单词的个数,而$c^∗$是频数为$c$的单词经过Good-Turing处理后的新的频数。例如,在某个语料库中,单词“love”出现了20次,而出现20次的单词共有100个,经过处理后,这100个出现过20次单词的频数可能变成18.2。

Interpolation:

Interpolation 包括 Linear Interpolation等。这种方式的思路为:在使用N-gram模型计算某一项的概率时,同时结合低阶的模型所计算出的概率。 以Trigram模型来说,使用interpolation方式后,计算每一项的概率公式为:

其中$\lambda_1+\lambda_2+\lambda_3=1$,其核心思想是:现在没有出现不代表未来不会出现

评估语言模型

评估语言模型的核心思路是做填空题,我们给定第一个单词让语言模型预测下一个单词,如此往复可以评估出语言模型的效果如何,其中的评估方法为Perplexity:Perplexity$=2^{-x},x:\text{average log likehood}$,我们训练语言模型的时候自然会希望$x$越小越好,于是Perplexity越小越好,因此我们训练出来的Perplexity应该是不断下降的,最后达到一个均衡值。Perplexity之于我们目前的训练目标就如同召回率精确率之于推荐系统,后面根据不同的任务还有不同的评估方法,但Perplexity是其中很重要的一个评估方法。

N-gram Order Unigram Bigram Trigram
Perplexity 962 170 109
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

扫一扫,分享到微信

微信分享二维码
  • Copyrights © 2020-2021 chenk
  • 由 帅气的CK本尊 强力驱动
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信