cws = chinese word segmentation

为什么要分词?

英文: 天然空格分割 + 词根

古文一般不加标点, 读书主要目的是”离经辨志” (“离”及断句), “明句读” (句号, 逗号).

20世纪后, 逐步统一规范了中文标点符号

有了标点符号后, 需进一步分词的意义? 消除歧义

• 我们/中/出了/叛徒 VS 我们/中出/了/叛徒
• 广州市/长隆乐园/欢迎/你 VS 广州市长/隆乐园/欢迎/你

业务功能落地场景

• 词云/热词分析/关键词抽取: 基于某个筛选维度, 分析高频出现词语
• 文本搜索
• 文本数据预处理

分词评价指标

• 准确率/召回率
  • p = 准确词数 / 实际分词数
  • r = 准确词数 / 标注分词数
• 缺点: 分词边界一致但是粒度细粗不能很好体现
  • 标注: 太/高兴/了
  • 识别1: 太高兴了 (p=r=0)
  • 识别2: 太高/兴了 (p=r=0)
• 登录词/未登录词 (OOV): 主要考察新词发现能力
• 识别速度 / 内存需求: 具体到业务落地时非常重要

词典分词

字符串匹配算法

问题: 文本长度N, 词典大小M, 词最长为D, 找出文本中所有在词典的词

Trie / 前缀树

• 为了匹配实现简单, 节点单字, 树深为D
• 需提前构建好

最长前缀匹配O(D) 应用场景: CIDR/路由表, 域名查找 (最长后缀)

全文匹配 (一个朴素的办法): 每个位置做一次前缀匹配O(N*D). 问题: 不匹配时很多计算路径信息被浪费了

AC:

• 每个节点记住到当前节点的最大后缀节点, 用于匹配失败后从该节点继续 (类比: 自动存档/回档)
• O(N)
• 内存占用优化: DAT (Double-array Trie) 双数组实现Trie,

See Code

多种分法的决策

词典无权重信息

• 优化目标: 最长匹配 OR 最多匹配 ?
• 最长匹配: 正向/逆向/双向
  • 正向 / FMM (Forward Max Match): 找当前最长匹配词
  • 逆向: 反向FMM
  • 双向: 都来一遍得到两个结果再决断, 优先选
  • NOTE: 都是贪心算法, 不保证匹配词总长最长, 本身是NP-hard问题

词典有权重信息 (词频)

• 最大词典权重 = 最大化共现概率 = max(prod(p)) = max(sum(log(p)))
• 等价于寻路问题

viterbi vs 寻路

都是DP, 保存到当前位置结束的最大权重及前向位置

See Code

OOV / 新词发现

不在词典中的片段, 直接当作新词肯定是不合适的, 需要尝试再切一下

HMM / Hidden Markov Model

状态: 当前字组成词的何处 表征: 输出的字

HMM考虑点

• 状态分几种
  • 两个状态标注分词够了, 但是两个状态太少
  • BEMS: Begin开始 / End结束 / Middle内部 / Single单词
  • BB1B2MES 6元法…
  • POS时, 还需要再乘上词性
  • 理论上状态越多越好, 但是训练数据支撑越少, 推断时速度越慢
• 基于字还是词做
• 一阶(unigram)还是高阶(n-gram) / 和上面基于字/词有一定重复
• HMM决定了连接只发生在临近词, 效果很有限

词典分词 和 HMM交互问题

两阶段流程:

1. 先基于词典分出来最大路径
2. 剩下的单字片段HMM尝试再合并做新词发现

问题:

• HMM切的片段里面也是部分有在词典的, 词频能否利用上
• 多阶段求最大, 不一定是全局最大

改进办法 (beam search 思路):

• 词典分词得到N个最大路径(及联合概率)
• 每个路径继续HMM再分(取最大或M个最大)
• 得到每种分法的联合概率, 在N*M个结果中取最大

jieba (0.39)

https://github.com/fxsjy/jieba/tree/v0.39

