Neural Sentence Embedding using Only In-domain Sentences for Out-of-domain Sentence Detection in Dialog Systems
Seonghan Ryu Seokhwan Kim Junhwi Choi Hwanjo Yu Gary Geunbae Lee









1]Seonghan Ryucor1
ryush@postech.ac.kr
[cor1]Corresponding author: 
  Tel.: +82-54-279-5567;  
  fax: +82-54-279-2299;
2]Seokhwan Kim 
kims@i2r.a-star.edu.sg
1]Junhwi Choi
chasunee@postech.ac.kr
1]Hwanjo Yu
hwanjoyu@postech.ac.kr
1]Gary Geunbae Lee
gblee@postech.ac.kr

[1]Pohang University of Science and Technology (POSTECH), 77 Cheongam-Ro, Nam-Gu, Pohang, 37673, Republic of Korea
[2]Institute for Infocomm Research (I2R), 1 Fusionopolis Way, # 21-01 Connexis (South Tower), 138632, Singapore

1 May 2013
10 May 2013
13 May 2013
15 May 2013




To ensure satisfactory user experience, dialog systems must be able to determine whether an input sentence is in-domain (ID) or out-of-domain (OOD).
We assume that only ID sentences are available as training data because collecting enough OOD sentences in an unbiased way is a laborious and time-consuming job.
This paper proposes a novel neural sentence embedding method that represents sentences in a low-dimensional continuous vector space that emphasizes aspects that distinguish ID cases from OOD cases.
We first used a large set of unlabeled text to pre-train word representations that are used to initialize neural sentence embedding.
Then we used domain-category analysis as an auxiliary task to train neural sentence embedding for OOD sentence detection.
After the sentence representations were learned, we used them to train an autoencoder aimed at OOD sentence detection.
We evaluated our method by experimentally comparing it to the state-of-the-art methods in an eight-domain dialog system; our proposed method achieved the highest accuracy in all tests.



41A0541A1065D0565D17
Natural language processingDialog systemsOut-of-domain sentence detectionNeural sentence embeddingArtificial neural networks Distributional semantics













§ INTRODUCTION



Dialog systems provide natural-language interfaces between humans and machines.
Because human conversation can range among topics, many studies have been recently conducted on multi-domain dialog systems <cit.>.
However, these systems are also restricted to a closed set of target domains and thus cannot provide appropriate responses to out-of-domain (OOD) requests.
For example, a dialog system that was designed to cover  and  domains could receive OOD requests such as “Would you recommend Italian restaurants for me?” that is in the  domain or “Please record Game of Thrones.” that is in the  domain.
To maintain user experience, the system must detect OOD requests and provide appropriate back-off responses such as rejection, rather than providing unrelated responses.

The main goal of this paper is to develop an accurate OOD sentence detection method.
We define OOD sentence detection as a binary classification problem of determining whether the system can respond appropriately to an input sentence, i.e.,

    f(x) =
        ID,    if x belongs to a domain d ∈ D,
    OOD,    otherwise,

where x is an input sentence, D is a closed set of target domain-categories such as  or , ID denotes in-domain, and OOD denotes out-of-domain.

Most previous studies <cit.> use both ID sentences and OOD sentences to train OOD sentence detection.
Collecting ID sentences is a necessary step in building many data-driven dialog systems.
However, the task of collecting enough OOD sentences to cover all other domains is laborious and time-consuming.
Therefore, the goal of this paper is to develop an accurate OOD sentence detection method that requires only ID sentences for training.

In this work, we present a novel neural sentence embedding method that represents sentences in a low-dimensional continuous vector space that emphasizes aspects that distinguish ID cases from OOD cases.
First, we use large set of unlabeled text to pre-train word representations for the initialization of neural sentence embedding.
Second, we use the similarity between OOD sentence detection and domain-category analysis <cit.> to train neural sentence embedding with only ID sentences.




=14.5pt
Domain-category analysis is a task that assigns one of a closed set of target domains to a given sentence; this analysis system can be trained using only ID sentences that are collected for each domain.
We think that the task of OOD sentence detection is more similar to domain-category analysis than to other tasks such sentiment analysis or speech-act analysis, so we expect that the features (i.e., representation) of a sentence extracted by a domain-category analysis system can be used for OOD sentence detection too.




