1

Topic Models for Unsupervised Cluster Matching
Tomoharu Iwata, Tsutomu Hirao, and Naonori Ueda
Abstract—We propose topic models for unsupervised cluster matching, which is the task of finding matching between clusters in
different domains without correspondence information. For example, the proposed model finds correspondence between document
clusters in English and German without alignment information, such as dictionaries and parallel sentences/documents. The proposedmodel assumes that documents in all languages have a common latent topic structure, and there are potentially infinite number of topic
proportion vectors in a latent topic space that is shared by all languages. Each document is generated using one of the topic proportion
vectors and language-specific word distributions. By inferring a topic proportion vector used for each document, we can allocate
documents in different languages into common clusters, where each cluster is associated with a topic proportion vector. Documents
assigned into the same cluster are considered to be matched. We develop an efficient inference procedure for the proposed model
based on collapsed Gibbs sampling. The effectiveness of the proposed model is demonstrated with real data sets including multilingual
corpora of Wikipedia and product reviews.
Index Terms—topic modeling, unsupervised object matching, clustering

F

1

I NTRODUCTION

T

HERE has been great interest in topic models for analyzing discrete data such as text documents [1], [2].
Topic models are successfully used in a wide variety of applications including information retrieval [3], collaborative
filtering [4] and image analysis [5], [6].
In this paper, we propose a topic model for unsupervised
object matching for bag-of-words data. Object matchingis an important task for finding correspondence between
objects in different domains. Examples of object matching
include matching vocabulary in different languages [7],matching images and annotations [8], and matching user
identifications in different databases [9]. When similarity
measures between objects in different domains, or correspondence data for learning similarity measures, are given,
we can find matching using them by using record linkage
methods [10]. However, in some applications, similarity
measures and correspondence data might be unavailable
because of cost or privacy issues.
For this situation, a number of unsupervised object
matching methods have been proposed recently, such as
kernelized sorting [11] and matching canonical correlation analysis [12], which can find correspondence withoutalignment information. These methods find only one-to-one
matching. However, some applications require many-tomany, or cluster-to-cluster, matching. For example, multiple
English words with the same meaning (e.g. car, automobile,
motorcar) correspond to multiple German words (e.g. wagen, automobil). We also might need to find correspondence
between groups of people instead of individuals.
The proposed model is an unsupervised method forcluster matching, which is the task of finding matching between clusters in different domains, where correspondence
and cluster information are unavailable. For example, theproposed model finds correspondence between document
clusters in English and German without alignment informa-•

T. Iwata, T. Hirao, and N. Ueda are with NTT Communication Science
Laboratories, 2-4 Hikaridai, Sorakugun, Seikacho, Kyoto, Japan 619-0237.
E-mail: iwata.tomoharu,hirao.tsutomu,ueda.naonori@lab.ntt.co.jp

tion, such as dictionaries and parallel sentences/documents.
Here, parallel sentences/documents mean that its Germantranslation is attached to each sentence/document in English. A number of topic models for multilingual corpora
have been proposed [13], [14], [15], [16]. However, thesemodels require alignment information. To our knowledge,
the proposed model is the first topic model that can findshared topics across different languages without alignment
information. In real applications, we might not have alignment information. For example, there are no dictionaries
between minor languages, creating parallel corpora requires
high cost, and morphological similarities cannot be used for
languages that use different alphabets. Another example ismatching user clusters in different companies, where a user
is represented by a set of products the user purchased. Sinceuser and product identifications are different in different
companies, there are no alignment information.
With the proposed model, a latent topic space is sharedacross all languages by considering that documents in all
languages have a common latent topic structure. In thelatent topic space, there are potentially infinite number of
topic proportion vectors, and each document is generatedusing one of the topic proportion vectors and languagespecific word distributions. By inferring a topic proportion
vector used for each document, we can allocate documents
in different languages into common clusters, where eachcluster is associated with a topic proportion vector. Documents assigned into the same cluster are considered to bematched. Figure 1 shows the framework of the proposedmodel. We use Dirichlet processes, which enable us to determine the number of clusters in the inference, and we do notneed to fix the number of clusters in advance. We develop
an efficient inference procedure for the proposed model
based on collapsed Gibbs sampling, where sampling of a
topic proportion vector assignment for each document andsampling of a topic assignment for each word are alternately
iterated.
The remainder of this paper is organized as follows. In
Section 2, we review related work on unsupervised object

2

TABLE 1
Notation.

θ1

Symbol
M
K
Dm
Vm
Nmd
wmdn

latent topic space

θ2
θ3

zmdn

wE5 wE3
wE2

E
4

w

wE1
documents in language E

G
1

w

wG2

G
3

w

smd
θ`k
φmkv
π`

Description
number of languages
number of topics
number of documents in language m
vocabulary size of language mnumber of words in document d in language m
nth word of document d in language m,wmdn ∈ {1, · · · , Vm }topic for the nth word of document din language m, zmdn ∈ {1, · · · , K}
index of the topic proportion vector used for
document d in language m, smd ∈ {1, · · · , ∞}probability of topic k for the `th topic proportion vector
probability of the v th word in topic k with language mprobability of cluster `wG4documents in language G

Fig. 1. The framework of the proposed model with bilingual data. The
proposed model has a latent topic space shared by different languages.
Each document w is generated depending on a topic proportion vector
θ . Documents associated with the same topic proportion vector are
considered as matched.

matching and topic modeling. We formulate the proposedmodel for unsupervised cluster matching in Section 3, anddescribe its inference procedure based on a Bayesian framework in Section 4. In Section 5, we demonstrate the effectiveness of the proposed model with experiments using document data sets including multilingual corpora of Wikipedia
and product reviews. Finally, we present concluding remarks and a discussion of future work in Section 6.

