Noname manuscript No.
(will be inserted by the editor)

Unsupervised Group Matching with
Application to Cross-lingual Topic Matching
without Alignment Information
Tomoharu Iwata · Motonobu Kanagawa ·Tsutomu Hirao · Kenji Fukumizu

Received: date / Accepted: date

Abstract We propose a method for unsupervised group matching, which is the taskof finding correspondence between groups across different domains without crossdomain similarity measurements or paired data. For example, the proposed method
can find matching of topic categories in different languages without alignment information. The proposed method interprets a group as a probability distribution, whichenables us to handle uncertainty in a limited amount of data, and to incorporate thehigh order information on groups. Groups are matched by maximizing the dependence between distributions, in which we use the Hilbert Schmidt independence criterion for measuring the dependence. By using kernel embedding which maps distributions into a reproducing kernel Hilbert space, we can calculate the dependence
between distributions without density estimation. In the experiments, we demonstrate
the effectiveness of the proposed method using synthetic and real data sets including
an application to cross-lingual topic matching.
Keywords Unsupervised object matching, Kernel embedding of distributions,
Multilingual corpus analysis
T. Iwata
NTT Communication Science Laboratories
2-4 Hikaridai, Seikacho, Sorakugun, Kyoto, 619-0237, Japan
Tel.: +81-774-93-5161
Fax: +81-774-93-5155
E-mail: iwata.tomoharu@lab.ntt.co.jp
M. Kanagawa
The Institute of Statistical Mathematics, Japan
T. Hirao
NTT Communication Science Laboratories, JapanK. Fukumizu
The Institute of Statistical Mathematics, Japan2

Tomoharu Iwata et al.

1 Introduction
Object matching is an important task in natural language processing, machine learning, data mining, image processing, bioinformatics, and so on. Examples of object
matching include matching an image with a caption (Socher and Fei-Fei, 2010), an
English word with a German word (Tripathi et al, 2010), concepts in different ontologies (Shvaiko and Euzenat, 2013), and user identification in different databases (Liet al, 2009). Most object matching methods require similarity measurements between
objects in different domains, or paired data across domains that contain correspondence information. However, similarity measurements and paired data are unavailable
in some applications because obtaining those information would incur a cost and require time, or invade privacy. For such situations, a number of methods for unsupervised object matching have been proposed, such as kernelized sorting (Quadrianto
et al, 2010) and matching canonical correlation analysis (Haghighi et al, 2008).
In this paper, we consider a related but different task, which we call unsupervisedgroup matching. Here, a group consists of a set of objects. In many data sets, objects form a group; documents are categorized according to their topics, users form
communities, movies are associated with genres, and images are grouped by contents. Unsupervised group matching is the task of finding correspondence between
groups given two sets of groups in different domains without cross-domain similarity
measurements or paired data. The task appears in a wide variety of applications fordata with groups. For instance, group matching can be used for matching topic categories in different languages given a multilingual corpora without dictionaries andparallel corpora, which is important especially for resource poor languages. Other
examples include matching groups of images and documents according to their topics (Barnard et al, 2003), matching user communities and movie genres by their preferences (Kamahara et al, 2005), discovering companies in the same position acrossdifferent countries by representing the companies with their products, and finding
correspondence between groups of genes in protein-protein interaction networks ofdifferent species (Terada and Sese, 2012).
This paper proposes a kernel-based sorting method for unsupervised group matching. The main idea of the proposed method is to interpret a group as a probability
distribution, and consider each object in a group as a sample from the underlying
distribution. Then, our problem is transformed to finding a matching between sets ofprobability distributions in different domains. Our method consists of two-steps (Figure 1). First, we map each distribution (group) into a reproducing kernel Hilbert space(RKHS) defined on a distinct domain, based on the framework of kernel embeddingof distributions (Smola et al, 2007). The kernel representation of distributions enables
us to maintain and handle necessary information of groups such as their covarianceor higher-order moments. Then we find a matching between the sets of elements inthe different RKHSs that maximizes the dependency between them. As a dependence
measure, we employ the Hilbert-Schmidt independence criterion (HSIC) (Gretton
et al, 2005), which can be used for unsupervised matching tasks once appropriate
kernels are defined for each domain. To apply HSIC, we define second-level kernels
on each RKHS, for which we conduct necessary theoretical analysis in the paper. Our

Unsupervised Group Matching

3

RKHS

observed
spacedomain1domain2Fig. 1 Framework of the proposed method. The input is two sets of grouped objects, where an object isrepresented by a point and the group is represented by its color in the observation space. The distribution
for each group is mapped into a reproducing kernel Hilbert space (RKHS) for each domain, where themapped distributions are represented by points in the RKHS. The groups in different domains are matchedbased on the Hilbert Schmidt independence criterion of the mapped distributions.

approach only requires similarity between objects within a distinct domain, and thus
does not need a similarity measure between objects across domains.
To our knowledge, this is the first study for unsupervised group matching. One
might think that a naive extension of unsupervised object matching methods could
be used for matching groups, where each group is represented by its typical value,such as mean and mode. However, in the process of transforming a group to a feature,
information loss is inevitable in general. For example, when a group is represented
by its mean, variance and skewness of the group cannot be considered in matching.
On the other hand, because the proposed method represents a group by its distribution using kernel embedding, it can preserve necessary information of distributions.
Another naive method for group matching is that objects are first aligned using an
object matching method, and then groups are matched using the object alignment information. This method, however, requires much more computational time than the
proposed one: the time complexity of the naive method is cubic to the number of objects, while that of the proposed method is cubic to the number of groups. Since thenumber of groups is much smaller than the number of objects, the proposed method
can efficiently find group matching. By handling a set of objects as a group insteadof as individual objects, we can reduce the computational time.
The remainder of this paper is organized as follows. In Section 2, we briefly review related work on unsupervised group matching. In Section 3, we formulate theproposed method, which calculates the dependency between distributions using the
HSIC and kernel embedding. In Section 4, we give theoretical results on the proposed
method. In Section 5, we demonstrate the effectiveness of the proposed method byusing synthetic and real data, which include multilingual categorized documents foran application of category matching in different languages. Finally, we present concluding remarks and a discussion of future work in Section 6.

