Title: ACHIEVING MORPHOLOGICAL AGREEMENT WITH CONCORDE

Abstract: Neural conversational models are widely used in applications like personal assistants and chat bots. These models seem to give better performance when operating on word level. However, for fusion languages like French, Russian and Polish, vocabulary size sometimes become infeasible since most of the words have lots of word forms. To reduce vocabulary size we propose a new pipeline for building conversational models: first generate words in standard form and then transform them into a grammatically correct sentence. For this task we propose a neural network architecture that efficiently employs correspondence between standardised and target words and significantly outperforms character-level models while being 2x faster in training and 20% faster at evaluation. The proposed pipeline gives better performance than character-level conversational models according to assessor testing.

1. INTRODUCTION:

Neural conversational models Vinyals & Le (2015) are used in a large number of applications: from technical support and chat bots to personal assistants. While being a powerful framework, they often suffer from high computational costs.

The main computational and memory bottleneck occurs at the vocabulary part of the model. Vocabulary is used to map a sequence of input tokens to embedding vectors: one embedding vector is stored for each word in vocabulary.

English is de-facto a standard language for training conversational models, mostly for a large number of speakers and simple grammar. In english, words usually have only a few word forms. For example, verbs may occur in present and past tenses, nouns can have singular and plural forms.

For many other languages, however, some words may have tens of word forms. This is the case for Polish, Russian, French and many other languages. For these languages storing all forms of frequent words in a vocabulary significantly increase computational costs.

To reduce vocabulary size, we propose to normalize input and output sentences by putting them into a standard form. Generated texts can then be converted into grammatically correct ones by solving morphological agreement task. This can be efficiently done by a model proposed in this work.

Our contribution is two-fold:

• We propose a neural network architecture for performing morphological agreement in fusion languages such as French, Polish and Russian (Section 2).

• We introduce a new approach to building conversational models: generating normalized text and then performing morphological agreement with proposed model (Section 3);

2. CONCORDE:

In this section we propose a neural network architecture for solving morphological agreement problem.

We start by formally defining the morphological agreement task. Consider a grammatically correct sentence with words [a 1 , a 2 , . . . , a K ]. Let S(a) be a function that maps any word to its standard form. For example, S("went") = "go". Goal of morphological agreement task is to learn a mapping from normalized sentence [S(a 1 ), S(a 2 ), . . . , S(a K )] = [a n 1 , ,a n 2 , . . . , a n K ] to initial sentence [a 1 , a 2 , . . . , a K ]. Interestingly, reverse mapping may be performed for each word independently using specialized dictionaries. Original task, however, needs to consider dependencies between words in sequence in order to output a coherent text.

An important property of this task is that the number of words, their order and meaning are explicitly contained in input sequence. To employ this knowledge, we propose a specific neural network architecture illustrated in Figure 1 . Network operates as follows: first all normalized words are embedded using the same character-level LSTM encoder. The goal of the next step is to incorporate global information about other words to embedding of each word. To do so we pass word embedding sequence through a bidirectional LSTM Graves et al. (2013) . This allows new embeddings to get information from all other words: information about previous words is brought by forward LSTM and information about subsequent words is taken from backward LSTM. Finally, new embeddings are decoded with character-level LSTM decoders. At this stage we also added attention Bahdanau et al. (2015) over input characters of corresponding words for better performance.

High-level overview of this model resembles sequence-to-sequence Sutskever et al. (2014) Unlike simple character-level sequence-to-sequence model, our architecture allows for much faster evaluation, since encoding and decoding phases can be done in parallel for each word. Also, one of the main advantages of our approach is that information paths from inputs to outputs are much shorter which leads to slower performance degradation as input length increases (see Section 5.3).

3. Q-CONCORDE: NEURAL CONVERSATION:

As discussed above, we propose a two stage approach to build a neural conversational model: first generate normalized answer using normalized question and then apply Concorde model to obtain grammatically correct response. In this section we discuss a modification of Concorde model for conditioning its output on question's morphological features.

A modification of Concorde model that we call Q-Concorde uses two sources of input: question and normalized answer. Question is first embedded into a single vector with character-level RNN. This vector may carry important morphological information such as time, case and plurality of questions.

