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

HMM Model

A model is a system that processes input data and provides an optimal output. For the character tagging method of word segmentation, the input consists of n characters, and the output consists of n tags. We use \lambda = \lambda_1 \lambda_2 \dots \lambda_n to represent the input sentence and o = o_1 o_2 \dots o_n to represent the output tags. What is the "optimal" output? From a probabilistic perspective, we 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 possibilities for o, and the optimal o should be the one with the highest probability.

Note that P(o|\lambda) is a conditional probability involving 2n variables, where n is variable. In this case, it is nearly impossible to model P(o|\lambda) precisely. Even so, we can simplify it slightly. For instance, if we assume that the output of each character depends only on the current character itself, 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) Estimating P(o_k|\lambda_k) is much easier. At this point, the problem is greatly simplified because to maximize P(o|\lambda), we only need to maximize each P(o_k|\lambda_k). This assumption is known as the independence assumption.

The above simplification is one approach, but it completely ignores context and can lead to illogical results (for example, in our 4-tag system, "b" must be followed by "m" or "e", but this maximization method might produce an output like "bbb", which is invalid). Therefore, we take the opposite approach and propose a hidden model (Hidden Markov Model), much like functions and inverse functions in mathematics, thinking in reverse.

By Bayes’ Theorem, we have: 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. Thus, maximizing P(o|\lambda) is equivalent to maximizing: P(\lambda|o)P(o) Now, we can apply the independence assumption to P(\lambda|o), obtaining: P(\lambda|o) = P(\lambda_1|o_1)P(\lambda_2|o_2)\dots P(\lambda_n|o_n) Meanwhile, 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}) Consequently: 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. By setting certain P(o_k|o_{k-1}) = 0, we can exclude invalid combinations such as "bb" or "bs".

Python Implementation

The above is a basic introduction to HMM. If the reader has a foundation in probability theory, it should be easy to understand. As we can see, HMM makes significant simplifications, meaning it cannot be perfectly accurate. Therefore, HMM models are generally used to solve "parts that cannot be resolved by dictionary-based methods" (similar to what the Jieba segmentation library does). Of course, you could strengthen the Markov assumption—for example, by assuming each state depends on the previous two states—which would certainly yield a more accurate model, but the parameters would be harder to estimate.

How do we train an HMM segmentation model? It mainly involves estimating the probabilities P(\lambda_k|o_k) and P(o_k|o_{k-1}). If you have a labeled corpus, estimating these is straightforward. But what if you don’t? A dictionary will suffice. We can transform a dictionary with frequencies into an HMM model. The Python implementation is 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). The calculation of P(\lambda_k|o_k) is derived from the dictionary; for example, all single-character words in the dictionary are counted under the "s" tag, the first characters of multi-character words are counted under the "b" tag, and so on. Logarithmic probabilities are used during calculation to prevent numerical underflow.

The transition probabilities in the second part are estimated based on intuition.

The third part uses the Viterbi algorithm (dynamic programming) to find the path with the maximum probability. For probability estimation, a simple "add-one smoothing" method is used, where characters that do not appear are counted once.

The entire code is quite simple, implemented in pure Python. Of course, the efficiency might not be high, and it is for reference only. Below are some tests:

>> print ’ ’.join(hmm_cut(u’jintiantianqibucuo’))
jintian tianqi bucuo

>> print ’ ’.join(hmm_cut(u’lixiangshiyigehaohaizi’))
lixiang shi yige hao haizi

>> print ’ ’.join(hmm_cut(u’xiaomingshuoshibiyeyuzhongguokexueyuanjisuansuo’))
xiaoming shuoshi biye yu zhong guoke xueyuan jisuan suo

As we can see, HMM tends to combine characters into pairs, so the results are not perfect. However, as a supplementary segmentation method for parts that cannot be formed into words using a dictionary, it is quite excellent. For example, in "Li Xiang is a good child," it automatically discovered the name "Li Xiang," which is difficult to solve using dictionary-based methods alone.

When reposting, please include the original article address: https://kexue.fm/archives/3922

For more detailed reposting guidelines, please refer to: Scientific Space FAQ