Recursive Neural Network Paraphrase Identification
for Example-based Dialog Retrieval
Lasguido Nio, Sakriani Sakti, Graham Neubig, Tomoki Toda, Satoshi Nakamura
Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama-cho, Ikoma, Nara 630-0192, Japan
E-mail: {lasguido.kp9,ssakti,neubig,tomoki,s-nakamura}@is.naist.jp

Abstract—An example-based dialog model often require a lot ofdata collections to achieve a good performance. However, when it
comes on handling an out of vocabulary (OOV) database queries,
this approach resulting in weakness and inadequate handlingof interactions between words in the sentence. In this work,
we try to overcome this problem by utilizing recursive neuralnetwork paraphrase identification to improve the robustness of
example-based dialog response retrieval. We model our dialogpair database and user input query with distributed word
representations, and employ recursive autoencoders and dynamic
pooling to determine whether two sentences with arbitrary length
have the same meaning. The distributed representations have thepotential to improve handling of OOV cases, and the recursive
structure can reduce confusion in example matching.

I. I NTRODUCTION
Rule based dialog system is a popular technique in utilizing
example conversation to generate a hand-made rule for chatoriented dialog system response generation. This techniquesachieved a current state of the art in the intelligent machine
test so called the Turing Test1 . To simplify work, rule based
technique is often created with an open source tools [1] thateasy to use. Behind it success, the rule based technique rely on
the humans hand-made rule that is complicated and difficult
to be expanded.
In other hand, the data-driven approach is not much explored technique that could overcoming this shortage. Given
the user input, this method search and generate a response
based on the conversation database. Comparing to the rule
based technique [2], [3], data-driven based doesn’t rely on
the complicated hand-made rules and easy to expanded. Thisapproach allows for the use of large amounts of data on the
Web to efficiently find responses for a large variety of user
queries, and becomes popular as lightweight methods to create
broad-coverage chat-oriented dialog systems [4], [5], [6], [7].
However, To achieve the good coverage, recording of a large
data set of real human-to-human conversation is necessary,and some studies propose constructing dialog examples fromavailable log databases created using Wizard of OZ (WOZ)
systems [8] or Twitter [9].
An example based dialog modeling (EBDM) is one ofmany approach to data-driven framework. It works by matching the user’s utterance with a query in the query-response
database, then returning the response that corresponds with the
1 http://people.exeter.ac.uk/km314/loebner2013/index.php

most closely matching query. By retrieving examples from a
database and displaying the response to the user, EBDM isonly able to generate examples that are actually included in
the database. Because of this, it is able to generate highly
natural output when a response is included in the database
and the example is able to be appropriately retrieved [4],[5], [6]. However, we can think of a number of situations
in which these simplistic methods are clearly inadequate. For
example, if the user’s utterance is “it is not raining today,”previously proposed matching methods will give “it is raining
today” a high score, and the system may provide the exact
opposite response a user desires. When the system is notable to find similar examples to determine the response, most
EBDM systems currently rely on either canned or template
response which may result in less than satisfactory output [10],[11].
In general, two factors contribute greatly to the accuracyof EBDM systems: the coverage of the dialogue corpus,
and the effectiveness of the example retrieval. We focus
particularly on the latter of these problems in EBDM systems,
arguing that more sophisticated methods for matching user
utterances and queries in the database are necessary. We notethat compositional distributional representation using neuralnetworks [12], [13] may have a potential to capture a large
number of linguistic phenomenon or a simpler one such asparaphrase. In this work, we introduce a new approach inapplying these representations to matching the user utterance
and queries in the database. Furthermore, we utilized dialog
corpora constructed from movie conversation data as a testbed
for the proposed method.
II. R ELATED W ORK
There have been a number of related work in response
retrieval and paraphrase detection field. It utilizes several
feature raging from the lexical matching feature [14], [15],[16], Wordnet-based semantic similarity measure [17], [18],and syntactic measure [19].
A method to detect paraphrase with a compositional distributional representations using neural networks previously
proposed by Socher et al. [20]. This method had becomea state of the art of paraphrase detection method. Usinga similar approach, we build a paraphrase detection modelout of dialog pair conversation corpus. Later, we utilize ourparaphrase model to retrieve an appropriate response in thedialog database to the user, especially when the system can
not find any match response in the example database (OOV
case).
III. OVERALL D IALOG S YSTEM
Figure 1 depicts an overview of our dialog system. User
input is treated by the dialog management system as a queryto our response generator module. Given the user input, our
response generator will search appropriate response throughthe database with the EBDM response retrieval in the firstplace. If there is no matched or related example dialog pairin the database, response generator will encounters OOV
problem. At this point, usually the system responses will outof topics and not related to the user input. We overcome
this condition by using the paraphrase retrieval to retrieve theappropriate response from the example database. To be noted
that, in this paper we focus on exploring the neural-networkbased retrieval performance.