4

Tomoharu Iwata et al.

2 Related Work
There have been proposed a number of unsupervised object matching methods, suchas kernelized sorting (Quadrianto et al, 2010), convex kernelized sorting (Djuric
et al, 2012), matching canonical correlation analysis (Haghighi et al, 2008), leastsquares object matching (Yamada and Sugiyama, 2011), variational Bayesian matching (Klami, 2012), and many-to-many matching latent variable models (Iwata et al,2013). Their applications include aligning multilingual documents, visualizing data
in a particular structure, and matching images. These methods find correspondence by
maximizing the dependency between matched pairs. Intuitively, they match objects
that have similar neighborhood relationships. For example, kernelized sorting uses
the HSIC for measuring the dependency that is calculated based on kernel matrices
for objects within each domain. These methods, however, are designed for object
matching, and thus cannot used for the group matching problem straightforwardly.
Kernel embedding has been used for extending kernel methods to grouped data.
For example, the support measure machine (Muandet et al, 2012) is a method for kernel based discriminative learning on distributions, which generalizes the support vector machine by kernel embedding. The one-class support measure machine (Muandet
and Schölkopf, 2013) is a group anomaly detection method that finds anomalous aggregated behaviors of objects. The support measure machine and the one-class support measure machine achieved high performance with classification and anomaly
detection tasks, respectively, by assuming that a group is modeled as a distribution.
The proposed method is a generalization of kernelized sorting for grouped data.
Group matching is related to ontology matching (Doan et al, 2004). Given two
taxonomies, ontology matching methods find the most similar concept node in theother taxonomy. Although there have been proposed a number of methods for ontology matching (Shvaiko and Euzenat, 2013), they are not unsupervised methods. For
example, they require that there are objects that appear in both domains, features areshared across different domains which enables us to calculate similarities, or graphstructures of the given ontologies are used for matching.

3 Proposed Method
3.1 Group matching
Suppose that we are given two grouped data sets from different domains {X1 , · · · , XN }and {Y1 , · · · , YN } with equal size N of groups. Here, Xn = {xn1 , · · · , xnIn } is aset of objects in the nth group in the first domain, xni ∈ X is the ith object in the nthgroup in the first domain, Yn = {yn1 , · · · , ynJn } is a set of objects in the nth groupin the second domain, and ynj ∈ Y is the jth object in the nth group in the second domain. The task is to find correspondence between groups across the first and second
domains. We assume that similarity, or kernel, can be calculated within a domain, butsimilarity across different domains is not given. The correspondence between groups,
or between objects, over different domains are unavailable. The number of objects ina group can be different over groups.

Unsupervised Group Matching5

We represent each group, or set of objects, by a probability distribution assuming that observed objects are generated from an unknown distribution. Let Pn is a
distribution of the nth group in the first domain, Xn ∼ Pn , and Qn is a distributionof the nth group in the second domain, Yn ∼ Qn . Then, the task of group matching is considered as the task of matching two sets of distributions, {P1 , · · · , PN }and {Q1 , · · · , QN }. The cross-domain matching is encoded in a permutation matrix
π ∈ ΠN , where}{(1)ΠN := π|π ∈ {0, 1}N ×N , π1N = 1N , π ⊤ 1N = 1N ,and 1N is the N dimensional vector of all ones. We find correspondence by maximizing the pairwise dependency as follows,()
arg max D {(Pn , Qπ(n) )}N
(2)
n=1 ,
π∈ΠN

where D(·) is a measurement for the dependency.

3.2 Dependency between distributions
For the dependency measure between distributions, we use the Hilbert-Schmidt information criterion (HSIC) (Gretton et al, 2005). The HSIC is successfully used for
unsupervised object matching methods, such as kernelized sorting (Quadrianto et al,
2010; Djuric et al, 2012). However, these methods use HSIC for dependency between
objects. In our task, the HSIC for dependency between distributions is required. For
obtaining the HSIC for distributions, we map distributions into the reproducing kernel Hilbert space (RKHS) using the kernel embedding (Smola et al, 2007). The kernel
embedding allows us to calculate the HSIC without density estimation while preserving necessary information of distributions.
3.2.1 Representation of distributions using kernel embeddings
Let k : X ×X → R be a reproducing kernel on X . Then it is known that there exists a
reproducing kernel Hilbert space (RKHS) Hk uniquely associated with k. The RKHS
Hk consists of functions on X , e.g. the function k(·, x), which is called the feature
vector of x ∈ X , is included in HX .
Then we represent any distribution P on X by its expectation of the feature vector(Smola et al, 2007):∫µP := Ex∼P [k(·, x)] =k(·, x)dP(x) ∈ Hk ,(3)
X

which is an element in the RKHS, and called the kernel embedding of P .
nThen by interpreting each group Xn = {xni }Ii=1
as an empirical distributionn1 ∑δx (·),
In i=1 ni

I

Pn :=

(4)

6

Tomoharu Iwata et al.

where δx is the Dirac delta function at point x ∈ X , the representation of the nthgroup is given byn1 ∑k(·, xni ) ∈ Hk .
In i=1

I

µPn =

(5)

When samples Xn are generated i.i.d. from a distribution P∗n , the convergence rateof the empirical mean µPn to the expectation µP∗n (Smola et al, 2007) is−1∥µP∗n − µPn ∥Hk = Op (In 2 ).

(6)

Let us consider two groups of samples generated from distributions P∗n and P∗m .
The distance between the empirical mean of the two groups ∥µPn − µPm ∥Hk con1
verges to that of the true distributions ∥µP∗n −µP∗m ∥Hk with the rate of Op (min(In , Im )− 2 )(Gretton et al, 2012b). In other words, we can detect the difference between groups
with this rate.
Similarly, we represent the groups on Y using the kernel embedding. Let ℓ :Y × Y → R be a reproducing kernel on Y, and Hℓ be the associated RKHS. Thennthe nth group Yn = {ynj }Jj=1
is represented as the embedding of the empirical∑Jn1
distribution Qn := Jn i=1 δynj (·):
n1 ∑ℓ(·, ynj ) ∈ Hℓ .
Jn j=1

J

µQn =

(7)

−1

If the samples are i.i.d., its convergence rate is Op (Jn 2 ) as in (6).
Advantages of using the kernel embedding for the representation of groups arethat 1) we do not need to prespecify the number of members in each group, 2) we canmeasure the distance, or similarity in terms of level-2 kernels introduced below, between groups, 3) we can deal with any domain of objects once we define a kernel, e.g.
documents or images, and 4) we can capture the properties of each group described
as a probability distribution, such as covariance structure of the group.
The property 4) is of special importance: for example, consider the case where
there are different groups Xn and Xm which share the same point as a mean, buthave different covariance structures. Then we cannot distinguish these groups if wenaively represent them with their shared mean value. Thus it is important that we candistinguish the groups by their higher order moments.
It is known that the order of moments to which the kernel embedding representation can distinguish is determined by the kernel k (Fukumizu et al, 2004; Smola et al,2007; Sriperumbudur et al, 2010). For example, if we use a polynomial kernelk(x, x′ ) = (⟨x, x′ ⟩ + c)d ,(8)of degree d ∈ N, we can represent distributions up to their d-th moments using
the kernel embedding. On the other hand, there exists a family of kernels that candistinguish any pair of distributions, such as the Gaussian kernel( γ)k(x, x′ ) = exp − ∥x − x′ ∥2 ,(9)2