Question embedding is then mixed with answer embeddings using linear mapping. The final model is shown in Figure 3 . 

𝑎 " 𝑎 # 𝑎 " $ 𝑎 # $ 𝑎 " % 𝑎 # % Char. LSTM encoder (A)

4. RELATED WORK:

Most frequently used models for sequence to sequence mapping rely on generating embedding vector that contains all information about input sequence. Reconstruction solely from this vector usually results in worse performance as length of the output sequence increases. Attention (Xu et al. (2015) , Luong et al. (2015) , Bahdanau et al. (2015) ) partially fixes this problem, though information bottleneck of embedding vector is still high.

Encoder-decoder models have mostly been applied to tasks like speech recognition (Graves & Schmidhuber (2005) , Graves et al. (2013) , Graves & Jaitly ( 2014)), machine translation (Bahdanau et al. (2015) , Sutskever et al. (2014) , Cho et al. (2014) ) and neural conversational models (Vinyals & Le (2015) , Shang et al. (2015) ).

Some works have tried to perform decomposition of input sequence to obtain shorter information paths. In (Johansen et al. ( 2016)) input is first processed character-wise and then embeddings that correspond to word endings are used for sequence-to-sequence model. This modification makes input-output information paths shorter which leads to better performance.

Word inflection is a most similar task to ours, but in this task model is asked to generate a specific word form while we want our model to automatically select desired word forms. Durrett & DeNero (2013) proposed a supervised approach to predicting the set of all word forms by generating transformation rules from known inflection tables. They also propose to use Conditional Random Fields for unseen base forms.

Besides recurrent networks, there has been an attempt to use convolutional networks. Ostling (2016) based his work on Faruqui et al. (2015) and proposed to first pass raw data through convolutional layers and then to pass them through recurrent encoder. Kim et al. (2016) uses character-level encoder and word-level decoder.

There has also been some work on achieving open vocabulary. Luong & Manning (2016) suggests to use character-wise encoder to generate embeddings of out-of-vocabulary words

5. EXPERIMENTS:

We evaluate our model in two steps. First we compare performance of Concorde and character-level models in three languages: French, Polish, and Russian. We then evaluate Q-Concorde model on Q&A task.

5.1. SETUP:

To construct training sets for French and Polish languages we use normalization vocabularies1 . For normalization of Russian language we use pymorphy2 Korobov (2015) library. We leave first 20 words from each sentence to reduce computational costs. Concorde and Q-Concorde models consist of 2-layer LSTM encoder and decoder with hidden size 512. 2016): we first embed each word using recurrent encoder and then compute sentence embedding by running word-level encoder on these embeddings. For baselines we use layer size of 768 which results in a comparable number of parameters for all models.

We train models with Adam Kingma & Ba (2014) optimizer in batch size 16 with learning rate 0.0002 that halves after each 50k updates. We terminate training after 300k updates which is enough for all models to converge.

5.2. OPENSUBTITLES:

To evaluate our model we used French, Russian an Polish corpuses from OpenSubtitles2 database. We performed morphological agreement for each subtitle line independently. We estimated potential vocabulary size reduction from normalization by selecting words that appeared more than 10 times in first 10M examples. This lead to 2.5 times reduction for Polish language, 2.4 for Russian, and 1.8 for French.

We evaluated our model in two metrics: word and sentence accuracies. Word accuracy shows a fraction of words that were correctly generated. Sentence accuracy corresponds to the fraction of sentences that were transformed without any mistake. Results are reported in Table 1 . From four models that we compared, our model gave the best performance among all datasets, while second best model was hierarchical model.

We inspected our model to show some examples where it was able to infer plural form and gender for unseen words (Table 2 ). For Russian language we found out that the model was able to learn some rare rules like changing the letter я to й when going to plural form in some words: один заяц , два зайца (one rabbit, two rabbits).