Fig. 2. Overview of neural-network-based retrieval.

each word in dictionary (i ∈ D) is embedded into ndimensional space L ∈ Rn×|D| . From this representation, aword vector can be seen as a single vector in the column L.
B. Recursive Autoencoder
By using the RAE algorithm, we combine word representations in a syntactic parse tree into a vector representationsof longer phrases. This approach is intends to capture thecompositionality of meaning that is naturally constrained by
the syntactic parse tree. To construct the final vector representation, this algorithm takes a word representations and abinary syntactic tree as an input.
In this algorithm, every child and non-terminal node in
the binary tree is collected as a feature representation of asentence. The binary tree forms the parent and children triplets(p → c1 c2 ) where each child could be a word representations
vector or the other non-terminal nodes. A parent p is calculated
through the neural network layer (Equation (1))

Fig. 1. Dialog Management System.

IV. N EURAL N ETWORK BASED R ETRIEVALA proper system response is retrieved by modeling example
database into neural word representation and calculating theprobability between the user input and an example in the
database. An overview of the paraphrased based retrieval is
depicted in Figure 2.
Adopting the work of [20], we utilize recursive autoencoders (RAE), dynamic pooling, and a softmax classifier todecide weather the sentence is paraphrased or not. In thefollowing section we describe about: (1) neural language
model, which computes a word representation as an input tothe RAE, (2) recursive autoencoders, and (3) dynamic pooling.
A. Word Representations
A distributed word representation is a n-dimensional vector
of continuous values used to represent a word in the vocabulary. They are often obtained by joint learning of neuralnetwork language models and distributed representation forwords [21]. Improved word representations [13] are known tocapture distributional syntactic and semantic information via
the word co-occurrence statistics. In a word representation,p = f (We [c1 ; c2 ] + b),(1)

