IEICE Transactions on Information and Systems,
vol.E97-D, no.4, pp.968–971, 2014.

1

Computationally Eﬃcient Estimation of Squared-loss
Mutual Information with Multiplicative Kernel Models
Tomoya Sakai
Tokyo Institute of Technology, Japan.
sakai@sg.cs.titech.ac.jp
Masashi Sugiyama
Tokyo Institute of Technology, Japan.
sugi@cs.titech.ac.jp
http://sugiyama-www.cs.titech.ac.jp/˜sugi

Abstract
Squared-loss mutual information (SMI) is a robust measure of the statistical dependence between random variables. The sample-based SMI approximator called
least-squares mutual information (LSMI) was demonstrated to be useful in performing various machine learning tasks such as dimension reduction, clustering,and causal inference. The original LSMI approximates the pointwise mutual information by using the kernel model, which is a linear combination of kernel basis
functions located on paired data samples. Although LSMI was proved to achieve
the optimal approximation accuracy asymptotically, its approximation capability islimited when the sample size is small due to an insuﬃcient number of kernel basis
functions. Increasing the number of kernel basis functions can mitigate this weakness, but a naive implementation of this idea significantly increases the computation
costs. In this article, we show that the computational complexity of LSMI with themultiplicative kernel model, which locates kernel basis functions on unpaired data
samples and thus the number of kernel basis functions is the sample size squared, isthe same as that for the plain kernel model. We experimentally demonstrate that
LSMI with the multiplicative kernel model is more accurate than that with plain
kernel models in small sample cases, with only mild increase in computation time.
Keywords
squared-loss mutual information, least-squares mutual information, density ratio
estimation, multiplicative kernel models, independence test.

LSMI with Multiplicative Kernel Models

12Introduction

Squared-loss mutual information (SMI) [1] between random variables X and Y is definedas the Pearson divergence from the joint density p(x, y) to the product of marginals
p(x)p(y):1
SMI(X, Y ) :=2(∫∫p(x)p(y)p(x, y)−1p(x)p(y)

)2
dxdy.

SMI is always non-negative and takes zero if and only if X and Y are statistically independent. Thus, SMI can be used as a measure of the statistical dependence between Xand Y .
When SMI is used in practice, the densities p(x, y), p(x), and p(y) are often unknown, and SMI is approximately computed using paired samples {(xi , yi )}ni=1 drawn
independently from density p(x, y). A naive way to approximate SMI is to estimate thedensities p(x, y), p(x), and p(y) from the samples and plug the estimated densities into
the definition of SMI.
However, this density estimation approach tends to perform poorly due to the division by estimated densities which considerably magnifies the estimation error. To
overcome this problem, the SMI approximator called least-squares mutual informationp(x,y)(LSMI) [1] directly estimates the density ratio p(x)p(y)without separately estimating eachdensity. LSMI was shown to possess excellent properties, e.g., it achieves the optimal
non-parametric convergence rate, it is numerically stable, its solution can be obtained analytically, and it works well in practice [2]. So far, LSMI has been successfully applied toperforming various machine learning tasks such as dimension reduction, clustering, object
matching, and causal inference [3].
p(x,y)The original LSMI approximates the density ratio p(x)p(y)using the kernel model,
which is a linear combination of kernel basis functions located on paired data samples{(xi , yi )}ni=1 . Although LSMI with the kernel model was proved to achieve the optimal
approximation accuracy asymptotically, its approximation capability is limited when thesample size is small because of too few kernel basis functions. A naive way to cope withthis problem is to increase the number of basis functions, but this significantly increases
the computation time.
In this paper, we propose to use the multiplicative kernel model in LSMI, which locateskernel basis functions on unpaired data samples {(xi , yj )}ni,j=1 (see Fig.1). Note that the
number of kernel basis functions in the multiplicative kernel model is n2 . Our criticaltheoretical contribution in this paper is that the computational complexity of LSMI withthe multiplicative kernel model is proved to be the same order as that with the plainkernel model. Through experiments, we demonstrate that LSMI with the multiplicative
kernel model is more accurate than that with the plain kernel model in small sample
cases, with only mild increase in computation time.

LSMI with Multiplicative Kernel Models

3

Figure 1: Kernel centers in the plain kernel model and the multiplicative kernel model.
The plain kernel model locates n kernels at paired samples {(xi , yi )}ni=1 (filled circles),while the multiplicative kernel model locates n2 kernels at unpaired samples {(xi , yj )}ni,j=1(filled and unfilled circles).

