Title: DIFFERENTIABLE CANONICAL CORRELATION ANALYSIS

Abstract: Canonical Correlation Analysis (CCA) computes maximally-correlated linear projections of two modalities. We propose Differentiable CCA, a formulation of CCA that can be cast as a layer within a multi-view neural network. Unlike Deep CCA, an earlier extension of CCA to nonlinear projections, our formulation enables gradient flow through the computation of the CCA projection matrices, and free choice of the final optimization target. We show the effectiveness of this approach in cross-modality retrieval experiments on two public image-to-text datasets, surpassing both Deep CCA and a multi-view network with freely-learned projections. We assume that Differentiable CCA could be a useful building block for many multi-modality tasks.

1. INTRODUCTION:

Deep Canonical Correlation Analysis (DCCA) (Andrew et al., 2013) is a non-linear extension of classic Canonical Correlation Analysis (CCA) (Hotelling, 1936) that learns highly correlated latent representations on top of two different neural networks. The central idea of our work is to extend this formulation and cast CCA as a fully differentiable neural network layer which allows for parameter optimization via back-propagation through the CCA projection matrices. This is in contrast to DCCA, where correlation analysis is the topmost part of the network and only used as an optimization target for maximizing the correlation between the respective views. DCCA in general gained a lot of attention recently. It inspired related methods such as Deep Linear Discriminant Analysis (Dorfer et al., 2015) as well as a discriminative re-formulation of DCCA (Elmadany et al., 2016) applied to improve speech-based emotion recognition. Wang et al. (2015a) show that joint optimization of correlation and reconstruction error in auto-encoder configurations is successfully used for representation learning on a multi-modal speech production dataset. We take this as a motivation to evolve and extend the applicability of DCCA.

In our experiments, we employ the proposed differentiable CCA layer in a cross-modality retrieval setup. Cross-modality retrieval is the task of retrieving relevant data of another type when a sample of a different modality is given as a search query. A recent survey by Wang et al. (2016) categorizes the task into binary and real-valued representation learning. In the case of real-valued representation learning, End-to-End DCCA (Yan & Mikolajczyk, 2015) achieves state of the art retrieval results in combination with retrieval by cosine distance computation. With differentiable CCA, it becomes possible to train the networks to directly minimize the objective which will be used for retrieval (e.g., the cosine distance), while still benefitting from the optimally-correlated projections obtained by CCA. Results on two publicly available datasets (Flickr30k (Young et al., 2014) , IAPR TC-12 (Grubinger et al., 2006) ) suggest that our approach is capable to improve retrieval results in both directions.

The remainder of our paper is structured as follows. In Section 2, we review classic and deep CCA, which are the basis for the differentiable CCA layer proposed in Section 3. In Section 4, we show results of an experimental evaluation in a cross-modality retrieval setting and provide further investigations on the representations learned by our networks. Finally, Section 5 concludes the paper.

2. FOUNDATION: CANONICAL CORRELATION ANALYSIS AND DEEP CCA:

In this section, we review the concepts of classical and deep Canonical Correlation Analysis, the basis for the methodology proposed in this work.

2.1. CANONICAL CORRELATION ANALYSIS (CCA):

Let x ∈ R dx and y ∈ R dy denote two random vectors with covariances Σ xx and Σ yy and crosscovariance Σ xy . The objective of CCA is to find two matrices A * ∈ R dx×k and B * ∈ R dy×k (with k ≤ d x and k ≤ d y ) that project x and y into a common space maximizing their cross-correlation:

(A * , B * ) = arg max A,B corr(A x, B y) (1)

To fix the scale of A and B and force the projected dimensions to be uncorrelated, the optimization is further constrained to A Σ xx A = B Σ yy B = I, arriving at:

(A * , B * ) = arg max A ΣxxA=B ΣyyB=I A Σ xy B (2) Let T = Σ -1/2 xx Σ xy Σ -1/2

yy , and let T = U diag(d)V be the Singular Value Decomposition (SVD) of T with ordered singular values d i ≥ d i+1 . As shown by Mardia et al. (1979) , we obtain A * and B * from the top k left-and right-singular vectors of T:

A * = Σ -1/2 xx U :k B * = Σ -1/2 yy V :k (3)

