Chinese Word Segmentation Series: 8. A Better New Word Discovery Algorithm

【中文分词系列】 8. 更好的新词发现算法 苏剑林 · 2017-03-11 · Machine Learning tokenization vocabulary new word discovery

【Chinese Word Segmentation Series】 8. A Better New-Word Discovery Algorithm

Readers who have followed this series in order will have noticed that it already offers two "from scratch" unsupervised segmentation schemes. The first is 《【Chinese Word Segmentation Series】 2. New Word Discovery Based on Segmentation》, which builds a vocabulary using the cohesion (mutual information) of adjacent characters — once you have a vocabulary, you can do dictionary-based segmentation. The second is 《【Chinese Word Segmentation Series】 5. Unsupervised Segmentation Based on a Language Model》, which can basically be said to provide a complete unsupervised segmentation method that stands on its own, independent of other prior work.

Overall, though, the first method always felt quick and satisfying, but crude; the second felt good and powerful, but overly complex (Viterbi decoding being one bottleneck). Could we strike a compromise between the two? That is exactly what this post delivers, achieving a balance between speed and quality. And why do I say "better"? Because I've spent quite a while working on vocabulary construction, and the vocabularies I built in the past never quite satisfied me (or rather, never satisfied myself) — glancing over the resulting word lists, you could always spot a fair number of unreasonable entries, and using them in practice required a lot of manual filtering. This time, though, the vocabulary generated in one pass has far fewer obviously unreasonable entries; if you don't look closely, you might not even notice any.

The Purpose of Segmentation

Segmentation is usually taken as the first step in text mining, as if it were the natural thing to do — but we should actually ask why. Why segment at all? After all, people write and read character by character.

When a model's memory and fitting capacity are strong enough (or, to put it simply, smart enough), we don't need segmentation at all — we can work directly with character-based models, such as character-based text classification or QA systems, which people have long been researching. But even when such models succeed, the added model complexity brings a drop in efficiency. So, quite often (especially in production environments), we look for simpler, more efficient solutions.

Which approach is most efficient? Taking text classification as an example, probably the simplest and most efficient method is the "naive Bayes classifier." Similarly, a more modern counterpart is FastText, which can be seen as a "neural network version" of naive Bayes. Note that naive Bayes rests on a naive assumption: that features are mutually independent. The more this assumption holds, the better naive Bayes performs. But for text, context is obviously tightly interconnected — does this assumption still hold?

Notice that when features are clearly not independent, one can consider combining features so that the correlations between the combined features are weaker, and then apply naive Bayes. For text, if characters are used as features, the naive assumption clearly fails — for instance, in "我喜欢数学" ("I like mathematics"), "喜" and "欢", as well as "数" and "学", are each clearly correlated. In this case, we can combine features to get "我/喜欢/数学" ("I/like/mathematics"), so that the correlation among these three segments is no longer so strong, and naive Bayes becomes applicable. You can see that this process looks a lot like segmentation — or, conversely, one of the main purposes of segmentation is precisely to split a sentence into several parts whose mutual correlation is relatively weak, making further processing easier. From this angle, what gets split out need not necessarily be "words" — it could be phrases, common collocations, and so on.

Put simply, segmentation exists to weaken correlation and reduce dependence on word order — and this matters quite a lot even in deep learning models. Some models skip segmentation but use CNNs instead, i.e., they take combinations of several characters as features; this is likewise a way of weakening inter-feature correlation through character combination.

Sketch of the Algorithm

Since segmentation is meant to weaken correlation, when we segment, we are essentially cutting at points where correlation is weak. The article 《【Chinese Word Segmentation Series】 2. New Word Discovery Based on Segmentation》 is really making this same point, except there it assumed that the correlation in text is determined solely by adjacent character pairs (2-grams), which is often unreasonable. For instance, in "林心如" (a name), the pair "心如" is weak, and in "共和国" ("republic"), the pair "和国" is weak — the cohesion (correlation) isn't very strong in either case, making them prone to mis-segmentation. So this post improves on the earlier one: instead of only considering the cohesion of adjacent characters, it simultaneously considers the internal cohesion of multi-character strings (n-grams). For example, define the internal cohesion of a three-character string as:

