School's Back! Let's Do Some Cloze Tests (iFLYTEK Cup) · English (unofficial) translations of posts at kexue.fm

Preface

Starting this year, the CCL conference plans to hold evaluation activities simultaneously. I have been interning at a startup recently, and the company signed up for this evaluation. The implementation eventually fell to me. This year’s evaluation task is reading comprehension, titled "The 1st ’iFLYTEK Cup’ Chinese Machine Reading Comprehension Evaluation." Although it is called reading comprehension, the task is actually relatively simple and belongs to the cloze test category: a blank is dug out of a passage, and a word must be selected from the context to fill in this blank. In the end, our model ranked 6th as a single system, with a validation set accuracy of 73.55% and a test set accuracy of 75.77%. You can view the leaderboard here. ("Guangzhou Flame Information Technology Co., Ltd." is the model described in this text.)

In fact, this dataset and task format were proposed by the Harbin Institute of Technology (HIT) last year, so this evaluation was jointly organized by HIT and iFLYTEK. HIT’s paper from last year, "Consensus Attention-based Neural Networks for Chinese Reading Comprehension", studied another dataset with the same format but different content using a general reading comprehension model. (General reading comprehension refers to providing a passage and a question and finding the answer from the passage; cloze tests can be considered a very small subset of general reading comprehension.)

Although the evaluation organizers often intentionally or unintentionally guided us to understand this problem as a reading comprehension problem in the task introduction, I feel that reading comprehension itself is much more difficult. This is just a cloze test, so we should just treat it as a pure cloze test. Therefore, this article only adopts an approach similar to language models. The advantage of this approach is that the logic is simple and intuitive, the computational cost is low (it can run with a batch size of 160 on my GTX1060), and it is easy to experiment with.

Model

Returning to the model, ours is actually quite simple and strictly follows the idea of "selecting a word from the context to fill in the blank." The schematic diagram is as follows:

Preliminary Analysis

First, note that the task is to pick a word from the context to fill in the missing position, such as:

[Passage]
1 ||| The Chamber of Commerce reports that consumer confidence rose to 78.1 in December, significantly higher than 72 in November.
2 ||| According to the Wall Street Journal, 2013 was the best year for the US stock market since 1995.
3 ||| In this year, the wise way to invest in the US stock market was to follow the "silly money".
4 ||| The so-called "silly money" XXXXX, in fact, is a simple portfolio of buying and holding US stocks.
5 ||| This strategy performed much better than the more complex investment methods used by hedge funds and other professional investors.

[Question - Cloze Type]
The so-called "silly money" XXXXX, in fact, is a simple portfolio of buying and holding US stocks.

[Answer]
Strategy

Friends familiar with Natural Language Processing will realize that this task is similar to a language model, or even simpler, because a language model predicts the next word from the previous n words, requiring a traversal of all words in the vocabulary. In contrast, this cloze task only needs to select from the context, greatly narrowing the search range. Of course, the focus of the two is different: language models care about probability distribution, while cloze tests care about prediction accuracy.

Context Encoding

Based on experience, LSTM works best for language modeling, so LSTM is also used here. To better capture global semantic information, multiple layers of bidirectional LSTM are stacked. Of course, for NLP, this is a standard procedure.

First, we break the material at "XXXXX" into a prefix and a suffix. Then, the prefix and suffix are sequentially input into the same bidirectional LSTM (calculated twice rather than concatenated and calculated once) to obtain their respective features. That is to say, the LSTMs for the prefix and suffix share parameters. Why? The reason is simple: when we read the context ourselves, we use the same brain; there is no need for different treatment. Once you have one LSTM layer, you can stack multiple layers, which is also standard. As for how many layers are suitable, it depends on the specific dataset. For this competition task, two layers showed a significant improvement over a single layer, while three layers showed no improvement or even a slight decrease.

Finally, to obtain the feature vector of the entire material (used for matching below), we only need to concatenate the final state vectors of the bidirectional LSTM to get the respective feature vectors of the prefix and suffix, and then average the two vectors to get the global feature vector.

(It is worth noting that if we switch to the dataset in the paper "Consensus Attention-based Neural Networks for Chinese Reading Comprehension" (same format, but content changed to People’s Daily), using the same model as in this article, the LSTM requires 3 layers, and the final accuracy is 0.5% higher than the best result in that paper.)