in Section 5. Another advantage of the proposed modelover MMLVM is its efficiency for analyzing documents.
The computational complexity of MMLVM is linear to the
vocabulary size, which is usually very large. In contest, thecomplexity of the proposed model is linear to the number ofwords occurred in a document, which is much smaller than
the total vocabulary size. ReMatch [24] is an unsupervised
cluster matching method for network data, but not for bagof-words data, which is our focus. ReMatch finds cluster
matching using a probabilistic model, where connectivity
between clusters is shared among different domains, andbinary edges in networks are assumed to be generated froma Bernoulli distribution. On the other hand, the proposedmodel assumes words are generated from topic-specificmultinomial distributions, and therefore it is able to utilize
word frequency information in bag-of-words data.

2

R ELATED W ORK

2.2

2.1

Unsupervised Object Matching

A number of topic models for modeling documents in multiple languages have been proposed. For example, polylingual topic models [13] find shared topics from aligned
documents, and are used for cross lingual entity linking [25].
Probabilistic cross-lingual latent semantic analysis [14] andJoint latent Dirichlet allocation [15] discover shared latent
topics by incorporating a bilingual dictionary into topic
models. Unsupervised multilingual topic models (MuTo)
can analyze unaligned text documents by matching vocabulary terms between different languages based on topic
models [16]. MuTo finds correspondences of vocabularyterms between different languages using Hungarian algorithm by maximizing a posterior. When MuTo used priorknowledge such as dictionaries or morphological features,
it found matching of semantically similar words in different
languages, and discovered coherent topics across different
languages. However, when MuTo did not use the priorknowledge, it could not find matching in their experiments.

There have been proposed a number of methods for unsupervised object matching, which is also called cross-domain
object matching, such as kernelized sorting [11], and its
convex extension [17], least square object matching [18],matching canonical correlation analysis [12], and Bayesian
object matching [19], [20]. These methods find matching bysorting objects so as to maximize dependence, or minimize
independence. For example, kernelized sorting uses HilbertSchmidt Independence Criterion (HSIC) [21] as a measurement of independence, and sorts objects by minimizing
HSIC between objects in two domains using the Hungarianalgorithm [22]. There are three limitations in these methods.
First, they find only one-to-one matching. Second, the number of domains need to be two. Third, the number of objects
in each domain should be the same across all domains. On
the other hand, the proposed model does not have theselimitations; it finds cluster matching from data with morethan two domains, and each domain can contain different
numbers of objects.
Recently, [23] proposed an unsupervised many-to-many
matching method based on probabilistic latent variable
models (MMLVM). However, since it assumes Gaussian
noise, it is inappropriate for discrete data such as document collections as shown by [3] and our experiments

3

Topic Modeling

P ROPOSED M ODEL

