Tensor Canonical Correlation Analysis for Multi-view Dimension Reduction

Introduction

The features utilized in many real-world data mining tasks are frequently of high dimension and extracted from multiple views (or sources). For example, both the page content and hyperlink represented by bag-of-words (BOW) are usually used in web page classification Blum and Mitchell (1998); Foster et al (2008), and it is common to combine the global (such as GIST Oliva and Torralba (2001)) and local (such as SIFT Lowe (2004)) descriptors in image annotation Chua et al (2009); Guillaumin et al (2009). In these applications, the features can have dimensions of up to several hundred or thousand.

Multi-view dimension reduction Foster et al (2008) seeks a low-dimensional common subspace to compactly represent the heterogeneous data, in which each of the data examples is associated with multiple high-dimensional features. It often benefits the subsequent learning process significantly in that the curse-of-dimensionality is alleviated and the computation-al efficiency is improved Hou et al (2010); Han et al (2012). Canonical correlation analysis (CCA), which is designed to inspect the linear relationship between two sets of variables Hardoon et al (2004); Bach and Jordan (2005), was formally introduced as a multi-view dimension reduction method in Foster et al (2008), where the authors prove that the labeled instance complexity can be effectively reduced under certain weak assumptions. In addition, CCA has been widely used for multi-view classification Farquhar et al (2005), regression Kakade and Foster (2007), clustering Blaschko and Lampert (2008); Chaudhuri et al (2009), etc. Theoretically, Bach and Jordan Bach and Jordan (2005) interpreted CCA probabilistically as a latent variable model, and thus it is able to be involved in a larger probabilistic model.

In spite of the profound theoretical foundation and practical success of CCA in multi-view learning, it can only handle data that is represented by two-view features. The features utilized in many real-world applications, however, are usually extracted from more than two views. For example, different kinds of color, texture and shape features are popular used in visual analysis-based tasks such as image annotation and video retrieval. A typical approach for generalizing CCA to several views is to maximize the sum of pairwise correlations between different views Vía et al (2007). The main drawback of this strategy is that only the statistics (correlation information) between pairs of features is explored, while high-order statistics that can only be obtained by simultaneously examining all features is ignored.

To tackle this problem, we develop tensor CCA (TCCA) to generalize CCA to handle an arbitrary number of views in a straightforward and yet natural way. In particular, TCCA aims to directly maximize the correlation between the canonical variables of all views, and this is achieved by analyzing the high-order covariance tensor over the data from all views. We prove that maximizing the correlation is equivalent to approximating the covariance tensor with a rank-1 tensor in an optimal least square sense. This approximation has been investigated in the literature and an efficient alternating least square (ALS) algorithm can be adopted for optimization Kroonenberg and De Leeuw (1980); De Lathauwer et al (2000b); Comon et al (2009). With respect to the traditional pairwise correlation maximization, the statistics (correlation information) explored can be measured using the $m(m-1)/2$ covariance matrices of size $(d^{2})$, where $m$ is the number of views and $d$ represents the average feature dimensions, whereas in the proposed TCCA, the size of the covariance tensor is $(d^{m})$. Fig. 1 is an illustrative example, where $m=3$. Much more correlation information is encoded in the common subspace shared by all features in multi-view dimension reduction, and thus hopefully better performance can be achieved. Furthermore, we extend the proposed TCCA to the non-linear case, which is useful when the feature dimensions are very high and limited instances are available. We perform extensive experiments on a variety of challenge tasks, including large scale biometric structure prediction, internet advertisement classification and web image annotation. We compare the proposed method with the traditional CCA Foster et al (2008) and its multi-view extension Vía et al (2007), as well as two representative unsupervised multi-view dimension reduction approaches Long et al (2008); Han et al (2012). The results confirm the effectiveness of the proposed TCCA.

The article is organized as follows. We summarize closely related works in Section 2. A brief introduction of CCA and its traditional multi-view extension is presented in Section 3. Section 4 includes the description, formulation, and analysis of the proposed TCCA, as well as its non-linear extension kernel TCCA (KTCCA) for multi-view dimension reduction. Extensive experiments are presented in Section 5 and the paper is concluded in Section 6.

