INTERSPEECH 2011

Unsupervised Clustering of Utterances using Non-parametric Bayesian
Methods
Ryuichiro Higashinaka1, Noriaki Kawamae2 , Kugatsu Sadamitsu1, Yasuhiro Minami3,
Toyomi Meguro3, Kohji Dohsaka3 , and Hirohito Inagaki1
1

NTT Cyber Space Laboratories, NTT Corporation
2
NTT Comware Corporation
3
NTT Communication Science Laboratories, NTT Corporation
Abstract

function of an utterance is influenced by the context of a dialogue. Finally, the CRP has been applied to the Dihana corpus[5], which is a collection of dialogues between a system and human users. Since utterances of automated systems can be rigid
because of the use of templates and rules, clustering can be easily performed for such data. We need to examine whether the
CRP can also be used for more complex data, such as humanhuman conversations, so as to clarify its applicability.

Unsupervised clustering of utterances can be useful for themodeling of dialogue acts for dialogue applications. Previously, the Chinese restaurant process (CRP), a non-parametric
Bayesian method, has been introduced and has shown promising results for the clustering of utterances in dialogue. This
paper newly introduces the infinite HMM, which is also a nonparametric Bayesian method, and verifies its effectiveness. Experimental results in two dialogue domains show that the infinite HMM, which takes into account the sequence of utterancesin its clustering process, significantly outperforms the CRP. Although the infinite HMM outperformed other methods, we also
found that clustering complex dialogue data, such as humanhuman conversations, is still hard when compared to humanmachine dialogues.
Index Terms:
Unsupervised clustering, Nonparametric
Bayesian methods, Chinese restaurant process, Infinite HMM

To address the above three problems, we introduce anothernon-parametric Bayesian method called the infinite HMM,
which can estimate the number of clusters while taking into account the sequence of utterances in its clustering process. We
compare the CRP with the infinite HMM to investigate whether
taking into account the sequence of utterances is effective. We
also compare the CRP and the infinite HMM with K-means provided with the correct number of clusters to clarify the effectiveness of non-parametric Bayesian methods. In addition, we
use human-human dialogue data we collected to investigate theapplicability of the CRP and the infinite HMM.

1. Introduction
Dialogue acts, which are meaning representations for utterances, play key roles in dialogue systems research [1]. Since
they serve as fundamental units for understanding user intentions, dialogue management, and language generation, theyneed to be carefully designed before any system deployment.
However, the appropriate modeling of dialogue acts is often
difficult because it requires an extensive effort by experts toachieve good coverage of user utterances.
One of the most difficult steps in dialogue act modeling is
to determine the number of dialogue acts. This paper proposes
applying unsupervised clustering methods to dialogue data inorder to find appropriate clusters of utterances and estimate thenumber of dialogue acts. There have been several attempts tocluster utterances using such methods as K-means [2] and Kohonen self-organizing maps (SOMs) [3]; however, they requirethat the number of clusters (or the size of lattices for SOMs)
be known in advance. Recently, a non-parametric Bayesian
method called the Chinese restaurant process (CRP) has beenutilized to infer the number of clusters in dialogue data and has
shown some promising signs [4]. This paper builds on theirfindings and aims to find solutions to some of the remaining
problems.
First, although the CRP has been shown to create better
clustering results as iterations increase [4], it has not been compared with other clustering methods, making it difficult to judge
the effectiveness of the CRP. Second, the CRP does not take
into account the sequence of utterances in the clustering process, which may not be appropriate when considering that the

Copyright © 2011 ISCA

2. Unsupervised Clustering Methods
We first describe K-means, which we regard as our baseline,
and then describe the two non-parametric Bayesian methods;
namely, the CRP and the infinite HMM. Both methods are related to the Dirichlet process [6], which is a non-parametric
Bayesian model [7]. Dirichlet process mixture (DPM) models[8] and hierarchical Dirichlet processes (HDPs) [9] are two realizations of the Dirichlet process for handling mixture models,
and the CRP and the infinite HMM are the implementations of
the DPM and the HDP, respectively. They both assume infinite
states in modeling data and have been applied to estimating thenumber of components in mixture models [10], the number ofstates in HMMs [9], and the number of dialogue acts in dialogue[4].
2.1. K-means
K-means is a standard method for clustering. Given a set of data
and the number of clusters (K), it clusters the data by iteratively
updating the centroids. Initially, K data are randomly chosen
as centroids, and each datum is clustered to its nearest centroidusing a distance function, such as the Euclidean distance. Then,centroids are updated to the mean of its cluster members. This
process is repeated until convergence. Although K-means is
widely used today for simplicity, its drawback is that K has tobe determined in advance.

