Back to School! Let's Play Fill-in-the-Blank (iFLYTEK Cup)
Foreword
Starting this year, the CCL conference plans to hold evaluation tasks alongside the regular proceedings. I've been interning at a startup recently, and the company signed up to participate in this evaluation. The implementation ended up falling on my shoulders. This year's task was reading comprehension, officially titled The First "iFLYTEK Cup" Chinese Machine Reading Comprehension Evaluation. Although it's called reading comprehension, the task is actually quite simple — it's really a cloze-style task: a blank is dug out of a passage, and you need to pick a word from the context to fill it in. In the end, our model ranked 6th among single systems, with 73.55% accuracy on the validation set and 75.77% on the test set. You can check out the leaderboard here. (The model listed under "Guangzhou Flame Information Technology Co., Ltd." is the one described in this post.)
Actually, this dataset and task format were originally proposed by HIT (Harbin Institute of Technology) last year, so this evaluation is jointly organized by HIT and iFLYTEK. HIT's paper from last year, Consensus Attention-based Neural Networks for Chinese Reading Comprehension, studied a dataset with the same format but different content, using a general-purpose reading comprehension model (general reading comprehension means: given a passage and a question, find the answer to the question within the passage; cloze can be considered a very small subset of general reading comprehension).
Although the organizers, in their introduction to this evaluation task, kept steering us — intentionally or not — toward treating this as a reading comprehension problem, I feel that reading comprehension itself is much harder than this. This is really just a fill-in-the-blank task, so it's fine to treat it purely as a cloze problem. Hence this post simply adopts a language-model-like approach to tackle it. The advantage of this approach is that the idea is simple and intuitive, and the computational cost is low (on my GTX 1060, I could run a batch size of 160), which makes experimentation convenient.
The Model
Back to the model — it's actually quite simple, and closely follows the idea of "picking a word from the context to fill the blank." The diagram is below.
Cloze modelmore
Preliminary Analysis
First, notice that the task is to pick a word from the context to fill in the blank position, for example:
[Passage]
1 ||| The Conference Board reported that consumer confidence rose to 78.1 in December, notably higher than 72 in November.
2 ||| The Wall Street Journal also reported that 2013 was the best year for the U.S. stock market since 1995.
3 ||| Over the course of the year, the smart move in U.S. equities investing was to chase "dumb money."
4 ||| So-called "dumb money" XXXXX, which is really just the ordinary portfolio of buying and holding U.S. stocks.
5 ||| This strategy performed far better than the more sophisticated investment methods used by hedge funds and other professional investors.
[Question - Fill-in-the-blank]
So-called "dumb money" XXXXX, which is really just the ordinary portfolio of buying and holding U.S. stocks.
[Answer]
strategy
Readers familiar with NLP will notice that this task is fairly similar to language modeling — in fact, one could argue it's even simpler, since a language model predicts the next word given the preceding $n$ words by searching over the entire vocabulary, whereas this cloze task only needs to search within the context, which greatly narrows the search space. Of course, the two tasks have different focuses: language modeling cares about the probability distribution, while cloze cares about prediction accuracy.
Context Encoding
Empirically, for language modeling, LSTMs tend to work best, so we use LSTMs here as well. To better capture global semantic information, we stack multiple layers of bidirectional LSTMs — standard practice in NLP by now.
First, we split the passage at the position of "XXXXX" into a preceding part and a following part. These two parts are then fed, one after another, into the same bidirectional LSTM (i.e., computed twice, rather than concatenated and computed once), to obtain their respective features. In other words, the LSTM encoding the preceding and following context shares parameters. Why? The reasoning is simple: when we read the surrounding context ourselves, we use the same brain for both — there's no need to treat them differently. Once we have one LSTM layer, we can stack several — again, standard practice. As for how many layers are appropriate, that depends on the specific dataset. For this competition's task, two layers gave a clear improvement over one layer, while three layers showed no further improvement over two — and even slightly worse performance.
Finally, to obtain a feature vector for the whole passage (used for the matching step below), we simply concatenate the final state vectors of the bidirectional LSTM to get feature vectors for the preceding and following context respectively, and then average the two vectors to get the global feature vector.
(It's worth noting that if we instead use the dataset from the paper Consensus Attention-based Neural Networks for Chinese Reading Comprehension — same format, but content drawn from People's Daily — the same model as described here requires 3 LSTM layers, and the final accuracy is 0.5% higher than the best result reported in that paper.)
Predicting Probabilities
The next question is: how do we implement "searching within the context" rather than searching over the entire vocabulary?
Recall how language modeling works: to search over the entire vocabulary, we'd use a fully-connected layer with as many nodes as there are words in the vocabulary, then apply softmax to predict probabilities. We can view this fully-connected layer as follows: we assign each word in the vocabulary a vector of the same dimension as the output feature, compute inner products, and then apply softmax. In other words, the pairing between features and words is realized via an inner product. This suggests an approach: if we make the LSTM's output feature the same dimension as the word embeddings, we can compute the inner product between this feature and the input word embeddings one by one (pairing them up), and then apply softmax — thereby restricting the search to the context only.
This was in fact my initial approach, but it only achieved 69%–70% accuracy. On reflection, I realized that after passing through multiple LSTM layers, the original word embeddings end up far removed from their original embedding space. So rather than pairing the LSTM output with the input word embeddings across this "long journey," why not pair it directly with the LSTM's intermediate hidden state vectors instead? At least within the same LSTM layer, the hidden state vectors are relatively close to each other (i.e., they lie in the same vector space), which should make matching easier.
Experiments confirmed this hypothesis. With this improved model, accuracy on the official validation set reached around 73%–74%, and on the test set, 75%–76%. Further experimentation over time didn't yield noticeable improvements, so this is the model we submitted.
Implementation Details
To be honest, I'm not very skilled at hyperparameter tuning, so the parameters in the code below are not necessarily optimal. I'd welcome anyone skilled in tuning to optimize the various hyperparameters and report better results. I believe that even with the model architecture described here, the results we obtained are not necessarily the best achievable.
Here are some of the more important implementation details:
1. The corpus for this competition is in the domain of fairy tales. We pretrained Word2Vec word embeddings using the training corpus plus additional fairy-tale text we crawled ourselves (see here for the crawling method), and used these as input to the LSTM.
2. To handle out-of-vocabulary words, we set up a padding/unknown symbol UNK (with ID 0 in the code). Since all the word embeddings were pretrained with Word2Vec, but UNK wasn't among them, only the embedding corresponding to UNK is left trainable.
3. We need to usebidirectional_dynamic_rnnto properly handle variable-length sequences.
4. After computing the final inner products, we need to subtract a large constant ($10^{12}$ was subtracted in the code) from the inner products at padding positions, before applying softmax and calling thesoftmax_cross_entropy_with_logitsloss function. The reasoning is simple: it's the softmax of the inner products that gives probabilities, so to force the probability at padding positions to be 0, the corresponding inner product needs to be a very large negative number.
5. If the target word appears multiple times in the context, the probability mass is spread evenly across each occurrence — that is, the cross-entropy target is not necessarily one-hot. When making the final prediction, the probabilities of repeated occurrences of the same word must be summed before taking the argmax.
Code
Dataset
Dataset download: https://github.com/ymcui/cmrc2017
The code below can also be viewed on my GitHub: https://github.com/bojone/CCL_CMRC2017
Training Script
#! -*- coding:utf-8 -*-
#实验环境：tensorflow 1.2
import codecs
import re
import os
import numpy as np
def split_data(text):
words = re.split('[ \n]+', text)
idx = words.index('XXXXX')
return words[:idx],words[idx+1:]
print u'正在读取训练语料...'
train_x = codecs.open('../CMRC2017_train/train.doc_query', encoding='utf-8').read()
train_x = re.split('<qid_.*?\n', train_x)[:-1]
train_x = ['\n'.join([l.split('||| ')[1] for l in re.split('\n+', t) if l.split('||| ')[0]]) for t in train_x]
train_x = [split_data(l) for l in train_x]
train_y = codecs.open('../CMRC2017_train/train.answer', encoding='utf-8').read()
train_y = train_y.split('\n')[:-1]
train_y = [l.split('||| ')[1] for l in train_y]
print u'正在读取验证语料...'
valid_x = codecs.open('../CMRC2017_cloze_valid/cloze.valid.doc_query', encoding='utf-8').read()
valid_x = re.split('<qid_.*?\n', valid_x)[:-1]
valid_x = ['\n'.join([l.split('||| ')[1] for l in re.split('\n+', t) if l.split('||| ')[0]]) for t in valid_x]
valid_x = [split_data(l) for l in valid_x]
valid_y = codecs.open('../CMRC2017_cloze_valid/cloze.valid.answer', encoding='utf-8').read()
valid_y = valid_y.split('\n')[:-1]
valid_y = [l.split('||| ')[1] for l in valid_y]
word_size = 128
if os.path.exists('model.config'): #如果有则读取配置信息
id2word,word2id,embedding_array = pickle.load(open('model.config'))
else: #如果没有则重新训练词向量
import jieba
import codecs
import logging
logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s', level=logging.INFO)
from gensim.models import Word2Vec
print u'正在对添加语料进行分词...'
additional = codecs.open('../additional.txt', encoding='utf-8').read().split('\n') #自行从网上爬的童话语料
additional = map(lambda s: jieba.lcut(s, HMM=False), additional)
class data_for_word2vec: #用迭代器将三个语料整合起来
def __iter__(self):
for x in train_x:
yield x[0]
yield x[1]
for x in valid_x:
yield x[0]
yield x[1]
for x in additional:
yield x
word2vec = Word2Vec(data_for_word2vec(), size=word_size, min_count=2, sg=2, negative=10, iter=10)
word2vec.save('word2vec_tk')
from collections import defaultdict
id2word = {i+1:j for i,j in enumerate(word2vec.wv.index2word)}
word2id = defaultdict(int, {j:i for i,j in id2word.items()})
embedding_array = np.array([word2vec[id2word[i+1]] for i in range(len(id2word))])
pickle.dump([id2word,word2id,embedding_array], open('model.config','w'))
import tensorflow as tf
padding_vec = tf.Variable(tf.random_uniform([1, word_size], -0.05, 0.05)) #只对填充向量进行训练，其余向量保持word2vec的结果
embeddings = tf.constant(embedding_array, dtype=tf.float32)
embeddings = tf.concat([padding_vec,embeddings], 0)
L_context = tf.placeholder(tf.int32, shape=[None,None])
L_context_length = tf.placeholder(tf.int32, shape=[None])
R_context = tf.placeholder(tf.int32, shape=[None,None])
R_context_length = tf.placeholder(tf.int32, shape=[None])
L_context_vec = tf.nn.embedding_lookup(embeddings, L_context)
R_context_vec = tf.nn.embedding_lookup(embeddings, R_context)
def add_brnn(inputs, rnn_size, seq_lens, name): #定义单层双向LSTM，上下文公用参数，分别过LSTM然后拼接
rnn_cell_fw = tf.contrib.rnn.BasicLSTMCell(rnn_size)
rnn_cell_bw = tf.contrib.rnn.BasicLSTMCell(rnn_size)
outputs = []
with tf.variable_scope(name_or_scope=name) as vs:
for input,seq_len in zip(inputs,seq_lens):
outputs.append(tf.nn.bidirectional_dynamic_rnn(rnn_cell_fw, rnn_cell_bw, input, sequence_length=seq_len, dtype=tf.float32))
vs.reuse_variables()
return [tf.concat(o[0],2) for o in outputs], [o[1] for o in outputs]
[L_outputs,R_outputs],[L_final_state,R_final_state] = add_brnn([L_context_vec,R_context_vec], word_size, [L_context_length,R_context_length], name='LSTM_1')
[L_outputs,R_outputs],[L_final_state,R_final_state] = add_brnn([L_outputs,R_outputs], word_size, [L_context_length,R_context_length], name='LSTM_2')
L_context_mask = (1-tf.cast(tf.sequence_mask(L_context_length), tf.float32))*(-1e12) #对填充位置进行mask，注意这里是softmax之前的mask，所以mask不是乘以0，而是减去1e12
R_context_mask = (1-tf.cast(tf.sequence_mask(R_context_length), tf.float32))*(-1e12)
context_mask = tf.concat([L_context_mask,R_context_mask], 1)
outputs = tf.concat([L_outputs,R_outputs], 1)
final_state = (tf.concat([L_final_state[0][1], L_final_state[1][1]], 1) + tf.concat([R_final_state[0][1], R_final_state[1][1]], 1))/2 #双向拼接、上下文取平均，得到encode向量
attention = context_mask + tf.matmul(outputs, tf.expand_dims(final_state, 2))[:,:,0] #encode向量与每个时间步状态向量做内积，然后mask，然后softmax
sample_labels = tf.placeholder(tf.float32, shape=[None,None])
loss = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(labels=sample_labels, logits=attention))
pred = tf.nn.softmax(attention)
train_step = tf.train.AdamOptimizer().minimize(loss)
init = tf.global_variables_initializer()
sess = tf.Session()
sess.run(init)
train_x = [([word2id[i] for i in j[0]] if j[0] else [0], [word2id[i] for i in j[1]] if j[1] else [0]) for j in train_x] #词序列ID化
train_y = [word2id[i] for i in train_y]
valid_x = [([word2id[i] for i in j[0]] if j[0] else [0], [word2id[i] for i in j[1]] if j[1] else [0]) for j in valid_x]
valid_y = [word2id[i] for i in valid_y]
def construct_sample(x, y, i):
return x[i][0], x[i][1], y[i]
train_x = [construct_sample(train_x, train_y, i) for i in range(len(train_x))] #输入输出配对，构成训练样本
valid_x = [construct_sample(valid_x, valid_y, i) for i in range(len(valid_x))]
batch_size = 160
def generate_batch_data(data, batch_size): #生成单个batch
np.random.shuffle(data)
batch = []
for x in data:
batch.append(x)
if len(batch) == batch_size:
l0 = [len(x[0]) for x in batch]
l1 = [len(x[1]) for x in batch]
x0 = np.array([x[0]+[0]*(max(l0)-len(x[0])) for x in batch])
x1 = np.array([x[1]+[0]*(max(l1)-len(x[1])) for x in batch])
x2 = np.array([[x[2]] for x in batch])
y = (np.hstack([x0,x1])==x2).astype(np.float32)
yield (x0,
x1,
y/y.sum(axis=1).reshape((-1,1)),
np.array(l0),
np.array(l1),
x2
)
batch = []
if batch:
l0 = [len(x[0]) for x in batch]
l1 = [len(x[1]) for x in batch]
x0 = np.array([x[0]+[0]*(max(l0)-len(x[0])) for x in batch])
x1 = np.array([x[1]+[0]*(max(l1)-len(x[1])) for x in batch])
x2 = np.array([[x[2]] for x in batch])
y = (np.hstack([x0,x1])==x2).astype(np.float32)
yield (x0,
x1,
y/y.sum(axis=1).reshape((-1,1)),
np.array(l0),
np.array(l1),
x2
)
batch = []
import datetime
import json
epochs = 30
saver = tf.train.Saver()
if not os.path.exists('./tk'):
os.mkdir('./tk')
try:
saver.restore(sess, './tk/tk_highest.ckpt')
except:
pass
def cumsum_proba(x, y): #对相同项的概率进行合并
tmp = {}
for i,j in zip(x, y):
if i in tmp:
tmp[i] += j
else:
tmp[i] = j
return tmp.keys()[np.argmax(tmp.values())]
highest_acc = 0.
train_log = {'loss':[], 'accuracy':[]}
for e in range(epochs):
train_data = list(generate_batch_data(train_x, batch_size))
count = 0
batch = 0
for x in train_data:
if batch % 10 == 0:
loss_ = sess.run(loss, feed_dict={L_context:x[0], R_context:x[1], sample_labels:x[2], L_context_length:x[3], R_context_length:x[4]})
print '%s, epoch %s, trained on %s samples, loss: %s'%(datetime.datetime.now(), e+1, count, loss_)
saver.save(sess, './tk/tk_%s.ckpt'%e) #每个epoch保存一次
train_log['loss'].append(float(loss_))
json.dump(train_log, open('train.log', 'w'))
sess.run(train_step, feed_dict={L_context:x[0], R_context:x[1], sample_labels:x[2], L_context_length:x[3], R_context_length:x[4]})
if batch % 100 == 0:
valid_data = list(generate_batch_data(valid_x, batch_size))
r = 0.
for x in valid_data:
p = sess.run(pred, feed_dict={L_context:x[0], R_context:x[1], sample_labels:x[2], L_context_length:x[3], R_context_length:x[4]})
w = np.hstack([x[0],x[1]])
r += (np.array([cumsum_proba(s,t) for s,t in zip(w, p)]) == x[5].reshape(-1)).sum()
acc = r/len(valid_x)
print '%s, valid accuracy %s'%(datetime.datetime.now(), acc)
train_log['accuracy'].append(acc)
if highest_acc <= acc:
highest_acc = acc
saver.save(sess, './tk/tk_highest.ckpt') #历史最好也保存一次
batch += 1
count += len(x[0])
Prediction Script
#! -*- coding:utf-8 -*-
#实验环境：tensorflow 1.2
import pickle
import numpy as np
id2word,word2id,embedding_array = pickle.load(open('model.config'))
word_size = embedding_array.shape[1]
import tensorflow as tf
padding_vec = tf.Variable(tf.random_uniform([1, word_size], -0.05, 0.05))
embeddings = tf.constant(embedding_array, dtype=tf.float32)
embeddings = tf.concat([padding_vec,embeddings], 0)
L_context = tf.placeholder(tf.int32, shape=[None,None])
L_context_length = tf.placeholder(tf.int32, shape=[None])
R_context = tf.placeholder(tf.int32, shape=[None,None])
R_context_length = tf.placeholder(tf.int32, shape=[None])
L_context_vec = tf.nn.embedding_lookup(embeddings, L_context)
R_context_vec = tf.nn.embedding_lookup(embeddings, R_context)
def add_brnn(inputs, rnn_size, seq_lens, name):
rnn_cell_fw = tf.contrib.rnn.BasicLSTMCell(rnn_size)
rnn_cell_bw = tf.contrib.rnn.BasicLSTMCell(rnn_size)
outputs = []
with tf.variable_scope(name_or_scope=name) as vs:
for input,seq_len in zip(inputs,seq_lens):
outputs.append(tf.nn.bidirectional_dynamic_rnn(rnn_cell_fw, rnn_cell_bw, input, sequence_length=seq_len, dtype=tf.float32))
vs.reuse_variables()
return [tf.concat(o[0],2) for o in outputs], [o[1] for o in outputs]
[L_outputs,R_outputs],[L_final_state,R_final_state] = add_brnn([L_context_vec,R_context_vec], word_size, [L_context_length,R_context_length], name='LSTM_1')
[L_outputs,R_outputs],[L_final_state,R_final_state] = add_brnn([L_outputs,R_outputs], word_size, [L_context_length,R_context_length], name='LSTM_2')
L_context_mask = (1-tf.cast(tf.sequence_mask(L_context_length), tf.float32))*(-1e12)
R_context_mask = (1-tf.cast(tf.sequence_mask(R_context_length), tf.float32))*(-1e12)
context_mask = tf.concat([L_context_mask,R_context_mask], 1)
outputs = tf.concat([L_outputs,R_outputs], 1)
final_state = (tf.concat([L_final_state[0][1], L_final_state[1][1]], 1) + tf.concat([R_final_state[0][1], R_final_state[1][1]], 1))/2
attention = context_mask + tf.matmul(outputs, tf.expand_dims(final_state, 2))[:,:,0]
sample_labels = tf.placeholder(tf.float32, shape=[None,None])
loss = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(labels=sample_labels, logits=attention))
pred = tf.nn.softmax(attention)
train_step = tf.train.AdamOptimizer().minimize(loss)
init = tf.global_variables_initializer()
sess = tf.Session()
sess.run(init)
saver = tf.train.Saver()
saver.restore(sess, './tk/tk_highest.ckpt')
import re
def split_data(text):
words = re.split('[ \n]+', text)
idx = words.index('XXXXX')
return words[:idx],words[idx+1:]
def cumsum_proba(x, y):
tmp = {}
for i,j in zip(x, y):
if i in tmp:
tmp[i] += j
else:
tmp[i] = j
return tmp.keys()[np.argmax(tmp.values())]
def predict(text): #输入的text为字符串，用空格隔开分词结果，待填空位置用XXXXX表示
text = split_data(text)
text = [word2id[i] for i in text[0]] if text[0] else [0], [word2id[i] for i in text[1]] if text[1] else [0]
p = sess.run(pred, feed_dict={L_context:[text[0]], R_context:[text[1]], L_context_length:[len(text[0])], R_context_length:[len(text[1])]})
return id2word.get(cumsum_proba(text[0]+text[1], p[0]),' ')
if __name__ == '__main__':
import codecs
import os
import sys
vaild_name = sys.argv[1]
output_name = sys.argv[2]
text = codecs.open(vaild_name, encoding='utf-8').read()
valid_x = re.split('<qid_.*?\n', text)[:-1]
valid_x = ['\n'.join([l.split('||| ')[1] for l in re.split('\n+', t) if l.split('||| ')[0]]) for t in valid_x]
valid_x = [split_data(l) for l in valid_x]
valid_x = [([word2id[i] for i in j[0]] if j[0] else [0], [word2id[i] for i in j[1]] if j[1] else [0]) for j in valid_x]
batch_size = 160
def generate_batch_data(data, batch_size):
batch = []
for x in data:
batch.append(x)
if len(batch) == batch_size:
l0 = [len(x[0]) for x in batch]
l1 = [len(x[1]) for x in batch]
x0 = np.array([x[0]+[0]*(max(l0)-len(x[0])) for x in batch])
x1 = np.array([x[1]+[0]*(max(l1)-len(x[1])) for x in batch])
yield (x0,
x1,
np.array(l0),
np.array(l1),
)
batch = []
if batch:
l0 = [len(x[0]) for x in batch]
l1 = [len(x[1]) for x in batch]
x0 = np.array([x[0]+[0]*(max(l0)-len(x[0])) for x in batch])
x1 = np.array([x[1]+[0]*(max(l1)-len(x[1])) for x in batch])
yield (x0,
x1,
np.array(l0),
np.array(l1),
)
batch = []
valid_data = list(generate_batch_data(valid_x, batch_size))
valid_result = []
for x in valid_data:
p = sess.run(pred, feed_dict={L_context:x[0], R_context:x[1], L_context_length:x[2], R_context_length:x[3]})
w = np.hstack([x[0],x[1]])
valid_result.extend(np.array([cumsum_proba(s,t) for s,t in zip(w, p)]))
#生成讯飞杯要求的评测格式
names = re.findall('<qid_\d+>', text)
s = '\n'.join(names[i]+' ||| '+id2word.get(j,' ') for i,j in enumerate(valid_result))
with codecs.open(output_name, 'w', encoding='utf-8') as f:
f.write(s)
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.