Statistical Learning Theory and Stochastic Optimization: Ecole d'Eté de Probabilités de Saint-Flour XXXI- 2001 (Lecture Notes in Mathematics, Vol. 1851) (Lecture Notes in Mathematics, 1851)

Statistical Learning Theory Is Aimed At Analyzing Complex Data With Necessarily Approximate Models. This Book Is Intended For An Audience With A Graduate Background In Probability Theory And Statistics. It Will Be Useful To Any Reader Wondering Why It May Be A Good Idea, To Use As Is Often Done In Practice A Notoriously Wrong'' (i.e. Over-simplified) Model To Predict, Estimate Or Classify. This Point Of View Takes Its Roots In Three Fields: Information Theory, Statistical Mechanics, And Pac-bayesian Theorems. Results On The Large Deviations Of Trajectories Of Markov Chains With Rare Transitions Are Also Included. They Are Meant To Provide A Better Understanding Of Stochastic Optimization Algorithms Of Common Use In Computing Estimators. The Author Focuses On Non-asymptotic Bounds Of The Statistical Risk, Allowing One To Choose Adaptively Between Rich And Structured Families Of Models And Corresponding Estimators. Two Mathematical Objects Pervade The Book: Entropy And Gibbs Measures. The Goal Is To Show How To Turn Them Into Versatile And Efficient Technical Tools, That Will Stimulate Further Studies And Results. Universal Lossless Data Compression -- Links Between Data Compression And Statistical Estimation -- Non Cumulated Mean Risk -- Gibbs Estimators -- Randomized Estimators And Empirical Complexity -- Deviation Inequalities -- Markov Chains With Exponential Transitions -- References -- Index. Olivier Catoni ; Editor, Jean Picard. ... Lectures Were Given At The 31st Probability Summer School In Saint-flour (july 8-25, 2001) ... --pref. Includes Bibliographical References (p. [261]-265) And Index. 1.1 A link between coding and estimation 1.1.1 Coding and Shannon entropy 1.1.2 Instantaneous codes 1.2 Universal coding and mixture codes 1.2.1 The Bayesian approach 1.2.2 The minimax approach 1.3 Lower bounds for the minimax compression rate 1.4 Mixtures of i.i.d. coding distributions 1.5 Double mixtures and adaptive compression 1.5.1 General principle 1.5.2 The context tree weighting coding distribution 1.5.3 Context tree weighting without initial context 1.5.4 Weighting of trees of arbitrary depth Appendix 1.6 Fano’s lemma 1.7 Decomposition of the Kullback divergence function 2.1 Estimating a conditional probability distribution with respect to the Kullback divergence 2.2 Least square regression 2.3 Pattern recognition 2.3.1 Prediction from classification trees 2.3.2 Noisy non ambiguous classification 2.3.3 Non randomized classification rules 3.1 The progressive mixture rule 3.1.1 Estimation of a conditional density 3.1.2 Some variants of the progressive mixture estimator 3.2 Estimating a Bernoulli random variable 3.2.1 The Laplace estimator 3.2.2 Some adaptive Laplace estimator 3.3 Adaptive histograms 3.4 Some remarks on approximate Monte-Carlo computations 3.5 Selection and aggregation : a toy example pointing out some differences 3.6 Least square regression 3.7 Adaptive regression estimation in Besov spaces 4.1 General framework 4.2 Dichotomic histograms 4.3 Mathematical framework for density estimation 4.4 Main oracle inequality 4.5 Checking the accuracy of the bounds on the Gaussian shift model 4.6 Application to adaptive classification 4.6.1 Randomized classification rule, general case 4.6.2 Randomized classification rule for “non-ambiguous” classification problems 4.6.3 Deterministic classification rule 4.6.4 Counter example 4.7 Two stage adaptive least square regression 4.8 One stage piecewise constant regression 4.9 Some abstract inference problem 4.10 Another type of bound 5.1 A pseudo-Bayesian approach to adaptive inference 5.1.1 General framework 5.1.2 Some pervading ideas 5.2 A randomized rule for pattern recognition 5.3 Generalizations of theorem 5.2.3 5.4 The non-ambiguous case 5.5 Empirical complexity bounds for the Gibbs estimator 5.6 Non randomized classification rules 5.7 Application to classification trees 5.8 The regression setting 5.9 Links with penalized least square regression 5.9.1 The general case 5.9.2 Adaptive linear least square regression estimation 5.10 Some elementary bounds 5.11 Some refinements about the linear regression case Introduction 6.1 Bounded range functionals of independent variables 6.2 Extension to unbounded ranges 6.3 Generalization to Markov chains Conclusion 7.1 Model definition 7.2 The reduction principle 7.3 Larve deviation estimates for the excursions from a domain 7.4 Fast reduction algorithm 7.5 Elevation function and cycle decomposition 7.6 Mean hitting times and ordered reduction 7.7 Convergence speeds 7.8 Generalized simulated annealing algorithm List of participants List of short lectures Blank Page Blank Page Blank Page Blank Page Statistical learning theory is aimed at analyzing complex data with necessarily approximate models. This book is intended for an audience with a graduate background in probability theory and statistics. It will be useful to any reader wondering why it may be a good idea, to use asis often done in practice a notoriously "wrong'' (i.e. over-simplified) model to predict, estimate or classify. This point of view takes its roots in three fields: information theory, statistical mechanics, and PAC-Bayesian theorems. Results on the large deviations of trajectories of Markov chains with rare transitions are also included. They are meant to provide a better understanding of stochastic optimization algorithms of common use in computing estimators. The author focuses on non-asymptotic bounds of the statistical risk, allowing one to choose adaptively between rich and structured families of models and corresponding estimators. Two mathematical objects pervade the book: entropy and Gibbs measures. The goal is to show how to turn them into versatile and efficient technical tools,that will stimulate further studies and results. TOC:Universal Lossless Data Compression.- Links Between Data Compression and Statistical Estimation.- Non Cumulated Mean Risk.- Gibbs Estimators.- Randomized Estimators and Empirical Complexity.- Deviation Inequalities.- Markov Chains with Exponential Transitions.- References.- Index We consider in this chapter a finite set E, called in this context the alphabet, and a E valued random process (Xn)n?N.