Dans de nombreux domaines tels que l’apprentissage statistique, la recherche opérationnelle ou encore la conception de circuits, une tâche est modélisée par un jeu de paramètres que l’on cherche à optimiser pour prendre la meilleure décision possible. Mathématiquement, le problème revient à minimiser une fonction de l’objectif recherché par des algorithmes itératifs. Le développement de ces derniers dépend alors de la géométrie de la fonction ou de la structure du problème. Dans une première partie, cette thèse étudie comment l’acuité d’une fonction autour de ses minima peut être exploitée par le redémarrage d’algorithmes classiques. Les schémas optimaux sont présentés pour des problèmes convexes généraux. Ils nécessitent cependant une description complète de la fonction, ce qui est rarement disponible. Des stratégies adaptatives sont donc développées et prouvées être quasi-optimales. Une analyse spécifique est ensuite conduite pour les problèmes parcimonieux qui cherchent des représentations compressées des variables du problème. Leur géométrie conique sous-jacente, qui décrit l’acuité de la fonction de l’objectif, se révèle contrôler à la fois la performance statistique du problème et l’efficacité des procédures d’optimisation par une seule quantité. Une seconde partie est dédiée aux problèmes d’apprentissage statistique. Ceux-ci effectuent une analyse prédictive de données à l’aide d’un large nombre d’exemples. Une approche générique est présentée pour à la fois résoudre le problème de prédiction et le simplifier en groupant soit les variables, les exemples ou les tâches. Des méthodes algorithmiques systématiques sont développées en analysant la géométrie induite par une partition des données. Une analyse théorique est finalement conduite lorsque les variables sont groupées par analogie avec les méthodes parcimonieuses. / In numerous fields such as machine learning, operational research or circuit design, a task is modeled by a set of parameters to be optimized in order to take the best possible decision. Formally, the problem amounts to minimize a function describing the desired objective with iterative algorithms. The development of these latter depends then on the characterization of the geometry of the function or the structure of the problem. In a first part, this thesis studies how sharpness of a function around its minimizers can be exploited by restarting classical algorithms. Optimal schemes are presented for general convex problems. They require however a complete description of the function that is rarely available. Adaptive strategies are therefore developed and shown to achieve nearly optimal rates. A specific analysis is then carried out for sparse problems that seek for compressed representation of the variables of the problem. Their underlying conic geometry, that describes sharpness of the objective, is shown to control both the statistical performance of the problem and the efficiency of dedicated optimization methods by a single quantity. A second part is dedicated to machine learning problems. These perform predictive analysis of data from large set of examples. A generic framework is presented to both solve the prediction problem and simplify it by grouping either features, samples or tasks. Systematic algorithmic approaches are developed by analyzing the geometry induced by partitions of the data. A theoretical analysis is then carried out for grouping features by analogy to sparse methods.

