La modélisation de la langue naturelle est l¿un des défis fondamentaux de l¿intelligence artificielle et de la conception de systèmes interactifs, avec applications dans les systèmes de dialogue, la génération de texte et la traduction automatique. Nous proposons un modèle log-linéaire discriminatif donnant la distribution des mots qui suivent un contexte donné. En raison de la parcimonie des données, nous proposons un terme de pénalité qui code correctement la structure de l¿espace fonctionnel pour éviter le sur-apprentissage et d¿améliorer la généralisation, tout en capturant de manière appropriée les dépendances à long terme. Le résultat est un modèle efficace qui capte suffisamment les dépendances longues sans occasionner une forte augmentation des ressources en espace ou en temps. Dans un modèle log-linéaire, les phases d¿apprentissage et de tests deviennent de plus en plus chères avec un nombre croissant de classes. Le nombre de classes dans un modèle de langue est la taille du vocabulaire, qui est généralement très importante. Une astuce courante consiste à appliquer le modèle en deux étapes: la première étape identifie le cluster le plus probable et la seconde prend le mot le plus probable du cluster choisi. Cette idée peut être généralisée à une hiérarchie de plus grande profondeur avec plusieurs niveaux de regroupement. Cependant, la performance du système de classification hiérarchique qui en résulte dépend du domaine d¿application et de la construction d¿une bonne hiérarchie. Nous étudions différentes stratégies pour construire la hiérarchie des catégories de leurs observations. / Modeling natural language is among fundamental challenges of artificial intelligence and the design of interactive machines, with applications spanning across various domains, such as dialogue systems, text generation and machine translation. We propose a discriminatively trained log-linear model to learn the distribution of words following a given context. Due to data sparsity, it is necessary to appropriately regularize the model using a penalty term. We design a penalty term that properly encodes the structure of the feature space to avoid overfitting and improve generalization while appropriately capturing long range dependencies. Some nice properties of specific structured penalties can be used to reduce the number of parameters required to encode the model. The outcome is an efficient model that suitably captures long dependencies in language without a significant increase in time or space requirements. In a log-linear model, both training and testing become increasingly expensive with growing number of classes. The number of classes in a language model is the size of the vocabulary which is typically very large. A common trick is to cluster classes and apply the model in two-steps; the first step picks the most probable cluster and the second picks the most probable word from the chosen cluster. This idea can be generalized to a hierarchy of larger depth with multiple levels of clustering. However, the performance of the resulting hierarchical classifier depends on the suitability of the clustering to the problem. We study different strategies to build the hierarchy of categories from their observations.

Pour réduire le temps d'acquisition ou bien améliorer la résolution spatio-temporelle dans certaines application en IRM, de puissantes techniques parallèles utilisant plusieurs antennes réceptrices sont apparues depuis les années 90. Dans ce contexte, les images d'IRM doivent être reconstruites à partir des données sous-échantillonnées acquises dans le "k-space". Plusieurs approches de reconstruction ont donc été proposées dont la méthode SENSitivity Encoding (SENSE). Cependant, les images reconstruites sont souvent entâchées par des artéfacts dus au bruit affectant les données observées, ou bien à des erreurs d'estimation des profils de sensibilité des antennes. Dans ce travail, nous présentons de nouvelles méthodes de reconstruction basées sur l'algorithme SENSE, qui introduisent une régularisation dans le domaine transformé en ondelettes afin de promouvoir la parcimonie de la solution. Sous des conditions expérimentales dégradées, ces méthodes donnent une bonne qualité de reconstruction contrairement à la méthode SENSE et aux autres techniques de régularisation classique (e.g. Tikhonov). Les méthodes proposées reposent sur des algorithmes parallèles d'optimisation permettant de traiter des critères convexes, mais non nécessairement différentiables contenant des a priori parcimonieux. Contrairement à la plupart des méthodes de reconstruction qui opèrent coupe par coupe, l'une des méthodes proposées permet une reconstruction 4D (3D + temps) en exploitant les corrélations spatiales et temporelles. Le problème d'estimation d'hyperparamètres sous-jacent au processus de régularisation a aussi été traité dans un cadre bayésien en utilisant des techniques MCMC. Une validation sur des données réelles anatomiques et fonctionnelles montre que les méthodes proposées réduisent les artéfacts de reconstruction et améliorent la sensibilité/spécificité statistique en IRM fonctionnelle.

.

.

