  This paper presents Correlated Nystrom Views (XNV), a fast semi-supervised
algorithm for regression and classification. The algorithm draws on two main
ideas. First, it generates two views consisting of computationally inexpensive
random features. Second, XNV applies multiview regression using Canonical
Correlation Analysis (CCA) on unlabeled data to bias the regression towards
useful features. It has been shown that, if the views contains accurate
estimators, CCA regression can substantially reduce variance with a minimal
increase in bias. Random views are justified by recent theoretical and
empirical work showing that regression with random features closely
approximates kernel regression, implying that random views can be expected to
contain accurate estimators. We show that XNV consistently outperforms a
state-of-the-art algorithm for semi-supervised learning: substantially
improving predictive performance and reducing the variability of performance on
a wide variety of real-world datasets, whilst also reducing runtime by orders
of magnitude.
