Intent Mining from past conversations
for conversational agent

The following methods are used for extracting features from the Natural language description and conversation data .

1. 1.

   Pre-trained Sentence Embedding (USE) : We use pre-trained sentence embedding(Universal Sentence Encoder [Cer et al., 2018]) without any fine-tuning for the downstream tasks. Here, we pass each short description to the model⁴⁴4https://tfhub.dev/google/universal-sentence-encoder/4 and extract 1-d vector representation.

2. 2.

   Dialog Act Classifier : Dialog Act Classifier [Stolcke et al., 2000a] is crucial to Natural Language Understanding, as it provides a general representation of speaker’s intent, that is not bound to any particular dialog domain. The correct interpretation of the intent behind a speaker’s utterance plays an important role in determining the success of the conversation. For example, consider these two utterances - “Book a flight for me” and “Can you book a flight”. The generic intent of the first utterance is a “Command” type and where the latter is a “Question” type, and the domain dependent intent is same for both case, “book a flight”. Understanding different cues of the natural language helps to generate better response. For example, for the first utterance, the dialog system can generate more human-like response, “Sure. Please wait for few minutes as I will start the booking process”, whereas for the second case it can be more straight forward as “Alright. Let me start the booking process.”

   In the context of our work, we use ATIS Corpus [Hemphill et al., 1990]; the dataset contains textual conversations related to Air Travel Information System. Utterances in the conversations are tagged with dialog act types - “Information”, “Query”, “Command”, “Greetings”, “Confirmation-Affirmation”. Natural language-based features such as part-of-speech of the tokens, bi-grams of parts-of-speech are extracted from the utterances and a sequence-based classifier (CRF [Lafferty et al., 2001]) is trained. The CRF model is configured with the following parameters - a. training algorithm: lbfgs [Zhu et al., 1997] (Gradient descent using the L-BFGS method), L2 regularization: 0.001. We train a sequence classifier using python-crfsuite⁵⁵5https://python-crfsuite.readthedocs.io/en/latest/; to tag utterances in a dialog system with dialog act type.

DBSCAN is a density based clustering non-parametric algorithm, given a set of points, it groups points together that are closely packed (points with many nearby neighbors, high-density area) and marks points that lie alone in low-density regions (whose nearest neighbors are too far away) as outliers. The primary advantages of density-based clustering one that a) it can automatically find clusters based on the definition of density, b) it can find clusters of arbitrary shape rather than being limited to “ball-shaped” ones. We propose a variation of this algorithm in our work and the primary motivation is driven by the following two research questions -

Research Question 1 : How to group a set of data points without defining a hard bound on the number of cluster?

Research Question 2: How to automatically search for clusters with different densities in a sparse data space?

DBSCAN is a popular density-based clustering algorithm that searches for clusters broadly with two parameters - a) Maximum distance and, b) Minimum number of points. In DBSCAN literature, a point is a core point if there exists a threshold number of points within a maximum distance including the core point. All the other points are classified as Noise.

Let, X be a set of points $\{x_{\mathrm{1}},x_{\mathrm{2}},..,x_{\mathrm{i}}\}$ to be clustered and the distance between any two points is defined by D(,).

Let S(X) be a subset of X. And, l = D(p, 0) = D(0, p) such that, l is the distance between point p and origin.
Let, $\mathpzc{N(\mathord{\cdot})}$ be the cardinality of a set. Let, ${x_{\mathrm{i}},x_{\mathrm{j}}}$ be any two points from the set S(X). such that,

Where, d is the maximum distance and K is the minimum number of points, according to the definition of DBSCAN.

We formulate that, there also exists a subset P(X) and let ${x_{\mathrm{i}},x_{\mathrm{j}}}$ be any two points in it. Then,

where, $K>K^{\mathrm{{}^{\prime}}}$. Equations 3 and 4 essentially tell that less frequent classes in the dataset can be found by increasing the distance value constraint and propose a minimum number points constraint for cluster discovery to tackle unbalanced data distribution.

We modify the DBSCAN algorithm, naming it ITER-DBSCAN, to work with datasets having imbalanced class distribution (Refer to Algorithm 1). The algorithm runs iteratively to search for clusters with high-density regions to low-density regions. The low-density region search is controlled by two parameters “max-distance”and “min-points”. “max-distance” parameters controls what is maximum distance to consider two items belongs to same group and “min-points” controls what is minimum number of items in a group to qualify it as a cluster. We use cosine-distance for calculating distance between points.

