Abstract: There are several dialog frameworks which allow manual specification of intents and rule based dialog flow. The rule based framework provides good control to dialog designers at the expense of being more time consuming and laborious. The job of a dialog designer can be reduced if we could identify pairs of user intents and corresponding responses automatically from prior conversations between users and agents. In this paper we propose an approach to find these frequent user utterances (which serve as examples for intents) and corresponding agent responses. We propose a novel SimCluster algorithm that extends standard K-means algorithm to simultaneously cluster user utterances and agent utterances by taking their adjacency information into account. The method also aligns these clusters to provide pairs of intents and response groups. We compare our results with those produced by using simple Kmeans clustering on a real dataset and observe upto 10% absolute improvement in F1-scores. Through our experiments on synthetic dataset, we show that our algorithm gains more advantage over K-means algorithm when the data has large variance.

Introduction: There are several existing works that focus on modelling conversation using prior human to human conversational data BIBREF0 , BIBREF1 , BIBREF2 . BIBREF3 models the conversation from pairs of consecutive tweets. Deep learning based approaches have also been used to model the dialog in an end to end manner BIBREF4 , BIBREF5 . Memory networks have been used by Bordes et al Bor16 to model goal based dialog conversations. More recently, deep reinforcement learning models have been used for generating interactive and coherent dialogs BIBREF6 and negotiation dialogs BIBREF7 . Industry on the other hand has focused on building frameworks that allow manual specification of dialog models such as api.ai, Watson Conversational Services, and Microsoft Bot framework. These frameworks provide ways to specify intents, and a dialog flow. The user utterances are mapped to intents that are passed to a dialog flow manager. The dialog manager generates a response and updates the dialog state. See Figure FIGREF4 for an example of some intents and a dialog flow in a technical support domain. The dialog flow shows that when a user expresses an intent of # laptop_heat, then the system should respond with an utterance “Could you let me know the serial number of your machine ”. The designer needs to specify intents (for example # laptop_heat, # email_not_opening) and also provide corresponding system responses in the dialog flow. This way of specifying a dialog model using intents and corresponding system responses manually is more popular in industry than a data driven approach as it makes dialog model easy to interpret and debug as well as provides a better control to a dialog designer. However, this is very time consuming and laborious and thus involves huge costs. One approach to reduce the task of a dialog designer is to provide her with frequent user intents and possible corresponding system responses in a given domain. This can be done by analysing prior human to human conversations in the domain. Figure FIGREF5 (a) provides some example conversations in the technical support domain between users and agents. In order to identify frequent user intents, one can use existing clustering algorithms to group together all the utterances from the users. Here each cluster would correspond to a new intent and each utterance in the cluster would correspond to an example for the intent. Similarly the agents utterances can be clustered to identify system responses. However, we argue that rather than treating user utterances and agents responses in an isolated manner, there is merit in jointly clustering them. There is adjacency information of these utterances that can be utilized to identify better user intents and system responses. As an example, consider agent utterances A.2 in box A and A.2 in box C in Figure FIGREF5 (a). The utterances “Which operating system do you use?" and “What OS is installed in your machine" have no syntactic similarity and therefore may not be grouped together. However the fact that these utterances are adjacent to the similar user utterances “I am unable to start notes email client" and “Unable to start my email client" provides some evidence that the agent utterances might be similar. Similarly the user utterances “My system keeps getting rebooted" and “Machine is booting time and again" ( box B and D in Figure FIGREF5 (a))- that are syntactically not similar - could be grouped together since the adjacent agent utterances, “Is your machine heating up?" and “Is the machine heating?" are similar. Joint clustering of user utterances and agent utterances allow us to align the user utterance clusters with agent utterance clusters. Figure FIGREF5 (b) shows some examples of user utterance clusters and agent utterance clusters along with their alignments. Note that the user utterance clusters can be used by a dialog designer to specify intents, the agent utterance clusters can be used to create system responses and their alignment can be used to create part of the dialog flow. We propose two ways to take adjacency information into account. Firstly we propose a method called SimCluster for jointly or simultaneously clustering user utterances and agent utterances. SimCluster extends the K-means clustering method by incorporating additional penalty terms in the objective function that try to align the clusters together (described in Section SECREF3 ). The algorithm creates initial user utterance clusters as well as agent utterance clusters and then use bi-partite matching to get the best alignment across these clusters. Minimizing the objective function pushes the cluster centroids to move towards the centroids of the aligned clusters. The process implicitly ensures that the similarity of adjacent agent utterances affect the grouping of user utterances and conversely similarity of adjacent user utterances affect the grouping of agent utterances. In our second approach we use the information about neighbouring utterances for creating the vector representation of an utterance. For this we train a sequence to sequence model BIBREF8 to create the vectors (described in Section SECREF5 ). Our experiments described in section SECREF5 show that we achieve upto 10% absolute improvement in F1 scores over standard K-means using SimCluster. Also we observe that clustering of customer utterances gains significantly by using the adjacency information of agent utterances whereas the gain in clustering quality of agent utterances is moderate. This is because the agent utterances typically follow similar syntactic constructs whereas customer utterances are more varied. Considering the agent utterances into account while clustering users utterances is thus helpful. The organization of the rest of the paper is as follows. In Section SECREF2 we describe the related work. In Section SECREF3 we describe our problem formulation for clustering and the associated algorithm. Finally in sections SECREF4 and SECREF5 we discuss our experiments on synthetic and real datasets respectively.

Question: How do they generate the synthetic dataset?
Answer: using generative process