[Chinese Word Segmentation Series] 3. The Character-Tagging Approach and the HMM Model

【中文分词系列】 3. 字标注法与HMM模型 苏剑林 · 2016-08-19 · Machine Learning probability Python tokenization HMM NLP

In this article, we take a pause from the dictionary-lookup method and turn instead to introducing the character-tagging approach. As mentioned earlier, character tagging performs segmentation by attaching a label to each character in a sentence — for instance, using the 4-tag scheme mentioned before (single: a character that forms a word on its own; begin: the first character of a multi-character word; middle: the middle part of a word with three or more characters; end: the last character of a multi-character word — each abbreviated to its first letter). Under this scheme, "为人民服务" ("serve the people") would be tagged as "sbebe". The 4-tag scheme is not the only option; there is also, for example, a 6-tag scheme. In theory, more fine-grained tagging schemes should, in principle, yield better results, but too many tags can also run into the problem of insufficient training samples for each tag. In practice, the 4-tag and 6-tag schemes are the most commonly used.

It's worth noting that this idea of tagging each character and thereby turning the problem into a sequence-to-sequence learning task is not just a segmentation method — it's a general approach to a large class of natural language problems. Named entity recognition, for example, can likewise be tackled with tagging methods. Coming back to segmentation, models that perform word segmentation via character tagging include the Hidden Markov Model (HMM), the Maximum Entropy model (ME), and the Conditional Random Field model (CRF), and their accuracy increases in that order. It's said that the best-performing segmenter in current public benchmarks is a 4-tag CRF. In this article, however, we're going to discuss the least accurate of the three — the HMM. In my view, it isn't really a specific model so much as a general-purpose idea for tackling a broad class of problems — a discipline of simplifying problems.

All of this starts with probabilistic models. More below.

The HMM Model

By "model" we mean something that processes our input data and produces the optimal output. For the character-tagging approach to segmentation, the input is a sequence of $n$ characters, and the output is a sequence of $n$ labels. Let $\lambda=\lambda_1 \lambda_2 \dots \lambda_n$ denote the input sentence and $o=o_1 o_2 \dots o_n$ the output. So what counts as the optimal output? From a probabilistic standpoint, we naturally want to maximize the following conditional probability:

$$\max P(o|\lambda) =\max P(o_1 o_2 \dots o_n|\lambda_1 \lambda_2 \dots \lambda_n)$$

In other words, there are many possible values of $o$, and the optimal $o$ should be the one with the highest probability, i.e. $o$.

Note that $P(o|\lambda)$ is a conditional probability over $2n$ variables, and moreover $n$ is itself variable in length. In this situation, it's essentially impossible to model $P(o|\lambda)$ exactly. Even so, we can make some simplifications — for instance, if we assume that the output for each character depends only on that character itself, then we have

$$P(o_1 o_2 \dots o_n|\lambda_1 \lambda_2 \dots \lambda_n) = P(o_1|\lambda_1)P(o_2|\lambda_2)\dots P(o_n|\lambda_n)$$

and estimating $P(o_k|\lambda_k)$ becomes much easier. This also greatly simplifies the problem, since maximizing $P(o|\lambda)$ now just requires maximizing each individual $P(o_k|\lambda_k)$. This assumption we've made is called the independence assumption.

The above simplification is one possible approach, but it completely ignores context, and it can produce unreasonable results (for instance, under our 4-tag scheme, a "b" tag can only be followed by "m" or "e", but with this "maximize each character independently" approach we might end up with an output like "bbb", which is invalid). So instead we flip things around and introduce a hidden model (the Hidden Markov Model) — much like how a function and its inverse function relate to each other in mathematics, we think about the problem in reverse.

By Bayes' rule, we get

$$P(o|\lambda)=\frac{P(o,\lambda)}{P(\lambda)}=\frac{P(\lambda|o)P(o)}{P(\lambda)}$$

Since $\lambda$ is the given input, $P(\lambda)$ is a constant and can be ignored. So maximizing $P(o|\lambda)$ is equivalent to maximizing

$$P(\lambda|o)P(o)$$

Now we can apply an independence assumption to $P(\lambda|o)$, giving

$$P(\lambda|o)=P(\lambda_1|o_1)P(\lambda_2|o_2)\dots P(\lambda_n|o_n)$$

Likewise, for $P(o)$ we have

$$P(o)=P(o_1)P(o_2|o_1)P(o_3|o_1,o_2)\dots P(o_n|o_1,o_2,\dots,o_{n-1})$$