$$\min\left\{\frac{P(abc)}{P(ab)P(c)},\frac{P(abc)}{P(a)P(bc)}\right\}$$

This definition essentially means enumerating all possible ways of splitting the string, since a genuine word should be "solid" at every possible cut point. The cohesion of four-character (or longer) strings is defined analogously. In general, we only need to go up to 4-grams (though, note, we can still extract words longer than four characters).

By taking multi-character strings into account, we can set a relatively high cohesion threshold while still preventing words like "共和国" from being mis-segmented, because once we consider three-character cohesion, "共和国" turns out to be quite solid. So this step follows the principle "better to let something through than to cut it wrongly."

However, both "各项" ("each item...") and "项目" ("project") have high internal cohesion, and since the previous step follows "better to let something through," this causes "各项目" to also be treated as a word — similar spurious examples include "支撑着", "球队员", "珠海港", and many more. But looking at 3-grams, the cohesion of these cases turns out to be quite low. So we need a "backtracking" step: after obtaining the vocabulary from the earlier steps, we filter it once more — the rule being that if an n-character word inside it does not appear among the original high-cohesion n-grams, it gets eliminated.

So the benefit of considering n-grams is that, even with a relatively large mutual-information threshold, we avoid mis-segmenting words while also excluding ambiguous, borderline cases. Take "共和国": the three-character mutual information is strong, while the two-character version is weak (mainly because "和国" isn't solid enough); yet we can also ensure that something like "的情况" doesn't get carved out, because with a slightly higher threshold, neither "的情" nor "的情况" is solid enough.

The Detailed Algorithm

The complete algorithm proceeds as follows:

Step 1, Counting: Choose some fixed $n$, count the 2-grams, 3-grams, …, n-grams, compute their internal cohesion, and keep only those segments above a certain threshold, forming a set $G$. In this step, different thresholds can be set for 2-grams, 3-grams, …, n-grams — they need not be the same, since longer strings generally have sparser statistics and are more likely to show inflated cohesion values, so the threshold should increase with string length.
Step 2, Segmentation: Use the above grams to segment the corpus (a rough segmentation) and count frequencies. The rule for segmentation is: as long as a segment appears in the set $G$ obtained in the previous step, it is not split. For example, for "各项目", as long as both "各项" and "项目" are in $G$, then even though "各项目" itself is not in $G$, it is still kept unsplit.
Step 3, Backtracking: After Step 2, "各项目" will have been extracted as a whole (since Step 2 guarantees erring on the side of not cutting). Backtracking means checking: if it is a word of length less than or equal to $n$ characters, check whether it is in $G$ — if not, it is eliminated; if it is longer than $n$ characters, check whether each of its $n$-character sub-segments is in $G$ — if even one sub-segment is missing, it is eliminated. Taking "各项目" as an example again, backtracking checks whether "各项目" is present among the 3-grams; if not, it gets eliminated.

Some additional notes on each step:

1. Using a relatively high cohesion threshold, while jointly considering multi-character strings, is meant to improve precision. For example, the two-character "共和" won't appear in the high-cohesion set, so it will be split (e.g., in "我一共和三个人去玩", "共和" gets split apart), but the three-character "共和国" does appear in the high-cohesion set, so within "中华人民共和国" the "共和" part won't be split.
2. Step 2 uses the set filtered out in Step 1 to segment sentences (you can think of this as a rough segmentation), and then computes statistics over these "rough segmentation results." Note that we are now counting the segmentation results themselves, which is a separate matter from the cohesion-based filtering in Step 1. We assume that even though this segmentation is rough, the high-frequency portion of it is still trustworthy, so we filter out the high-frequency part.
3. In Step 3, for example, since both "各项" and "项目" appear among the high-cohesion segments, Step 2 will also fail to split "各项目" apart. But we don't want "各项目" to become a word, because the cohesion between "各" and "项目" is not actually high (the fact that "各" and "项" have high cohesion does not imply that "各" and "项目" do). So through backtracking, we remove "各项目" (we only need to check whether "各项目" is present in the originally computed high-cohesion set, so this step is computationally cheap).

Implementation

Below is a reference implementation. First, to save memory, let's write an iterator that yields articles one at a time:

import re
import pymongo
from tqdm import tqdm
import hashlib

db = pymongo.MongoClient().weixin.text_articles
md5 = lambda s: hashlib.md5(s).hexdigest()

def texts():
    texts_set = set()
    for a in tqdm(db.find(no_cursor_timeout=True).limit(3000000)):
        if md5(a['text'].encode('utf-8')) in texts_set:
            continue
        else:
            texts_set.add(md5(a['text'].encode('utf-8')))
            for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', a['text']):
                if t:
                    yield t
    print u'最终计算了%s篇文章' % len(texts_set)

A bit of explanation: my articles are stored in MongoDB, so I read them with pymongo — if your articles are stored in files, the approach is analogous. Of course, if you have enough memory and not too many articles, there's nothing wrong with just loading all the articles into memory as a list. I import hashlib to deduplicate articles; I import the regular-expression module re to strip out meaningless characters beforehand (anything that isn't Chinese, English, or a digit); and I import tqdm to display progress.