Moreover, the cross-correlation in the projection space is the sum of the top k singular values:

corr(A * x, B * y) = i≤k d i (4)

In practice, the covariances and cross-covariance of x and y are usually not known, but estimated from a training set of m paired vectors, expressed as matrices

X ∈ R dx×m , Y ∈ R dy×m : X = X - 1 m X1 Y = Y - 1 m Y1 (5) Σxx = 1 m -1 XX + rI Σxy = 1 m -1 XY Σyy = 1 m -1 YY + rI (6)

Here, r is a regularization parameter ensuring the matrices are positive definite. Substituting these estimates for Σ xx , Σ xy and Σ yy , respectively, we can estimate A * and B * using Equation 3.

2.2 DEEP CANONICAL CORRELATION ANALYSIS (DCCA) Andrew et al. (2013) propose an extension of CCA that allows learning parametric nonlinear transformations of two variables maximizing the cross-correlation after optimal projection. Specifically, let a ∈ R da and b ∈ R d b denote two random vectors, and let x = f (a; Θ f ) and y = g(b; Θ g ) denote their nonlinear transformations, parameterized by Θ f and Θ g . For example, f and g could be feed-forward neural networks. As before, Equation 3 gives the linear transformations of x and y optimizing the CCA objective in Equation 2. Deep CCA optimizes Θ f and Θ g to further increase the cross-correlation. For d x = d y = k, the CCA objective is equal to the sum of all singular values of T (Equation 4), which is equal to its trace norm: In contrast, our CCA layer establishes gradient flow over the CCA computation. This allows us to use the projection output of CCA as input for subsequent components in a multi-view network (e.g., a retrieval objective such as cosine distance). Andrew et al. (2013) show how to compute the gradient of this Trace Norm Objective (TNO) with respect to x and y. Assuming f and g are differentiable with respect to Θ f and Θ g (as is the case for neural networks), this allows to optimize the nonlinear transformations via a gradient-based method. Figure 1a shows a schematic sketch of DCCA, as a fixed objective backpropagated through two neural networks.

EQUATION

3. DIFFERENTIABLE IMPLEMENTATION OF CCA:

In this section, we further extend DCCA to allow not only an arbitrary nonlinear transformation of the inputs, but also arbitrary transformations of (or objectives on) the projected vectors. This allows CCA to be used as a building block within a multi-modality neural network, instead of as a final objective only. In the following, we will discuss how to enable backpropagation through CCA, what to consider when doing stochastic updates, and how to apply it for cross-modality retrieval.

3.1. GRADIENT OF CCA:

As mentioned above, we can compute the canonical correlation along with the optimal projection matrices from the singular value decomposition

T = Σ -1/2 xx Σ xy Σ -1/2 yy = U diag(d)V .

Specifically, we obtain the correlation as i d i , and projections as

A * = Σ -1/2 xx U and B * = Σ -1/2 yy V.

For DCCA, it suffices to compute the gradient of the total correlation wrt. x and y in order to backpropagate it through the two networks f and g. Using the chain rule, Andrew et al. (2013) decompose this into the gradients of the total correlation wrt. Σ xx , Σ xy and Σ yy , and the gradients of those wrt.

x and y. Their derivations of the former make use of the fact that both the gradient of i d i wrt. T and the gradient of ||T|| tr (the trace norm objective in Equation 7) wrt. T T have a simple form; see Andrew et al. (2013, Sec. 7) for details.

For our differentiable CCA, we instead need the gradients of the projected data A * x and B * y wrt.

x and y, which require ∂U ∂x,y and ∂V ∂x,y . We could again decompose this into the gradients wrt. T, the gradients of T wrt. Σ xx , Σ xy and Σ yy and the gradients of those wrt. x and y. However, while the gradients of U and V wrt. T are known (Papadopoulo & Lourakis, 2000) , they involve solving O((d x d y ) 2 ) linear 2×2 systems. To arrive at a more practical implementation that does not require the gradient of the SVD, we reformulate the solution to use two symmetric eigendecompositions TT = U diag(e)U and T T = V diag(e)V (Petersen & Pedersen, 2012, Eq. 270) . This gives us the same left and right eigenvectors we would obtain from the SVD (save for possibly flipped signs, which are easy to fix), along with the squared singular values (e i = d 2 i ). The gradients of eigenvectors of symmetric real eigensystems have a simple form (Magnus, 1985, Eq. 7) and both TT and T T are differentiable wrt. x and y, enabling a sufficiently efficient implementation in a graph-based, auto-differentiating math compiler such as Theano (Theano Development Team, 2016) .

