Chinese Word Segmentation Series: 5. Unsupervised Segmentation Based on Language Models

【中文分词系列】 5. 基于语言模型的无监督分词 苏剑林 · 2016-09-12 · Machine Learning tokenization NLP unsupervised new word discovery

Chinese Word Segmentation Series 5. Unsupervised Word Segmentation Based on Language Models

So far, the previous four posts have introduced several ideas about word segmentation, including dictionary-lookup methods based on maximum probability, and character-tagging methods based on HMMs or LSTMs. These are all established research approaches — what I have done is simply summarize them. Dictionary lookup and character tagging each have their own merits, and I've long wondered: could we build an unsupervised segmentation model that only needs a large corpus to train on? In other words, how the text should be split should be decided by the corpus itself, not by anything intrinsic to the language. Put simply, given enough corpus data, the data itself should tell us how to segment.

This sounds ideal, but how do we actually do it? 《2. New Word Discovery Based on Segmentation》 offered one idea, but it wasn't thorough enough. The new-word-discovery method based on segmentation there can indeed be viewed as a kind of unsupervised segmentation approach — it uses a simple cohesion measure to decide whether a boundary should be inserted at a given point. But from the perspective of word segmentation proper, such a system is really too crude. So I've kept thinking about how to improve its precision, and got some meaningful results early on, but never arrived at a complete theory. Recently, I finally managed to fill in the gaps. Since I haven't found similar work elsewhere, this can be counted as an original contribution of mine to the field of word segmentation.

Language Models

Let me first briefly discuss language models. more

Many readers interested in data mining have already heard of Word2Vec and know it as a tool for generating word embeddings; many also know that word embeddings can be used as input features for models. But I suspect not many readers know why word embeddings exist, or why Word2Vec is able to produce them. The brilliance of Word2Vec itself (made by Google, fast, effective, well implemented in Python, etc.) has overshadowed both similar products and the underlying principles. In fact, the original purpose of word embeddings was to better construct language models — the classic reference here is one of deep learning's founding fathers, Bengio, and his paper A Neural Probabilistic Language Model. The focus of this section is language models, not word embeddings. For readers interested in word embeddings, see the following articles:

Deep Learning in NLP (Part 1): Word Embeddings and Language Models:
http://licstar.net/archives/328
The "How We Understand Language" series on Huoguang Yaoyi's blog:
http://www.flickering.cn/?s=我们是这样理解语言的

A language model is a model that computes the conditional probability

$$p(w_n|w_1,w_2,\dots,w_{n-1})$$

where $w_1,w_2,\dots,w_{n-1}$ denotes the preceding $n-1$ words (or characters) in the sentence, and $w_n$ is the $n$-th word (or character). Language models are used in many areas, such as word segmentation, speech recognition, and machine translation. There are various ways to obtain a language model: the simplest is "statistics + smoothing," and there are also maximum-entropy language models, CRF-based language models, and so on. What's studied most extensively under the current deep learning paradigm is the "neural network language model." The rough idea is: $p(w_n|w_1,w_2,\dots,w_{n-1})$ is some function of $w_1,w_2,\dots,w_n$, and since we don't know the exact form of this function, we use a neural network to fit it. To fit it better, and to reduce the number of model parameters, words are also "embedded" into a real vector space — represented by short vectors — and trained jointly with the language model. From this angle, word embeddings are really just a byproduct of the language model.

It's rather interesting — though also quite natural, in hindsight — that the word embeddings produced by a language model capture semantics fairly well. What is semantics? For humans, semantics is a process of reasoning and understanding, and our language model — predicting the next character from the preceding $n-1$ characters — is likewise a process of inference. Since it involves an element of inference, it stands to reason that it can capture some semantic information as well.

Unsupervised Word Segmentation

I've spent quite a bit of time on language models, but the segmentation method this post introduces is indeed built on the foundation of a "character-based language model."

Let's start from the maximum-probability method: if we have a string of length $l$, $s_1, s_2, \dots, s_l$, and the optimal segmentation result is $w_1, w_2, \dots, w_m$, then this should be the segmentation, among all possible ones, that maximizes the product of probabilities

$$p(w_1)p(w_2)\dots p(w_m)$$

Without a dictionary, of course, there's no such thing as these words $w_1, w_2, \dots, w_m$ to begin with. But we can use Bayes' formula to convert word-level probabilities into character-combination probabilities:

$$p(w)=p(c_1)p(c_2|c_1)p(c_3|c_1 c_2)\dots p(c_k|c_1 c_2 \dots c_{k-1})$$

