自然语言处理导论

文本处理

 

正则表达式

匹配单个字符

字符	功能
.	匹配任意一个字符（除了\n）
[]	匹配 [] 中列举的字符
\d	匹配数字，即 0-9
\D	匹配非数字
\s	匹配空白，即 空格、tab键
\S	匹配非空白
\w	匹配单词字符，即 a-z、A-Z、0-9、_
\W	匹配非单词字符

匹配多个字符

字符	功能
*	匹配前一个字符出现 0 次或无限次
+	匹配前一个字符出现 1 次或无限次
?	匹配前一个字符出现 0 次或 1 次
{m}	匹配前一个字符出现 m 次
{m,n}	匹配前一个字符出现 m 到 n 次

匹配开头或结尾

字符	功能
^	匹配字符串开头
$	匹配字符串结尾

• | 匹配左右任一个表达式。yours|mine|his
• [\text{^}] \text{^}在方括号内表示非后面的字符。[\text{^A-Z}]

pat = re.compile(pattern)，创建模式对象pat，以后只要用 pat.match 等自己的方法。

match(pattern,string)，从字符串开始处匹配模式，返回第一个匹配上的。

group(i)。匹配分组，group(0) 为整个匹配上的串。

import re
s = "bdsbfhsa121321"
print(re.search(r"(\D+)(\d+)", s).group(0))
#group(0):bdsbfhsa121321
#group(1):bdsbfhsa
#group(2):121321

search(pattern,string)，从字符串每个位置开始，返回第一个匹配上的。

由于match和search返回的是_sre.SRE_Match格式，所以要配合group使用。

split(pattern,string)，把string用pattern分割，返回列表。

sub(pat,repl,string)，把string中所有pat的匹配项替换为repl，返回新字符串。

findall(pattern,string)，找到所有匹配，返回列表。

 

词干提取和词形还原

词干提取是去词的前后缀，抽取词的词干或词根，不一定能表达完整的语义，方法较为简单，例如 leave - leav。

词形还原是把一个词汇还原为一般形式，能够表达完整语义，例如 leave - leaf，方法较为复杂，需要词性标注标签。

 

中文分词

基于规则的分词方法：依据词典进行分词

• 正向最大匹配：从左到右贪心选择尽量长且在词典中的词，删除，再继续。词典中始终没有就自成一词。
• 逆向最大匹配：从右到左贪心选择尽量长且在词典中的词，删除，再继续。词典中始终没有就自成一词。注意词典中词也反过来了。
• 双向最大匹配：上述两种算法都做一遍，根据：长词越多越好，非词典词和单字词越少越好，总词数越少越好。选择一种方案作为结果。
• 结巴分词

 

基于统计的分词方法

• 最大概率法
• 字标注法

 

文本分类

 

定义

文本分类是将自然语言的文本（例如，网页，电子邮件，新闻，公司文档等）归入到预定义的语义类别中。

 

作用

• 文本分类组织，便于管理、归档、检索和维护
• 垃圾邮件过滤

 

分本分类的类别

• 文本内容分类。时事，财经，体育，军事等。
• 文本情感分类。称赞批评，风险机会，电商评论，政治立场等。
• 文本题材分类。个人主页，新闻，评论，科技文献等。

 

基本流程

1. 预处理。去掉特殊字符、标点等，分词，去停词，取词干，删去低频词。
2. 词包
3. 特征选择
4. 构建分类器

 

朴素贝叶斯

$$\begin{align} P(Y=y|X=x)&=\frac{P(Y=y)\cdot P(X=x|Y=y)}{P(X=x)}\\ &=\frac{P(Y=y)\cdot P(X=x|Y=y)}{\sum_yP(Y=y)P(X=x|Y=y)}\\ \end{align}$$

似然：$P(X=x|Y=y)$

先验概率：$P(Y=y)$

后验概率：$P(Y=y|X=x)$

取后验概率最大的标签 $y$。

 

平滑

$add-\alpha$：

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

 

不同 $\alpha_i$：

$$P(x_i|y)=\frac{n_{i,y}+\alpha_i}{n_y+\sum_{j=1}^V\alpha_j}\\$$

 