2081

28- 31 August 2011, Florence, Italy

3. Experiment2.2. Chinese Restaurant Process
In the CRP, a datum is called a customer and a cluster a table.
The first customer becomes seated at the first table. Then, eachfollowing customer (ci ), sits at one of the currently occupied
tables (tj ) or creates a new table (tnew ; new is the index given
to a new table) with the probability
8>< n(tj ) · P(ci |tj ) (if j = new)
N +αP(tj |ci ) ∝α>:· P(ci |tj ) (if j = new),N +α

We performed an experiment to verify the effectiveness of the
non-parametric Bayesian methods. We first prepared dialogue
data, and converted the utterances into feature vectors. Then,
we applied the three clustering methods to the vectors. For
the evaluation, we compare the clustering results against thehuman-annotated dialogue acts.
3.1. Dialogue Data
We used dialogues in an animal discussion (AD) domain andattentive listening (AL) domain. All dialogues are in Japaneseand are text dialogues although we also plan to work on spoken
dialogue data.

where ‘n(tj )’ is a function that returns the number of customers
for tj , N the total number of customers already seated, α thehyper-parameter that determines how likely a new table is created, and P(ci |tj ) the probability that ci is generated from tj ;that is,Y
P(w|tj )count(ci ,w)P(ci |tj ) =3.1.1. Animal Discussion Domain
We collected chat-like dialogues using an automated dialoguesystem [11]. In this domain, the conversational participants(the system and a human user) talked about likes and dislikes
about animals via a text chat interface. The data consist of 1000
dialogues and all user/system utterances were annotated with
29 dialogue acts, which include those related to self-disclosure,question, response, and greetings. See [11] for the descriptionof the system and the definitions of the dialogue acts.

w∈W

P(w|tj ) = P

count(tj , w) + βw∈W count(tj , w) + |W | · β.

Here, W is a set of features, count(∗, w) a function that returns
the number of occurrences of a feature w for a customer or atable, and β the hyper-parameter. We use a uniform distribution
for P(ci |tnew ).
After all customers have been seated, Gibbs sampling is
performed; that is, we repeat picking up one of the customers
from its table and relocating the customer as if he/she were thelast customer to be seated. After performing a sufficient numberof samplings, we obtain the optimal number of tables together
with their customers, which become the clustering results.

3.1.2. Attentive Listening
We collected human-human listening-oriented dialogues [12].
In this AL domain, a listener attentively listens to the other inorder to satisfy the speaker’s desire to speak and to make himself/herself heard.
We collected such listening-oriented dialogues using a website where users taking the roles of listeners and speakers werematched up to have conversations. The conversations were done
through a text-chat interface. The use of facial expressions was
not allowed. The participants ended each conversation after
approximately ten minutes. We collected 1260 such listeningoriented dialogues and annotated them with 38 dialogue acts.
The dialogue acts include those for greetings, giving information, sympathy, self-disclosure, and so forth. See [12] for thecomplete list of dialogue acts.

2.3. Infinite HMM
In the infinite HMM, a customer ci becomes seated at an already occupied table tj or creates a new table (tj=new ) with theprobabilityP(tj |ci ) ∝ P(tci−1 , tj ) · P(tj , tci+1 ) · P(ci |tj ),where tc means the table of a customer c. Here, we assume thatthe customers are given a sequential order, and ci−1 and ci+1
denote the previous and next data of ci . P(tj , tk ) is a simple
transition probability:

3.2. Creating Feature Vectors
Since the computational cost of Gibbs sampling is rather high,we randomly sampled 50 dialogues from each domain for use inthis experiment. There are 2894 and 2470 utterances in the AD
and AL domains, respectively. Each utterance was converted
into a feature vector using the bag-of-words (BOW) representation. As a morphological analyzer, we used ChaSen 1 and used
word base forms as features. To avoid the influence of uncommon words, we did not use words that occurred less than ten
times in the entire data set in each domain.
We conceived two other feature sets: (a) CW-POS, inwhich content words (nouns, verbs, adjectives, and unknown
words) are abstracted to their part-of-speech (POS) tags before
making a BOW representation, and (b) POS, in which all words
are abstracted to their POS tags. The motivation behind (a) is toabstract proper nouns and numerical expressions and to put anemphasis on cue phrases, such as functional words (non-content
words), which are known to be strong classification indicatorsof dialogue acts [13]. We have (b) as an extreme case of abstrac-