We can also see that our model can infer gender from words. To show that we chose feminine, masculine and neuter words and asked the model to perform agreement with word "one". This word changes its spelling for different genders in French, Polish, and Russian. Results presented in Table 3 suggest that model can indeed correctly solve this task by setting correct gender to the numeral. Finally in Table 4 we show results on full sentences. Interestingly, on quite a complex Russian example our model was able to perform agreement. To select the correct form of word соседнем (neighbouring), network had to use multiple markers from different parts of a sentence: gender from подъезд (entrance) and case from в (in).

5.3. PERFORMANCE ON LONG SEQUENCES:

As a motivation for our model we argued that making shorter input-output paths may reduce information load of the embedding vector. To check this hypothesis we computed average sentence accuracy for different input lengths and reported results in Figure 3 .

We can clearly see that all baseline models perform worse as the input length increases. However, this is not the case for our model -while character-level models perform with almost 0% accuracy when input is 100 characters long, our model still gives similar performance as for short sentences.

This result can be explained by the way in which models use embedding vectors. Baseline models have to share embedding capacity between all words in a sentence. Our model, however, has a separate embedding for each word and does not require the whole sentence to be squeezed into one vector. It is also clear that character-level models perform better for short sequences (about 33% of the test set). This may be the case since the capacity of the embedding vector is not fully used for them. 

Nie dostaniesz więcej od nikogo innego:

Despite being worse for short inputs, our model can still handles many important cases quite well including those discussed in Section 5.2.

5.4. DIALOG CORPUS:

To evaluate our conversation model we constructed a corpus of question-answer pairs from web site Otvet.mail.ru -general topic Russian service for questions and answers (analogue of Quora.com). The uniqueness of this corpus is that it contains general knowledge questions that allow the trained model to answer questions about movies, capitals, etc. This requires many rare entity-related words to be in the vocabulary which makes it extremely large without normalization.

Q-CONCORDE VS CONCORDE:

First we compared Q-Concorde and Concorde models to show that Q-Concorde can indeed grasp important morphological features form a context. We also trained baseline models with context concatenated to input sentence (with a special delimiter in between). word and sentence accuracies are reported in Table 5 . Again, Concorde model was able to outperform baselines even though it didn't have access to the context. Also, Q-Concorde model was able to improve Concorde's performance. answer in corresponding tense. We also tried to change gender of a word "did" in a question: from masculine делал ) to feminine далала . Our model used the correct gender to generate the answer. While model generated grammatically correct answers in all three cases, in the third case (past simple, masculine) model answered in less common form with a meaning that differs from expected one. Finally, we apply Q-Concorde model to a proposed pipeline for training conversational models. We compare our model with a 3-layer character-level sequence-to-sequence model which was trained on grammatically correct sentences. For generating diverse answers we train two models: one to predict answer given question and the other to predict question given answer, as suggested in Li et al. (2015) . This allows us to discard answers that are too general.

To compare two models we set an experiment environment where assessors were asked to select one of two possible answers to the given question: one was generated by character-wise model and another was generated by our pipeline. Assessors did not know the order in which cases were shown and so they did not know which model generated the text. In 62.1% cases assessors selected the proposed model, and in the remaining 37.9% assessors preferred character-wise model.

5.5. COMPUTATIONAL COSTS:

We noticed that time for processing one batch is much higher for character-level models since they need to process longer sequences sequentially. In Table 9 we report time for forward and backward pass of one batch (16 objects) and other important computational characteristics. We measured this time on GeForce GTX TITAN X graphic card. It turns out that proposed models have comparable evaluation time, but train faster than unigram and hierarchical models.

:

http://www.lexiconista.com/datasets/lemmatization/

http://opus.lingfil.uu.se/OpenSubtitles2016.php

Figures and Tables:

Figure 1: Concorde model.

Figure 2: Q-Concorde model.