where [c1 ; c2 ] is concatenation of the two children and f is atanh activation function. The weight (We ) and bias (b) value
are trained using recursive autoencoders [20].
C. Dynamic Pooling
After obtaining the RAE-derived representation of the sentence, next we would like to calculate the similarity of two
sentences. In order to do so, we need to deal with thearbitrary length of the sentence. Thus, we need to normalized
the RAE word representations into a fixed length vector
with an algorithm called dynamic pooling. As we described
previously, every sentence fed into the RAE forms a binary
tree representation. Given this, we can define a matrix M ,where the rows and columns in this matrix represent two
sentences with the different lengths i and j. This row andcolumn represents the non-terminal nodes and leaves in thebinary tree, therefore the matrix M ’s size is 2i − 1 × 2j − 1.
This algorithm takes a matrix M as an input and output amatrix M 0 with the fixed size n × n. In this algorithm, matrix
M will be divide into n roughly equal parts. Every minimalvalue in the rectangular window is selected to form a n × ngrid. During this process, matrix M 0 will lose some part of theinformation compared to the original matrix M [20]. But thisapproach manages to capture the matrix M ’s global structure.
Given the uniform size of matrix M 0 from every sentence,
we classify each utterance similarity using a softmax classifierlayer afterwards. The softmax classifier takes the matrix M 0 as
an input, and outputs a confidence score that decided whether
a user input and dialog database is a paraphrase or not.
V. E XPERIMENTAL S ETUP
A. Dialog Corpora
In this work, we use a movie scripts to build our dialog
corpus. We collect our movie script dialogues based on Friends
TV show scripts2 , The Internet Movie Script Database3 , andThe Daily Script4 . The total number of gathered movie scripts
is 1,786 with 1,042,288 dialog pairs. More details on the data
can be found in [22]In our movie dialog corpus, we define two basic typesof information for each dialog: actor and utterances. The
utterances are the actual content of each dialog turn in themovie scripts. The actor refers to the character name in themovies. This actor and utterance information will be utilizedin construct the dialog corpus.
B. Filtering
In our previous study, we have introduce a tri-turn unit
to find the candidate of dialog-pairs [23]. Given the HTML
format of movie script as input, we construct a dialog corpus
by perform a filtering as follows,
1 Preprocessing, which removes unnecessary informationand normalize the text. This step is done by transforming
raw HTML files into raw text format. To transforma variety of sources of movie scripts that had various
formats, we implemented several parsing algorithms tofetch the information from the raw movie conversation.
We also remove unnecessary explanatory information
about the movie scenes.
2 The extraction of a dialog-pairs, which ensures that theconversation is done between two people talking eachother. We perform dialog (tri-turn) extraction to find thecandidate of dialog-pairs to construct appropriate dialogpair examples from raw movie scripts files. A tri-turn isa three conversation turns between two actors X and Y
that has the pattern X-Y-X. In one tri-turn, the first andlast dialog turn are performed by the same actor andthe second dialog turn is performed by the other actor.
Later the query-response pairs are made by separating
the tri-turn pattern X-Y-X into two pairs, X-Y and Y-X.
3 Semantic similarity calculation, which ensure that theeach query-response pair is semantically related. To
ensure the semantic relationship between dialog-pairs,
semantic similarity [24] as shown in Equation (2) is
performed. The similarity of sentence X and Y can beobtained by calculating the relation between Xsyn andYsyn . Xsyn and Ysyn respectively is a group of WordNet5 synsets for each word in the sentence X and Y thatare linked by a complex network of lexical relations.
Every dialog pair with high similarity is included as an
example database.
2 × |Xsyn ∩ Ysyn |(2)
semsim (X, Y ) =|Xsyn | + |Ysyn |C. NN-based Retrieval Setup
In our experiment, we use the trained RAE with 150,000
sentences from NYT and AP section of the Gigaword corpus
provided by Socher et al. [20]. To generate all the parsetrees for the RAE algorithm, we use the Stanford parser [25].
We also employ the 100-dimensional word representations
computed and provided by Turian et al. [26]. Furthermore,
we use natural language processing tools and Wordnet synsets
provided by the NLTK toolkit6 , and Apache Lucene7 to
calculate the TF-IDF based cosine similarity.
After performing pre-processing, filtering, and picking somewords to be transformed into a vector of word representations,
we finally use 10,033 dialog pairs as our training and test data.
During the experiment, we randomly separate our dialog pairs
data into 1,000 and 9,033 pairs consecutively as test and train
dialog pairs data.
When training the NN-based retrieval model, we need toconsider that the NN-based retrieval model is also rely on thesoftmax classifier layer. This layer decide whether a user queryand dialog database is similar or not. To provide a balance
amount of similar and not similar query during training, we
do cross product all the training dialog (9,033 pairs) witheach other and calculate the syntactic-semantic similarity (seeEquation 3) between them. We assume that the similar queryis obtained when the syntactic-semantic score is exclusively
between 0.7 and 0.9, and not similar query is obtained when
the syntactic-semantic score is exclusively between 0.2 and
0.4. In the end, we got 1,421,338 pair of dialog train with theratio between similar and not similar sentence is 50:50 .
sim(S1 , S2 ) = α[semsim (S1 , S2 )] + (1 − α)[cossim (S1 , S2 )](3)
VI. P ERFORMANCE OF NN-BASED R ETRIEVAL
Table I shows the correlation between user input and example database. We calculate syntactic-semantic score sim foreach utterance pair (S1 and S2). We observed that when autterance pair have a high similarity score (a similar pair),it will generates a clear diagonal structure of dark line in
the matrix representation. This matrix shows the paraphrase
relations between two utterances. A clear diagonal structureof dark line in the matrix was a result from the Euclidean
distance computation. During this case, the NN-based retrieval
is manage to find a close/paraphrased sentence to the input
query.

