Generalization in Unsupervised Learning

We are interested in the following questions. Given a finite data set S, with neither labels nor side information, and an unsupervised learning algorithm A, can the generalization of A be assessed on S? Similarly, given two unsupervised learning algorithms, A(1) and A(2), for the same learning task, can one assess whether one will generalize "better" on future data drawn from the same source as S? In this paper, we develop a general approach to answering these questions in a reliable and efficient manner using mild assumptions on A. We first propose a concrete generalization criterion for unsupervised learning that is analogous to prediction error in supervised learning. Then, we develop a computationally efficient procedure that realizes the generalization criterion on finite data sets, and propose and extension for comparing the generalization of two algorithms on the same data set. We validate the overall framework on algorithms for clustering and dimensionality reduction (linear and nonlinear).