where $w$ is a $k$-character word, and $c_1,c_2,\dots,c_k$ are respectively the $1,2,\dots,k$-th characters of $w$. Notice that $p(c_k|c_1 c_2 \dots c_{k-1})$ is exactly the character-level language model mentioned earlier.

Of course, for large $k$, $p(c_k|c_1 c_2 \dots c_{k-1})$ is still not easy to estimate. Fortunately, based on experience, the average word length isn't very large, so an n-gram language model suffices — and setting $n$ to 4 already works quite well.

So how exactly does the segmentation process work? Suppose we have the string $s_1, s_2, s_3\dots, s_l$. If we don't segment it at all, its path probability is

$$p(s_1)p(s_2)p(s_3)\dots p(s_l)$$

If $s_1, s_2$ should be merged into a single word, its path probability is

$$p(s_1 s_2)p(s_3)\dots p(s_l)=p(s_1)p(s_2|s_1)p(s_3)\dots p(s_l)$$

If $s_2, s_3$ should be merged into a single word, its path probability is

$$p(s_1)p(s_2 s_3)\dots p(s_l)=p(s_1)p(s_2)p(s_3|s_2)\dots p(s_l)$$

If $s_1, s_2, s_3$ should be merged into a single word, its path probability is

$$p(s_1 s_2 s_3)\dots p(s_l)=p(s_1)p(s_2|s_1)p(s_3|s_1 s_2)\dots p(s_l)$$

Notice the pattern? Every segmentation scheme is, in fact, a product of $l$ conditional probabilities, and what we're doing is searching among these products of conditional probabilities for the one that yields the largest value. Conversely, once we know the optimal multiplication pattern, we can directly read off the corresponding segmentation.

Viewed more systematically, this is really just recasting segmentation as a tagging problem. If the character-level language model uses a 4-gram, this is equivalent to performing the following character tagging:

b: single-character word, or the first character of a multi-character word
c: the second character of a multi-character word
d: the third character of a multi-character word
e: the remaining characters of a multi-character word

For a character $s_k$ in the sentence, we have

$$\begin{aligned}&p(b)=p(s_k)\\ &p(c)=p(s_k|s_{k-1})\\ &p(d)=p(s_k|s_{k-2} s_{k-1})\\ &p(e)=p(s_k|s_{k-3} s_{k-2} s_{k-1}) \end{aligned}$$

This turns the segmentation problem into a character-tagging problem, where the probability of each tag is given by the language model. Moreover, it's clear that a "b" tag can only be followed by "b" or "c," and similarly, the only nonzero transition probabilities are:

$$p(b|b),\,p(c|b),\,p(b|c),\,p(d|c),\,p(b|d),\,p(e|d),\,p(b|e),\,p(e|e)$$

The values of these transition probabilities determine whether the segmentation favors longer or shorter words. Finding the optimal path is, as always, done via the Viterbi algorithm.

At this point, the problem reduces to training a language model — and this is unsupervised. All we need to do is put effort into optimizing the language model, and this is an area that is already mature both in theory and in practice, with plenty of ready-made tools available. For a simple approach, one could just use a traditional "statistics + smoothing" model; if semantic modeling is desired, one could use a modern neural language model instead. In short, the quality of the segmentation depends on the quality of the language model.

Practice: Training

Let's start by training the language model. Here, the text data consists of about 500,000 WeChat public-account articles, roughly 2GB in size. The language model is trained using the traditional "statistics + smoothing" approach, with the tool kenlm.

kenlm is a language modeling tool written in C++, known for its speed and low memory footprint; it also provides a Python interface. First, download and compile it:

wget -O - http://kheafield.com/code/kenlm.tar.gz |tar xz 
cd kenlm
./bjam -j4
python setup.py install

Next, train the language model. kenlm's input is quite flexible — there's no need to pre-generate a corpus text file; data can instead be streamed in through a pipe. For instance, first write a script p.py:

import pymongo
db = pymongo.MongoClient().weixin.text_articles

for text in db.find(no_cursor_timeout=True).limit(500000):
    print ' '.join(text['text']).encode('utf-8')

My articles are stored in MongoDB, hence the format above; if your data is stored elsewhere, adjust accordingly. It's actually quite simple: just segment the text you want to train on (with spaces between tokens — if you're building a character-based model, put spaces between each character), then print each one out.

Then we can train the language model — here we train a 4-gram model:

python p.py|./kenlm/bin/lmplz -o 4 > weixin.arpa
./kenlm/bin/build_binary weixin.arpa weixin.klm