评估标准

Accuarcy（准确率）

$$\frac{TP+TN}{TP+TN+FP+FN}$$

 

Precision（精确率）

选中的项中正确的概率

$$\frac{TP}{TP+FP}\\$$

 

Recall（召回率）

正确的项被选中的概率

$$\frac{TP}{TP+FN}\\$$

 

F1

$$F=\frac{2PR}{(P+R)}\\$$

 

语言模型

 

用途

• 计算句子正确的概率
• 决定哪个词序列的可能性更大
• 已知若干词，预测下一个词

 

应用

语音识别，上下文敏感的拼写检查，机器翻译，手写体识别，OCR（光学字符识别）

 

目标

计算词序列的概率

$$P(W)=P(w_1,w_2,\cdots,w_n)$$

 

链式法则

$$P(w_1,w_2,\cdots,w_n)=\prod_i P(w_i|w_1w_2\cdots w_{i-1})\\$$

 

马尔科夫假设

一阶马尔科夫假设：

$$P(x_i|x_1,\cdots,x_{i-1})\approx P(x_i|x_{i-1})\\$$

 

二阶马尔科夫假设：

$$P(x_i|x_1,\cdots,x_{i-1})\approx P(x_i|x_{i-2},x_{i-1})\\$$

 

N-gram语言模型

 

Unigram Model

$$P(w_1,\cdots,w_n)=\prod_i P(w_i)\\$$

Bigram Model

基于一阶马尔科夫假设

$$P(w_1,\cdots,w_n)=\prod_{i}P(w_i|w_{i-1})\times P(STOP|w_n)\\$$

Trigram Model

基于二阶马尔科夫假设

$$P(w_1,\cdots,w_n)=\prod_{i}P(w_i|w_{i-2},w_{i-1})\times P(STOP|w_{n-1},w_n)\\$$

总结

深度学习可以视为无穷元语法。

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

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

 

评估

Perplexity（困惑度）

$$\text{perplexity}=\sqrt[N]{\frac{1}{P(w_1,\cdots,w_n)}}\\$$

 

平滑

$add-\alpha$，Interpolation（插值法），Kneser-Ney smoothing

 

Interpolation（插值法）

$$\begin{align} P(w_i|w_{i-2},w_{i-1})&=\lambda_1 P(w_i|w_{i-2},w_{i-1})\\ &+\lambda_2 P(w_i|w_{i-1})\\ &+\lambda_3P(w_i)\\ \\ \lambda_1+\lambda_2+\lambda_3=1\\ \end{align}$$

 

Kneser-Ney smoothing

$$P(w_i|w_{i-1})=\frac{\max\{c(w_{i-1},w_i)-d,0\}}{c(w_{i-1})}+\lambda(w_{i-1})P_{CONTINUATION}(w_i)\\ \\ P_{CONTINUATION}(w)=\frac{|v\in V:c(v,w)>0|}{|v',w'\in V:c(v',w')>0|}\\$$

 

拼写检查

• Non-word Errors：错误词不在词典中。
• Real-word Errors：错误词在词典中。

 

噪声信道模型

 

最短编辑距离

$dp[i][j]$ 表示 串S前 i 个字符，串T前 j 个字符的最短编辑距离。

$$dp[i][0]=i\\ dp[0][j]=j\\$$

$$dp[i][j]=\min \begin{cases} dp[i-1][j]+1\\ dp[i][j-1]+1\\ dp[i-1][j-1]+2\cdot[S_i\neq T_j]\\ \end{cases}$$

流程

$$\text{prob of candidate}=P(candidate|W)\cdot P(mistake|candidate)\\$$

结合语言模型求解 $P(candidate|W)$。

1. 对于错误的词，根据编辑距离生成候选词，常选距离为 1 或 2 的词。
2. 对于 real-word Errors 需要对每个词都生成候选词。如上图。
3. 根据给定文本库计算 $P(mistake|candidate)$。
4. 根据语言模型（unigram/bigram/trigram/···)，计算 $P(candidate|W)$，例如 bigram，$P(candidate|W)\approx P(candidate|w_{i-1})$。
5. 选出 $\text{prob of candidate}$ 最高的词作为修改词。

 

