Inference Principles and Model Selection - Dagstuhl

1 Inference Principles and Model - byJoachim Buhmann, Bernhard Sch olkopfThe core problem of statistics and machine learning addresses the question howcan we efficiently find a statistical Model to describe empirical data. Classicalstatistical approaches to solve this problem have been complemented during thelast 15 years by Neural Computation, a very promising strategy to data anal-ysis. The Dagstuhl seminar on Inference Principles and Model Selection the fourth in a series of Machine Learning and Neural Computation workshopsin 1994, 1997, 1999 and 2001 was intended to review this exciting develop-ment of the field and to discuss the foundation of statisticaland computationallearning theory with its deep (and still unresolved) questions. The participantsrepresented all of the involved disciplines from statistics and computer science toinformation theory and philosophy.

2 The burning question ofmany participants ifthere exist notions of Inference studied in philosophy thatmachine learning hasoverlooked so far came up in several sessions and especiallyin the first tutorial onPhilosophical Foundations (Matthias Hild). Three pioneers of the field, Sun-ichiAmari, Phil Dawid and Vladimir Vapnik provided valuable insights how the fieldof learning machines developed from the sixties up to today and what kind ofchallenges are lying still ahead of have been the main conclusions of the seminar?In contrast to the previous seminars, this workshop with itstutorials and shortposition statements (rather than conference style talks) forced the participants toconcentrate on conceptual issues with as little obstruction as possible by technicaldetails. Common ground between Bayesian Inference , statistical and computa-tional learning theory and logical approaches to inferenceas well as concepts frominformation theory have been observed and widely final discussion session summarized the following open issues of the field:1.

3 Tali Tishby reminded us that learning and information extraction goes be-yond the issues of sample fluctuations which are extensivelystudied in theComputational Learning Theory community. What are the correct infer-ence Principles to detect structures hidden in data?2. How can we evaluate learning Principles and algorithms? How should wedesign good experiments?13. Is Model Selection or Model combination more effective in structure detec-tion?4. How can we find more characterization results for learningalgorithms?What is an appropriate size of the validation set?5. How should we proceed in non situations where data are dependent?How can the concepts from classification and regression be extended to timeseries analysis and to Markov random What is the correct number of Inference levels?Most of these questions will stay with us for the next decadesbut this workshophas raised the awareness of all participants which parts of machine learning andneural computation are based on fundamental Principles andwhere we still haveto discover such a solid , 30.

4 Juli 2001 Joachim M. BuhmannRemark:These abstracts and links to slides are available Information Geometry and Inference Principles52 Gradient Estimates in Reinforcement Learning63 Concentration inequalities and penalization methods in modelselection74 Tracking a Small Set of Experts by Mixing Past Posteriors85 Learning and Combinatorial Optimization: The noisy TravelingSalesman Problem86 Hilbertian Learning97 Vicinal Risk Minimization118 Bayesian and Prequential Inference for Model Selection119 Model Selection and Infinite Models1210 Bagging equalizes influence1211 Kernel Methods1312 Algorithmic Luckiness1413 Inductive Reasoning1414 Gaps and Bridges between Inductive Inference and StatisticalLearning Theory1515 Assessing Reliability of Unsupervised Learning: a ResamplingApproach1616 Bias of Estimators and Regularization Terms1617 Models in Hyperbolic Space1718 Optimal Inductive Inference Under an Algorithmic Prior Re-flecting Maximally Efficient Data Generation1719 Stability of Posterior Estimates for Kernels1820 Statistical Inference and Relevant Information Encoding18321 Optimal aggregation of classifiers in statistical learning1922 Development of Statistical Learning Theory1923 Predictive complexity.

5 Theory, possible applications,and openproblems2024 On-line learning - Methods and Open Problem2025 Reinforcement Learning with Many Parameters2126 Constructive Model Building2227 SVM and VC Theory (Statistical Learning Theory)2241 Information Geometry and Inference Princi-plesShun-ichi AmariRIKEN Brain Science InstituteInformation geometry studies the intrinsic geometrical structure of a family ofprobability distributions. The structure is uniquely defined from the principle ofinvariance, giving a Riemannian metric (due to the Fisher information matrix)and a dual pair of affine connections. It is useful in many problems related tostochastic phenomena such as statistical Inference , modelselection, informationtheory, control systems theory, apply the method of information geometry to multilayer perceptrons, whichhave nonlinear input-output relations depending on the modifiable are modified by learning from examples.

