【Chinese Word Segmentation Series】 6. Chinese Word Segmentation Based on a Fully Convolutional Network

【中文分词系列】 6. 基于全卷积网络的中文分词 苏剑林 · 2017-01-13 · Machine Learning deep learning tokenization NLP

I've already written about using LSTM for word segmentation, and today's post covers a CNN-based approach — more precisely an FCN, a fully convolutional network. Actually, the main purpose of this model wasn't really to study Chinese word segmentation, but to practice TensorFlow. I've been using Keras for two years now, so I'm quite familiar with it, and I've gradually noticed some of its shortcomings — for instance, it's inconvenient when handling variable-length inputs, and adding custom constraints is fairly difficult. So I decided to just try native TensorFlow, and after trying it, it turned out not to be that complicated after all. Well, it's still Python — how complicated could it really be? This post is essentially an exercise in handling variable-length-input tasks with TensorFlow, using Chinese word segmentation as the example, and at the end I've added hard decoding, which combines deep learning with dictionary-based segmentation.

CNN

Also, a bit about FCNs. Looking at it from the perspective of language tasks, a (1D) convolution is essentially an n-gram model. From this angle, CNNs are actually far more natural for language than RNNs — RNNs seem specifically designed for sequence tasks, whereas CNNs are more of an extension of the traditional n-gram model. Another point: both CNNs and RNNs use weight sharing, which might look like just a compromise to reduce computation, but in fact there's a deeper reason behind it. Weight sharing in CNNs is an inevitable consequence of translation invariance, not merely a choice made to reduce computation. Think about it: if you shift an image slightly, or insert a meaningless space at the beginning of a sentence (causing all subsequent characters to shift back by one position), the result should be similar or even identical — and this requires the convolution to necessarily be weight-shared, i.e., the weights must not depend on position. more

RNN-based models, especially LSTM, have long dominated language tasks, but recently the gated convolutional network GCNN is said to have surpassed LSTM (by a small margin) on language modeling — which suggests that CNNs still have plenty of potential even in language tasks. The advantage of LSTM is its ability to capture long-range dependencies, but in reality, truly long-range dependencies are rare in language tasks. Even in language modeling, the probability of the next character really only depends on the preceding few characters, not the entire preceding text — and CNNs can achieve the same effect just by stacking more layers or using larger convolution kernels. But CNNs have another particular advantage: they're much faster than RNNs. When accelerated with a GPU, convolution is exactly what GPUs are best at, since GPUs were originally designed for image processing — the speedup GPUs give to CNNs is far more pronounced than what they give to RNNs...

All of this makes me favor CNNs more, much like the Facebook team does (that GCNN was their work). A fully convolutional network uses convolutions from start to finish, which lets it handle variable-length inputs — and it's especially well-suited to tasks where the input length is variable but the input and output lengths are equal.

Corpus

The task in this post is to build a Chinese word segmentation system with an FCN, still following the sbme character-tagging approach — readers unfamiliar with this can refer back to earlier posts in the series. Since this is supervised training, we need to choose a corpus. There are two good options: one is the 2014 People's Daily corpus, and the other is the corpus from the backoff2005 competition, which also comes with an evaluation script. I've experimented with both.

If using the 2014 People's Daily corpus, the preprocessing code is:

import glob
import re
from tqdm import tqdm
from collections import Counter, defaultdict
import json
import numpy as np
import os

txt_names = glob.glob('./2014/*/*.txt')

pure_texts = []
pure_tags = []
stops = u'，。！？；、：,\.!\?;:\n'
for name in tqdm(iter(txt_names)):
    txt = open(name).read().decode('utf-8', 'ignore')
    txt = re.sub('/[a-z\d]*|\[|\]', '', txt)
    txt = [i.strip(' ') for i in re.split('['+stops+']', txt) if i.strip(' ')]
    for t in txt:
        pure_texts.append('')
        pure_tags.append('')
        for w in re.split(' +', t):
            pure_texts[-1] += w
            if len(w) == 1:
                pure_tags[-1] += 's'
            else:
                pure_tags[-1] += 'b' + 'm'*(len(w)-2) + 'e'

If using the backoff2005 corpus, the preprocessing code is:

import re
from tqdm import tqdm
from collections import Counter, defaultdict
import json
import numpy as np
import os

pure_texts = []
pure_tags = []
stops = u'，。！？；、：,\.!\?;:\n'
for txt in tqdm(open('msr_training.txt')):
    txt = [i.strip(' ').decode('gbk', 'ignore') for i in re.split('['+stops+']', txt) if i.strip(' ')]
    for t in txt:
        pure_texts.append('')
        pure_tags.append('')
        for w in re.split(' +', t):
            pure_texts[-1] += w
            if len(w) == 1:
                pure_tags[-1] += 's'
            else:
                pure_tags[-1] += 'b' + 'm'*(len(w)-2) + 'e'