词的语义表示

 

词向量

• Term-document matrix：文档与词的矩阵

  

  横向表示词向量，纵向表示文档向量。

• Term-context matrix

  用上下文表示一个单词。

  左右各 Window Size 个单词。

  

 

TF-IDF

针对 Term-document

$tf_{i,j}$：单词 $i$ 在文档 $j$ 中出现的频率，即单词 $i$ 在文档 $j$ 中出现次数 / 所有单词在文档 $j$ 中出现次数之和。

$$\text{tf}_{i,j}=\frac{n_{i,j}}{\sum_k n_{k,j}}\\$$

$idf_{i}$：总文档数 / 包含单词 $i$ 的文档数。

$$\text{idf}_i=\log \frac{|D|}{|d:t_i\in d|}$$

$$\text{tfidf}_{i,j}=tf_{i,j}\cdot idf_i\\$$

 

PMI

针对 Term-context

$$\text{PMI}(X,Y)=\log_2\frac{P(x,y)}{P(x)P(y)}\\$$

PPMI在此基础上把 PMI 与 0 取 max。

$w$ 为单词，$c$ 为它的一个上下文单词。

$$\text{PPMI}=\max(\log_2\frac{P(w,c)}{P(w)P(c)},0)\\$$

若 $P(w,c)=0$ 可加入平滑。

$$ P(\text{w=information},\text{c=data})=6/19=0.32\\ P(\text{w=information})=11/19=0.58\\ P(\text{c=data})=7/19=0.37\\ \text{PMI(information,data)}=\log_2\frac{0.32}{0.58*0.37}=0.58\\ $$  

语义相似度

余弦相似度基于 PPMI

$$cos(\vec{v},\vec{w})=\frac{\vec{v}\cdot \vec{w}}{|\vec{v}||\vec{w}|}\\$$

 

SVD

用于 Term-document matrix 数据降维。

对高维矩阵做奇异值分解，取权重最高的 K 维。

不足：

• 矩阵维度大小不固定，会随新词的添加而变化，语料库大小也随之变化。
• 矩阵过于稀疏，大部分单词不会同时出现。
• 矩阵维度太高。
• 训练成本太高。
• 需要加入一些隐含词来解决词频不均衡的问题。

 

神经网络预测方法

利用神经网络方法训练得到词向量。

与SVD可以有相同作用，但是计算量更低。

参考 https://blog.csdn.net/qq_34872215/article/details/88085288

 

词性标注

 

词性标注集：https://www.cnblogs.com/elpsycongroo/p/9369111.html

 

生成模型与判别模型

参考 https://blog.csdn.net/zouxy09/article/details/8195017

监督学习方法分为生成方法与判别方法，产生的模型称为生成模型与判别模型。

生成模型从数据集中学习到数据与标签的联合概率分布 $P(x,y)$，之所以称为生成模型是因为可以根据这个联合概率分布自己生成一些 $(x,y)$。例如朴素贝叶斯和隐马尔科夫模型等。

判别模型学习到的则是条件概率分布 $P(y|x)$，即直接可以学习到在给定数据 $x$ 的条件下，标签为 $y$ 的概率，可以直接用来分类。例如k近邻，感知机，决策树，支持向量机等。

通过公式 $P(x,y)=P(y)P(x|y)$，生成模型可以得到判别模型，但判别模型不能得到生成模型。

 

马尔可夫模型

基于以下两个假设。

1. 在时间 t 的状态只与其在时间 t-1 的状态相关。构成一个离散的一阶马尔可夫链。也就是满足上面提到过的一阶马尔可夫假设。

   $$p(q_t=S_j|q_{t-1}=S_i,q_{t-2}=S_k,\cdots)=p(q_t=S_j|q_{t-1}=S_i)\\$$

2. 不动性假设。状态与时间无关。即可以定义一个与时间无关的状态转移矩阵。

   $$p(q_t=S_j|q_{t-1}=S_i)=a_{ij}\\$$

 

隐马尔可夫模型

有多种状态，每一种状态都可能产生一些可观察事件，现在已知一个可观察事件的序列，要猜测状态转移的流程。