Although we assume that the given data are text documentswith multiple languages in this paper, where each language
corresponds to a domain, the proposed model is applicable
to a wide range of discrete data, such as image data, where3each image is represented by visual words [26], and purchase log data, where each user is represented by a set ofitems the user purchased.
Suppose that we are given documents in M languages
Dm
W = (Wm )M
m=1 , where Wm = (wmd )d=1 is a set of text
md
documents in language m, and wmd = (wmdn )N
n=1 is a setof words in document d of language m. Our notation issummarized in Table 1. Note that correspondences between
documents in different languages and correspondences between vocabulary terms in different languages are notgiven. The number of documents Nm and the vocabulary
size Vm for each language can be different from those ofother languages. The task is to find matching clusters of
documents across multiple languages in an unsupervisedmanner.
The proposed model is assumed to have potentiallyinfinite number of topic proportion vectors θ1 , · · · , θ∞ ina latent topic space shared by all languages. Here, θ`
is a K -dimensional vector, θ`k represents the probabilityof generating topic k for the `th topic proportion vector,Pθ`k ≥ 0 and K
k=1 θ`k = 1. We use a stick-breaking process,which is a way of constructing Dirichlet processes [27]. Let
smd ∈ {1, · · · , ∞} be the latent index of a topic proportion
vector for document d in language m. It means that the document d is generated using topic proportion vector θsmd . A
topic proportion vector can be used by different documents
in different languages. The generative process is the samewith that of latent Dirichlet allocation (LDA) given the topic
proportions. For each of the Nmd words in the document,
a topic zmdn is chosen according to the topic proportions
θsmd . Then word wmdn is generated from a language- andtopic-specific multinomial distribution over words φmzmdn .
Here, φmk is a Vm -dimensional vector, φmkv represents theprobability of generating word v in topic k , φmkv ≥ 0, andPVm
v=1 φmkv = 1.
Polylingual topic model (PTM) is a topic model for analyzing documents in multiple languages, such as multilingual corpora [13]. With PTM, documents need to be aligned
across different languages. PTM assumes that aligned documents have the same topic proportion vector θ1d = · · · =θM d . Shared topics can be found with PTM by using acommon topic proportion vector for aligned documents.
However, alignment information is unavailable in our task,
and therefore PTM is not applicable. On the other hand, we
consider that topic proportion vector for each document islatent, which is indicated by smd , and thus the proposedmodel can handle unaligned documents.
In summary, the proposed model generates documents
in multiple languages W according to the following process,1)
2)

Draw cluster proportions π ∼ Stick(γ)
For each cluster: ` = 1, . . . , ∞a)3)Draw a topic proportion vectorθ` ∼ Dirichlet(α)

For each language: m = 1, . . . , Ma)For each topic: k = 1, . . . , Ki)b)Draw a word distribution
φmk ∼ Dirichlet(β)

For each document: d = 1, . . . , Dm

α

z

θ

w

ND

φ

K

β
M

(a) latent Dirichlet allocation

α

z

θ

w

ND

φ

K

β
M

(b) polylingual topic model

γ
α

s

π
θ

z

∞

w

ND

φ

K

β
M

(c) proposed modelFig. 2. Graphical model representation of latent Dirichlet allocation, thepolylingual topic model, and the proposed model.

i)ii)

Draw a cluster assignment
smd ∼ Discrete(π)
For each word: n = 1, . . . , Nmd
A)
B)

Draw a topic
zmdn ∼ Discrete(θsmd )Draw a word
wmdn ∼ Discrete(φmzmdn )Here, Stick(γ) is the stick-breaking process that generates
mixture weights for a Dirichlet process with concentration
parameter γ . π = (π1 , π2 , · · · ) is a cluster proportion vector,
where π` represents the probability of selecting cluster `, or
the probabilityof using the `th topic proportion vector, π` ≥P
0 and ∞`=1 π` = 1. Dirichlet(·) represents the Dirichlet
distribution, and α and β are Dirichlet parameters. Figure 2
shows graphical model representations of latent Dirichlet
allocation (LDA), the polylingual topic model (PTM), andthe proposed model, where shaded and unshaded nodes
indicate observed and latent variables, respectively. With
LDA, each document has a topic proportion vector θ , which
is not shared across different languages. With PTM, a topic
proportion vector θ is shared across corresponded documents in different languages by using correspondence information, and align topics over different languages. With theproposed model, a topic proportion vector θ is shared acrossdocuments assigned to the same cluster, which enables us toalign topics without correspondence information.
The joint likelihood of words W, latent topic assignmd Dm M
ments Z = (((zmdn )Nn=1 )d=1 )m=1 and latent clusters S =Dm M((smd )d=1 )m=1 is given byp(W, Z, S|α, β, γ) = p(S|γ)p(Z|S, α)p(W|Z, β).

(1)

4

By analytically integrating out cluster proportions π , thefirst factor is calculated byQ
γL L`=1 (D` − 1)!
p(S|γ) =,(2)γ(γ + 1) · · · (γ + D − 1)
where L is the number of clusters that contain more than adocument, D` is the number of documents assigned to clusPM
ter `, and D = m=1 Dm is the total number of documents.
Since we use conjugate Dirichlet priors for multinomialKM
parameters, Θ = (θ` )L`=1 and Φ = ((φmk )k=1 )m=1 , we canintegrate out Θ and Φ analytically in a similar way withlatent Dirichlet allocation [2]. Then, the second factor of (1)is given by
L Q
Γ(αK)L Y K
k=1 Γ(N`k + α)p(Z|S, α) =
,
(3)
KL
Γ(α)
Γ(N` + αK)`=1where N`k is the number of words assigned to topic k inPKdocuments of cluster `, N` = k=1 N`k and Γ(·) represents
the Gamma function. The third factor of (1) is given by
M
K Q m
Y
Γ(βVm )K Y Vv=1
Γ(Nmkv + β)p(W|Z, β) =
, (4)
Vm K
Γ(β)
Γ(N
mk + βVm )m=1
k=1
where Nmkv is the number of times word P
v has beenVmassigned to topic k in language m and Nmk = v=1
Nmkv .
See Appendix A for the derivation of (3) and (4).

4Algorithm 1 Inference procedures for the proposed model.
Input: multiple language data sets X , initial number ofclusters L, number of topics K , hyperparameters α, β, γ ,number of iterations T
Output: cluster assignments S , topic assignments Z
1: initialize S and Z
2: for t = 1, · · · , T do
3://sampling topic assignments
4:for m = 1, · · · , M do
5:
for d = 1, · · · , Dm do
6:for n = 1, · · · , Nmd do
7:sample zmdn using probability (5) from
{1, · · · , K}8:
end for9:
end for10:
end for11://sampling cluster assignments
12:
for m = 1, · · · , M do
13:
for d = 1, · · · , Dm do
14:sample smd using (6) from {1, · · · , L + 1}
15:
if smd = L + 1 then16:
update the number of clusters L ← L + 1
17:
end if18:
end for19:
end for
20: end for

I NFERENCE

Since cluster proportions π , topic proportion vectors Θ andword distributions Φ can be analytically integrated out,
latent variables that we need to infer are latent topic assignments Z and latent cluster assignments S. The inference of
Z and S given multilingual documents W can be efficiently
computed using collapsed Gibbs sampling [2]. Given thecurrent state of all but one variable zmdn , the assignment ofa latent topic to the nth word in document d of language mis sampled from the following probability:p(zmdn = k|W, Z\mdn , S, α, β, γ) Nmkwmdn \mdn + β,∝ Nsmd k\mdn + α ·Nmk\mdn + βVm(5)where \i represents the count or set when excluding example i. This probability is derived using (3) and (4). The
sampling probability for the latent cluster smd is as follows:p(smd = `|W, Z, S\md , α, β, γ)p(smd = `, S\md |γ) p(Z|smd = `, S\md , α)·.
∝p(S\md |γ)p(Z\md |S\md , α)Here, the first factor is given byp(smd = `, S\md |γ)
D`\md
∝
γ
p(S\md |γ)

if ` ≤ L
if ` = L + 1,

θ̂mdk =
(6)

Nsmd k + α,
Nsmd + αK(9)PKwhere Nsmd =k=1 Nsmd k is the number of words assigned to cluster smd , and(7)

using (2), and the second factor is given byp(Z|smd = `, S\md , α)p(Z\md |S\md , α)=using (3). See Appendix B for the derivation.
Algorithm 1 shows the procedures for inferring the proposed model based on the collapsed Gibbs sampling. Here,
T is the number of iterations. For the input, we give theinitial number of clusters L. In our experiments, we set theinitial number of clusters L = 1. The cluster assignments S
and topic assignments Z are initialized by randomly selecting an integer from {1, · · · , L} and {1, · · · , K}, respectively.
By iterating collapsed Gibbs sampling of latent topic assignments zmdn for all words m = 1, · · · , M , d = 1, · · · , Dm ,N = 1, · · · , Nmd with (5) and the sampling of latent clusters
smd for all documents m = 1, · · · , M , d = 1, · · · , Dm with
(6), we infer the latent variables of the proposed model. The
documents that are assigned into the same cluster are considered as matched. The point estimate of topic proportion
vectors and word distributions are obtained byKY
Γ(N`\md + αK)
Γ(N`k\md + Nmdk + α),Γ(N`\md + Nmd + αK) k=1
Γ(N`k\md + α)
(8)

