[Chinese Word Segmentation Series] 8. A Better New Word Discovery Algorithm

The Purpose of Word Segmentation

Word segmentation is generally the first step in text mining, which seems natural, but we should ask why: Why segment words at all? Humans write and understand based on characters (in Chinese).

When a model’s memory and fitting capabilities are strong enough (or simply put, intelligent enough), we could theoretically skip segmentation and work directly with character-based models. For example, character-based text classification and question-answering systems are already being researched. However, even if these models succeed, their complexity often leads to decreased efficiency. Therefore, in many cases (especially in production environments), we seek simpler and more efficient solutions.

What is the most efficient solution? Taking text classification as an example, the simplest and most efficient is likely the "Naive Bayes Classifier." Similarly, a more modern version is FastText, which can be seen as a "neural network version" of Naive Bayes. Note that Naive Bayes relies on a "naive" assumption: that features are independent of each other. The more this assumption holds, the better Naive Bayes performs. However, for text, the context is clearly closely linked. Does this assumption still hold?

Note that when features are clearly not independent, one can consider combining features to weaken the correlation between them before using Naive Bayes. For example, in text, if characters are used as features, the naive assumption clearly fails. In the phrase "I like mathematics" (Wo xi-huan shu-xue), "xi" and "huan" are highly correlated, as are "shu" and "xue." We can combine these features into "I / like / mathematics." Now, the correlation between these three segments is much weaker, making the assumption more applicable. This process is very similar to word segmentation. Conversely, one of the main purposes of segmentation is to divide a sentence into several parts with weak correlations to facilitate further processing. From this perspective, what we segment might not necessarily be "words," but could be phrases or common collocations.

Simply put, segmentation is meant to weaken correlation and reduce dependence on word order. This is quite important even in deep learning models. Some models do not use segmentation but use CNNs, which treat combinations of several characters as features—this is also an expression of weakening feature correlation through character combination.

Algorithm Idea

Since segmentation is meant to weaken correlation, we should cut the text where correlation is weak. The article "[Chinese Word Segmentation Series] 2. New Word Discovery Based on Segmentation" followed this logic, but it assumed that text correlation was determined only by adjacent character pairs (2-grams). This is often unreasonable. For example, in the name "Lin Xinru," the cohesion of "Xinru" might not be strong, or in "Republic" (Gong-he-guo), the cohesion of "he-guo" is weak, leading to incorrect cuts. Therefore, this article improves upon the previous one. While the previous method only considered the cohesion of adjacent characters, we now consider the internal cohesion of multi-character strings (n-grams). For instance, we define the internal cohesion of a 3-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 split points, because a word should be "solid" at every point. The cohesion for strings of 4 characters or more is defined similarly. Generally, we only need to consider up to 4-grams (though we can still segment words longer than 4 characters).

By considering multi-character n-grams, we can set a higher cohesion threshold while preventing words like "Republic" (Gong-he-guo) from being mis-segmented. Because we consider 3-gram cohesion, "Republic" appears quite solid. Thus, this step follows the principle of "better to over-include than to mis-segment."

However, words like "each item" (ge-xiang) and "project" (xiang-mu) both have high internal cohesion. Because the previous step is "better to over-include," this might result in "each project" (ge-xiang-mu) being treated as a single word. Similar examples include "supporting" (zhi-cheng-zhe), "team members" (qiu-dui-yuan), and "Zhuhai Port" (Zhu-hai-gang). But in the context of 3-grams, these cases have very low cohesion. Therefore, we need a "backtracking" process. After obtaining the word list from the previous steps, we filter it again. The rule is: if an n-character word in the list was not among the original high-cohesion n-grams, it is "out."

The benefit of considering n-grams is that we can use a larger mutual information threshold to avoid mis-segmenting words while excluding ambiguous ones. For example, in "Republic," the 3-character mutual information is strong while the 2-character one is weak (mainly because "he-guo" is not solid). This also ensures that phrases like "of the situation" (de-qing-kuang) are not extracted, because with a higher threshold, neither "of the" (de-qing) nor "of the situation" (de-qing-kuang) is solid.