Unsupervised Group Matching

7

with γ > 0. Such kernels are called characteristic 1 (Fukumizu et al, 2008; Sriperumbudur et al, 2010).
3.2.2 HSIC on embedded distributions
Given the representation of the groups (5, 7), the maximization problem (2) now turns
to be
(
)
arg max D {(µPn , µQπ(n) )}N
(10)
n=1 .
π∈ΠN

Let P and Q be the sets of all probability distributions on X and Y, respectively. Let
FP := {µP : P ∈ P} ⊂ Hk and FQ := {µQ : Q ∈ Q} ⊂ Hℓ be the sets of all theembedded distributions. Then what we next do is to define the dependency measure
D on (FP , FQ ). To this end, we apply HSIC to the sets of kernel embeddings.
Without loss of generality, assume that we would like to quantify the amount ofdependency of the matching {(µPn , µQn )}N
n=1 . HSIC measures the dependency ofthe set of pairs {(µPn , µQn )}N
by
1)
first
assuming that they are samples fromn=1
some joint distribution Pr(µP , µQ ) on FP × FQ and 2) then estimating the distance
between the joint distribution Pr(µP , µQ ) and the product of their marginal distributions Pr(µP ) and Pr(µQ ) using the samples {(µPn , µQn )}N
n=1 .
HSIC also represents the distributions on FP × FQ using the kernel embedding.
Thus, we need to additionally define kernels on FP and FQ . We denote these kernels
in capitals; let K and L be reproducing kernels on FP and FQ , respectively. We willcall these kernels level-2, in contrast to the kernels k and ℓ used for the representationof groups in the first level. We will show concrete examples of the level-2 kernels
later in Section 3.4.
Let HK and HL be the RKHSs associated with the kernels K and L, respectively.
Then we can define an RKHS on FP × FQ by their tensor product HK ⊗ HL , whichis equivalent to the RKHS associated with the joint kernel K ⊗L on FP ×FQ definedby
K ⊗ L((µP , µ′P ), (µQ , µ′Q )) := K(µP , µ′P )L(µQ , µ′Q ).

(11)

Using the joint kernel, we represent the joint distribution Pr(µP , µQ ) as the kernel embedding EµP ,µQ [K(·, µP ) ⊗ L(·, µQ )] into HK ⊗ HL . Likewise, the productof the marginal distributions Pr(µP ) and Pr(µQ ) is embedded as EµP [K(·, µP )] ⊗EµQ [L(·, µQ )]. Then HSIC (in population) is defined as the distance between theseembeddings (Smola et al, 2007):∥EµP [K(·, µP )] ⊗ EµQ [L(·, µQ )] − EµP ,µQ [K(·, µP ) ⊗ L(·, µQ )]∥2HK ⊗HL ≥ 0,
(12)
where ∥ · ∥HK ⊗HL denotes the norm of HK ⊗ HL .
∫More precisely, kernel k is called characteristic if the map P → Hk : P → µP := k(·, x)dP(x) is
injective. Thus, if we use a characteristic kernel, then the embedding µP uniquely identifies the underling
distribution P.
1

8

Tomoharu Iwata et al.

It immediately follows that when the joint kernel K ⊗ L is characteristic, i.e. theembedding of distributions into HK ⊗ HL is injective, then HSIC (12) is equal tozero if and only if µP and µQ are independent. In other words, a large value of HSIC
indicates that there is a strong dependency between µP and µQ . In Section 4.2, wewill show that the joint kernel is characteristic when the level-2 kernels K and L aregiven as Gaussian kernels.
3.3 Group kernelized sorting
Given the matching {(µPn , µQn )}N
n=1 , which can be seen as samples from Pr(µP , µQ ),the empirical estimate of HSIC (12) is then given by (Gretton et al, 2005)
D({(µPn , µQn )}Nn=1 ) :=

11
trHKHL = 2 trK̄L̄,
2
N
N

(13)

