UCAS自然语言处理

国科大自然语言处理（宗成庆）笔记

期末提示

• 并列句计算，好像是边界距离计算，好像是编辑距离计算
• 概念弄清楚
• 分类 聚类 评价的指标
• 句法分析
  • 依存句法分析
  • 怎么评价性能
• 分词
  • 分词错误类型
  • 汉语分词
  • 并列句计算
• 机器翻译怎么度量译文质量

数学基础

1. 熵
   3. 单位为二进制位比特 (bit)
   4. 熵又称为自信息(self-information)，表示信源X每发一个信号所提供的平均信息量
   5. 熵也可以被视为描述一个随机变量 的不确定性的数量。一个随机变量的熵越大， 它的不确定性越大。那么，正确估计其值的可 能性就越小
2. 联合熵
   2. 就是描述一对随机变量平均所需要的信息量
3. 条件熵
   1. 
   2. 
   3. 可以不用直接求条件熵，而是通过连锁法则算
   4. 
   5. 
4. 熵率
   1. 
5. 相对熵、KL散度、KL距离、Kullback-Leibler divergence
   1. 
   2. 注意这个前面没有负号
6. 交叉熵
   1. 
7. 困惑度
   1. 
8. 互信息
   1. 
   2. 
9. 双字耦合度
   1. 
   2. 
10. 噪声信道模型
    1. 在信号传输的过程中都要进行双重性处理：一方面要 通过压缩消除所有的冗余，另一方面又要通过增加一定的可控冗余以保障输入信号经过噪声信道后可以很好地恢复原状。信息编码时要尽量占用少量的空间，但又必须保持 足够的冗余以便能够检测和校验错误。接收到的信号需要 被解码使其尽量恢复到原始的输入信号
    2. 噪声信道模型的目标就是优化噪声信道中信号传输的 吞吐量和准确率，其基本假设是一个信道的输出以一定的 概率依赖于输入。
    3. 
    4. 
11. 编辑距离
    1. 

形式语言与自动机

形式语言定义

1. 形式语言定义
   1. 
2. 形式语言推导
   1. 
   2. 
   3. 
   4. 
3. 文法生成语言L(G)
   1. 

乔姆斯基四类文法

1. 正则文法(regular grammar, RG), 或称 3型文法
2. 上下文无关文法(context-free grammar, CFG), 或称2型文法
3. 上下文有关文法(context-sensitive grammar, CSG), 或称1型文法
4. 无约束文法(unrestricted grammar)，或称0型文法

如果一种语言能由几种文法所产生，则把这种语言 称为在这几种文法中受限制最多的那种文法所产生的 语言

正则文法

3型文法

1. 定义
   1. 
2. 转换为正则文法
   1. 

上下文无关文法

2型文法

1. 定义
   1. 
2. 派生树
   1. 
3. 二义性
   1. 一个文法 G，如果存在某个句子有不只一棵分析树与之对应，那么称这个文法是二义的
   2. 

上下文有关文法

1型文法

1. 定义
   1. 

无约束文法

0型文法

1. 定义
   1. 、
      

自动机

自动机是有穷地表示无穷语言的另一种方法。每一 个语言的句子都能被某种自动机所接受。

• 有限(状态)自动机(finite automata, FA)，用的最多，对应正则文法（3型）
• 下推自动机(push-down automata, PDA)，对应上下文无关文法（2型）
• 线性带限自动机(linear bounded automata)，对应上下文有关文法（1型）
• 图灵机(Turing Machine)，没有实际意义，一般不用，对应无约束文法（0型）

有限状态自动机

1. 确定性有限自动机(deterministic finite automata, DFA)
   1. 
   2. 
   3. 终止状态用双圈表示，起始 状态用有“开始”标记的箭头表示
   4. 
2. 非确定性有限自动机(non-deterministic finite automata, NFA)
   1. 
   2. 

正则文法和有限自动机关系

1. 
2. 文法转换为自动机
   1. 
   2. 
   3. 
3. 自动机转文法
   1. 
   2. 
   3. 转换结果

语料库与语言知识库

1. 语料库定义(corpus)
   • 用于存放语言数据的文件(语言数据库)。