Related Work

Dimension reduction is a key technique in machine learning. The goal of dimension reduction is to find a low dimensional representation for high dimensional data Xia et al (2010). Feature selection and feature transformation and the two main approaches for dimension reduction. The former aims to select a subset of variables from the original, while the latter transforms the data to a new space of fewer dimensions. The dimension reduction can be performed in an either unsupervised (e.g., principal component analysis (PCA) and Laplacian eigenmaps (LE) Belkin and Niyogi (2001)), semi-supervised Benabdeslem and Hindawi (2014), or supervised (e.g., linear discriminant analysis (LDA)) setting, differed in the amount of labeled information being utilized.

In another research line, multi-view learning has attracted much attention recently. The multi-view we refer to here is the multiple feature representations of an object, not the spatial viewpoints in some other vision and graphics applications Su et al (2009). We generally classify the multi-view learning algorithms into three families: weighted view combination Lanckriet et al (2004); McFee and Lanckriet (2011), multi-view dimension reduction Hardoon et al (2004); White et al (2012), and view agreement exploration Blum and Mitchell (1998); Kumar et al (2011). Multi-view dimension reduction focuses on removing irrelevant or redundant information Benabdeslem and Hindawi (2014) and reducing the feature dimension of data that consists of multiple views by leveraging the dependencies, coherence, and complementarity of those views. The different views are often assumed to be conditionally independent, thus a latent representation shared by all views can be obtained by exploiting the conditional independence structure of the multi-view data Foster et al (2008); Long et al (2008); White et al (2012); Han et al (2012); Chen et al (2012). For example, canonical correlation analysis (CCA) is employed for multi-view dimension reduction in Foster et al (2008) to exploit the underlying conditional independence and redundancy assumption in multi-view learning. A general unsupervised learning method is presented in Long et al (2008) for multi-view data, where a consensus representation is learned by first applying dimension reduction technique (such as spectral embedding Belkin and Niyogi (2001)) on each view and then combining the results via matrix factorization. In Han et al (2012), the structured sparsity Jenatton et al (2011) is enforced among the different views in the learning of low-dimension consensus representation, to allow information being shared across subsets of features adaptively. In contrast to unsupervised multi-view dimension reduction, the similarity/dissimilarity pairwise constraints are utilized in Hou et al (2010) for semi-supervised multi-view dimension reduction. In Chen et al (2012), the supervising information is also incorporated in the learned latent shared subspace by the use of a large-margin latent Markov network. In these methods, local optimal subspace can usually be obtained. Therefore, White et al. White et al (2012) proposed a convex formulation for learning a shared subspace of multiple sources. In the learned subspace, conditional independence constraints are enforced.

2 Canonical Correlation Analysis and Its Extensions

Canonical correlation analysis (CCA), originally proposed by Hotelling (1936), finds bases for two random variables (or sets of variables) so that the coordinates of the variable pairs projected on these bases are maximally correlated Hardoon et al (2004). Much success has been achieved by applying CCA to pattern recognition and data mining. For example, SVM-2K was proposed in Farquhar et al (2005) for two-view classification. It combines kernel CCA and support vector machine (SVM) in a single optimization problem, and the authors prove that the Rademacher complexity of SVM-2K is significantly lower than the individual SVMs. Kakade and Foster Kakade and Foster (2007) presented a multi-view regression algorithm regularized with a norm that is derived by applying CCA on unlabeled data. The authors show that the intrinsic dimension of the regression problem with the induced norm can be characterized by the correlation coefficients obtained in CCA. Under the conditionally uncorrelated assumption, a simple and efficient subspace learning algorithm based on CCA was proposed in Chaudhuri et al (2009) for multi-view clustering. The algorithm was shown to work well under much weaker separation conditions than the previous clustering methods.