φ̂mkv =

Nmkv + β,
Nmk + βVm

(10)respectively.
The computational complexity of an iteration of thecollapsed Gibbs sampling with the proposed model is linear
to the number of languages, the number of documents, thenumber of topics, the number of clusters, and the document
length, but it does not depend on the vocabulary size.

55

E XPERIMENTS

We evaluated the proposed model by using two bilingual
document sets. In the next section, we explain the data
used. In Subsections 5.2 and 5.2, we show the discovered
topics and quantitative results, respectively, when we fix
the hyperparameters and data sets. In Subsection 5.4, weanalyze the effect of hyperparameter and data settings.
5.1

Data

We used the following two data sets: Wikipedia and Review.
The Wikipedia data set consists of Wikipedia documents
written in English and German. For each language, we
sampled 150 documents that were categorized in ‘Nobel laureates in Physics’, ‘Nobel laureates in Chemistry’, ‘American basketball players’, ‘American composers’, and ‘English
footballers’. The Review data set consists of review documents in English and Japanese obtained from Amazon.com
and Amazon.co.jp. The reviews are written about products
categorized in ‘Watch’, ‘Book’, ‘Electronics’, ‘Kitchen’ and‘Music’. We sampled 1,000 documents for each category, and
5,000 documents in total. Stop-words were omitted for bothof the data sets, where stop word lists were downloaded
from https://code.google.com/archive/p/stop-words. We
used 1,000 and 3,000 most frequently occurring words asfeatures in Wikipedia and Review data sets, respectively.
5.2

Discovered Shared Topics

Table 2 shows some examples of extracted shared topics
with the proposed model from the Wikipedia data set. In
our experiments, we used the following hyperparameters:
α = 0.1, β = 1, γ = 1. The initial number of clusters was set
to one. The proposed model successfully found common
topics between English and German without alignment
information; Topic1 is about Nobel prize, Topic2 is aboutmusic, Topic 3 is about soccer, and Topic4 is about basketball. Two categories ‘Nobel laureates in Physics’ and ‘Nobel
laureates inn Chemistry’ were joined in the first topic. Thisis reasonable because the two categories are closely related.
Note that there are common or similar words in English andGerman, such as ‘manchester’, ‘nba’ and ‘jordan’, we do not
use any morphological information for the inference.
The proposed model also discovered shared topics fromthe Review data set as shown in Table 3; Topic1 is aboutmusic, Topic2 is about watch/camera, Topic3 is about books,
and Topic4 is about kitchen products. When matching morphologically similar languages such as English and German,
we can use string similarities between words. However,when we try to match morphilogically different languages
such as English and Japanese, we cannot use morphological features. Thus, it is important to develop methods for
unsupervised matching.
5.3

Quantitative Results

For the quantitative evaluation, we used precision, recalland F-measure as measurements. The precision is calculatedby the rate of correctly matched pairs among pairs that are
estimated as matched. Here, a matched pair means thatthe two documents are assigned into the same cluster or
category. The recall is calculated by the rate of correctly

matched pairs among truly matched pairs. The F-measureis the harmonic mean of precision and recall. For all of themeasurements, a higher value indicates a higher matching
performance.
We compared the proposed model with MMLVM,
Shared-LDA and Mix-KS. MMLVM is unsupervised manyto-many matching latent variable models [23]. Shared-LDA
is a latent Dirichlet allocation model that shares a Dirichletprior for topic proportions across different languages. The
hyper-parameters for the Dirichlet prior were estimatedby the fixed point iteration method. After the inference,
topic proportion vectors were clustered using the k -means
method. Mix-KS is a combination of mixture models andkernelized sorting. Mix-KS finds cluster matching by thefollowing procedure. First, documents are clustered in eachlanguage independently using a mixture of multinomial
distributions. Then, clusters are matched by convex kernelized sorting [17], which is an unsupervised object matching method, using the mean vector of each cluster asfeatures. As the number of clusters in Shared-LDA and
Mix-KS, we used the estimated number of clusters by the
proposed model for a fair comparison. We also comparedwith Random as a baseline method, in which documents
are randomly assigned to one of the clusters shared by all
languages.
Table 4 shows the precision, recall and F-measures,
which are averaged over 30 experiments using different
sampled documents for each data set. For the proposedmodel, MMLVM and Shared-LDA, we set the number of
topics at K = 10. The proposed model has achieved
the highest precision, recall and F-measure for both data
sets. Since MMLVM assumes Gaussian observation noise,the performance was low for analyzing text documents.
Shared-LDA and Mix-KS find correspondence of clusters
with two steps of clustering and matching. Therefore, errors
accumulated in clustering cannot be corrected in matchingprocess. On the other hand, since the proposed model
performs clustering and matching simultaneously in one
probabilistic framework, clusters are estimated so as tobe optimal when documents from different languages arematched. Mix-KS might find different cluster structures fordifferent languages because it performs clustering for eachlanguage separately and has local optima for each language.
In contrast, by sharing clusters among different languages,
the proposed model alleviates to be trapped in different
local optima. The recall is low compared with the precision.
This result indicates that documents in the same category
are assigned into different clusters, and modeling a category
requires multiple topic proportion vectors in these data sets.
The computational time of the proposed model was 1.5
hours with the Wikipedia data on PC with Xeon 5160 3GHz
CPU, and that of MMLVM was 45.5 hours. With the Review
data, the proposed model took 4.8 hours, and the MMLVM
was not finished.
Table 5 (a) shows a confusion matrix for the Wikipedia
data set, where clusters are estimated using the proposedmodel, and the total number of clusters was 11. The documents categorized in ‘English footballers’ in English andGerman are perfectly matched in the third cluster, whereother documents are not assigned into the third cluster.
This result is obtained because the documents in ‘English