Parameters: ITER-DBSCAN parameters are descried below,

• •

  data-points: The primary input to the algorithm is a set of data-points (textual data) for clustering.

• •

  featuretransformer: Transformer function to convert the textual data into feature representation⁶⁶6In this work the feature representation is referred as numerical feature..

• •

  initial-min-distance: Initial distance value for creating cluster.

• •

  initial-number-of-points: Initial number of points in a group for cluster validation.

• •

  delta-min-distance: Single distance value is not enough to cluster sparse dataset, at each iteration the distance value is increased by delta-min-distance parameter to search for new cluster.

• •

  delta-number-of-points: Minimum number of points parameter is decreased by delta-number-of-points parameter at each iteration for finding low density cluster.

• •

  min-points: Iteration is terminated when the minimum number of points for cluster creation reaches min-points.

• •

  max-iteration: max-iteration is the maximum number of times algorithm runs and updates delta-min-distance and delta-number-of-points for cluster discovery.

Our clustering approach provides a set of labeled conversation-intent pair and a set of unlabeled conversations, as the density-based clustering might not group all the data points. A statistical classifier such as Logistic Regression⁷⁷7Other statistical classifier or neural network-based model might provide better accuracy, but this part is out of the scope of our current research learns a mapping function between labelled conversations and intents. The trained classifier propagates the intent to the unlabelled conversations to generate a final intent classification training dataset.

In industrial service desk scenario, the metadata or description about the conversation is added later by the service agent after the issue is resolved and may not available in many cases. In this section, we describe two methods to extract textual descriptions from the raw conversation logs which can then be fed into our clustering model -

• •

  The agent answering to the service call always clarifies the intent with the user. Therefore, we can extract all the question asked by the Agent during the conversation with Dialog Act Classifier model (an SVM classifier created using trained Fasttext word embeddings as feature) and apply our clustering and label propagation approach to find different set of questions asked by the agent. We mark a special type of questions asked by the agent is “intent_clarfication” to clarify the intent. For example - “As I understand you need recording service to be enabled for Skype for Business” (Refer to Table 1) where Agent clarifies the request with the request with user. We can extract this sentence for Short description of the conversation.

• •

  We can also extract top-3 user utterances of “Information” or “Question” type using Dialog Act Classifier model. This utterance set can be also used for representing a short description about the conversation. This design choice is made from the observation that a user informs about her queries in the top few messages and DAC model filters some of the unrelated utterances (such as greetings and command type) leaving behind the ones that can be used in our purpose. COMMAND type utterance removal is a special case, since in our conversation dataset users request rather than command agents for help. But in other scenario, we might need to add COMMAND type utterances for representing short description of the conversation.

The Airlines Twitter Conversation dataset [Perkins and Yang, 2019] is a human-human conversation dataset⁸⁸8https://github.com/asappresearch/dialog-intent-induction related to user queries posted on various topics on Twitter about airline-related travel. We extract a short description from these conversations, discussed in section 3.4.

The Finance dataset [Casanueva et al., 2020] contains various online banking queries annotated with their corresponding intents⁹⁹9https://github.com/PolyAI-LDN/task-specific-datasets publised by PolyAI team. The AskUbuntuCorpus, ChatbotCorpus and WebApplicationCorpus, this three corpora [Braun et al., 2017] collected from StackExchange and Telegram Chatbot contains utterances with intent labels¹⁰¹⁰10https://github.com/sebischair/NLU-Evaluation-Corpora. The ATIS dataset¹¹¹¹11https://www.kaggle.com/hassanamin/atis-airlinetravelinformationsystem, which provides large number of messages and their associated intents, is useful for intent discovery/ classification problems including chatbots. Personal Assistant is another large scale dataset [Xingkun Liu and Rieser, 2019] consisting of messages posted by a personal assistant. The dataset¹²¹²12https://github.com/xliuhw/NLU-Evaluation-Data contains 25K+ messages with 64 intent label. Stackoverflow Dataset¹³¹³13https://github.com/jacoxu/StackOverflow is a short text dataset used for classification and clustering of extracted queries from StackOverflow website.

We use standard clustering metrics to evaluate the algorithms. We adapt metrics such as precision, recall, F1 score, and unsupervised clustering accuracy from the work of Perkins [Perkins and Yang, 2019] to compare our results for the conversation datasets. To evaluate the short text datasets, we primarily use two metrics: a) Normalized Mutual Information [Vinh et al., 2009], b) Adjusted Rand Index [Hubert and Arabie, 1985].

