An RKHS for multi-view learning and manifold co-regularization

Vikas Sindhwani, David S. RosenbergICML 2008 · OpenReview

Introduction

In semi-supervised learning, practitioners often have access to a small amount of labeled data and a vast amount of unlabeled data. A popular strategy to leverage this unlabeled data is "multi-view learning," where data is examined through different "lenses" or feature sets (e.g., the text of a webpage versus the anchor text of incoming links). The core intuition is that a good predictor in one view should agree with a good predictor in the other view on unlabeled examples—a concept known as co-regularization.

Previously, enforcing this agreement required solving complex joint optimization problems across multiple function spaces. This complexity made it difficult to derive theoretical guarantees or to integrate these ideas into standard machine learning algorithms like Support Vector Machines (SVMs). Furthermore, existing manifold-based methods often struggled when the "intrinsic" geometry of the data conflicted with the "ambient" function space, such as trying to fit a simple linear model to data curved along a circle.

This paper simplifies multi-view semi-supervised learning by proving that co-regularization can be condensed into a single, standard Reproducing Kernel Hilbert Space (RKHS). By deriving an explicit "co-regularization kernel," the authors enable researchers to use standard supervised learning tools to solve complex multi-view problems and introduce CoMR, a powerful new approach for learning on manifolds.

The Co-Regularization RKHS Framework

The authors make a significant theoretical breakthrough by constructing a single, unified RKHS ($\tilde{\mathcal{H}}$) that inherently contains the co-regularization constraint.

  1. The Co-Regularization Kernel: They derive an explicit mathematical formula for a new kernel, $\tilde{k}(x, z)$. This kernel is "data-dependent" because it incorporates the geometry of the unlabeled data directly into its formulation.
  2. Reduction to Supervised Learning: Because they have defined a valid RKHS, the Representer Theorem applies. This means that a complex multi-view semi-supervised problem can now be solved as a simple, standard supervised kernel problem using the new $\tilde{k}$.
  3. Theoretical Simplicity: By moving to a single RKHS, proving generalization bounds becomes much easier. The authors show that previous complex proofs for Rademacher complexity in co-regularization now follow from standard, well-known results.

Manifold Co-Regularization (CoMR)

The authors apply this unified framework to manifold learning, treating the "ambient" Euclidean view and the "intrinsic" manifold view (represented by a graph Laplacian) as two separate views. By co-regularizing them, they create a model that is smooth both in space and along the data manifold.

Standard Manifold Regularization (MR) is often "rigid"—it strictly forces the function to be smooth on the manifold. CoMR is more flexible; it effectively adds "slack variables" that allow the model to better fit the manifold's shape even if the underlying function space is restricted. Furthermore, unlike many graph-based methods that are transductive (only working on data they have already seen), this RKHS formulation naturally handles out-of-sample extensions for new test data.

Experimental Results

The authors evaluated their CoMR algorithm against standard Manifold Regularization (MR) on five diverse datasets: LINES (a synthetic 2D dataset), G50C, USPST (handwritten digits), COIL20 (object images), and PCMAC (text categorization).

The proposed CoMR algorithm consistently outperformed standard MR across almost all benchmarks. The results were statistically significant on all datasets except G50C, where both methods performed similarly near the Bayes error rate.

  • LINES: Error dropped dramatically from 7.7% (MR) to 1.0% (CoMR). The LINES dataset was specifically designed to show where standard MR fails due to classes lying on perpendicular lines.
  • COIL20: Error dropped significantly from 23.8% to 14.8%.
  • USPST: Error was reduced from 18.2% to 14.1%.
  • PCMAC: Error improved from 11.9% to 8.9%.
Comparison of MR and CoMR on the LINES dataset

As illustrated above, CoMR successfully captures the underlying structure of the LINES dataset where standard MR fails to align the decision boundary correctly.

Limitations and Future Work

While theoretically elegant and empirically strong, the approach has a few limitations:

  • Computational Cost: The co-regularization kernel involves inverting a matrix related to the unlabeled data. While standard for kernel methods, this can be computationally expensive for extremely large datasets.
  • Parameter Sensitivity: The method introduces parameters ($\gamma, \mu$) that control the trade-off between the views and the regularization. While the authors used validation sets to find these, automated ways to tune these would be beneficial.
  • Scaling Views: While the theory supports multiple views, the experimental focus was primarily on two. Extending the empirical analysis to three or more distinct data views remains a path for future exploration.

Summary updated

Abstract

Inspired by co-training, many multi-view semi-supervised kernel methods implement the following idea: find a function in each of multiple Reproducing Kernel Hilbert Spaces (RKHSs) such that (a) the chosen functions make similar predictions on unlabeled examples, and (b) the average prediction given by the chosen functions performs well on labeled examples. In this paper, we construct a single RKHS with a data-dependent "co-regularization" norm that reduces these approaches to standard supervised learning. The reproducing kernel for this RKHS can be explicitly derived and plugged into any kernel method, greatly extending the theoretical and algorithmic scope of coregularization. In particular, with this development, the Rademacher complexity bound for co-regularization given in (Rosenberg & Bartlett, 2007) follows easily from wellknown results. Furthermore, more refined bounds given by localized Rademacher complexity can also be easily applied. We propose a co-regularization based algorithmic alternative to manifold regularization (Belkin et al., 2006; Sindhwani et al., 2005a) that leads to major empirical improvements on semi-supervised tasks. Unlike the recently proposed transductive approach of (Yu et al., 2008), our RKHS formulation is truly semi-supervised and naturally extends to unseen test data.
BibTeX
@inproceedings{sindhwani2008rkhs,
  author = {Vikas Sindhwani and David S. Rosenberg},
  title = {{An RKHS for multi-view learning and manifold co-regularization}},
  booktitle = {International Conference on Machine Learning},
  year = {2008},
  url = {https://openreview.net/forum?id=SyW2TsZu-r},
}
Figure