2 http://ufwebsite.tripod.com/scripts/scripts.htm

5 http://wordnet.princeton.edu/

3 http://imsdb.com/

6 http://nltk.org

4 http://dailyscript.com/

7 http://lucene.apache.org/

In NN-based retrieval (RNN) approach, given the user input
the system will find a paraphrased input sentence in the dialog
pair example database. Later, it will outputs the corresponding
response from the matched dialog pair. The comparison of the
RNN with EBDM TF-IDF based cosine similarity (ebdm) canbe seen in the table II.
sim
0.94

0.93

0.65

Sentences
S1 ) Captain, we can not keep
going fast on these icy roads.

MatrixS2 ) We can not keep going
fast on these icy roads!
S1 ) I’ll see you there.
S2 ) I’ll see you.
for say to myself?
S1 ) So what do you haveto say for yourself?

0.60

S2 ) Why should I have anything
for say to myself?
S1 ) Hold your fire! He’s
got a girl.

0.50

S2 ) Looks like he’s got a hostage.
S1 ) I’ve been careful, I’ve
been waiting my chance.

0.38

S2 ) Oh, you’ve been under a lot of stress.
S1 ) Yes, I can see that too
and I don’t think it’s so terrible.
S2 ) That’s why I do all the thinking.
TABLE IS ENTENCE PAIRS .

user input
I own this store.

I am not!

That look you justgave me?

ebdm response
Who told you to buy
a brownstone on myblock, in my neighborhood on my sideof the street?
I can’t speak for myfriend, but my friend
is in a loving, committed relationship.
But you gave me aticket to the Super
Bowl. Hand it over,
my friend.

rnn response
What are you talking
about? You love yourjob.

You’re wrong.

I do. I want to very
badly.

TABLE II
EBDM AND RNN R ESPONSE COMPARISON .

VII. C ONCLUSION
In this paper, we investigated recursive neural network
paraphrase identification techniques in order to retrieve responses in a data-driven chat-oriented dialog system. The
experiment shows that the neural network based retrieval isable to capture the correlation between user input and example
database especially when the user input is not available in theexample database (OOV case). As future work, exploring andapplying the neural network word representations into dialog
example database can be a promising future direction.
ACKNOWLEDGMENT
Part of this work was supported by JSPS KAKENHI Grant
Number 26870371.
R EFERENCES[1] R. S. Wallace, “The anatomy of a.l.i.c.e.” in Parsing the Turing Test,
R. Epstein, G. Roberts, and G. Beber, Eds. Springer Netherlands, 2009,
pp. 181–210.