Le déferlement numérique qui caractérise l’ère scientifique moderne a entraîné l’apparition de nouveaux types de données partageant une démesure commune : l’acquisition simultanée et rapide d’un très grand nombre de quantités observables. Qu’elles proviennent de puces ADN, de spectromètres de masse ou d’imagerie par résonance nucléaire, ces bases de données, qualifiées de données de grande dimension, sont désormais omniprésentes, tant dans le monde scientifique que technologique. Le traitement de ces données de grande dimension nécessite un renouvellement profond de l’arsenal statistique traditionnel, qui se trouve inadapté à ce nouveau cadre, notamment en raison du très grand nombre de variables impliquées. En effet, confrontée aux cas impliquant un plus grand nombre de variables que d’observations, une grande partie des techniques statistiques classiques est incapable de donner des résultats satisfaisants. Dans un premier temps, nous introduisons les problèmes statistiques inhérents aux modelés de données de grande dimension. Plusieurs solutions classiques sont détaillées et nous motivons le choix de l’approche empruntée au cours de cette thèse : le paradigme bayésien de sélection de modèles. Ce dernier fait ensuite l’objet d’une revue de littérature détaillée, en insistant sur plusieurs développements récents. Viennent ensuite trois chapitres de contributions nouvelles à la sélection de modèles en grande dimension. En premier lieu, nous présentons un nouvel algorithme pour la régression linéaire bayésienne parcimonieuse en grande dimension, dont les performances sont très bonnes, tant sur données réelles que simulées. Une nouvelle base de données de régression linéaire est également introduite : il s’agit de prédire la fréquentation du musée d’Orsay à l’aide de données vélibs. Ensuite, nous nous penchons sur le problème de la sélection de modelés pour l’analyse en composantes principales (ACP). En nous basant sur un résultat théorique nouveau, nous effectuons les premiers calculs exacts de vraisemblance marginale pour ce modelé. Cela nous permet de proposer deux nouveaux algorithmes pour l’ACP parcimonieuse, un premier, appelé GSPPCA, permettant d’effectuer de la sélection de variables, et un second, appelé NGPPCA, permettant d’estimer la dimension intrinsèque de données de grande dimension. Les performances empiriques de ces deux techniques sont extrêmement compétitives. Dans le cadre de données d’expression ADN notamment, l’approche de sélection de variables proposée permet de déceler sans supervision des ensembles de gènes particulièrement pertinents. / The numerical surge that characterizes the modern scientific era led to the rise of new kinds of data united in one common immoderation: the simultaneous acquisition of a large number of measurable quantities. Whether coming from DNA microarrays, mass spectrometers, or nuclear magnetic resonance, these data, usually called high-dimensional, are now ubiquitous in scientific and technological worlds. Processing these data calls for an important renewal of the traditional statistical toolset, unfit for such frameworks that involve a large number of variables. Indeed, when the number of variables exceeds the number of observations, most traditional statistics becomes inefficient. First, we give a brief overview of the statistical issues that arise with high-dimensional data. Several popular solutions are presented, and we present some arguments in favor of the method utilized and advocated in this thesis: Bayesian model uncertainty. This chosen framework is the subject of a detailed review that insists on several recent developments. After these surveys come three original contributions to high-dimensional model selection. A new algorithm for high-dimensional sparse regression called SpinyReg is presented. It compares favorably to state-of-the-art methods on both real and synthetic data sets. A new data set for high-dimensional regression is also described: it involves predicting the number of visitors in the Orsay museum in Paris using bike-sharing data. We focus next on model selection for high-dimensional principal component analysis (PCA). Using a new theoretical result, we derive the first closed-form expression of the marginal likelihood of a PCA model. This allows us to propose two algorithms for model selection in PCA. A first one called globally sparse probabilistic PCA (GSPPCA) that allows to perform scalable variable selection, and a second one called normal-gamma probabilistic PCA (NGPPCA) that estimates the intrinsic dimensionality of a high-dimensional data set. Both methods are competitive with other popular approaches. In particular, using unlabeled DNA microarray data, GSPPCA is able to select genes that are more biologically relevant than several popular approaches.

La tomographie SAR exploite plusieurs acquisitions d'une même zone acquises d'un point de vue légerement différent pour reconstruire la densité complexe de réflectivité au sol. Cette technique d'imagerie s'appuyant sur l'émission et la réception d'ondes électromagnétiques cohérentes, les données analysées sont complexes et l'information spatiale manquante (selon la verticale) est codée dans la phase. De nombreuse méthodes ont pu être proposées pour retrouver cette information. L'utilisation des redondances naturelles à certains milieux n'est toutefois généralement pas exploitée pour améliorer l'estimation tomographique. Cette thèse propose d'utiliser l'information structurelle propre aux structures urbaines pour régulariser les densités de réflecteurs obtenues par cette technique. / SAR tomography consists in exploiting multiple images from the same area acquired from a slightly different angle to retrieve the 3-D distribution of the complex reflectivity on the ground. As the transmitted waves are coherent, the desired spatial information (along with the vertical axis) is coded in the phase of the pixels. Many methods have been proposed to retrieve this information in the past years. However, the natural redundancies of the scene are generally not exploited to improve the tomographic estimation step. This Ph.D. presents new approaches to regularize the estimated reflectivity density obtained through SAR tomography by exploiting the urban geometrical structures.