In addition to these applications, there have been dozens of developments for CCA, most of which concentrate on inspecting the relationship between two sets of tensors rather than vectors. For example, the classical CCA was extended in Lee and Choi (2007) to 2D-CCA, which directly analyzes 2D images without reshaping them into vectors. Some of its extensions are local 2D-CCA Wang (2010), sparse 2D-CCA Yan et al (2012), and multilinear CCA (MCCA) Lu (2013). Considering that the two high-order tensors to be studied may share multiple modes (e.g., the video volume data), Kim and Cipolla Kim and Cipolla (2009) presented two architectures for tensor correlation maximization by applying canonical transformation on the non-shared modes. In this way, features that have a good balance between flexibility and descriptive power may be obtained. This method is also termed “tensor CCA” (TCCA), but is quite different from the approach proposed in this paper. The main difference lies in that the latter focuses on analyzing two high-order tensor data sets, while our objective is to analyze the high-order statistics among multiple vector data sets (views).

The most closely related works to our methods, as far as we are concerned, are the maximum variance CCA (CCA-MAXVAR) Kettenring (1971) and an adaptive CCA algorithm termed CCA-LS Vía et al (2007), which is based on least square (LS) regression. The CCA-MAXVAR algorithm is performed by weighted combination of the canonical variables (projected vectors) of all views to approximate a latent common representation. This approach requires costly singular value decomposition (SVD) for optimization and cannot be trained in an adaptive fashion. To avoid these drawbacks, Via et al. Vía et al (2007) reformulated CCA-MAXVAR as a set of coupled LS regression problems, which seeks to minimize the distance between each pair of canonical variables. The reformulation is proved to be equivalent to the original CCA-MAXVAR formulation, but is much more efficient and can be learned adaptively. Nevertheless, there is still a disadvantage to both CCA-LS and CCA-MAXVAR, namely that only the pairwise correlations are exploited, while the high order correlations between all views are ignored. We developed the following tensor CCA framework to rectify this shortcoming.

Canonical Correlation Analysis (CCA) and Its Multi-view Generalization

where $\mathbf{z}_{p}=X_{p}^{T}\mathbf{h}_{p}$ is the vector of canonical variables, $\mathbf{z}$ is the best possible one-dimensional PCA representation, and $\mathbf{a}=[\alpha_{1},\ldots,\alpha_{m}]^{T}$ is the vector of combination weights. To avoid a trivial solution, an additional constraint such as $\|\alpha_{p}\|_{2}^{2}=m$ is enforced. The solutions of (3.2) can be obtained using the SVD of $X_{p}$. To develop an efficient and adaptive algorithm, Via et al. Vía et al (2007) reformulated (3.2) as

The orthogonal constraint $(z^{(i)})^{T}z^{(j)}=0,i\neq j$ is imposed on the different solutions, which can be obtained by using an iterative algorithm based on LS regression Vía et al (2007). Here, $\mathbf{z}^{(i)}=\frac{1}{m}\sum_{p=1}^{m}\mathbf{z}_{p}^{(i)}$ and $\mathbf{z}_{p}^{(i)}$ is a vector of canonical variables projected using the $i$’th canonical vector in the $p$’th view.

Tensor Canonical Correlation Analysis (TCCA)

Let $\mathcal{A}$ be an $m$-order tensor of size $I_{1}\times I_{2}\times\ldots\times I_{m}$, and $U$ be a $J_{p}\times I_{p}$ matrix. The $p$-mode product of $\mathcal{A}$ and $U$ is then denoted as $\mathcal{B}=\mathcal{A}\times_{p}U$, which is an $I_{1}\times\ldots I_{p-1}\times J_{p}\times I_{p+1}\times I_{m}$ tensor with the element

The product of $\mathcal{A}$ and a sequence of matrices $\{U_{p}\in R^{J_{p}\times I_{p}}\}_{p=1}^{m}$ is a $J_{1}\times J_{2}\times\ldots\times J_{m}$ tensor denoted by

The mode-$p$ matricization of $\mathcal{A}$ is denoted as an $I_{p}\times(I_{1}I_{p-1}I_{p+1}I_{m})$ matrix $A_{(p)}$, which is obtained by mapping the fibers associated with the $p$’th dimension of $\mathcal{A}$ as the rows of $A_{(p)}$, and aligning the corresponding fibers of all the other dimensions as the columns. Here, the columns can be ordered in any way. The $p$-mode multiplication $\mathcal{B}=\mathcal{A}\times_{p}U$ can be manipulated as matrix multiplication by storing the tensors in metricized form, i.e., $B_{(p)}=UA_{(p)}$. Specifically, the series of $p$-mode product in (4.2) can be expressed as a series of Kronecker products and is given by