Normalized Mutual Information(NMI): NMI is designed as a combined measure for the accuracy of clustering and the total number of clusters. NMI is an entropy based metric that computes the amount of common information between two partitions -

where, Y is class labels, C is cluster labels, H(.) is Entropy and I(Y;C) is Mutual information between Y and C.

Adjusted Rand Index(ARI): ARI computes a similarity measure between two clusterings by considering all pairs of samples and counting pairs that are assigned in the same or different clusters in the predicted and true clusterings. ARI is an improved version of Rand Index, which is defined as follows:

The range of AMI and NMI is from 0 to 1, a larger value indicates a higher agreement between ground truth and the predicted partition for the dataset.

We evaluate DBSCAN, HDBSCAN and ITER-DBSCAN on a wide variety of parameters. We use the scikit-learn implementation of DBSCAN¹⁴¹⁴14https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html and HDBSCAN¹⁵¹⁵15https://github.com/scikit-learn-contrib/hdbscan. We generate a wide range based on the combination of the parameters described below. All the other parameters are kept at default according to the implementation. We use cosine distance function for evaluating the clustering algorithms. To evaluate the results better, we keep the minimum cluster size as 3 for all the density based clustering algorithm.

• •

  DBSCAN:  For evaluaton of DBSCAN, we select the minimum distance parameter between a range 0.09 to 0.40 with a change of 0.01 (Example: [0.09, 0.10, 0.11, .., 0.40]). We also configure the minimum sample parameter between a range 3 to 20 with a change of 1.
  

• •

  HDSCAN: We configure the minimum cluster size parameter between a range of 3 to 15 with a change of 1. We set the minimum samples parameter between a range 3 to 15 with a change of 1.
  

• •

  ITER-DBSCAN: We set a range of values for three parameters of ITER-DBSCAN for evaluation. We use five initial distance value 0.09, 0.12, 0.15, 0.20, 0.30. We set the maximum iteration and initial minimum sample parameters between a range 10 to 15 and 10 to 25 respectively, with a change step of 1. We keep the other parameters constant - such as, delta-min-distance as 0.01, delta-number-of-points as 1, minimum points as 3.

In Table 3, we present the evaluation of our algorithm on Twitter airline conversation dataset(TwACS) with DBSCAN and AV-KMeans. We use 4 evaluation metrics adapted from the work of Perkins [Perkins and Yang, 2019]. The HDBSCAN algorithm did not find any clusters for this dataset, hence not reported. We evaluate the dataset with the top-3 utterances extracted from conversation, with (and without) dialog act classifier based feature extraction. We report the effectiveness of feature extraction methodology in Table 3.

In Table 4, we present our algorithm ITER-DBSCAN results as a comparison to DBSCAN and HDBSCAN. For each dataset, we describe the total number of intents and the number of intents the algorithm identified. We also present the Normalized Mutual information score and Adjusted Rand Score for clustering evaluation. In most of the task, our algorithm achieves state-of-the-art results on the intent discovery and different clustering metrics.

In this section, we study the growth of number of clusters to identify different number of intents. We present the result of all datasets in figure 1. We plot the change of intent counts in x axis and the change of number of clusters in y axis. We also study the effect of parameter configurations for the Finance Dataset in figure 2, and how it changes the number of intents and clusters. In x-axis of the figure 2, we plot the difference between initial minimum distance and maximum iteration which can be regarded as the minimum possible cluster size. In y-axis of the figure 2, we plot the number of intents (left) and number of clusters (right). In figure 2, we lay the change of intent count with respect to different initial distance. The plot also shows that the number of clusters decreases as the difference between as minimum cluster size increases and initial distance between 0.12 to 0.20 provides better stability in discovering intents. So, in practice we can use this two parameters to balance between the number of clusters and the coverage of the intents.

Density based clustering algorithm uses local topological structure to create meaningful clusters. Time cost increases with data dimension and number of points [Gan and Tao, 2015]. To overcome this complexity, we partition large dataset into distinct subsets and apply our algorithm to this subsets in parallel. We use K-Means clustering for generating subsets of data when the dataset size is more than 10K. We use the following function (5) - to set the number of clusters for K-Means algorithm :

In figure 3, we plot the time taken by density-based clustering algorithms to process the datasets of section 4. Due to parallelization, the time complexity of our algorithm becomes almost linear with dataset size (after reaching volume of 10K).