Then sort the corpus by string length. This is because although TensorFlow supports variable-length inputs, during training all sequences within a batch need to have equal length, so we need to do a simple clustering (grouping by length). Next we build a mapping table — this is all fairly standard stuff:

ls = [len(i) for i in pure_texts]
ls = np.argsort(ls)[::-1]
pure_texts = [pure_texts[i] for i in ls]
pure_tags = [pure_tags[i] for i in ls]

min_count = 2
word_count = Counter(''.join(pure_texts))
word_count = Counter({i:j for i,j in word_count.iteritems() if j >= min_count})
word2id = defaultdict(int)
id_here = 0
for i in word_count.most_common():
    id_here += 1
    word2id[i[0]] = id_here

json.dump(word2id, open('word2id.json', 'w'))
vocabulary_size = len(word2id) + 1
tag2vec = {'s':[1, 0, 0, 0], 'b':[0, 1, 0, 0], 'm':[0, 0, 1, 0], 'e':[0, 0, 0, 1]}

Build a generator to produce training samples for each batch. Note that here batch_size is only an upper bound, since each batch requires all sentences to have the same length, meaning not every batch will actually reach a size of 1024.

batch_size = 1024

def data():
    l = len(pure_texts[0])
    x = []
    y = []
    for i in range(len(pure_texts)):
        if len(pure_texts[i]) != l or len(x) == batch_size:
            yield x,y
            x = []
            y = []
            l = len(pure_texts[i])
        x.append([word2id[j] for j in pure_texts[i]])
        y.append([tag2vec[j] for j in pure_tags[i]])

Model

Now it's time to build the model, which is actually quite simple: just three convolutional layers stacked together. We don't specify an input length — it's set to None — and we set padding='SAME' so the output has the same length as the input (for this reason, we also don't use pooling). ReLU is used as the activation in between, softmax at the end, and cross-entropy as the loss function — and that's it. With TensorFlow, you have to write out every step yourself, but it's really not that complicated either.

import tensorflow as tf

embedding_size = 128
keep_prob = tf.placeholder(tf.float32)

embeddings = tf.Variable(tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0))
x = tf.placeholder(tf.int32, shape=[None, None])
embedded = tf.nn.embedding_lookup(embeddings, x)
embedded_dropout = tf.nn.dropout(embedded, keep_prob)
W_conv1 = tf.Variable(tf.random_uniform([3, embedding_size, embedding_size], -1.0, 1.0))
b_conv1 = tf.Variable(tf.random_uniform([embedding_size], -1.0, 1.0))
y_conv1 = tf.nn.relu(tf.nn.conv1d(embedded_dropout, W_conv1, stride=1, padding='SAME') + b_conv1)
W_conv2 = tf.Variable(tf.random_uniform([3, embedding_size, embedding_size/4], -1.0, 1.0))
b_conv2 = tf.Variable(tf.random_uniform([embedding_size/4], -1.0, 1.0))
y_conv2 = tf.nn.relu(tf.nn.conv1d(y_conv1, W_conv2, stride=1, padding='SAME') + b_conv2)
W_conv3 = tf.Variable(tf.random_uniform([3, embedding_size/4, 4], -1.0, 1.0))
b_conv3 = tf.Variable(tf.random_uniform([4], -1.0, 1.0))
y = tf.nn.softmax(tf.nn.conv1d(y_conv2, W_conv3, stride=1, padding='SAME') + b_conv3)

y_ = tf.placeholder(tf.float32, shape=[None, None, 4])
cross_entropy = - tf.reduce_sum(y_ * tf.log(y + 1e-20))
train_step = tf.train.AdamOptimizer().minimize(cross_entropy)
correct_prediction = tf.equal(tf.argmax(y, 2), tf.argmax(y_, 2))
accuracy = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))

That's the entire model. Now for training. Once again, I recommend using tqdm to help display progress (showing progress, speed, and accuracy in real time) — it's simply a perfect match.

init = tf.global_variables_initializer()
sess = tf.Session()
sess.run(init)
nb_epoch = 300

for i in range(nb_epoch):
    d = tqdm(data(), desc=u'Epcho %s, Accuracy: 0.0'%(i+1))
    k = 0
    accs = []
    for xxx,yyy in d:
        k += 1
        if k%100 == 0:
            acc = sess.run(accuracy, feed_dict={x: xxx, y_: yyy, keep_prob:1})
            accs.append(acc)
            d.set_description('Epcho %s, Accuracy: %s'%(i+1, acc))
        sess.run(train_step, feed_dict={x: xxx, y_: yyy, keep_prob:0.5})
    print u'Epcho %s Mean Accuracy: %s'%(i+1, np.mean(accs))

saver = tf.train.Saver()
saver.save(sess, './ckpt/cw.ckpt')

