[Chinese Tokenization Series] 2. New Word Discovery Based on Segmentation

【中文分词系列】 2. 基于切分的新词发现 苏剑林 · 2016-08-18 · Machine Learning tokenization unsupervised NLP new word discovery

The previous post covered fast tokenization based on a dictionary and the AC automaton. Dictionary-based tokenization has an obvious advantage: it is easy to maintain and adapt to a new domain. If you move to a new domain, you only need to add the corresponding domain-specific new words to achieve reasonably good tokenization. Of course, whether a good, domain-adapted dictionary is easy to obtain depends on the specific situation. This post discusses the topic of new word discovery.

This topic was already discussed last year in The Information Entropy Method for New Word Discovery and Its Implementation, where the algorithm comes from matrix67's article Sociolinguistics in the Internet Era: Text Data Mining Based on SNS. That article mainly used three metrics — frequency, cohesion (called mutual information entropy once you take the log), and freedom (boundary entropy) — to judge whether a segment forms a word. If you've actually tried implementing this algorithm yourself, you'll find it comes with a series of difficulties. First, to obtain $n$-character words, you need to enumerate all $1\sim n$-character slices and compute statistics for each of them, which becomes painfully time-consuming once $n$ gets large. Second, and most painful of all, is computing boundary entropy — this requires grouping and counting statistics for every single segment before computing the entropy, which is an enormous amount of work. This post presents an approach that can substantially reduce the computational cost of new word discovery. more

The Algorithm

Looking back at how matrix67's algorithm performs new word discovery, we can recognize that what new word discovery really does is judge, based on the corpus, whether a given segment truly forms a word — and forming a word means being relatively independent, i.e., not further splittable. So why not flip this around? Why don't we instead look for segments that cannot form a word? As stated earlier, we say that when a segment's cohesion exceeds a certain threshold, it might form a word (and we then go on to check its boundary entropy). Doesn't that also mean that when a segment's cohesion falls below a certain threshold, it definitely cannot form a word? In that case we can simply cut it apart right there in the original corpus.

We can make a suitable simplification: if $a,b$ are two adjacent characters in the corpus, we can count the number of times $(a,b)$ appears as a pair, $\#(a,b)$, and from this estimate its frequency $P(a,b)$. We then separately count the number of occurrences of $a,b$, $\#a,\#b$, and estimate their frequencies $P(a),P(b)$. If

$$\frac{P(a,b)}{P(a)P(b)} < \alpha \quad (\alpha\text{is a given threshold greater than 1})$$

then we should cut these two characters apart in the original corpus. This operation is, in essence, using this metric to perform a preliminary segmentation of the raw corpus! Once this preliminary segmentation is done, we can count word frequencies and filter based on them.

Compared with the three metrics in matrix67's article, we now only use two: frequency and cohesion, dropping the most computationally expensive one, boundary entropy. Moreover, when computing cohesion, we only need to compute the cohesion of two-character segments, saving us from computing cohesion for longer segments as well. Yet, because our approach is based on segmentation, we not only cut down the computation drastically, but in theory can still recover words of arbitrary length!

Implementation

This looks pretty ideal — less computation, and more powerful results. But how does it perform in practice? How much does it differ from the results of matrix67's algorithm? That's something you really have to try for yourself to know for sure. I ran an experiment using 300,000 WeChat public account articles (about 1GB), and found the results to be quite satisfying — the whole process took about 10 minutes. Below is the implementation code, which is quite short, pure Python, with no third-party library dependencies, and very memory-friendly. Here texts can be either a list or an iterator (returning one article at a time), and pairing it with the tqdm library makes it easy to display progress. Finally, when computing the statistics, I applied add-$\gamma$ smoothing to mitigate unreasonable word occurrences. In the past, I would have reached for Pandas without a second thought for this kind of statistical computation, but recently I tried some of Python's native libraries and found them quite handy too~

import pymongo

db = pymongo.MongoClient().baike.items
def texts():
    for a in db.find(no_cursor_timeout=True).limit(1000000):
        yield a['content']

from collections import defaultdict #defaultdict是经过封装的dict，它能够让我们设定默认值
from tqdm import tqdm #tqdm是一个非常易用的用来显示进度的库
from math import log
import re

