Quantized-Dialog Language Model for Goal-Oriented Conversational Systems
R. Chulaka Gunasekara David Nahamoo Lazaros C. Polymenakos Jatin Ganhotra Kshitij P. Fadnis


Band signatures for strong nonlinear Hall effect in bilayer WTe_2
    X. C. Xie
    December 30, 2023
=================================================================




We propose a novel methodology to address dialog learning in the context of goal-oriented conversational systems.
The key idea is to quantize the dialog space into clusters and create a language model across the clusters, thus allowing for an accurate choice of the next utterance in the conversation. 

This quantized-dialog language model methodology has been applied to the end-to-end goal-oriented track of 
the latest Dialog System Technology Challenges (DSTC6). The objective is to find the correct system utterance from a pool of candidates in order to complete a dialog between a user 
and an automated restaurant-reservation system.
Our results show that the technique proposed in this paper achieves high accuracy regarding selection of the correct candidate utterance, and outperforms other state-of-the-art approaches based on neural networks. 







Index Terms: language models, goal-oriented conversational systems, dialog learning, deep learning for dialog


§ INTRODUCTION

The Dialog State Tracking Challenge (DSTC; now rebranded as Dialog System Technology Challenges) initiative was 
originally conceived to provide a benchmark for the evaluation of  dialog-management , DSTC6 <http://workshop.colips.org/dstc6/>), is divided into three different tracks, and our work addresses the end-to-end goal-oriented dialog track. This track focuses on a restaurant-reservation problem: the objective is to book a table in a restaurant satisfying a number of requirements given by the user.

It is interesting to note that, as suggested in <cit.>, methodologies based on rules may solve the goal-oriented dialog problem proposed in DSTC6 with full accuracy (i.e., no errors at all). By contrast, data-driven conversational systems (see, e.g., <cit.>), are typically easier to apply to new domains and often perform in a satisfactory manner, but usually are less accurate than rule-based methods. 

In the implicit approach of developing dialog systems, the models are learned from the available interaction data, without using the traditional feature engineering and conversational components such as natural language understanding (NLU), dialog management, semantic matching etc. These models have the capability to continuously learn from the data and improve even after deployment, without cost and time consuming redesign of the features of individual components. Recent approaches of implicit dialog systems rely on applying deep learning techniques (e.g. sequence-to-sequence architectures) on the dialog data for prediction or generation of the next utterance in a dialog <cit.>. But, the accuracies of these models on a variety of dialog datasets have been low <cit.>. 

During prediction, the current approaches select the next utterance from all possible responses that can be given at any turn, along with all their possible syntactic variations. This explodes the space of possible choices and leads to poor performance. To alleviate this problem, we propose the quantized representation of dialogs, which reduces the state space for prediction and improves the performance of data-driven conversational systems.

The paper is structured as follows. In the next section, we briefly describe the problem and dataset considered. Then, in Section <ref> we introduce the quantized-dialog language model and, based on it, we develop a next utterance selection method for our goal-oriented dialog. In Section <ref>, we present results comparing the new approach with two reference schemes that rely on neural networks. Finally, we conclude our work with a few observations and indicate directions of future work.



§ PROBLEM STATEMENT AND DATASET



The main problem in the goal-oriented dialog-learning track in DSTC6 is further divided into four major subtasks: i) Issuing API calls, ii) Updating API calls, iii) Displaying options and iv) Providing extra information. The first two subtasks address dialog interaction for the collection of user requirements for restaurant reservation: atmosphere, location, cuisine, number of people in the party, and price range. Once these five requirements have been fulfilled, an API call is issued in order to retrieve (at least three) restaurants from a knowledge database that satisfy the requirements. Subtask three is about presenting the user with possible restaurant choices and subtask four is about providing additional information related to the restaurant option the user selected (i.e., restaurant address and phone number). There is a fifth subtask that combines the four subtasks mentioned and aims at modeling a complete dialog system for restaurant reservation.

