NLP复习大纲_nlp 复习

第一章：概述

1. 什么是自然语言处理？

计算机具备人类的听、说、读、写、译、问、答、搜索、摘要、对话和聊天等能力

知识和常识进行推理和决策

支持客服、诊断、法律、教学等场景

2. 自然语言处理的主要任务有哪些？

分析、理解、转换、生成

1. 转换：

• 翻译 • 运用翻译规则或统计模型等，将源语言的文本转换为目标语言的文本
• 文摘 • 对源语言的长文本进行压缩，提取出关键句子的短文本

2. 生成

• 自动作文 生成符合逻辑的连贯的文本
• 聊天对话生成 模拟人类生成对话

3. 自然语言存在的难点？

词汇句法方面的问题尚未解决，已开始挑战语义、知识、推理等深层课题

1. 注音歧义 --针对单字
2. 语音歧义 --针对句子
3. 分词歧义 --中文；英文介词的分割
4. 修饰歧义
5. 句法歧义
6. 篇章歧义 --文章上下文语境
7. 语义歧义 --针对单字
8. 病构——真实文本的语言现象很复杂，不规范，不干净

• 未登录词
• 已知词的新用法（有事微信我
• 不合乎语法的句子

9. 重述
10. 层间循环依赖问题

• 高层模块-需要-底层模块分析
• 底层模块-需要-高层模块的指导

第二章：文本处理基础

1. 会写正则表达式

中括号内表示匹配任意字符

"[wW]"
#匹配w或W

"[abcd]"
#匹配abcd
# 等价于[a-d]
1
2
3
4
5
6

^且方框中,放在字符最前端，表示“非” —— 非后面的字符开头
（不是字符最前端则视为匹配^本身）

"[^wW]"
#匹配不是w或W开头的字符串

如Wwthie，返回Ww后面的第一个字符，t

1
2
3
4
5

^且方框[]外，表示以[]里面的字符开头

'^[A-Z]'
# start with a capital letter

'^[^A-Za-z]' 
# not start with a capital letter

1
2
3
4
5
6

$表示以前面字符结尾

\.$ 
# ending with .

.$ 
# ending with any character
1
2
3
4
5

• ? 前置字符出现0次或1次
• * 前置字符出现0次或多次（包括一次）
• + 前置字符出现1次或多次
• . 匹配任意一个字符(只出现一次，多了少了都不行)

没有括号内外区别

分组

要使析取运算符仅适用于特定模式，我们需要使用括号运算符。将模式括在括号中，使其在相邻操作符中充当单个字符

语法：

1. 优先级由高到低
2. 匹配选择贪婪策略 —— [a-z]*，0次或者多次，然而，正则表达式
   匹配最大字符串。

捕获组

（）捕获组

r=r"(\d{4})-(\d{2})-(\d\d)"
p=re.compile(r)
print(p.match('2008-12-03').group())
print(p.match('2008-12-03').group(1))
print(p.match('2008-12-03').group(2))
print(p.match('2008-12-03').group(3))
# 2008-12-03 2008 12 03

1
2
3
4
5
6
7
8

（？P）命名捕获组

p = re.compile(r'(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d\d)')
match=p.match('2008-12-03-2009')
print(match.group("year"))
print(match.group("month"))
print(match.group("day"))
# 2008 12 03
1
2
3
4
5
6

（?:） 匹配pattern，但不捕获匹配结果

pattern = r"(?P<python>123)(?:456)(789)"
string = "123456789"
match = re.match(pattern,string)
if match:
print(match.group("python"))
print(match.groups())
# 123 ('123', '789')
1
2
3
4
5
6
7

（?=）匹配后面跟的是pattern的内容，不匹配pattern

s="windows2019windows2018windows1989"
res=re.sub("windows(?=2018|1989)","microsoft",s)
print(res)
# windows2019microsoft2018microsoft1989
# 匹配的前面改，后面的不捕获
1
2
3
4
5

（?<!）匹配后面跟的不是pattern的内容，不匹配pattern

s="windows2019windows2018windows1989"
res=re.sub("windows(?!2018|1989)","microsoft",s)
print(res)
# microsoft2019windows2018windows1989
1
2
3
4

