2010 International Conference on Pattern Recognition

SemiCCA: Efﬁcient semi-supervised learning of
canonical correlations
Akisato Kimura∗ , Hirokazu Kameoka∗ , Masashi Sugiyama† , Takuho Nakano‡∗ ,Eisaku Maeda∗ , Hitoshi Sakano∗ and Katsuhiko Ishiguro∗∗ NTT Communication Science Laboratories, Keihanna Science City, Kyoto, Japan.

E-mail: akisato@ieee.org
E-mail: sugi@cs.titech.ac.jp
E-mail: t-nakano@hil.t.u-tokyo.ac.jp† Graduate School of Information Science and Engineering, Tokyo Institute of Technology‡ Graduate School of Information Science and Technology, the University of Tokyo

SemiCCA is a generalized (and intuitively comprehensible)
variant of semi-supervised CCA with Tikhonov regularization.

Abstract—Canonical correlation analysis (CCA) is a powerfultool for analyzing multi-dimensional paired data. However, CCA
tends to perform poorly when the number of paired samples islimited, which is often the case in practice. To cope with thisproblem, we propose a semi-supervised variant of CCA named“SemiCCA” that allows us to incorporate additional unpaired
samples for mitigating overﬁttng. The proposed method smoothly
bridges the eigenvalue problems of CCA and principal component
analysis (PCA), and thus its solution can be computed efﬁciently
just by solving a single (generalized) eigenvalue problem as theoriginal CCA. Preliminary experiments with artiﬁcially generated
samples and PASCAL VOC data sets demonstrate the effectiveness of the proposed method.
Index Terms—Canonical correlation analysis, semi-supervised
learning, generalized eigenproblem, automatic image annotation

II. C ANONICAL C ORRELATION A NALYSIS (CCA)
Consider a set of paired samples of size N , X (L) =(L)= {y n }N{xn }Nn=1 and Y
n=1 , where each sample xn (resp.
y n ) is represented as a vector with dimension dx (resp. dy ).
Without loss of generality, we assume that X (L) and Y (L) areboth centered, which can always be achieved by subtracting
the sample means from each sample. CCA is a method ofﬁnding bases wx and wy for X (L) and Y (L) such that theircorrelation is maximized asmax (wx ,wy )I. I NTRODUCTION

(1)

N
(L)
(L)
(L)

where S (L)xx = 1/N
n=1 xn xn , and S yy , S xy and S yx
are deﬁned similarly. The solution (wx , wy ) is given as thesolution of the following generalized eigenvalue problem:

 
 

(L)
0
S (L)
S
0
wx
w
x
xy
xx
=λ
. (2)
(L)
w
wy
0
S
S (L)
0
y
yy
yx

Analyzing high-dimensional co-occurring data (x, y) is an
important challenge in machine learning and pattern recognition communities, e.g., in the context of automatic audio
tagging [1] and image annotation retrieval1 [2]. Canonicalcorrelation analysis (CCA) [3] is a classical but still powerful
method for analyzing multivariate paired samples. CCA ﬁnds
projection directions wx and wy so that correlation between

projected samples w
x x and w y y is maximized.
However, the performance of CCA tends to be degradedwhen the number of paired samples (x, y) is limited, where
we often encounter in various real-world applications. Evenin such cases, a large number of additional unpaired samples(i.e., x-only samples and y-only samples) are often available.
To utilize such additional unpaired samples, several semisupervised [4] extensions of (mainly kernelized) CCA havebeen proposed, e.g., based on Tikhonov regularization [5] andgraph-Laplacian regularization [6].
In this paper, we propose a yet another semi-supervised
variant of CCA called SemiCCA. SemiCCA utilizes additional
unpaired samples by smoothly bridging CCA and principal
component analysis (PCA). More speciﬁcally, the eigenvalue
problems of CCA and PCA are combined using a trade-off
parameter. Thus the solution of SemiCCA can still be obtained
just by solving the combined eigenvalue problem, which isthe same computational complexity as the original CCA.

Taking the top dz ≤ min(dx , dy ) generalized eigenvectors as
row vectors, we obtain dz -dimensional mappings (W x , W y ).
III. T HE PROPOSED METHOD : S EMI CCA
A. Concept
When the number of paired samples is small, CCA tends
to overﬁt the given paired samples. Here, let us considerx
the situation where unpaired samples X (U ) = {xn }N
n=N +1
Ny
(U )
2
and Y
= {y n }n=N +1 are additionally provided , where
X (U ) and Y (U ) might be independently generated. Since
the original CCA cannot directly incorporate such unpaired
samples, we propose a novel method named SemiCCA that can
avoid overﬁtting by utilizing the additional unpaired samples.
Let us explain the idea of SemiCCA using an illustrative
two-dimensional data set depicted in Fig. 1, where paired(resp. unpaired) samples are plotted with white (resp. redand blue). When only the paired samples (X (L) , Y (L) ) are
2 In the context of automatic image annotation, X (U ) only exists, whereas
Y (U ) is empty. However, the proposed method SemiCCA can be plausible
even in the case of the presence of X(U ) and/or Y (U )1 In such cases, x corresponds to an audio/image feature, and y corresponds