6

TABLE 2
Examples of topics extracted by the proposed model from the Wikipedia data. In each topic, the top row shows probable words in English, and thebottom row shows those in German.

Topic1
EN: nobel physics prize planck marconi laureates bardeen chemistry physicist max
DE: chemie physik otto physiker nobelpreis chemiker hochschullehrer preisverleihung nobelstiftung max
Topic2
EN: piano composer composers orchestra songs score composition lewis compositions string
DE: davis komponist love spiel jazz my album american nba grammy
Topic3
EN: cup robson players goals match manchester manager fa scored squad
DE: fc united saison verein manchester nationalmannschaft west mannschaft englischer trainer
Topic4
EN: nba basketball johnson coach players finals boston jordan draft championship
DE: nba jackson basketballspieler saison team bryant music bird jordan vereinigte

TABLE 3
Examples of topics extracted by the proposed model from Review data. In each topic, the top row shows probable words of the topic in English,
the middle row shows those in Japanese, and the bottom row shows English translation of those in Japanese at the middle.

TABLE 4
Average precision, recall and F-measure with their standard errors. Values in bold typeface are statistically better at the 5% level from those innormal typeface as indicated by a paired t-test.

Wikipedia
Review

Proposed
0.41 ± 0.04
0.33 ± 0.02(a) Precision
MMLVM Shared-LDA
0.40 ± 0.03
0.20 ± 0.02
NA
0.19 ± 0.01

Mix-KS
0.26 ± 0.04
0.19 ± 0.03

Random0.20 ± 0.00
0.20 ± 0.00

Wikipedia
Review

Proposed
0.44 ± 0.05
0.36 ± 0.03(b) Recall
MMLVM Shared-LDA
0.15 ± 0.01
0.28 ± 0.03
NA
0.29 ± 0.02

Mix-KS
0.16 ± 0.03
0.08 ± 0.02

Random0.11 ± 0.01
0.03 ± 0.00

Wikipedia
Review

Proposed
0.42 ± 0.05
0.34 ± 0.02(c) F-measure
MMLVM Shared-LDA
0.22 ± 0.02
0.23 ± 0.02
NA
0.23 ± 0.02

Mix-KS
0.19 ± 0.03
0.11 ± 0.02

Random0.14 ± 0.00
0.06 ± 0.00

footballers’ consist of distinct words from documents inother categories. On the other hand, the documents in‘Nobel laureates in Physics’ and those in ‘Nobel laureates in
Chemistry’ are clustered into the same cluster, because they
are similar categories. The proposed model failed to distinguish ‘Nobel laureates in Physics’ from ‘Nobel laureatesin Chemistry’. However, documents from other categories
were not assigned into the second cluster, and the proposedmodel succeeded to distinguish ‘Nobel laureates’ categories

from the other categories.
Table 5 (b) shows a confusion matrix for the Review
data set, where the total number of clusters was 25. For
documents categorized in ‘Books’ and ‘Music’, the proposedmodel found matching between English and Japanese.
However, many documents in ‘Watch’, ‘Electronics’ and‘Kitchen’ are assigned to the same cluster because they are
similar; ‘Watch’ can be seen as a part of ‘Electronics’, andsome products in ‘Kitchen’ are electronics.

7