Next, straightforward counting:

from collections import defaultdict
import numpy as np

n = 4
min_count = 128
ngrams = defaultdict(int)

for t in texts():
    for i in range(len(t)):
        for j in range(1, n+1):
            if i+j <= len(t):
                ngrams[t[i:i+j]] += 1

ngrams = {i:j for i,j in ngrams.iteritems() if j >= min_count}
total = 1.*sum([j for i,j in ngrams.iteritems() if len(i) == 1])

Here $n$ is the maximum segment length to consider (the n-grams mentioned earlier) — I'd suggest setting it to at least 3; min_count is set according to your needs. Next comes the cohesion filtering:

min_proba = {2:5, 3:25, 4:125}

def is_keep(s, min_proba):
    if len(s) >= 2:
        score = min([total*ngrams[s]/(ngrams[s[:i+1]]*ngrams[s[i+1:]]) for i in range(len(s)-1)])
        if score > min_proba[len(s)]:
            return True
    else:
        return False

ngrams_ = set(i for i,j in ngrams.iteritems() if is_keep(i, min_proba))

As already mentioned, different thresholds can be set for grams of different lengths, so a dictionary is used to specify them. Personally, I find it works well to have the thresholds form a geometric sequence with a common ratio of 5, though this really depends on the size of your data. Next, we define the segmentation function and compute segmentation statistics:

def cut(s):
    r = np.array([0]*(len(s)-1))
    for i in range(len(s)-1):
        for j in range(2, n+1):
            if s[i:i+j] in ngrams_:
                r[i:i+j-1] += 1
    w = [s[0]]
    for i in range(1, len(s)):
        if r[i-1] > 0:
            w[-1] += s[i]
        else:
            w.append(s[i])
    return w

words = defaultdict(int)
for t in texts():
    for i in cut(t):
        words[i] += 1

words = {i:j for i,j in words.iteritems() if j >= min_count}

Finally, backtracking:

def is_real(s):
    if len(s) >= 3:
        for i in range(3, n+1):
            for j in range(len(s)-i+1):
                if s[j:j+i] not in ngrams_:
                    return False
        return True
    else:
        return True

w = {i:j for i,j in words.iteritems() if is_real(i)}

Most of the algorithm's runtime is spent on computing n-gram statistics and on the final text segmentation step.

Sharing the Vocabulary

Finally, I'm sharing the vocabulary built with the above algorithm from three million WeChat articles, without any manual post-processing. I'm releasing it both for general use (it contains quite a few WeChat-related terms that many popular segmentation tools lack, so it should be genuinely useful) and so that others can verify the results for themselves.

Download: 300w微信文章做新词发现的词库.zip