N ×N
where H = I − 1N 1⊤
are the kerN /N is a centering matrix, and K, L ∈ R
nel matrices for the kernel embeddings, i.e. Kn,m = K(µPn , µPm ) and Ln,m =L(µQn , µQm ), and K̄ = HKH and L̄ = HLH denote the centered versions of K
and L, respectively.
Then, we solve the task of unsupervised group matching based on the frameworkof (2) using the HSIC (13) for the dependency between distributions as follows,arg max tr(K̄π ⊤ L̄π).

(14)

π∈ΠN

We refer to the proposed method as group kernelized sorting.
We find group matching by solving a convex relaxation of (14) as describedin (Djuric et al, 2012). The convex version achieved better matching performance
than the original kernelized sorting. Equation (14) is rewritten by the following equivalent problem,arg min ∥ K̄π ⊤ − (L̄π)⊤ ∥2 ,
π∈ΠN

(15)

where ∥ · ∥ denotes the Frobenius norm. We relax the constraint that π is a permutation matrix, and then obtain the following convex problem,arg min∗π∥ K̄π ∗⊤ − (L̄π ∗ )⊤ ∥2∗
subject to πij≥ 0,

π ∗ 1 = 1,

π ∗⊤ 1 = 1,(16)

where the permutation matrix binary constraint πij ∈ {0, 1} is replaced by the inter∗val constraint πij∈ [0, 1], and π ∗ is a doubly-stochastic matrix. This convex problem
can be solved by a numerical optimization method, such as the trust-region-reflective
algorithm (Coleman and Li, 1996), which is used for our experiments. The time complexity for each iteration is O(N 2 ).
After doubly-stochastic matrix π ∗ is obtained by (16), we find hard assignments
by solving the following linear assignment problem defined by π ∗ ,∑∗arg min
πij πij
,
(17)
π∈ΠN

i,j

Unsupervised Group Matching

9

Algorithm 1 Procedures of the proposed method.
Require: two grouped data sets {Xn }, {Yn }, level-1 and level-2 kernels
Ensure: assignments π
1: calculate kernel values between groups K, L
2: centerize the kernel values K̄, L̄
3: obtain a doubly-stochastic matrix π ∗ by (16)
4: obtain hard assignments π by (17)where the Hungarian algorithm (Kuhn, 1955) is used. Algorithm 1 shows the procedures of the proposed method. The time complexity for solving (17) by the Hungarianalgorithm is cubic to the number of groups, O(N 3 ).
The doubly-stochastic matrix π ∗ contains soft assignments. Therefore, we can∗∗rank matched groups with the ith group using probabilities πi1, · · · , πiN.

3.4 Level-2 kernels
We show here examples of level-2 kernel K on the set of embedded distributions FP ,as well as their empirical estimates (Muandet et al, 2012). We will omit those for L
on FQ , as they are similar to the case of
Recall that we represent each group Xn∑K.
Ink(·, xni ) using kernel k on the originalas an empirical embedding µPn = I1n i=1
space X .
Linear kernel. Linear kernel KLIN on FP ⊂ Hk is defined as KLIN (µP , µP′ ) :=⟨µP , µP′ ⟩Hk , ∀µP , µ′P ∈ FP . Thus, the kernel value for group Xn and group Xm isgiven by⟨KLIN (µPn , µPm ) =

=

In
Im
1 ∑
1 ∑
k(·, xni ),k(·, xmj )In i=1
Im j=1

⟩

In ∑
Im
∑

1
k(xni , xmj ).
In Im i=1 j=1

Hk

(18)

Polynomial kernels. Nonlinear kernels can also be defined on FP . For example,a polynomial kernel on FP is given by
KPOLY (µPn , µPm ) = (⟨µPn , µPm ⟩Hk + c)d ,(19)