L'un des challenges majeurs de la cosmologie moderne réside en la nature même de la matière et de l'énergie noire. La matière noire peut être directement tracée à travers son effet gravitationnel sur les formes des galaxies. La mission Euclid de l'Agence Spatiale Européenne fournira précisément des données à cette fin. L'exploitation de telles données requiert une modélisation précise de la Fonction d'Étalement du Point (FEP) de l'instrument d'observation, ce qui constitue l'objectif de cette thèse.Nous avons développé des méthodes non-paramétriques permettant d'estimer de manière fiable la FEP sur l'ensemble du champ de vue d'un instrument, à partir d'images non résolues d'étoiles, ceci en tenant compte du bruit, d'un possible sous-échantillonnage des observations et de la variabilité spatiale de la FEP. Ce travail tire avantage d'outils et concepts mathématiques modernes parmi lesquelles la parcimonie. Une extension importante de ce travail serait de prendre en compte la dépendance en longueur d'onde de la FEP. / One of the biggest challenges of modern cosmology is to gain a more precise knowledge of the dark energy and the dark matter nature. Fortunately, the dark matter can be traced directly through its gravitational effect on galaxies shapes. The European Spatial Agency Euclid mission will precisely provide data for such a purpose. A critical step is analyzing these data will be to accurately model the instrument Point Spread Function (PSF), which the focus of this thesis.We developed non parametric methods to reliably estimate the PSFs across an instrument field-of-view, based on unresolved stars images and accounting for noise, undersampling and PSFs spatial variability. At the core of these contributions, modern mathematical tools and concepts such as sparsity. An important extension of this work will be to account for the PSFs wavelength dependency.

La nouvelle génération d’instrument d’interféromètre radio, tels que LOFAR et SKA, nous permettra de construire des images radio à haute résolution angulaire et avec une bonne sensibilité. L’un des problèmes majeurs de l’imagerie interférométrie est qu’il s’agit d’un problème inverse mal posé car seulement quelques coefficients de Fourier (visibilités) peuvent être mesurés par un interféromètre radio. La théorie de l’Acquisition Comprimée (Compressed Sensing) nous permet d’envisager ce problème sous un autre angle et son efficacité pour la radioastronomie a été montrée. Cette thèse se concentre sur la méthodologie de la reconstruction de données à l’Acquisition Comprimée Multicanaux et son application en radioastronomie. Par exemple, les transitoires radios sont un domaine de recherche actif en radioastronomie, mais leur détection est un problème difficile en raison de la faible résolution angulaire et des observations à faible rapport signal-sur-bruit. Pour résoudre ce problème, nous avons exploité la parcimonie de l’information temporelle des transitoires radios et nous avons proposé une méthode de reconstruction spatio-temporelle pour détecter efficacement les sources radios. Les expériences ont démontré la force de cette méthode de reconstruction en comparaison avec les méthodes de l’état de l’art. Une deuxième application concerne l’imagerie interférométrie radio à multi-longueur d’onde dans lesquelles les données sont dégradées différemment en termes de longueur d’onde car la réponse instrumentale varie en fonction de la longueur d’onde. Basé sur le modèle de mélange de sources, un nouveau modèle est proposé pour effectuer de manière jointe une Séparation de Sources en Aveugle et une déconvolution (SSAD). Le problème SSAD n’est pas seulement non-convexe mais aussi mal conditionné en raison des noyaux de convolution. Notre méthode proposée DecGMCA, qui utilise un a priori de parcimonie et emploie un scénario de moindre carré alternatif, est un algorithme efficace pour aborder simultanément les problèmes de déconvolution et de SSA. Les expériences ont démontré que notre approche jointe permet d’obtenir de meilleurs résultats comparée à une analyse standard consistant en une application séquentielle d’une déconvolution suivie d’une séparation de sources en aveugle. / The new generation of radio interferometer instruments, such as LOFAR and SKA, will allow us to build radio images with very high angular resolution and sensitivity. One of the major problems in interferometry imaging is that it involves an ill-posed inverse problem, because only a few Fourier components (visibility points) can be acquired by a radio interferometer. Compressed Sensing (CS) theory is a paradigm to solve many underdetermined inverse problems and has shown its strength in radio astronomy. This thesis focuses on the methodology of Multichannel Compressed Sensing data reconstruction and its application in radio astronomy. For instance, radio transients are an active research field in radio astronomy but their detection is a challenging problem because of low angular resolution and low signal-to-noise observations. To address this issue, we investigated the sparsity of temporal information of radio transients and proposed a spatial-temporal sparse reconstruction method to efficiently detect radio sources. Experiments have shown the strength of this sparse recovery method compared to the state-of-the-art methods. A second application is concerned with multi-wavelength radio interferometry imaging in which the data are degraded differently in terms of wavelength due to the wavelength-dependent varying instrumental beam. Based on a source mixture model, a novel Deconvolution Blind Source Separation (DBSS) model is proposed. The DBSS problem is not only non-convex but also ill conditioned due to convolution kernels. Our proposed DecGMCA method, which benefits from a sparsity prior and leverages an alternating projected least squares, is an efficient algorithm to tackle simultaneously the deconvolution and BSS problems. Experiments have shown that taking into account joint deconvolution and BSS gives much better results than applying sequential deconvolution and BSS.