Therefore we adopt a feature extractor that is trained for domain-category analysis, and use it as a neural sentence embedding system for OOD sentence detection.
Lastly, the learned representations of ID sentences are used to train an autoencoder that detects whether an input sentence is ID or OOD based on its reconstruction error.
To the best of our knowledge, this is the first study that applies neural sentence embedding to solve the sentence representation problem of OOD sentence detection.

The remainder of this paper is organized as follows:
In Section <ref>, we review previous studies.
In Section <ref>, we describe our method in detail.
In Section <ref>, we explain our experimental data, evaluation metrics, and methods to be compared.
In Section <ref>, we show and discuss the experimental results.
In Section <ref>, we conclude this paper.



§ RELATED WORK



Previous studies <cit.> on OOD sentence detection use sentence representations based on bag-of-words models, which have limitations in representing rare or unknown words; those words are likely to appear in OOD sentences.
Lane et al. <cit.> proposed an in-domain verification (IDV) method, which uses only ID sentences to build domain-wise one-vs.-rest classifiers that generate low confidence scores for OOD sentences, and then uses the scores as evidence that a sentence was OOD.
We implemented this method and compared it to our work.
Nakano et al. <cit.> proposed an two-stage domain selection framework, which uses both ID sentences and OOD sentences to build multi-domain dialog systems; the main contribution is to use discourse information to prevent erroneous domain switching, but whenever developers expand the domain of a dialog system they must reassess all OOD sentences because some will become ID due to the change of the boundary between ID and OOD.
Tur et al. <cit.> used syntactic feature and semantic feature for OOD sentence detection; web search queries are used as OOD sentences to eliminate the need to collect OOD sentences, but such queries are noisy because some are actually ID, and they cannot be obtained readily without using a commercial search engine.
Compared to these studies, the main contribution of this paper is a neural sentence embedding method that can understand rare words and unknown words.

Recently, neural sentence embedding methods have been assessed for their ability to solve the sentence representation problem.
Paragraph Vector <cit.> is a well-known method that uses a large set of unlabeled text to learn sentence representations, but the representations are  not optimized for a specific task because they are learned based on unsupervised objectives.
In contrast, some researchers have worked on supervised sentence embedding particularly for natural language understanding using recurrent neural networks (RNNs) <cit.> and long short-term memory (LSTM) networks <cit.>.
However, because we cannot define an objective function based on classification error between ID cases and OOD cases, these methods are not directly applicable to our problem in which only ID sentences are available as a training set.
To solve this problem, we exploit the similarity between OOD sentence detection and domain-category analysis (Section <ref>).

Another important part of OOD sentence detection is  classification that uses the training data about a target class to distinguish between target items and uninteresting items.
Nearest Neighbor Distances (NN-d) <cit.> classifies an input item as the target class when the local density[The local density of an item is the distance between the item and its closest item in the training data.] of the item is larger than the local density of its closest item.
A one-class support vector machine (OSVM) <cit.> learn a decision function about distinguishment.
In this work, we propose to use an autoencoder to detect OOD sentences, and compare the results to those obtained using other methods including NN-d and OSVM.



§ THE PROPOSED OOD-SENTENCE DETECTION METHOD





We defined OOD sentence detection f(x) as a binary classification problem (Section <ref>).
However, unlike most other binary classification problems, we assume that only ID sentences are available as training data.
With these ID sentences, domain-category analysis g(x)=d ∈ D can be built under another assumption that the domain category for each ID sentence is given.

When we represent sentences in m-dimensional continuous vector space, we take sentence embedding ε(x) ∈ℝ^m from an LSTM network trained with g(x) as the supervised objective.
Then, we build an autoencoder that consists of an encoder ϕ that takes sentences represented by ε(x) and maps them onto a different space, and a decoder ψ that reconstructs their original representations.
Finally, we use the learned autoencoder (ϕ, ψ) to detect OOD sentences of which reconstruction errors are greater a threshold θ as:


    f(x) =
        ID,    if ‖ψ(ϕ(ε(x)))-ε(x)‖^2 < θ,
    OOD,    otherwise.


The details of the proposed method (Fig. <ref>) are presented in the remainder of this section.



 §.§ Pre-training of word representations



Before training neural sentence embedding, words must be represented in a low-dimensional continuous vector space in which semantically-similar words are located near each other.
For example, `London' should be closer to `Paris' than to `apple' in the vector space.
The pre-trained word representations would be fine-tuned when sentence representations are learned using ID sentences (Section <ref>).
However, the amount of ID sentences is smaller than the amount of unlabeled text such as Wikipedia articles, so pre-training increases both the accuracy and coverage of the word representations.