以上图为例，黄球和红球是两个可观察事件，N，V，A 等罐子就是一些状态。从黄球变到红球可能是从 罐子A 转移到 罐子 N，（因为罐子A里有黄球，N里有红球），但也可能是由 A 转移到 T，因为 T 里也有红球。这两种转移都是可能的，但我们并不知道究竟是哪一种。这就是HMM的定义描述中所说的“状态转换过程是隐蔽的”。

将模型描述为 $\mu=(S,O,A,B,\pi)$ ，即（状态序列，观察序列，状态转移概率矩阵，发射概率矩阵，初始状态概率分布），或 $\mu=(A,B,\pi)$。

 

问题 1：给定模型 $\mu=(A,B,\pi)$ 和观察序列 $O=O_1O_2\cdots O_T$，快速计算 $P(O|\mu)$ 。

令 $Q=q_1 q_2\cdots q_T$ 为状态序列。

$$p(O|\mu)=\sum_{Q}p(Q|\mu)\times p(O|Q,\mu)$$

• 前向算法
• 后向算法

 

问题 2：给定模型 $\mu=(A,B,\pi)$ 和观察序列 $O=O_1O_2\cdots O_T$，得到最优状态序列 $Q=q_1q_2\cdots q_T$。

• Viterbi搜索算法

 

问题 3：给定一个观察序列 $O=O_1O_2\cdots O_T$，如何根据最大似然估计来求模型的参数值，即如何调节模型的参数，使得 $p(O|\mu)$ 最大？

• 前向后向算法

 

前向算法

$dp[t][i]$ 表示在时刻 $t$，状态为 $S_i$，出现观察序列 $O_1O_2\cdots O_t$ 的概率。

枚举 $t-1$ 时刻状态，转移到 $t$ 时刻状态，并在 $t$ 时刻发射观察事件 $O(t)$。

复杂度 $O(N^2T)$，其中 $N$ 为状态总数。

$$dp[1][i]=\pi_i b_i(O_1)\\ dp[t][i]=(\sum_{j=1}^N dp[t-1][j]\cdot a_{ji})\times b_i(O_{t})\\ p(O|\mu)=\sum_{i=1}^N dp[T][i]\\$$

其中 $b_i(O_{t})$ 表示在 $S_i$ 状态下出现观察事件 $O_{t}$ 的概率，即发射概率。

 

后向算法

$dp[t][i]$ 表示在时刻 $t$，状态为 $S_i$，出现观察序列 $O_{t+1}O_{t+2}\cdots O_T$ 的概率。

注意这里是在时刻 $t$ 输出 $O_{t+1}$，也就是说在时刻 $T$ 时什么都没有输出。

复杂度同前向算法 $O(N^2T)$。

$$dp[T][i]=1\\ dp[t][i]=\sum_{j=1}^N a_{ij}b_j(O_{t+1})\times dp[t+1][j]\\ p(O|\mu)=\sum_{i=1}^N dp[1][i]\times \pi_i\times b_i(O_1)\\$$

 

Viterbi搜索算法

其实就是输出上面的 dp 路径。

也就是在前向算法的基础上，再维护一个 $fa[t][i]=k$ 表示 $dp[t][i]$ 的最大值是由状态 $q_{t-1}=S_k$ 转移得到的。

复杂度必然也是同前向算法 $O(N^2 T)$。

 

HMM用于词性标注

即给定 词串 $W$，隐马尔可夫模型 $\lambda$，词性标注序列 $T$，求 $P(T|W,\lambda)$。

以下计算都在模型 $\lambda$ 的基础上，所以可以先去掉条件概率中的 $\lambda$，变为 $P(T|W)$。

$$P(T|W)=\frac{P(T,W)}{P(W)}=\frac{P(T)P(W|T)}{P(W)}\\$$

得到

$$P(T|W)\propto P(T)P(W|T)\\$$

结合马尔可夫模型的一阶假设

$$P(T)=P(t_1|t_0)P(t_2|t_1)\cdots P(t_i|t_{i-1})\\$$

