[Chinese Word Segmentation Series] 7. Deep Learning Segmentation with Just a Dictionary!
This series has slowly grown to its 7th post, and by now we've basically sorted out the various segmentation models. Aside from a few minor tweaks (like swapping the final classifier for a CRF), the rest is just a matter of experimenting further. Broadly speaking, if you want speed, use dictionary-based segmentation; if you want to properly resolve combinational ambiguity and new-word recognition, use more complex models, such as the LSTM or FCN approaches I introduced earlier. But the problem is that training a segmenter with deep learning requires labeled corpora, which is time-consuming and labor-intensive. The few publicly available labeled corpora that do exist are unlikely to keep up with the times — for example, hardly any public segmentation system can correctly split "扫描二维码，关注微信号" (scan the QR code and follow the WeChat account).
This post is exactly such an experiment. Using nothing but a dictionary, I trained a deep-learning-based segmenter, and it actually turned out surprisingly well! This approach can be considered semi-supervised, or even unsupervised.
Random combination is enough
The method is very simple: since deep learning needs a corpus, I'll just generate one myself. How? By randomly combining words from a dictionary. "Wait, wait — random combinations aren't natural language, are they?" I had the same doubt at first, but after experimenting, I found that this approach works remarkably well, sometimes even outperforming models trained on labeled corpora.
Without further ado, let's get started. First, we need to prepare a word list with word frequencies — frequency information is essential; without it, the results suffer significantly. Then we write a function that randomly picks words from the vocabulary with probability proportional to their frequency, and combines 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 here we group words by weight in order to implement weighted random sampling. The speed of this sampling depends on the number of groups, so it's best to preprocess the dictionary's word frequencies so that they "cluster" together — for example, rounding words that appear 10001, 10002, or 10003 times all down to 10000, and words that appear 12001, 12002, 12003, or 12004 times all down to 12000, and so on. This step matters quite a bit, because if you have a GPU, the training speed bottleneck downstream ends up being right here.
Next, we build the character vocabulary and write the generator — all fairly standard stuff, still using the 4-tag character-tagging scheme, with an added "x" tag to represent padding. Readers who aren't familiar with this can go back and read the earlier post on LSTM-based 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 = [], []
Still the same old model
For the model, either the LSTM or CNN I wrote about before will do; I used LSTM here, and the results show that LSTM has quite strong memorization capability.
# 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')
On my GTX 1060, combined with my dictionary (500,000 distinct words), each epoch takes about 70 seconds. Here I save the model every 10 epochs, and the range(100) is just an arbitrary choice — since checkpoints are saved every 10 epochs, readers can stop the program at any point and check the results.
Regarding accuracy: since mask_zero=True is used, the "x" tag is ignored during training, but the training accuracy displayed at the end still includes the "x" tag in its calculation, so the displayed accuracy caps out below 0.3 — roughly around 0.28. This doesn't matter; once training is done, we just test it directly.
One final piece of practical advice: the larger the character embedding dimension, the better the recognition of long words tends to be.
Combining with dynamic programming for output
At this point, we bring in the Viterbi algorithm, using dynamic programming to produce the final output. Dynamic programming guarantees an optimal result but comes at the cost of efficiency. Directly outputting the classifier's argmax prediction can also yield similar results (though in theory tagging sequences like "bbbb" could occur). It depends on the situation — since this is an experiment, I used Viterbi here; but in a real production environment, for the sake of speed, it's probably better not to (trading a bit of accuracy for a big boost 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 basically unchanged from before. It's not very efficient, but again, this is an experiment — if anyone's interested in deploying this to production, feel free to optimize it yourself.
Let's test it
Using the dictionary I compiled myself, the final model achieves about 85% accuracy on the backoff2005 evaluation set (as computed by backoff2005's official scoring script), though this accuracy depends heavily on your dictionary.
Sounds unimpressive? That doesn't really matter. First, we didn't use its training set at all — this was purely unsupervised training based on a dictionary, so this accuracy is already quite satisfying. Second, while the accuracy number looks low, the actual situation is better than it appears, because this is really just a matter of differing segmentation conventions in the corpus. For example:
1. The gold-standard answer in the evaluation set splits "古老的中华文化" into "古老/的/中华/文化" (ancient/'s/Chinese/culture), while the model splits it into "古老/的/中华文化" (ancient/'s/Chinese culture);
2. The gold-standard answer splits "在录入上走向中西文求同的道路" into "在/录入/上/走/向/中/西文/求/同/的/道路", while the model splits it into "在/录入/上/走向/中西文/求同/的/道路";
3. The gold-standard answer splits "更是教育学家关心的问题" into "更/是/教育学/家/关心/的/问题", while the model splits it into "更是/教育学家/关心/的/问题".
A quick scan turns up many more examples like these, which shows that the backoff2005 annotations themselves aren't especially consistent either. We shouldn't fixate too much on this accuracy number; what's more worth noting is that the model we obtained has better recognition of new and long words, and to achieve this, all we needed was a dictionary — much easier to come by than labeled data. This is extremely useful for building customized segmenters for specific domains (such as medicine, travel, and so on).
Below are some more test examples, and the results here are generally even better than those from the earlier supervised training:
Franklin D. Roosevelt was one of the important leaders of the Allied Powers during World War II. After the Pearl Harbor incident of 1941, Roosevelt pushed hard for a declaration of war against Japan, and introduced price controls and rationing. Through the Lend-Lease Act, Roosevelt turned the United States into the "arsenal of democracy," making the U.S. the main arms supplier and financier of the Allies, and also driving a massive expansion of domestic industry in the U.S., achieving full employment. In the later stages of the war, as the Allies gradually turned the tide, Roosevelt played a key role in shaping the postwar world order, an influence especially evident at the Yalta Conference and in the founding of the United Nations. Later, with U.S. assistance, the Allied forces defeated Germany, Italy, and Japan.
Su Jianlin is the blogger behind Scientific Spaces.
Those who are married and those who are not yet married.
E. coli is a major bacterium and the most abundant type of bacteria found in the intestinal tracts of humans and many animals.
The Jiuzhaigou National Nature Reserve is located within Nanping County, in the Aba Tibetan and Qiang Autonomous Prefecture, Sichuan Province, more than 400 kilometers from Chengdu, and is a valley area extending over 40 kilometers deep.
Modern people in inland China know of Dunhuang because of the Mogao Caves. Because of the Mogao Caves, Dunhuang also became famous abroad in modern times. But the Mogao Caves began to be carved as early as the 4th century, and it wasn't until 1900 that they drew worldwide attention — whereas Dunhuang, ever since the time of Emperor Wu of Han, more than a hundred years BC, had already been a renowned city in the northwest.
What was once done to the Parthenon is now being done to the Old Summer Palace, only more thoroughly, more beautifully, to the point of leaving nothing behind. All the treasures of all our cathedrals put together could perhaps not match this magnificent museum of the East. There you would find not only art treasures, but also piles of gold and silver ware. What a great achievement! What a tremendous haul! Two victors — one stuffed his pockets, that much is plain to see; the other filled his crates.
Don't forget — this was produced using nothing but a dictionary. Many of the segmented words, especially personal names, weren't even in the dictionary. Is that result satisfying enough?
Some reflections
Back to our initial puzzle: why can text made of randomly combined words train such a good segmenter? The reason lies in the fact that dictionary-based segmentation, from the start, makes an implicit assumption: a sentence is a random combination of words. Under this assumption, segmenting means splitting the string so as to maximize the following probability:
$$p(w_1)p(w_2)\dots p(w_n)$$
And the process of solving this maximization is exactly dynamic programming.
Here, we're essentially relying on the same assumption — that text is a random combination of words. Strictly speaking, this assumption doesn't hold, but in general it's good enough, and the results bear that out. What might be surprising is that the resulting segmenter can even correctly split combinationally ambiguous sentences like "结婚的和尚未结婚的" ("those who are married and those not yet married"). But this isn't really hard to understand: when we do the random combination, we pick words with probability proportional to their frequency, which means high-frequency words appear more often and low-frequency words less often. After enough repetitions of this process, we've effectively used the LSTM to learn dynamic programming itself!
This is quite remarkable — it suggests that we can use LSTMs to learn traditional optimization algorithms! Taking it further, by adapting RNNs to tackle classic CS problems — such as convex hulls, triangulation, or even TSP — the most amazing part is that this approach actually performs decently, sometimes even better than some approximation algorithms. (see this discussion) Note that problems like TSP are NP-hard, and in principle admit no polynomial-time solution — yet with LSTMs, we might even obtain an effectively linear-time solution. What a huge shock that would be to the field of classical algorithms! Using neural networks to design optimization algorithms, and then using those optimization algorithms to optimize neural networks — achieving a system that optimizes itself — now that would be true intelligence!
Uh, I've gotten off track. Anyway, results are the only real proof, I suppose.
Pretrained model available
Finally, here's a link to a model I've already trained, for readers using Keras who want to try it out:
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.