The training data released in the challenge consists of 10,000 dialogs per subtask (including the fifth task). The automated dialog system evaluated as part of the challenge has to select the correct next utterance in each dialog subtask out of a number of possible candidates. Test data consists of four test sets, each with 5,000 dialogs split equally (1000 dialogs) over the five tasks.
These four sets will be referred to in this paper as tst1, tst2, tst3 and tst4.
The first test set is based on the same type of dialogs that occur in the training data.
The second set incorporates out-of-vocabulary entities (e.g., new cuisine types) and restaurants extracted from a knowledge database that is different from the one used in the training data.
The third test set includes six entity types in the user requirements (the additional entity type is related to dietary restrictions) whereas there are only five in the training data.
Out-of-vocabulary entities corresponding to the six types as well as the restaurants from the new knowledge database are combined in the fourth set.


§ A QUANTIZED LANGUAGE MODEL FOR GOAL-ORIENTED DIALOG LEARNING


In this section we discuss our main contribution, which is the quantized-dialog language model (QDLM). In Figure <ref> we show the model components for training and prediction (runtime), that we discuss in the sequel.






 §.§ Utterance preprocessing

Natural language utterances usually contain information that may be unnecessary in a decision-making process. 
To remove irrelevant information, we preprocess the utterances via delexicalization of entities (or more generally parameters) relevant 
to the dialog goal. 



User utterances that contain entity values found in the knowledge base are transformed into a corresponding vector of entity
types. During this transformation, the entity types that were identified in previous utterances are also preserved.

The order of the entity types in the vector is: cuisinetype, location, numpeople, pricerange and atmosphere.







An example of preprocessed dialog is shown in Table <ref>. 
We also detect dubious statements regarding entity/parameter selection by the user 
(see, e.g., utterance 11 in that table; more details will be discussed later in Section <ref>).
Constructing the language model with this delexicalized representation helps the quantized language model 
learn the dialog policy more accurately. 




























In Task 3 and 4, the set of restaurants recommended (obtained by means of the API call) is also preprocessed to 
identify the order in which the restaurants should be presented to the user. 
Consistent with our delexicalization approach, the name of the restaurant which should be proposed in the i^th place is modified 
to , and each of its properties (e.g., location, price, rating, etc.)
are accordingly changed to . 




 §.§ Utterance quantization and language model


Once the preprocessing is completed, the utterances are embedded into a vector space representation using the Bag-of-Words encoding <cit.> scheme. 
More complex procedures such as the Skip-Thought algorithm (see, e.g., <cit.>) can also be considered 
for this process. 
Next, the utterances are clustered in the embedding space to create a quantized representation. 

In this implementation, each different vector was identified with a different cluster. Once the clusters are identified, each utterance can be represented by the identifier associated with the cluster that particular utterance belongs to. This yields to a quantized representation of utterances. 
Once the utterances are quantized, a conversation can be represented as a sequence of clusters. 
For example, consider a dialog D, which comprises the sequence of utterances {u_1, u_2, ..., u_N}, 
where u_i is a natural language utterance.
Following the quantization, the dialog D can be represented as a set of numbers {c_1, c_2, ..., c_N}, 
where each c_i corresponds to the cluster identifier where u_i belongs. 

One of the simplest methods to assign probabilities to sequences of tokens is the 
n-gram language model <cit.>. 





The high-level idea is that the probability values for the candidate utterances are calculated using an n-gram language model constructed on the clusters.
In constructing the language model, we consider cluster transitions in all dialogs to calculate the transition probabilities between the clusters. 
This n-gram language model estimates the probability P(c_i | c_i-n, ... , c_i-1).









 §.§ Runtime and utterance prediction

The utterance prediction problem can be formalized as arg max_u   P(u | u_1, ... u_i-1), 
where u denotes the utterance that maximizes the conditional probability with respect to all previous utterances.
In the quantized dialog space, this problem is transformed into the cluster prediction 
problem arg max_c   P(c | c_1, ... c_i-1), where c is the cluster identifier that 
maximizes the conditional probability with respect to the clusters associated with all the previous utterances. 
Note that we can estimate this by the n-gram language model 

as follows: 
    arg max_c   P(c | c_1, ... c_i-1) ≈arg max_c   P(c | c_i-1, ... c_i-n).
 
