Search

Despite the attractive qualities of convolutional neural networks (CNNs), and the universality of architectures emerging now, CNNs are still prohibitive regarding environmental impact due to electric consumption or carbon footprint, as well as deployment in constrained platform such as microcomputers. We address this problem and sketch how PAC-Bayesian theory can be applied to learn lighter

The introduction of the Kullback-Leibler divergence in PAC-Bayesian theory can be traced back to the work of [1]. It allows to design learning procedure with generalization errors based on an optimal trade-off between accuracy on the training set, and complexity. This complexity is penalized thanks to the Kullback-Leibler divergence from a prior distribution, modeling a domain knowledge over the set of candidates or weak learners. In the context of high dimensional statistics, it gives rise to sparsity oracle inequalities or more recently sparsity regret bounds, where the complexity is measured thanks to 0 or 1 −norms. In this paper, we propose to extend the PAC-Bayesian theory to get more generic regret bounds for sequential weighted averages, where (1) the measure of complexity is based on any ad-hoc criterion and (2) the prior distribution could be very simple. These results arise by introducing a new measure of divergences from the prior in terms of Bregman divergence or Optimal Transport.

We consider the problem of clustering when we observe a corrupted sample. We test two bandwidth selection methods. It allows to deal with the isotropic and the anisotropic problem of selecting the bandwidth of a deconvolution kernel. These methods are based on Lepski's type procedure. The first method compares empirical risks associated with different bandwidths by using ICI (Intersection of Confidence Intervals) rule whereas the second one computes the gradient of the empirical risk and allows us to construct an anisotropic data-driven bandwidth. Numerical experiments are proposed to illustrate the efficiency of the methods.

The effect of errors in variables in quantization is investigated. Given a noisy sample $Z_i=X_i+\epsilon_i,i=1,\ldots,n$, where $(X_i)_{i=1, \ldots ,n}$ are i.i.d. with law $P$, we want to find the best approximation of the probability distribution $P$ with $k\geq 1$ points called codepoints. We prove general excess risk bounds with fast rates for an empirical minimization based on a deconvolution kernel estimator. These rates depend on the behaviour of the density of $P$ and the asymptotic behaviour of the characteristic function of the noise $\epsilon$. This general study can be applied to the problem of $k$-means clustering with noisy data. For this purpose, we introduce a deconvolution $k$-means stochastic minimization which reaches fast rates of convergence under standard Pollard's regularity assumptions. We also introduce a new algorithm to deal with $k$-means clustering with errors in variables. Following the theoretical study, the algorithm mixes different tools from the inverse problem literature and the machine learning community. Coarsely, it is based on a two-step procedure: (1) a deconvolution step to deal with noisy inputs and (2) Newton's iterations as the popular $k$-means.

We know that $\ell_0$-penalized methods have good theoretical properties but unfortunately high computational cost. On the contrary, convex relaxations - such as the Lasso - have been introduced but their theoretical guarantees hold for restricted models. To tackle this impasse, \cite{dalalyantsybakov2,dalalyantsybakov3} come up with sparsity priors in a Pac-Bayesian framework. They give rise to good theoretical properties, i.e. sparsity oracle inequalities, reached by computationally attractive sequential procedures. In this paper, we investigate this issue in clustering. We construct online \textit{clustering} algorithms which learn according to the following game protocol. At each trial $t\geq 1$, nature reveals a deterministic $x_t\in\R^d$, $d\geq 1$. A forecaster predicts the next value with several - and as small as possible - proposals. Then, nature reveals the next value and the forecaster pays the minimal distance between this value and its set of proposals. To deal with this problem, we use the Pac-Bayesian theory with group-sparsity priors. It gives sparsity regret bounds and allows us to perform online clustering of a possible non-stationnary process, without any knowledge about the number of clusters. These results can be applied to the classical i.i.d. case to deal with the problem of model selection clustering as well as high dimensional clustering.

Nous nous intéressons dans ce travail à la construction et à la mise en oeuvre d'une méthode de clustering en ligne. Face à des flux de données massives, le clustering est une gageure tant d'un point de vue théorique qu'algorithmique. Nous proposons un nouvel algorithme de clustering en ligne, reposant sur l'approche PAC-bayésienne. En particulier, le nombre de clusters est estimé dynamiquement (c'est-à-dire qu'il peut changer au cours du temps), et nous démontrons des bornes de regret parcimonieuses. De plus, un algorithme via RJMCMC, appelé Paco est présenté, et ses performances sur données simulées seront commentées. Mots-clés. Bornes de regret parcimonieuses, Clustering en ligne, Reversible Jump MCMC, Théorie PAC-bayésienne. Abstract. We address the online clustering problem. When faced with high frequency streams of data, clustering raises theoretical and algorithmic pitfalls. Working under a sparsity assumption, a new online clustering algorithm is introduced. Our procedure relies on the PAC-Bayesian approach, allowing for a dynamic (i.e., time-dependent) estimation of the number of clusters. Its theoretical merits are supported by sparsity regret bounds, and an RJMCMC-flavored implementation called Paco is proposed along with numerical experiments to assess its potential.

