Optimization and statistical learning theory for piecewise smooth and switching regression
Optimisation et théorie statistique de l'apprentissage pour la régression douce par morceaux et à commutations
Abstract
This manuscript deals with several machine learning problems. More precisely, we study two regression problems involving multiple models: piecewise smooth regression and switching regression. Piecewise smooth regression refers to the case where the target function involves jumps (of values or derivatives) and is usually tackled by learning multiple smooth models and a classifier determining the active model on the basis of the input. Switching regression refers to the case where the target function switches between multiple behaviors arbitrarily (and thus independently of the input). The first part of the document focuses on optimization and computational complexity issues. Here, we try to characterize under which conditions it is possible to exactly minimize the empirical risk of these particular regression models. In the second part, we analyze the generalization performance of the models in the framework of statistical learning theory. The standard tools of this framework are introduced in a chapter dedicated to multi-category classification, which we encounter in piecewise smooth regression and which also shares a number of characteristic features with switching regression regarding the analysis in generalization.
Technically, the first part contains proofs of NP-hardness, polynomial-time exact algorithms for fixed dimensions and a global optimization method with reasonable computing time for moderate dimensions. The second part derives risk bounds by relying on the estimation of Rademacher complexities, structural decomposition lemmas, chaining arguments and covering numbers. The obtained risk bounds are discussed with a particular emphasis on their dependency on the number of component models.
Ce manuscrit s'intéresse à différents problèmes d'apprentissage automatique. En premier lieu, nous nous concentrons sur des problèmes de régression à modèles multiples~: la régression de fonctions lisses par morceaux et la régression à commutations. Deux types de contributions sont exposées. Les premières relèvent des domaines de l'optimisation et de la complexité algorithmique. Ici, on tente de savoir dans quelle mesure il est possible de minimiser exactement l'erreur empirique de modèles de régression dans les différents cadres évoqués plus haut.
Dans une seconde partie, nous tentons de caractériser les performances en généralisation de ces modèles. Cette partie relève de la théorie statistique de l'apprentissage dont les outils sont introduits dans un chapitre traitant de la discrimination multi-classe. Celle-ci apparaît en effet de manière naturelle lorsque l'on définit les fonctions de régression lisses par morceaux au travers d'un ensemble de modèles lisses et d'un classifieur chargé de sélectionner un de ces modèles en fonction de l'entrée. Nous montrons dans ce manuscrit qu'il existe aussi un autre lien en termes du rôle joué dans les bornes sur l'erreur de généralisation par le nombre de catégories en discrimination et par le nombre de modèles en régression.
Techniquement, la première partie contient des preuves de NP-difficulté, des algorithmes exacts polynomiaux par rapport au nombre de données à dimension fixée et une méthode d'optimisation globale à temps raisonnable en dimension modérée. La seconde partie repose sur l'estimation de complexités de Rademacher, au travers de lemmes de décomposition, de chaînage "à la Dudley" et de nombres de couverture. Les bornes obtenues dans cette dernière partie sont discutées avec une attention particulière à leur dépendance au nombre de catégories ou de modèles.
Origin | Files produced by the author(s) |
---|
Loading...