arpa is the generic language model format, and klm is the binary format defined by kenlm; the klm format takes up less space. Finally, we can load it in Python:

import kenlm
model = kenlm.Model('weixin.klm')
model.score('微 信', bos=False, eos=False)
'''
score函数输出的是对数概率，即log10(p('微 信'))，其中字符串可以是gbk，也可以是utf-8
bos=False, eos=False意思是不自动添加句首和句末标记符
'''

Practice: Segmentation

With the above groundwork in place, we can now build a segmentation system.

import kenlm
model = kenlm.Model('weixin.klm')

from math import log10

#这里的转移概率是人工总结的，总的来说，就是要降低长词的可能性。
trans = {'bb':1, 'bc':0.15, 'cb':1, 'cd':0.01, 'db':1, 'de':0.01, 'eb':1, 'ee':0.001}
trans = {i:log10(j) for i,j in trans.iteritems()}

def viterbi(nodes):
    paths = nodes[0]
    for l in range(1, len(nodes)):
        paths_ = paths
        paths = {}
        for i in nodes[l]:
            nows = {}
            for j in paths_:
                if j[-1]+i in trans:
                    nows[j+i]= paths_[j]+nodes[l][i]+trans[j[-1]+i]
            k = nows.values().index(max(nows.values()))
            paths[nows.keys()[k]] = nows.values()[k]
    return paths.keys()[paths.values().index(max(paths.values()))]

def cp(s):
    return (model.score(' '.join(s), bos=False, eos=False) - model.score(' '.join(s[:-1]), bos=False, eos=False)) or -100.0

def mycut(s):
    nodes = [{'b':cp(s[i]), 'c':cp(s[i-1:i+1]), 'd':cp(s[i-2:i+1]), 'e':cp(s[i-3:i+1])} for i in range(len(s))]
    tags = viterbi(nodes)
    words = [s[0]]
    for i in range(1, len(s)):
        if tags[i] == 'b':
            words.append(s[i])
        else:
            words[-1] += s[i]
    return words

Practice: Results

The language model file is nearly 3GB, so I won't be releasing it directly — readers who need it can contact me. Below are some example outputs.

Water is the source of life, a nutrient substance that humanity relies on for survival and cannot be replaced. In order to help team members better understand how critical water is to life, raise their scientific awareness of water, and advocate water conservation and environmental protection... [segmented example text, unchanged]

As you can see, the results are quite good — recognition of long words works well overall. However, some results don't quite match our intuitions; for instance, "队员们" (team members) is treated as a single word, and "且无可替代" (and cannot be replaced) is incorrectly split into "且无 可 替代," because "且无" occurs too frequently.

[Second example text, unchanged]

Here we can see that even a long compound like "拾柴火焰高" (many hands make a great fire — an idiom meaning "the more contributors, the bigger the effect") is recognized quite well. Of course, there are plenty of errors too — for example, "把所有" (all the), "让我们" (let us), and "请伸出您" (please extend your) all get treated as single words.

[Third example text, unchanged]

Summing Up

Overall, this unsupervised segmentation approach essentially summarizes our habitual usage patterns — it extracts the common character sequences we tend to use. As a result, it performs quite well on many long words, especially fixed idiomatic expressions. At the same time, we also have plenty of frequent character combinations, such as the aforementioned "让我们," which likewise get treated as single "words." We might feel this is unreasonable, but flipping it around: since we so often say "让我们," why shouldn't "让我们" be treated as a "word"?

In other words, what we're really doing when we perform word segmentation is extracting fixed usage patterns in advance — and these fixed patterns don't necessarily correspond to what we intuitively think of as "words"; they might just as well be idiomatic expressions. There is, of course, a tension here: if the segmentation granularity is too fine, the vocabulary won't be too large, but individual sentences will become longer (in terms of token count); if the granularity is too coarse, the vocabulary size may explode, but the benefit is that individual sentences become shorter. The segmentation method presented in this post allows us to adjust the granularity by tuning the transition probabilities, adapting it to different tasks.

At the same time, as already mentioned, the quality of segmentation depends on the quality of the language model, which means we only need to focus on optimizing the language model — and the language model can be trained in an unsupervised manner, which is a clear advantage. For instance, if we want a segmentation model with genuine semantic understanding, we can train the language model using neural networks; if speed is our priority, the traditional statistical approach works perfectly well (training a language model from 500,000 documents with kenlm took less than 10 minutes). All in all, this approach offers maximum flexibility.