重新写了之前的新词发现算法:更快更好的新词发现
By 苏剑林 | 2019-09-09 | 92555位读者 |新词发现是NLP的基础任务之一,主要是希望通过无监督发掘一些语言特征(主要是统计特征),来判断一批语料中哪些字符片段可能是一个新词。本站也多次围绕“新词发现”这个话题写过文章,比如:
在这些文章之中,笔者觉得理论最漂亮的是《基于语言模型的无监督分词》,而作为新词发现算法来说综合性能比较好的应该是《更好的新词发现算法》,本文就是复现这篇文章的新词发现算法。
背景 #
当时写《【中文分词系列】 8. 更好的新词发现算法》的时候,笔者就已经给出过一个基本的实现并且做过验证了。然而,当初的版本是纯Python写的,并且当时只是想着快速验证效果,所以写得相当随意,会存在比较严重的效率问题。最近把这事想起来了,觉得不想浪费这个算法,所以就重写了一遍,利用了一些工具和技巧,把速度提上去了。
顺便说一下,“新词发现”是一个比较通俗的叫法,更准确的叫法应该是“无监督构建词库”,因为原则上它能完整地构建一个词库出来,而不仅仅是“新词”。当然,你可以将它跟常用词库进行对比,删掉常见词,就可以得到新词了。
细节 #
主要改动如下:
1、使用了语言模型工具kenlm的count_ngrams程序来统计ngram。由于kenlm是用C++写的,速度有保证,并且它还做了优化,所以对内存很友好。
2、在第二次遍历词库以得到候选词的时候,使用了Trie树结构来加速搜索字符串是否出现过某个ngram。Trie树或者其变种基本上是所有基于词典的分词工具的标配,就是因为它可以加快搜索字符串中是否出现过词典中的词。
使用 #
本次开源地址位于:
注意这个脚本应该只能在Linux系统下使用。如果你想要在Windows下使用,应该需要做些修改,具体做哪些修改,我也不知道,请自行解决。注意算法本身理论上能适用于任意语言,但本文的实现原则上只适用于以“字”为基本单位的语言。
在决定使用该库之前,还望读者能花点时间读一下《【中文分词系列】 8. 更好的新词发现算法》,对算法步骤有个基本了解,以便更好地弄懂下述使用步骤。
Github中核心的脚本是word_discovery.py,它包含了完整的实现和使用例子。下面我们简单梳理一下这个例子。
首先,写一个语料的生成器,逐句返回语料:
import re
import glob
# 语料生成器,并且初步预处理语料
# 这个生成器例子的具体含义不重要,只需要知道它就是逐句地把文本yield出来就行了
def text_generator():
txts = glob.glob('/root/thuctc/THUCNews/*/*.txt')
for txt in txts:
d = open(txt).read()
d = d.decode('utf-8').replace(u'\u3000', ' ').strip()
yield re.sub(u'[^\u4e00-\u9fa50-9a-zA-Z ]+', '\n', d)
读者不需要看懂我这个生成器究竟在做什么,只需要知道这个生成器就是在逐句地把原始语料给yield
出来就行了。如果你还不懂生成器怎么写,请自己去学。请不要在此文章内讨论“语料格式应该是怎样的”、“我要怎么改才能适用我的语料”这样的问题,谢谢。
顺便提一下,因为是无监督训练,语料一般都是越大越好,几百M到几个G都可以,但其实如果你只要几M的语料(比如一部小说),也可以直接测试,也能看到基本的效果(但可能要修改下面的参数)。
有了生成器之后,配置一些参数,然后就可以逐个步骤执行了:
min_count = 32
order = 4
corpus_file = 'thucnews.corpus' # 语料保存的文件名
vocab_file = 'thucnews.chars' # 字符集保存的文件名
ngram_file = 'thucnews.ngrams' # ngram集保存的文件名
output_file = 'thucnews.vocab' # 最后导出的词表文件名
write_corpus(text_generator(), corpus_file) # 将语料转存为文本
count_ngrams(corpus_file, order, vocab_file, ngram_file) # 用Kenlm统计ngram
ngrams = KenlmNgrams(vocab_file, ngram_file, order, min_count) # 加载ngram
ngrams = filter_ngrams(ngrams.ngrams, ngrams.total, [0, 2, 4, 6]) # 过滤ngram
注意,kenlm需要一个以空格分词的、纯文本格式的语料作为输入,而write_corpus
函数就是帮我们做这件事情的,然后count_ngrams
就是调用kenlm的count_ngrams程序来统计ngram。所以,你需要自行编译好kenlm,并把它的count_ngrams放到跟word_discovery.py同一目录下。如果有Linux环境,那kenlm的编译相当简单,笔者之前在这里也讨论过kenlm,可以参考。count_ngrams
执行完毕后,结果会保存在一个二进制文件中,而KenlmNgrams
就是读取这个文件的,如果你输入的语料比较大,那么这一步会需要比较大的内存。最后filter_ngrams
就是过滤ngram了,[0, 2, 4, 6]是互信息的阈值,其中第一个0无意义,仅填充用,而2, 4, 6分别是2gram、3gram、4gram的互信息阈值,基本上单调递增比较好。
至此,我们完成了所有的“准备工作”,现在可以着手构建词库了。首先构建一个ngram的Trie树,然后用这个Trie树就可以做一个基本的“预分词”:
ngtrie = SimpleTrie() # 构建ngram的Trie树
for w in Progress(ngrams, 100000, desc=u'build ngram trie'):
_ = ngtrie.add_word(w)
candidates = {} # 得到候选词
for t in Progress(text_generator(), 1000, desc='discovering words'):
for w in ngtrie.tokenize(t): # 预分词
candidates[w] = candidates.get(w, 0) + 1
这个预分词的过程在《【中文分词系列】 8. 更好的新词发现算法》就介绍过了,总之有点像最大匹配,由ngram片段连接成尽可能长的候选词。
最后,再把候选词过滤一下,就可以把词库保存下来了:
# 频数过滤
candidates = {i: j for i, j in candidates.items() if j >= min_count}
# 互信息过滤(回溯)
candidates = filter_vocab(candidates, ngrams, order)
# 输出结果文件
with open(output_file, 'w') as f:
for i, j in sorted(candidates.items(), key=lambda s: -s[1]):
s = '%s %s\n' % (i.encode('utf-8'), j)
f.write(s)
评测 #
读者之前老说我写的这些算法没有标准评测,这次我就做了一个简单的评测,评测脚本是evaluate.py。
具体来说,以THUCNews为基础语料,就用上述脚本构建一个词库(总用时约40分钟),只保留前5万个词,用结巴分词加载这个5万词的词库(不用它自带的词库,并且关闭新词发现功能),这就构成了一个基于无监督词库的分词工具,然后用这个分词工具去分bakeoff 2005提供的测试集,并且还是用它的测试脚本评测,最终在PKU这个测试集上得分是:
$$\begin{array}{c|c|c}
\hline
\text{RECALL} & \text{PRECISION} & \text{F1}\\
\hline
0.777 & 0.711 & 0.742\\
\hline\end{array}$$
也就是说能做到0.742的F1。这是个什么水平呢?ICLR 2019有一篇文章叫做《Unsupervised Word Discovery with Segmental Neural Language Models》,里边提到了它在同一个测试集上的结果为F1=0.731,照这样看这个算法的结果还不差于顶会的最优结果呢~读者可以自行下载THUCNews语料来完整地复现上述结果。
另外,更多的语料可以实现更好的效果。这是我从500万篇微信公众号文章(保存为文本之后是20多G)提取出来的词库:wx.vocab.zip,供读者有需使用。保留这个词库的前5万词,然后进行同样的评测,F1明显超过了顶会的结果:
$$\begin{array}{c|c|c}
\hline
\text{RECALL} & \text{PRECISION} & \text{F1}\\
\hline
0.799 & 0.734 & 0.765\\
\hline\end{array}$$
(注:这里是为了给效果提供一个直观感知,比较可能是不公平的,因为我不确定这篇论文中的训练集用了哪些语料。但我感觉在相同时间内本文算法会优于论文的算法,因为直觉论文的算法训练起来会很慢。作者也没有开源,所以有不少不确定之处,如有错谬,请读者指正。)
总结 #
本文复现了笔者之前提出了新词发现(词库构建)算法,主要是做了速度上的优化,然后做了做简单的效果评测。但具体效果读者还是得在使用中慢慢调试了。
祝大家使用愉快~Enjoy it!
转载到请包括本文地址:https://kexue.fm/archives/6920
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Sep. 09, 2019). 《重新写了之前的新词发现算法:更快更好的新词发现 》[Blog post]. Retrieved from https://kexue.fm/archives/6920
@online{kexuefm-6920,
title={重新写了之前的新词发现算法:更快更好的新词发现},
author={苏剑林},
year={2019},
month={Sep},
url={\url{https://kexue.fm/archives/6920}},
}
April 14th, 2023
请教苏神,对于中英文混杂的语料(其实也是中文新闻,但是会有一些英文单词,比如AIGC,ChatGPT等),通过上述方式好像这些英文词汇无法提取出来。请问应该在哪里进行调整呢?
英文单词不是直接按空格分割,统计,筛除高频的全英文字母片段就行了?
October 10th, 2023
苏神,请教一下哈。就是我用了1G文本数据(5000w条句子无监督训练)占用了内存100G(新词效果在业务领域下面不错的),但是你上面说用到了20G文本语料,你是怎么加载的,分批训练20G?还是你的机器内存本身就很大?
-----------------------------------
提交过一次,但是直接失败了,又重新打了一遍
好久没跑过这个程序了,但我当时的内存顶天也就几百G吧,肯定没有你的比例那么多(100G * 20 = 2000G)
你看一下是哪一步占的内存多?另外有时候占的是虚拟内存,可能大也无妨。
最后推荐试一下我最新写的bytepiece,它的训练算法也相当于新词发现,并且占用内存相对来说更低。
CPU: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
内存: 16.0 GB, 可用 4.9 GB
在上面这台笔记本电脑(Windows 10)上一个分词初学者折腾好几天了,先是安装编译 kenlm Windows 版,昨天下午终于开始可以用 100 MB大文件试试了,结果到今早上班也没有出来,思索着是不是真的要去申请大服务器吗?死马当活马医,仔细一步步调试程序发现在单语料文件很大时内存I/O开销很厉害的问题,经过优化后12分钟处理完总计1.08 GB 语料。
我看你提交了很多改动,但貌似并非所有改动都是必须的,能否精炼出提高效率的核心代码呢?
另外就是现在可以尝试一下 https://github.com/bojone/bytepiece ,这个效率更好,并且它的训练算法本质上也是新词发现算法。
December 30th, 2023
换了H100,1T内存够了,效果不错
----------------------------------
对了,苏神,怎么找回注册的密码啊,密码忘了
私聊我重置默认密码