Prediction Probability

The next question is: how can we implement "searching in the context" instead of searching in the entire vocabulary?

Recall that when we build a language model, if we want to search the entire vocabulary, we need a fully connected layer where the number of nodes is the number of words in the vocabulary, followed by a softmax to predict the probability. We can look at the fully connected layer this way: we assign a vector with the same dimension as the output feature to every word in the vocabulary, perform an inner product operation, and then apply softmax. In other words, the matching between features and words is achieved through the inner product. This provides a reference idea: if we make the dimension of the features output by the LSTM the same as the word vector dimension, and then perform an inner product (pairing) between this feature and the input word vectors one by one, we can then apply softmax. This achieves searching only within the context.

I initially used this approach, but the accuracy only reached 69%–70%. After analysis, I realized that after the original word vectors are encoded by multiple layers of LSTM, they have actually moved far away from the original word vector space. Therefore, instead of "traveling a long distance" to pair with the input word vectors, why not pair directly with the intermediate state vectors of the LSTM? At least within the same LSTM layer, the state vectors are relatively close (meaning they are in the same vector space), making matching easier.

Experiments proved my hypothesis. After improving the model, it reached an accuracy of about 73%–74% on the official validation set and 75%–76% on the test set. After further experimentation, there was no significant improvement, so I submitted this model.

Implementation Details

In fact, I am not very good at hyperparameter tuning, so the parameters in the following code may not be optimal. I look forward to tuning experts optimizing the parameters to provide better results. I believe that even for the model in this article, the results we provided are not yet optimal.

Below are some important details in the implementation of the model:

1. The corpus domain for this task is fairy tales. We pre-trained Word2Vec word vectors using the training corpus and additional fairy tale corpora (refer to here for the crawling method), and then used them as input for the LSTM;

2. To handle out-of-vocabulary (OOV) words, a padding symbol UNK is generally set (ID 0 is used in the code). Since the word vectors here are pre-trained with Word2Vec, but UNK is not, only the training of the word vector corresponding to UNK is enabled;

3. bidirectional_dynamic_rnn must be used to handle variable-length sequence issues;

4. After the final inner product step, a large constant (10^{12} in the code) must be subtracted from the inner product at the padding positions before performing softmax and calling the softmax_cross_entropy_with_logits loss function. The reason is simple: the softmax of the inner product is the probability. To make the probability of the padding position zero, the inner product result at the corresponding position must be a very small negative number;

5. If the target word appears multiple times in the context, the probability is spread across each occurrence. That is, the cross-entropy target is not necessarily in one-hot format. During final prediction, the probabilities of repeated words must be summed before sorting to find the maximum.

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 -*-
# Experimental environment: tensorflow 1.2

import codecs
import re
import os
import numpy as np
import pickle

def split_data(text):
    words = re.split('[ \n]+', text)
    idx = words.index('XXXXX')
    return words[:idx],words[idx+1:]

print 'Reading training corpus...'
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 'Reading validation corpus...'
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'): # Read config if exists
    id2word,word2id,embedding_array = pickle.load(open('model.config'))
else: # Retrain word vectors if not
    import jieba
    import logging
    logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s', level=logging.INFO)
    from gensim.models import Word2Vec
    print 'Tokenizing additional corpus...'
    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: # Iterator to integrate corpora
        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

# Only train padding vector, others keep word2vec results
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): # Single layer Bi-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')

# Mask padding positions
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)
# Bi-concatenation, average context
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
# Inner product and softmax
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)

# ID-ize word sequences
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]
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): # Generate 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)

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): # Merge probabilities
    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)
            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 -*-
# Experimental environment: tensorflow 1.2

import pickle
import numpy as np
import tensorflow as tf
import re
import codecs
import sys

id2word,word2id,embedding_array = pickle.load(open('model.config'))
word_size = embedding_array.shape[1]

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]
pred = tf.nn.softmax(attention)

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

saver = tf.train.Saver()
saver.restore(sess, './tk/tk_highest.ckpt')

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): # Input text is string, space-separated, blank as 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__':
    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))

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

    # Generate evaluation format
    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)

Original address: https://kexue.fm/archives/4564

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