[2] J. Weizenbaum, “Eliza - a computer program for the study of natural
language communication between man and machine,” Commun. ACM,
vol. 9, no. 1, pp. 36–45, 1966.
[3] R.Wallace, Be Your Own Botmaster. A.L.I.C.E A.I. Foundation, 2003.
[4] S. Jung, C. Lee, and G. Lee, “Dialog studio: An example based spoken
dialog system development workbench,” in Proc. of the Dialogs on dialog: Multidisciplinary Evaluation of Advanced Speech-based Interactive
Systems. Interspeech 2006-ICSLP satellite workshop,, Pittsburgh, USA,2006.
[5] C. Lee, S. Lee, S. Jung, K. Kim, D. Lee, and G. Lee, “Correlation-based
query relaxation for example-based dialog modeling,” in Proc. of ASRU,
Merano, Italy, 2009, pp. 474–478.
[6] K. Kim, C. Lee, D. Lee, J. Choi, S. Jung, and G. Lee, “Modelingconfirmations for example-based dialog management,” in Proc. of SLT,Berkeley, California, USA, 2010, pp. 324–329.
[7] A. Ritter, C. Cherry, and W. B. Dolan, “Data-driven response generation
in social media,” in Proc. of EMNLP, Edinburgh, Scotland, UK., July
2011, pp. 583–593.
[8] H. Murao, N. Kawaguchi., S. Matsubara, Y. Yamaguchi, and Y. Inagaki,“Example-based spoken dialogue system using WOZ system log,” inProc. of SIGDIAL, Saporo, Japan, 2003, pp. 140–148.
[9] F. Bessho, T. Harada, and Y. Kuniyoshi, “Dialog system using real-time
crowdsourcing and twitter large-scale corpus,” in Proc. of SIGDIAL,
Seoul, South Korea, 2012, pp. 227–231.
[10] C. Lee, S. Jung, S. Kim, and G. G. Lee, “Example-based dialog
modeling for practical multi-domain dialog system,” Speech Commun.,vol. 51, no. 5, pp. 466–484, May 2009.
[11] N. Chambers and J. Allen, “Stochastic language generation in a dialoguesystem: Toward a domain independent generator.” in Proc. of SIGDIAL,
Cambridge, Massachusetts, USA, 2004, pp. 9–18.
[12] R. Socher, B. Huval, C. D. Manning, and A. Y. Ng, “Semantic compositionality through recursive matrix-vector spaces,” in Proc. of EMNLP,
2012.
[13] R. Collobert and J. Weston, “A unified architecture for natural language
processing: Deep neural networks with multitask learning,” in Proc. of
ICML, New York, NY, USA, 2008, pp. 160–167.
[14] R. E. Banchs and H. Li, “IRIS: a chat-oriented dialogue system basedon the vector space model,” in Proc. of ACL (System Demonstrations),
2012, pp. 37–42.
[15] R. E. Banchs, “Movie-dic: a movie dialogue corpus for research anddevelopment.” in Proc. of ACL, 2012, pp. 203–207.
[16] L. Qiu, M.-Y. Kan, and T.-S. Chua, “Paraphrase recognition via dissimilarity significance classification,” in Proc. of EMNLP, Stroudsburg, PA,
USA, 2006, pp. 18–26.
[17] L. Nio, S. Sakti, G. Neubig, T. Toda, and S. Nakamura, “Combinationof example-based and smt-based approaches in a chat-oriented dialog
system,” in Proc. of ICE-ID, 2013.
[18] A. Islam and D. Inkpen, “Semantic similarity of short texts,” in Proc.
of RANLP, Borovets, Bulgaria, September 2007.
[19] D. Das and N. A. Smith, “Paraphrase identification as probabilistic
quasi-synchronous recognition,” in Proc. of ACL-IJCNLP, Stroudsburg,
PA, USA, 2009, pp. 468–476.
[20] R. Socher, E. H. Huang, J. Pennington, A. Y. Ng, and C. D. Manning,“Dynamic pooling and unfolding recursive autoencoders for paraphrase
detection,” in Advances in Neural Information Processing Systems 24,
2011.
[21] Y. Bengio, R. Ducharme, P. Vincent, and C. Janvin, “A neural probabilistic language model,” J. Mach. Learn. Res., vol. 3, pp. 1137–1155,
Mar. 2003.
[22] L. Nio, S. Sakti, G. Neubig, T. Toda, and S. Nakamura, “Utilizing human-to-human conversation examples for a multi domain chatoriented dialog system,” IEICE Transactions on Information and Systems, June 2014.
[23] L. Nio, S. Sakti, G. Neubig, T. Toda, M. Adriani, and S. Nakamura,“Developing non-goal dialog system based on examples of drama
television,” in Proc. of IWSDS, Paris, France, 12 2012.
[24] D. Liu, Z. Liu, and Q. Dong, “A dependency grammar and wordnet based
sentence similarity measure,” Journal of Computational Information
Systems, vol. 8, no. 3, pp. 1027–1035, 2012.
[25] D. Klein and C. D. Manning, “Accurate unlexicalized parsing,” in Proc.
of ACL, Stroudsburg, PA, USA, 2003, pp. 423–430.
[26] J. Turian, L. Ratinov, and Y. Bengio, “Word representations: A simple
and general method for semi-supervised learning,” in Proc. of ACL,
2010.