L'objectif de cette thèse est de développer une nouvelle méthodologie pour la détection active de défaillances, basée sur approche multimodèle et robuste des fautes. Ce travail prolonge des recherches effectuées dans le projet Metalau de l'Inria. L'apport essentiel de cette thèse est la prise en compte de modèles évoluant en boucle fermée. On utilise une approche multi-modèle pour modéliser le modèle en fonctionnement normal et le modèle défaillant. Les avantages potentiels de l'utilisation d'un feedback dynamique linéaire et ses propriétés de robustesse sont analysés dans la construction de signaux de détection auxiliaires. On compare les résultats obtenus avec ceux du cas boucle ouverte. La formulation du problème de détection active dans le cas d'un modèle en boucle fermée est nouvelle et repose sur la prise en considération de la norme du signal de détection auxiliaire comme critère d'optimisation. On considère aussi des fonctions coût plus générales, telles celles qui sont utilisées pour mesurer la performance de feedbacks dans des problèmes de la théorie de la commande linéaire robuste. La solution complète repose sur la résolution de plusieurs problèmes d'optimisation non standards / The aim is to develop a novel theory of robust active failure detection based on multi-model formulation of faults. The original method was already proposed by the Metalau group of INRIA. We have continued to work on the extension of this approach to more general cases. The focus is on the effects of feedback on the previous approach. The multi-model approach is still used to model the normal and the failed systems; however the possible advantages of using linear dynamic feedback in the construction of the auxiliary signal for robust fault detection is considered and the results are compared to the previously developed open-loop setup. An original formulation of the active fault detection problem using feedback is developed. The norm of the auxiliary signal is considered as a possible cost criterion. Also, we have considered a more general cost function that has already been used for measuring the performance of feedback configurations in Linear Control Theory. We have given a complete solution to this problem. In order to find a complete solution, several mathematical problems are solved

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

L'objectif de cette thèse est de proposer des méthodes fiables, efficaces et rapides pour minimiser des critères convexes apparaissant dans la résolution de problèmes inverses en imagerie. Ainsi, nous nous intéresserons à des problèmes de restauration/reconstruction lorsque les données sont dégradées par un opérateur linéaire et un bruit qui peut être non additif. La fiabilité de la méthode sera assurée par l'utilisation d'algorithmes proximaux dont la convergence est garantie lorsqu'il s'agit de minimiser des critères convexes. La quête d'efficacité impliquera le choix d'un critère adapté aux caractéristiques du bruit, à l'opérateur linéaire et au type d'image à reconstruire. En particulier, nous utiliserons des termes de régularisation basés sur la variation totale et/ou favorisant la parcimonie des coefficients du signal recherché dans une trame. L'utilisation de trames nous amènera à considérer deux approches : une formulation du critère à l'analyse et une formulation du critère à la synthèse. De plus, nous étendrons les algorithmes proximaux et leurs preuves de convergence aux cas de problèmes inverses multicomposantes. La recherche de la rapidité de traitement se traduira par l'utilisation d'algorithmes proximaux parallélisables. Les résultats théoriques obtenus seront illustrés sur différents types de problèmes inverses de grandes tailles comme la restauration d'images mais aussi la stéréoscopie, l'imagerie multispectrale, la décomposition en composantes de texture et de géométrie. Une application attirera plus particulièrement notre attention ; il s'agit de la reconstruction de l'activité dynamique en Tomographie par Emission de Positrons (TEP) qui constitue un problème inverse difficile mettant en jeu un opérateur de projection et un bruit de Poisson dégradant fortement les données observées. Pour optimiser la qualité de reconstruction, nous exploiterons les caractéristiques spatio-temporelles de l'activité dans les tissus / The objective of this work is to propose reliable, efficient and fast methods for minimizing convex criteria, that are found in inverse problems for imagery. We focus on restoration/reconstruction problems when data is degraded with both a linear operator and noise, where the latter is not assumed to be necessarily additive.The methods reliability is ensured through the use of proximal algorithms, the convergence of which is guaranteed when a convex criterion is considered. Efficiency is sought through the choice of criteria adapted to the noise characteristics, the linear operators and the image specificities. Of particular interest are regularization terms based on total variation and/or sparsity of signal frame coefficients. As a consequence of the use of frames, two approaches are investigated, depending on whether the analysis or the synthesis formulation is chosen. Fast processing requirements lead us to consider proximal algorithms with a parallel structure. Theoretical results are illustrated on several large size inverse problems arising in image restoration, stereoscopy, multi-spectral imagery and decomposition into texture and geometry components. We focus on a particular application, namely Positron Emission Tomography (PET), which is particularly difficult because of the presence of a projection operator combined with Poisson noise, leading to highly corrupted data. To optimize the quality of the reconstruction, we make use of the spatio-temporal characteristics of brain tissue activity