to a feature derived from the associated text information.

1051-4651/10 $26.00 © 2010 IEEE
DOI 10.1109/ICPR.2010.719(L)w
x S xy w y,(L) S (L) w
w
S
w
w
x
y
x xx
y yy

2925
2937
2933

Fig. 1.

Effects of unpaired samples in SemiCCA

The trade-off parameters control the trade-off between CCA
and PCA. Namely, when β = 1, Eq. (3) is reduced to the
CCA eigenvalue problem Eq. (2), while when β = 0, Eq. (3)is reduced to the PCA eigenvalue problem, under the assumption that X = (X (L) , X (U ) ) and Y = (Y (L) , Y (U ) ) are
uncorrelated. In general, SemiCCA with a trade-off parameter0 < β < 1 inherits the properties of both CCA and PCA sothat the global structure in each domain and the co-occurrence
information of paired samples are smoothly controlled.
We focused on the case where two sets of samples are given,
but SemiCCA can be easily extended to multiple data setsby considering correlations over all pairs of samples [6], [8].
Also, the proposed method can be easily extended to nonlinear or non-vectorial domains by introducing the kernel trick[6]. From the formulation of kernelized SemiCCA, we canprove that semi-supervised CCA with Tikhonov regularization
presented in [6] is a special case of SemiCCA, where someelements of kernel matrices are forced to be 0. We omit thedetails for this issue due to the limited space.
IV. E XPERIMENT WITH ARTIFICIAL DATA

used, poor projection directions may be obtained by CCA due
to overﬁttng. In contrast, unpaired samples reveal the global
structure of whole the samples in each domain. Note once abasis in one sample space is rectiﬁed, the corresponding basesin the other sample space is also rectiﬁed so that correlations
between two bases are maximized.
B. Deﬁnition
Motivated by the above illustration, we propose to combine
CCA with principal component analysis (PCA) for utilizing
unpaired samples. There are various possibilities to combine
CCA and PCA. Here, we combine the eigenvalue problemsof CCA and PCA since this allows us to compute the combined solution efﬁciently3 . More speciﬁcally, the solution of
SemiCCA is given by the leading generalized eigenvectors of
the following generalized eigenvalue problem:
 
 
wx
wx
= λC
,
(3)
B
wy
wy




0
S (L)
0
S xx
xy
,
+ (1 − βB )B = βB
0
S yy
S (L)
0
yx




0
S (L)
I Dx
0
xx
C = βC+ (1 − βC )
,
0
I Dy
0
S (L)
yy
Nx
xn x
S xx = n=1
n /Nx ,Ny
S yy = n=1 y n y n /Ny ,I d is the d × d identity matrix, and βB and βC are constants
named trade-off parameters taking a value in [0, 1]. From now
on, we focus on using the single shared trade-off parameterβ instead of the individual parameters βB and βC since theindividual parameters makes the parameter choice laborious.

We ﬁrst evaluated the performance of the proposed method
using the artiﬁcial data set created as follows: We considered a
Gaussian pLSA model, where the latent random variable (corresponding to a canonical variable in the framework of CCA)
is denoted by Z and observations are denoted by X and Y . Wezdrew samples {z i }N
i=1 from N (0, I dz ) of dimension dz = 10
and number of samples Nz = 10000, where N (x, ΣX ) is a
Gaussian probability density function (PDF) with mean x andcovariance matrix ΣX . The means and covariance matricesof the conditional (Gaussian) densities p(X|Z) and p(Y |Z)
were determined randomly for each trial. More speciﬁcally,
we randomly generated each component of transformation
matrices T x and T y and means x and y following N (0, 1).
zThen complete paired samples {(xi , y i )}N
i=1 were created as
xi = T x z i + x + δ x,i ,y i = T y z i + y + δ y,i ,δ x,i ∼ N (0, ΣX|Z ),δ y,i ∼ N (0, ΣY |Z ),where each component of ΣX|Z and ΣY |Z was generated
from the folded standard normal distribution. The dimensionsof the samples are set to dx = 15 and dy = 20.
z
We removed several samples from {y i }N
i=1 by a simple
linear discrimination.
As a discriminant function, we useddyad (yd − y d ) − θ, where a = (a1 , . . . , ady )
f (y) = d=1
is a coefﬁcient vector satisfying a = 1, and θ is thediscrimination threshold such that the larger θ we set, themore samples removed. A sample (xi , y i ) was kept paired if
f (y i ) > 0, and y i was removed otherwise.
We compare the proposed SemiCCA with the original CCA.
We evaluated the performance of (Semi)CCA by the weighted
sum of cosine distances deﬁned as follows:C(W x , W ∗x , Λ∗ ) =3 This idea is motivated by [7], which combines a variant of Fisher
discriminant analysis with PCA by blending the eigenvalue problems.