3.2. STOCHASTIC OPTIMIZATION:

For classical CCA, Σ xx , Σ xy and Σ yy are estimated from a large set of m training examples (Equation 6). In contrast, gradient-based optimization of neural networks usually estimates the gradients wrt. network parameters from mini-batches of n randomly drawn examples, with n m. In Deep CCA as well as in our extension, the correlations are functions of the network parameters that we need to backpropagate through, effectively enforcing m = n. Andrew et al. (2013) solve this discrepancy by optimizing the network parameters with L-BFGS on the full training set, which is infeasible for very large datasets. Yan & Mikolajczyk (2015) instead train on small mini-batches, estimating correlation matrices of size 4096×4096 from 100 examples only, which seems risky. We will choose a way in between, training on large mini-batches to obtain stable estimates. This approach was also taken by Wang et al. (2015b, Sec. 5 .1), who found minibatches of 400-1000 examples to even outperform full-batch L-BFGS. In addition, for testing, we optionally re-estimate the correlation matrices (and the corresponding projection matrices) using a larger set of m > n examples.

Another tempting option is to train on small mini-batches, but use exponential moving averages updated with each mini-batch as follows:

Σ xx ← Σ xx (1 -α) + Σxx α Σ xy ← Σ xy (1 -α) + Σxy α Σ yy ← Σ yy (1 -α) + Σyy α

With proper initialization and a sufficiently small coefficient α, this gives stable estimates even for small n. However, since only the estimates from the current mini-batch Σxx , Σxy and Σyy can be practically considered in backpropagation, this changes the learning dynamics: For too small α, the projection matrices will be virtually degraded to constants. Empirically, we found that large mini-batches perform slightly better than small batches with moving averages (see Appendix B).

3.3. CROSS-MODALITY RETRIEVAL WITH DIFFERENTIABLE CCA:

DCCA maximizes the correlation between the latent representations of two different neural networks. When the two network inputs a and b represent different views of an entity (e.g., an image and its textual description), DCCA projects them into a common space where they are highly correlated. This can be exploited for cross-modality retrieval: Projecting one modality of an entity, we can find the best-matching representations of the second modality (e.g., an image for a textual description, or vice versa). To find the best matches, a common option is to compute nearest neighbors in terms of cosine distance (Yan & Mikolajczyk, 2015) , which is closely related to correlation.

Given the methodology introduced above, we now have the means to optimize DCCA projections directly for the task at hand. In Figure 1b , we show a possible setting where we put the differentiable CCA layer on top of a multi-view network. Instead of optimizing the networks to maximize the correlation of the projected views (the TNO), we can optimize the networks towards a task-specific objective and still benefit from the optimality of the CCA projections.

For this work, we optimize towards minimal cosine distance between the correlated views, the very metric used for retrieval. In the next section, we empirically show that this is indeed beneficial in terms of quantitative retrieval performance as well as convergence speed of network training.

4. EXPERIMENTS:

We evaluate our approach in cross-modality retrieval experiments on two publicly available datasets (also considered by Yan & Mikolajczyk (2015) ) and provide investigations on the representations learned by the network.

4.1. EXPERIMENTAL SETUP:

For the evaluation of our approach, we consider Flickr30k and IAPR TC-12, two publicly available datasets for cross-modality retrieval. Flickr30k consists of image-caption pairs, where each image A man in a white cowboy hat reclines in front of a window in an airport.

A young man rests on an airport seat with a cowboy hat over his face.

A woman relaxes on a couch , with a white cowboy hat over her head.

A man is sleeping inside on a bench with his hat over his eyes.