This manuscript studies the statistical performances of kernel methods to solve the binary classification problem. We observe an independent and identically distributed (i.i.d.) sequence of random pairs $(X_i,Y_i)$, $i=1,\ldots ,n$ of unknown probability distribution $P$ over $\mathcal{X}\times \{-1,+1\}$. The aim is to learn, from a new observation $X$, the corresponding class $Y\in\{-1,+1\}$ where $(X,Y)\sim P$. A well-known minimizer of the generalization error $R(f)=P(f(X)\not= Y)$ is called the Bayes rule. The present work proposes to give rates of convergence to the Bayes for SVM-type minimization. We also study a new procedure of model selection called the Risk Hull Minimization. Kernel methods are based on the minimization of an empirical risk and a regularizer. Support Vector Machines is one of the most classical representant. In a first time, we propose learning rates for this algorithm and consider the problem of adaptation to the margin and to the complexity. We also provide a new procedure of penalized empirical risk minimization using Besov spaces as hypothesis spaces. Finally we study a new method of model selection called the Risk Hull Minimization. We use this procedure in binary classification to select the bandwidth of a KPM classifier and give statistical performances in terms of oracle inequality., Cette thèse se concentre sur le modèle de classification binaire. Etant donné $n$ couples de variables aléatoires indépendantes et identiquement distribuées (i.i.d.) $(X_i,Y_i)$, $i=1,\ldots ,n$ de loi $P$, on cherche à prédire la classe $Y\in\{-1,+1\}$ d'une nouvelle entrée $X$ où $(X,Y)$ est de loi $P$. La règle de Bayes, notée $f^*$, minimise l'erreur de généralisation $R(f)=P(f(X)\not=Y)$. Un algorithme de classification doit s'approcher de la règle de Bayes. Cette thèse suit deux axes : établir des vitesses de convergence vers la règle de Bayes et proposer des procédures adaptatives.Les méthodes de régularisation ont montrées leurs intérêts pour résoudre des problèmes de classification. L'algorithme des Machines à Vecteurs de Support (SVM) est aujourd'hui le représentant le plus populaire. Dans un premier temps, cette thèse étudie les performances statistiques de cet algorithme, et considère le problème d'adaptation à la marge et à la complexité. On étend ces résultats à une nouvelle procédure de minimisation de risque empirique pénalisée sur les espaces de Besov. Enfin la dernière partie se concentre sur une nouvelle procédure de sélection de modèles : la minimisation de l'enveloppe du risque (RHM). Introduite par L.Cavalier et Y.Golubev dans le cadre des problèmes inverses, on cherche à l'appliquer au contexte de la classification.

This manuscript studies the statistical performances of kernel methods to solve the binary classification problem. We observe an independent and identically distributed (i.i.d.) sequence of random pairs $(X_i,Y_i)$, $i=1,\ldots ,n$ of unknown probability distribution $P$ over $\mathcal{X}\times \{-1,+1\}$. The aim is to learn, from a new observation $X$, the corresponding class $Y\in\{-1,+1\}$ where $(X,Y)\sim P$. A well-known minimizer of the generalization error $R(f)=P(f(X)\not= Y)$ is called the Bayes rule. The present work proposes to give rates of convergence to the Bayes for SVM-type minimization. We also study a new procedure of model selection called the Risk Hull Minimization. Kernel methods are based on the minimization of an empirical risk and a regularizer. Support Vector Machines is one of the most classical representant. In a first time, we propose learning rates for this algorithm and consider the problem of adaptation to the margin and to the complexity. We also provide a new procedure of penalized empirical risk minimization using Besov spaces as hypothesis spaces. Finally we study a new method of model selection called the Risk Hull Minimization. We use this procedure in binary classification to select the bandwidth of a KPM classifier and give statistical performances in terms of oracle inequality.; Cette thèse se concentre sur le modèle de classification binaire. Etant donné $n$ couples de variables aléatoires indépendantes et identiquement distribuées (i.i.d.) $(X_i,Y_i)$, $i=1,\ldots ,n$ de loi $P$, on cherche à prédire la classe $Y\in\{-1,+1\}$ d'une nouvelle entrée $X$ où $(X,Y)$ est de loi $P$. La règle de Bayes, notée $f^*$, minimise l'erreur de généralisation $R(f)=P(f(X)\not=Y)$. Un algorithme de classification doit s'approcher de la règle de Bayes. Cette thèse suit deux axes : établir des vitesses de convergence vers la règle de Bayes et proposer des procédures adaptatives.Les méthodes de régularisation ont montrées leurs intérêts pour résoudre des problèmes de classification. L'algorithme des Machines à Vecteurs de Support (SVM) est aujourd'hui le représentant le plus populaire. Dans un premier temps, cette thèse étudie les performances statistiques de cet algorithme, et considère le problème d'adaptation à la marge et à la complexité. On étend ces résultats à une nouvelle procédure de minimisation de risque empirique pénalisée sur les espaces de Besov. Enfin la dernière partie se concentre sur une nouvelle procédure de sélection de modèles : la minimisation de l'enveloppe du risque (RHM). Introduite par L.Cavalier et Y.Golubev dans le cadre des problèmes inverses, on cherche à l'appliquer au contexte de la classification.

