Source-linked AI summary
Sparse Canonical Correlation Analysis
David R. Hardoon, John Shawe-Taylor
TL;DR
The paper addresses sparse CCA when the first view uses an ML-primal representation and the second uses an ML-dual representation. It introduces a convex least squares method with sparse projections in both views, then evaluates it on bilingual mate retrieval. SCCA performs as well as KCCA with few original features and outperforms KCCA with many, while the authors note that hyperparameter tuning remains open.
Problem
Existing CCA projections use all features, motivating sparse, interpretable projections for an ML-primal/ML-dual setting.
Method
SCCA formulates CCA as convex least squares, jointly seeking sparse primal and dual projections while preserving a kernel-defined dual view.
Results
SCCA matches KCCA with few original features and outperforms KCCA with many on English-French and English-Spanish mate retrieval.
Takeaways & Limitations
With extremely large feature counts, SCCA learns a common semantic space using a very sparse ML-primal/ML-dual representation.
Takeaways & Limitations
Hyperparameters were not tuned for optimal results, and alternative index-selection strategies remain future work.
Abstract
from arXiv · showhide
We present a novel method for solving Canonical Correlation Analysis (CCA) in a sparse convex framework using a least squares approach. The presented method focuses on the scenario when one is interested in (or limited to) a primal representation for the first view while having a dual representation for the second view. Sparse CCA (SCCA) minimises the number of features used in both the primal and dual projections while maximising the correlation between the two views. The method is demonstrated on two paired corpuses of English-French and English-Spanish for mate-retrieval. We are able to observe, in the mate-retreival, that when the number of the original features is large SCCA outperforms Kernel CCA (KCCA), learning the common semantic space from a sparse set of features.
1 Introduction
CCA finds paired projection vectors that maximise correlation between two views, but dense projections over all features can be difficult to interpret. This paper introduces a sparse ML-primal/ML-dual formulation and evaluates it against KCCA on bilingual mate retrieval.
- CCA motivation: CCA finds pairs of vectors that maximise correlation between paired variables viewed as representations of the same object.
- Motivation for sparsity: Dense CCA projections combine all primal and dual features, making the learned solutions difficult to interpret.
- Proposed approach: SCCA uses a convex least squares formulation to select few relevant features while explaining as much correlation as possible.
- Proposed approach: The method formulates one view in the ML-primal input space and the other in the ML-dual kernel space.
- Evaluation: On bilingual mate retrieval, SCCA matches KCCA with few original features and outperforms it when the original feature count is large.
2 Canonical Correlation Analysis
The paper reviews primal CCA and its kernelized dual formulation. Kernelizing first maps data into higher-dimensional feature spaces, enabling CCA to model nonlinear relationships and express weights through training examples.
- Canonical correlation analysis: CCA maximises correlation between projections of paired data using within-set and between-set covariance structure.
- Kernel CCA: Kernel CCA projects each view into a higher-dimensional feature space before performing CCA.
- Kernel CCA: In the kernel formulation, projection weights are expressed as linear combinations of training examples, yielding a dual CCA optimisation problem.
- Regularisation: Theoretical analyses commonly motivate regularisation for KCCA, while linear-kernel regularised KCCA is equivalent to regularised CCA.
3 Sparse CCA
The sparse formulation targets interpretable ML-primal/ML-dual projections by replacing constrained correlation optimisation with convex least squares and sparsity controls. The resulting method uses sparse weights in both views while retaining a kernel-defined dual representation.
- Motivation and scope: The ML-primal/ML-dual setting is motivated by applications requiring interpretable mappings between features in one view and specific contexts or stimuli in another.
- Motivation and scope: This paper experimentally limits its scope to bilingual text problems and considers ML-primal first-view and ML-dual second-view representations.
- Primal-dual formulation: The primal-dual CCA problem chooses first-view weights w and second-view dual features e to maximise their correlation.
- Sparse reformulation: Correlation maximisation can be reformulated as minimising the distance between X′w and Ke, with scaling fixed through an infinity-norm constraint on e.
- Sparse reformulation: The method re-normalises e after optimisation so ∥Ke∥2 = 1 while retaining kernel information through the dual-view kernel K.
- Sparsity constraints: Sparsity is imposed on e by fixing one coefficient and constraining the 1-norm of the remaining coefficients, while the 1-norm of w is also constrained.
- Convexity: The joint objective is convex because the squared norm is quadratic and bounded below, while the 1-norm constraints are linear.
4 Derivation & Algorithm
The method solves a sparse primal-dual CCA problem by alternating updates of feature and dual projection vectors, using Lagrangian constraints to select non-zero elements. It includes iterative convergence checks, automatic sparsity scaling, and deflation for extracting orthogonal feature directions.
- Algorithm: The proposed algorithm alternates between solving ML-primal and dual variables while greedily minimizing the gap between their Lagrangian solutions.This produces sparse w and e vectors through iterative updates between the two formulations.
- Algorithm: The algorithm checks primal and dual constraints after each alternating update and repeats the process until the constraints hold.The high-level procedure cycles through primal updates, primal constraint checks, dual updates, and dual constraint checks.
- Sparse updates: Dual-variable bounds identify which indices of w and e require updates, restricting changes to elements that violate the relevant constraints.The bounds are 0 ≤ α−, α+ ≤ 2µj for w-related variables, while β values below 0 identify updates for e.
- Sparsity formulation: The Lagrangian represents w through positive and negative components and constrains e to positive entries, enabling 1-norm sparsity terms for both projections.The scale factors µ and γ control the trade-off between the objective and sparsity, while positivity allows γ∥e∥1 to be written as γe′j.
- Algorithm: Algorithm 1 takes the data matrix, kernel matrix, and k as inputs, initializes w and e, updates the selected variables, and outputs feature directions w and e.The implementation alternates convergence over w and e and updates variables whose associated constraints are violated.
- Deflation: Deflation projects the data onto orthogonal complements after each paired extraction, producing orthogonal projection directions for the primal and dual views.The procedure constructs residual matrices for successive paired directions and applies corresponding primal and dual projection formulas.
- Algorithm limitations: Selecting the optimal k at every iteration is computationally impractical, so the experiments choose k values sequentially in numerical order.The authors identify subset-based selection as a possible future extension and note that the automatic sparsity setting may not be optimal.
5 Experiments
Experiments evaluate automatic sparsity selection and SCCA mate retrieval on paired English-French and English-Spanish corpora. SCCA matches KCCA with substantially fewer features in English-French and outperforms KCCA in English-Spanish while using sparse representations.
- Experimental setup: The experiments use TFIDF-normalised paired corpora with a linear kernel for the dual view: 300 English-French samples and 1,000 English-Spanish samples.The corpora contain 2,637 English and 2,951 French features, versus 40,629 English and 57,796 Spanish features.
- Hyperparameter validation: Automatic selection of µ produces a document-generation sparsity level close to the ideal ratio of 1 across English-French queries.The ideal ratio corresponds to selecting the same number of words as the original paired document.
- Mate retrieval: SCCA and KCCA have extremely similar English-French mate-retrieval error and converge when enough projections are used.With 35 projections, SCCA uses approximately 142 words and 42 documents, while KCCA uses 2,794 words and 50 documents.
- Mate retrieval: SCCA outperforms KCCA throughout the English-Spanish mate-retrieval experiment with 100 training and 900 testing documents.KCCA uses all 49,212 words, whereas SCCA uses a maximum of 460 words.
- Interpretation: The results indicate that SCCA extracts meaningful cross-language semantics using only relevant features, especially when the original feature count is large.The paper identifies sparsity and interpretability as SCCA’s main gains, while leaving hyperparameter optimality for future research.
6 Conclusions
The paper presents SCCA as a convex least-squares method for sparse CCA in an ML-primal/ML-dual setting, with a greedy optimisation algorithm. Experiments show that it can learn bilingual semantic spaces from sparse representations, while hyperparameter selection and broader formulations remain open questions.
- 6 Conclusions: SCCA formulates sparse CCA as a convex least-squares problem for an ML-primal first view and an ML-dual second view.The method seeks to use few relevant features while explaining correlation between the views.
- 6 Conclusions: A greedy optimisation algorithm is derived for the proposed SCCA formulation.
- 6 Conclusions: SCCA learns common semantic spaces from very sparse ML-primal and ML-dual representations in English-French and English-Spanish mate-retrieval experiments.The method is demonstrated on paired bilingual corpora and is especially intended for settings with many features.
- 6 Conclusions: Automatically selecting the hyperparameters µ and γ to achieve optimal results remains an open question.
- 6 Conclusions: Extending SCCA to ML-primal/ML-primal or ML-dual/ML-dual frameworks remains future work.
- 6 Conclusions: The paper characterises this work as an initial stage for a sparse framework to be explored and extended.