At this point we can make a Markov assumption: each output depends only on the previous output. Then:

$$P(o)=P(o_1)P(o_2|o_1)P(o_3|o_2)\dots P(o_n|o_{n-1})\sim P(o_2|o_1)P(o_3|o_2)\dots P(o_n|o_{n-1})$$

and so

$$P(\lambda|o)P(o)\sim P(\lambda_1|o_1) P(o_2|o_1) P(\lambda_2|o_2) P(o_3|o_2) \dots P(o_n|o_{n-1}) P(\lambda_n|o_n)$$

We call $P(\lambda_k|o_k)$ the emission probability, and $P(o_k|o_{k-1})$ the transition probability. At this stage, we can set certain values of $P(o_k|o_{k-1})=0$ to exclude invalid combinations such as "bb" or "bs".

Python Implementation

That covers the basics of the HMM. If the reader has some background in probability theory, this should not be too hard to follow. As you can see, the HMM makes a great many simplifications to the problem — simplifications so drastic that it can't possibly be very precise. Because of this, HMM models are generally used to handle "the parts that the dictionary-lookup method can't resolve" (similar to what Jieba does). Of course, you could strengthen the Markov assumption — for example, assuming each state depends on the previous two states — which would certainly give a more accurate model, but the model's parameters would then become much harder to estimate.

How do we train an HMM segmentation model? Mainly, it comes down to estimating the two probabilities $P(\lambda_k|o_k)$ and $P(o_k|o_{k-1})$. If we have a corpus of tagged data, estimating these two probabilities shouldn't be too hard. But what if we don't have one? A dictionary alone will do in a pinch. We can convert a dictionary with frequency counts into an HMM model, implemented in Python as follows:

from collections import Counter
from math import log

hmm_model = {i:Counter() for i in 'sbme'}

with open('dict.txt') as f:
    for line in f:
    lines = line.decode('utf-8').split(' ')
    if len(lines[0]) == 1:
    hmm_model['s'][lines[0]] += int(lines[1])
    else:
    hmm_model['b'][lines[0][0]] += int(lines[1])
    hmm_model['e'][lines[0][-1]] += int(lines[1])
    for m in lines[0][1:-1]:
    hmm_model['m'][m] += int(lines[1])

log_total = {i:log(sum(hmm_model[i].values())) for i in 'sbme'}

trans = {'ss':0.3,
    'sb':0.7,
    'bm':0.3,
    'be':0.7, 
    'mm':0.3,
    'me':0.7,
    'es':0.3,
    'eb':0.7
 }

trans = {i:log(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 hmm_cut(s):
    nodes = [{i:log(j[t]+1)-log_total[i] for i,j in hmm_model.iteritems()} for t in s]
    tags = viterbi(nodes)
    words = [s[0]]
    for i in range(1, len(s)):
        if tags[i] in ['b', 's']:
            words.append(s[i])
        else:
            words[-1] += s[i]
    return words

The first part of the code uses a dictionary to represent $P(\lambda_k|o_k)$; $P(\lambda_k|o_k)$ is computed from the dictionary — for example, all single-character words in the dictionary are counted under the "s" tag, the first character of every multi-character word is counted under the "b" tag, and so on. Log probabilities are used during the computation to prevent underflow.

The second part, the transition probabilities, are estimated directly by intuition.

The third part uses the Viterbi algorithm — dynamic programming — to find the maximum-probability path. For probability estimation, we simply used add-one smoothing, counting every unseen character once.

The whole thing is quite simple, implemented in pure Python. Of course, it's not necessarily very efficient — it's provided for reference only. Here's a bit of testing:

\>>print ' '.join(hmm_cut(u'今天天气不错'))
今天 天气 不错
\>>print ' '.join(hmm_cut(u'李想是一个好孩子'))
李想 是 一个 好 孩子
\>>print ' '.join(hmm_cut(u'小明硕士毕业于中国科学院计算所'))
小明 硕士 毕业 于 中 国科 学院 计算 所

As you can see, the HMM tends to lump two characters together, so the results are not perfect. However, as a supplementary segmentation method for parts that the dictionary-lookup approach fails to split into words, it performs quite well — for instance, in "李想是一个好孩子" ("Li Xiang is a good child"), it automatically identified the personal name "李想" ("Li Xiang"), something that's very hard to achieve with dictionary lookup alone.