人工知能学会研究会資料
SIG-SLUD-B402-01

Robust Example-based Dialog Retrieval using Distributed Word
Representations and Recursive Autoencoders
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: Based on our previous work on example-based chat-oriented dialog systems that utilize a human-to-human conversation. Though promising, our previous simple retrieval techniques
resulting a weakness on handling an out of vocabulary (OOV) database queries. In this paper we
discuss an approach to increase the robustness of example-based dialog response retrieval. We employ a recursive neural network paraphrase identiﬁcation technique to achieve a good performanceon ﬁnding a good response in dialog-pair database. To achieve that, we remodel our previous
dialog-pair database into distributed word representation. We apply an recursive autoencoders
and dynamic pooling algorithm between user utterance and database to decide whether they havea same meaning or not, even when they composed in diﬀerent word and structure. These distribute
representations and recusive autoencoders have the potential to enhance our retrieval techniques
and reduce confusion in example matching, especially when handling an OOV cases. We alsopresent the system performance evaluation based on objective and subjective metrics.

1

Introduction

Recently, an intelligent dialog system that can givea natural response gain more attention. Despite a demand on speciﬁc task dialog system, researcher are
seeing increasing interest in developing an lightweightdata-driven methods to cover broad-coverage chatoriented dialog systems [1, 2, 3, 4]. It becomes more
attractive because, comparing to the rule based technique [5, 6], these method doesn’t rely on the complicated hand-made rules and easy to expanded. Datadriven approaches allow for the use of large amountsof data on the Web to eﬃciently ﬁnd responses fora large variety of user queries. However, to achieve
broad coverage, recording of a large data set of realhuman-to-human conversation is necessary. Some studies propose constructing dialog examples from available log database like Twitter [8] or Wizzard of Oz(WOZ) [7].
Example-based dialog modeling (EBDM) is one ofmany approach to data-driven dialog. As one of thedata driven approaches, EBDM utilize a data thatconsists of query-response pairs. Where the queryis representative of the user’s input to the system,and the response is representative of the system’s response. By simply generate an answer that are actu-

ally included in the database as an example, EBDM
is able to generate an highly natural output when a
response is included in the database, especially when
the user utterance is included in the database and theexample is able to be appropriately retrieved [1, 2, 3].
Despite these advantages, EBDM may response uncorrelated response when the system could not ﬁndany example in the database. Most EBDM systemrely on canned or template response to handle thisproblem [9, 10], which may resulting in less than unsatisfactory output.
In most cases, EBDM employs response retrieval
techniques to match up the user’s utterance with aquery in the query-response database. Later, it will
outputs a response that correspond to the matchingquery. The greater number of previous work performs
response retrieval by using a simple lexical measuresuch as TF-IDF weighted cosine similarity [11, 12]or syntactic-semantic similarity based on POS strings
and WordNet synsets [13]. Still, these simple response
retrieval techniques are not suﬃcient enough to comprehend a number of situations like retrieving a simple logic manipulation or paraphrase sentence in theexample database.
There are two factors that greatly contribute to the−1−accuracy of EBDM systems: (1) the coverage of the
dialogue corpus, and (2) the eﬀectiveness of the example retrieval. In this work, we focus on latter these
problems, especially on employing more sophisticatedmethod for matching user utterances and queries inthe example database.
In this work, we rely on the great improvement in
distributional representations of language using vector space word representations [14]. This compositional distributional word representation that built
upon a neural networks [15] may have a potential tocapture a large number of linguistic phenomenon. Following the successful work of Socher et al. [16], we also
employ recursive autoencoders model to match theuser utterance and queries in the example database.
In the end, we evaluate our proposed method subjectively and objectively by utilizing dialog corpora constructed from movie conversation data as a testbed.

2

Dialog System and Baseline
EBDM

Generally, EBDM chooses a response from the examples database by computing similarity measure between the user input and the query part of the queryresponse pairs. Then, it returns the associated response for the query with the highest similarity. Basedon the previous work [17, 18], we utilize TF-IDF based
cosine similarity as the baseline similarity measure foruse in EBDM.
TF-IDF based cosine similarity calculates cosine
similarity (Equation (1)) over the term vector of two
sentences, S1 and S2 . In order to increase the emphasis on important words, We applied additional TFIDF weighting to the term vector (Equation (2)) [19].
We set Ft,T as a term frequency t in a sentence T , andDFt as the total number of sentences in the queryresponse pairs that contain term t.
S1 · S2
cossim (S1 , S2 ) =(1)∥ S1 ∥ ∥ S2 ∥()|T |T F IDF (t, T ) = Ft,T log
(2)
DFt

