Beyond Adjacency Pairs: Hierarchical Clustering of Long Sequences for Human-Machine Dialogues (2020)

Abstract: This work proposes a framework to predict sequences in dialogues, using turn based syntactic features and dialogue control functions. Syntactic features were extracted using dependency parsing, while dialogue control functions were manually labelled. These features were transformed using tf-idf and word embedding; feature selection was done using Principal Component Analysis (PCA). We ran experiments on six combinations of features to predict sequences with Hierarchical Agglomerative Clustering. An analysis of the clustering results indicate that using word embeddings and syntactic features, significantly improved the results.

## introduction dialogues between humans is not a solitary activity of words, rather the involved participants have certain desires/goals that they want to achieve. in order to do that, they co-create understanding, by aligning aspects of their believes/knowledge to achieve their goals and reach a consensus using dialogue control functions. dialogues between humans and machines can be facilitated by dialogue management systems (dms). a basic dms operates by coordinating natural language understanding (nlu), natural language generation (nlg) and a dialogue manager (dm). a dm employs either learned or hand-crafted strategies to the output from the nlu and sends its decisions to nlg that carries forward the interaction with the human participant. a dm's flexibility can be partially attributed to the incoming knowledge from the nlu. by dm's flexibility we mean to have functions for anaphora resolution, co-referencing, keeping track of topic shifts and being able to return to previous topics @xcite . the motivation behind this work is to explore sequences @xcite in dialogues that can improve the nlu's knowledge. a well explored dialogue sequencing method @xcite with-in conversation analysis (ca) are studied as adjacency pairs @xcite such as (question-answer, request-accept, greeting-greeting etc.), where the first one in the pair is called first pair part (f p p base ) and the second one is called second pair part (sp p base ). for exploring long sequences, ca provides a relevant framework of sequence expansion @xcite allowing the prior mentioned base parts to be expanded with preceding parts (f p p pre , sp p pre ), insertion parts (f p p insert , sp p insert ) or succeeding parts by (f p p post , sp p post ). this work proposes to use sequence expansion to analyse how much long sequences can be predicted by the machine learning models in order to build the knowledge for nlu. as an initial step, this work uses above mentioned sequence expansion labels to study the dendrograms and sequences of nodes longer than adjacency pairs. the paper is structured as follows: section 2 presents a summary of related literature and provides the necessary background. the methodology and the clustering model is presented in section 3, and section 4 presents the results of our proposed model. section 5 concludes this article. ## literature and background structuring in dialogues have been explored by many researches utilising different sequencing theories: discourse representation theory @xcite , conversation analysis (ca) @xcite , and rhetorical sequence theory @xcite to name a few. detailing these theories is beyond the scope of this work, but we will briefly explain some of their use-cases. for instance, @xcite used rhetorical sequence theory for sequencing task-driven dialogues and report several issues such as, deciding a minimal unit for annotation, overlap between subjectmatter and presentational relations. in @xcite , the authors presented a novel theory called segmented discourse interpretation theory (sdrt), combining the knowledge from dynamic semantics, common sense reasoning, and speech act theory. the authors claimed sdrt to be the most formally mature and linguistically grounded theory. while, the above mentioned works focused more on strengthening the theoretical foundations for dialogue sequencing, the authors @xcite identified themselves with solving practical matters of extracting sequences. their corpus of humanhuman tutorial dialogues were manually annotated with dialogue acts and trained on a hidden markov model (hmm) on adjacency pairs. more recently, the authors in @xcite presented a multi-party corpus annotated with discourse sequence relations following sdrt mentioned earlier. authors in @xcite proposed a hierarchical annotation scheme for query systems such as travel booking, in order to determine intents from complex nested queries compared to a single intent for each slot. in @xcite , the authors used a variational recurrent neural network (vrnn) and variational inference for dialogue sequence in taskoriented dialogues (finding restaurant and getting weather report). the proposed work here is closely in line with @xcite @xcite , where in prior work the authors proposed a two step methodology of extracting two dimensional patterns in dialogues, followed by clustering. their dialogues are manually annotated with emotion, gaze and dialogue act. in the latter work, the authors demonstrated the significance of dialogue sequencing for building domain agnostic dialogue models using ca. they explored sequence expansion and developed an annotation tool to annotate dialogues with subsequences based on ca and dialogue control functions. in the final work the authors used syntactic, communicative and ca based features and formalised them by extending the cooperating distributed grammar system. the biggest difference of this work from the above mentioned prior works is in the definition of the task, i.e, the dialogue corpus. all the prior work has utilised either publicly available corpora based on query systems, while this work aimed to gather as diverse genres of task-driven query/reservation (booking laundry, ordering food), collaboration (cooking, taking medications, going to the flower shop) dialogues and chit-chat dialogues. the other difference is in the annotation approach and the training input, where, we neither use only manually labelled or the entire utterance as the input. instead, we combine manually labelled and automatically extracted features. the next section briefly provides some background on adjacency pairs and ca based sequence expansion. ## methodology the method employed by this work to predict long sequences uses feature engineering and unsupervised clustering method on n-grams of syntactic features and dialogue control functions. the next sections provide details on the features used and the components of the model. overall, our framework consists of following stages represented in figure 1: 1. preparation of the corpus-consists of determining which genres should be considered, then merging of the samples from different sources was done, then the corpus was preprocessed by performing data cleaning, missing imputation, and assignment of uniqueidentifier. ## results to evaluate the hac model on different combination of features, we compute the silhouette coefficient, calinski harabasz index and davies bouldin score, these metrics illustrate if the model generated well defined clusters. in statistics cophnet, measures how well the dendro-gram preserves the pair wise distances of original data points @xcite . we use cophnet to measure the cor-relation between original and the predicted data points. the evaluation of the hac model is illustrated in the ## conclusion, discussion and future work this work explored combination of features (syntactic features and dialogue control functions) in order to find sequences in dialogues, such that we can build nlu functions for capturing information distributed over turns longer than two for dms to possibly conduct flexible dialogues. dependency parsing was used for extracting syntactic features (uni-grams and tri-grams) and dialogue control functions were labelled manually using iso 24617 -2 scheme. the feature transformation was done using tf-idf (when using only dialogue control function training the model), and glove embedding were used for combination of features (dialogue control functions and syntactic features), for both the cases feature selection was done with p ca. the selected features were modelled with hierarchical agglomerative clustering, the results validated our assumption that capturing longer sequences using syntactic features can provide knowledge that adjacency pairs would fall short in. this work being at a preliminary stage doesn't provide any concrete solution yet for building flexible dialogue strategies and rich knowledge sources, however it can be seen as more of a proof-ofconcept for using syntactic features and sequence expansion labels for dialogue sequencing. the benefit of using syntactic features is that they can be extracted automatically from the raw data and stateof-the-art methods are robust enough. this work explored tuples of syntactic features, instead trees or graphs must be explored. syntactic features provides flexibility to a machine, in the sense that it can select and prioritise to accomplish a topic (objects, nouns, etc) depending on the goals and/or the domain it is employed for. for pronoun resolution, relationship between prior mentioned proper noun/s and incoming pronouns can be established using extraction of uni-gram syntactic features delimited by se labels. for managing multiple dialogue control functions, coordinating conjunctions and interjections can be used for identifying response generation. this work also comes with its limitations, where the first is related to the corpus, which could be biased due to a large number of samples being synthetically prepared by the author. another limitation is the size of the corpus. the author is currently working on both of these limitations and in the future we have planned to combine different genres of dialogues from publicly available sources. another limitation of this work is that it doesn't use any dialogue features such as intents, semantics, context, etc. other limitations include selection and model of the syntactic features, where some of the features such as auxiliary verbs should be dropped because of their low frequency, it could be also a bias from the corpus that was used. a common assumption that dialogues are about subjects objects and verbs could not be held by this work. whether dialogues are task-driven or open ended or chit-chat-one commonality is that they all are directed towards activities fulfilling human needs (both tangible or intangible) more abstract models such as bdi models @xcite and/or activity theory @xcite should be considered and be complemented with syntactic and pragmatic features mentioned here.