TABLE 5
Confusion matrices for (a) Wikipedia and (b) Review data sets. Each row represents categories of the given data, and each column represents
cluster indices inferred by the proposed model. Thus, (c, `) element shows the number of documents that are categorized in the cth category andassigned to the `th cluster. The left and right values in each element show the value for languages 1 and 2, respectively. We show clusters that
contain more than 5% of total documents.

1
category \ cluster
Nobel laureates in Physics
Nobel laureates in Chemistry
American basketball players
American composers
English footballers

EN
0
17
0
0
0
1

category \ cluster
Watch
Books
Electronics
Kitchen
Music

EN
943
13
986
427
4

(a) Wikipedia
2
DE EN DE
4
30
25
3
11
25
0
0
0
14
0
1
0
0
0

EN
0
0
0
0
30

(b) Review
2
JP
EN
JP
951
4
2
10
1
11
918
0
3
787
2
3
15 691 750

EN
1
899
1
5
15

0.45

3

4
DE
0
0
0
0
30

EN
0
0
0
18
0

JP
2
875
1
1
10

EN
2
1
0
463
2

3

5
DE
0
0
3
5
0

EN
0
0
27
0
0

DE
0
2
27
10
0

4
JP
7
10
31
127
12

0.35

0.4

Proposed

Proposed

0.3

0.35
0.25
F−measureF−measure

0.3
0.25
0.2

Fixed #clusters

0.2
0.15

0.15

Fixed #clusters

0.1
0.1
0.05

0.05
0

10

20

30
#clusters

4050(a) Wikipedia

0

10

20

30
#clusters

4050(b) Review

Fig. 3. F-measure with different fixed numbers of clusters.

We evaluated the effectiveness of the Dirichlet process
in the proposed model that enable us to determine thenumber of clusters in the inference. Figure 3 shows theF-measures with the proposed model and a method withthe fixed number of clusters. The comparing method is thesame with the proposed model except for that it does not
use Dirichlet processes but fixes the number of clusters.
The proposed model achieved the better F-measure than thecomparing method with any number of fixed clusters. Thisis because the proposed model can adaptively change thenumber of clusters in the inference, which alleviates local
optima, by using the Dirichlet processes. On the other hand,the comparing method is likely to be trapped into poor
local optima since it cannot change the number of clusters.
This result indicates that the Dirichlet process is useful for
improving matching performance.
5.4

Sensitivity Analysis

Figure 4 shows the 1) F-measure, 2) computational timeand 3) estimated number of clusters with (a) different numbers of categories, (b) different numbers of documents, (c)different vocabulary size, (d) different numbers of topics
K , and (e) different concentration parameters γ . For (a),we used Wikipedia documents in English and German,
where we kept the total number of documents at 400 whilechanging the number of categories. Here, we used 5,000
most frequently occurring words. The F-measure decreased
as the number of categories increased (a-1) since matching many categories was difficult. The proposed model
achieved higher F-measure than Shared-LDA and Randomwith different numbers of categories. The estimated numberof clusters did not increase as the number of categories
increased. This would be because categories in the given
data does not correspond to clusters in our model. Some
documents in the same category are clustered into multiple
different clusters, which is also seen in the experimentshown in Table 5. Another reason would be that Dirichlet
process mixtures are inconsistent for the number of clusters [28].
For (b)–(e), we used Amazon review documents in English and Japanese, where 1,000 documents were sampledfrom each of the five product categories, and 3,000 mostfrequently occurring words, K = 10 and γ = 1 wereused as the basic settings. The F-measure decreased as thenumber of documents increased (b-1). It would be because
the proposed model found too many clusters (b-3), whichwere finer than categories in the given data, when many
documents were given. The computational time and theestimated number of clusters were increased as the numberof documents increased (b-2, 3).

81) F-measure2) computational time (sec)3) estimated number of clusters

0.3

55

260
0.25

50

250

0.15
0.1

#clusterstime

F-measure

0.2

240

45

230

40

220

35

Proposed

Shared-LDA
0.05
Random
0

10

20

30

210

40

5

10

15

#categories

20
25#categories

30

35

30

40

5

10

15

20
25
#categories

30

35

40

2000

4000

6000

8000 10000 12000 14000#documents(a) different numbers of categories
4

7

90

0.4

6

80

0.35

5

70

0.3

Proposed

60

3

0.2

Shared-LDA

50
40

0.15

2
30

0.1

Random1

0.05
0#clusters

4
0.25

time

F-measure

x 10

2000

4000

6000

8000

0

10000 12000 14000

20

2000

4000

6000

#documents

108000 10000 12000 14000#documents(b) different numbers of documents
4

1.85
1.8

0.4
0.35

45

1.75

Proposed

1.7

40#clusters

0.3

1.65

0.25

time

F-measure

50

x 10

Shared-LDA

0.2

1.6
1.55

0.15

1.45

Random

0.05
0

30

1.5

0.1

35

25

1.4
2000

4000

6000

8000

1.35

10000

2000

4000
6000
vocabulary size

vocabulary size

8000

20

10000

2000

4000
6000
vocabulary size

8000

10000

40

50

(c) different vocabulary size
4

8

x 10

40

0.45

7

0.4

35

6

0.35

Proposed30

0.2#clusters

5time

F−measure

0.3
0.25

4
3

25
20

0.15

2
0.1

Random

0

15

1

0.05

0
10

20

30
#topics

40

10

50

20

30
#topics

40

10

50

10

20

30
#topics(d) different numbers of topics K
4

3.2

0.4

x 10

160

3

0.35

140

2.8

0.3

120

0.2
0.15

#clusters

Proposedtime

F-measure

2.6
0.25

2.4
2.2

100
80

2
60

0.1

1.8

Random
0.05

40

1.6

0
10

0

10

gamma

1

10

2

1.4

0

10

1

10
gamma

2

10

20

0

10

1

10
gamma

2

10

(e) different concentration parameters γ
Fig. 4. 1) F-measure, 2) computational time, and 3) estimated number of clusters when we vary (a) the number of categories, (b) the number of
documents, (c) vocabulary size, (d) the number of topics, and (e) the concentration parameter.

9The F-measure of the proposed model increased as the
vocabulary size increased (c-1) since we were able to utilize
more information. The computational time was small whenthe vocabulary size was small V = 1000 (c-2), because
the average document length was short. The computationaltime did not change after the vocabulary size was larger
than 2,000 (c-2) since the decline of the estimated numberof clusters (c-3) canceled out the effect of the gain of theaverage document length. For all data sets, the proposedmodel achieved higher F-measure than Shared-LDA and
Random (a-1, b-1, c-1).
The F-measure was highest when the number of topics
was K = 30 (d-1). The computational time linearly increased with the number of topics K (d-2). On the other
hand, the computational time of MMLVM cubically increases with K since it calculates the inverse of a (K × K )matrix, which prohibits us to employ MMLVM with a large
number of topics. When the number of topics was high, theestimated number of clusters was low (d-3). It would be
because the given data were modeled with a small numberof clusters by utilizing many topics.
The F-measure decreased as the concentration parameterincreased (e-1) since many irrelevant clusters were generated with a high concentration parameter (e-3). When theconcentration parameter γ increased, the estimated numberof clusters increased (e-3), and therefore, the computationaltime increased (e-2).