2. 语料库语言学(corpus linguistics)
   • 基于语料库进行的语言学研究。研究自然语言文本的采集、存储、检索、统计、 词性和句法及语义信息的标注、以及具有上述功能的 语料库在语言定量分析、词典编纂、作品风格分析和 人类语言技术等领域中的应用。
3. 类型
   1. 按内容构成和目的划分
      1. 
   2. 按语言种类划分和标注
      1. 
   3. 平衡语料库
      1. 
   4. 平行语料库
      1. 
      2. 
   5. 共时语料库和历时语料库
      1. 
      2. 
4. 问题和现状
   1. 

语言模型

传统语言模型

n元文法

1. 计算语句先验
   1. 
2. 历史基元过多问题
   1. 
   2. 
   3. 
3. 定义
   1. 
   2. 
4. 举例
   1. 
   2. 
   3. 

参数估计

1. 
2. 
3. 问题是，存在数据匮乏的情况，导致一些概率算出来是0， 因此要进行数据平滑

数据平滑

1. 基本思想
   1. 
2. 加一法
   1. 其实就是分子加1，分母加上所有的类（词汇表V大小）
   2. 
   3. 
3. 减值法/折扣法
   1. 
   2. 自己查下，考试应该不考
   3. Good-Turning估计法
   4. 后退法
   5. 绝对减值法
      1. 
      2. 
      3. 
   6. 线性减值法
      1. 
   7. 四种减值法的比较
      1. 
4. 删除插值法
   1. 
   2. 

语言模型自适应

1. 方法
   1. 

n元文法应用

分词

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 

分词与词性标注一体化方法

1. 
2. 
3. 
4. 
5. 
6. 

神经语言模型

1. 传统语言模型的问题
   1. 
   2. 

前馈神经网络语言模型

这部分省略

循环神经网络语言模型

RNN和LSTM，以及Self-attention的内容，也省略

附录有BP算法的推导，可以自己看

文本表示

基础

1. 概念
   1. 
2. 特征项
   1. 
3. 特征项权重：词频，TF-IDF，逆文档频率
   1. 
4. 规范化Normalization
   1. 

分布式表示

表示学习模型

1. 文本概念表示模型：以（概率）潜在语义分析和潜在狄利克雷分布为代表的主题模型，旨在挖掘 文本中的隐含主题或概念，文本将被表示为主题 的分布向量
   1. 
2. 深度表示学习模型：通过深度学习模型以最优化特定目标函数（例如语言模型似然度）的方式在 分布式向量空间中学习文本的低维实数向量表示

词语的表示学习

1. 
2. 

3. NNLM模型

   1. 

4. C&W模型

   1. 中心词进行随机替换
   2. 
   3. 

5. word2vec: CBOW和Skip-Gram

   1. 
   2. 
   3. 
   4. 

6. Glove模型

   1. 
   2. 太多了，省略

7. 负采样和噪声对比估计

   1. 
   2. 
   3. 
   4. 
   5. 负采样技术的目标函数与噪声对比估计相同，但是不同于
      噪声对比估计方法，负采样技术不对样本集合进行概率归
      一化，而直接采用神经网络语言模型输出

8. 字词混合的表示学习

   1. 词语由字或字符构成，一方面词语作为不可分割的单元可以获得一个表示；另一方面词语作为字的组合，通过字的表示也可以获得一个表示；两种表示结合得到更优表示
   2. 在低维、稠密的实数向量空间中，相似的词聚集在一起， 在相同的历史上下文中具有相似的概率分布

短语的表示学习

1. 词袋模型
   1. 
2. 递归自编码器
   1. 
3. 双语约束模型
   1. 
   2. 

句子的表示学习

1. 词袋模型
   1. 平均
   2. 加权平均
2. PV-DM模型
   1. 
   2. 
3. PV-DBOW模型
   1. 
4. Skip-Thought模型
   1. 
   2. 
5. CNN模型
   1. 对于一个句子，卷积神经网络CNN以每个词的词向量为输入，通过顺 序地对上下文窗口进行卷积（Convolution）总结局部信息，并利用池 化层（Pooling）提取全局的重要信息，再经过其他网络层（卷积池化 层、Dropout层、线性层等），得到固定维度的句子向量表达，以刻 画句子全局性的语义信息
   2. 