(?<=pattern) 匹配前面是pattern的内容，不匹配pattern

s="windows2019microsoft2019windows1989"
res=re.sub("(?<=windows)2019","pattern",s)
print(res)
# windowspatternmicrosoft2019windows1989
1
2
3
4

(?<!pattern) 匹配前面不是pattern的内容，不匹配pattern，

s="windows2019microfost2019"
res=re.sub("(?<!microfost)2019","pattern",s)
print(res)
windowspatternmicrofost2019
1
2
3
4

给定字符串会写程序返回查询结果

3. 会写正向、逆向和双向匹配程序

正

def forward_match(st, dic, max_len):
    div_res = []
    location = 0
    while location < len(st):                       # 遍历整个字符串
        longest_word = st[location]         
        for i in range(location + 1, len(st) + 1):  # 在不超MAX_LENGTH的情况下往后加单个字符判断是否满足要求
            temp_word = st[location : i]
            if len(temp_word) > max_len:        
                break
            if temp_word in dic:
                if len(temp_word) > len(longest_word):
                    longest_word = temp_word
        div_res.append(longest_word)                # 加入结果
        location += len(longest_word)
    return div_res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

逆

def backward_match(st, dic, max_len):
    # 本质就是前缀反过来
    div_res = []
    location = 0
    st = st[::-1]
    while location < len(st):           #原理同forward，在处理过程中需要加入reverse操作来保证语义通顺
        longest_word = st[location]     #不加的话从右往左看其实也是可以的
        for i in range(location + 1, len(st) + 1):
            temp_word = st[location : i]
            if len(temp_word) > max_len:
                break
            temp_word = temp_word[::-1]
            if temp_word in dic:
                if len(temp_word) > len(longest_word):
                    longest_word = temp_word
        div_res.append(longest_word)
        location += len(longest_word)
    div_res.reverse()
    return div_res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双

def bidir_match_1(st, dic, max_len):
    fm = forward_match(st, dic, max_len)
    bm = backward_match(st, dic, max_len)

    lenf = len(fm)                              # 分词数量
    lenb = len(bm)
    singlef = sum(1 for i in fm if len(i) == 1) # 单字数量
    singleb = sum(1 for i in bm if len(i) == 1)
    bigf = sum(len(i)** 1.2 for i in fm)           # 高颗粒度词 给1.2次幂避免权重过大
    bigb = sum(len(i)** 1.2 for i in bm)            

    evaluation_f = bigf - 3 * (lenf + singlef)        # 高颗粒度 - 分词 - 单字作为输出指标
    evaluation_b = bigb - 3 * (lenb + singleb)
    if evaluation_f > evaluation_b:
        return "forward",fm
    else:
        return "backward",bm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

会阅读/根据程序写出分词结果

5. 什么是文本标记化？

将字符序列转换为标记（token）序列的过程。

从输入字符流中生成标记的过程叫作标记化（tokenization），在这个过程中，词法分析器还会对标记进行分类

1. 分句
2. 分词

预处理过程

1. 原始数据文件
2. 非数字字符的符号转化为空，大小写转换
3. 文本标记化 —— 分词
4. 去停用词
5. 词性标注
6. 词干提取/词形还原
7. 统计排序

6. 什么是词干提取？什么是词形还原？有什么不同？

1. 词干提取 - Stemming
   词干提取是去除单词的前后缀得到词根的过程。大家常见的前后词缀有「名词的复数」、「进行式」、「过去分词」

• 抽取词的词干或词根形式
• 不一定能够表达完整语义
• 简单
• 如 leave leav

2. 词形还原 - Lemmatisation
   词形还原是基于词典，将单词的复杂形态转变成最基础的形态。
   词形还原不是简单地将前后缀去掉，而是会根据词典将单词进行
   转换。比如「drove」会转换为「drive」

• 把一个词汇还原为一般形式
• 完整语义
• 复杂 需要词性标注标签
• leave - leaf

第三章：文本分类

1. 随机变量