transitions(tj , tk ) + γ,
transitions(tj , tl ) + K · γ + α
l=1P(tj , tk ) = PK

where α is the hyper-parameter that determines how likely a
new table is created, K is the number of occupied tables, andtransitions(tj , tk ) returns the number of transitions from tj to
tk . γ is a flooring value to avoid zero probability. The probability for creating a new table isP(tci−1 , tnew ) · P(tnew , tci+1 ) · P(ci |tnew ),α,
l=1 transitions(tci−1 , tl ) + αα= 1.
P(tnew , tci+1 ) =0+αHere, we use a uniform distribution for P(ci |tnew ).
Similarly to the CRP, Gibbs sampling is performed to obtain the optimal number of tables and the locations for the customers.
P(tci−1 , tnew ) = PK

1 http://chasen-legacy.sourceforge.jp/2082

Table 1: Evaluation results averaged over all 100 trials for the animal discussion domain. The asterisks, +, and † indicate statisticalsignificance (p<0.01) by a non-paired t-test over K-means, the CRP, and the infinite HMM, respectively.
K-meansPOS
CW-POS BOW POS
0.464
0.471
0.438 0.460
0.346+† 0.281
0.231 0.326†
27
27
27
27.96

Feature set
PurityF# Clusters

CRP
Infinite HMM
CW-POS BOW POS
CW-POS BOW
0.537∗
0.551∗ 0.655∗+ 0.674∗+ 0.645∗+
0.343∗
0.421∗ 0.215
0.384∗+ 0.476∗+
32.01
35.03 453.70 180.40
143.62

Table 2: Evaluation results averaged over all 100 trials for the attentive listening domain. See Table 1 for the notations in the table.
Feature set
PurityF# Clusters

POS
0.270+
0.134†
33

K-means
CW-POS BOW POS
0.278
0.249 0.253
0.140
0.138 0.136†
33
33
21.11

CRP
Infinite HMM
CW-POS BOW POS
CW-POS BOW
0.315∗
0.326∗ 0.315∗+ 0.348∗+ 0.344∗+
0.156∗
0.159∗ 0.119
0.164∗+ 0.171∗+
25.70
29.28 112.70 35.40
38.00
cluster, false positive is the number of times a pair with a different dialogue act tag are clustered in the same cluster, and false
negative is the number of times a pair with the same dialogue
act tag are clustered in different clusters.

tion. The dimensions of the feature vectors for BOW, CW-POS,and POS in the AD domain are 564, 193, and 57, respectively,
and those in the AL domain are 1673, 404, and 62, respectively.
3.3. Evaluation Procedure

3.5. Results

We applied K-means, the CRP, and the infinite HMM to ourfeature vectors using the three sets of features. We used Kmeans as our baseline. Here, we provided K-means with thecorrect number of dialogue acts so that it could be a competitive
baseline. The correct number of dialogue acts is the number of
dialogue acts that are present in the sampled data. We had 27
and 33 dialogue acts in the AD and AL domains, respectively.
We used the Euclidean distance.
Since the performance of K-means depends on the initial
randomly created clusters and the CRP and the infinite HMM
work probabilistically, we performed 100 trials for each clustering method and compared their averaged performance. For
the CRP and the infinite HMM, we used tentative values of 0.1
for α and 0.01 for β and γ. The number of iterations (sweeps)
was set to 100, which means that each customer is considered
100 times to be relocated.

Tables 1 and 2 show the clustering performance averaged over
100 trials. When we focus on the BOW feature set, we can confirm that the CRP performs better than K-means, but we alsofind that the infinite HMM performs significantly better thanthe CRP. When we look at the number of clusters, we see a similar number of clusters for K-means and the CRP, but a larger
number of clusters for the infinite HMM, which is not surprisingconsidering that the context is taken into account. The high performance of the infinite HMM suggests that similar utteranceson the surface level have been successfully clustered into different clusters depending on the context. The number of clusters
by the CRP is generally closer to the correct number, suggesting that humans design dialogue acts mostly irrespective of utterance sequences and that the number of dialogue acts can beredesigned to be more fine-grained by taking the context into account. Note that we have a very large number of clusters for theinfinite HMM with the POS feature set, probably because thelack of word information is complemented by the transitions.
When we focus on the other feature sets, we see that they
perform poorly compared to the BOW, suggesting that both content words and functional words are important in distinguishingdialogue acts. When we look at the differences in the domains,
we see that it is much harder to cluster human-human utterances (i.e., the AL domain) as we expected, although the infinite
HMM still performs reasonably better than other methods.
Table 3 shows the clustering results in the AL domain for
the infinite HMM using the BOW feature set. As the tableshows, each dialogue act is mostly clustered into single dominating clusters. This indicates that, by looking at these dominating clusters, we could obtain typical utterances of the same
dialogue act, leading to a rapid modeling of dialogue acts from
dialogue data.