文档的表示学习

1. 词袋模型
2. CNN模型
3. 层次化模型
   1. 

预训练模型

ELMo预训练模型

1. 
2. 
3. 
4. 
5. 

GPT预训练模型

1. 
2. 
3. 下游任务
   1. 
   2. 分类，对最后一个hidden进行变换后softmax
4. 优点：
   1. 任务统一: 大部分语言处理任务形式化为语言模型任务
   2. 

BERT预训练模型

参考以前的博客BERT-预训练源码理解和论文笔记 | Attention Is All You Need

概率图模型

概率图模型的演变

马尔科夫模型

1. 描述
   1. 
2. 假设
   1. 当前状态只和前一个状态有关
   2. 
   3. 状态的转移和时间t无关
   4. 
3. 
4. 和NFA关系
   1. 
   2. 
   3. 

隐马尔科夫模型HMM

模型介绍

1. 
2. 
3. 
4. 

核心问题

给定HMM求观察序列

1. 

快速计算观察序列概率

前向算法和后向算法

1. 
2. 上面的方法，会导致有个状态序列，指数级组合爆炸

前向算法

1. 
2. 
3. 
4. 
5. 时间复杂度：

后向算法

1. 
2. 
3. 
4. 
5. 时间复杂度：

发现最优状态序列

如何发现“最优”状态序列能够“最好地解释”观察序列？

维特比算法

1. 
2. 
3. 

模型参数学习

1. 
2. 
3. 
4. 
5. 

HMM应用

1. 分词
2. 词性标注

条件随机场模型CRF

省略

形态分析、汉语分词与词性标注

1. 词性标注（消岐）中的并列鉴别规则
2. 标出命名实体，说明类型

英语形态分析

1. 有规律变化单词的形态还原
2. 动词、名词、形容词、副词不规则变化单词的形态还原
3. 对于表示年代、时间、百分数、货币、序数词的数字形态还原
4. 合成词的形态还原

形态分析的一般方法

1. 查词典，如果词典中有该词，直接确定该词的原形；
2. 根据不同情况查找相应规则对单词进行还原处理，如果还原后在词典中找到该词，则得到该词的原形；如果找不到相 应变换规则或者变换后词典中仍查不到该词，则作为未登 录词处理；
3. 进入未登录词处理模块。

汉语自动分词

1. 交集型歧义
   1. 中国/ 人为/ 了/ 实现/ 自己/ 的/ 梦想
   2. 中国人/ 为了/ 实现/ 自己/ 的/ 梦想
   3. 中/ 国人/ 为了/ 实现/ 自己/ 的/ 梦想
   4. 
2. 组合型歧义
   1. 门/ 把/ 手/ 弄/ 坏/ 了/ 。
   2. 门/ 把手/ 弄/ 坏/ 了/ 。
3. 分词基本原则
   1. 
4. 辅助原则
   1. div
      
   2. 
   3. 
   4. 
5. 评价指标
   1. 
   2. 

汉语自动分词方法

1. 最大匹配法
   1. 
   2. 
   3. 
   4. 
2. .最少分词法(最短路径法) 有词典切分
   1. 基本思想
      
   2. 
   3. 
   4. 
3. 基于语言模型的分词方法
   1. 基本思路
      
   2. 
4. 基于HMM的分词
5. 由字构词 (基于字标注)的分词方法
   1. 
   2. 
6. 生成式和判别式模型区别
   1. 
   2. 
7. 生成式方法与区分式方法的结合
   1. 
   2. 
   3. 
   4. 

未登录词

1. 命名实体
   1. 人名、地名、机构名、时间、日期、货币、百分比，数字如果在这些类别中的话就算命名实体，如果不在，通常也有单独的数字识别任务
2. 其他新词，如专业词汇和新的普通词

子词切分（BPE算法）

1. 
2. 
3. 

例子

1. 
2. 

词性标注

1. 标注方法
   1. 
   2. 
   3. 
   4. 
   5. 

句法分析

短语结构分析

• 基于CFG规则的分析方法
  • 线图分析法
  • CYK分析法
• 基于PCFG的分析法
• 句法分析性能评估
• 局部句法分析

线图分析法