We compare our model to three baselines: unigram charRNN, bigram charRNN and hierarchical model. Unigram and bigram models are standard sequence-to-sequence models with attentionLuong et al. (2015) that operate with characters or pairs of characters as tokens. We use 2-layer LSTM as an encoder. Decoder consists of 2-layer LSTM followed by attention layer and another recurrent layer. The third baseline is a hierarchical model motivated byJohansen et al. (

Figure 3: Test accuracy on French corpus for different input lengths.

network: model learns to map input characters to output characters for each word using encoder-decoder sceme. The difference is that bidirectional neural network is used to distribute information between different words.

Table content: <table><tr><td>𝑎 #</td><td/><td>𝑎 "</td><td/></tr><tr><td>Char. LSTM</td><td/><td>Char. LSTM</td><td/></tr><tr><td>decoder</td><td/><td>decoder</td><td/></tr><tr><td>𝑎 # $</td><td>Bidirectional LSTM</td><td>𝑎 " $</td><td>…</td></tr><tr><td>Char. LSTM</td><td/><td>Char. LSTM</td><td/></tr><tr><td>encoder</td><td/><td>encoder</td><td/></tr><tr><td>𝑎 # %</td><td/><td>𝑎 " %</td><td/></tr></table>

Performance of our model for different languages. Results are reported in word accuracy (w) and sentence accuracy (s).

Table content: <table><tr><td/><td colspan="2">CharRNN</td><td colspan="2">Bigrams</td><td colspan="2">Hierarchical</td><td colspan="2">Concorde</td></tr><tr><td/><td>w</td><td>s</td><td>w</td><td>s</td><td>w</td><td>s</td><td>w</td><td>s</td></tr><tr><td>French</td><td colspan="8">train 84.53 50.83 53.47 39.36 85.34 51.54 89.18 58.34 test 83.10 50.50 53.08 40.35 83.03 50.52 87.90 56.86</td></tr><tr><td>Russian</td><td colspan="8">train 73.89 42.60 48.07 35.35 75.67 44.16 83.95 51.94 test 75.88 44.97 49.75 37.29 77.73 46.26 85.18 53.97</td></tr><tr><td>Polish</td><td colspan="8">train 70.40 38.51 45.58 31.16 70.50 38.30 79.51 45.10 test 70.41 38.02 44.07 31.10 70.71 38.31 79.76 44.93</td></tr></table>

Model inspection: single and plural forms.

Table content: <table><tr><td/><td colspan="2">Single</td><td/><td>Plural</td></tr><tr><td/><td>Normalized</td><td>Output</td><td colspan="2">Normalized Output</td></tr><tr><td>French</td><td>un château</td><td>Un château</td><td colspan="2">deux château Deux châteaux</td></tr><tr><td colspan="2">Russian один заяц</td><td>Один заяц</td><td>два заяц</td><td>Два зайца</td></tr><tr><td>Polish</td><td colspan="3">jeden ołówek Jeden ołówek dwa ołówek</td><td>Dwa ołówki</td></tr></table>

Model inspection: gender. f. is Feminine, m. is Masculine and n. is Neuter.

Table content: <table><tr><td/><td/><td/><td>Normalized</td><td>Output</td></tr><tr><td/><td>French</td><td colspan="2">f. m. un témoin un personne</td><td>Une personne Un témoin</td></tr><tr><td/><td colspan="2">Russian f.</td><td>один тарелка</td><td>Одна тарелка</td></tr><tr><td/><td/><td colspan="2">m. один пирог</td><td>Один пирог</td></tr><tr><td/><td/><td colspan="2">n. один растение</td><td>Одно растение</td></tr><tr><td/><td>Polish</td><td>f.</td><td>jeden kawa</td><td>Jedn ą kawa</td></tr><tr><td/><td/><td colspan="2">m. jeden człowiek</td><td>Jeden człowiek</td></tr><tr><td/><td/><td colspan="2">n. jeden mleko</td><td>Jedno mleko</td></tr><tr><td/><td/><td colspan="3">Table 4: Model inspection: examples</td></tr><tr><td>French</td><td colspan="4">Norm. il vouloir d l amour d le joie de le bon humeur</td></tr><tr><td/><td>Out.</td><td/><td colspan="2">Je veux d l amour d la joie de la bonne humeur</td></tr><tr><td colspan="5">Russian Norm. девочка элиса жить в соседний подъезд</td></tr><tr><td/><td>Out.</td><td/><td colspan="2">Девочка Элис живет в соседнем подъезде</td></tr><tr><td>Polish</td><td colspan="4">Norm. on dostać dużo oda nikt inny</td></tr><tr><td/><td>Out.</td><td/><td/></tr></table>

Performance of Q-Concorde and baselines on Otvet.mail.ru dataset.

Table content: <table><tr><td/><td colspan="2">CharRNN</td><td colspan="2">Bigrams</td><td colspan="2">Hierarchical</td><td colspan="2">Concorde</td><td colspan="2">Q-Concorde</td></tr><tr><td/><td>w</td><td>s</td><td>w</td><td>s</td><td>w</td><td>s</td><td>w</td><td>s</td><td>w</td><td>s</td></tr><tr><td colspan="11">train 72.95 38.75 47.43 34.81 74.69 35.36 81.61 44.43 83.04 48.24</td></tr><tr><td>test</td><td colspan="10">72.83 38.88 48.58 36.63 74.99 35.2 81.51 43.75 83.13 48.10</td></tr><tr><td colspan="11">We inspected cases on which Q-Concorde model showed better performance than Concorde (Table</td></tr><tr><td colspan="11">6). In example 1 of this table, question was asked about a single object. Q-Concorde model used</td></tr><tr><td colspan="11">singular form, while Concorde used plural. Q-Concorde was also able to successfully carry correct</td></tr><tr><td colspan="7">case (example 2) and time (example 3) from the question.</td><td/><td/><td/></tr></table>

Cases on which Q-Concorde is better than Concorde.

Table content: <table><tr><td/><td>Question</td><td>какой ты человек сложный или с тобой все просто</td></tr><tr><td>1</td><td>Concorde</td><td>простые и добрые</td></tr><tr><td/><td colspan="2">Q-Concorde простой и добрый</td></tr><tr><td/><td>Question</td><td>что прячут под вуалью</td></tr><tr><td>2</td><td>Concorde</td><td>тайна</td></tr><tr><td/><td colspan="2">Q-Concorde тайну</td></tr><tr><td/><td>Question</td><td>вас матери сколько носили месяцев</td></tr><tr><td>3</td><td>Concorde</td><td>по стандарту выносят</td></tr><tr><td/><td colspan="2">Q-Concorde по стандарту выносили</td></tr></table>

Cases on which Q-Concorde is worse than Concorde.

Table content: <table><tr><td/><td>Question</td><td>какой тарифный план выбрать</td></tr><tr><td>1</td><td>Concorde</td><td>позвоните вашему оператору</td></tr><tr><td/><td colspan="2">Q-Concorde позвони вашему оператору</td></tr><tr><td/><td>Question</td><td>что у вас на завтрак</td></tr><tr><td>2</td><td>Concorde</td><td>только поцелуи</td></tr><tr><td/><td colspan="2">Q-Concorde только поцелуй</td></tr></table>

Inspection of Q-Concorde model.

Table content: <table><tr><td>Question</td><td colspan="2">Normalized answer Answer</td></tr><tr><td>чего ты делаешь</td><td/><td>я хожу гулять</td></tr><tr><td>чего ты делала</td><td>я хожу гулять</td><td>я ходила гулять</td></tr><tr><td>чего ты делал</td><td/><td>я ходил гулял</td></tr><tr><td>5.4.1 CONVERSATION MODEL</td><td/><td/></tr></table>

Peer review (iclr2018):
 The key contributions of this paper are: (a) proposes to reduce the vocabulary size in large sequence to sequence mapping tasks (e.g., translation) by first mapping them into a "standard" form and then into their correct morphological form, (b) they achieve this by clever use of character LSTM encoder / decoder that sandwiches a bidirectional LSTM which captures context, (c) they demonstrate clear and substantial performance gains on the OpenSubtitle task, and (d) they demonstrate clear and substantial performance gains on a dialog question answer task. Their analysis in Section 5.3 shows one clear advantage of this model in the context of long sequences. As an aside, the authors should correct the numbering of their Figures (there is no Figure 3) and provide better captions to the Tables so the results shown can easily understood at a glance. The only drawback of the paper is that this does not advance representation learning per se though a nice application of current models.