其中 $P(t_i|t_{i-1})=\frac{训练语料中t_i出现在t_{i-1}后的次数}{训练语料中t_{i-1}出现的次数}$

结合HMM的独立性假设（在状态 $S_i$ 下发射 $w_i$ 的概率独立）

$$P(W|T)\approx P(w_1|t_1)P(w_2|t_2)\cdots P(w_i|t_i)\\$$

其中 P(w_i|t_i)=\frac{\text{训练语料中w_i$的词性被标记为$t_i的次数}}{\text{训练语料中t_i出现的总次数}}

例：

再使用 Veterbi算法 得到最优词性标注序列。

 

逻辑回归最大熵

逻辑回归

是判别模型

$$P(y=1|x,\beta)=\frac{1}{1+\exp(-\sum_{i=1}^Fx_i\beta_i)}=\frac{1}{1+e^{-\vec{x}\cdot \vec{\beta}}}\\$$

根据特征向量与系数向量的乘积得到概率。

从训练数据中学到系数向量。

特征选择不需要基于独立性假设。且可以选择任意与文章有关的内容。

在测试时，对于一个 $x$，我们选择 $\arg \max\limits_y P(y|x)$，所以在训练时，我们希望得到系数 $\beta$ 最大化正确标签的概率，根据极大似然估计，设定似然函数为 $L(\beta)=\prod\limits_{i=1}^NP(y_i|x_i,\beta)$，则要求得 $\arg\max \limits_\beta\prod\limits_{i=1}^NP(y_i|x_i,\beta)$。

 

逻辑回归用在语言模型

$$P(Y=y|X=x;\beta)=\frac{\exp(x^T\beta_y)}{\sum_i\exp(x^T\beta_i)}\\$$

即对 $\exp(x^T\beta_y)$ 的归一化。

 

Unigram LM

只有 BIAS 一维。

Bigram LM

Trigram LM

平滑

增加一阶特征，即 $P(w_i|w_{i-1})$。

 

最大熵马尔可夫模型

Viterbi算法

Viterbi for HMM：

$$v_t(y)=\max_{u\in Y}[v_{t-1}(u)\times P(y_t=y|y_{t-1}=u)P(x_t|y_t=y)]\\$$

Viterbi for MEMM：

$$v_t(y)=\max_{u\in Y}[v_{t-1}(u)\times P(y_t=y|y_{t-1}=u,x,\beta)]\\$$

局部归一化

在 $\prod\limits_{i=1}^nP(y_{i}|y_{i-1},x,\beta)$ 乘法的每一步都做归一化。

例如，设状态 MD->TO，MD->VB，则分别计算出 $P(TO|MD)$ 和 $P(VB|MD)$ 后，分别归一化变成 $\frac{P(TO|MD)}{P(TO|MD)+P(VB|MD)}$ 和 $\frac{P(VB|MD)}{P(TO|MD)+P(VB|MD)}$。

局部归一化会导致 Viterbi 算法无法得到最优路径。

例如若 MD->TO，NN->TO，即这两种状态都是只能得到 TO，那么

 

命名实体识别

命名实体：现实世界中具体或抽象的实体。如人，机构，地点等。广义地讲，命名实体还可以包含时间，日期，金钱等。需要在具体应用中判断。

包括基于字典/规则的命名实体识别方法，与基于统计的命名实体识别方法。

 

基于字典的命名实体识别方法

• 正向最大匹配算法
• 反向最大匹配算法
• 最短路径法（最少分词法）

与之前介绍的分词中的方法类似。

 

基于统计的命名实体识别方法

• 生成式方法。首先建立学习样本的生成模型，再利用模型对预测结果进行间接推理。

  例如：HMM，PCFG。

• 判别式方法。转化为序列标注问题。

  例如：Maxent，SVM，CRF，CNN，RNN，LSTM+CRF。

 

条件随机场（CRF）

定义：给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型。

特点：假设输出随机变量构成马尔可夫随机场。

应用：不同类型的标注问题，例如：单个目标的标注，序列标注，图标注。

HMM是生成式模型，难以考虑复杂的特征。HMM是概率有向图。

CRF是判别式模型，可以考虑复杂特征。CRF是概率无向图。

 