As the utterances within a cluster are similar to one another, any utterance in the predicted cluster c 
can be selected as the predicted utterance u. In this implementation, previous 7 clusters were used to determine the probability distribution of the next cluster using the language model.  



During the evaluation of all the candidates for a response, the cluster to which each candidate belongs is identified, and then the language model is used to calculate
the probability associated with that cluster. Then we rank the candidate responses using this probability value together with the constructed dialog state (discussed in Section <ref>). 



 §.§ Dialog-state update

In the approach presented in this paper, the dialog state corresponds to a key-value store associated with each 
entity specified by the user and its respective value (e.g.,  and ). 

The dialog-state update is based on a keyword matching algorithm, assisted by a hierarchical sentence classifier. 
The keyword matcher compares each word mentioned in a user utterance against all the entities in the knowledge base. 
Figure <ref> illustrates the operation of the dialog-state update module, and the last column of Table <ref> refers to the corresponding dialog state maintained through the dialog.
The hierarchical classifier is implemented using a publicly available text classification service[https://www.ibm.com/watson/services/natural-language-classifier/.], and the operations of individual classifiers are explained below.




When an entity is detected in a user utterance, the first classifier (denoted as Classifier 1 in Figure <ref>) 
 confirms the selection of that entity as a user specification. 
For example, the entity associated with the  is not confirmed as part of a user request in 
      ; by contrast  is a confirmed requirement in the user utterance .

Utterances with detected but unconfirmed entities are labeled as dubious. When preparing training data for this classifier, we label as   the  user utterances with entities detected, followed
by the system utterance `whenever you’re ready', and we label as  the other user utterances with just the entities detected. 



If two or more entities of the same type are identified in the same utterance but only one indicates user requirements, 
the second classifier (denoted as Classifier 2 in Figure <ref>) allows selection of 
order to update the dialog state.
The training data for this classifier were prepared by, first, transforming utterances such as    
 
into the form  
, and then identifying the correct entity  (label) from the subsequent API call.




Once the language model predicts that the next utterance is an API call, the key-value pairs associated with the current 
dialog state are used to fill in the slots of the API call. 
The API call thus constructed is compared against the given candidates using (word-level) Levenshtein distance (see, e.g., <cit.>) in order to rank them.

It is important to note that, because QDLM has been trained on delexicalized data, out-of-vocabulary entities and 
restaurants from new knowledge databases can be handled without modifying the approach - with the caveat that the restaurants need to have the same information fields as in the database used for training.
We stress that the only modification we introduced in order to deal with additional parameters in the user requirements was 
to increase accordingly the number of key-value pairs in the dialog state (i.e., six pairs were considered 
in two of the test sets).
Therefore, when QDLM predicts that the next utterance should be an API call, the number of slots 
necessary for the call are directly given by the existing number of key-value pairs in the dialog state.









§ EXPERIMENTS AND RESULTS


In this section, we first present the two neural network approaches that were used for comparison with QDLM.
Then, we report and briefly analyze the results of the three techniques on the DSTC6 datasets.



 §.§ Baselines considered



For our first baseline, we choose a relatively simple architecture: a multi-layer feed-forward neural network (<cit.>)[For this baseline approach we would like to acknowledge David Echeverría Ciaurri who contributed to its design and implementation.].
This network is applied to each dialog and candidate answer to yield a confidence metric defined in the interval [0,1].
In all cases, a logistic function is considered after the output layer. 


The first two tasks in DSTC6 are addressed by means of a network with one hidden layer of size 100 with rectified 
linear unit as activation function.
The networks for Task 3 and 4 have three and two hidden layers, respectively, all of them of size 100 
(and also followed by rectified linear units). These networks were optimized, for each task individually, for accuracy and convergence rate by varying number of hidden layers, hidden layer sizes and activation layer functions.



The dialogs in Task 5 were first classified into four subtasks and then four networks of the same type as those were used to predict the next candidate utterance. 





Binary cross-entropy was minimized for each network by means of the Adam optimizer (see, e.g., <cit.>).
From all the dialogs in the dataset, 75% of them are used to train the networks.









The input to each network was designed to allow ready application of the approach to other domains than restaurant 
reservations

(e.g., hotel-booking engines).
In all five tasks, the input vector includes the last four dialog utterances, each mapped to a 50-dimensional vector.
In the first four tasks, the input incorporates the 50-dimensional vector encoding of the candidate utterance as well. 
Additionally, Task 1 and 2 input encodes entities in the dialog and candidate answer by means of two 20-dimensional vectors each corresponding to the 20 different entities in the training data. For Task 3, we use instead  a vector with five components (the encodings for up to five names of restaurants that can be recommended 
by the system) and one scalar (the encoding for the name of the restaurant, if any, in the 
candidate utterance). Similarly, for Task 4 we use a vector with three components (the encodings of the name 
of the restaurant selected by the user and the corresponding address and phone number).
The current implementation for the neural-network classifier described here only handles five different types 
of entities (thus, it is not applicable to requests based on six or more types of entities). An additional limitation is discussed in  <cit.>, where the feed-forward neural-network approach is shown to be unable to capture the functional dependency between a given output and past inputs in the network.












































Our second baseline is based on end-to-end memory networks, recently proposed in <cit.>. This approach has exhibited promising results on 
natural language processing tasks such as question answering (see, e.g., <cit.>).
Memory Networks <cit.> operate by writing and then iteratively reading from memory. They compute multiple internal states using hops and the memory values are learned by soft-attention of user query with the previous dialog utterances. The internal state, combined with the context is later used to predict the required response. The concept of multiple computation hops allows to attend over different parts of context (previous dialog utterances) during each hop and hence captures an improved internal state for the overall dialog. In this implementation, the previous utterances and the user query were passed to the network encoded in bag-of-words representation, and the network learns the representations for the vocabulary, using cross-entropy loss objective function for the predictions.

An advantage of using end-to-end memory networks for the DSTC6 challenge is that they provide a common architecture for 
all five tasks and require less 

`feature engineering’ than the feed-forward neural network based classifier and QDLM approaches discussed above.

In these experiments, we split the training data into two parts, 80% of it for training the network 
and the remaining 20% for testing the network trained.



 §.§ Discussion of results





Accuracy results for the training data (all five tasks) obtained with quantized-dialog language model (QDLM), feed-forward neural network (FFNN) and memory network (MN) are shown in Table <ref>. 
The last row in that table represents the average performance. We had to choose one method for submitting our results for the test data for the challenge. The decision for dropping our MN method was justified by the fact that the average accuracy for this method, i.e., 0.948, was clearly lower than the average accuracy of the other two techniques. Despite the fact that QDLM and FFNN show comparable performance for the training data, we observed that QDLM is better suited to handle additional parameters (as the ones present in the sets tst3 and tst4). Therefore, we only evaluated QDLM on the test data. 








The results obtained are summarized in Table <ref> for four test data tst1, tst2, tst3 and tst4, with an average accuracy of 0.981. The results for tst1 and tst2 are similar to what we obtained for the training set with accuracy values very close to one. We conclude that out-of-vocabulary entities and restaurants are handled successfully. QDLM shows lower accuracy in tst3 and tst4. While our technique can handle the API-call candidates with additional entity type, it does not properly deal with candidate utterances that query about the value of the additional entity type. We are working on a solution to this problem by further quantization of entity types.



 






§ CONCLUSIONS AND FUTURE WORK




In this paper, we have introduced the Quantized-Dialog Language Model (QDLM) technique for constructing goal-oriented conversational systems. The method has been applied to the end-to-end goal-oriented dialog learning track of the sixth edition of the Dialog System Technology Challenges (DSTC6). The dataset in this track is a large collection of restaurant-reservation conversations. The challenge is constructed for the design of systems that can accurately select the correct utterance from a pool of candidate utterances that appropriately completes a given dialog. 

The QDLM technique achieved around 98% candidate selection accuracy across 4 test sets each having 5000 conversations. Most of the errors were in test sets 3 and 4 where the candidate selection for dialogs with unseen entity types were not properly handled. Since the submission of the results for the challenge, we have made progress in this respect by further quantization in the candidate space for entity types to eliminate the dependency on multiple entity types. We have also started working on the integration of QDLM with sequence to sequence based natural language generation methods and we will report results in a future publication.






































IEEEtran