3

proposed method employ neural network-based retrieval to retrieve more appropriate responses fromthe example database. In this method, a proper system response is retrieved by modeling our example
database using neural word representations and calculating the probability that the user input and a queryin the database are paraphrases.
An overview of the neural-network-based retrieval
is depicted in Figure 1. To decide weather the sentence is paraphrased or not, we utilize recursive autoencoders (RAE), dynamic pooling, and a dynamic
pooling’s softmax classiﬁer, adopting the work of [16].

Neural Network Based
RetrievalThough simple, a cosine similarity method haveproblems with robustness, which we will discuss inmore detail in the following sections. Therefore, our

図 1: Overview of neural-network-based retrieval.

3.1

Word Representation

Word representation are obtained with discriminative and non-probabilistic model [14], in which a wordin the dictionary (i ∈ D) is embedded into q-dimensional
space S ∈ Rq×|D| . During training, the model concatenate n embedded word e(i), where e is the lookup
table and i is a word in dictionary. For every training update, the model read n-gram x = (i1 , i2 , ..., in )from the corpus. For every n-gram x, the concatenated model E(x) = e(i1 ) · e(i2 ) · ... · e(in ) (“·” is concatenation) will be passed through single hidden layer
neural network to predict the score s(x). We deﬁnex′ = (i1 , i2 , ..., i′n ) as a noise n-gram, where the lastword of the n-gram i′n ̸= in is chosen uniformly fromthe vocabulary [20].
The training runs based on the criterion that the
input n-gram x must have a score at least some margin higher than the noise n-gram x′ . By minimizing
the loss stochastic L(x) = max(0, 1 − s(x) + s(x′ )),the training do the gradient descent simultaneously
over the neural network parameter and the embedding lookup table. In the end, the embedding lookup
table is the output product of the training process.
By improving this representation with the word co-−2−

occurrence statistics, this representation may capture
distributional syntactic and semantic information [14].
One of the word representation advantage is thatthey allow for soft matching of similar words, especially when there is no exact match. For instance,
if we have an input sentence “I like to frequent taverns” that is unavailable in the example database, ourexisting response generator will fail and response theuser input with an uncorrelated response because it
could not ﬁnd any in the database. However, by using
distributed word representation, we could match theabove sentence with another sentence that semantically similar but has diﬀerent words such as “visit”
for “frequent” and “bars” for “taverns”.

3.2

performance is evaluated through the Euclidean distance between original input and its estimated reconstruction node (Equation (4))

where

(4)

[c′1 , c′2 ] = f (Wd p + bd ).

(5)

This process will be repeated recursively for all nonterminal nodes. In the course of RAE training, wewant to minimize the total error of all inputs pairs
on every non-terminal node. The total error can beobtain by adding up all the calculated error from asingle parse tree T∑
Etree (T ) =
E(p).
(6)
p∈T

Recursive Autoencoder

Now we have word representation to represent eachword in the dictionary. In order to represent a sentence which is a group of sentence, we need to string
up the word to each other. We will use the RAE algorithm to do that part. This algorithm combines word
representation into vector representations of longer
phrases in a syntactic parse tree. By using the syntactic parse tree, this algorithm may capture the compositionality of meaning that is naturally constrained by
the tree. To construct the vector representation, thisalgorithm needs word representations and a binarysyntactic tree as input.

図 2: Recursive autoencoder model.
During construction, every child and non-terminal
node in the binary tree is collected as a feature representation of a sentence. A binary tree is composed byparents and its children that form a triplets relationship (p → c1 c2 ). A child could be a word representation vector or another non-terminal nodes. A parent p
is calculated through the neural network layer (Equation (3)).

p = f (We [c1 ; c2 ] + b),

E(p) = ||[c1 ; c2 ] − [c′1 ; c′2 ]||2(3)

where [c1 ; c2 ] is concatenation of the vector of twochildren and f is a tanh activation function.
The parameters We and b are trained using recursive autoencoders as shown in Figure 2. The RAE