This thesis deals with audio inpainting problem. Firstly, basic concepts are summarized. Then, sparse representation of signals is introduced along with several algorithms. In the main part dedicated to the audio inpainting, the problem is defined and actual methods are presented and compared. The newest approach using the harmonic strucure of sound signals is then introduced, followed by several experiments and evaluation. Lastly, an algorithm ensuring the maximal computational efficiency is derived.

Tato zpráva popisuje  experimentální práci na statistické jazykovém modelování pomocí rekurentních neuronových sítí (RNN). Je zde předložen důkladný přehled dosud publikovaných prací, následovaný popisem algoritmů pro trénování příslušných modelů. Většina z popsaných technik byla implementována ve vlastním nástroji, založeném na knihovně Theano. Byla provedena rozsáhlá sada experimentů s modelem Jednoduché rekurentní sítě (SRN), která odhalila některé jejich dosud nepublikované vlastnosti. Při statické evaluaci modelu byly dosažené výsledky relativně cca. o 2.7 % horší, než nejlepší publikované výsledky. V případě dynamické evaluace však bylo dosaženo relativního zlepšení o 1 %. Dále bylo experimentováno i s modelem Strukturně omezené rekurentní sítě, ale ten se nepodařilo natrénovat k předpokládáným výkonům. Konečně bylo navrženo rozšíření SRN, pojmenované Náhodně prořidlá rekurentní neuronová síť. Experimentálně bylo potvrzeno, že RS-RNN dosahuje lepších výsledků v učení vlastního trénovacího korpusu a kombinace několika RS-RNN modelů přináší o 30 % větší zlepšení než kombinace stejného počtu SRN.