We utilize the distributional hypothesis of words: the meanings of words can be found by their accompanying words <cit.>.
We first use a large set of unlabeled texts extracted from Korean Wikipedia articles as the training set, then use it to train a skipgram neural network <cit.> that predicts 10 surrounding words by using a v-dimensional hidden layer; we set v as 100.
When the training set consists of k unique words in its vocabulary, the result of pre-training is a matrix E∈ℝ^v × k in which the ith column is a v-dimensional vector that represents the ith word.



 §.§ Neural sentence embedding using an LSTM network





Sentence embedding ε aims to represent given sentences in an m-dimensional continuous vector space.
To process variable-length sentences, we use an LSTM network <cit.>, which uses a recurrent architecture that learns by repeatedly computing given operations for every word in each sentence.
We suppose that the features of domain-category analysis are also important in OOD sentence detection, so we use a set of ID sentences to train a network (Fig. <ref>) that classifies a given sentence into a domain category.
The values in the last hidden layer of the trained network represent the given sentence, so ε can be taken from the trained network.
This is a sort of transfer-learning approach <cit.> that learns knowledge from an auxiliary task (i.e., domain-category analysis) and applies the knowledge to a target task (i.e., OOD sentence detection).

The pre-trained word representations (Section <ref>) are fine-tuned based on back-propagation from the objective function of the LSTM network;
fine-tuning finds task-specific word representations, whereas pre-trained word representations describe general word meaning.
However, some words in OOD sentences appear rarely or never in ID sentences; this imbalance hinders the fine-tuning of the word representations, so the word representations cannot be fined-tuned accurately.
To prevent this problem, we use a two-channel approach: a non-static channel is fine-tuned during training, whereas a static channel is fixed.
This multi-channel idea has been used earlier for sentiment analysis <cit.> but not for OOD sentence detection.
In addition, we apply dropout <cit.> to the non-recurrent layers in our LSTM network.
Dropout is a regularization technique that randomly drops some nodes in artificial neural networks during training.
Especially, dropout prevents our LSTM network from becoming biased toward the non-static channel.

Based on our design, our LSTM network is defined as follows.
Let w^(t)∈ℕ^k be the one-hot vector representation of the tth word in a given sentence.
The dense vector representation v^(t)∈ℝ^2v of the tth word is defined as


    v^(t)=[E_sw^(t), E_nw^(t)],

where E_s ∈ℝ^v × k is the weight matrix for the static channel and E_n ∈ℝ^v × k is the weight matrix for the non-static channel;
both E_s and E_n are initialized to E that was pre-trained in Section <ref>, but only E_n is fine-tuned during the training; a dropout rate of 50% is applied to both E_sw^(t) and E_nw^(t).



In tth LSTM unit (Fig. <ref>), input gate i^(t), forget gate f^(t), memory cell state c^(t), output gate o^(t), and hidden state h^(t) are defined as

    i^(t)   =σ(W_i [h^(t-1), v^(t)] + b_i), 
    f^(t)   =σ(W_f [h^(t-1), v^(t)] + b_f), 
    C̃^(t)   =tanh(W_C [h^(t-1), v^(t)] + b_C), 
    c^(t)   =i^(t)⊗C̃^(t) + f^(t)⊗c^(t-1), 
    o^(t)   =σ(W_o [h^(t-1), v^(t)] + b_o), 
    h^(t)   =o^(t)⊗tanh(c^(t)),


where ⊗ denotes element-wise product, σ is the sigmoid activation function, W_i, W_f, W_C, and W_o are weight matrices, and b_i, b_f, b_C, and b_o are bias vectors.
We use bidirectional structure <cit.> of the LSTM network to prevent it from becoming biased toward the last few words, so those weights are defined independently for the forward LSTM and the backward LSTM.

The output domain-category layer y∈ℝ^|D| is computed
based on [h^(n), h^(n)], which is the concatenation of the last hidden layers of both the forward LSTM and the backward LSTM, so that

    y=softmax(W_y [h^(n), h^(n)] + b_y),

where W_y is a weight matrix and b_y is a bias vector; A dropout rate of 50% is applied to [h^(n), h^(n)].

The LSTM network is trained to minimize the categorical cross entropy between the gold standard domain category and the predicted output.
As a result, given a sentence, [h^(n), h^(n)] of the trained network represents the sentence in a vector space that emphasizes the distinguishing aspects among domain categories.



 §.§ One-class classification using an autoencoder





