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

Language Models

First, let’s briefly discuss language models.

Many readers in data mining have heard of Word2Vec and know it as a tool that can generate word vectors. Many also know how to use word vectors as features for model input. However, I believe many readers do not know why word vectors exist or why Word2Vec can generate them. The brilliance of Word2Vec itself (produced by Google, fast, effective, well-implemented in Python, etc.) has overshadowed similar products and the underlying principles. In fact, the original intention of word vectors was to better generate language models. The most classic article is likely by one of the founders of deep learning—Bengio—titled "A Neural Probabilistic Language Model." The focus of this section is on language models, not word vectors. For those interested in word vectors, you may refer to the following articles:

Deep Learning in NLP (I) Word Vectors and Language Models:
http://licstar.net/archives/328

The "How We Understand Language" series from Flickering:
http://www.flickering.cn/?s=How+We+Understand+Language

A language model is a model that calculates the conditional probability: p(w_n|w_1,w_2,\dots,w_{n-1}) where w_1,w_2,\dots,w_{n-1} are the previous n-1 words (or characters) in a sentence, and w_n is the n-th word (or character). Language models have applications in many areas, such as word segmentation, speech recognition, and machine translation. There are many methods to obtain a language model. For example, the simplest is the "statistics + smoothing" method. There are also Maximum Entropy language models, CRF language models, etc. Currently, under the deep learning framework, "Neural Network Language Models" are heavily researched. The general idea is: p(w_n|w_1,w_2,\dots,w_{n-1}) is a function of w_1,w_2,\dots,w_n. I do not know the specific form of this function, so I use a neural network to fit it. To better fit it and reduce model parameters, words are "embedded" into a real number space, represented by short vectors, and trained alongside the language model. From this perspective, word vectors are merely a byproduct of the language model.

Word vectors generated by language models can represent semantics quite well, which is interesting but also reasonable. What is semantics? For humans, semantics is a process of reasoning and understanding. Our language model predicts the next character from the previous n-1 characters, which is also a reasoning process. Since it contains reasoning components, it has the potential to capture semantics.

Unsupervised Segmentation

We seem to have talked a lot about language models, but the segmentation method introduced in this article is based on a "character-based language model."

We start from the maximum probability method. If a string s_1, s_2, \dots, s_l of length l has an optimal segmentation result w_1, w_2, \dots, w_m, then it should be the one among all possible segmentations that maximizes the product of probabilities: p(w_1)p(w_2)\dots p(w_m)

If there is no dictionary, then the words w_1, w_2, \dots, w_m naturally do not exist. However, we can use Bayes’ theorem to convert the probability of a word into the combination probability of characters: 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 the 1st, 2nd, ..., k-th characters of w, respectively. We can see that p(c_k|c_1 c_2 \dots c_{k-1}) is the character-based language model we mentioned earlier.

Of course, for a very large k, p(c_k|c_1 c_2 \dots c_{k-1}) is still difficult to estimate. Fortunately, according to our experience, the average length of a word is not very large. Therefore, an n-gram language model is sufficient, and n=4 usually yields good results.

How exactly is the segmentation performed? For a string s_1, s_2, s_3 \dots, s_l, if no segmentation is performed, its path probability should be: p(s_1)p(s_2)p(s_3)\dots p(s_l) If s_1, s_2 should be merged into one word, the 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 one word, the 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 one word, the 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) Do you see the pattern? Every segmentation method actually corresponds to the multiplication of l conditional probabilities. We are looking for the multiplication pattern that yields the maximum result. Similarly, if we know the optimal multiplication pattern, we can write out the corresponding segmentation result.

More systematically, this converts segmentation into a tagging problem. If the character language model is a 4-gram, it is equivalent to 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 part of a multi-character word

For a character s_k in a 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. Furthermore, it is obvious that ’b’ can only be followed by ’b’ or ’c’. Similarly, the only non-zero 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 long or short words are segmented. Finally, finding the optimal path is still completed by the Viterbi algorithm.

At this point, the problem turns into training the language model, which is unsupervised. We only need to focus on optimizing the language model, and both theory and practice in this area are very mature, with many existing tools available. Simply, one can use the traditional "statistics + smoothing" model; if one wants to work from semantics, the latest neural language models can be used. In short, the effectiveness of segmentation depends on the quality of the language model.

Practice: Training

First, let’s train the language model. The text data here consists of 500,000 WeChat public account articles, about 2GB in size. The language model is trained using the traditional "statistics + smoothing" method, using the kenlm tool.

kenlm is a language model tool written in C++, characterized by high speed and low memory usage. 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

Then train the language model. The input for kenlm is flexible; you don’t need to pre-generate a corpus text file, but can pass it through a pipe. For example, first write a p.py:

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

for text in db.find(no_cursor_timeout=True).limit(500000):
    # Segment the text you want to train (separated by spaces)
    # If doing a character-based model, separate each character with spaces
    print ' '.join(text['text']).encode('utf-8')

Then you 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

The arpa format is a general language model format, while klm is a binary format defined by kenlm that takes up less space. Finally, we can load it in Python:

import kenlm
model = kenlm.Model('weixin.klm')
model.score('W e i X i n', bos=False, eos=False)
'''
The score function outputs the log probability, i.e., log10(p('W e i X i n'))
bos=False, eos=False means do not automatically add start/end markers
'''

Practice: Segmentation

With the above foundation, we can create a segmentation system.

import kenlm
model = kenlm.Model('weixin.klm')
from math import log10

# Transition probabilities are manually summarized to reduce long word likelihood
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 size is nearly 3GB, so it is not provided here. Below are some examples of the segmentation results.