• 是一个随机实验结果的可能数值
• 随机变量有数值集合……
• 随机变量可以随机地取集合里任何的值，每个值可以有不同的可能性（概率）

2. 极大似然估计

似然估计：
参数估计的方法之一。

• 已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚
• 参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值，
• 似然估计提供了一种区分概率的方法，也是一种在所有可能性中选择单个最佳概率的策略。

选出最有可能的模型
P(X)的极大似然估计；我们观察到的数据（X）是最有可能的概率值

3. 贝叶斯公式

$$P(Y=y|X=x)=\frac{P(Y=y)P(X=x|Y=y)}{{\sum }_{y}P(Y=y)P(X=x|Y=y)}$$

推导
$$P(A|B)=\frac{P(B|A)P(A)}{P(B)}=\frac{P(B|A)P(A)}{P(A)P(A|B)+P(A‘)P(A‘|B)}$$

4. 拉普拉斯平滑

$$P(x_i|y)=\frac{n_{i,y}+a}{n_y+Va}$$

每个样本都+1（不一定是+1，可以自行设置别的数a），然后总样本+n（别的数a对应+na）就是加一平滑 —— laplace的特殊情况

5. 会给定计算一句话计算情感是正向还是负向的概率

记 事件：出现某句话，为B
记 事件他是正向 A
所以就现场推贝叶斯代入计算比较即可

6. 会根据混淆矩阵，计算精确率、准确率和召回率

混淆矩阵

1. TP true positive：认为是正向，并且确实是正向的数量
2. FP false positive：认为是正向，实际是负向的数据
3. TN：认为是负，实际是负
4. FN ：认为是负，实际为正

$$ACC=\frac{TP+TN}{TP+TN+NF+FP}$$
准确率：左上到右下/总和

$$PRE=\frac{TP}{TP+FP}$$
精确率：左上角/上横

$$REC=\frac{TP}{TP+FN}$$
召回率：左上角/左竖

第四章：语言模型

1. 什么是语言模型？

目标：计算一个句子或一系列单词的概率

2. 如何计算语言模型？

链式
$$P(“itswaterissotransparent”)=P(its)\times P(water|its)\times P(is|itswater)\times P(so|itswateris)\times P(transparent|itswaterisso)$$

问题：可能句子太多，无法有重组数据

简化假设 —— 马尔科夫假设
$$P(the|itswaterissotransparentthat)\approx P(the|that)\approx P(the|transparentthat)$$

3. 写出句子的n元文法

类似上文，只不过马尔科夫假设后面，条件概率的条件变为n - 1元 —— 需要注意START的标注

累乘

4. n的选取策略

• n >= 4时数据稀疏和计算代价又变得显著起来，实际工程中几乎不使用

更大的n：对下一个词出现的约束信息更多，具有更大的辨别力

更小的n：在训练语料库中出现的次数更多，具有更可靠的统计信息，具有更高的可靠性

• 经验上，trigram用的最多，尽管如此，原则上，能
  用bigram解决，绝不使用trigram

5. 什么是困惑度，如何计算困惑度？

困惑度Perplexity = 测试数据的逆概率，按词平均

$$per=\sqrt[n]{\frac{1}{P(w_1...w_n)}}$$

一元
$$per=e^{-\frac{1}{N}{\sum }_i^{N}logP(w_i)}$$

三元
$$per=e^{-\frac{1}{N}{\sum }_i^{N}logP(w_i|w_{i-2},w_{i-1})}$$

6. 自然语言处理中N-Gram模型的Smoothing算法有哪些？

1. 数据稀疏
2. 拉普拉斯平滑
3. 加一平滑MLE
4. 回退法和插值法$\lambda p+(1-\lambda )q$
5. Kneser-Ney 平滑

• 当退回到较低阶的n-gram时，可能整体的n-gram频率不是最好的 Francisco这个词出现的频率更高，但出现在较少且独特的bigram组合 (“San Francisco”)中
• 估计一个词在新的序列中出现的可能性有多大

7. Laplace平滑 (add-one, add-α)和回退插值法的主要思想是什么？

