Rewriting the Previous New-Word Discovery Algorithm: Faster and Better

重新写了之前的新词发现算法：更快更好的新词发现 苏剑林 · 2019-09-09 · Machine Learning tokenization unsupervised NLP new word discovery

New-word discovery is one of the fundamental tasks in NLP: through unsupervised discovery of certain linguistic features (mostly statistical ones), we try to determine which character spans in a corpus are likely to be new words. This blog has covered the topic of "new-word discovery" a number of times before, for instance:

The Information-Entropy Method for New-Word Discovery and Its Implementation
Chinese Word Segmentation Series 2: New-Word Discovery Based on Segmentation
Chinese Word Segmentation Series 5: Unsupervised Segmentation Based on Language Models
Chinese Word Segmentation Series 7: Deep Learning Segmentation? All You Need Is a Dictionary!
Chinese Word Segmentation Series 8: A Better New-Word Discovery Algorithm
Sharing an Unsupervised Mining of Domain-Specific Vocabulary

Among these posts, I think the one with the most elegant theory is "Unsupervised Segmentation Based on Language Models," while the one with the best overall performance as a new-word discovery algorithm should be "A Better New-Word Discovery Algorithm." This post is a reimplementation of the new-word discovery algorithm from that latter piece. more

Background

Back when I wrote Chinese Word Segmentation Series 8: A Better New-Word Discovery Algorithm, I had already provided a basic implementation and validated it. However, that version was written purely in Python, and since I was only trying to quickly verify the results at the time, the code was written rather carelessly and suffered from fairly serious efficiency problems. I recently revisited this and, not wanting the algorithm to go to waste, rewrote it, making use of some tools and tricks to speed things up.

By the way, "new-word discovery" is a fairly colloquial name; a more accurate name would be "unsupervised vocabulary construction," since in principle it can build an entire vocabulary from scratch, not just "new words." Of course, you can compare it against a common-word dictionary and remove the common words to get the new words.

Details

The main changes are as follows:

1. I used the kenlm language-modeling toolkit's count_ngrams program to count ngrams. Since kenlm is written in C++, its speed is reliable, and it also has been optimized to be memory-friendly.
2. When traversing the vocabulary a second time to obtain candidate words, I used a trie structure to speed up checking whether a given ngram has appeared in a string. Tries (or their variants) are pretty much standard equipment in every dictionary-based segmentation tool, precisely because they speed up the search for whether words from a dictionary appear in a string.

Usage

The code for this release is available at:

https://github.com/bojone/word-discovery

Note that this script should only work on Linux. If you want to use it on Windows, you'll probably need to make some modifications — exactly what modifications, I don't know, so please figure it out yourself. Note that although the algorithm itself is theoretically applicable to any language, this particular implementation is, in principle, only applicable to languages whose basic unit is the "character."

Before deciding to use this library, I'd encourage readers to spend a bit of time reading Chinese Word Segmentation Series 8: A Better New-Word Discovery Algorithm, so as to get a basic understanding of the algorithm's steps and better follow the usage instructions below.

The core script in the GitHub repo is word_discovery.py, which contains the complete implementation along with a usage example. Let's briefly walk through this example below.

First, write a corpus generator that yields the corpus sentence by sentence:

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)

You don't need to understand exactly what this generator is doing — just know that it yields the raw corpus yield sentence by sentence. If you don't yet know how to write a generator, please go learn that on your own. Please don't raise questions in the comments of this post like "what format should the corpus be in" or "how should I modify this to fit my own corpus" — thanks.

By the way, since this is unsupervised training, the bigger the corpus the better, generally speaking — anywhere from a few hundred MB to several GB works. But if you only have a few MB of corpus (say, a single novel), you can also test directly with that and see some basic results (though you may need to adjust the parameters below).

Once you have the generator, configure a few parameters, and then run through the steps one by one:

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

Note that kenlm requires plain-text input with words separated by spaces, and the write_corpus function is what handles this for us; then count_ngrams calls kenlm's count_ngrams program to count the ngrams. So you'll need to compile kenlm yourself and put its count_ngrams binary in the same directory as word_discovery.py. If you have a Linux environment, compiling kenlm is quite simple — I discussed kenlm before here, which you can refer to. Once count_ngrams finishes running, the results are saved to a binary file, and KenlmNgrams is what reads that file — if your input corpus is large, this step will require quite a bit of memory. Finally, filter_ngrams is what filters the ngrams; [0, 2, 4, 6] are the mutual-information thresholds, where the first 0 is meaningless (just a placeholder), and 2, 4, 6 are the mutual-information thresholds for 2-grams, 3-grams, and 4-grams respectively — generally it's better if they increase monotonically.

At this point we've finished all the "preparatory work," and can now get down to building the vocabulary. First, build a trie out of the ngrams, and then use this trie to do a basic "pre-segmentation":

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

This pre-segmentation process was already covered in Chinese Word Segmentation Series 8: A Better New-Word Discovery Algorithm — essentially it's similar to maximum matching, where ngram fragments are joined together into candidate words that are as long as possible.

Finally, after filtering the candidate words, we can save the resulting vocabulary:

# 频数过滤
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)

Evaluation

Readers have often pointed out that these algorithms of mine lack standard evaluations, so this time I put together a simple evaluation, with the evaluation script available at evaluate.py.

Specifically, using THUCNews as the base corpus, I used the script above to build a vocabulary (taking about 40 minutes total), kept only the top 50,000 words, and loaded this 50k-word vocabulary into Jieba segmentation (without using its built-in dictionary, and with its own new-word discovery feature turned off). This gives us a segmentation tool based on an unsupervised vocabulary. I then used this tool to segment the test set provided by bakeoff 2005, and evaluated it using bakeoff's own evaluation script. The final score on the PKU test set is:

$$\begin{array}{c|c|c} \hline \text{RECALL} & \text{PRECISION} & \text{F1}\\ \hline 0.777 & 0.711 & 0.742\\ \hline\end{array}$$

In other words, it achieves an F1 of 0.742. How good is that? There's an ICLR 2019 paper called Unsupervised Word Discovery with Segmental Neural Language Models that reports an F1 of 0.731 on the same test set. Going by that, this algorithm's result doesn't fall short of a top-conference state-of-the-art result at all. Readers can download the THUCNews corpus themselves to fully reproduce the results above.

Also, more corpus data yields even better results. Here's a vocabulary I extracted from 5 million WeChat public-account articles (over 20 GB once saved as text): wx.vocab.zip, in case readers need it. Keeping the top 50,000 words of this vocabulary and running the same evaluation, the F1 clearly surpasses the top-conference result:

$$\begin{array}{c|c|c} \hline \text{RECALL} & \text{PRECISION} & \text{F1}\\ \hline 0.799 & 0.734 & 0.765\\ \hline\end{array}$$

(Note: this comparison is meant purely to give an intuitive sense of the results, and it may well be unfair, since I'm not sure exactly what training corpus that paper used. But my sense is that, given the same amount of time, the algorithm in this post would outperform the paper's algorithm, because I suspect the paper's algorithm would be quite slow to train. The authors also didn't release their code, so there's a fair amount of uncertainty here — if I'm mistaken about anything, please correct me.)

Summary

This post reimplements a new-word discovery (vocabulary construction) algorithm I proposed earlier, mainly optimizing it for speed, and then runs a simple evaluation of its performance. As for how well it works for your specific use case, you'll still need to tune it through trial and error yourself.

Enjoy using it~ Enjoy it!