One advantage of using recursive autoencoder isthat it can capture the compositional structure ofphrases and their similarity within the two given sentences. For example, a sentence “tons of stuﬀ to throwaway” and “a lot of junk to dispose” there are relationship between words and phrases such as “tonsof stuﬀ” with “a lot” and “throw away” with “dispose”. Using the recursive autoencoder, we can not
only capture the word paraphrase similarity, but also
the phrase similarity.

3.3

Dynamic Pooling and Softmax Classifier

Once we obtained the RAE-derived representationof the sentence, we would like to calculate the similarity of two sentences. To achieve that, we need to deal
with the arbitrary length of the sentence. Thus, normalizing the RAE word representations into a ﬁxed
length of vector become necessary. Given the binary
tree representation of a sentence, we can deﬁne a matrix M , where rows and columns in this matrix represent two sentences with the diﬀerent lengths i andj. This row and column represents the non-terminal
nodes and leaves in the binary tree, therefore the matrix M ’s size is 2i − 1 × 2j − 1.
In dynamic pooling, we aim to takes a matrix M as
an input and output a matrix M ′ with the ﬁxed sizen × n. In order to do so, matrix M will be divided
into n roughly equal parts. Every minimal value in therectangular window is selected to form a n × n grid.
During this process, matrix M ′ will lose some partof the information compared to the original matrix
M [16]. But this approach manages to capture thematrix M ’s global structure.

−3−By obtaining the uniform size of matrix M ′ from thegiven two sentence, next we classify matrix M ′ using asoftmax classiﬁer. Softmax classiﬁer takes the matrix
M ′ as an input, and outputs a conﬁdence score that
decided whether a user utterance and dialog databaseis a paraphrase or not.

4

Experimental Setup

4.1

Dialog Corpora

4.3

A dialog corpus used in this experiment is collectedfrom several movie script source such as Friends TV
show scripts1 , The Internet Movie Script Database2 ,and The Daily Script3 . 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 [18]. In general, we deﬁne two basic types of information for eachdialog: actor and utterances. The utterances are theactual content of each dialog turn in the movie scripts.
The actor refers to the character name in the movies.
Later, this information will be utilized in constructing
the dialog corpus.

4.2

of WordNet4 synsets for each word in the sentence X and Y . Next, every high similarity dialog pair will be included as an example database.
2 × |Xsyn ∩ Ysyn |semsim (X, Y ) =(7)|Xsyn | + |Ysyn |Filtering

In our previous study, we have introduce a tri-turnunit to ﬁnd the candidate of dialog-pairs [17]. Given
the HTML format of movie script as input, we construct a dialog corpus by perform a ﬁltering as follows,
1 The extraction of a dialog-pairs, which ensures that the conversation is done between two
people talking each other. To obtain two-way
conversation script, we perform dialog (tri-turn)
extraction to ﬁnd the candidate of dialog-pairs.
A tri-turn is a three conversation turns between
two actors X and Y that has the pattern X-YX. In tri-turn, the ﬁrst and last dialog turn are
performed by the same actor and the second dialog turn is performed by the other actor. Laterthe query-response pairs are made by separating the tri-turn pattern X-Y-X into two pairs,
X-Y and Y-X.
2 Semantic similarity calculation, which ensure that each query-response pair is semantically related. This process employs semantic
similarity [21] as shown in Equation (7). The
similarity of sentence X and Y can be obtainedby calculating the relation between Xsyn andYsyn , where Xsyn and Ysyn respectively is a group

EBDM Setup

We perform the ﬁltering on the EBDM example
database by using natural language tools and Wordnet synsets provided by NLTK toolkit5 . We also use
Apache Lucene6 to calculate the TF-IDF based cosine similarity. During experiment, we deﬁne Qtest as
a query from the test set. In order to get the appropriate response similar to the actual response Rtest ,we use two retrieval techniques, TF-IDF based cosine similarity retrieval cossim (Qtest , Qtrain ) and NNbased retrieval rnn(Qtest , Qtrain ). They are used toobtain the closest query Qtrain in the train database.
The response Rtrain that trails the closest query isgiven as an output response.

4.4

NN-Based Retrieval Setup