Autoencoders are feed-forward neural networks that encode and decode given inputs.
When an autoencoder is trained on interesting data, the reconstruction error is low for interesting input data but high for uninteresting input data.
Following the idea of one-class classification <cit.> based on this characteristic,
we use all ID sentences represented by ε in Section <ref> to train an autoencoder (Fig. <ref>) that aims to use reconstruction errors to detect OOD sentences.

The autoencoder is the pair of an encoder ϕ and a decoder ψ.
Let r∈ℝ^m be a given sentence representation.
Encoding layer c∈ℝ^m/2 and decoding layer r̂∈ℝ^m are defined as

    c   =tanh(W_ϕr + b_ϕ), 
    r̂   =tanh(W_ψc + b_ψ),

where W_ϕ and W_ψ are weight matrices and b_ϕ and b_ψ are bias vectors.
The autoencoder is trained to minimize the reconstruction error ‖r - r̂‖^2.



§ EXPERIMENTAL SETUP





 §.§ Implementation details



To implement the pre-training of word representations (Section <ref>), we use Gensim library <cit.>; we chose initial learning rate 0.05 and decreased it linearly.
To implement the LSTM network (Section <ref>) and the autoencoder (Section <ref>), we use Keras library <cit.>; we tried three optimization algorithms (adam <cit.>, adadelta <cit.>, rmsprop <cit.>) for the LSTM network and the autoencoder, and tried two hidden layer sizes (100 and 150) for the LSTM network.
In Section <ref>, we present the result only with the best optimization algorithm and the best hidden layer size, instead of enumerating all results.



 §.§ Data set



To demonstrate the effectiveness of our proposed method, we experimented on a data set of 7,975 Korean sentences.
The data set was collected manually using a Wizard-of-Oz approach by several groups of people from industries in Korea including LG Electronics and Mediazen.
The data set consists of 5,755 ID sentences for eight domains: , , , , , , , and ; and 2,200 OOD sentences for five domains: , , , , and .
Eighty percent of the ID sentences were used to train the models; the remaining ID sentences and all OOD sentences were used for testing.
Although we used Korean sentences to implement our method, it does not rely on language-specific processes except for word tokenization, and can therefore be applied to other languages.



 §.§ Evaluation metrics



We use equal error rate (EER) to represent the accuracy of OOD sentence detection <cit.>.
EER is the error rate at which false acceptance rate

    FAR   = Number of accepted OOD sentences/Number of OOD sentences


and false rejection rate


    FRR   = Number of rejected ID sentences/Number of ID sentences


are equal.







 §.§ Compared methods



We evaluated all possible combinations of sentence representation method and classification method.
First, we called our neural sentence embedding method (Section <ref>)  because it uses an LSTM trained for domain category (DC) analysis.
We compare DC-LSTM to eight sentence-representation methods.
 


  * BoW. Bag-of-words represents a sentence as a vector in which the ith element is the frequency of the ith keyword in the sentence. We use n-gram by increasing n from 1 to 3 to capture local word order; only the result with the best n is presented in Section <ref>.


  * TF-IDF. A sentence is represented as a vector in which the ith element is the product of the term frequency (TF) and the inverted document frequency (IDF) of the ith keyword in the sentence. We use n-gram as in BoW.


  * Neural BoW <cit.>. A sentence is represented as the element-wise average of its word representations obtained in Section <ref>.


  * PV-DBOW. This is the distributed BoW version of Paragraph Vector (Section <ref>). We use Doc2Vec implementation in Gensim library <cit.>, and set the dimension of sentence representation to 200.


  * PV-DM. This is the distributed memory version of Paragraph Vector (Section <ref>). The rest is the same as PV-DBOW


  * SA-RNN. A sentence is represented by the last hidden layer of the RNN trained for speech-act (SA) analysis instead of domain-category analysis.
To do this, we manually annotate speech acts on the same data set; our system includes five speech-act labels: , , , , and .

  * SA-LSTM. This is the LSTM network version of SA-RNN.

  * DC-RNN. This is the RNN version of DC-LSTM.

In the RNNs and the LSTM networks, we compare four variations of word embedding: random, static, non-static, and two-channel; the first one initializes word embedding randomly, and the others were described in Section <ref>.