1. 三种策略
   1. 自底向上 (Bottom-up)
   2. 从上到下 (Top-down)
   3. 从上到下和从下到上结合
2. 
3. 
4. 例子
   1. 
   2. 
   3. 
   4. 
   5. 
   6. 
   7. 

CYK分析法

1. 
2. 

例子

1. 
2. 
3. 

基于PCFG的分析法

1. 
2. 
3. 
4. 
5. 
6. 

句法分析性能评估

1. 精度precision
2. 召回recall
3. F1分数
4. 交叉括号数：（括号有重叠都算）：一棵分析树中与其他分析树中边界相交叉的成分个数的平均值。通常是对应位置的短语比较
5. 交叉准确率
6. 词性标注准确率

依存句法分析

在依存语法理论中，“依存”就是指词与词之间支配与被 支配的关系，这种关系不是对等的，而是有方向的。处于支配 地位的成分称为支配者(governor, regent, head)，而处于被支配 地位的成分称为从属者(modifier, subordinate, dependency)。

1. 
2. 

依存句法四条公理

(1) 一个句子只有一个独立的成分；即单一父结点(single headed)
(2) 句子的其他成分都从属于某一成分；即连通(connective)
(3) 任何一成分都不能依存于两个或多个成分；即无环(acyclic)
(4) 如果成分A直接从属于成分B，而成分C在句子中位于A和B
之间，那么，成分C或者从属于A，或者从属于B，或者从 属于A和B之间的某一成分；即可投射(projective)

依存分析方法

目前依存句法结构描述一般采用有向图方法或依存树方法，
所采用的句法分析算法可大致归为以下4类：

• 生成式分析方法(generative parsing)
• 判别式分析方法(discriminative parsing)
• 决策式(确定性)分析方法(deterministic parsing)
• 基于约束满足的分析方法(constraint satisfaction parsing)

Arc-eager algorithmX算法

1. 
2. 
3. 
4. 
5. 

评价指标

1. 无标记依存正确率(unlabeled attachment score, UA 或 UAS)：所有词中找到其正确支配词的词所占的百分比，没有找到支配词的词(即根结点)也算在内
2. 带标记依存正确率(labeled attachment score, LA 或 LAS)：所有词中找到其正确支配词并且依存关系类型也标注正确的词所占的百分比，根结点也算在内。就是在UA里面找依存关系标注正确的
3. 依存正确率(dependency accuracy, DA)：所有非根结点词中找到其正确支配词的词所占的百分比。就是UA的分子分母同时减去1
4. 根正确率(root accuracy, RA)：有两种定义方式：
   • (1)正确根结点的个数与句子个数的比值；
   • (2)所有句子中找到正确根结点的句子所占的百分比。
   • 对单根结点语言或句子来说，二者是等价的。
5. 完全匹配率(complete match, CM)：所有句子中无标记依存结构完全正确的句子所占的百分比

短语结构和依存关系转换

1. 
2. 
3. 
4. 
5. 

基于深度学习的句法分析

略

英汉句法结构特点对比

略

语义分析

语义网络的概念

语义网络通过由实体、概念或动作、状态及语义关系组成的 有向图来表达知识、描述语义。

1. 有向图：图的结点表示实体或概念，图的边表示实体或概念
   之间的关系。
2. 边的类型：
   • “是一种抽象(IS-A)”: A到B的边表示“A是B的一种特例”;
   • “是一部分(PART-OF)”: A到B的边表示“A是B的一部分”;
   • “是属性(IS)”：A到B的边表示“A是B的一种属性”；
   • “拥有/占用(HAVE)”: A到B的边表示 “A拥有B”；
   • “次序在先/前(BEFORE)”: A到B的边表示 “A在B之前”
3. 事件的语义网络表示
   1. 当语义网络表示事件时，结点之间的关系可以是施事、受事、 时间等。这里所说的“事件”指某个具体的动作或状态，并非 我们日常生活中所说的事件。
4. 事件的语义关系
   1. 

词义消岐

1. 
2. 其他略

语义角色标注

1. 
2. 
3. 
4. 

语义的表征与解码

略

篇章分析

略

机器翻译

1. 问题和现状
   1. 
2. 基本观点
   1. 

基本翻译方法