Ce manuscrit est structuré en deux parties. La première partie composée des chapitres 2à 4 aborde le problème d'estimation du nombre de classes dans une population avec une application en écologie. La deuxième partie, correspondant au chapitre 5,concerne la mise en oeuvre de méthodes statistiques pour analyser des données de pêche. Dans la première partie, nous considérons une population hétérogène subdiviséeen plusieurs classes. À partir d'un échantillon, les effectifs d'individus observés parclasse, encore appelés abondances, sont utilisés pour estimer le nombre total declasses dans la population. Dans la littérature consacrée à l'estimation du nombrede classes, les méthodes basées sur un mélange de distributions de Poisson semblentêtre les plus performantes (voir par exemple les travaux de Chao and Bunge (2002)dans le cadre paramétrique et celui de Wang and Lindsay (2005) dans un cadrenon paramétrique). La mise en oeuvre de ces approches sur des données réellesmet en évidence que la distribution des abondances peut être approchée par unedistribution convexe. Nous proposons une approche non paramétrique pour estimerla distribution des abondances sous contrainte de convexité. Cette contrainte définitun cadre théorique d'estimation d'une densité discrète. Le problème d'estimation dunombre de classes est donc abordé en deux volets. Nous montrons d'une part l'existenceet l'unicité d'un estimateur d'une densité discrète sous la contrainte de convexité.Sous cette contrainte, nous démontrons qu'une densité discrète s'écrit comme un mélange de densités triangulaires. À partir de l'algorithme de réduction du supportproposé par Groeneboom et al. (2008), nous proposons un algorithme exact pourestimer les proportions dans le mélange. D'autre part, la procédure d'estimationd'une densité discrète convexe nous sert de cadre pour l'estimation de la distributiontronquée en zéro des observations d'abondance. L'estimation de la loi tronquée obtenue est ensuite prolongée en zéro pour estimer la probabilité qu'une classe ne soit pasobservée. Ce prolongement en zéro est fait de façon à annuler la proportion dela première composante dans le mélange de densités triangulaires. Nousaboutissons à une estimation du nombre de classes à l'aide d'un modèle binomial ensupposant que chaque classe apparaît dans un échantillon par une épreuve deBernoulli. Nous montrons la convergence en loi de l'estimateur proposé. Sur le plan pratique, une application aux données réelles en écologie est présentée. La méthode est ensuite comparée à d'autres méthodes concurrentes à l'aide de simulations. La seconde partie présente l'analyse des données de pêche collectées dans le fleuveOuémé au Bénin. Nous proposons une démarche statistique permettant de regrouperles espèces selon leur profil temporel d'abondances, d'estimer le stock d'une espèceainsi que leur capturabilité par les engins de pêche artisanale. / This manuscript is structured in two parts. The #rst part composed of Chapters 2to 4 deals with the problem of estimating the number of classes in a population withan application in ecology. The second part, corresponding to Chapter 5, concernsthe application of statistical methods to analyze fisheries data.In the first part, we consider a heterogeneous population split into several classes.From a sample, the numbers of observed individuals per class, also called abun-dances, are used to estimate the total number of classes in the population. In theliterature devoted to the number of classes estimation, methods based on a mix-ture of Poisson distributions seem to be the most effcient (see for example the workof Chao and Bunge (2002) in the parametric framework and that of Wang and Lind-say (2005) in a non-parametric framework). Applications of these approaches to realdata show that the distribution of abundances can be approximated by a convexdistribution. We propose a non-parametric approach to estimate the distribution ofabundances under the constraint of convexity. This constraint defines a theoreticalframework for estimating a discrete density. The problem of estimating the numberof classes is then tackled in two steps.We show on the one hand the existence and uniqueness of an estimator of adiscrete density under the constraint of convexity. Under this constraint, we provethat a discrete density can be written as a mixture of triangular distributions. Usingthe support reduction algorithm proposed by Groeneboom et al. (2008), we proposean exact algorithm to estimate the proportions in the mixture.On the other hand, the estimation procedure of a discrete convex density is usedto estimate the zero-truncated distribution of the observed abundance data. Thezero-truncated distribution estimate is then extended at zero to derive an estimateof the probability that a class is not observed. This extension is made so as tocancel the first component in the mixture of triangular distributions. An estimateof the total number of classes is obtained through a binomial model assuming thateach class appears in a sample by a Bernoulli trial. We show the convergence inlaw of the proposed estimator. On practical view, an application to real ecologicaldata is presented. The method is then compared to other concurrent methods usingsimulations.The second part presents the analysis of fisheries data collected on the Ouémériver in Benin. We propose a statistical approach for grouping species accordingto their temporal abundance profile, to estimate the stock of a species and theircatchability by artisanal fishing gears.