During the experiment, we employ the 100-dimensional
word representation computed and provided by Turian
et al. [20]. We also use the trained RAE with 150,000
sentences from NYT and AP section of Gigaword corpus, provided by Socher et al. [16]. As an input
for RAE, we use Stanford parser [22] to generate theparse tree for our conversation dialog database.
After performing pre-processing, ﬁltering, and choosing dialog pairs that can be transformed into a vectorof word representations, we ﬁnally use 10,033 dialog
pairs as our training and test data. We randomly separate our dialog pair data into 1,000 dialog pairs fortest and 9,033 dialog pairs for train.
In order to provide a balance amount of similar andnon-similar queries during training, we do cross product to all training dialogues (9,033 pairs) with eachother, and calculate the the syntactic-semantic similarity [18]sim(S1 , S2 ) = α[semsim (S1 , S2 )]+(1−α)[cossim (S1 , S2 )].
We assume that a similar query is obtained when
the syntactic-semantic score is exclusively between 0.7
and 0.9, and a non-similar query is obtained when
the syntactic-semantic score is exclusively between 0.2

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

4 http://wordnet.princeton.edu/

2 http://imsdb.com/

5 http://nltk.org

3 http://dailyscript.com/

6 http://lucene.apache.org/−4−and 0.47 . In the end, we obtained 1,421,338 pairs of
training data with the ratio between similar and nonsimilar sentences being 50:50.

5Evaluation

5.1

Performance of NN-Based Retrieval

sim

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

Matrix

0.94

0.60

0.50

S2 ) We can not keep going
fast on these icy roads!
S1 ) Hold your fire! He’s
got a girl.
S2 ) Looks like he’s got a hostage.
S1 ) I’ve been careful, I’ve
been waiting my chance.
S2 ) Oh, you’ve been under a lot of stress.

表 1: Sentence pairs.

The correlation between user input and example
database can be seen in the Table 1. For each utterance pair (S1 and S2) we calculate syntactic-semantic
score sim. The rightmost column contain a matrix
representation that depict the paraphrase relations
between two utterances. As seen in the matrix representation, when a utterance pair have a high similarity
score (a similar pair), it will generates a clear diagonal structure of dark line. This diagonal structure
was a result from the Euclidean distance computation. When this diagonal structure is clearly seen,
NN-based retrieval is manage to ﬁnd a close or paraphrased sentence to the input query.

5.2

scoring model (rnn and csm) that we use for retrieving the system response.
In our observation, we found out that the two methods have roughly similar results. In order to look moreclosely at the evaluation results, we split all testingdata into three cases (Table 2) based on each system’s
retrieval score.
1 Case 1 (closest example found; CEF) when the
csm retrieval score is more than a threshold.
During this case, the csm has managed to ﬁnd
a close example in the database.
2 Case 2 (out of vocabulary; OOV) when the csm
retrieval score is less than or equal to threshold
and rnn retrieval score is more than the threshold. In this group, the csm does not manage toﬁnd any close examples in the database, but theparaphrase identiﬁcation model did.
3 Case 3 (out of vocabulary - non paraphrase;
OOV-NP) when both the csm and rnn retrieval
scores are less than or equal to the threshold.
For this case, there is no match with the given
input for either method.

Objective Evaluation

CEF
OOV
OOV-NP

csm > thresholdOX
X

rnn > thresholdOX

表 2: Evaluation case.

We evaluate the system response objectively by calculating the system output response Routput similarity
with the actual expected output Rtest . We compare
the NN-based retrieval (rnn) to the baseline systemusing TF-IDF cosine similarity retrieval (csm). In order to do so we score the system by using the same
7 Note that it would be better to manually create a corpus of similar and non-similar utterances, but this is extremely
time consuming, so we take the more light-weight automatic
approach in this paper.

図 3: Objective evaluation results for each thresholdover TF-IDF based cosine similarity metrics (upper)
and NN-based similarity metrics (lower).

As can be seen in the Figure 3, we measured theobjective evaluation score at diﬀerent thresholds todetermine the threshold value. We obtain a threshold score 0.7 by observing the longest evaluation score
diﬀerence between rnn and csm. With this thresh-−5−