6integrating out topic proportion vectors Φ as follows,p(Z|S, α)
Z Y
L
M D
m N
md
Y
Y
Y
=
p(zmdn |θsmd )dΘp(θ` |α)m=1 d=1 n=1
K
M Dm Nmd
Y
Γ(αK) Y α−1 Y Y=θθsmd ,zmd dΘ`kK
Γ(α) k=1
m=1 d=1 n=1`=1
L K
Γ(αK)L Y Y N`k +α−1=dΘθΓ(α)KL `=1 k=1 `k
L QΓ(αK)L Y K
k=1 Γ(N`k + α)
=
.
(11)
KL
Γ(α)
Γ(N` + αK)
`=1
`=1

Z Y
L

Here, in the second equation, we used the fact that p(θ` |α)is a Dirichlet distribution and p(zmdn |θsmd ) = θsQ. In
md ,zmdK
R QK
Γ(αk )
αk −1
k=1
PK
dθ
=
θ
the fourth equation, we usedk=1 k
Γ( k=1 αk )which is the normalizing constant of the Dirichlet distribution. In a similar way, we can derive the probability of words
W given latent topics Z and Dirichlet parameter β (4).
Similarly, the derivation of the probability of words W
given latent topics Z and Dirichlet parameter β (4) is given
as follows,p(W |Z, β)
D
M Z Y
K
m N
md
Y
Y
Y
p(wmdn |φmd )dΦm=p(φmk |β)d=1 n=1
V
D
m
m N
md
Y
Y
Γ(βVm ) Y
β−1
φφmdwmdn dΦm=
Γ(β)Vm v=1 mkv d=1 n=1
m=1
k=1
Z Y
Vm
M
K Y
Y
Γ(βVm )KNmkv +β−1
=
φmkv
dΦm
Vm K
Γ(β)
m=1
k=1 v=1
M
K Q m
Y
Γ(βVm )K Y Vv=1
Γ(Nmkv + β)
=
.
(12)
Vm K
Γ(β)
Γ(N
mk + βVm )
m=1
k=1
m=1
k=1
Z
M
K
Y
Y

C ONCLUSION

We proposed a topic model to find cluster matching without alignment information for discrete data with multiple
domains. The proposed model has a set of topic proportion
vectors shared among different languages. By assigning a
topic proportion vector for each document, documents in all
languages are clustered in a common space. The documents
assigned into the same cluster are considered as matched.
In the experiments, we confirmed that the proposed model
could perform better than a combination of clustering andunsupervised object matching. We also showed that the
proposed model could extract shared topics from real multilingual text data sets without dictionaries and parallel
documents.
For future work, we will extend the proposed model
for a semi-supervised setting, where a small number ofcorrespondence information is available. With the proposedmodel, the number of topics and concentration parameterare hyperparameters to be set by users. The number of
topics can be inferred by using hierarchical Dirichlet processes [29] or nested Dirichlet processes [30]. The concentration parameter can be inferred by using Markov chain
Monte Carlo methods assuming a gamma prior [29].

A PPENDIX A
D ERIVATION OF (3) AND (4)The derivation of the probability of latent topics Z given
latent clusters S and Dirichlet parameter α (3) is given by

A PPENDIX B
D ERIVATION OF (8)The derivation of (8) is given as follows,p(Z|smd = `, S\md , α)L QK
Γ(αK)L Y k=1 Γ(N`0 k\md + α)=
Γ(α)KL `0 =1 Γ(N`0 \md + αK)
QKΓ(N`\md + αK)
k=1 Γ(N`k\md + Nmdk + α)× QK
Γ(N`\md + Nmd + αK)
k=1 Γ(N`k\md + α)
= p(Z\md |S\md , α)×KY
Γ(N`k\md + Nmdk + α)Γ(N`\md + αK).
Γ(N`\md + Nmd + αK) k=1
Γ(N`k\md + α)
(13)

R EFERENCES[1][2]

D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent Dirichlet allocation,”
Journal of Machine Learning Research, vol. 3, pp. 993–1022, 2003.
T. L. Griffiths and M. Steyvers, “Finding scientific topics,” Proceedings of the National Academy of Sciences, vol. 101 Suppl 1, pp.
5228–5235, 2004.

10

T. Hofmann, “Probabilistic latent semantic analysis,” in Proceedingsof Conference on Uncertainty in Artificial Intelligence, 1999, pp. 289–
296.
[4] ——, “Collaborative filtering via Gaussian probabilistic latentsemantic analysis,” in Proceedings of the Annual International ACM
SIGIR Conference on Research and Development in Information Retrieval, 2003, pp. 259–266.
[5] D. M. Blei and M. I. Jordan, “Modeling annotated data,” inProceedings of the Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval, 2003, pp. 127–134.
[6] L. Cao and L. Fei-Fei, “Spatially coherent latent topic model for
concurrent object segmentation and classification.” in Proceedingsof IEEE Intern. Conf. in Computer Vision (ICCV), 2007.
[7] A. Tripathi, A. Klami, and S. Virpioja, “Bilingual sentence matching using kernel CCA,” in MLSP ’10: Proceedings of the 2010 IEEE
International Workshop on Machine Learning for Signal Processing,
2010, pp. 130–135.
[8] R. Socher and L. Fei-Fei, “Connecting modalities: Semi-supervised
segmentation and annotation of images using unaligned text
corpora,” in Proceedings of the IEEE Conference on Computer Vision
and Pattern Recognition, ser. CVPR, 2010, pp. 966–973.
[9] B. Li, Q. Yang, and X. Xue, “Transfer learning for collaborative
filtering via a rating-matrix generative model,” in Proceedings ofthe 26th Annual International Conference on Machine Learning, ser.
ICML ’09, 2009, pp. 617–624.
[10] I. P. Fellegi and A. B. Sunter, “A theory for record linkage,” Journalof the American Statistical Association, vol. 64, no. 328, pp. 1183–
1210, 1969.
[11] N. Quadrianto, A. J. Smola, L. Song, and T. Tuytelaars, “Kernelized
sorting,” IEEE Trans. on Pattern Analysis and Machine Intelligence,
vol. 32, no. 10, pp. 1809–1821, 2010.
[12] A. Haghighi, P. Liang, T. Berg-Kirkpatrick, and D. Klein, “Learningbilingual lexicons from monolingual corpora,” in Proceedings of
ACL-08: HLT, 2008, pp. 771–779.
[13] D. Mimno, H. M. Wallach, J. Naradowsky, D. A. Smith, and
A. McCallum, “Polylingual topic models,” in Proceedings of the2009 Conference on Empirical Methods in Natural Language Processing,
2009, pp. 880–889.
[14] D. Zhang, Q. Mei, and C. Zhai, “Cross-lingual latent topic extraction,” in Proceedings of the 48th Annual Meeting of the Association for
Computational Linguistics, 2010, pp. 1128–1137.
[15] J. Jagarlamudi and H. Daumé III, “Extracting multilingual topics
from unaligned comparable corpora,” in Advances in Information
Retrieval. Springer, 2010, pp. 444–456.
[16] J. Boyd-Graber and D. Blei, “Multilingual topic models for unaligned text,” in Proceedings of Conference on Uncertainty in Artificial
Intelligence, 2009, pp. 75–82.
[17] N. Djuric, M. Grbovic, and S. Vucetic, “Convex kernelized sorting,” in Proceedings of AAAI Conference on Artificial Intelligence,
2012.
[18] M. Yamada and M. Sugiyama, “Cross-domain object matchingwith model selection,” in Proceedings of International Conference on
Articial Intelligence and Statistics, 2011, pp. 807–815.
[19] A. Klami, “Variational Bayesian matching,” in Proceedings of Asian
Conference on Machine Learning, 2012, pp. 205–220.
[20] ——, “Bayesian object matching,” Machine learning, vol. 92, pp.
225–250, 2013.
[21] A. Smola, A. Gretton, L. Song, and B. Schölkopf, “A Hilbert spaceembedding for distributions,” in Algorithmic Learning Theory, 2007,
pp. 13–31.
[22] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97,
1955.
[23] T. Iwata, T. Hirao, and N. Ueda, “Unsupervised cluster matching
via probabilistic latent variable models,” in Proceedings of the AAAI
Conference on Artificial Intelligence, 2013.
[24] T. Iwata, J. Lloyd, and Z. Ghahramani, “Unsupervised many-tomany object matching for relational data,” IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol. 38, no. 3, pp. 607–
619, 2016.
[25] T. Zhang, K. Liu, and J. Zhao, “Cross lingual entity linking withbilingual topic model,” in Proceedings of the International Joint
Conference on Artificial Intelligence, 2013, pp. 2218–2224.
[26] G. Csurka, C. Dance, J. Willamowski, L. Fan, and C. Bray, “Visual
categorization with bags of keypoints,” in ECCV International
Workshop on Statistical Learning in Computer Vision, 2004.
[3][27] J. Sethuraman, “A constructive definition of Dirichlet priors,”
Statistica Sinica, vol. 4, pp. 639–650, 1994.
[28] J. W. Miller and M. T. Harrison, “A simple example of dirichlet
process mixture inconsistency for the number of components,” inAdvances in Neural Information Processing Systems, 2013, pp. 199–
206.
[29] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei, “Hierarchical
Dirichlet processes,” Journal of the American Statistical Association,
vol. 101, no. 476, pp. 1566–1581, 2006.
[30] A. Rodriguez, D. B. Dunson, and A. E. Gelfand, “The nested
Dirichlet process,” Journal of the American Statistical Association, vol.
103, no. 483, 2008.

Tomoharu Iwata received the B.S. degree inenvironmental information from Keio University
in 2001, the M.S. degree in arts and sciencesfrom the University of Tokyo in 2003, and the
Ph.D. degree in informatics from Kyoto University in 2008. In 2003, he joined NTT Communication Science Laboratories, Japan. From 2012
to 2013, he was a visiting researcher at Machine Learning Group, Department of Engineering, University of Cambridge, UK. He is currently a senior research scientist (distinguishedresearcher) at Ueda Research Laboratory of NTT Communication Science Laboratories, Kyoto, Japan. His research interests include data
mining, machine learning, information visualization, and recommendersystems.

Tsutomu Hirao received the B.E. from Kansai University in 1995, M.E. and Ph.D. in Engineering from Nara Institute of Science andTechnology in 1997 and 2002, respectively. He
is currently with NTT Communication Science
Laboratories. His current research interests include Natural Language Processing and Machine Learning.

Naonori Ueda received the B.S., M.S., andPh D degrees in Communication Engineeringfrom Osaka University, Osaka, Japan, in 1982,
1984, and 1992, respectively. In 1984, he joined
the Electrical Communication Laboratories, NTT,
Japan, where he was engaged in research on
image processing, pattern recognition, and computer vision. In 1991, he joined the NTT Communication Science Laboratories. From 1993 to
1994, he was a visiting scholar at Purdue University, West Lafayette, USA. He was a directorof NTT Communication Science Laboratories(April,2010-March,2013).
Currently, he is a head of Ueda Research Laboratory (NTT Fellow), andis a director of Machine Learning and Data Science Center. He also
serves as a Deputy Director, RIKEN Center for Advanced Intelligence
Project, newly established in April, 2016. He is a visiting professor, Graduate School of Informatics, Kyoto University, and National Institute ofInformatics (NII). He is a member of the Information Processing Societyof Japan(IPSJ), a fellow of the Institute of Electronics, Information, andCommunication Engineers in Japan(IEICE), and a senior member ofIEEE.