[Chinese Word Segmentation Series] 7. Deep Learning Segmentation? All You Need is a Dictionary!

Random Combination is Enough

The method is simple: since deep learning requires a corpus, I will generate one myself. How? By randomly combining words from a dictionary. Wait, wouldn’t random combinations result in unnatural language? I was skeptical at first, but after experimenting, I found that the results were exceptionally good, sometimes even surpassing results obtained from labeled corpora.

Let’s get started. First, you need to prepare a word list with word frequencies. Word frequency is essential; without it, the effectiveness will be significantly reduced. Then, write a function to randomly select words from the dictionary with a probability proportional to their frequency and combine them into "sentences."

import numpy as np
import pandas as pd

class Random_Choice:
    def __init__(self, elements, weights):
        d = pd.DataFrame(zip(elements, weights))
        self.elements, self.weights = [], []
        for i,j in d.groupby(1):
            self.weights.append(len(j)*i)
            self.elements.append(tuple(j[0]))
        self.weights = np.cumsum(self.weights).astype(np.float64)/sum(self.weights)
    def choice(self):
        r = np.random.random()
        w = self.elements[np.where(self.weights >= r)[0][0]]
        return w[np.random.randint(0, len(w))]

Note that we group by weights to implement random sampling. The speed of random sampling depends on the number of groups, so it is best to preprocess the dictionary frequencies so that they "cluster." For example, words appearing 10001, 10002, or 10003 times can all be rounded to 10000, and words appearing 12001, 12002, 12003, or 12004 times can be rounded to 12000. This step is quite important because if you have a GPU, this will be the bottleneck for training speed.

Next, we count the character table and write a generator. These are standard procedures using the 4-tag character labeling method, adding an ’x’ tag for padding. Readers who are unclear can refer back to the article on LSTM word segmentation:

import pickle
words = pd.read_csv('dict.txt', delimiter='\t', header=None, encoding='utf-8')
words[0] = words[0].apply(unicode)
words = words.set_index(0)[1]

try:
    char2id = pickle.load(open('char2id.dic'))
except:
    from collections import defaultdict
    print u'fail to load old char2id.'
    char2id = pd.Series(list(''.join(words.index))).value_counts()
    char2id[:] = range(1, len(char2id)+1)
    char2id = defaultdict(int, char2id.to_dict())
    pickle.dump(char2id, open('char2id.dic', 'w'))

word_size = 128
maxlen = 48
batch_size = 1024

def word2tag(s):
    if len(s) == 1:
        return 's'
    elif len(s) >= 2:
        return 'b'+'m'*(len(s)-2)+'e'

tag2id = {'s':[1,0,0,0,0], 'b':[0,1,0,0,0], 'm':[0,0,1,0,0], 'e':[0,0,0,1,0]}

def data_generator():
    wc = Random_Choice(words.index, words)
    x, y = [], []
    while True:
        n = np.random.randint(1, 17)
        seq = [wc.choice() for i in range(n)]
        tag = ''.join([word2tag(i) for i in seq])
        seq = [char2id[i] for i in ''.join(seq)]
        if len(seq) > maxlen:
            continue
        else:
            seq = seq + [0]*(maxlen-len(seq))
            tag = [tag2id[i] for i in tag]
            tag = tag + [[0,0,0,0,1]]*(maxlen-len(tag))
            x.append(seq)
            y.append(tag)
        if len(x) == batch_size:
            yield np.array(x), np.array(y)
            x, y = [], []

Using the Previous Model

For the model, you can use the LSTM or CNN written previously. I used LSTM here, and the results show that LSTM has strong memory capabilities.

# Running on Keras 2.0 + Tensorflow 1.0

from keras.layers import Dense, Embedding, LSTM, TimeDistributed, Input, Bidirectional
from keras.models import Model

sequence = Input(shape=(maxlen,), dtype='int32')
embedded = Embedding(len(char2id)+1, word_size, input_length=maxlen, mask_zero=True)(sequence)
blstm = Bidirectional(LSTM(64, return_sequences=True))(embedded)
output = TimeDistributed(Dense(5, activation='softmax'))(blstm)
model = Model(inputs=sequence, outputs=output)
model.compile(loss='categorical_crossentropy', optimizer='adam')

try:
    model.load_weights('model.weights')