• POS逻辑和单分词逻辑不太一样
• 词典匹配非单词一定分
• 词典加载词性固定
• 做了全局状态 / re_xxx
• 没有持续维护了
• 连续单字走HMM, 一些常见介词容易误连起来, 效果不好

# https://github.com/fxsjy/jieba/issues/212
jieba.lcut("我们中出了叛徒", HMM=True)
['我们', '中出', '了', '叛徒']

See Code

实现上可优化点:

• 一般进去的文本时提前处理过的, 不用再正则切一遍
• 去掉全局变量
• 加载提前, 避免每次调用初始化检查
• 概率log计算可提前处理掉
• 不用考虑PY2
• get_DAG是两层循环, 可改用AC+DAT
• 状态转移数据可以改成文件加载/优化数据结构
• …

序列标注问题

tagging, pos, ner, chunking, …

对比分词, 多了一个词性维度

序列标注: N*S DAG 网格上的最大路径选择

词性:

• 语言角度: 名词/形容词/动词/…
• 业务角度:
  • 时间/日期/价格/…
  • 地名/人名/品牌名/…
  • 品类名/成分词/功效词/营销词/…

MEMM & CRF & SP

• 2000 / MEMM / Max Entropy Markov Model
  • 辨别式模型
• 2001 / CRF / Conditional Random Field / 条件随机场
  • 解决标签偏置问题 (Label Bias Problem)
  • LAC
• 2002 / SP / Structured Perceptron / 结构化感知器
  • THULAC / LTP

REF dm-ner.md

深度学习模型

模型层级

1. 表征层 (独热编码变稀疏表征): Embedding / BERT / …
2. 记忆层: RNN / Bi-LSTM / Bi-GRU
   • 学输入对每个状态的概率表达
3. 表达层: HMM / CRF / SP / …
   • 学状态迁移概率

LAC

https://github.com/baidu/lac

https://github.com/PaddlePaddle/models/tree/release/1.8/PaddleNLP/lexical_analysis

https://github.com/PaddlePaddle/PaddleNLP/tree/develop/examples/lexical_analysis

模型结构: Embedding + bi-GRU * 2 + CRF

评价

• 评测分词质量优于jieba
• 长文本大概率彻底躺平不分
  • e.g.: 红烧酱汁料包正宗红烧味懒人专属红烧酱汁90克
• 识别速度慢
• 运行时依赖大 (近500M, 多个模型文件全打包进依赖, 即便推断时用不到, 打包了整个Paddle框架)
• 百度KPI项目? 废弃整合进会PaddleNLP项目?
• Paddle问题
  • 硬件avx指令集绑定, mac/win某些版本加载失败
  • 代码质量差, 自行改logging配置, 内存泄露, …

逆向想法:

1. 模型参数提取, 构造相同网络结构后导出ONNX
2. 用于生成文本训练数据, 训练还原

LTP

TODO https://github.com/HIT-SCIR/ltp

HanLP

TODO https://github.com/hankcs/HanLP

Zipf Law / Power Law / 幂律 / 长尾理论 / 马太效应 / 二八定律

ref: https://www.nature.com/articles/srep00812

• 词出现频次和排名成反比
• QQ-plot / quantile-quantile plot 是条直线 ??
• log-log plot 是条直线 ??

编码 / Tokenization / 压缩 / 无监督自学习生成字典

TODO

上述分词 (构造词典, 计算HMM经验概率) 需要大量标注好的数据, 如何无监督的方式出分词? 语料 -> 最小编码字典过程

无损压缩 OR 有损压缩 ?

有损压缩: 掐头去尾

• 丢掉词频最高的部分: 最大化减少编码后数据大小, 幂律下放弃最少的人减最大的负担
• 丢掉词频很低的部分: 减少编码表宽, 也是小样本不具备学习意义

Reference

• https://zhuanlan.zhihu.com/p/67475895
• https://www.cnblogs.com/en-heng/p/6234006.html
• http://www.matrix67.com/blog/archives/5044
• https://kexue.fm/archives/5542
• https://kexue.fm/archives/7213