Output from the training process (this was trained on a MacBook's CPU; with a GTX 1060 for acceleration, each epoch only takes 3 seconds):

Epcho 1, Accuracy: 0.717359: 347it [01:06, 5.21it/s]
Epcho 1 Mean Accuracy: 0.56555
Epcho 2, Accuracy: 0.759943: 347it [01:08, 8.62it/s]
Epcho 2 Mean Accuracy: 0.74762
Epcho 3, Accuracy: 0.598692: 347it [01:08, 5.08it/s]
Epcho 3 Mean Accuracy: 0.693505
Epcho 4, Accuracy: 0.634529: 347it [01:07, 5.14it/s]
Epcho 4 Mean Accuracy: 0.613064
Epcho 5, Accuracy: 0.659949: 347it [01:07, 5.16it/s]
Epcho 5 Mean Accuracy: 0.643388
Epcho 6, Accuracy: 0.709635: 347it [01:07, 5.14it/s]
Epcho 6 Mean Accuracy: 0.679544
Epcho 7, Accuracy: 0.742839: 271it [00:42, 2.45it/s]
...

Hard Decoding

Once training is done, all that's left is prediction, tagging, and segmentation — pretty basic stuff, not much to say about it. In the end, this achieves 93% accuracy on the backoff2005 evaluation set (accuracy computed via the score script provided by backoff2005). Not the best result, but good enough — the more interesting part is the adjustment described below.

But as everyone knows, character-tagging-based segmentation requires labeled training data, and once training is finished, the model becomes adapted to that particular corpus, making it hard to extend to new domains. Or put another way: if you find places where it segments incorrectly, there's no quick way to fix them. Dictionary-based methods, on the other hand, are easy to adjust — you just need to add or remove entries in the dictionary, or adjust word frequencies. This makes it worth considering how to combine deep learning with a dictionary, and here I've done something simple: adding hard decoding (manual intervention in decoding) at the final decoding stage.

The model's predictions give us the probability of each tag, and then the Viterbi algorithm is used to find the optimal path. But before running Viterbi, we can use a dictionary to adjust the tag probabilities. Here's how it works: add an add_dict.txt file, where each line contains a word along with a multiplier — this multiplier is the factor by which the corresponding tag probabilities should be scaled up. For example, if the dictionary specifies the entry "科学空间,10" (kexue kongjian, "science space", with multiplier 10), and we're segmenting the sentence "科学空间挺好" ("kexue kongjian is quite good"), we first use the model to get the tag probabilities for these six characters, then check whether the word "科学空间" appears in this sentence. Since it does, we multiply the probability of the first character being tagged s by 10, the probabilities of the second and third characters being tagged m by 10, and the probability of the fourth character being tagged e by 10 (no need to renormalize, since only the relative values matter). Similarly, if there are places where the model fails to make a needed cut, these can also be added to the dictionary with a multiplier of less than 1.

Results:

Before adding the dictionary: 扫描 二维码 ， 关注 微 信号 。
(After adding to the dictionary: 微信号,10) After adding the dictionary: 扫描 二维码 ， 关注 微信号 。

Of course, this is just an empirical trick. The code for the remaining part is below — since this is only meant to demonstrate the effect, it uses regular expressions for the lookup; if you're after efficiency, you should use a multi-pattern matching tool such as the Aho–Corasick automaton instead:

trans_proba = {'ss':1, 'sb':1, 'bm':1, 'be':1, 'mm':1, 'me':1, 'es':1, 'eb':1}
trans_proba = {i:np.log(j) for i,j in trans_proba.iteritems()}

add_dict = {}
if os.path.exists('add_dict.txt'):
    with open('add_dict.txt') as f:
        for l in f:
            a,b = l.split(',')
            add_dict[a.decode('utf-8')] = np.log(float(b))
    

def viterbi(nodes):
    paths = nodes[0]
    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 trans_proba.keys():
                    nows[j+i]= paths_[j]+nodes[l][i]+trans_proba[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:
        nodes = [dict(zip('sbme', np.log(k)))
                 for k in sess.run(y, feed_dict={x:[[word2id[i] for i in s]], keep_prob:1})[0]
                ]
        for w,f in add_dict.iteritems():
            for i in re.finditer(w, s):
                if len(w) == 1:
                    nodes[i.start()]['s'] += f
                else:
                    nodes[i.start()]['b'] += f
                    nodes[i.end()-1]['e'] += f
                    for j in range(i.start()+1, i.end()-1):
                        nodes[j]['m'] += f
        tags = viterbi(nodes)
        words = [s[0]]
        for i in range(1, len(s)):
            if tags[i] in ['s', 'b']:
                words.append(s[i])
            else:
                words[-1] += s[i]
        return words
    else:
        return []

def cut_words(s):
    i = 0
    r = []
    for j in re.finditer('['+stops+' ]'+'|[a-zA-Z\d]+', s):
        r.extend(simple_cut(s[i:j.start()]))
        r.append(s[j.start():j.end()])
        i = j.end()
    if i != len(s):
        r.extend(simple_cut(s[i:]))
    return r