前者：平滑是概率量的重新分配 —— 解决零概率的问题
后者：任意两个语言模型p和q(λ∈[0,1])的线性插值也是一个有效的语言
模型 —— 使高阶语言模型更加健壮

第五章：文本纠错

1. 计算两个词的最短编辑距离

DP

DP[i,0] = i
DP[0,j] = j
for i in range(n):
    for j in range(m):
        a = DP[i-1, j] + 1 #增删
        b = DP[i, j-1] + 1 #增删
        c = 0
        if x[i] == y[j]:
            c = DP[i-1, j-1]
        else:
            c = DP[i-1, j-1] + 2 # 替换
        min_num = min(a, b, c)
DP[n, m]是最短距离
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 什么是噪声信道模型

正确的查询通过一个噪声信道传输，在传输过程中受到外界 千扰，导致在信息接收端收到的杳询发生错误

把有噪声的输出信号恢复输入信号

看到一个拼错的单词的观察值x
-》 找出正确的单词w
$$w=argmaxP(w|x)=P(x|w)P(w)/P(x)\approx argmaxP(x|w)P(w)$$

3. 采用噪声信道模型需要的外部资源

一些拼写错误测试集
• Wikipedia’s list of common English misspelling
• Aspell filtered version of that list
• Birkbeck spelling error corpus
• Peter Norvig’s list of errors (includes Wikipedia and
Birkbeck, for training or testing
1
2
3
4
5
6

4. 文本纠错的实现步骤

1. 对句子的单词生成候选词集合
   • 本身
   • 差一个字母的单词
   • 同音词
2. 选择最佳候选词
   • 噪音信道
   • 任务分类器
   • 概率获取依靠：Language mode（n-gram) 或 Channel model（信道概率）

• 给定一个句子w1,w2,w3,…,wn
• 对每个词wi生成候选词集
• 选择使P(W)最大化的序列W （在所有可能的句子中替换一个词）

EXAMPLE：

1. 建立词典库
2. 对于词库里没有的词，根据编辑距离生成候选词集合
3. 下载spell-errors.txt，计算p（x|w）
4. 计算句子中候选词的Unigram（p(w)），Bigram(p(w|w1))概率，注意平滑
5. 选出概率和最高的候选词，作为修改词

第六章：词的语义表示：

1. 什么是词嵌入？

把词映射为实数域上向量的技术

1. one-hot表示
2. 分布式表示 不同的方式对“公司”（或上下文）的概念进行编码。
   • 词项-文档
   • 词项-上下文矩阵

2. One hot 编码的不足？

• 会产生大量冗余的稀疏矩阵
• 没体现维度（单词）间的关系

3. 如何计算TFIDF

针对 词项-文档矩阵

TF:即一个词在文中出现的次数

计算 词语t 出现在文档d中的次数
$$t{f}_{i,j}=\frac{n_{i,j}}{{\sum }_k{n}_{k,j}}$$
IDF：逆文档频率，一个词在若干文档中出现。出现的文档数越少，值越大
i d f i = l o g ∣ D ∣ ∣ { d : t i ∈ d } ∣ idf_i = log\frac{|D|}{|\{d:t_i\in d\}|} idfi​=log∣{d:ti​∈d}∣∣D∣​

两者相乘为TF-IDF

4. 如何计算PMI和PPMI

Pointwise mutual information
x和y这两个词在一起出现的次数比它们独立出现的次数多吗？
$$PMI(X,Y)=lo{g}_2\frac{P(x,y)}{P(x)P(y)}$$

PPMI (Positive PMI between two words):

• 将所有小于0的PMI值替换为零

矩阵中计算
为

$$P(i,j)=f(i,j)/[\sum f(i,n)+\sum f(n,j)]$$
【就是（交点）除以（竖之和加横之和）

$$P(i)=\sum f(i,n)/[\sum f(i,n)+\sum f(n,j)]$$

(横之和)/（竖之和加横之和）

$$P(i)=\sum f(n,j)/[\sum f(i,n)+\sum f(n,j)]$$
算出P(i,j),P(i),P(j)代入上式PMI

5. 计算词语之间的余弦相似度