r

i=1

2934
2938
2926

λ∗i

∗
w
x,i w x,i,
wx,i  · w∗x,i Fig. 2.

Average evaluation score for artiﬁcial data

Fig. 4.

Histogram of trade-off parameters taking the highest score.

V. A PPLICATIONS TO AUTOMATIC IMAGE ANNOTATION
A. Method

Fig. 3.

Average trade-off parameter taking the highest score.

where W ∗x = (w∗x,1 , w∗x,2 , . . . , w∗x,dz ) and Λ∗ =diag(λ∗1 , λ∗2 , . . . , λ∗dz ) are the “true” eigenvectors and eigenvalues. We took an oracle setting for selecting the trade-off
parameter β. Namely, we adopted the trade-off parameter βmarking the highest score for each trial.
Figure 2 shows the evaluation scores averaged over 10000
independent trials for several discrimination thresholds θ andalso shows the average number of paired samples for eachdiscrimination threshold. The results indicate that SemiCCA
tends to outperform the ordinary CCA; it is note worthy thateven when the number of unpaired samples is not so large,
SemiCCA performs better than the original CCA.
Figure 3 shows the trade-off parameter taking the highest
score averaged over all the trials, and Figure 4 depicts thehistogram of the best trade-off parameters. The results imply
that the best trade-off parameters have a concave proﬁle withrespect to the number of paired samples. Since standard errorsof the best trade-off parameters were relatively small, we
expect to obtain similar results not only for oracle settings but
also for cross validation scenarios. The results also indicatethat the best trade-off parameters were usually close to 1, i.e.,
the effect of PCA is only mildly incorporated. Nevertheless,the performance is much improved, as shown in Figure 2.

We describe the method of automatic image annotation
based on the one by Nakayama et al. [9], [10] with the helpof SemiCCA.
First of all, feature vectors are extracted from images andassociated text labels. Each text label is composed of text
words selected from a word set given in advance. We utilizex
Bag of Features (BoF) as image features X = {xn }Nn=1 ,where SURF [11] is used for key-point detection and descriptor extraction, and binary word vectors Y = {y n }N
n=1
as text features. Note that {xn }N
n=1 are labeled images, whilex{xn }Nn=N +1 are unlabeled.
Next, a topic model is constructed from feature vectors(X, Y ) with the help of SemiCCA. The ﬁrst step is togenerate latent variables Z = {z n }N
n=1 with SemiCCA. Morespeciﬁcally, a function fx : Rdx → Rdz is derived from X as
training samples with SemiCCA as fx (x) = Λ1/2 W x x, andlatent variables Z are generated from X with fx . The second
step is to set up a topic model. The topic model is describedby the following equation:Np(x, y) =n=1 p(x|z n )p(y|z n )/N ,p(x|z n ) ∝ exp(−fx (x) − z n /2γ 2 ),p(y|z n )p(yd = 1|z n )p(yd = 0|z n )dy=d=1 p(yd |z n ),= μδ(1 − yn,d ) + (1 − μ)Nd /N,= 1 − p(yd = 0|z n ),where yn,d is the d-th element of y n , Nd is the number ofthe images containing the d-th word in labeled samples, δ(·)
is Dirac delta, an operator ∝ stands for proportion, and γ andμ are constants.
Once the model estimation has been ﬁnished, we can
execute automatic image annotation through maximum a posteriori (MAP) estimation. More speciﬁcally, the text feature yof the most probable text label w can be derived by using animage feature x(g) extracted from a given image, as follows:
y

2935
2939
2927

=

argmax p(y|x(g) )y∈[0,1]dy(4)case of β = 1.0, annotation with topic models learned by
SemiCCA would achieve at least as the same accuracy as theone by the original CCA. Fig. 6 indicates that a topic modelbuild with the help of SemiCCA outperformed that of theoriginal CCA. The total performance seemed to be poor for
VOC participants, however, it should be noted again that weremoved all the bounding boxes and only utilized class labels.
VI. C ONCLUDING R EMARKS