成对马尔可夫性

任意一对没有直接相连的节点，在给定其它所有节点 O 的条件下互相独立。

 

局部马尔可夫性

设 $v$ 是图 G 中任意一点，O 是与 v 直接相连的所有点，U 是除 v，O 外的所有点，则给定随机变量组 $Y_o$ 的条件下 $Y_v$ 与 $Y_U$ 独立。

任意一个节点与所有不与他直接相连的节点，在给定与他相连的节点组O的条件下，互相独立。

 

全局马尔可夫性

设节点集合 $V,U$ 是被节点集合 $O$ 分开的任意两个节点集合，则在给定 $Y_o$ 的条件下 $Y_U$ 和 $Y_V$ 独立。

 

马尔可夫随机场

如果概率无向图模型的联合概率分布 $P(Y)$ 满足全部三种马尔可夫性，则称为马尔可夫随机场。

目的：将整体的联合概率分布 $P(Y)$ 分解为若干子联合概率的乘积的形式，也就是进行因子分解。

最大团：不能再加进任何一个点使成为更大的团，则是最大团。并不一定只有整个图上包含点数最多的团。

因子分解：将马尔可夫随机场模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式。

设 C 是图 G 上的最大团，$\Psi_c(Y_c)$ 是 C 上的函数。则因子分解为

$$P(Y)=\frac{1}{Z}\prod_c\Psi_c(Y_c)\\$$

其中 $Z$ 是归一化因子。

$$Z=\sum_{Y}\prod_c\Psi_c(Y_c)\\$$

 

线性链条件随机场

条件随机场：若随机变量 Y 构成由无向图G表示的马尔可夫随机场，则称条件概率分布 $P(Y|X)$ 为条件随机场。

$$P(Y_v|X,Y_w,w\neq v)=P(Y_v|X,Y_w,w\backsim v)\\$$

其中 $w\backsim v$ 表示与 $v$ 直接相连的所有节点，$w\neq v$ 表示除 $v$ 以外的所有节点。

即 给定除 v 以外的所有点的条件概率分布 等于 给定与 v 相连的点的条件概率分布。

线性链条件随机场

在条件随机场的基础上，$X=(X_1,X_2,\cdots,X_n),Y=(Y_1,Y_2,\cdots,Y_n)$ 均为线性链表示的随机变量序列。

$$P(Y_i|X,Y_1,\cdots Y_{i-1},Y_{i+1},\cdots ,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})\\$$

参数形式

上面说过，条件随机场是马尔可夫随机场，而马尔可夫随机场可以因式分解为最大团上的乘积。

在线性链条件随机场中，每一个相邻的点对都是一个最大团，所以条件概率分布可以表示为所有相邻点对上的函数的乘积。

下面取的函数为 $\exp$ 函数，所以相当于exp中指数的和。

$$P(y|x)=\frac{1}{Z(x)}\exp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))\\$$

$$Z(x)=\sum_y\exp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))\\$$

其中 $x$ 为可观察样本的任意特征（例如：词本身，大小写，词性等），这里假设有 $k$ 个特征，特征的重要程度由 $\lambda$ 控制，训练得到。

$t_k$ 定义在边上的特征函数，也称转移特征，依赖于前一个和当前位置。

$s_l$ 定义在点上的特征函数，也称状态特征，依赖于当前位置。

例如：

解：

$$p(y|x)\propto \exp[\sum_{k=1}^5\lambda_k\sum_{i=2}^3t_k(y_{i-1},y_i,x,i)+\sum_{k=1}^4\mu_k\sum_{i=1}^3s_k(y_i,x,i)]\\ \lambda_1t_1+\lambda_5t_5+\mu_1s_1+\mu_2s_2+\mu_4s_4=1+0.2+1+0.5+0.5=3.2\\ P(y_1=1,y_2=2,y_3=3|x)\propto \exp(3.2)\\$$

 

HMM vs CRF

