Information-theoretic dataset selection for fast kernel learning
António R. C. Paiva · 2017
Kernel methods have been used to effectively tackle nonlinear or nonparametric machine learning problems. However, their computational and memory complexity grows at least quadratically with the number of training samples. This issue has made these methods difficult to use for medium to large-sized datasets and hindered practical applications. A common approach involves the use of only a selected subset of training data. This paper proposes an information-theoretic strategy for selecting a subset of the training samples that is most representative of the data structure. Using an information-theoretic measure to quantity the difference in the density estimated from the subset selected and the complete training set, the problem can be formulated in an error minimization sense and efficiently solved via the proposed algorithm. A major advantage of this approach is that the selected points automatically tradeoff accuracy with regard to the original data and diversity in the selected subset. Another major advantage is that, in contrast to previously proposed methods, our approach naturally suggests a stopping criterion that can be intuitively interpreted in terms of information lost in the approximation of the distribution. Using this stopping criterion, the number of points to select is automatically determined in a data dependent manner.