class Find_Words:
    def __init__(self, min_count=10, min_pmi=0):
        self.min_count = min_count
        self.min_pmi = min_pmi
        self.chars, self.pairs = defaultdict(int), defaultdict(int) #如果键不存在，那么就用int函数
                                                                  #初始化一个值，int()的默认结果为0
        self.total = 0.
    def text_filter(self, texts): #预切断句子，以免得到太多无意义（不是中文、英文、数字）的字符串
        for a in tqdm(texts):
            for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', a): #这个正则表达式匹配的是任意非中文、
                                                              #非英文、非数字，因此它的意思就是用任
                                                              #意非中文、非英文、非数字的字符断开句子
                if t:
                    yield t
    def count(self, texts): #计数函数，计算单字出现频数、相邻两字出现的频数
        for text in self.text_filter(texts):
            self.chars[text[0]] += 1
            for i in range(len(text)-1):
                self.chars[text[i+1]] += 1
                self.pairs[text[i:i+2]] += 1
                self.total += 1
        self.chars = {i:j for i,j in self.chars.items() if j >= self.min_count} #最少频数过滤
        self.pairs = {i:j for i,j in self.pairs.items() if j >= self.min_count} #最少频数过滤
        self.strong_segments = set()
        for i,j in self.pairs.items(): #根据互信息找出比较“密切”的邻字
            _ = log(self.total*j/(self.chars[i[0]]*self.chars[i[1]]))
            if _ >= self.min_pmi:
                self.strong_segments.add(i)
    def find_words(self, texts): #根据前述结果来找词语
        self.words = defaultdict(int)
        for text in self.text_filter(texts):
            s = text[0]
            for i in range(len(text)-1):
                if text[i:i+2] in self.strong_segments: #如果比较“密切”则不断开
                    s += text[i+1]
                else:
                    self.words[s] += 1 #否则断开，前述片段作为一个词来统计
                    s = text[i+1]
            self.words[s] += 1 #最后一个“词”
        self.words = {i:j for i,j in self.words.items() if j >= self.min_count} #最后再次根据频数过滤

fw = Find_Words(16, 1)
fw.count(texts())
fw.find_words(texts())

import pandas as pd
words = pd.Series(fw.words).sort_values(ascending=False)

Reference code for streaming SQL data in Python:

from sqlalchemy import *

def sql_data_generator():
    db = create_engine('mysql+pymysql://user:password@123.456.789.123/yourdatabase?charset=utf8')
    result = db.execution_options(stream_results=True).execute(text('select content from articles'))
    for t in result:
        yield t[0]

Analysis

Of course, this algorithm is not without its shortcomings — there are still some issues worth discussing. Generally speaking, in order to get finer-grained words (avoiding splitting out too many meaningless long words), we might choose a larger $\alpha$, e.g. $\alpha=10$. But this brings a problem: the cohesion between two adjacent characters within a word is not necessarily large. A typical example is "共和国" (republic) — both "和" and "国" are very common characters, and the cohesion of "和国" as a pair is not particularly high (around 3 in WeChat text). If $\alpha$ is too large, this word will end up getting cut incorrectly (in fact, it's "共和" and "国" that have high cohesion). There are many similar examples, such as "心如" in "林心如" (Ruby Lin), whose cohesion is also not very high (though of course, if the corpus is drawn from entertainment-industry text, that's a different story). On the other hand, if we set $\alpha=1$ small, then we need an even larger corpus in order for the resulting vocabulary to be complete. This is something that needs careful consideration when using this algorithm.

WeChat Dictionary

Finally, I'd like to share a word list I extracted from 300,000 recent WeChat public account articles (roughly 1GB, over 300 million characters), with a minimum cohesion of 1 and a minimum frequency of 100. As you can see from the list, words clearly associated with WeChat have all been successfully extracted. And since these are the most recent public account articles, words related to recent hot topics — the Olympics, Wang Baoqiang — were also extracted.

WeChat Dictionary: dict.txt

References

"Non-mainstream Natural Language Processing — the Forgetting Algorithm Series (II): Large-Scale Corpus Vocabulary Generation": http://www.52nlp.cn/forgetnlp2