2Least-Squares Mutual Information

In this section, we review the sample-based SMI approximator called least-squares mutualinformation (LSMI) [1].
Basic Idea: Suppose that we are given a set of paired samples {(xi , yi )}ni=1 drawn
independently from the joint distribution with density p(x, y). The key idea of LSMI isp(x,y)
without going through density
to directly estimate the density ratio r(x, y) := p(x)p(y)estimation of p(x, y), p(x), and p(y).
Let g(x, y) be a model of the density ratio. We learn the model g so that the following
squared-error J is minimized:∫∫ ()2
1
J(g) :=
g(x, y) − r(x, y) p(x)p(y)dxdy
2∫∫1g(x, y)2 p(x)p(y)dxdy=2∫∫−g(x, y)p(x, y)dxdy + C,
where C is a constant that does not depend on g. By approximating the expectations
contained in J by the empirical averages, including a regularization functional R(g), andignoring the irrelevant constant, the LSMI optimization problem is formulated as follows:][nn∑
11 ∑g(xi , yj )2−g(xi , yi )+λR(g) ,gb := argmin
22nngi,j=1i=1where λ ≥ 0 is the regularization parameter.

LSMI with Multiplicative Kernel Models

4

Based on another expression of SMI,∫∫
1r(x, y)2 p(x)p(y)dxdySMI(X, Y ) = −2∫∫
1+r(x, y)p(x, y)dxdy − ,2

the SMI approximator called LSMI is given as follows:
nn1 ∑1∑
12LSMI := − 2gb(xi , yj ) +gb(xi , yi ) − .
2n i,j=1n i=12

LSMI with Linear Model: As a density ratio model, let us use the linear-in-parametermodel:g(x, y) =b∑

θℓ ϕℓ (x, y) = θ ⊤ ϕ(x, y),ℓ=1

where b denotes the number of parameters, θ = (θ1 , . . . , θb )⊤ is the parameter vector, andϕ(x, y) = (ϕ1 (x, y), . . . , ϕb (x, y))⊤ are the basis function vector.
For the squared regularization functional R(g) = θ ⊤ θ/2, the LSMI optimization criterion is expressed as][λ1⊤⊤⊤b+ θ θ ,b −θ hθ Gθθb := argmin
22θ∈Rbb are defined byb and hwhere Gnn
1 ∑1∑
⊤ bb
G := 2ϕ(xi , yj )ϕ(xi , yj ) , h :=ϕ(xi , yi ).
n i,j=1n i=1By taking the derivative of the above objective function with respect to the parameter
vector θ, the following system of linear equations is obtained:bb θb + λθb = h.
G(1)b where Ib is theb + λIb )−1 h,This linear system can be solved analytically as θb = (Gb-dimensional identity matrix. Finally, the density ratio estimator gb(x, y) is given bygb(x, y) = θb⊤ ϕ(x, y), and thus LSMI is expressed as
1b − 1.
b θb + θb⊤ h
LSMI = − θb⊤ G
22
LSMI with Kernel Models: As an example of basis functions ϕ, let us use the kernelmodel :n∑g(x, y) :=θi K(x, xi )L(y, yi ) = θ ⊤ [k(x) ◦ l(y)] ,i=1

LSMI with Multiplicative Kernel Models

5

where K(x, x′ ) and L(y, y ′ ) are kernel functions for x and y, θ = (θ1 , . . . , θn )⊤ is a parameter vector, k(x) = (K(x, x1 ), . . . , K(x, xn ))⊤ and l(y) = (L(y, y1 ), . . . , L(y, yn ))⊤are empirical kernel vectors, and ◦ denotes the Hadamard product.
b are expressed asb and h
For the kernel model, Gb = 1 (K ◦ L)⊤ 1n ,b = 1 (K ⊤ K) ◦ (L⊤ L), hG
2nnwhere Ki,j = K(xi , xj ), Li,j = L(yi , yj ), and 1n is the n-dimensional vector with all ones.
Thus, the computational complexity for computing LSMI for the kernel model is O(n3 ).
Under some technical conditions, LSMI with the kernel model was proved to achievethe optimal approximation accuracy asymptotically [2]. However, its approximation capability is limited when the sample size is small, partially because the number of kernelbasis functions is too small. This drawback may be overcome by increasing the numberof basis functions, but this in turn significantly increases the computation time.

3LSMI with Multiplicative Kernel Models

In this section, we propose to use the multiplicative kernel model in LSMI, which locateskernel basis functions at unpaired data samples {(xi , yj )}ni,j=1 . As illustrated in Fig.1, themultiplicative kernel model contains n2 kernel basis functions. This allows us to utilize
the Kronecker structure to significantly reduce the computational cost.
The multiplicative kernel model is expressed asg(x, y) :=n∑

θi,j K(x, xi )L(y, yj )i,j=1

= vec (Θ)⊤ [(1n ⊗ k(x)) ◦ (l(y) ⊗ 1n )] ,where Θ is the n × n parameter matrix with Θi,j = θi,j , vec (·) denotes the vectorizationof a matrix, and ⊗ denotes the Kronecker product.
b are expressed asb and hFor the above multiplicative kernel model, G
b = vec(H),b=Le ⊗ K,
f hfGe = 1 L⊤ L, K
f = 1 K ⊤ K, and H
f = 1 K ⊤ L. The Kronecker structure of Gb iswhere Lnnn
brought by the fact that kernel basis functions share the same centers in the multiplicativeb satisfies
kernel model. Then, Eq.(1) yields that the solution ΘfΘ
bLe + λΘb = H.
fKThis is called the discrete Sylvester equation, and can be solved with computational complexity O(n3 ) [4]. Finally, LSMI with the multiplicative kernel model is expressed as
1 b ⊤fb e
f − 1.
b ⊤ H)K ΘL) + tr(ΘLSMI = − tr(Θ22(2)LSMI with Multiplicative Kernel Models

6The computational complexity for calculating Eq.(2) is O(n3 ), and therefore the overall
computational complexity of LSMI with the multiplicative kernel model is the same asthat with the plain kernel model, even though the number of kernel basis functions isincreased from n to n2 .

4Experiments

In this section, we experimentally evaluate the performance of LSMI with the plain kernel
model and the multiplicative kernel model.
For regression, we use the Gaussian kernel with the common bandwidth for K(x, x′ )and L(y, y ′ ) after element-wise standardization of x and y. For classification, we use thedelta kernel for L(y, y ′ ). The Gaussian width and regularization parameter are determined by 5-fold cross-validation.
Numerical Illustration: First, we use the following toy datasets with onedimensional x and y:(A) Dependent: x and y are dependent asp(x, y) = 21 N (z; 12 , I2 ) + 12 N (z; −12 , I2 ) ,where z = (x, y)⊤ and 12 = (1, 1)⊤ . N (z; µ, Σ) denotes the multi-dimensional
normal density with mean vector µ and covariance matrix Σ.
(B) Independent: x and y are independent as p(x, y) = 1/4 if −1 < x, y < 1 and zerootherwise.
Fig.2(a) depicts kernel centers of the plain kernel model and the multiplicative kernel
model for 50 samples in the dependent case (A). Fig.2(b) depicts the true density-ratiop(x,y)
function p(x)p(y)and its estimates with the plain kernel model and the multiplicative kernel
model, respectively, for 50 samples. The graphs show that the function obtained with themultiplicative kernel model approximates the true density-ratio function better than thatobtained with the plain kernel model at around the origin.
More qualitatively, Figs.2(c) and 2(d) show the mean and standard error of the LSMI
values and the computation time, respectively, over 1000 runs. ‘naive’ denotes the naive
implementation of the multiplicative kernel model (i.e., solving the system of n2 linearequations). The graphs show that LSMI with the multiplicative kernel model is moreaccurate than that with the plain kernel model. In terms of the computation time, theeﬃcient implementation of LSMI with the multiplicative kernel model is shown to bemuch faster than its naive implementation and is only slightly slower than LSMI withthe plain kernel model. Therefore, given a certain approximation level, LSMI with themultiplicative kernel model is computationally more eﬃcient than that with the plain
kernel model.
The results in the independent case (B) are plotted in Fig.3, again showing that LSMI
with the multiplicative kernel model is more accurate than that with the plain kernel

74433221100yyLSMI with Multiplicative Kernel Models−1−1−2−2−3−3−4−4−20x

2−4−44−20x24(a) Kernel centers of the plain (left) and multiplicative (right) kernel models
41.8

3

1.6
1.4

2

1.2

1
y

1
0
0.8
−1

0.6

−2

0.4

−3

0.2

−4−4−20x

4

2

2.5

342

3

2

1.5

2

2
1.5

0

1−1

1

10

y1
y4

0.5

−1

0.5

−2

0−20−3−4−4−20x

2−3−0.5−4−4

4−20x24(b) True density ratio (top) and its estimates with plain (left)
and multiplicative (right) kernel models
0.21

Estimated SMI

0.18

0.16

0.14
plain
multiplicativetruth

0.120.1

Computation time [sec.]

10010−110

plain
multiplicativenaive
−2050

100
150200
Number of samples

250(c) SMI values

300

10050

100
150200
Number of samples

250

300(d) Computation time

Figure 2: Experimental results for the dependent dataset. The best method and comparable ones according to the t-test at the significance level 1% are specified by ‘◦’.LSMI with Multiplicative Kernel Models

80.08110Computation time [sec.]plain
multiplicative

0.07

Estimated SMI

0.06
0.05
0.04
0.03
0.02

010−110plain
multiplicative
naive

0.01
0−2050100150200
Number of samples

250300100(a) SMI values

50100150200
Number of samples

250300(b) Computation time

Figure 3: Experimental results for the independent dataset. The best method and comparable ones according to the t-test at the significance level 1% are specified by ‘◦’.
11
0.9

0.8

plain (dep.)
multiplicative (dep.)
plain (ind.)multiplicative (ind.)

0.6

0.8
0.7
0.60.50.40.4
0.3

0.2

0.2
00204060
Number of samples

80

100(a) Ionosphere (d = 34, c = 2)
10.1
0

plain (dep.)
multiplicative (dep.)
plain (ind.)multiplicative (ind.)
204060
Number of samples

80

100(b) Liver-disorders (d = 6, c =2)
1

0.8

0.8
plain (dep.)
multiplicative (dep.)
plain (ind.)multiplicative (ind.)

0.6

0.6

0.4

0.4

0.2

0.2

00204060
Number of samples

80

plain (dep.)
multiplicative (dep.)
plain (ind.)multiplicative (ind.)100(c) Shuttle (d = 9, c = 7)00204060Number of samples

80100(d) Vehicle (d = 18, c = 4)

Figure 4: Experimental results for the benchmark datasets. Frequency of accepting thenull hypothesis over 100 runs under the significance level 0.05 is depicted. d and c denotethe input dimensionality and the number of classes of the dataset, respectively.
model. Similarly, the eﬃcient implementation of LSMI with the multiplicative kernel
model is much faster than its naive implementation and is only slightly slower than LSMI
with the plain kernel model.
Benchmark Datasets: Finally, we apply LSMI to independence testing in the frame-

LSMI with Multiplicative Kernel Models

9work of the permutation test [5].
We employ 4 real-world classification datasets taken from the UCI repository available from http://archive.ics.uci.edu/ml/. We use the original dataset {(xi , yi )}ni=1(where x and y are dependent) to evaluate the type-II error (i.e., whether a statistical
test can reject the wrong null hypothesis that x and y are independent). We also use its
randomly shuﬄed dataset {(xi , yei )}ni=1 (where x and y are independent) for evaluating
the type-I error (i.e., whether a statistical test can accept the correct null hypothesis thatx and y are independent).
Fig.4 shows the type-I and type-II errors for 100 runs under the significance level 0.05.
The graphs show that the multiplicative kernel model tends to provide lower type-II errors
than the plain kernel model, while their type-I errors are comparable.

5Conclusions

In this paper, we proposed to use the multiplicative kernel model for approximatingsquared-loss mutual information. The key contribution of the proposal is that, eventhough the number of parameters is squared, its computational complexity does not exceedthat of the original method with the plain kernel model. Through numerical experiments,
we showed that the proposed method achieves lower type-II errors and comparable type-I
errors in independence testing.
This work was supported by KAKENHI 23120004 and AOARD.

References[1] T. Suzuki, M. Sugiyama, T. Kanamori, and J. Sese, “Mutual information estimation
reveals global associations between stimuli and biological processes,” BMC Bioinformatics, vol.10, pp.S52:1–S52:12, 2009.
[2] M. Sugiyama, T. Suzuki, and T. Kanamori, Density Ratio Estimation in Machine
Learning, Cambridge University Press, Cambridge, UK, 2012.
[3] M. Sugiyama, “Machine learning with squared-loss mutual information,” Entropy,vol.15, pp.80–112, 2013.
[4] V. Sima, Algorithms for Linear-Quadratic Optimization, Marcel Dekker, New York,NY, USA, 1996.
[5] T. Suzuki and M. Sugiyama, “Least-squares independence test,” IEICE Transactions
on Information and Systems, vol.E94-D, pp.1333–1336, 2011.