La sélection d’un modèle approprié est l’une des tâches essentielles de l’apprentissage statistique. En général, pour une tâche d’apprentissage donnée, on considère plusieurs classes de modèles ordonnées selon un certain ordre de « complexité». Dans ce cadre, le processus de sélection de modèle revient `a trouver la « complexité » optimale, permettant d’estimer un modèle assurant une bonne généralisation. Ce problème de sélection de modèle se résume à l’estimation d’un ou plusieurs hyper-paramètres définissant la complexité du modèle, par opposition aux paramètres qui permettent de spécifier le modèle dans la classe de complexité choisie. L’approche habituelle pour déterminer ces hyper-paramètres consiste à utiliser une « grille ». On se donne un ensemble de valeurs possibles et on estime, pour chacune de ces valeurs, l’erreur de généralisation du meilleur modèle. On s’intéresse, dans cette thèse, à une approche alternative consistant à calculer l’ensemble des solutions possibles pour toutes les valeurs des hyper-paramètres. C’est ce qu’on appelle le chemin de régularisation. Il se trouve que pour les problèmes d’apprentissage qui nous intéressent, des programmes quadratiques paramétriques, on montre que le chemin de régularisation associé à certains hyper-paramètres est linéaire par morceaux et que son calcul a une complexité numérique de l’ordre d’un multiple entier de la complexité de calcul d’un modèle avec un seul jeu hyper-paramètres. La thèse est organisée en trois parties. La première donne le cadre général des problèmes d’apprentissage de type SVM (Séparateurs à Vaste Marge ou Support Vector Machines) ainsi que les outils théoriques et algorithmiques permettant d’appréhender ce problème. La deuxième partie traite du problème d’apprentissage supervisé pour la classification et l’ordonnancement dans le cadre des SVM. On montre que le chemin de régularisation de ces problèmes est linéaire par morceaux. Ce résultat nous permet de développer des algorithmes originaux de discrimination et d’ordonnancement. La troisième partie aborde successivement les problèmes d’apprentissage semi supervisé et non supervisé. Pour l’apprentissage semi supervisé, nous introduisons un critère de parcimonie et proposons l’algorithme de chemin de régularisation associé. En ce qui concerne l’apprentissage non supervisé nous utilisons une approche de type « réduction de dimension ». Contrairement aux méthodes à base de graphes de similarité qui utilisent un nombre fixe de voisins, nous introduisons une nouvelle méthode permettant un choix adaptatif et approprié du nombre de voisins. / The selection of a proper model is an essential task in statistical learning. In general, for a given learning task, a set of parameters has to be chosen, each parameter corresponds to a different degree of “complexity”. In this situation, the model selection procedure becomes a search for the optimal “complexity”, allowing us to estimate a model that assures a good generalization. This model selection problem can be summarized as the calculation of one or more hyperparameters defining the model complexity in contrast to the parameters that allow to specify a model in the chosen complexity class. The usual approach to determine these parameters is to use a “grid search”. Given a set of possible values, the generalization error for the best model is estimated for each of these values. This thesis is focused in an alternative approach consisting in calculating the complete set of possible solution for all hyperparameter values. This is what is called the regularization path. It can be shown that for the problems we are interested in, parametric quadratic programming (PQP), the corresponding regularization path is piece wise linear. Moreover, its calculation is no more complex than calculating a single PQP solution. This thesis is organized in three chapters, the first one introduces the general setting of a learning problem under the Support Vector Machines’ (SVM) framework together with the theory and algorithms that allow us to find a solution. The second part deals with supervised learning problems for classification and ranking using the SVM framework. It is shown that the regularization path of these problems is piecewise linear and alternative proofs to the one of Rosset [Ross 07b] are given via the subdifferential. These results lead to the corresponding algorithms to solve the mentioned supervised problems. The third part deals with semi-supervised learning problems followed by unsupervised learning problems. For the semi-supervised learning a sparsity constraint is introduced along with the corresponding regularization path algorithm. Graph-based dimensionality reduction methods are used for unsupervised learning problems. Our main contribution is a novel algorithm that allows to choose the number of nearest neighbors in an adaptive and appropriate way contrary to classical approaches based on a fix number of neighbors.

La toxicité et l’efficacité de plus de 30 agents anticancéreux présentent de très fortes variations en fonction du temps de dosage. Par conséquent, les biologistes qui étudient le rythme circadien ont besoin d’une méthode très précise pour estimer le vecteur de composantes périodiques (CP) de signaux chronobiologiques. En outre, dans les développements récents, non seulement la période dominante ou le vecteur de CP présentent un intérêt crucial, mais aussi leurs stabilités ou variabilités. Dans les expériences effectuées en traitement du cancer, les signaux enregistrés correspondant à différentes phases de traitement sont courts, de sept jours pour le segment de synchronisation jusqu’à deux ou trois jours pour le segment après traitement. Lorsqu’on étudie la stabilité de la période dominante nous devons considérer des signaux très court par rapport à la connaissance a priori de la période dominante, placée dans le domaine circadien. Les approches classiques fondées sur la transformée de Fourier (TF) sont inefficaces (i.e. manque de précision) compte tenu de la particularité des données (i.e. la courte longueur). Dans cette thèse, nous proposons une nouvelle méthode pour l’estimation du vecteur de CP des signaux biomédicaux, en utilisant les informations biologiques a priori et en considérant un modèle qui représente le bruit. Les signaux enregistrés dans le cadre d’expériences développées pour le traitement du cancer ont un nombre limité de périodes. Cette information a priori peut être traduite comme la parcimonie du vecteur de CP. La méthode proposée considère l’estimation de vecteur de CP comme un problème inverse enutilisant l’inférence bayésienne générale afin de déduire toutes les inconnues de notre modèle, à savoir le vecteur de CP mais aussi les hyperparamètres (i.e. les variances associées). / The toxicity and efficacy of more than 30 anticancer agents presents very high variations, depending on the dosing time. Therefore the biologists studying the circadian rhythm require a very precise method for estimating the Periodic Components (PC) vector of chronobiological signals. Moreover, in recent developments not only the dominant period or the PC vector present a crucial interest, but also their stability or variability. In cancer treatment experiments the recorded signals corresponding to different phases of treatment are short, from seven days for the synchronization segment to two or three days for the after treatment segment. When studying the stability of the dominant period we have to consider very short length signals relative to the prior knowledge of the dominant period, placed in the circadian domain. The classical approaches, based on Fourier Transform (FT) methods are inefficient (i.e. lack of precision) considering the particularities of the data (i.e. the short length). In this thesis we propose a new method for the estimation of the PC vector of biomedical signals, using the biological prior informations and considering a model that accounts for the noise. The experiments developed in the cancer treatment context are recording signals expressing a limited number of periods. This is a prior information that can be translated as the sparsity of the PC vector. The proposed method considers the PC vector estimation as an Inverse Problem (IP) using the general Bayesian inference in order to infer all the unknowns of our model, i.e. the PC vector but also the hyperparameters.

Ill-posed inverse problems with quadratic structure are introduced, studied and solved. As an example an inverse problem appearing in laser optics is solved numerically based on a new regularized inversion algorithm. In addition, the theory of sparsity promoting regularization is extended to situations in which sparsity cannot be expected and also to equations with non-injective operators.