Fig. 5.

Fig. 6.

In this paper, we proposed a new semi-supervised variant of CCA that we named SemiCCA. Unlike the previous
semi-supervised CCA, our formulation is quite simple andalso intuitively comprehensive. Namely, SemiCCA smoothly
bridges CCA with paired samples and PCA with paired andunpaired samples by a trade-off parameter. We evaluatedits performance by using artiﬁcially generated samples andPASCAL VOC data set, and revealed the effectiveness of
SemiCCA against the original CCA.
Our future work includes some comparison of SemiCCA
with other semi-supervised variants of CCA, especially basedon Tikhonov regulirization [5], [6], mutually complementary integration of SemiCCA into some methods of semisupervised learning based on graph Laplacian reguralization,
and applications to various challenging real-world problems
e.g. automatic music/image/video annotation and retrieval,and multi-model event correlation analysis for audio-video
synchronization and audio-visual speech recognition.

Example images in PASCAL VOC data set

R EFERENCES

Experiment results for automatic image annotation

N=argmaxy∈[0,1]dy[1] J. S. Downie, “The music information retrieval evaluation exchange(2005–2007): A window into music information retrieval research,”
Acoustical Science and Technology, vol. 29, no. 4, pp. 247–255, 2008.
[2] M. Everingham et al., “The PASCAL Visual Object Classes Challenge
2009 (VOC2009) Results,” http://www.pascal-network.org/challenges/
VOC/voc2009/workshop/index.html.
[3] H. Hotelling, “Analysis of a complex of statistical variables into
principal components,” J. Educ. Psych., vol. 24, 1933.
[4] O. Chapelle et al. Semi-Supervised Learning, MIT Press, 2006.
[5] D. R. Hardoon et al. “Canonical correlation analysis: An overview
with application to learning methods,” Neural Computation, vol. 16,
no. 12, pp. 2639–2664, 2004.
[6] M. B. Blaschko et al. “Semi-supervised laplacian regularization ofkernel canonical correlation analysis,” in Proc. ECML PKDD ’08,
Berlin, Heidelberg, 2008, pp. 133–145.
[7] M. Sugiyama et al. “Semi-supervised local Fisher discriminant analysis
for dimensionality reduction,” Machine Learning, vol. 78, no. 1–2, pp.
35–61, 2010.
[8] H. Yanai and S. Puntanen, “Partial canonical correlation associated with
the inverse and some generalized inverse of a partitioned dispersion
matrix,” in Proc. the third Paciﬁc Area Statistical Conference on
Statistical Sciences and Data Analysis, pp. 253–264, 1993.
[9] H. Nayayama et al. “High-performance image annotation and retrieval
for weakly labeled images,” in Proc. PCM, pp. 601–610. 2008,[10] T. Harada et al. “Image annotation retrieval based on efﬁcient learningof contextual latent space,” in Proc. ICME, 2009.
[11] H. Bay et al. “Speeded-up robust features (surf),” CVIU, vol. 110, no.
3, pp.346–359, 2008.
[12] G. Carneiro et al. “Supervised learning of semantic classes for image
annotation and retrieval,” IEEE Trans PAMI, vol. 29, no. 3, pp. 394–
410, 2007.
[13] M. Wang et al. “Semi-supervised kernel density estimation for video
annotation,” CVIU, vol. 113, no. 3, pp.384–396, 2009.

(g)|z n )p(y|z n )n=1 p(x.
N(g) |z )nn=1 p(x(5)

B. Experiments
We next evaluated the effectiveness of SemiCCA under
the task of automatic image annotation with PASCAL VisualObject Challenge (VOC) 2008/2009 data sets [2]. This data set
is composed of images including objects from 20 visual object
classes related to people, animals, vehicles and furniture.
Multiple objects from multiple classes may be present in asingle image. Example images are put on Fig. 5. As you cansee, each image has a bounding box and object class label foreach object presented in the image. However, we removed all
the bounding boxes and only utilized class labels to simulate“weak labeling” settings [12], where images are weakly related
to multiple words without region information.
We utilized all of the 5096 images in VOC2008 training
data set, and separated them into 500 labeled images fortraining, 500 unlabeled images for evaluation and the rest
(4096 images) as unlabeled images for training. Also, 9647
images in VOC2009 training/test data set were added tounlabeled images for training. In total, 13743 unlabeled images
for training were utilized. We adopted the precision rate P R
and recall rate RE as the evaluation measures.
Fig. 6 shows the experimental results for the automatic
annotation task. Since SemiCCA includes CCA as a special

2936
2940
2928