1. 直接转换法
   1. 从源语言句子的表层出发，将单词、短语或句子 直接置换成目标语言译文，必要时进行简单的词序调 整。对原文句子的分析仅满足于特定译文生成的需要。 这类翻译系统一般针对某一个特定的语言对，将分析 与生成、语言数据、文法和规则与程序等都融合在一 起
2. 基于规则的翻译方法
   1. 对源语言和目标语言均进行适当描述、把翻译机制与 语法分开、用规则描述语法的实现思想，这就是基于 规则的翻译方法
   2. 步骤
      
   3. 评价：
      
3. 基于中间语言的翻译方法
   1. 
   2. 
   3. 
4. 基于语料库的翻译方法
   1. 基于事例的翻译方法
      1. 
      2. 
   2. 统计机器翻译
   3. 神经网络机器翻译
5. 

统计机器翻译

1. 基本思想
   1. 
2. 噪声信道模型
   1. 
   2. 
3. 统计翻译三个关键问题
   1. 估计语言模型概率；
      1. n-gram问题
      2. 
   2. 估计翻译概率；
      1. 
      2. 
      3. 
      4. 
      5. 
      6. 
   3. 快速有效地搜索T 使得最大。

神经网络机器翻译

1. 对比
   1. 统计机器翻译
      1. 数据稀疏（离散符号表示）
      2. 复杂结构无能为力
      3. 强烈依赖先验
      4. 可解释性高
   2. 神经机器翻译
      1. 连续稠密分布式表示
      2. 双语平行语料库 相同
      3. 可解释性低
      4. 翻译性能高，简单有效
2. 系统融合方法
   1. 
   2. 句子级系统融合
      1. 针对同一个源语言句子，利用最小贝叶斯风险解码或重打分方法比较多个机器翻译系统的译文输 出，将最优的翻译结果作为最终的一致翻译结果
   3. 短语级系统融合
      1. 利用多个翻译系统的输出结果，重新抽取短语翻译规则集合，并利用新的短语翻译规则进行重新 解码
   4. 词语级系统融合
      1. 首先将多个翻译系统的译文输出进行词语对齐，构建一个混淆网络，对混淆网络中的每个位置的 候选词进行置信度估计，最后进行混淆网络解码
   5. 深度学习的系统融合
      1. 首先将多个翻译系统的译文进行编码，然后采用层次注意机制模型预测每个时刻目标语言的输出： 底层注意机制决定该时刻更关注哪个源语言片段， 上层注意机制决定该时刻更依赖哪个系统的输出
3. 译文评估方法
   1. 句子错误率：译文与参考答案不完全相同的句子为错误句子。错误句子占全部译文的比率。
   2. 单词错误率(Multiple Word Error Rate on Multiple Reference, 记作 mWER)：分别计算译文与每个参考译文的编辑距离，以最短的为评分依据，进行归一化处理
   3. 与位置无关的单词错误率 ( Position independent mWER, 记作mPER )：不考虑单词在句子中的顺序
   4. METEOR 评测方法：对候选译文与参考译文进行词对齐，计算词汇完全 匹配、词干匹配、同义词匹配等各种情况的准确率 ( P)、召回率(R)和F平均值
   5. BLEU方法
      1. 将机器翻译产生的候选译文与人翻译的多个参考 译文相比较，越接近，候选译文的正确率越高。
      2. 
      3. 
      4. 
   6. NIST
      1. 
      2. 

文本分类和聚类

传统机器学习方法

深度学习方法

文本分类性能评估

1. TP
2. FP
3. TN
4. FN
5. Precision
6. Recall
7. Acc
8. 宏平均：
   1. 分别算完，再加起来除以类别数
   2. 
9. 微平均
   1. 整体的TP等加起来，只算一次
   2. 
10. P-R曲线
    1. 
11. ROC曲线
    1. 

文本聚类指标

两个文本对象相似度

1. 
2. 
3. 
4. 

两个文本集合相似度

1. 
2. 
3. 
4. 
5. 
6. 

文本和簇的相似度

• 样本与簇之间的相似性通常转化为样本间的相似度或 簇间的相似度进行计算。
• 如果用均值向量来表示一个簇，那么样本与簇之间的 相似性可以转化为样本与均值向量的样本相似性。
• 如果将一个样本视为一个簇，那么就可以采用前面介 绍的簇间的相似性度量方法进行计算