3.4. Evaluation Metrics
We used the purity and the F measure (harmonic mean of precision and recall) as our evaluation metrics [14]. The purity
indicates how occupied each cluster is with the same dialogue
act, and the F measure indicates how accurately each pair ofdata are clustered:
Purity:1 X
max |ck ∩ dj |,jNKpurity(C, D) =k=1

where C = {c1 . . . cK } is the set of clusters, D = {d1 . . . dN }the set of dialogue act tags, and N the number of data.
F measure:precision =TPTP, recall =,TP + FPTP + FN

4. Summary and Future Work

2 · precision · recall,
precision + recall
where TP, FP, and FN indicate true positive, false positive, andfalse negative. Here, true positive is the number of times a pairof data with the same dialogue act tag are clustered in the same
F=

This paper introduced the infinite HMM, a non-parametric
Bayesian method, for the clustering of utterances in dialogue.
Experimental results showed that the infinite HMM significantly outperforms the previously proposed CRP in two dia-2083

Table 4: Averaged number of clusters over 100 trials for thecontact center simulation dialogues.

Table 3: Clustering results in the AL domain by the infinite
HMM using the BOW feature set. Shown here are the results forone of the 100 trials. There were 37 clusters made in this trial.
This table shows to which clusters the reference dialogue acts(DAs) were clustered. Cluster IDs and their counts are shown as<cluster ID>:<count>. Reference DAs that occurred less than
20 times and clusters IDs with less than two counts are omitted
for brevity. The largest counts in each row are shown in bold.
Reference DA
GREETING
SELF - DISC - FACTSELF - DISC - PREF
(positive)
SYMPATHY

INFORMATIONSELF - DISC - PREF
(negative)
QUESTION - FACTCONFIRMATIONSELF - DISC - EXP
THANKSSELF - DISC - PREF
(neutral)
ACKNOWLEDGMENTQUESTION - PREF
QUESTION INFORMATIONSELF - DISC - DESIRESELF - DISC - HABITREPEAT
ADMIRATIONNON - SYMPATHY
APPROVALSELF - DISC - PLAN
QUESTION - HABITPROPOSAL
PARAPHRASE

CRPInfinite HMM
Feature set POS CW-POS BOW POS CW-POS BOW# Clusters 27.46
30.00 31.18 911.03
61.96 78.70
dialogue acts for contact center simulation dialogues where an
operator and a user perform transactions [15]. Table 4 showsthe estimated number of clusters when we used 50 sampled dialogues (6550 utterances). The experimental condition was thesame as we described in Section 3. It can be seen that the appropriate number of dialogue acts for this domain can be around30 and can reach up to 80. We plan to use this insight in ourmodeling of dialogue acts in the development of our call summarization system [15]. In addition, we also need to optimize
the hyper-parameters α, β and γ for the CRP and the infinite
HMM for better clustering accuracy.

Clusters
1:8, 3:38, 7:147, 9:5, 10:4, 13:60,
15:4, 19:15, 21:8, 26:7, 27:6
1:7, 2:3, 3:3, 4:44, 5:3, 6:14, 9:50,
10:88, 11:5, 14:3, 15:4, 17:12, 18:6,
19:20, 20:7, 22:11, 23:5, 24:4, 26:3
2:14, 3:3, 4:7, 6:3, 9:18, 10:112,
11:12, 16:3, 17:20, 18:11, 19:5, 24:3,
26:23, 28:15
1:3, 2:23, 3:6, 4:10, 6:3, 9:11, 10:28,
12:3, 13:5, 16:6, 17:23, 18:5, 19:6,
25:3, 26:117, 28:3
1:4, 2:3, 3:4, 4:19, 6:15, 8:3, 9:21,
10:67, 11:3, 14:5, 15:5, 17:9, 18:11,
20:4, 24:3, 26:5, 28:4
3:3, 4:8, 6:4, 9:8, 10:68, 11:6, 16:4,
18:3, 19:4, 24:5, 26:4
6:24, 8:10, 9:12, 10:13, 11:3, 15:34,
18:5, 22:8, 24:7
4:3, 6:6, 8:7, 9:9, 10:20, 11:5, 15:5,
17:3, 18:11, 20:3, 24:9, 26:16
1:4, 4:25, 5:3, 6:7, 9:6, 10:16, 19:7,
24:3, 30:5
21:77
4:5, 6:5, 9:10, 10:30