where $\{c_{1},c_{2},\ldots,c_{L}\}=\{p+1,p+2,\ldots,m,1,2,\ldots,p-1\}$ is a forward cyclic ordering for the indices of the tensor dimensions that map to the column of the matrix. Finally, the Frobenius norm of the tensor $\mathcal{A}$ is given by

2 Problem Formulation

and the covariance tensor among all views is calculated as

The high order canonical correlation is given by

The proof is presented in the Appendix. By further considering that $X_{p}X_{p}^{T}=C_{pp},p=1,\ldots,m$, the problem (4.5) becomes

We further add a regularization term in the constraints to control the model complexity, and thus the constraints of problem (4.7) become

The problems (4.7) and (4.9) are equivalent.

It is straightforward that the constraints of problems (4.7) and (4.9) are equivalent, and now we prove that the objective of the two problems is the same as follows,

where the metricizing property of the tensor-matrix product presented in (4.3) and some basic properties of the Kronecker product are applied. ∎

3 Solutions

It has been presented in De Lathauwer et al (2000b) that the problem (4.9) is equivalent to finding the best rank-$1$ approximation of the tensor $\mathcal{M}$, i.e., if we define $\hat{\mathcal{M}}=\rho\mathbf{u}_{1}\circ\mathbf{u}_{2}\circ\ldots\circ\mathbf{u}_{m}$, then the optimization problem becomes

The solution can be obtained using the alternating least square (ALS) algorithm Kroonenberg and De Leeuw (1980); Comon et al (2009). Some other algorithms, such as the high-order power method (HOPM) De Lathauwer et al (2000b) and the tensor power method Allen (2012), can also be applied here for optimization, but our empirical findings indicate that the ALS algorithm performs the best in our experiments.

As in the two-view CCA, we perform a recursive maximization of the correlation between linear combinations of $X_{p},p=1,\ldots,m$. However, we cannot expect the different linear combinations $\mathbf{h}_{p}^{(1)},\ldots,\mathbf{h}_{p}^{(r)}$ of $X_{p}$ to be uncorrelated with each other, where $r$ is the rank of $\mathcal{M}$ (the determination of the rank value is still an open problem for the high-order tensors De Lathauwer et al (2000a)). That is, the orthogonality constraints cannot be imposed on $\mathbf{u}_{p}^{(1)},\ldots,\mathbf{u}_{p}^{(r)}$, since the sum of rank-1 decomposition and orthogonal decomposition of high-order tensors cannot be satisfied simultaneously De Lathauwer et al (2000a).

4 Non-linear Extension

The projections $\{\mathbf{h}_{p}\}$ are linear in TCCA and thus may be not appropriate for instances that lie in quite non-linear feature space. To this end, we develop kernel tensor CCA (KTCCA) that extends the proposed TCCA to the non-linear case. KTCCA aims to find non-linear projections by first projecting the data into higher dimensional space induced by the feature mapping $\phi$:

where the mapped dimension $D_{p}$ may be infinite. Then the variance matrices

and the canonical variables $\mathbf{z}_{p}=\phi^{T}(X_{p})\mathbf{h}_{p}$. It follows from the Representer Theorem Scholkopf and Smola (2002) that $\mathbf{h}_{p}$ can be rewritten as a linear combination of the given instances, i.e.,

where $K_{pp}=\phi^{T}(X_{p})\phi(X_{p})$ is the kernel matrix of the $p$’th view. The derivation is similar to Theorem 2. Here $\mathcal{K}_{12\ldots m}=\mathcal{C}_{12\ldots m}\times_{1}\phi^{T}(X_{1})\times_{2}\phi^{T}(X_{2})\ldots\times_{m}\phi^{T}(X_{m})$ and can be calculated according to the following theorem.

in which $\mathbf{k}_{pn}=\phi^{T}(X_{p})\phi(\mathbf{x}_{pn})$, i.e., the $n$’th column of the kernel matrix $K_{pp}$, $p=1,\ldots,m$.