A person is sleeping at an airport with a hat on their head. a green and brown embankment with brown houses on the right and a light brown sandy beach at the dark blue sea on the left; a dark mountain range behind it and white clouds in a light blue sky in the background; is annotated with five different textual descriptions. The train-validation-test split for Flickr30k is 28000-1000-1000. In terms of evaluation setup, we follow the related work and report results on two different evaluation protocols. Protocol pooled pools the five available captions into one "concatenated" text, meaning that only one but richer text annotation remains per image. This is done for all three sets. Protocol 5 captions pools only the captions of the train set and keeps five separate annotations for validation and test set. The IAPR TC-12 dataset contains 20000 natural images where only one -but compared to Flickr30k more detailed -caption is available for each image. As no predefined train-validation-test split is provided, we randomly select 2000 images for testing, 1000 for validation and keep the rest for training. Yan & Mikolajczyk (2015) also use 2000 images for testing, but did not explicitly mention hold out images for validation. Table 1 shows an example image along with its corresponding captions or caption for either dataset.

The task at hand for both datasets is to retrieve the correct counterpart -either text or imagewhen given a query element of the other modality. We follow Yan & Mikolajczyk (2015) and use the cosine distance for retrieval in the projection space. As evaluation measures we consider the Recall@k (R@k) as well as the Median Rank (MR) and the Mean Average Precision (MAP). The R@k rate (high is better) is the ratio of queries which have the correct corresponding counterpart in the first k retrieval results. The MR is the median position (low is better) of the target in a similarityordered list of available candidates. Finally, we define the MAP (high is better) as the mean value of 1/Rank over all queries.

The input to our networks is a 4096-dimensional image feature vector along with a corresponding text vector representation (5793 for Flickr30k, 2048 for IAPR TC-12). In terms of text preprocessing, we follow Yan & Mikolajczyk (2015) , tokenizing and lemmatizing the raw captions as the first step. Based on the lemmatized captions, we compute l2-normalized TF/IDF-vectors, omitting words with an overall occurrence smaller than 5 times for Flickr30k and 3 times for IAPR TC-12, respectively. The image represenations are computed from the last hidden layer of a network pretrained on ImageNet (layer fc7 of CNN_S by Chatfield et al. (2014) ).

4.2. NETWORK ARCHITECTURES AND OPTIMIZATION DETAILS:

We feed 4096-dimensional image vectors along with the corresponding text representation into our networks. The image representation is followed by a linear dense layer with 128 units (this will also be the dimensionality k = 128 of the resulting CCA retrieval space). The text vector is processed by two batch-normalized (Ioffe & Szegedy, 2015) dense layers of 1024 units each and an ELU activation function (Clevert et al., 2015) . As a last layer for the text representation network, we again apply a dense layer with 128 linear units. For a fair comparison, we keep the structure (and number of parameters) of all networks in our experiments the same. The only parameters that vary are the objectives and the corresponding optimization/regularization strategies. In particular, we apply a grid search on the respective hyper-parameters and report the best results for each method. Optimization is performed either using Stochastic Gradient Descent (SGD) with momentum or by the adam (Kingma & Ba, 2014) update rule.

Table 2: Cross-modality retrieval results on Flickr30k. "E2E-DCCA" is taken from Yan & Mikolajczyk (2015) , all other results are our own. Methods marked with "*" re-estimate projection matrices from a larger batch than used during training (10,000 training examples), see Section 3.2.

Image-to-Text:

Text-to-Image Protocol Method R@1 R@5 R@10 MR R@1 R@5 R@10 MR As optimization targets, we consider the following candidates: (1) The Trace Norm Objective (TNO) as our base line for cross-modality retrieval (Yan & Mikolajczyk, 2015) . ( 2) The proposed differentiable CCA layer in combination with the objectives cosine distance (CCAL-cos), squared cosine distance (CCAL-cos 2 ) and euclidean distance (CCAL-l2). As an additional setting, we consider a freely-learnable projection layer where the projection matrices A and B are randomly initialized weights that can be optimized by the network using SGD in the conventional way. This allows to assess the benefit of using CCA-derived projections within a multi-view network under otherwise unchanged objectives. For this experiment, we optimize for the squared cosine distance and denote the setting by learned-cos 2 . The batch size is set to 1000 samples to allow stable covariance estimates for the CCA (Section 3.2). For further stabilization, we regularize the covariance matrices (Andrew et al., 2013) by adding scaled (r = 10 -3 ) identity matrices to the estimates Σ xx , Σ yy and T (Section 2.1). The variants based on differentiable CCA are additionally regularized by L2 weight decay. No dropout is used in this settings as it harmed optimization in our experiments. When optimizing with the TNO we follow Yan & Mikolajczyk (2015) and use dropout (p = 0.5) after the first two dense layers of the text network. In Table 4 in Appendix A we provide the optimization settings for all configurations in detail, found using a grid search optimizing MAP on the validation set.