6 When noises disturb the output,the behavior of a multilayer perceptron is described by the conditional proba-bility distribution of the output conditioned on the input,and the probabilitydistribution is parameterized by the modifiable parameter space, called the neuromanifold, is a family of probability distribu-tions in which the learning process is represented by a trajectory. The stochasticgradient learning method is most popular in on-line learning. However, whenthe parameter space has a Riemannian structure, the gradient does not representthe true steepest direction and should be replaced by the Riemannian or nat-ural gradient. The backprop method is notorious for slow convergence, due toplateaus. Such plateaus are created by the underlying geometrical structure, andthe natural gradient method is shown to have a very good convergence is, however, difficult to calculate the Fisher informationmatrix explicitly andto invert it.

7 We give an adaptive method of obtaining the inverse of the Fisherinformation matrix the neuromanifold is not so strongly curved, the natural gradient is not sodifferent from the ordinary gradient. This suggests that theneuromanifold isstrongly curved. We show many hierarchical structures suchas multilayer per-ceptrons, Gaussian mixtures, ARMA models in time series, etc., include singularpoints in the parameter spaces, where the Fisher information matrix singularities are given rise to by its inner symmetry, and occurs at the pointson which the system parameters become redundant. Model Selection is importantwhen the true system lies in a neighborhood of such , we need to analyze the behaviors of statistical Inference and learning,when the true system lies in a neighborhood of a singular point. The conven-tional Cramer-Rao paradigm does not hold in such a case, because the Fisherinformation is degenerate.

8 The central limit theorem cannot be applied, should remark that Model Selection is important in such asituation, but theconventional theories of AIC and MDL are based on the Cramer-Rao paradigmwhich does not hold. Hence, we need to have a new theoretical paradigm. TheBaysian framework should be also present talk will discuss these aspects of geometry of neuro- manifolds inconnection with learning, Inference and Model Gradient Estimates in Reinforcement Learn-ingPeter BartlettBIOwulf Technologies, consider the problem of controlling a partially observable Markov decisionprocess (POMDP), so as to maximize the time average of a reward parameterized stochastic policies, one approach is to use the gradient of theperformance criterion with respect to the policy parameters. We present al-gorithms to estimate these gradients from a single sample path, by relying onmixing properties of the controlled POMDP.

9 We give bounds onthe estimationand approximation errors fo these estimates for finite samples, in terms of a cer-tain mixing time of the controlled POMDP. The variance of these Monte Carlosestimates can be reduced using additive control variate methods. Two commonlyused approaches, reward baselines and actor-critic algorithms, are special present bounds on the expected error for these algorithms, and derive thebaselines and critics that minimize these bounds. These results allow us to eval-uate how suboptimal commonly used algorithms are, and lead to new algorithmsfor gradient estimates.(joint work with Evan Greensmith and Jonathan Baxter)63 Concentration inequalities and penalization meth-ods in Model selectionStephane BoucheronLaboratorie de Recherche en Informatique,CNRS - Universit e Paris-Sud (FR)Concentration inequalities constitute natural extensions of the classical expo-nential bounds for sums fo independent random variables.

10 (Azuma-Hoeffdings,Bennett, Bernstein). Concentration may be regarded as a new look at inde-pendence . The basic message may be formulated as follows: any function ofmany independent random variables that is smooth in an appropriate sense isalmost constant. The definition of smoothness or alternatively of enlargementof sets, starting from smoothness Hamming distance,to the recent for-mulations by Talagrand, is not straightforward. Such extensions are very usefulwhen trying to characterize the fluctuations of quantities such as empirical VC-dimension, empricial VC-entropies, Rademacher complexities. Those last resultscan be obtained using the relatively transparent entropy method proposed byLedoux - One of the killer applications of the concentrationapproach was thetails of suprema of empirical processes indexed by bounded functions (Talagrand96, Ledoux 97, Massart 2000, Rio 2001) Concentration inequalities deal with thevery topic of the Vapnik-Chervonenkis inequalities.