Second, we compare the autoencoder to four classification methods.



  * NN-d (Section <ref>). We use the Jaccard distance of two sentences as the distance measure.


  * OSVM (Section <ref>). We use OneClassSVM implementation in scikit-learn library <cit.>, and apply three types of kernels to it: linear, polynomial, and radial basis function; only the result with the best kernel is presented in Section <ref>.


  * CBC. The combination of binary classifiers rejects input sentences that are rejected by all the domain-wise one-vs.-rest classifiers.
We use SVC implementation in scikit-learn library <cit.>, and apply kernels as in OSVM.


  * IDV (Section <ref>). In-domain verification (IDV) uses the  individual classifiers as CBC does. However, IDV uses their confidence scores as the feature of classification.





§ RESULTS AND DISCUSSION



Our proposed method, autoencoder + DC-LSTM w/ two-channel, was the most accurate (EER=7.02%) in the OOD sentence detection experiment (Table <ref>).
IDV + BoW (EER=13.69%) is a previous study <cit.> that used only ID sentences for training.
One-class deep neural network (OCDNN)[OCDNN uses a recursive neural network instead of a recurrent neural network.] for opinion-relation detection <cit.> can be applied also to OOD sentence detection, and their method corresponds to autoencoder + DC-RNN w/ non-static (EER=9.16%).
This result means that our proposed method decreased EER by 23.37% compared to the state-of-the-art method.

In the remainder of this section, we present five detailed observations from the experiment.

(1) The supervised embedding methods based on domain-category analysis were more accurate than the other sentence representation methods such as the supervised embedding methods based on speech-act analysis.
This superiority means for neural sentence embedding in OOD sentence detection, domain-category analysis is a more suitable auxiliary task than speech-act analysis.
In contrast, the unsupervised sentence embedding methods cannot optimize the sentence representations for OOD sentence detection, so those methods had higher error rates than even one-hot encoding methods.



(2) DC-LSTMs were more accurate than DC-RNNs.
To compare them in detail, we divided the test set into , , and  groups based on the length of each sentence (Fig. <ref>);
DC-LSTM w/ two-channel greatly reduced the error rate of DC-RNN w/ non-static in the  group (-7.08% points), although the difference was small in the  group (-1.43% points) and the  group (+1.33% points).
This result means that, in OOD sentence detection, LSTM networks reduce the vanishing-gradient problem of standard RNNs.



(3) DC-LSTM w/ two-channel was more accurate than DC-LSTM w/ random, w/ static, or w/ non-static.
Nevertheless, the best accuracy of domain-category analysis itself was achieved by LSTM w/ non-static rather than by LSTM w/ two-channel (Table <ref>); we think the reason is that the accuracy of domain-category analysis can be increased by fine-tuning the representations of only known words.
To summarize, the two-channel approach is effective in OOD sentence detection, but we cannot say that it is effective in general.





(4) The autoencoder was the best classification method for DC-LSTM w/ two-channel.
As expected, the reconstruction errors in the autoencoder were low for ID sentences but high for OOD sentences on average (Fig. <ref> and Fig. <ref>).
This result means that the reconstruction error by the autoencoder is reliable evidence that a sentence is OOD.



(5) The number of domains affected the result.
When we used subsets of the domains by varying the number of target domains from 2 to 7 to train and test OOD sentence detection, the average EER was proportional to the number of domains (red circles in Fig <ref>) although the EER decreased when the number of domains was increased from 7 to 8 (green cross in Fig <ref>).
However, the results were improved when all domains were used to train sentence embedding (blue squares in Fig <ref>).
Therefore, we can conclude that increasing the number of domains can decrease the accuracy of autoencoders but can increase the accuracy of sentence embedding.



§ CONCLUSION



To detect OOD sentences, we developed a method that is trained using only ID sentences.
We used an LSTM network trained for domain-category analysis as a neural sentence embedding system for OOD sentence detection because the features for domain-category analysis are also effective for OOD sentence detection; the word representations were pre-trained using a large set of unlabeled text before domain-category analysis was trained.
We used the learned sentence representations to train an autoencoder that detects OOD sentences based on their reconstruction errors.
In an experiment on a data set of an eight-domain dialog system, the proposed method achieved higher accuracy than the state-of-the-art methods.
This method will help to improve user experience in dialog systems by enabling them to detect OOD sentences accurately.



§ ACKNOWLEDGMENTS


This research was supported by the MSIP, Korea, under the G-ITRC support program (IITP-2016-R6812-16-0001) supervised by the IITP.
We thank the editor and two anonymous reviewers for their insightful comments.
We also thank Dr. Derek Jon Lactin for his careful proofreading.

model2-names