In this paper, we deal with the data-driven selection of multidimensional and possibly anisotropic bandwidths in the general framework of kernel empirical risk minimization. We propose a universal selection rule, which leads to optimal adaptive results in a large variety of statistical models such as nonparametric robust regression and statistical learning with errors in variables. These results are stated in the context of smooth loss functions, where the gradient of the risk appears as a good criterion to measure the performance of our estimators. The selection rule consists of a comparison of gradient empirical risks. It can be viewed as a nontrivial improvement of the so-called Goldenshluger-Lepski method to nonlinear estimators. Furthermore, one main advantage of our selection rule is the nondependency on the Hessian matrix of the risk, usually involved in standard adaptive procedures., Comment: Published at http://dx.doi.org/10.1214/15-AOS1318 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The problem of adaptive noisy clustering is investigated. Given a set of noisy observations $Z_i=X_i+\epsilon_i$, $i=1,...,n$, the goal is to design clusters associated with the law of $X_i$'s, with unknown density $f$ with respect to the Lebesgue measure. Since we observe a corrupted sample, a direct approach as the popular {\it $k$-means} is not suitable in this case. In this paper, we propose a noisy $k$-means minimization, which is based on the $k$-means loss function and a deconvolution estimator of the density $f$. In particular, this approach suffers from the dependence on a bandwidth involved in the deconvolution kernel. Fast rates of convergence for the excess risk are proposed for a particular choice of the bandwidth, which depends on the smoothness of the density $f$. Then, we turn out into the main issue of the paper: the data-driven choice of the bandwidth. We state an adaptive upper bound for a new selection rule, called ERC (Empirical Risk Comparison). This selection rule is based on the Lepski's principle, where empirical risks associated with different bandwidths are compared. Finally, we illustrate that this adaptive rule can be used in many statistical problems of $M$-estimation where the empirical risk depends on a nuisance parameter., Comment: 22 pages

The Quantitative Trait Loci (QTL) mapping of plant architecture is a critical step for understanding the genetic determinism of plant architecture. Previous studies adopted simple measurements, such as plant-height, stem-diameter and branching-intensity for QTL mapping of plant architecture. Many of these quantitative traits were generally correlated to each other, which give rise to statistical problem in the detection of QTL. We aim to test the applicability of kernel methods to phenotyping inflorescence architecture and its QTL mapping. We first test Kernel Principal Component Analysis (KPCA) and Support Vector Machines (SVM) over an artificial dataset of simulated inflorescences with different types of flower distribution, which is coded as a sequence of flower-number per node along a shoot. The ability of discriminating the different inflorescence types by SVM and KPCA is illustrated. We then apply the KPCA representation to the real dataset of rose inflorescence shoots (n=1460) obtained from a 98 F-1 hybrid mapping population. We find kernel principal components with high heritability ( > 0.7), and the QTL analysis identifies a new QTL, which was not detected by a trait-by-trait analysis of simple architectural measurements. The main tools developed in this paper could be use to tackle the general problem of QTL mapping of complex (sequences, 3D structure, graphs) phenotypic traits. (C) 2013 Elsevier Ltd. All rights reserved.

The effect of errors in variables in quantization is investigated. We prove general exact and non-exact oracle inequalities with fast rates for an empirical minimization based on a noisy sample $Z_i=X_i+\epsilon_i,i=1,\ldots,n$, where $X_i$ are i.i.d. with density $f$ and $\epsilon_i$ are i.i.d. with density $\eta$. These rates depend on the geometry of the density $f$ and the asymptotic behaviour of the characteristic function of $\eta$. This general study can be applied to the problem of $k$-means clustering with noisy data. For this purpose, we introduce a deconvolution $k$-means stochastic minimization which reaches fast rates of convergence under standard Pollard's regularity assumptions., Comment: 30 pages. arXiv admin note: text overlap with arXiv:1205.1417