4.3. EXPERIMENTAL RESULTS ON CROSS-MODALITY RETRIEVAL:

Table 2 lists our results on Flickr30k. Along with our experiments, we also show the results reported in (Yan & Mikolajczyk, 2015) as a reference (E2E-DCCA). However, a direct comparison to our results may not be fair: E2E-DCCA uses a different ImageNet-pretrained network for the image representation, and finetunes this network while we keep it fixed (as we are only interested in comparing differentiable CCA to alternatives, not in obtaining the best possible results). Our TNO results use the same objective as E2E-DCCA, but our network architecture, permitting direct comparison.

When comparing the performance of our networks, we observe a gain both for image-to-text and text-to-image retrieval when training with the CCAL-cos 2 objective compared to TNO (e.g., R@1 of 34.1 compared to 29.9 under protocol pooled). This indicates that training a network directly on the objective used for retrieval (using differentiable CCA) is a reasonable design choice. A closer look at the results also reveals that the squared cosine distance is superior compared to the remaining objectives. We further observe that the randomly initialized projection matrices learned entirely by SGD (learned-cos 2 ) show poor performance compared to their CCA counterpart (even though in theory, they could converge to exactly the same solution). This suggests that exploiting the beneficial properties of the CCA projections directly within a network during training is a powerful tool, supporting optimization of related objectives. CCAL-l2 for example performs poorer than the variants including cosine losses but still better than the version with learned weights. On protocol 5 captions, we only report the best results (CCAL-cos 2 ) along with the TNO and observe similar tendencies. Note that there are various other methods reporting results on Flickr30k (Karpathy et al., 2014; Socher et al., 2014; Mao et al., 2014; Kiros et al., 2014) which partly surpass ours, for example by using more elaborate processing of the textual descriptions. We omit these results as we focus on the comparison of DCCA with the proposed differentiable CCA layer.

In Table 3 , we list our results on the IAPR TC-12 dataset. We again show the retrieval performances of Yan & Mikolajczyk (2015) as a baseline (again with limited comparability, due to a different architecture and a different train-validation-test split), along with our implementation of the TNO and the CCA layer trained with squared cosine distance. For image-to-text retrieval, we achieve slightly better retrieval performances when training with cosine distance and propagating the gradients back through the differentiable CCA layer. For the other direction, results are slightly worse.

4.4. INVESTIGATIONS ON LEARNED REPRESENTATIONS:

In this section, we provide a more detailed look at the learned representations. We compare the representations learned with the TNO to the proposed CCA layer optimized with the squared cosine distance objective. For easier comparison, we re-train both networks with a reduced projection dimensionality of h = 64 -otherwise, the TNO takes much longer to converge than the CCA layer. This results in slightly decreased performance for both, but the relative tendences are preserved.

Figure 2a shows the evolution of the mean correlation (mean over singular values with maximum 1.0) on the training set during optimization. Allong with the correlation, we also plot the average cosine distance between corresponding pairs on the validation set. As expected, for the TNO we observe a continous decrease of cosine distance when the correlation increases. Interestingly, this is not the case for CCAL-cos 2 . The result suggests that the network found a way of minimizing the cosine distance other than by increasing correlation between the representations -the latter even decreases after a few training epochs. In Figure 2b , we plot the corresponding evolution of MAP on the training and validation set, confirming that the decreased cosine distance indeed also leads to improved retrieval performance. Finally, in Figure 2c we compare the individual correlation coefficients (magnitudes of CCA singular values on the training set) of both representations after the last training epoch. This details the observation in Figure 2a : not only the total correlation, but also the individual correlation coefficients are considerably higher when training with TNO, even though the retrieval performance is lower.

5. CONCLUSION:

We presented a fully differentiable version of Canonical Correlation Analysis which enables us to back-propagate errors directly through the computation of CCA. As this requires to establish gradient flow through CCA, we formulate it to allow easy computation of the partial derivatives ∂A * ∂x,y and ∂B * ∂x,y of CCA's projection matrices A * and B * with respect to the input data x and y. With this formulation, we can incorporate CCA as a building block within multi-modality neural networks that produces maximally-correlated projections of its inputs. In our experiments, we use this building block within a cross-modality retrieval setting, optimizing a network to minimize the cosine distance of the correlated CCA projections. Experimental results show that when using the cosine distance for retrieval (as is common for correlated views), this is superior to optimizing a network for maximally-correlated projections (as done in Deep CCA), or not using CCA at all. We further observed (Section 4.4) that it is not necessarily required to have maximum correlation to achieve a high retrieval performance. Finally, our differentiable CCA layer could provide a useful basis for further research, e.g., as an intermediate processing step for learning binary cross-modality retrieval representations.

:



Figures and Tables:

Figure 1: Comparison of DCCA and the prosed differentiable CCA layer. DCCA optimizes the correlation of the two different views and is therefore the topmost part of the network. In contrast, our CCA layer establishes gradient flow over the CCA computation. This allows us to use the projection output of CCA as input for subsequent components in a multi-view network (e.g., a retrieval objective such as cosine distance).

Figure 2: Comparison of the TNO and CCAL-cos 2 based on the total amount of canonical correlation (sum over singular values d) as well as the cosine distance between corresponding samples.

Example images for Flickr30k (top) and IAPR

Table content: <table/>

Cross-modality retrieval results on IAPR TC-12

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>Image-to-Text</td><td>Text-to-Image</td></tr><tr><td/><td/><td/><td colspan="2">Method</td><td/><td colspan="3">R@1 R@5 MAP MR R@1 R@5 MAP MR</td></tr><tr><td/><td/><td/><td colspan="3">E2E-DCCA</td><td colspan="3">30.2</td><td>57.0 0.426</td><td>29.5</td><td>60.0 0.415</td></tr><tr><td/><td/><td/><td colspan="2">TNO*</td><td/><td colspan="3">30.0</td><td>56.7 0.424</td><td>4</td><td>28.0</td><td>55.4 0.410</td><td>5</td></tr><tr><td/><td/><td/><td colspan="6">CCAL-cos 2 * 31.1</td><td>58.4 0.439</td><td>4</td><td>26.8</td><td>55.1 0.403</td><td>4</td></tr><tr><td/><td>0.6</td><td/><td/><td/><td/><td/><td/><td>0.75</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>0.70</td></tr><tr><td/><td>0.5</td><td/><td/><td/><td/><td/><td/><td>0.65</td></tr><tr><td>Mean Correlation</td><td>0.3 0.4</td><td/><td/><td colspan="3">dcos(TNO, va) dcos(CCALcos 2 , va)</td><td/><td>0.45 0.50 0.55 0.60 Cosine Distance</td></tr><tr><td/><td>0.2</td><td/><td/><td colspan="3">corr(CCALcos 2 , tr) corr(TNO, tr)</td><td/><td>0.35 0.40</td></tr><tr><td/><td>0</td><td>10</td><td>20</td><td>30 Epoch 40</td><td>50</td><td>60</td><td>70</td><td>0.30</td></tr></table>

Peer review (iclr2017):
After a second look of the paper, I am still confused what the authors are trying to achieve. The CCA objective is not differentiable in the sense that the sum of singular values (trace norm) of T is not differentiable. It appears to me (from the title, and section 3), the authors are trying to solve this problem. However, -- Did the authors simply reformulate the CCA objective or change the objective? The authors need to be explicit here. -- What is the relationship between the retrieval objective and the *CCA layer*? I could imagine different ways of combining them, such as combination or bi-level optimization. And I could not find discussion about this in section 3. For this, equations would be helpful. -- Even though the CCA objective is not differentiable in the above sense, it has not caused major problem for training (e.g., in principle we need batch training, but empirically using large minibatches works fine). The authors need to justify why the original gradient computation is problematic for what the authors are trying to achieve. From the authors* response to my question 2, it seems they still use SVD of T, so I am not sure if the proposed method has advantage in computational efficiency. In terms of paper organization, it is better to describe the retrieval objective earlier than in the experiments. And I still encourage the authors to conduct the comparison with contrastive loss that I mentioned in my previous comments.