except:
    print u'fail to load old weights.'

for i in range(100):
    print i
    model.fit_generator(data_generator(), steps_per_epoch=100, epochs=10)
    model.save_weights('model.weights')

Using my GTX1060 and my dictionary (500,000 unique words), each epoch takes about 70s. Here, the model is saved every 10 epochs. The ‘range(100)‘ is arbitrary; since it saves every 10 epochs, you can interrupt the program at any time to check the results.

Regarding accuracy, note that because ‘mask_zero=True‘ is used, the ’x’ tag is ignored during training. However, the final training accuracy displayed includes the ’x’ tag, so the displayed accuracy will only be around 0.28 to 0.3. This is not important; we can test it after training is complete.

One final tip: the larger the character vector dimension, the better the recognition of long words usually is.

Combining with Dynamic Programming for Output

Now, we combine this with the Viterbi algorithm to output the final results via dynamic programming. Dynamic programming ensures the optimal result but reduces efficiency. Directly outputting the maximum result predicted by the classifier can yield similar results (though theoretically, it might produce invalid sequences like "bbbb"). This depends on the situation; since this is an experiment, I used Viterbi. In a production environment, for the sake of speed, it might be better to skip it (sacrificing a bit of precision for a significant increase in speed).

zy = {'be':0.5,
      'bm':0.5,
      'eb':0.5,
      'es':0.5,
      'me':0.5,
      'mm':0.5,
      'sb':0.5,
      'ss':0.5
     }

zy = {i:np.log(zy[i]) for i in zy.keys()}

def viterbi(nodes):
    paths = {'b':nodes[0]['b'], 's':nodes[0]['s']}
    for l in range(1,len(nodes)):
        paths_ = paths.copy()
        paths = {}
        for i in nodes[l].keys():
            nows = {}
            for j in paths_.keys():
                if j[-1]+i in zy.keys():
                    nows[j+i]= paths_[j]+nodes[l][i]+zy[j[-1]+i]
            k = np.argmax(nows.values())
            paths[nows.keys()[k]] = nows.values()[k]
    return paths.keys()[np.argmax(paths.values())]

def simple_cut(s):
    if s:
        s = s[:maxlen]
        r = model.predict(np.array([[char2id[i] for i in s]+[0]*(maxlen-len(s))]), verbose=False)[0][:len(s)]
        r = np.log(r)
        nodes = [dict(zip(['s','b','m','e'], i[:4])) for i in r]
        t = viterbi(nodes)
        words = []
        for i in range(len(s)):
            if t[i] in ['s', 'b']:
                words.append(s[i])
            else:
                words[-1] += s[i]
        return words
    else:
        return []

import re
not_cuts = re.compile(u'([\da-zA-Z ]+)|[.,?!\"\"'']')
def cut_word(s):
    result = []
    j = 0
    for i in not_cuts.finditer(s):
        result.extend(simple_cut(s[j:i.start()]))
        result.append(s[i.start():i.end()])
        j = i.end()
    result.extend(simple_cut(s[j:]))
    return result

The code here is the same as before, with almost no changes. The efficiency is not very high, but as mentioned, this is an experiment. If you are interested in using it in production, find a way to optimize it yourself.

Let’s Test It

Combined with my own organized dictionary, the final model achieved an accuracy of about 85% on the backoff2005 evaluation set (calculated using the score script provided by backoff2005). This accuracy depends on your dictionary.

Does it look terrible? It doesn’t matter. First, we didn’t use its training set; we used purely unsupervised training with a dictionary. This accuracy is already quite satisfactory. Second, while the accuracy seems low, the actual performance is better because it’s often just a matter of segmentation standards. For example:

1. The gold standard of the evaluation set segments "Ancient Chinese culture" as "Ancient / the / China / culture," while the model segments it as "Ancient / the / Chinese culture";

2. The gold standard segments "On the path of seeking common ground between Chinese and Western languages in input" as "In / input / on / walk / towards / Chinese / Western language / seek / same / ’s / road," while the model segments it as "In / input / on / walking towards / Chinese and Western languages / seeking common ground / ’s / road";

3. The gold standard segments "It is a question that educators care about" as "Even / is / education / specialist / care / ’s / question," while the model segments it as "Even is / educators / care / ’s / question";

