Unsupervised Learning without Overfitting: Empirical Risk Approximation as an Induction Principle for Reliable Clustering
(1999)

Unsupervised learning algorithms are designed to extract structure from data s amples on the basis of a cost function for structures. For a reliable and robust inference proce ss, th unsupervised learning algorithm has to guarantee that the extracted structures ar e typical for the data source. In particular, it has to reject all structures where the infe renc is dominated by the arbitrariness of the sample noise and which, consequently, can be characterize d as overfitting in unsupervised learning. This paper summarizes an inference principle called Empirical Risk Approximationwhich allows us to quantitatively measure the overfitting effect and to derive a criterion as a saveguard against it. The crucial condition for learning is me t if (i) the empirical risk of learning uniformly converges towards the expected risk and if ( ii) the hypothesis class retains a minimal variety for consistent inference. Parameter s l ction of learnable data structures is demonstrated for the case of k-means clustering and Monte Carlo simulations are presented to support the selection principle. 1 PHILOSOPHY OF UNSUPERVISED LEARNING Learning algorithms are designed to extract structure from data. Two class es of algorithms have been widely discussed in the literature – supervised andunsupervised learning. The distinction between the two classes depends on supervision or teacher informati on which is either available to the learning algorithm or missing in the learning process. T hi paper describes a statistical learning theory of unsupervised learning. We summarize an induct ion principle for unsupervised learning which is refered to as Empirical Risk Approximation[1]. This principle is based on the optimization of a quality functional for structures in data and, most i portantly, it contains a safeguard against overfitting of structure to the noise in a sampl e set. The extracted structure of the data is encoded by a loss function and it is assumed to produce a lear ning risk below a predefined risk threshold. This induction principle is summarized by the fol lowing two inference steps: 1. Define a hypothesis class containing loss functions which evaluate candidate structures of the data and which measure their quality. Control the complexity of the hypothesis class by an upper bound on the costs. 2. Select an arbitrary loss function from the smallest subset which still guarantees c onsistent learning (in the sense of Statistical Learning Theory). The reader should note that the learning algorithm has to return a structure with c ostsbounded by a preselected cost threshold, but it is not required to return the structure w ith minimal empirical risk as in Vapnik’s “Empirical Risk Minimization” induction principle for classi fication and regression [2]. All structures in the data with risk smaller than the sel cted risk bound are considered to be equivalent in the approximation process without further distinction. Various cases of unsupervised learning algorithms are discussed in the literature wi h mphasis on the optimization aspect, i.e., data clustering or vector quantization, self-organi zing maps, principal or independent component analysis and principal curves, projection pursuit or algorithms for relational data as multidimensional scaling and pairwise clustering and histogram based clustering methods. How can we select a loss function from a hypothesis class with desired approxim ation quality or, equivalently, find a structure with bounded costs? The nested sequence of hypothesis classe suggests a tracking strategy of solutions which are elements of smaller and sm ller hypothesis classes in that sequence. The sequential sampling can be implemented by soluti on tracking, i.e., admissible solutions are incrementally improved by gradient descent if t he process samples from a subset with smaller risk bound than in the previous sampling step. Candidate procedure for the sampling of structures from the hypothesis class are stochastic search t chniques or continuation methods like simulated or deterministic annealing, although the theory does not refer to any particular learning algorithm. The general framework of Empirical Risk Approximationand its mathematical formulation is presented in Sec. 2, whereas a more detailed discussion can be found in [1]. Thi s theory of unsupervised learning is applied to the case of central clustering in Sec. 3. 2 MATHEMATICAL FRAMEWORK FOR UNSUPERVISED LEARNING The data samples X = xi 2 : IRd; 1 i l which have to be analysed by the unsupervised learning algorithm are elements of a suitable d-dimensional Euclidian space. The data are distributed according to a measure which is assumed to be known for the analysis. A mathematically precise statement of the Empirical Risk Approximationinduction principle requires several definitions which formalize the notion of searching for struct ure in the data. The quality of structures extracted from the data set X is evaluated by a learning cost function R̂( ;X ) = 1l l Xi=1 h(xi; ): (1) R̂( ;X ) denotes theempirical risk of learning a structure for an i.i.d. sample set X . The functionh(x; ) is known asloss function in statistics. It measures the costs for processing a generic datumx and often corresponds to the negative log-likelihood of a stochastic model. For example in vector quantization, the loss function quantifies what the costs are t o ssign a data pointx to a particular prototype or codebook vector. Each value 2 parametrizes an individual loss functions with denoting the parameter set. The parameter characterizes the different structures of the data set which are hypothetically considered candida te structures in the learning process and which have to be validated. Statistical learning t heory distinguishes between different classes of loss functions, i.e., 0 1 functions in classification problems, bounded functions and unbounded non-negative functions in regression problems. This paper is concerned with the class of unbounded non-negative functions since we are particularly interested in polynomially increasing loss function ( O kxkp)) as they occur in vector quantization. Note that the quality measurê R( ;X ) depends on the i.i.d. data set X and, therefore, is itself a random variable. The relevant quality measure for unsupervised learning, howev er, is the expectation value of this random variable, known as the expected risk of learning R( ) = Z h(x; ) d (x): (2) While minima ofR̂( ;X ) or solutions with bounded empirical risk are influenced by fluctuations in the samples, it is the expected risk R( ) which completely assesses the quality of learning results in a sound probabilistic fashion. The distribution is assumed to be known in the following analysis and it has to decay sufficiently fast such that all rth moments ( r > 2) of the loss functionh(x; ) are bounded byE fjh(x; ) R( )jrg r! r 2V fh(x; )g; 8 2 . E f:g andV f:g denote expectation and variance of a random variable, respectively. is a distribution dependent constant. The moment constraint on the distribution h lds for all distributions with exponentially fast decaying tails which include all distri butions with finite support. Empirical Risk Approximationis an induction principle which requires the learning algorithm to sample from the smallest consistently learnable subset of the hypothesis cla s . In the following, the hypothesis class H contains all loss functions h(x; ); 2 and the subsets of risk bounded loss functions HR are defined as HR = fh(x; ) : 2 ^ R( ) R g : (3) The subsetsHR are obviously nested since HR 1 HR 2 H forR 1 R 2 1 andH = limR !1HR . R induces a structure on the hypothesis class in the sense of Vapnik’s “Structural Risk” and essentially controls the complexity of the hypothesis clas . TheEmpirical Risk Approximationinduction principle requires to define a nested sequence of hypothesis classes with bounded expected risk and to sample from the hypothesis clas s with the desired approximation quality. Algorithmically, however, we select t he loss function according to the bounded empirical risk̂ R( ;X ) R . This induction principle is consistent if a bounded empirical risk implies in the asymptotic limit that the loss functi o has bounded expected riskR( ) R and, therefore, is an element of the hypothesis class HR , i.e., 8 2 lim l!1 R̂( ;X ) R =) h(x; ) 2 HR : (4) This implication essentially states that the expected risk asymptotica lly does not exceed the risk bound (R( ) R ) and, therefore, the inferred structure is an approximation of the optimal data structure with risk not worse than R . The consistency assumption (4) for Empirical Risk Approximationholds if the empirical risk uniformly converges towards the expected risk lim l!1P(sup 2 jR( ) R̂( ;X )j pV fh(x; )g > ) = 0; 8 > 0; (5) where denotes the hypothesis set of distinguishable structures. defines an -netH ;R on the set of loss functions HR or coarsens the hypothesis class with an -separated set if there does not exist a finite -net forHR . Using results from the theory of empirical processes the probability of an –deviation of empirical risk from expected risk can be bounded by Bernstein’s inequality ([3], Lemma 2.2.11) P( sup 2 jR( ) R̂( ;X )j pV fh(x; )g > ) 2jH j exp l 2 2(1 + = min) : (6) The minimal variance of all loss functions is denoted by 2 min = inf 2 V fh(x; )g. jH j denotes the cardinality of an -net constructed for the hypothesis class HR under the assumption of the measure . The confidence level limits the probability of large deviations [1]. The large deviation inequality weighs two competing effects in the learning probl em, i.e., the probability of a large deviation exponentially decreases with growing sample si ze l, whereas a large deviation becomes increasingly likely with growing cardinality of the hypothesis class. A compromise between both effects determines how reliable an estimate ac tually is for a given data set X . The sample complexity l0( ; ) is defined as the nec