• HMM 是一种生成式模型，利用转移矩阵和生成矩阵建模相邻状态的转移概率和状态到观察的生成概率。无法利用复杂特征（只有两个矩阵建模）。
• CRF是一种判别式模型，可以使用任意的复杂特征（特征函数）（虽然每个位置有一个矩阵，但是矩阵的元素是由特征函数和权重计算得到，我们可以任意地定义特征函数从而考虑各种特征），可以建模观察序列和多个状态的关系，考虑了状态之间的关系。

 

句法分析

上下文无关文法（CFG）

context-free grammar。

$G=(N,\Sigma,R,S)$

$N$ ———— 非终结符构成的有限集合。如 NP，VP，S。

$\Sigma$ ———— 终结符构成的有限集合。如 the，dog，a。

$R$ ———— 产生式构成的集合，产生式的形式为 $A\rightarrow \beta,\beta\in(\Sigma,N)$，如 $S\rightarrow NP\text{ }VP,Noun\rightarrow dog$。

$S$ ———— 起始符号。

上下文无关文法中的产生式左侧的非终结符一定只能有一个符号。在每一个出现了产生式左侧的符号的地方都可以通过这个产生式替换为右侧的符号串，而不用考虑这个符号的上下文。

括号表示法

子树在一个括号里，终结符不需要再分隔。

评估

先表示为 $\{(label_1,l_1,r_1),\cdots,(label_n,l_n,r_n)\}$ 的元组的集合形式，$label_i$ 为标签，$l_i$ 为第一个单词的下标，$r_i$ 为最后一个单词的下标。

假设现在有2棵树，则

第一棵树的精确率Precision为 既在第一棵树中又在第二棵树中的元组个数 / 第一棵树中的元组个数。

第一棵树的召回率Recall为 既在第一棵树中又在第二棵树中的元组个数 / 第二棵树中的元组个数。

 

概率上下文无关文法（PCFG）

给定一个上下文无关文法，每个产生式都有概率。且对于每一种 $A$，都有

$$\sum_i P(A\rightarrow \beta_i)=\sum_i P(\beta_i|A)=1$$

给定一棵PCFG的树，就相当于每条边上都有边权是这条边代表的产生式的概率。

则由这棵树产生的句子的概率等于所有边权的乘积。

 

乔姆斯基范式（CNF）

$G=(N,\Sigma,R,S)$

$N$ ———— 非终结符构成的有限集合。如 NP，VP，S。

$\Sigma$ ———— 终结符构成的有限集合。如 the，dog，a。

$S$ ———— 起始符号。

上面三个都与CFG相同。区别在于下面。

$R$ ———— 产生式构成的集合，产生式的形式为 $A\rightarrow \beta$。$\beta$ 只能是 $\Sigma$ 中的单个终结符，或者 $N$ 中的两个非终结符。即树上节点要么有两个非叶节点儿子，要么只有一个叶节点儿子。

 

CKY算法

根据上面定义中的限制，原句子中的每个区间要么长度为1，要么只能由两个区间组合而成，所以就成了个典型的区间dp。

$dp[i][j]$ 表示区间 $[i,j]$ 能否用一个 $N$ 或 $\Sigma$ 中的符号表示。

则从小到大枚举长度，再枚举区间左端点，再枚举分割点，分割成两个已求出的区间进行转移。

CKY算法用于得到所有该句子可能的分解。

区间dp复杂度即为 $O(n^3)$

 

基于PCFG的CKY算法

上面的CKY算法中 $dp[i][j]$ 只能为 0/1。

加入概率，即 $dp[i][j]$ 表示对区间 $[i,j]$ 的众多分解方式中，概率最大的那个分解方式的概率。

 

问题与改进

问题：在不同位置的同一个产生式可能有不同的概率。

例如：位于主语位置的 NP ，产生DT NN的概率与位于宾语位置的NP产生 DT NN 的概率不同。

改进：在树上每个非叶节点上标注它的父亲，以此判断它所处的位置，并使用不同的概率。

难点：使得语法非常臃肿，且数据集不够。

 

问题：叶节点无法影响树的概率。

例如：一条边 VBD->saw，换成 VBD->sneezed，树的概率不变。

改进：在每个非叶节点上标注它的子树中的一个关键的叶节点。

难点：不可能对每个终结符都已知概率。