We give the proof in the Appendix. To avoid trivial learning, we follow Hardoon et al (2004) and introduce a partial least square (PLS) term to penalize the norms of the weight vectors $\{\mathbf{a}_{p}\}$. That is, the constraints of problem (4.13) become

Because the matrix $(K_{pp}^{2}+\epsilon K_{pp})$ is positive definite, it has a unique Cholesky decomposition, and we can denote its decomposition as $(K_{pp}^{2}+\epsilon K_{pp})=L_{p}^{T}L_{p}$. Let $\mathbf{b}_{p}=L_{p}\mathbf{a}_{p}$ and $\mathcal{S}=\mathcal{K}_{12\ldots m}\times_{1}(L_{1}^{-1})^{T}\times_{2}(L_{2}^{-1})^{T}\ldots\times_{m}(L_{m}^{-1})^{T}$, we can reformulate (4.13) as

Similar to TCCA, this problem is equivalent to finding the best rank-$1$ approximation of $\mathcal{S}$, and the solution can be found using the ALS algorithm. By recursively maximizing the correlation, we obtain $\mathbf{b}_{p}^{(1)},\ldots,\mathbf{b}_{p}^{(r)}$. Let $B_{p}=[\mathbf{b}_{p}^{(1)},\ldots,\mathbf{b}_{p}^{(r)}]$, and the canonical variables $\mathbf{z}_{p}=\phi^{T}(X_{p})\mathbf{h}_{p}=\phi^{T}(X_{p})\phi(X_{p})\mathbf{a}_{p}=K_{pp}L_{p}^{-1}\mathbf{b}_{p}$ and the projected data for the $p$’th view are then

5 Complexity Analysis

According to the above analysis, we can see that the complexity of TCCA is independent of the number of instances, and thus our method can be scaled in very large sample size problems. Similarly, the complexities of KTCCA are determined by the tensor $\mathcal{S}$, the size of which is $N^{m}$. The space and time complexities are $O(N^{m})$ and $O(trN^{m})$ respectively. This means that KTCCA is capable of being scaled in problems that have very high feature dimensions and a small number of instances.

Experiments

In this section, we empirically validate the effectiveness of the proposed TCCA on a biometric structure prediction and an advertisement classification problem following Foster et al (2008), as well as on a challenging web image annotation task Chua et al (2009). In all of the following experiments, five random choices of the labeled instances are used. Twenty percent of the test data (or unlabeled data in the transductive setting) are used for validation, which means that the parameters (if not specified) corresponding to the best performance on the validation set are used for testing. The evaluation criterion is the classification accuracy.

BSF: using the single view feature that achieves the best performance in RLS/$k$NN-based classification.

CAT: concatenating the normalized features of all the views into a long vector, and then performing RLS/$k$NN-based classification.

CCA Foster et al (2008): using the CCA formulation presented in Foster et al (2008) to find a common representation of two different views. In this formulation, a regularization term $\epsilon I$ is added to control the model complexity, and we set the parameter $\epsilon$ as $10^{-2}$ in biometric structure prediction and advertisement classification according to Foster et al (2008). The parameter is tuned over the set $\{10^{i}|i=-5,\ldots,4\}$ in web image annotation. The implementation details can be found in Foster et al (2008). For $m$ different views, there are $m(m-1)/2$ subsets of two views. The subset that achieves the best performance is termed CCA (BST). To combine the results of all subsets, we average their predicted scores in RLS-based classification and adopt the majority voting strategy in $k$NN. This combination approach is termed CCA (AVG).

CCA-LS Vía et al (2007): a generalization of CCA to multiple views based on least square (LS) regression.

DSE Long et al (2008): a general and popular unsupervised multi-view dimension reduction method based on spectral embedding.

SSMVD Han et al (2012): a recently proposed unsupervised multi-view dimension reduction method based on the structured sparsity-inducing norm Jenatton et al (2011).

TCCA: the proposed tensor CCA. The regularization parameter $\epsilon$ is optimized the same as in CCA.

In the first step of DSE and SSMVD, PCA is taken as the dimension reduction method for each view, and the result dimension (of each view) is set to be $100$ empirically.

