PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for Learning Kernels Based on Centered Alignment

Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh

arXiv:1203.0550v3cs.LGcs.AI

TL;DR

The paper addresses kernel selection, where feature or kernel choices strongly affect learning success, by introducing centered-alignment-based algorithms and theoretical analyses. Experiments in classification and regression show consistent improvements over uniform combinations and prior kernel-learning methods.

  • Problem

    Kernel or feature selection is critical to learning success, yet effective kernel-learning solutions have been difficult to improve beyond uniform combinations.

  • Method

    The paper uses centered alignment as a similarity measure to learn non-negative combinations of base kernels, develops efficient alignment algorithms, and analyzes their theoretical properties.

  • Results

    Experiments show consistent performance improvements over uniform kernel combinations and previous kernel-learning techniques in both classification and regression.

  • Takeaways & Limitations

    Centered alignment provides an efficient and practical basis for kernel-learning algorithms with empirical gains across classification and regression.

  • Takeaways & Limitations

    The paper does not prove that good alignment is necessary for obtaining a good classifier.

Abstract

from arXiv · show

This paper presents new and effective algorithms for learning kernels. In particular, as shown by our empirical results, these algorithms consistently outperform the so-called uniform combination solution that has proven to be difficult to improve upon in the past, as well as other algorithms for learning kernels based on convex combinations of base kernels in both classification and regression. Our algorithms are based on the notion of centered alignment which is used as a similarity measure between kernels or kernel matrices. We present a number of novel algorithmic, theoretical, and empirical results for learning kernels based on our notion of centered alignment. In particular, we describe efficient algorithms for learning a maximum alignment kernel by showing that the problem can be reduced to a simple QP and discuss a one-stage algorithm for learning both a kernel and a hypothesis based on that kernel using an alignment-based regularization. Our theoretical results include a novel concentration bound for centered alignment between kernel matrices, the proof of the existence of effective predictors for kernels with high alignment, both for classification and for regression, and the proof of stability-based generalization bounds for a broad family of algorithms for learning kernels based on centered alignment. We also report the results of experiments with our centered alignment-based algorithms in both classification and regression.

1. Introduction

The paper develops centered-alignment algorithms to reduce user reliance on manually chosen features and to address the difficulty of consistently outperforming uniform kernel combinations. It combines efficient kernel-learning procedures with theoretical guarantees and experiments showing consistent gains in classification and regression.

  • Feature choice is critical because poor features make learning challenging, while better features increase the likelihood of success.
  • Learning kernels from data partially relieves users from specifying features manually.
  • Convex combinations of finite base-kernel sets have been widely studied, but prior methods had not consistently and significantly surpassed uniform combinations in classification or regression.
  • Centered alignment measures similarity between kernels or kernel matrices, with centering and normalization identified as critical components for effective kernel learning.
  • The proposed two-stage algorithms first learn a non-negative combination of base kernels, then use SVM or KRR to select a prediction hypothesis.
  • Theoretical results include an O(1/√m) concentration bound, effective predictors for high-alignment kernels, and stability-based generalization bounds.
  • Experiments in classification and regression show improvements over uniform combinations and one-stage kernel-learning algorithms, with centered alignment strongly correlated with performance.

2. Alignment definitions

The paper defines centered kernel functions, centered kernel matrices, and centered alignment by removing feature or matrix means before measuring similarity. It motivates centering as critical because non-centered alignment can fail to track predictive performance.

  • Centered kernel functions: Centering a feature mapping subtracts its expectation, producing a centered kernel Kc that remains positive definite and has zero expected kernel value.The centered kernel is defined through inner products of centered feature mappings, so the construction is independent of the chosen mapping.
  • Centered kernel matrices: For a finite sample, centering subtracts the empirical feature mean and replaces the kernel matrix with a centered positive semi-definite matrix.The centered matrix can be written as an inner product of mean-subtracted feature vectors and has entries summing to zero.
  • Alignment: Centered alignment measures similarity between centered kernel functions or matrices, whereas earlier alignment definitions compare the uncentered objects.For positive-definite symmetric kernels, the centered-alignment value lies between 0 and 1.
  • Why centering matters: In a separable two-point example, non-centered alignment is A = (α^2 + (1 − α)^2)^1/2 and equals about .707 when α = 1/2, while centered alignment is ρ(K, K′) = 1 for every α.The example uses K(x, x′) = x · x′ + 1 and a target label kernel, demonstrating that centering removes the mismatch between alignment and separability.

