Table of Contents
关于
- 《自然语言处理入门》何晗，HanLP作者
- 主要内容
- 中文分词
- 序列标注与分词
- CRF
- 词性标注
- 命名实体识别
- 信息抽取
- 文本聚类
- 文本分类
- 依存句法分析
- 深度学习与NLP
- HanLP主要代码是通过Java实现的，方便集成到线上环境；同时支持python，其实底层还是通过python来调用Java包
第1章 新手上路
- 基于规则的专家系统
- 波特词干算法，由一些列规则组成，规则有优先级之分
- 基于统计的学习方法
- 语料库
- 中文分词：人名日报
第2章 词典分词
- 词典：HanLP自带了千万级词典，同时提供mini版
- 切分算法
- 完全切分，即遍历所有连续字序列，跟词典中的词进行匹配。输出所有可能的词
- 正向最长匹配：即认为越长的词优先级越高，优先匹配长词。从前往后扫叫做正向最长匹配，从后往前扫叫逆向最长匹配
- 逆向最长匹配：总的而言，逆向最长匹配效果好于正向，孙茂松教授论文
- 双向最长匹配：汉语中单字词数量远小于非单字词
- 同时执行正向和逆向最长匹配，若两者词数不一样，选择词数更好的那一个
- 否则返回单字最少的那个。
- 其他情况返回你想最长匹配
- 性能：
- Python set 比用java 的treemap慢
- 正向和逆向性能差不多，但是java的不好说，可能因为垃圾回收机制，正向快一些？
def fully_segment(text, dic): """ text: 文本序列 dic: set 集合，包含词典中所有的词 """ word_list = [] for i in range(len(text)): for j in range(len(text)): word = text[i:j] if word in dic: word_list.append(word) return word_list def forward_segment(text, dic): word_list = [] for i in range(len(text)): for j in range(len(text)): word = text[i:j] if word in dic: word_list.append(word) return word_list
- 字典树 trie 树，前缀树；避免了前缀的重复比较，比简单的二叉树匹配要快
- 由于子节点较多，所以孩子节点集合要用字典或者map来实现
- 首字散列其余二分的字典树：在逆向和双向匹配是，大约比Java的treemap快一倍的样子
- 首字：用字符散列函数来查询孩子，子节点个数很大，例如65535
- 其余的节点，通过二分查找来查询孩子
- 前缀树的妙用：优化到1000万字每秒
- 出发点，如果「自然」不在词典中，那么所有以「自然」开头的词都不在词典中。比普通实现的全切分可以快5-7倍
-
双数组字典树：略，进一步加速2-3倍
-
中文分词的评估
- 将切分区间标记为起止下标[i,j]
- 统计预测的区间集合A跟标注样本的区间集合B的交集，计算precision和recall
$$
P = \frac{|A \cap B|}{|A|} \\
R = \frac{|A \cap B|}{|B|}
$$
- 评估指标
- P，R，F1
- Roov，即不在词典内的词召回率
- Riv，即在词典内的词召回率，因为存在歧义的问题，所以无法做到100%
-
最长匹配算法，在MSR语料上的P为89%，R为95%，F192%，Roov2.58%,Riv97%
-
字典树的其他应用
- 停用词过滤，敏感词过滤
- 繁简体转化，需要按词进行转换
- 拼音转换，需要按词进行转换
第3章 二元语法与中文分词
- 基本思想是，利用语言模型这个先验知识，来对分词的歧义情况消歧义。例如，可以解决「商品和服务」的两种分法「商品 和 服务」 「商品 和服 务」，前者的概率较高
- 语言模型通过以词为单位的二元语言模型来建模。举例
- p(商品 和 服务) = p(商品|BOS) p(和|商品) p(服务|和) p(EOS|服务)
- p(商品 和服 务) = p(商品|BOS) p(和服|商品) p(务|和服) p(EOS|务)
- 上述条件概率通过统计得到 p(w1 | w0) = #(w0 w1)/#(w0)
-
数据稀疏和平滑，高阶语言模型用低阶平滑，例如2元模型用1元平滑
$$
p(w1|w0) = \lambda p(w1|w0) + (1-\lambda) p(w1)
$$ -
分词语料库：人民日报，MSR
- 分词的每一种切分（在这种方法中要求最小粒度要在词典中），都可以看做词图上的一条路径，所以分词就变成找到一条概率最大的路径。当用log处理概率后，就可以认为是一个最短路径问题。viterbi译码算法
- 与用户词典的融合
- 低优先级，用户词典合并：例如，统计分词后结果「商品 和 服务 员」，如果「服务员」出现在用户词典中，那么会合并为「商品 和 服务员」
- 高优先级，干预词网生成，一元词频由用户提供，二元词频直接由一元词频伪造（搞成相同）。分出概率较高，一般只在一定要分出的场景下才用
- 问题，OOV 新词；因为OOV和新词都不在词典中，所以新词无法召回
第4章 隐马尔科夫模型与序列标注
- 中文分词作为一种序列标注问题，每个字可以属于的类别
- B，词首
- E，词尾
- M，词中
- S，单字成词
- 隐马尔科夫模型
- 状态：词的类别：BEMS
- 转移概率：即标注的类别转移概率矩阵A，可以通过事先从语料中统计出来
- 发射概率：从类别（隐状态）到字（观测值、显状态）的概率，也是可以从语料中统计出来
样本生成问题
- 医疗诊断
- 初始化一个隐状态
- 根据发射矩阵采样一个观测状态
- 根据转移矩阵采样下一个隐状态
- 重复2-3
模型训练
- 估计三个概率：初始概率，转移概率，发射概率
- 极大似然估计：即简单的统计
模型预测
- 维特比译码算法，回忆卷积码译码算法
- 最大化条件概率 P(观测序列|隐状态序列)，对给定的观测序列X，寻找隐序列Y最大概率 P(Y|X) = P(X, Y)/P(X)，也就是只要最大化联合概率 P(X, Y) 即可
- 算法的主要步骤
- 从i=1到N，N是观测序列长度
- 用pj 表示最优隐状态序列是第i个个隐状态的联合概率，即 P([o1,o2,..,oi], [s1,s2,...,si])
- 那么有动态规划方程，即从第i个状态递归到第i+1个状态的递归方程。因此每一步只需要保留|S|个p和最优序列
$$
p_j^{i+1} = \max_k p_k A_{k, j} B_{j, o_i}
$$
HMM应用于中文分词
- HanLP中的HMMSegmenter
- 对于非字典中的词统一映射到UNK
- 一阶HMM的F1值只有79%，不如词典分词，但Roov提高到41%
二阶HMM
- 转移概率从只依赖前一个tag，还依赖前二个tag；只有转移概率变了，发射概率不变
- 估计方式和预测逻辑基本类似，只需要改一下转移概率的计算方式
- 第二个时刻需要特殊处理，第二个时刻因为没有二阶转移概率，所以用的是一阶转移概率
- 效果：Roov相比一阶有少量提升，但是F1反而稍微下降。
- 结论：增加阶数，对提升效果不明显，无法改变F1值不如词典的问题
第5章 感知机分类与序列标注
- 感知机部分略，感知机的损失函数是 $(loss = - \hat{y} y = max(0, - y w^T x))$，没有间隔，SVM在感知机上加了个间隔参数
- 投票感知机和平均感知机：即多个模型融合和多模型只是将权重平均
- 基于感知机的人名性别分类：用字做特征
- 结构化预测问题：如序列预测，语法树。关键是对可能的结构进行打分（在分词中，对每一种标注序列进行打分）
- 预测，结构化维特比译码算法：将概率换成打分即可，打分等于前一步打分+新增的该步打分（模型建模得到）
基于结构化感知机的中文分词
- 将分词当做多分类任务，依赖序列之前的信息和当前的信息
- 结构化感知机中的序列打分相当于联合概率
- score([x1,x2,...,xk+1], [y0,y1,y2,...,yk+1]) = score([x1,x2,...,xk], [y0,y1,y2,...,yk]) + score(xk+1, yk+1)
- score(xk+1, yk+1) 用一个线性多分类模型来建模(用xk+1预测yk+1)，特征不仅仅包含当前位置的特征，还附近的字特征和上文的标签特征
- 特征提取：
- 转移特征：相当于转移概率矩阵的用途。前一个字的标签
- 状态特征：类似于发射矩阵的用户。当前字附近的1gram和2gram
- 模型压缩：去掉权重很小的特征
- 模型的F1：96%，Roov：70%。集合了基于词典和HMM的优点，效果比二者都好。基本达到实用水平。
- 特征工程
- 叠字，相邻两个字是否相等
- 四元语法，相邻4个字符为窗口的所有n-gram
- 词典特征，用户词典全切分后，当前字符位置最长词语的长度
- 偏旁部首，字的偏旁
第6章 条件随机场与序列标注
- 性能比感知机强大
- CRF，P(Y|X)
- 特征函数，$(f(y_{t-1}, y_t, [x_1, ...,x_t]))$
- 条件概率建模
$$
p(Y|X) = \frac{1}{Z(X)} \Pi \exp(\sum_k w_k f_k(y_{t-1}, y_t, X_t))
$$ - 结构化感知机和CRF的打分函数完全相同
- CRF的梯度是特征函数在经验分布上的期望与模型分布上的期望之差。当差变为0了，模型就拟合了经验数据（即训练完了）
$$
\frac{\partial l}{\partial w_k} = E_{\hat{p}}(f_k) - E_{w}(f_k)
$$ -
上述期望是对所有的Y求（即所有可能的标签）和所有的X求（即所有样本）
-
对比结构化感知机
- 相同点：
- 特征函数相同
- 权重向量相同
- 打分函数相同
- 预测算法相同，都是用维特比译码。CRF的联合概率可以分解为多步的乘积
- 同属结构化学习
- 不同点：即损失函数不同，本质上来讲，感知机损失相当于只有正样本，而CRF损失还加了负样本
- 训练算法不同：感知机在线学习；CRF是批量学习。即使都使用在线学习也不一样
- 感知机：$(-\Delta w = \phi(x^i , y^i) - \phi(x^i, - \hat{y}))$。只惩罚当前这个分错的类别
- CRF：$(-\Delta w = \phi(x^i , y^i) - E_w\phi(x^i , y) )$。期望是对所有可能的yi求的，所以是对所有的其他类别做惩罚
- 相同点：
-
CRF工具包，CRF++ https://taku910.github.io/crfpp/
- 效果，超过结构化感知机，F1+0.1%，Roov+1%
- CRF可以看做多分类逻辑回归应用到序列问题（结构化逻辑回归？）
第7章 词性标注
- 联合模型：需要分词和词性同时标注的语料，虽然效果好，但是语料难搞，特征倍数扩大。所以主流还是将分词作为上游任务（语料多），词性标注作为下游任务
- 语料：
- 人民日报语料库与PKU标注集，43中词性
- 国家语委语料库与863标注集，20个一级，29个二级词性
- 诛仙语料库与CTB标注集
- 标注准确率，HMM大约40-45%，CRF 80%+
第8章 命名实体识别
- 将词聚合成复合词，NER
- 人名
- 机构名
- 商品名
- 基于规则
- 词典：机构名、人名
- 正则表达式：数字、英文识别
- 语料：
- 人民日报
- MSRA
- 基于层叠HMM的角色标注框架
- 基于序列标注的命名实体识别 BMES
- 特征提取
- 转移特征 yt-1
- 词特征 wt-1,wt-1,w,wt+1,wt+2
- 词性特征 tag_t-1, tag_t, tag_t+1
- 评测指标：P、R、F1
第9章 信息抽取
- 新词抽取，可以简单理解为OOV，领域词典
- 非监督新词发现：交互信息熵，即得知x带来对预测y的不确定性的降低量。显然，这个不确定性减少量越高，代表这两个词越可能是新词
$$
I(x;y) = \log \frac{p(x, y)}{p(x) p(y)} = I(y) - I(y|x)
$$ - 关键词提取
- 词频
- TF-IDF
- TextRank：将词看做节点，共现看做边，利用PageRank算法生成
- 短语提取：搜索引擎自动推荐、文档简介生成
- 多个词构成的词组
- 互信息，提取二元语法短语（即2个词构成的短期），n元语法
- 关键句提取：将句子看做节点，相似看做边的权重，利用PageRank算法生成
- BM25相似度，将其中一个句子中的词看做query，另一个句子看做文档，计算query跟文档的相似度（由TF和文档长度计算得出），然后将所有query按照IDF加权求和，得到相似度
第10章 文本聚类
- 词袋模型
- 特征：
- 布尔词频
- TF-IDF
- 词向量，词向量求和得到文档向量。TF，SVD，LDA，word2vec etc
- K-Means聚类
第11章 文本分类
- 分词，卡方特征选择
- 朴素贝叶斯
- SVM
- 情感分类
第12章 依存句法分析
- 短语结构树：即一棵语法树，上下文无关文法（见编译原理）
- 树库（treebank）：宾州树库（英文），中文树库
- 依存句法理论：词与词间存在主从关系，是二元不对等关系。生成依存句法树
- 有且只有一个词不依赖其他词语
- 其他的所有词必须依存于其他词
- 每个单词不能依存于多个单词
- 如果A依存于B，那么AB之间的C只能依存于A、B或者AB之间的词
FAQ
为什么逆向最长匹配通常好于正向最长匹配
为什么字典树相比普通的二叉树要快
- 例如，比较「你好」，普通二叉树每个字都要比较多次；而字典树「你」只比较一次！
为什么二元语言模型要求切分的最小粒度要在词典中
- 因为不在词典中，没法通过词频计算概率
二元语法解决的根本问题是什么
- 利用语言模型，消除只用字典分词出现的切分的歧义
- 基本单元是词，在词典中的词
- HMM处理的基本单元是字
HMM中对UNK的发射概率是如何处理的
结构化维特比译码算法模型参数如何训练
- 直接当做监督学习的任务来学；只是译码的时候是，从左到右，利用维特比译码算法+打分函数进行预测
感知机模型如何跟词典融合
HMM为什么不如结构化感知机和CRF
- 因为HMM只建模了隐状态（即标签）的前后关联关系，而没有建模显状态（字）的前后关联关系
- 结构化感知机通过状态特征，建模字的前后关联关系（即语言模型）
- CRF直接建模标签的前后关联，字的前后关联，字根标签的发射关系
结构化感知机和CRF的区别是什么？为什么CRF效果更好？
如何理解CRF的本质
- CRF的本质是在建模 P([y1,y2,...,yn]|[x1,x2,...,xn])
- 它对上述条件概率做了一定的简化
- P([y1,y2,...,yt]|[x1,x2,...,xt]) = P([y1,y2,...,yt-1]|[x1,x2,...,xt-1]) P(yt|yt-1, [x1,x2,...,xn])
- 其中条件概率 P(yt|yt-1, [x1,x2,...,xn]) 通过一个线性函数来拟合(其实就是多分类逻辑回归)
$$
P(y_t|y_{t-1}, [x_1,x_2,...,x_n]) = \frac{1}{Z(X)} \Pi \exp(\sum_k w_k f_k(y_{t-1}, y_t, X_t))
$$ - 总结起来，CRF有这些特点
- 建模序列到序列的条件概率
- 认为yt至于前面的y有关，而跟t后面的y无关，但是跟全部的x都有关
- 在yt前面的y给定下，将预测yt变成一个多分类问题，用一个多分类逻辑来建模
CRF vs HMM
- HMM可以看做CRF的特例：
- yt 只跟 xt 有关，即 P(yt|yt-1, [x1,x2,...,xn]) = P(yt|xt)
- xt 只跟 xt-1 有关，马尔科夫性，CRF没有这个假定