The dataset used in this set of experiments is SecStrhttp://www.kyb.tuebingen.mpg.de/ssl-book, which is a benchmark dataset for evaluating semi-supervised systems Chapelle et al (2006). The task associated with this dataset is “to predict the secondary structure of a given amino acid in a protein based on a sequence window centered around that amino acid” Chapelle et al (2006). The SecStr dataset is large-scale and contains $84K$ instances. We randomly select $100$ instances as labeled samples. There are also $1200K$ unlabeled instances which we use to observe the performance of three CCA-based methods (CCA, CCA-LS and TCCA) with respect to different amounts of unlabeled data. Following Foster et al (2008), all the provided data are used (as unlabeled instances) to find the common subspace in the CCA-based methods. The performance is evaluated in a transductive setting on the unlabeled samples (except those for validation) of the $84K$ instances. Both DSE and SSMVD are naturally transductive, since they learn the low-dimensional representation of given data directly, and no projection matrix is learned for new data. Therefore, these two methods cannot handle very large datasets and the experiments are conducted only on the $84K$ instances. In particular, DSE needs to solve an eigen-decomposition problem of size $N\times N$. The time cost or memory cost is intolerable when $N$ is $84K$, and thus a subset of $10K$ samples are utilized.

The features provided are $15$ categorical attributes, each of which is generated at a position in $[-7,+7]$ from the sequence window of amino acid, and represented by a $21$-dimensional sparse binary vector. We divided the $315(15\times 21)$ features into three views:

View-1: attributes based on the left context (positions in $$);

View-2: attributes based on the current position and middle context (positions in $$);

View-3: attributes based on the right context (positions in $$).

The performance of the compared methods in relation to the dimension of the common subspace is shown in Fig. 3. Accuracy is averaged over $5$ runs for each dimension $r$ in $\{5,10,\ldots,100,110,\ldots,200,220,\ldots,300\}$. The performance of the different methods at their best dimensions are summarized in Table 1. From the results, we observe that: 1) the concatenation strategy (CAT) is comparable to and slightly better than the strategy of only using the best single view features (BSF); 2) by learning the common subspace, all the compared multi-view dimension reduction methods are significantly better than the BSF and CAT baselines, if the dimensionalities are properly set according to the accuracy on the validation dataset. In particular, CCA (BST) is superior to CAT, although only a subset of two views is utilized in the former; 3) the accuracy of all three CCA-based methods increases with an increasing number of unlabeled data. By combining the results of different subsets, CCA (AVG) is better than CCA (BST); 4) CCA-LS is superior to CCA (BST), but their performance at their best dimension is comparable. When the number of unlabeled data is $84K$, DSE and SSMVD are comparable to CCA (BST) and CCA-LS respectively; 5) the performance of TCCA does not decease significantly as CCA-LS and CCA do when the number of dimensions is high. The main reason is that the ALS algorithm used in TCCA seeks to maximize the canonical correlations for all the $r$ factors simultaneously, but not to greedily find orthogonal decomposition components Allen (2012). That is, the main variance tends to be explained uniformly by all factors, not only by the first several factors. This is also the reason why there are some oscillations in TCCA; 6) the proposed TCCA significantly outperforms all the other methods on most dimensionalities. This demonstrates that the high order correlation information between all features is well discovered, and that exploring this kind of information is much better than only exploring the correlation information between pairs of features, as in CCA-LS.

1.2 Advertisement Classification

This set of experiments is conducted on the Ads (internet advertisements)http://archive.ics.uci.edu/ml/datasets/Internet+Advertisements dataset from the well-known UCI Machine Learning Repository. The task is to predict whether or not a given hyperlink (associated with an image) is an advertisement. There are $3,279$ instances in this dataset. We randomly choose $100$ instances as labeled training samples, and all the instances except those for validation are utilized as unlabeled samples to find the common subspace. The performance is evaluated in a transductive setting on the unlabeled samples.

We use the features as described in Kushmerick (1999), and omit the attributes that have missing values, such as the height (and width) of the image. The remained attributes are represented by binary ($1/0$) features which indicate the presence/absence of corresponding terms. For CCA-LS and TCCA, we divide all these features into three views as follows:

View-1: features based on the terms in the image s URL, caption, and alt text. $588$ dimensions;

View-2: features based on the terms in the URL of the current site. $495$ dimensions;

View-3: features based on the terms in the anchor URL. $472$ dimensions.

Fig. 4 shows the classification accuracy of the compared methods (in relation to the dimension $r$), and the accuracies at their best dimensions are summarized in Table 2. In contrast to the observations of the last set of experiments, we can see that: 1) the accuracy of the concatenation strategy (CAT) and the best single view (BSF) are almost the same. The performance of CAT is relatively worse since the feature dimension in this set of experiments is high ($1,555$ dimensions), and over-fitting occurs given the limited number of labeled samples; 2) the performance of DSE and SSMVD first increase and then decrease sharply with an increasing number of the dimension $r$, while the CCA-based methods are much steady; 3) the improvement of TCCA compared with the other CCA-based methods is not as great as in the last set of experiments. This is because we need more samples to approximate the true underlying high order correlation compared with the traditional pairwise correlation, since there are more variables to be estimated in the high order statistics. The unlabeled instances utilized in this set of experiments are much fewer, thus the high order correlation information is not well explored. CCA-LS is only comparable to CCA for the same reason.

1.3 Web Image Annotation

We further verify the effectiveness of the proposed algorithm on a natural image dataset NUS-WIDE Chua et al (2009). This dataset contains $269,648$ images, and our experiments are conduct on a subset that consists of $11,189$ images belonging to $10$ mammal concepts: bear, cat, cow, dog, elk, fox, horse, tiger, whale, and zebra. We randomly split the images into a training set of $5,597$ images and a test set of $5,592$ images. Distinguishing between these concepts is very challenging, since many of them are similar to each other, e.g., cat and tiger. We randomly choose $\{4,6,8\}$ labeled instances for each concept in the training set, and all the training instances are utilized as unlabeled samples to find the common subspace.

In this dataset, we choose three types of visual feature, namely $500$-D bag of visual words based on SIFT Lowe (2004) descriptors, $144$-D color auto-correlogram, and $128$-D wavelet texture, to represent each image Chua et al (2009).

The annotation performance of the compared methods is shown in Fig. 5 and Table 3. It can be seen from the results that: 1) in general, performance improves with an increased number of labeled instances; 2) CCA-LS is comparable to CCA (BST) and CCA (AVG), while the best performance (peak of the curve) of CCA-LS is usually higher; 3) the performance of DSE is poor when $r$ is large, while SSMVD is much steady and can be superior to CCA (AVG) and CCA-LS sometimes; 4) the accuracies of CCA (AVG) and CCA-LS first increase and then decrease with an increasing number of the dimension $r$, while the results of the proposed TCCA are satisfactory even though $r$ is large; 3) the accuracy of TCCA is significantly better than that of all the other methods under most dimensionalities.

2 Evaluation of the Non-linear Extension

We evaluate the non-linear extension of the proposed TCCA in the web image annotation task. As discussed in Section 4.5, the non-linear extension is able to handle the small sample size problem, where the feature dimensions can be very high and possibly infinite. We thus randomly choose a small set of $500$ samples from the animal subset. To perform the non-linear classification, we construct a kernel for each kind of feature. The kernel is defined by

BSK: using the single view kernel that achieves the best performance in the $k$NN-based classification.

AVG: averaging the normalized kernels of all the views, and then performing $k$NN-based classification.

KCCA Hardoon et al (2004): using the KCCA formulation presented in Hardoon et al (2004) to find a common representation of two different views. The regularization parameter is optimized over the set $\{10^{i}|i=-7,\ldots,2\}$. The setup of KCCA (BST) and KCCA (AVG) are similar as CCA (BST) and CCA (AVG) in the experiments of the linear version.

KTCCA: the non-linear extension of the proposed tensor CCA. The regularization parameter $\epsilon$ is optimized in the same way as in KCCA.