衡量聚类指标

1. 外部指标
   1. 
   2. 
   3. 
   4. 
   5. 
2. 内部标准
   1. 
   2. 
   3. 

信息抽取

• 信息抽取是从非结构化、半结构化的自然语言文本 （如网页新闻、学术文献、社交媒体等）中抽取实 体、实体属性、实体间的关系以及事件等事实信息 ，并形成结构化数据输出的一种文本数据挖掘技术 [ Sarawagi, 2008]
• 从非结构化文本到机器可读信息的一种转换技术 [Wu, 2010]

命名实体识别

1. 概念
   • 信息抽取的一项基础任务
   • 自动识别出文本中指定类别的实体，包括人名、地名、 机构名、日期、时间和货币等七类
   • 人名（例如“乔布斯”）、地名（例如“北京”）、组 织机构名（例如“中国科学院”）、时间（例如“10点 30分”）、日期（例如“2017年6月1日”）、货币（例 如“1000美元”）、百分比（例如“百分之五十”）
   • 由于时间、日期、货币和百分比规则性强，利用模板或 正则表达式基本可处理
   • 人名、地名和组织机构名是关注重点
2. 目标
   • 包含两个任务：实体检测和实体分类
   • 实体检测：检测出文本中哪些词串属于实体，也即发现 实体的左边界和右边界
   • 实体分类：判别检测出的实体具体属于哪个类别
3. 方法（将实体检测和分类任务联合建模）
   1. 基于规则的方法
   2. 基于有监督的机器学习方法
      1. 
      2. 基于HMM的NER
      3. 基于CRF的NER
      4. 基于DNN的NER
4. 评价指标
   1. 以实体为单位
   2. 

实体消岐

1. 概念
   1. 一篇文档中同一实体可能有多种不同的指称（Mention） ，不同文档中相同名称的实体也可能表示不同的含义。 前者需要共指消解（Coreference Resolution）技术，后者 需要实体链接（Entity Linking）技术
   2. 共指消解就是为文本中的指称确定其具体实体的过程(一篇文档中同一实体)
      1. [李克强]接见[美国总统][特朗普]，[他]首先对[美国总统]的到来表示热烈欢迎。
      2. “美国总统”和“特朗普”表示同一实体，“他”实际 指代的是“李克强”，即例子中的所有指称聚为两类
   3. 实体链接就是确定实体指称所对应的真实世界实体的过程(不同文档中相同名称)
      1. “张杰多次参加春节联欢晚会。原上海交通大学校长张杰院士出任中国科学院副院长。
      2. 在第一句话中，“张杰”指的是“歌手张杰”，而第二句话中的“张杰”指的是“中科院院士张杰”
2. 典型方法
3. 实体链接评价
   1. 
   2. 

关系抽取

1. 概念
   1. 
   2. 
   3. 
2. 评价指标
   1. 

事件抽取

1. 概念
   1. 
   2. 
   3. 
2. 实例
   1. 
   2. 
   3. 
3. 典型方法
   1. 基于联合模型的事件抽取方法
   2. 基于分布式模型的事件抽取方法
4. 评价指标
   1. 
   2. 几乎所有模型都将事件抽取任务分解为触发词识别和事件角色 分类两个步骤，其中触发词识别又可分解为触发词定位与事件 类型分类两个子任务，事件角色分类又可分解为事件元素识别 与角色分类两个子任务；因此，客观评测一般对四个子任务分 别进行测试
   3. 若模型找到了触发词的在事件描述中的具体位置， 那么触发 词定位正确；在定位正确的基础上，如果事件的类型也预测 正确，那么事件类型分类任务得到正确结果。若某候选事件 元素被正确识别为触发词的关联属性，那么事件元素识别是 正确的，如果正确识别的事件元素进一步被预测为正确的事 件角色，那么最终的事件角色分类也是正确的。根据匹配结 果，利用准确率（ Precision）、召回率（Recall）和F1值分别度量各个子任务的性能

人机对话

任务型对话系统

聊天型对话系统

问答系统

系统搭建方法