$$cos(v,w)=\frac{v\ast w}{|v||w|}=\frac{\sum v_i{w}_i}{\sqrt{v_i^2}\sqrt{w_i^2}}$$

• -1: 向量指向相反的方向
• +1: 向量指向同一个方向
• 0: 向量正交

原始频率或PPMI为非负，因此余弦
范围为0-1

6. CBOW和Skip-Gram相同和不同之处

Skip-gram:基于目标词预测上下文

• 以这个句子中的某个词作为训练输入 比如orange，通常把这样的词叫做中心词(center word)
• 以这个词周围的词作为训练标签 比如juice，也叫做上下文词(context word)
• 训练一个输入中心词预测上下文词的模型

CBOW：与SG相反，基于临近词（上下文词）预测目标词

相同之处：他们建立的模型是fake task，目的是为了获得词向量/词矩阵

第七章:词性标注

1. 什么是生成模型

由数据学习联合概率密度分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：P(Y|X)= P(X,Y)/ P(X)。

基本思想是首先建立样本的联合概率概率密度模型P(X,Y)，然后再得到后验概率P(Y|X)，再利用它进行分类。

$$P(x,y)=P(y)P(x|y)$$

2. 什么是判别模型

由数据直接学习决策函数Y=f(X) 或者 条件概率分布P(Y|X) 作为预测的模型，即判别模型。

基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。典型的判别模型包括k近邻，感知级，决策树，支持向量机等

• 给定输入x
• 预测要输出什么y

EXAMPLE:

判别式模型：要确定一个羊是山羊还是绵羊，用判别式模型的方法是从历史数据中学习到模型，然后通过提取这只羊的特征来预测出这只羊是山羊的概率，是绵羊的概率。

生成式模型：是根据山羊的特征首先学习出一个山羊的模型，然后根据绵羊的特征学习出一个绵羊的模型，然后从这只羊中提取特征，放到山羊模型中看概率是多少，再放到绵羊模型中看概率是多少，哪个大就是哪个。

3. 隐马尔可夫模型的五个要素

1. S:隐含状态集合。
2. N:观察状态集合。
3. A:隐藏状态间的转移概率矩阵。
4. B:隐-显状态发散矩阵（即隐藏状态到输出状态的概率）。
5. $\pi$:初始概率分布（隐藏状态的初始概率分布）。

4. 隐马尔可夫模型解决的三个问题

1. 在给定模型$\mu =(A,B,\pi )$ 观察序列O＝O1O2…OT的情况下，怎样快速计算概率p(O|μ)？ --前向算法
2. 在给定模型 和观察序列O＝O1O2…OT的情况下，如何选择在一定意义下“最优”的状态序列Q = q1 q2 … qT，使得该状态序列“最好地解释”观察序列？ —— 类似求最大似然估计 – Viterbi搜索算法
3. 给定一个观察序列O＝O1O2…OT ，如何根据最大似然估计来求模型的参数值？即如何调节模型的参数，使得p(O|μ)最大？ – 前向后向算法

5. 隐马尔可夫模型的两个假设

1. 如果在特定情况下，系统在时间t 的状态只与其在时间t-1 的状态相关，则该系统构成一个离散的一阶马尔可夫链
   $$p(q_t=S_j|q_{t-1}=S_i,q_{t-2}=S_j...)=p(q_t=S_j|q_{t-1}=S_i)$$
   类比2-gram模型

2. 如果只考虑独立于时间t 的随机过程，即所谓的不动性假设，状态与时间无关，那么
   $$p(q_t=S_j|q_{t-1}=S_i)=a_{ij}$$

6. 维特比算法的实现过程以及每个节点更新伪代码

第八章：逻辑回归和最大熵马尔可夫模型

1. 逻辑回归的假设函数

$$p=\frac{1}{1+e^{-z}}$$
得到[0,1]之间输出

2. 最大熵马尔可夫模型和隐马尔科夫模型的不同

• HMM模型是对转移概率和表现概率直接建模，统计共现概率，HMM就是典型的概率有向图，其就是概率有向图的计算概率方式，只不过概率有向图中的前边节点会有多个节点，而隐马尔可夫前面只有一个节点