where d ∈ N is the order of polynomial and c > 0 is a constant.
Gaussian kernels. We can define a Gaussian kernel Kγ on FP with parameterγ > 0 by)( γ
Kγ (µPn , µPm ) = exp − ||µPn − µPm ||2Hk( γ2)= exp − (⟨µPn , µPn ⟩Hk − 2⟨µPn , µPm ⟩Hk + ⟨µPm , µPm ⟩Hk ) .
2
(20)

10

Tomoharu Iwata et al.

Note that we can calculate the inner-product ⟨·⟩Hk in the above nonlinear kernels as
for linear kernel KLIN (18).
The time complexity for calculating the kernel matrix K of N kernel embeddingsis O(N 2 I 2 ), where I is the average number of objects in each group.

3.5 Discussion
We assume that a group is modeled as a distribution. When samples in a group
Xn = {xn1 , · · · , xnIn } are generated i.i.d. according to a distribution P∗n , it is valid
to represent this group by the empirical distribution Pn . In general, the samples are
assumed to have a stationary distribution P∗n , and the empirical distribution Pn should
be a consistent estimator of that distribution.
The performance of unsupervised group matching depends on kernels. When correspondence information between groups in different domains is available, we would
select the best kernel by evaluating the matching performance. In the case that correspondence information is unavailable, it is impossible to select the best kernel interms of the matching performance. However, some heuristics could be used. For
example, the median trick can be used for Gaussian kernels, where the median of
pairwise distances between the kernel embeddings is used for its width. The mediantrick has been widely used for kernel embeddings (Quadrianto et al, 2010; Gretton
et al, 2012b; Song et al, 2012; Muandet and Schölkopf, 2013). Another heuristic is
to use kernels that maximize RKHS distance (Sriperumbudur et al, 2009), which isequivalent to minimizing the error in classifying groups under linear loss.

4 Theoretical Analysis
4.1 Relation between HSIC on the embeddings and the original spaces
Here, we see that HSIC on the kernel embeddings defined in the previous section canbe reduced to HSIC on the original spaces for special situations. Proposition 1 below,
which is similar to the one obtained for the support measure machines (Muandet et al,2012), shows that if the level-2 kernels are linear and the distributions of the groups
have a specific form, HSIC of the embeddings can be written in terms of HSIC on theoriginal spaces using specific kernels. The proof is given in the appendix.
Proposition 1 Let k and ℓ be bounded kernels. Let p(x|x′ ) and q(y|y ′ ) be conditional densities on X and Y, respectively. Assume that we are given distributions{(Pn , Qn )}N
n=1 whose densities are given by p(x|xn ) and q(y|yn ), where xn ∈X , yn ∈ Y are points in the original spaces. Then HSIC (13) on embeddings{(µPn , µQn )}N
n=1 using linear kernels for FP and FQ is equivalent to HSIC on{(xn , yn )}N
n=1 using the kernels∫ ∫kp (x, x′ ) :=k(x̃, x̃′ )dp(x̃|x)dp(x̃′ |x′ ),(21)

Unsupervised Group Matching

11

and
′

∫ ∫

ℓq (y, y ) :=ℓ(ỹ, ỹ ′ )dq(ỹ|y)dq(ỹ ′ |y ′ )(22)for X and Y, respectively.
Let us explain the proposition by some instantiations. For example, if each groupis represented by one point in the original space, i.e. p(·|xn ) := δxn (·) and p(·|yn ) :=δyn (·), then we have kp (x, x′ ) = k(x, x′ ) and ℓq (y, y ′ ) = ℓ(y, y ′ ). Thus, HSIC on
groups subsumes HSIC on the original spaces as a special case.
Consider another case where each distribution is described by a Gaussian dis2
2
tribution with mean xn and fixed variance σX> 0, i.e. p(x|xn ) = N (xn , σX
I).
′
Assume also that the kernel is Gaussian with bandwidth σ > 0, i.e. k(x, x ) =kσ2 (x, x′ ) := exp(−∥x − x′ ∥2 /2σ 2 ). Then the convolution theorem of Gaussian
σ2
d/2
distributions shows that kp (x, x′ ) = ( σ2 +2σ
kσ2 +2σX2 (x, x′ ). Namely, in this2 )Xcase HSIC on the kernel embeddings is reduced to HSIC on the original spaces using
Gaussian kernels with larger bandwidth.
Note that our approach does not assume any model for the distributions, and thus
can be applied to situations where such prior knowledge on the group structures is
not available.
4.2 Characteristic property of the Gaussian kernel on the set of kernel embeddings
As stated in Section 3.2.2, HSIC in population (12) is equal to zero if and only µP andµQ are independent, when the joint kernel K ⊗ L is characteristic. It can be easily
shown that the joint kernel is characteristic if both of the level-2 kernels K and L
are characteristic. Here, we show that the Gaussian kernel Kγ (20) defined on FP(and thus the Gaussian kernel on FQ ) is characteristic. The proofs are given in the
appendix.
We first show in Lemma 1 below that the set of all the kernel embeddings FP is
compact if the original space X is compact.
Lemma 1 Let (X , dX ) be a compact metric space and P be the set of all Borel
probability measures on X . Let k be a continuous kernel on X , Hk be its RKHS, and∫FP := {f ∈ Hk : f = k(·, x)dP(x), ∃P ∈ P}.
(23)
Let γk be a metric on FP defined by
γk (f, g) = ∥f − g∥Hk , ∀f, g ∈ FP .

(24)

Then (FP , γk ) is a compact metric space.
It is known that a universal kernel2 on a compact metric space is characteristic. By
showing that Kγ is universal using the result of (Christmann and Steinwart, 2010),
we have the following theorem.
2 A kernel is called universal if its associated RKHS is dense in the space of bounded continuousfunctions (Steinwart, 2001).

12

Tomoharu Iwata et al.

(a) Domain 1(b) Domain 2

Fig. 2 Example of two-domain synthetic data with five groups. Each point represents an object, and its
color shows the assigned group.

Theorem 1 Let (X , dX ) be a compact metric space. Then the Gaussian kernel Kγ(20) is characteristic to the set of all probability measures on (FP , γk ).
Let us intuitively explain the obtained result. Suppose that the joint distribution
Pr(µP , µQ ) and the product of their marginals Pr(µP ) and Pr(µQ ) have the same“mean” and “covariance” over FP × FQ , but differ in their higher order moments.
If we use polynomial kernels of order 2 as K and L, then HSIC (12) gives the value
zero. This is because in this case the kernel embeddings into HK ⊗ HL only distinguish the distributions on FP × FQ up to their covariance structures. As seen fromthis example, if the level-2 kernels are not characteristic, HSIC may not detect thedependency between µP and µQ even if there exists dependency in their higher ordermoments. On the other hand, we can measure any dependency between µP and µQ
using HSIC if we use characteristic kernels for K and L.
Thus Theorem 1 ensures that if we use the Gaussian kernels for K and L, theoretically we can detect any dependency between µP and µQ . Note, however, that we
can also use kernels that are not characteristic in practice, as we use the linear kernel(18) in Section 5.1 and 5.2. In such cases, HSIC takes a large value if there exists
strong linear dependency between µP and µQ .

5 Experiments
5.1 Synthetic data
To demonstrate the performance of the proposed method, we used synthetic twodomain data. The data consist of five groups for each domain, and objects in a groupare distributed according to a group-specific two-dimensional Gaussian distribution.
An example of the synthetic data is shown in Figure 2. The five Gaussians in thesecond domain are the rotated versions of Gaussians in the first domain. Two pairs ofGaussians (red-blue and purple-orange) share their means but have different covariance matrices.
We compared the proposed method, group kernelized sorting (GKS), with twoother kernelized sorting based methods: KS-mean and KS-object. With the KS-meanUnsupervised Group Matching

13

Table 1 Average matching accuracies and their standard errors with different level-1 kernels using thesynthetic data. Linear represents the linear kernel. Polynomial represents the polynomial kernel with degree two and constant one. Gaussian (γ = 1) represents the Gaussian kernel with width γ = 1. Gaussian(median) represents the Gaussian kernel with median trick.
Level-1 kernel
Accuracy

Linear
0.536 ± 0.029

Polynomial
0.524 ± 0.025

Gaussian (γ = 1)
0.680 ± 0.037

Gaussian (median)
0.946 ± 0.014

method, first the empirical mean for each group is calculated, and then convex kernelized sorting (Djuric et al, 2012) is performed using the empirical means as features
for each group. With the KS-object method, objects are first matched based on kernelized sorting using the original features. Next, we calculate a doubly-stochastic matrix
that represents correspondence probabilities between groups, which are estimated by
the number of matched objects between groups. Then, groups are matched using the
doubly-stochastic matrix by the Hungarian algorithm. For the proposed method, weused Gaussian kernels with median trick as level-1 kernels, and linear kernels as
level-2 kernels.
Figure 3 shows the matching accuracy and computational time with different
numbers of objects, which are averaged over 100 experiments. The accuracy with
the KS-mean was low because it did not use covariance information for each group.
The accuracy with the KS-object was slightly higher than that with the proposed
method (GKS) with this simple example. However, the computational time of theKS-object was much higher than those of the proposed method and KS-mean. The
computational time of the proposed method with 500 objects was 3.4 seconds. The
time complexity of the proposed method and KS-mean is cubic to the number ofgroups, while that of the KS-object is cubic to the number of objects, which is costly
since the number of groups is much smaller than the number of objects.
Table 1 shows the matching accuracy with different level-1 kernels using the synthetic data with 200 objects. For the level-2 kernel, we used the linear kernel. Since
the linear and polynomial kernels are not characteristic, their accuracies were lower
than the Gaussian kernel, which is characteristic. The performance of the Gaussian
kernel with median trick was better than the Gaussian kernel with fixed width γ = 1.
This result indicates that the kernel parameter setting is important, and the mediantrick works for the proposed method.

5.2 Splitted real data
We evaluated the proposed method by using four data sets with multiple class labels,
which were obtained from the LIBSVM data sets (Chang and Lin, 2011). The statistics of the four data sets are summarized in Table 2. The data sets with two domains
were generated by random splitting of the features as (Quadrianto et al, 2010; Djuric
et al, 2012) did in their experiments. Because the two domains do not share theirfeatures, similarities between objects in different domains cannot be calculated. We
assume that objects with the same class labels form a group. We used Gaussian level1 kernel and linear level-2 kernel for the proposed method, and Gaussian kernel for
the KS-mean method. The result is shown in Table 3, which are averaged over 100

14

Tomoharu Iwata et al.
1
0.9

GKS
KS−meanKS−objectaccuracy

0.8
0.7
0.6
0.5
0.4
0.3
0

100

200
300
#objects

400500(a) Matching accuracy
GKS
KS−meanKS−object

7000
6000

time

5000
4000
3000
2000
1000
0
0

100

200
300
#objects

400500(b) Computational time in seconds
Fig. 3 Average matching accuracy and computational time with different numbers of objects using thesynthetic data. The bars show their standard errors.
Table 2 Statistics of four splitted real data sets.
#objects#groups

Glass
214
6

Vowel
528
11

Satimage
4,435
6Letter
15,00026experiments. The KS-object method was not applicable to Satimage and Letter data
sets because they contain a large number of objects. The proposed method (GKS)
achieved higher matching accuracy than the KS-mean and KS-object methods in allof the data sets. This result indicates that the proposed method successfully finds
correspondence between groups by representing each group by its distribution using
kernel embedding.

5.3 Cross-lingual topic matching
For an application of unsupervised group matching, we employed the proposed method
for matching text document topic categories in different languages. We used 78 cat-Unsupervised Group Matching

15

Table 3 Average matching accuracies and their standard errors with four splitted real data sets. Values inbold typeface are statistically better at the 5% level from those in normal typeface as indicated by a paired
t-test.
MethodGKS
KS-meanKS-object
RandomGlass
0.442 ± 0.030
0.297 ± 0.024
0.245 ± 0.020
0.167 ± 0.000

Vowel
0.249 ± 0.017
0.167 ± 0.017
0.168 ± 0.013
0.091 ± 0.000

Satimage
0.993 ± 0.005
0.955 ± 0.015
N/A
0.167 ± 0.000

Letter
0.058 ± 0.005
0.049 ± 0.005
N/A
0.038 ± 0.000

Table 4 Matching accuracy with multilingual Wikipedia data. Values in bold typeface are better than theother.
GKS
KS-mean
Vocabulary-size

GKS
KS-mean
Vocabulary-size

EN-DE
0.603
0.192
0.051

EN-FI
0.321
0.269
0.051

EN-FR
0.564
0.346
0.051

EN-IT
0.782
0.564
0.064

EN-JA
0.410
0.231
0.051

DE-JA
0.526
0.167
0.026

FI-FR
0.564
0.449
0.026

FI-IT
0.526
0.308
0.077

FI-JA
0.449
0.064
0.051

FR-IT
0.577
0.679
0.090

DE-FI
0.385
0.295
0.090
FR-JA
0.513
0.487
0.038

DE-FR
0.538
0.397
0.051
IT-JA
0.564
0.256
0.103

DE-IT
0.615
0.385
0.051
Average
0.529
0.339
0.058

egories from Wikipedia in six languages: English (EN), German (DE), Finnish (FI),French (FR), Italian (IT) and Japanese (JA). Each category contains at least 100 documents, and a document can be associated with multiple categories. The numberof documents is 7,447 for each language. For the feature vector of documents, weused tf-idf (term frequency - inverse document frequency). The feature vectors werethen normalized to unit length in terms of ℓ2 norm. For the level-1 kernel, we useda polynomial kernel with degree two and zero constant, which is a common kernel
for the bag of words representation of text documents (Taira and Haruno, 1999). For
the level-2 kernel, we used a Gaussian kernel with median trick. We compared with
KS-mean and Vocabulary-size. The vocabulary-size method finds category matchingbased on the average vocabulary size per document, where it assumes that a groupwith large vocabulary in a language is likely to have large vocabulary in different
languages. We did not compare with KS-object because it is inapplicable to data witha large number of objects as shown above.
The matching accuracy between pairs of six languages is shown in Table 4. The
accuracy with random matching is 0.013. With 14 language pairs out of 15 pairs, theproposed method achieved the highest accuracy. In some language pairs, e.g. EN-DE
and DE-JA, improvement of the proposed method from the KS-mean was significant.
This implies that the empirical average of word counts is not enough for representing
document categories, and it is important to model the distribution of documents ineach category. Table 5 shows incorrectly matched categories estimated by the proposed method. Even though they were incorrect, the proposed method found correspondence between related categories across different languages, such as ‘Premier
League player’ and ‘Football (soccer) strikers’, ‘English-language films’ and ‘American films’, and ‘American stage actors’ and ‘New York actors’ in matching between
English and German.

16

Tomoharu Iwata et al.

Table 5 Examples of incorrectly matched categories in Wikipedia
EnglishDisambiguation
Premier League players
English-language films
2006 FIFA World Cup players
American films
American film directors
American stage actors
Greek mythology
2002 FIFA World Cup players
Emmy Award winners
UEFA Euro 2004 players
EnglishAmerican film actors
Disambiguation
American television actors
Hollywood Walk of Fame
Grammy Award winners
English-language films
American films
American film directors
La Liga footballers
American Jews
Greek mythology
EnglishDisambiguation
American television actors
Grammy Award winners
Least Concern species
English-language films
American films
Greek mythology
BAFTA winners (people)
2002 FIFA World Cup players
Emmy Award winners
Jewish actors
EnglishDisambiguation
English-language films
2006 FIFA World Cup players
American films
American film directors
Greek mythology
BAFTA winners (people)
Emmy Award winners
Jewish actors
2000s music groups
1990s music groups
EnglishDisambiguation
English-language films
2006 FIFA World Cup players
Serie A players
American films
American film directors
La Liga footballers
American Jews
American stage actors
Greek mythology
National flags

GermanGreek mythology
Football (soccer) strikers
American films
Premier League players
English-language films
American novelists
New York actors
20th century classical composers
Football (soccer) midfielders
Jewish actors
UEFA Euro 2000 players
FinnishAmerican television actors
2000s automobiles
California actors
American film directors
Disambiguation
Rock and Roll Hall of Fame inductees
20th century classical composers
BAFTA winners (people)
Football (soccer) midfielders
Hollywood Walk of Fame
Medicinal plants
French2000s automobiles
New York actors
Disambiguation
Grammy Award winners
American films
Companies listed on
the New York Stock Exchange
1990s music groups
American voice actors
Football (soccer) strikers
BAFTA winners (people)
American television actors
ItalianChemical elements
American films
Football (soccer) midfielders
Greek mythology
BAFTA winners (people)
English-language films
Emmy Award winners
Jewish actors
American film directors
1990s music groups
2000s music groups
Japanese
Knights of the Golden Fleece
American films
Football (soccer) midfielders
Italian footballers
American novelists
English-language films
Football (soccer) strikers
People from New York City
Jewish actors
Chemical elements
Disambiguation

Unsupervised Group Matching17

6 Conclusion
We proposed a method for unsupervised group matching, called group kernelized
sorting, for finding correspondence between groups in different domains. With theproposed method, a group is represented by a distribution, and distributions are matchedby maximizing the dependency. The dependency is measured by the Hilbert space information criterion, which can be calculated efficiently by mapping distributions into
reproducing kernel Hilbert spaces. In experiments, we confirmed that the proposed
method can perform much better than object matching based methods using synthetic
and real data sets. The high performance of the proposed method indicates the validity of modeling groups as distributions.
Our approach can be further improved in a number of ways. We can extend the
proposed method to semi-supervised setting, where a small number of correspondences across different domains are available. The correspondences can be either
between groups or between objects. The proposed method can also be extended todata with different number of groups across different domains. This can be achievedby using the rectangular doubly-stochastic matrix in (16), and adding dummy groups
with low connecting weights so as to discourage aligning with these dummy groupsin (17) as proposed in (Jagarlamudi et al, 2010).
Since we assume that two domains have common groups, a method to distinguish whether the given data contain common groups or not would be beneficial.
The doubly-stochastic matrix π ∗ obtained by (16) might be used for this. When there
are common groups, the doubly-stochastic matrix are likely to be clear as with similar to a permutation matrix. On the other hand, when there is no common groups,
the doubly-stochastic matrix would be unconcentrated, and the probability mass is
scattered in a wide variety of possible matchings.

A Proofs
A.1 Proof of Proposition 1
Proof First note that kp is well-defined since k is bounded. Then we have
KLIN (µPn , µPm ) := ⟨µPn , µPm ⟩H
k
⟨∫
⟩
∫
=
k(·, x)dp(x|xn ), k(·, x̃)dp(x̃|xm )
Hk

∫ ∫
=

k(x, x̃)dp(x|xn )dp(x̃|xm )= kp (xn , xm ).

(25)This completes the proof for kp . The proof for ℓq is obtained by a literal repetition of the arguments above.

A.2 Proof of Lemma 1
Proof It is known that the space of probabilities P with the weak topology is compact, provided that
(X , dX ) is compact (Thm. 6.4., (Parthasarathy, 1967)). Let (Pn )∞n=1 be a sequence in P such that Pn

18

Tomoharu Iwata et al.

converges weakly to P. Then,∫γk (µPn , µP )2 =∫k(x, x̃)dPn (x)dPn (x̃) − 2∫
k(x, x̃)dPn (x)dP(x̃) +k(x, x̃)dP(x)dP(x̃)

converges to zero by the definition of weak convergence, since k(x, x̃) is a bounded continuous function.
This implies that the mapping P 7→ µP is continuous, and thus its image FP is compact (Thm. 2.2.3., (Dudley, 2002)).

A.3 Proof of Theorem 1
Proof Thm. 2.2. of (Christmann and Steinwart, 2010) shows that Kγ is universal on FP , since the identity
map
id : (FP , γk ) → (Hk , ∥ · ∥Hk ),(26)

is clearly continuous and injective. Therefore, Kγ is characteristic on FP , since a universal kernel on acompact metric space is characteristic (Thm. 5, (Gretton et al, 2012a)).

References
Barnard K, Duygulu P, Forsyth D, De Freitas N, Blei DM, Jordan MI (2003) Matching words and pictures.
Journal of Machine Learning Research 3:1107–1135
Chang C, Lin C (2011) LIBSVM: a library for support vector machines. ACM Transactions on Intelligent
Systems and Technology 2(3):27
Christmann A, Steinwart I (2010) Universal kernels on non-standard input spaces. In: Advances in Neural
Information Processing Systems, pp 406–414
Coleman TF, Li Y (1996) An interior trust region approach for nonlinear minimization subject to bounds.
SIAM Journal on Optimization 6(2):418–445
Djuric N, Grbovic M, Vucetic S (2012) Convex kernelized sorting. In: AAAI Conference on Artificial
Intelligence
Doan A, Madhavan J, Domingos P, Halevy A (2004) Ontology matching: A machine learning approach.
In: Handbook on Ontologies, pp 385–403
Dudley RM (2002) Real Analysis and Probability. Cambridge University Press
Fukumizu K, Bach FR, Jordan MI (2004) Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces. Journal of Machine Learning Research 5:73–99
Fukumizu K, Gretton A, Sun X, Schölkopf B (2008) Kernel measures of conditional dependence. In:
Advances in Neural Information Processing Systems, pp 489–496
Gretton A, Bousquet O, Smola A, Schölkopf B (2005) Measuring statistical dependence with HilbertSchmidt norms. In: Algorithmic Learning Theory, vol 3734, pp 63–77
Gretton A, Borgwardt K, Rasch M, Schölkopf B, Smola A (2012a) A kernel two-sample test. Journal of
Machine Learning Research 13:723–773
Gretton A, Borgwardt KM, Rasch MJ, Schölkopf B, Smola A (2012b) A kernel two-sample test. Journalof Machine Learning Research 13(1):723–773
Haghighi A, Liang P, Berg-Kirkpatrick T, Klein D (2008) Learning bilingual lexicons from monolingual
corpora. In: Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp 771–779
Iwata T, Hirao T, Ueda N (2013) Unsupervised cluster matching via probabilistic latent variable models.
In: AAAI Conference on Artificial Intelligence, pp 445–451
Jagarlamudi J, Juarez S, Daumé III H (2010) Kernelized sorting for natural language processing. In: AAAI
Conference on Artificial Intelligence, pp 1020–1025
Kamahara J, Asakawa T, Shimojo S, Miyahara H (2005) A community-based recommendation system toreveal unexpected interests. In: International Multimedia Modelling Conference, pp 433–438
Klami A (2012) Variational Bayesian matching. In: Asian Conference on Machine Learning, pp 205–220

Unsupervised Group Matching

19

Kuhn HW (1955) The hungarian method for the assignment problem. Naval Research Logistics Quarterly
2(1–2):83–97
Li B, Yang Q, Xue X (2009) Transfer learning for collaborative filtering via a rating-matrix generativemodel. In: International Conference on Machine Learning, pp 617–624
Muandet K, Schölkopf B (2013) One-class support measure machines for group anomaly detection. In:
Conference on Uncertainty in Artificial Intelligence, pp 449–458
Muandet K, Fukumizu K, Dinuzzo F, Schölkopf B (2012) Learning from distributions via support measuremachines. In: Advances in Neural Information Processing Systems, pp 10–18
Parthasarathy KR (1967) Probability Measures on Metric Spaces. Academic Press
Quadrianto N, Smola AJ, Song L, Tuytelaars T (2010) Kernelized sorting. IEEE Transactions on PatternAnalysis and Machine Intelligence 32(10):1809–1821
Shvaiko P, Euzenat J (2013) Ontology matching: state of the art and future challenges. IEEE Transactions
on Knowledge and Data Engineering 25(1):158–176
Smola A, Gretton A, Song L, Schölkopf B (2007) A Hilbert space embedding for distributions. In: Algorithmic Learning Theory, pp 13–31
Socher R, Fei-Fei L (2010) Connecting modalities: Semi-supervised segmentation and annotation of images using unaligned text corpora. In: IEEE Conference on Computer Vision and Pattern Recognition,
pp 966–973
Song L, Smola A, Gretton A, Bedo J, Borgwardt K (2012) Feature selection via dependence maximization.
Journal of Machine Learning Research 13(1):1393–1434
Sriperumbudur BK, Fukumizu K, Gretton A, Lanckriet GR, Schölkopf B (2009) Kernel choice and classifiability for RKHS embeddings of probability distributions. In: Advances in Neural Information Processing Systems, pp 1750–1758
Sriperumbudur BK, Gretton A, Fukumizu K, Schölkopf B, Lanckriet GR (2010) Hilbert space embeddings
and metrics on probability measures. Journal of Machine Learning Research 11:1517–1561
Steinwart I (2001) On the influence of the kernel on the consistency of support vector machines. Journalof Machine Learning Research 2:67–93
Taira H, Haruno M (1999) Feature selection in SVM text categorization. In: National Conference on Artificial Intelligence, pp 480–486
Terada A, Sese J (2012) Global alignment of protein-protein interaction networks for analyzing evolutionary changes of network frameworks. In: Proceedings of 4th International Conference on Bioinformatics
and Computational Biology, pp 196–201
Tripathi A, Klami A, Virpioja S (2010) Bilingual sentence matching using kernel CCA. In: IEEE International Workshop on Machine Learning for Signal Processing, pp 130–135
Yamada M, Sugiyama M (2011) Cross-domain object matching with model selection. In: International
Conference on Artificial Intelligence and Statistics, pp 807–815