Abstract
A crucial technique for scaling kernel methods to very large datasets reaching or exceeding millions of instances is based on low-rank approximation of kernel matrices. The Nyström method is a popular technique to generate low-rank matrix approximations but it requires sampling of a large number of columns from the original matrix to achieve good accuracy. This chapter describes a new family of algorithms based on mixtures of Nyström approximations, Ensemble Nyström algorithms, that yield more accurate low-rank approximations than the standard Nyström method. We give a detailed study of variants of these algorithms based on simple averaging, an exponential weight method, and regression-based methods. A theoretical analysis of these algorithms, including novel error bounds guaranteeing a better convergence rate than the standard Nyström method is also presented. Finally, experiments with several datasets containing up to 1 M points are presented, demonstrating significant improvement over the standard Nyström approximation.
Original language | English (US) |
---|---|
Title of host publication | Ensemble Machine Learning |
Subtitle of host publication | Methods and Applications |
Publisher | Springer US |
Pages | 203-223 |
Number of pages | 21 |
ISBN (Electronic) | 9781441993267 |
ISBN (Print) | 9781441993250 |
DOIs | |
State | Published - Jan 1 2012 |
ASJC Scopus subject areas
- General Computer Science