3. Algorithms

The paper develops two-stage and single-stage kernel-learning algorithms based on centered alignment, using non-negative combinations of base kernels and standard prediction methods. Its alignment maximization procedures account for kernel correlations and can be reduced to efficient quadratic programs.

  • Overall framework: The algorithms use kernels K_µ = Σ_k µ_kK_k with non-negative weights, followed by SVM or KRR training, while a single-stage variant learns weights and hypotheses simultaneously.Two-stage methods first determine the mixture weights and then train a standard kernel-based predictor.
  • Independent alignment: The independent alignment method computes each base kernel’s alignment with the label kernel separately and chooses each weight proportional to that alignment.For q = 2, this is the solution of the corresponding L2-constrained optimization up to Frobenius-norm normalization.
  • Joint alignment maximization: The joint alignment maximization method selects mixture weights by maximizing centered alignment between the combined kernel and the target label kernel while accounting for correlations among base kernels.The optimization can use L2- or L1-norm constraints without changing the solution direction, followed by appropriate scaling.
  • Linear combination: For the linear-combination problem, the optimal direction is µ⋆ = M^-1a / ∥M^-1a∥ when the base kernels are linearly independent.Here a contains alignment-related coefficients and M captures pairwise interactions among the centered base kernels.
  • Convex combination: With non-negative unit-norm weights, alignment maximization reduces to a simple QP whose normalized solution gives the optimal kernel weights.The QP can also be solved with an SVM solver; matrix inversion is unnecessary, including in the non-invertible case, although the solution may then be non-unique.

4. Theoretical results

Theoretical results establish concentration, predictor-accuracy, and stability-based generalization guarantees for centered-alignment kernel learning in classification and regression.

  • Concentration bounds: O(1/√m) concentration bounds relate centered alignment to its empirical estimate.The bound controls the quantity |ρ − bρ| directly.
  • Accurate predictors: High alignment between a kernel K and the label-derived target kernel KY guarantees the existence of accurate classification and regression predictors.The target kernel is defined by KY(x, x′) = yy′.
  • Accurate predictors: The regression predictor analysis assumes centered labels with E[y] = 0 and normalized labels with E[y^2] = 1.The paper notes that centered-label assumptions can be removed using more cumbersome definitions.
  • Accurate predictors: For finite samples, the empirical predictor’s risk differs from the population predictor’s risk by O(1/√m) with high probability in both settings.This result applies to both classification and regression.
  • Accurate predictors: For classification, the predictor h* has high accuracy when kernel alignment is high and Γ is not too large.The analysis defines Γ using ratios of conditional and joint second moments of the centered kernel.
  • Stability and generalization: Stability-based bounds are proved for two-stage alignment-based algorithms whose first stage selects kernel-combination weights and whose second stage uses KRR.Analogous classification results can use SVMs in the second stage.

5. Experiments

The experiments compare centered-alignment methods with uniform and one-stage kernel combinations in classification and regression, using cross-validated datasets and Gaussian or rank-one base kernels. Across these settings, alignment-based methods generally improve performance, with two-stage alignf often matching or exceeding alternatives while align offers a cheaper heuristic.

  • Experimental design: The experiments compare unif, one-stage, align, and alignf using error and alignment measures, with 5-fold cross-validation.For two-stage methods, the same training and validation data are used in both stages, and Λ is selected by validation-set grid search.
  • General kernel combinations: Gaussian-kernel experiments use centered, trace-one base kernels with varying bandwidths on datasets from UCI and Delve.The bandwidth range is chosen so the base kernels differ sufficiently in alignment and performance.
  • General kernel combinations: In all Gaussian-kernel datasets, alignment-based methods improve over the uniform combination and one-stage kernel-learning algorithms.Align often increases final-kernel alignment and performance, while alignf gives the best alignment by directly maximizing it.
  • General kernel combinations: On kinematics and ionosphere, one-stage KRR shows no significant improvement over two-stage alignf, whose weights closely coincide with the optimally tuned one-stage solution.The two-stage method requires fewer parameters and reduces to a standard QP.
  • Rank-one kernel combinations: Rank-one sentiment kernels use 4,000 frequent bigrams, with each base kernel trace-normalized and labels centered across four domains.The regression target is a rating from 1 to 5, while classification separates positive from negative reviews.
  • Rank-one kernel combinations: In the rank-one setting, align significantly improves alignment and error percentage over unif and somewhat improves over one-stage l2-krr.Sparse weighting from alignf or l1-svm can improve alignment in some cases without improving performance.