The experimental results are shown in Fig. 6 and Table 4. Compared with the results in Fig. 5, we can see that: 1) although a small number of unlabeled samples is utilized, the performance is better since the separability is improved by the non-linear projection, which is implemented via the kernel trick Shawe-Taylor and Cristianini (2004); 2) the simple AVG view combination strategy outperforms the best single view kernel (BSK) significantly, and is comparable to KCCA (BST); 3) KCCA (AVG) is slightly better than KCCA (BST), and the proposed KTCCA achieves the best performance under most dimensionalities.

3 Empirical analysis of the computational complexity

In this subsection, we empirically analyze the computational complexity of the different methods. The experiments are conducted in Matlab R2012b on a $2\times 3.33$ GHz Intel Xeon ($6$ cores) computer, where the memory is $48$GB $1333$MHz ECC DDR3-RAM. The results (time cost and memory cost) on the different datasets are shown in Fig. 7-10. From the results, we observe that: 1) the costs of the proposed TCCA are higher than the other CCA-based methods in general. This is because the decomposition is performed on a large $d_{1}\times d_{2}\times\ldots\times d_{m}$ covariance tensor, instead of one or multiple $d_{p}\times d_{q}$ covariance matrices, where $p,q=1,\ldots,m$ are the view indices. The tensor decomposition method we adopt in this paper is the ALS algorithm Kroonenberg and De Leeuw (1980); Comon et al (2009), which could result in satisfactory accuracy but is not efficient; 2) TCCA is much more efficient than DSE or SSMVD when the feature dimensions are not very high and the number of instances is large (see Fig. 7 for example). This demonstrates the superiority of TCCA compared with the existed unsupervised multi-view dimension reduction methods on the large sample size problems.

Conclusion

Standard CCA cannot deal with multi-view data, and its typical multi-view extensions ignore the high order statistics (correlation information) among all feature views. To resolve this problem, we have presented tensor CCA (TCCA) to discover such statistics by analyzing the covariance tensor of all views.

From the experimental validation on a variety of application tasks, we conclude that: 1) finding a common subspace for all views using the CCA-based strategy is often better than simply concatenating all the features, especially when the feature dimension is high; 2) examining more statistics, which may require more unlabeled data to be utilized, often leads to better performance; 3) by exploring the high order statistics, the proposed TCCA outperforms the other methods, especially when the dimension of the common subspace is high.

Compared with CCA and its traditional multi-view extensions, the main disadvantage of the proposed TCCA is the high computational cost. Most of the TCCA cost lies in the tensor decomposition, which is not the point of this paper. In the future, we will devote efficient tensor decomposition methods that could speed up TCCA, or introduce the parallel computing technique by utilizing GPU to accelerate the ALS tensor decomposition.

Appendix A Proof of Thoerem 1

According to the definition of the element-wise product, we have

where $\mathbf{z}_{p}(n)$ denotes the $n$’th entry of the vector $\mathbf{z}_{p}$, and the same notation is used for $\mathbf{x}_{pn}$ and $\mathbf{h}$. Additionally,

According to the definition of the $p$-mode product of a tensor and matrix, we have

Appendix B Proof of Theorem 3

Let $\mathcal{F}=\mathcal{C}_{12\ldots m}\times_{1}\phi^{T}(X_{1})\times_{2}\phi^{T}(X_{2})\ldots\times_{m}\phi^{T}(X_{m})$ and $\mathcal{G}=\frac{1}{N}\sum_{n=1}^{N}\mathbf{k}_{1n}\circ\mathbf{k}_{2n}\circ\ldots\circ\mathbf{k}_{mn}$, then according to the definition of the outer product, the $(j_{1},j_{2},\ldots,j_{m})$’th entry of $\mathcal{G}$ is

where $\mathbf{k}_{pn}(j_{p})$ is the $j_{p}$’th element of the vector $\mathbf{k}_{pn},p=1,\ldots,m$. Additionally, the $(j_{1},j_{2},\ldots,j_{m})$’th entry of $\mathcal{C}$ is

where $\phi_{pn}(i_{p})$ is the $i_{p}$’th element of the vector $\phi(x_{pn}),p=1,\ldots,m$. According to the definition of the tensor-matrix product, we have

Then the $(j_{1},j_{2},\ldots,j_{m})$’th entry of $\mathcal{F}$ is

By comparing (B.1) and (B.3), we complete the proof. ∎

References