Dans la première partie de cette thèse, on présente des inégalités de concentration convexe pour des intégrales stochastiques. Ces résultats sont obtenus par calcul stochastique e tpar calcul de Malliavin forward/backward. On présente également des inégalités de déviation pour les exponentielles martingales à saut.Dans une deuxième partie on présente des théorèmes limites pour le conditionnement du mouvement brownien. / In the first part of this thesis, we present some convex concentration inequalities for stochastic integrals. These results are obtained by forward/backward stochastic calculus combined with Malliavin calculus. We also present deviation inequalities for exponentialjump-diffusion.In the second part, we present some limit theorems for the conditionning of Brownian motion.

Ces dernières années, l'importance cruciale des métriques en apprentissage automatique a mené à un intérêt grandissant pour l'optimisation de distances et de similarités en utilisant l'information contenue dans des données d'apprentissage pour les rendre adaptées au problème traité. Ce domaine de recherche est souvent appelé apprentissage de métriques. En général, les méthodes existantes optimisent les paramètres d'une métrique devant respecter des contraintes locales sur les données d'apprentissage. Les métriques ainsi apprises sont généralement utilisées dans des algorithmes de plus proches voisins ou de clustering.Concernant les données numériques, beaucoup de travaux ont porté sur l'apprentissage de distance de Mahalanobis, paramétrisée par une matrice positive semi-définie. Les méthodes récentes sont capables de traiter des jeux de données de grande taille.Moins de travaux ont été dédiés à l'apprentissage de métriques pour les données structurées (comme les chaînes ou les arbres), car cela implique souvent des procédures plus complexes. La plupart des travaux portent sur l'optimisation d'une notion de distance d'édition, qui mesure (en termes de nombre d'opérations) le coût de transformer un objet en un autre.Au regard de l'état de l'art, nous avons identifié deux limites importantes des approches actuelles. Premièrement, elles permettent d'améliorer la performance d'algorithmes locaux comme les k plus proches voisins, mais l'apprentissage de métriques pour des algorithmes globaux (comme les classifieurs linéaires) n'a pour l'instant pas été beaucoup étudié. Le deuxième point, sans doute le plus important, est que la question de la capacité de généralisation des méthodes d'apprentissage de métriques a été largement ignorée.Dans cette thèse, nous proposons des contributions théoriques et algorithmiques qui répondent à ces limites. Notre première contribution est la construction d'un nouveau noyau construit à partir de probabilités d'édition apprises. A l'inverse d'autres noyaux entre chaînes, sa validité est garantie et il ne comporte aucun paramètre. Notre deuxième contribution est une nouvelle approche d'apprentissage de similarités d'édition pour les chaînes et les arbres inspirée par la théorie des (epsilon,gamma,tau)-bonnes fonctions de similarité et formulée comme un problème d'optimisation convexe. En utilisant la notion de stabilité uniforme, nous établissons des garanties théoriques pour la similarité apprise qui donne une borne sur l'erreur en généralisation d'un classifieur linéaire construit à partir de cette similarité. Dans notre troisième contribution, nous étendons ces principes à l'apprentissage de métriques pour les données numériques en proposant une méthode d'apprentissage de similarité bilinéaire qui optimise efficacement l'(epsilon,gamma,tau)-goodness. La similarité est apprise sous contraintes globales, plus appropriées à la classification linéaire. Nous dérivons des garanties théoriques pour notre approche, qui donnent de meilleurs bornes en généralisation pour le classifieur que dans le cas des données structurées. Notre dernière contribution est un cadre théorique permettant d'établir des bornes en généralisation pour de nombreuses méthodes existantes d'apprentissage de métriques. Ce cadre est basé sur la notion de robustesse algorithmique et permet la dérivation de bornes pour des fonctions de perte et des régulariseurs variés / In recent years, the crucial importance of metrics in machine learningalgorithms has led to an increasing interest in optimizing distanceand similarity functions using knowledge from training data to make them suitable for the problem at hand.This area of research is known as metric learning. Existing methods typically aim at optimizing the parameters of a given metric with respect to some local constraints over the training sample. The learned metrics are generally used in nearest-neighbor and clustering algorithms.When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance, which is parameterized by a positive semi-definite matrix. Recent methods offer good scalability to large datasets.Less work has been devoted to metric learning from structured objects (such as strings or trees), because it often involves complex procedures. Most of the work has focused on optimizing a notion of edit distance, which measures (in terms of number of operations) the cost of turning an object into another.We identify two important limitations of current supervised metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not really been studied so far. Second, and perhaps more importantly, the question of the generalization ability of metric learning methods has been largely ignored.In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Unlike other string kernels, it is guaranteed to be valid and parameter-free. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (epsilon,gamma,tau)-good similarity functions and formulated as a convex optimization problem. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend the same ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (epsilon,gamma,tau)-goodness. The similarity is learned based on global constraints that are more appropriate to linear classification. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms. It is based on a simple adaptation of the notion of algorithmic robustness and allows the derivation of bounds for various loss functions and regularizers.