6. Conclusion

The paper concludes that centered-alignment methods provide novel algorithmic, theoretical, and empirical results for learning kernels. Experiments show consistent performance improvements over prior techniques and uniform combinations, while the authors qualify the link between alignment and classifier accuracy.

  • Contributions: The paper presents novel algorithmic, theoretical, and empirical results for learning kernels based on centered alignment.The algorithms are described as efficient and easy to implement.
  • Empirical conclusion: Experiments show consistent performance improvements over previous learning-kernel techniques and uniform combinations in classification and regression.The paper also states that its algorithms can be used in varied applications and provides an open-source implementation.
  • Scope of the conclusion: The theory and experiments suggest accurate predictors can exist for kernels with good centered alignment, but do not prove that good alignment is necessary for a good classifier.The authors note that other efficiently computable similarity measures could support analogous learning algorithms.

Appendix A. Lemmas supporting proof of Proposition 11

This appendix develops perturbation and expectation bounds needed for concentration results involving centered kernel alignment. The lemmas control how kernel-matrix quantities change when one sample point is replaced and show that estimation bias decreases with sample size.

  • Perturbation bounds: The appendix studies samples differing in one point to bound perturbations of centered kernel-matrix expressions.The kernel diagonals are assumed bounded by R^2 and R′^2.
  • Perturbation bounds: The perturbation proof decomposes the centered-kernel expression into terms and bounds each contribution using the diagonal-kernel assumptions.Combining the four component inequalities yields the stated perturbation lemma.
  • Expectation analysis: The estimation bias decreases at rate O(1/m).This follows from the difference between the relevant expectations after bounding terms by R^2R′^2.
  • Expectation analysis: The appendix expands expectations of centered kernel products, applies identities for distinct sample indices, and collects terms to obtain the expectation expression.The derivation proceeds by expanding the expression and simplifying the expected terms.

Appendix B. Stability bounds for alignment maximization algorithm

This appendix analyzes stability for the alignment-maximization optimization and the normalized solution vector. It formulates the sample-dependent problem and uses convexity and optimality to bound changes when one sample point changes.

  • Normalized solutions: The appendix relates the normalized solution vectors μ=v/∥v∥ and μ′=v′/∥v′∥ through an identity for their difference Δμ.This identity is used to study how normalization affects stability.
  • Alignment maximization: The alignment-maximization problem is written as a sample-dependent minimization involving matrix M and vector a.The reformulation makes explicit that the optimization data depend on the training sample S.
  • Stability proof: For samples differing by one point, Proposition 21 bounds the change Δv between the corresponding solutions v and v′.The proof uses convexity of C={v: v≥0} and compares objective values along feasible interpolations.

Appendix C. Significance tests for empirical results

The appendix reports paired-sample one-sided significance tests comparing algorithm mean errors across classification and regression datasets. Results indicate broad significant improvements for the alignment-based methods, with specific dataset exceptions.

  • Test procedure: The tests compare each algorithm’s mean error against the algorithm listed in the corresponding row at significance level p = 0.1.An entry of 1 means the column algorithm’s mean error is significantly lower; 0 means the null hypothesis cannot be rejected.
  • Table scope: Table 5 presents significance tests for the rank-one kernel-combination results reported in Table 3.The table’s entries encode whether the column algorithm has significantly better accuracy than the row algorithm.
Loading 1203.0550v3…