A quick scan reveals many such examples. This indicates that the labeling of backoff2005 itself is not strictly standardized. We shouldn’t worry too much about this accuracy. Instead, we should notice that the model we obtained has better recognition for new words and long words. To achieve this effect, only a dictionary is needed, which is much easier than labeling data. This is very effective for customizing segmentation systems for specific fields (such as medicine, tourism, etc.).

Below are some test examples. These results are generally better than those from supervised training:

Roosevelt was one of the important leaders of the Allied camp during World War II. After the Pearl Harbor incident in 1941, Roosevelt strongly advocated declaring war on Japan and introduced price controls and rationing. With the Lend-Lease Act, Roosevelt transformed the United States into the "arsenal of democracy," making the U.S. the primary arms supplier and financier for the Allies, and also causing a significant expansion of domestic industry and achieving full employment. After the Allies gradually turned the tide in the later stages of the war, Roosevelt played a key role in shaping the post-war world order, with his influence particularly evident in the Yalta Conference and the founding of the United Nations. Later, with U.S. assistance, the Allies defeated Germany, Italy, and Japan.

Jianlin Su is the blogger of Scientific Space.

Those who are married and those who are not yet married.

E. coli is one of the most important and numerous bacteria in the intestines of humans and many animals.

Jiuzhaigou National Nature Reserve is located in Nanping County, Aba Tibetan and Qiang Autonomous Prefecture, Sichuan Province, more than 400 kilometers away from Chengdu. It is a mountain valley with a depth of more than 40 kilometers.

Modern mainlanders know Dunhuang because of the Mogao Caves. Dunhuang also became famous overseas in modern times because of the Mogao Caves. However, the Mogao Caves were first carved in the 4th century and did not attract world attention until 1900, while Dunhuang had been a famous city in the Northwest since the time of Emperor Wu of the Han Dynasty, more than a hundred years BC.

What was done to the Parthenon before is now being done to the Summer Palace, only more thoroughly and more beautifully, to the point of total destruction. All the treasures of our cathedrals added together might not equal this great and magnificent museum of the East. There were not only artistic treasures but also heaps of gold and silver products. A great achievement! A huge harvest! Two victors, one stuffed his pockets, which is visible, and the other filled his trunks.

Don’t forget, this was done using only a dictionary. Many of the segmented words, especially names, are not even in the dictionary. Isn’t this effect satisfactory enough?

Thinking About Why

Returning to our initial doubt: why can randomly combined text train a great word segmenter? The reason is that our initial dictionary-based segmentation made an assumption: sentences are formed by randomly combining words. Thus, to segment a sentence, we need to partition the string to maximize the following probability: p(w_1)p(w_2)\dots p(w_n) The final solution process uses dynamic programming.

And here, we are essentially following the same assumption—that text is randomly combined. Strictly speaking, this assumption is not true, but generally, it is sufficient, and the results prove it. What might be surprising is that a segmenter created this way can even resolve combinatorial ambiguities like "those who are married and those who are not yet married." It’s not hard to understand: when we combine words randomly, we pick them according to their frequency. This causes high-frequency words to appear more often and low-frequency words to appear less often. After a large number of repetitions, we have effectively learned the dynamic programming process through the LSTM!

This is astonishing. It means we can use LSTM to learn traditional optimization algorithms! Furthermore, by improving RNNs to solve traditional CS problems like convex hulls, triangulation, or even the TSP, the most amazing part is that it actually works quite well, sometimes even better than some approximation algorithms (https://www.zhihu.com/question/47563637). Note that problems like TSP are NP-hard and theoretically have no polynomial-time solution, but using LSTM, we might even get a linear effective solution. What a shock to the field of traditional algorithms! Using neural networks to design optimization algorithms and ultimately using optimization algorithms to optimize neural networks to achieve self-optimization—that is true intelligence!

Well, I’ve wandered off-topic. In short, effectiveness is the only standard.

Pre-trained Model

Finally, I am sharing a pre-trained model. Readers with Keras can download and test it:
seg.zip (Note: These weights may no longer be compatible with the latest versions of TensorFlow and Keras; please train your own using the code above.)

Please include the original address when reposting: https://kexue.fm/archives/4245

For more details on reposting, please refer to: Scientific Space FAQ