• MEMM模型是对转移概率和表现概率建立联合概率，统计时统计的是条件概率，但MEMM容易陷入局部最优，是因为MEMM只在局部做归一化

EXAMPLE:
对于一个标注任务，“我爱北京天安门“， 标注为” s s b e b c e”。

对于HMM的话，其判断这个标注成立的概率为 $P=P(s转移到s)\times P(‘我’表现为s)\times P(s转移到b)\times P(‘爱’表现为s)\times \dots \times P()$

训练时，要统计状态转移概率矩阵和表现矩阵。

对于MEMM的话，其判断这个标注成立的概率为 $P=P(s转移到s|’我’表现为s)\times P(‘我’表现为s)\times P(s转移到b|’爱’表现为s)\times P(‘爱’表现为s)\times ..$训练时，要统计条件状态转移概率矩阵和表现矩阵，相比于HMM，状态转移概率矩阵变成了条件状态概率矩阵。

3. 标注偏置问题

MEMM模型克服了观察值之间严格独立产生的问题，但是由于状态之间的假设理论，使得该模型存在标注偏置问题

状态总是倾向于留在自己的状态——而不是其他状态

由于分支数不同，概率的分布不均衡，导致状态的转移存在不公平的情况。

第九章:命名实体识别

1. 中文命名实体识别的难点

• 实体边界识别和确定实体类别

时间、日期、货币和百分比的构成有比较明显的规律，识别起来相对容易
人名、地名、机构名的用字灵活，识别的难度很大

• 在不同领域、 场景下, 命名实体的外延有差
• 数量巨大,不能枚举,难以全部收录在词典中
• 某些类型的实体名称变化频繁，并且没有严格的规律可以遵循
• 表达形式多样
• 首次出现后往往采用缩写形式

2. 隐马尔可夫模型与CRF模型的不同？

1. 与HMM比较，CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息。特征设计灵活（与MEMM一样）

3. 马尔科夫随机场，满足哪些特性？

1. 成对马尔科夫性
2. 局部马尔科夫性
3. 全局马尔可夫性
   
   
   

4. 团和最大团

5. 条件随机场

设X与Y是随机变量，P(Y|X)是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图G=(V,E)表示的马尔可夫随机场，则称条件概率分布P(Y|X)为条件随机场。

$$P(Y_v|X,Y_w,w\ne v)=P(Y_V|X,Y_w,w\tilde{v})$$

其中，w~v表示在图G=(V,E)中与结点v有边连接的所有结点w，w≠v表
示结点v以外的所有结点

6. 条件随机场通常采用的特征函数

7. 条件随机场解码方法

问题描述：给定条件随机场P(Y|X)和输入序列(观察序列)x，求条件概率
最大的输出序列(标记序列)y*
 Viterbi算法：

• 根据上述公式，条件随机场的预测问题成为求非规范化概率最大的最优路径问题

第十章：成分句法分析

1. 什么上下文无关文法

若一个形式文法$G=(N,\Sigma ,P,S)$ 的产生式规则都取如下的形式：$V->w$，则谓之。其中 $V\in N，w\in (N\cup \Sigma )\ast$

2. 什么是乔姆斯基范式

在计算机科学中，一个形式文法是Chomsky 范式的，当且仅当所有产生规则都有如下形式：

1. $A\to BC$
2. $A\to \alpha$
3. $S\to \epsilon$

这里的A,B和C是非终结符，α 是终结符（表示常量值的符号），S是开始符号，而 ε 是空串。还有，B和C都不可以是开始符号。

所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。

3. CKY算法的实现

矩阵上三角的DP

function CKY-PARSE(words, grammar) returns table
​
  for j from 1 to LENGTH(words) do
    for all {A | A -> words[j] in grammar}
      table[j-1, j] += A
    for i from j-2 to 0 do
      for k from i+1 to j-1 do
        for all {A | A -> BC in grammar and B in table[i,k] and C in table [k,j]}
          table[i,j] += A
1
2
3
4
5
6
7
8
9

4. CKY for PCFGs算法实现

找出若干个PCFGs树，选出来概率最高的那个树