old, the amount of data in CEF, OOV, and OOV-NP
respectively are 587, 206, and 207.
The details of the objective evaluation results foreach of these groups is shown in Figure 4. The left
ﬁgure shows evaluation calculated by TF-IDF based
cosine similarity (cos-tf-idf ), the right ﬁgure shows
evaluation calculated by NN-based similarity (paraphrase). Furthermore, by using the best thresholdscore in Figure 4, we can see that the NN-based retrieval rnn approach performs better compared to thebaseline method in the OOV data. However, the results is dropped in the case OOV-NP data.

図 4: Objective evaluation results. The left ﬁgureshows evaluation over TF-IDF based cosine similarity, the right ﬁgure shows evaluation over NN-basedsimilarity.

5.3(OOV-NP), the rnn response may not be related tothe user utterance topic. In this situation, the user
tends to choose the baseline approach response over
the rnn response.

6

Conclusion

In this work, we employed distributed word representation and recursive autoencoders as an paraphrase identiﬁcation model. We investigated this model
to retrieve responses in a data-driven chat-oriented dialog system, and compared it with our previous workin TF-IDF based cosine similarity retrieval. The experiment shows that the NN based retrieval is able
to capture the correlation between user input and example database especially when the user input is notavailable in the example database (OOV case). Furthermore, objective evaluation shows that that the
NN-based retrieval approach performs slightly better
compared to the TF-IDF based cosine similarity retrieval approach when both methods ﬁnd a response,or when only the rnn method ﬁnds a response.

参考文献
[1]

[2]

Subjective Evaluation

[3]

[4]

[5]

[6]
[7]

[8]

[9]

[10]

図 5: Subjective evaluation results.
During the subjective evaluation, we asked 10 human annotators to give a naturalness score between 15 to the system response Routput given the input query
Qtest . A higher score indicates that the system is giving a natural and relevant system response to the user
input, otherwise lower scores indicate that the systemdoesn’t give a related or natural response. In thisevaluation, each person assesses 50 randomly selectedquery-response pairs that were evenly distribtued overall systems. The results of this evaluation are shownin Figure 5. We can see in the ﬁgure that the rnn
perform slightly better compared to the baseline approach for the CEF and OOV cases. However, whenboth of the systems can not ﬁnd any good response

−6−

[11]

[12]
[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]
[21]

[22]

S. Jung, C. Lee, and G.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.
C. Lee, S. Lee, S. Jung, K. Kim, D. Lee, and G.G. Lee, “Correlationbased query relaxation for example-based dialog modeling,” in Proc. of
ASRU, Merano, Italy, 2009, pp. 474–478.
K. Kim, C. Lee, D. Lee, J. Choi, S. Jung, and G. G. Lee, “Modelingconfirmations for example-based dialog management,” in Proc. of SLT,Berkeley, California, USA, 2010, pp. 324-329.
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.
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.
R. Wallace, Be Your Own Botmaster, A.L.I.C.E A.I. Foundation, 2003.
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.
F. Bessho, T. Harada, and Y. Kuniyoshi, “Dialog system using realrime crowdsourcing and Twitter large-scale corpus,” in Proc. of SIGDIAL,
Seoul, South Korea, 2012, pp. 227-231.
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.
N. Chambers and J. Allen, “Stochastic language generation in a dialogue system: Toward a domain independent generator.,” in Proc. of
SIGDIAL, Cambridge, Massachusetts, USA, 2004, pp. 9-18.
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.
R. E. Banchs, “Movie-dic: a movie dialogue corpus for research anddevelopment,” in Proc. of ACL (2), 2012, pp. 203-207.
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, Bali, Indonesia, 2013.
R. Collobert and J. Weston, “A unified architecture for natural language processing: Deep neural networks with multitask learning,” inProc. of ICML, New York, NY, USA, 2008, pp. 160-167.
R. Socher, B. Huval, C. D. Manning, and A. Y. Ng, “Semantic compositionality through recursive matrix-vector spaces,” in Proc. of EMNLP,
2012.
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.
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.
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.
G. Salton, A. Wong, and C. S. Yang, “A vector space model for automatic indexing,” Commun. ACM, vol. 18, no. 11, pp. 613-620, Nov.
1975.
J. Turian, L. Ratinov, and Y. Bengio, “Word representations: A simple
and general method for semi-supervised learning,” in Proc. of ACL, 2010.
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.
D. Klein and C. D. Manning, “Accurate unlexicalized parsing,” in Proc.
of ACL, Stroudsburg, PA, USA, 2003, pp. 423-430.