Water is the source of life , is the nutrient substance that humans rely on for survival and is irreplaceable . To make the team members understand the vital importance of water to life more deeply , improve the team members ’ scientific understanding and comprehension of water , and advocate for environmental awareness of water conservation and love , the Youth Environmental Knowledge Science Classroom entered Dajin Primary School to conduct a science knowledge lecture titled "Water and Life" for nearly 300 team members in the fifth and sixth grades . This activity was divided into three sessions . The speaker , Teacher Zhu , combined PPT with pictures and text to vividly communicate with the team members from four aspects : the characteristics of water , water and life , water and life , and water-saving techniques . Teacher Zhu told the team members the importance of water to the human body , explained the nutritional composition of water in detail , and reminded the team members to learn healthy and scientific drinking methods , and shared water-saving tips , hoping that all team members can take themselves as examples and strive to undertake the responsibility of "Little Water Conservation Publicity Officers" , actively leading people around them to participate in water conservation . PH test paper was used to detect the acidity and alkalinity of water . The team members all showed strong interest and took test papers home to test water quality . After the lecture , the team members all received graduation certificates for the "Little Water Conservation Publicity Officer" training course . From the excited expressions of the team members , one could feel their determination to save and love water . Protect the water environment , cherish water resources , start from small things , start from yourself . As long as everyone protects the ecology and cares for the environment , then blue water and blue sky will be closer and closer to us ! The best way to reward the editor is – Like \downarrow\downarrow Long press the QR code , follow us ! \downarrow\downarrow

As seen, the results are quite good, especially for long words. However, some cases may not fit our usual habits, such as "team members" being treated as a single word, or "and is irreplaceable" being split slightly incorrectly because certain combinations are very frequent.

The District Volunteer Association learned a few days ago that a resident family in Sanguandian Community , Lulin Street was in particular difficulty . On the afternoon of December 12 , 7 volunteers were recruited to come to the home of old man Zhou Quanlu in Lulin Sanguandian , bringing a bag of rice and a quilt . The consolation items for this support were provided by the Guangfeng District Volunteer Association Charity Fund . "Warm Winter Action" , as one of the important poverty alleviation projects of the Volunteer Association , is executed by volunteers participating in the Warm Winter Action who are responsible for distributing items to the hands of the families in difficulty identified through visits . Volunteers talked with old man Zhou Quanlu on-site , learning about his basic family situation from him and the surrounding masses . He is 62 years old this year and married a wife with mental illness . They had 2 sons , the older one is 14 years old and the younger one is 12 years old . The wife left home ten years ago and has not returned since , leaving him to live with the 2 sons . Since the sons inherited the mother’s mental illness , the older son’s various abnormal behaviors mean he cannot attend school normally and can only follow the younger son all day doing nothing , idling around , unable to do anything . Old Zhou himself is an honest farmer . This year he accidentally fell while doing farm work , and the medical expenses were more than 20,000 yuan , all raised by the village and relatives and neighbors . The house he lives in was also built with funds raised by relatives . In the messy living room , clothes are basically not washed ; if they get wet , they are just hung up to dry and then worn again . We saw the food being cooked in his house ; this is the kitchen that the whole family relies on for survival . This is the bedroom , the bedding is all dilapidated . We brought a new quilt . His niece occasionally helps him organize the hygiene and do some housework . Giving roses to others leaves a fragrance in your hand ; helping the poor and weak is an ancient virtue ; ability is not divided into large or small , and good deeds are not divided into first or last ; true feelings lie in giving . Many hands make light work . We will gather all the power of love together to pass on the warmth of the big social family , pass on social positive energy , and let the future dreams of children in difficulty fly ! Stretch out your hands , dedicate your love , let us take action together , care for families in difficulty , and let them grow up healthily and happily under the same blue sky ! If you or the people around you have clothes or quilts for boys aged 12-15 , please stretch out your loving hands to give this special family a warm winter ! ! ! Warm winter material receiving address : Guangfeng District Volunteer Association . Contact person : Mr. Duan (186 0703 4818) , Ms. Chen (138 7032 7003) . Contributed by : Duan Jianbo . Photos : Duan Jianbo . Edited by : Zhou Xiaofei .

Even for long phrases like "many hands make light work," there is good recognition. Of course, there are also many errors, such as "take all," "let us," and "please reach out your" becoming single words.

In Summary

In summary, this unsupervised segmentation method actually summarizes our usage habits and extracts common usage patterns. Therefore, it has a very good recognition effect for many long words, especially fixed idioms. At the same time, some frequent character combinations, such as "let us," are also regarded as single words. We might feel this is unreasonable, but on the other hand, since we often say "let us," why not treat it as a "word"?

In other words, word segmentation is essentially extracting fixed language patterns in advance. These patterns are not necessarily "words" in our traditional understanding but could be habitual expressions. There is a trade-off: if the segmentation granularity is too fine, the vocabulary size will not be too large, but the length of a single sentence will increase; if the granularity is too coarse, the vocabulary size may explode, but the sentence length will decrease. The method provided in this article allows for the adjustment of segmentation granularity by changing transition probabilities to suit different tasks.

Furthermore, as mentioned, the effectiveness depends on the quality of the language model, which allows us to focus solely on optimizing the language model. Since language models can be trained unsupervised, this is a significant advantage. For example, if we want a segmentation model with semantic understanding, we can use neural networks; if we care about speed, traditional statistical methods are excellent (using kenlm to get a model from 500,000 texts took less than 10 minutes). In short, it provides maximum freedom.

Reprinting: Please include the original link: https://kexue.fm/archives/3956

For more details on reprinting, please refer to: Science Space FAQ