5. References[1] A. Stolcke, N. Coccaro, R. Bates, P. Taylor, C. V. Ess-Dykema,
K. Ries, E. Shriberg, D. Jurafsky, R. Martin, and M. Meteer, “Dialogue act modeling for automatic tagging and recognition of conversational speech,” Computational Linguistics, vol. 26, no. 3, pp.
339–373, 2000.
[2] K. Ohtake, “Unsupervised approach for dialogue act classification,” in Proc. PACLIC-22, 2008, pp. 445–451.
[3] T. Andernach, M. Poel, and E. Salomons, “Finding classesof dialogue utterances with Kohonen networks,” in Proc. theECML/MLnet Workshop on Empirical Learning of Natural Language Processing Tasks, 1997, pp. 85–94.
[4] N. Crook, R. Granell, and S. Pulman, “Unsupervised classification of dialogue acts using a Dirichlet process mixture model,” inProc. SIGDIAL, 2009, pp. 341–348.
[5] D. Griol, L. F. Hurtado, E. Sanchis, and E. Segarra, “Acquiringand evaluating a dialog corpus through a dialog simulation technique,” in Proc. SIGDIAL, 2007, pp. 39–42.
[6] T. S. Ferguson, “A Bayesian analysis of some nonparametric problems,” Annals of Statistics, vol. 1, pp. 209–230, 1973.
[7] J. K. Ghosh, Bayesian Nonparametrics. Springer, 2003.
[8] D. Aldous, “Exchangeability and related topics,” in Lecture Notes
in Math, vol. 1117, 1985, pp. 1–198.
[9] Y. Teh, M. Jordan, M. Beal, and D. Blei, “Sharing clusters among
related groups: Hierarchical Dirichlet processes,” in Proc. NIPS,
2004.
[10] C. E. Rasmussen and Z. Ghahramani, “Infinite mixtures of Gaussian process experts,” in Proc. NIPS, 2001, pp. 881–888.
[11] R. Higashinaka, K. Dohsaka, and H. Isozaki, “Effects of selfdisclosure and empathy in human-computer dialogue,” in Proc.
SLT, 2008, pp. 109–112.
[12] T. Meguro, R. Higashinaka, Y. Minami, and K. Dohsaka, “Controlling listening-oriented dialogue using partially observable
Markov decision processes,” in Proc. COLING, 2010, pp. 761–
769.
[13] N. Webb and M. Ferguson, “Automatic extraction of cue phrases
for cross-corpus dialogue act classification,” in Proc. COLING,
vol. Poster, 2010, pp. 1310–1317.
[14] C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Information Retrieval. Cambridge University Press, 2008, (Chapter16: Flat clustering).
[15] R. Higashinaka, Y. Minami, H. Nishikawa, K. Dohsaka, T. Meguro, S. Takahashi, and G. Kikui, “Learning to model domainspecific utterance sequences for extractive summarization of contact center dialogues,” in Proc. COLING, vol. Poster, 2010, pp.
400–408.

3:3, 13:6, 17:4, 26:38
6:10, 8:7, 9:3, 10:11, 16:3, 18:8, 19:4,
24:4
6:6, 8:4, 9:3, 10:12, 16:4, 18:8, 24:6
3:3, 5:3, 6:3, 9:6, 10:10, 19:9
4:8, 6:7, 9:5, 10:11, 20:3
3:4, 6:3, 9:5, 10:6, 26:7
3:5, 9:4, 10:4, 17:6, 26:7, 28:3
1:3, 4:5, 9:4, 10:7, 19:5
6:4, 9:4, 10:5, 17:6, 26:5
9:4, 10:3, 19:10
8:3, 18:4, 22:4, 24:3
10:4, 19:12
9:4, 10:4

logue domains. Regarding the problems mentioned in the introduction, we found that (1) the CRP works better than K-means
but the infinite HMM performs significantly better, (2) the sequence of utterances should be incorporated to achieve better
clustering performance, and (3) human-human dialogues aremuch harder to cluster compared to human-machine dialogues.
As future work, we need to investigate other features forbetter clustering performance, especially for human-human dialogues. In addition, we would like to adopt our findings in ourmodeling of dialogue acts for new domains. As a trial, we applied the CRP and the infinite HMM to estimate the number of2084