Detailed Algorithm

The complete algorithm steps are as follows:

Step 1, Statistics: Select a fixed n, count 2-grams, 3-grams, ..., n-grams, and calculate their internal cohesion. Keep only those segments above a certain threshold to form a set G. In this step, you can set different thresholds for 2-grams, 3-grams, ..., n-grams. They don’t have to be the same because, generally, the larger the character count, the less sufficient the statistics, making them more likely to be biased upwards. Thus, the larger the character count, the higher the threshold should be.

Step 2, Segmentation: Use the aforementioned grams to segment the corpus (rough segmentation) and count frequencies. The rule is: if a segment appears in the set G obtained in the previous step, it is not split. For example, for "each project" (ge-xiang-mu), as long as "each item" (ge-xiang) and "project" (xiang-mu) are in G, even if "each project" is not in G, it will not be split and will be preserved.

Step 3, Backtracking: After Step 2, "each project" might be extracted (since Step 2 ensures over-inclusion). Backtracking involves checking: if it is a word of n characters or fewer, check if it is in G; if not, it is removed. If it is a word longer than n characters, check if every n-character sub-segment is in G; if any sub-segment is missing, it is removed. Taking "each project" as an example, backtracking checks if "each project" is in the 3-grams; if not, it is out.

Supplementary notes for each step:

1. Using higher cohesion while considering multi-character strings is for better accuracy. For example, the 2-character "gong-he" (republic/total) might not appear in the high-cohesion set, so it would be split (e.g., in "I went to play with three people in total"), but the 3-character "Gong-he-guo" (Republic) appears in the high-cohesion set, so "gong-he" within "People’s Republic of China" will not be split.

2. Step 2 segments sentences based on the set filtered in Step 1 (think of it as rough segmentation) and then counts the results. Note that we are now counting the segmentation results, which is distinct from the cohesion set filtering in Step 1. We believe that although this segmentation is rough, the high-frequency parts are reliable, so we filter for high-frequency results.

3. Step 3: For example, because "each item" and "project" both appear in the high-cohesion segments, Step 2 will not split "each project." However, we don’t want "each project" to be a word because the cohesion between "each" and "project" is not high (high cohesion between "each" and "item" doesn’t imply high cohesion between "each" and "project"). Thus, through backtracking, "each project" is removed (one only needs to check if "each project" was in the original high-cohesion set, so the computational cost is very low).

Code Implementation

Below is a reference implementation. First, to save memory, we write an iterator to output articles one by one:

import re
import pymongo
from tqdm import tqdm
import hashlib

# Connect to MongoDB
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')))
            # Pre-process to remove non-alphanumeric/non-Chinese characters
            for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', a['text']):
                if t:
                    yield t
    print u'Finally processed %s articles' % len(texts_set)

Explanation: My articles are stored in MongoDB, so I use pymongo. If articles are in files, the approach is similar. If memory allows and there aren’t too many articles, loading them into a list is fine. hashlib is for deduplication, re is for removing meaningless characters, and tqdm shows progress.

Next, we perform 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 length of segments to consider (the n-grams mentioned earlier); I suggest at least 3. min_count is set based on requirements. Next is the cohesion filtering:

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

def is_keep(s, min_proba):
    if len(s) >= 2:
        # Calculate internal cohesion
        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 mentioned, different thresholds can be set for different lengths. I used a dictionary for this. Personally, I find that thresholds increasing by a factor of 5 work well, though this depends on the data size. Next, define the segmentation function and perform 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)}

The main time is spent on n-gram statistics and the final text segmentation.

Dictionary Sharing

Finally, I am sharing the lexicon built from 3 million WeChat articles using the above algorithm. It has not undergone any manual post-processing. I am sharing it for general use (it contains many WeChat-related terms that many popular segmentation tools lack, which is quite valuable) and for readers to verify the results.

Resource Download: Lexicon from 3m WeChat Articles for New Word Discovery.zip

Reprinting: Please include the original article address: https://kexue.fm/archives/4256

Detailed Reprinting Guidelines: Please refer to "Scientific Space FAQ"