[Chinese Word Segmentation Series] 6. Chinese Word Segmentation Based on Fully Convolutional Networks

CNN

Regarding FCN: when applied to linguistic tasks, (one-dimensional) convolution is essentially an n-gram model. From this perspective, CNNs are actually much more natural than RNNs. RNNs seem specifically designed for sequence tasks, whereas CNNs are an extension of traditional n-gram models. Furthermore, both CNNs and RNNs utilize weight sharing. While this might seem like a compromise to reduce computation, there is deep reasoning behind it. Weight sharing in CNNs is an inevitable result of translation invariance, not just a choice to reduce computation. Imagine shifting an image slightly, or inserting a meaningless space at the beginning of a sentence (causing all subsequent characters to shift back by one position). This should yield a similar or identical result, which requires the convolution to be weight-shared—meaning the weights cannot depend on the position.

RNN-type models, especially LSTM, have long been the dominant force in linguistic tasks. However, recently, GCNNs (Gated Convolutional Neural Networks) have reportedly outperformed LSTMs (slightly) in language modeling. This indicates that even in linguistic tasks, CNNs have significant potential. The advantage of LSTM is its ability to capture long-distance information, but in reality, there are not many linguistic tasks that truly require very long-distance dependencies. Even in language models, the probability of the next character usually depends only on the preceding few characters, rather than the entire preceding text. As long as a CNN has enough layers and large enough kernels, it can achieve this effect. Moreover, CNNs have a distinct advantage: they are much faster than RNNs. When using GPU acceleration, GPUs are best at convolution because they were originally designed for image processing. The acceleration provided by GPUs for CNNs is much more pronounced than for RNNs.

The reasons above make me prefer CNNs, much like the Facebook team (who developed GCNN). Fully Convolutional Networks use convolution from start to finish, allowing them to handle variable-length inputs. They are particularly suitable for tasks where the input length is variable but the input and output lengths are equal.

Corpus

The task in this article is to build a Chinese word segmentation system using FCN. The approach still uses the SBME character tagging method (if you are unfamiliar, please refer to previous articles). Since this is supervised training, we need a corpus. Two good options are the 2014 People’s Daily corpus and the backoff2005 competition corpus; the latter also includes an evaluation system. I have 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 input, the lengths within each batch must be equal during training. Therefore, a simple clustering (by length) is required. Next, generate a mapping table, which is standard procedure:

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]}

Create a generator to produce training samples for each batch. Note that the batch_size here is just an upper limit; since sentences within a batch must have the same length, not every batch will 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 is time to build the model. It is quite simple: three layers of convolution stacked together. The input length is not specified (set to None), and padding=’SAME’ is used to ensure the output length matches the input (for this reason, no pooling is used). ReLU activation is used for intermediate layers, and Softmax for the final layer, with cross-entropy as the loss function. With TensorFlow, you have to write out each process, but it is not very complicated.

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 is the entire model. Now, we train. I highly recommend using tqdm to assist with progress display (real-time display of progress, speed, and accuracy); it is 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'Epoch %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('Epoch %s, Accuracy: %s'%(i+1, acc))
        sess.run(train_step, feed_dict={x: xxx, y_: yyy, keep_prob:0.5})
    print u'Epoch %s Mean Accuracy: %s'%(i+1, np.mean(accs))

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

Training process output (trained on a MacBook CPU; using a GTX 1060 takes only 3s per epoch):

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

Hard Decoding

After training, the remaining steps are prediction, tagging, and segmentation, which are all basic. Ultimately, the model achieves 93% accuracy on the backoff2005 evaluation set (calculated using the provided score script). While not the absolute best, it is sufficient, especially considering the following adjustments.

As is well known, character-tagging-based segmentation requires labeled training data. Once trained, it adapts to that specific corpus and is difficult to extend to new domains. Furthermore, if errors are found, they cannot be quickly corrected. In contrast, dictionary-based methods are easy to adjust by simply adding/removing words or adjusting frequencies. We can consider how to combine deep learning with a dictionary. Here, I simply add hard decoding (manual intervention during decoding) at the final stage.

Model prediction yields probabilities for each tag. Next, the Viterbi algorithm is used to find the optimal path. However, before Viterbi, we can use a dictionary to adjust the probabilities of each tag. The method is: add an add_dict.txt file where each line is a word and a multiplier. This multiplier is used to increase the probability of the corresponding tags. For example, if the dictionary specifies "ScientificSpace,10", and we segment "ScientificSpaceIsGood", we first get the tag probabilities for these characters. Then, finding that "ScientificSpace" exists in the sentence, we multiply the probability of the first character being ’s’ by 10, the second and third characters being ’m’ by 10, and the fourth character being ’e’ by 10 (no normalization needed as we only care about relative values). Similarly, if certain segments are missed, they can be added to the dictionary with a multiplier less than 1.

Effect:

Before adding dictionary: Scan QR code , follow WeChat ID .

(After adding dictionary: WeChatID, 10) After adding dictionary: Scan QR code , follow WeChatID .

Of course, this is just an empirical method. The code for this part follows. Since this is for demonstration, I used regular expressions for searching; for better efficiency, a multi-pattern matching tool like an AC automaton should be used:

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

Original URL: https://kexue.fm/archives/4195