Nous étudions quatre problèmes d'ordonnancement sur machines parallèles. Ces quatre problèmes diffèrent par le critère que l'on cherche à minimiser : la somme des dates de fin, la somme pondérée des dates de fin, le retard total ou le retard total pondéré. Les jobs à ordonnancer sout soumis à des dates de disponibilité. Nous avons proposé pour ces quatres problèmes plusieurs règles de dominance. Une étude des bornes<br />inférieures a également été réalisée. Enfin, nous avons proposé une méthode de résolution exacte utilisant les règles de dominance ainsi que les bornes inférieures.

Prévoir le comportement de matéiaux hétérogènes aléatoires en fonction de la répartition spatiale des constituants reste un problème largement ouvert, dont on expose les enjeux, le formalisme et les diverses approches micromécaniques associées. Une étude expérimentale sur des matériaux biphasés fer/argent et fer/cuivre de morphologie "matrice/inclusions" ou à phases co-continues montre que l'influence des paramètres morphologiques est surtout sensible à l'échelle locale et concerne notamment les hétérogénéités de déformation, caractérisées en termes de moyennes par phase et de fonctions de distribution, mesurées grâce à une technique originale de microextensométrie. Les modèles classiques ne rendant pas compte des phénomènes observés, une nouvelle approche fondée sur la notion de "motif morphologique représentatif" est proposée. Un premier modèle à motifs multicouches admet une expression semi-analytique mais s'avère toujours insuffisant. Une description morphologique plus riche obtenue avec des motifs de structure interne quelconque en distribution ellipsoïdale conduit à des encadrements rigoureux et des estimations autocohérentes du comportement linéaire effectif. La théorie sous-jacente est exposée en détail, la signification physique véritable de ces modèles étant précisée. La mise en œuvre effective par des outils numériques conduit par exemple à de nouveaux résultats pour des composites anisotropes à renforts particulaires, dont on décrit ainsi correctement les interactions locales. La prise en compte de certains phénomènes de corrélation à grande distance observés expérimentalement dans le domaine non linéaire reste en revanche une question ouverte.

Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants.

La connaissance de l'environnement marin est nécessaire pour un grand nombre d'applications dans le domaine de l'acoustique sous-marine comme la communication, la localisation et détection sonar et la surveillance des mammifères marins. Il constitue le moyen principal pour éviter les interférences néfastes entre le milieu naturel et les actions industriels et militaires conduites en zones côtières.Notre travail de thèse se place dans un contexte de sonar actif avec des fréquences allant de 1 kHz à 10 kHz pour des distances de propagations allant de 1 km à plusieurs dizaines de kilomètres. Nous nous intéressons particulièrement aux environnements de propagation grands fonds, à l'utilisation des antennes industrielles comme les antennes de flancs, les antennes cylindriques et les antennes linéaires remorquées, et à l'utilisation de signaux large bande afin de travailler avec des résolutions en distance et en vitesse très élevées. Le travail de recherche présenté dans ce mémoire est dédié à la recherche de nouveaux paramètres discriminants pour la classification de cible sous-marine en sonar actif et notamment à l'estimation de l'immersion instantanée.Cette étude présente : (1) les calculs de nouvelles bornes de Cramer-Rao pour la position d'une cible en distance en et en profondeur, (2) l'estimation conjointe de la distance et de l'immersion d'une cible à partir de la mesure des temps d'arrivées et des angles d'élévations sur une antenne surfacique et (3) l'estimation conjointe de la distance, de l'immersion et du gisement d'une cible à partir de la mesure des temps d'arrivées et des pseudo-gisements sur une antenne linéaire remorquée.Les méthodes développées lors de cette étude ont été validées sur des simulations, des données expérimentales à petite échelle et des données réelles en mer. / The knowledge of the marine environment is required for many underwater applications such as communications, sonar localization and detection, and marine mammals monitoring. It enables preventing harmful interference between the natural environment and industrial and military actions in coastal areas.This thesis work concentrates upton the context of active sonar with frequencies from 1 kHz to 10 kHz and long propagation ranges from 1 km to several tens of kilometers. We also concentrates upon deep water environment, the use of industrial arrays such as cylindrical arrays, flank arrays and linear towed arrays, and the use of large time-bandwidth signals in order to obtain high distance and speed resolutions. This research work is dedicated to the research of new features for the underwater target classification in active sonar, and specifically to the instantaneous target-depth estimation.This thesis presents: (1) calculations of new Cramer-Rao bounds for the target-position in range and in depth, (2) the joint estimation of the target-depth and the target-range from the arrival time and elevation angle measures with a surface array, (3) the joint estimation of the target-depth, the target-range and the target-bearing from the arrival time and pseudo-bearing angle measures with a linear towed array.The methods presented in this manuscript have been benchmarked on simulation, on reduced-scale experimental data and real marine data.

Cette thèse est une contribution au domaine de l'estimation non-paramétrique sous contrainte de forme. Les fonctions sont discrètes et la forme considérée, appelée k-monotonie, k désignant un entier supérieur à 2, est une généralisation de la convexité. L'entier k constitue un indicateur du degré de creux d'une fonction convexe. Le manuscrit est structuré en trois parties en plus de l'introduction, de la conclusion et d'une annexe.Introduction :L'introduction comprend trois chapitres. Le premier présente un état de l'art de l'estimation de densité sous contrainte de forme. Le second est une synthèse des résultats obtenus au cours de la thèse, disponible en français et en anglais. Enfin, le Chapitre 3 regroupe quelques notations et des résultats mathématiques utilisés au cours du manuscrit.Partie I : Estimation d'une densité discrète sous contrainte de k-monotonieDeux estimateurs des moindres carrés d'une distribution discrète p* sous contrainte de k-monotonie sont proposés. Leur caractérisation est basée sur la décomposition en base de spline des suites k-monotones, et sur les propriétés de leurs primitives. Les propriétés statistiques de ces estimateurs sont étudiées. Leur qualité d'estimation, en particulier, est appréciée. Elle est mesurée en terme d'erreur quadratique, les deux estimateurs convergent à la vitesse paramétrique. Un algorithme dérivé de l'Algorithme de Réduction de Support est implémenté et disponible au R-package pkmon. Une étude sur jeux de données simulés illustre les propriétés de ces estimateurs. Ce travail a été publié dans Electronic Journal of Statistics (Giguelay, 2017).Partie II : Calculs de bornes de risqueDans le premier chapitre de la Partie II, le risque quadratique de l'estimateur des moindres carrés introduit précédemment est borné. Cette borne est adaptative en le sens qu'elle dépend d'un compromis entre la distance de p* à la frontière de l'ensemble des densités k-monotones à support fini, et de la complexité (en terme de décomposition dans la base de spline) des densités appartenant à cet ensemble qui sont suffisamment proches de p*. La méthode est basée sur une formulation variationnelle du risque proposée par Chatterjee (2014) etgénéralisée au cadre de l'estimation de densité. Par la suite, les entropies à crochet des espaces fonctionnels correspondants sont calculées afin de contrôler le supremum de processus empiriques impliqué dans l'erreur quadratique. L'optimalité de la borne de risque est ensuite discutée au regard des résultats obtenus dans le cas continu et dans le cadre de la régression.Dans le second chapitre de la Partie II, des résultats complémentaires sur les entropies à crochet pour les espaces de fonctions k-monotones sont donnés.Partie III : Estimation du nombre d'espèces dans une population et tests de k-monotonieLa dernière partie traite du problème de l'estimation du nombre d'espèces dans une population. La modélisation choisie est celle d'une distribution d'abondance commune à toutes les espèces et définie comme un mélange. La méthode proposée repose sur l'hypothèse de k-monotonie d'abondance. Cette hypothèse permet de rendre le problème de l'estimation du nombre d'espèces identifiable. Deux approches sont proposées. La première est basée sur l'estimateur des moindres carrés sous contrainte de k-monotonie, tandis que la seconde est basée sur l'estimateur empirique. Les deux estimateurs sont comparés sur une étude sur données simulées. L'estimation du nombre d'espèces étant fortement dépendante du degré de k-monotonie choisi dans le modèle, trois procédures de tests multiples sont ensuite proposées pour inférer le degré k directement sur la base des observations. Le niveau et la puissance de ces procédures sont calculés, puis évalués au moyen d'une étude sur jeux de données simulés et la méthode est appliquée sur des jeux de données réels issus de la littérature. / This thesis belongs to the field of nonparametric density estimation under shape constraint. The densities are discrete and the form is k-monotonicity, k>1, which is a generalization of convexity. The integer k is an indicator for the hollow's degree of a convex function. This thesis is composed of three parts, an introduction, a conclusion and an appendix.Introduction :The introduction is structured in three chapters. First Chapter is a state of the art of the topic of density estimation under shape constraint. The second chapter of the introduction is a synthesis of the thesis, available in French and in English. Finally Chapter 3 is a short chapter which summarizes the notations and the classical mathematical results used in the manuscript.Part I : Estimation of a discrete distribution under k-monotonicityconstraintTwo least-square estimators of a discrete distribution p* under constraint of k-monotonicity are proposed. Their characterisation is based on the decomposition on a spline basis of k-monotone sequences, and on the properties of their primitives. Their statistical properties are studied, and in particular their quality of estimation is measured in terms of the quadratic error. They are proved to converge at the parametric rate. An algorithm derived from the support reduction algorithm is implemented in the R-package pkmon. A simulation study illustrates the properties of the estimators. This piece of works, which constitutes Part I of the manuscript, has been published in ElectronicJournal of Statistics (Giguelay, 2017).Part II : Calculation of risks boundsIn the first chapter of Part II, a methodology for calculating riskbounds of the least-square estimator is given. These bounds are adaptive in that they depend on a compromise between the distance of p* on the frontier of the set of k-monotone densities with finite support, and the complexity (linked to the spline decomposition) of densities belonging to this set that are closed to p*. The methodology based on the variational formula of the risk proposed by Chatterjee (2014) is generalized to the framework of discrete k-monotone densities. Then the bracketting entropies of the relevant functionnal space are calculating, leading to control the empirical process involved in the quadratic risk. Optimality of the risk bound is discussed in comparaison with the results previously obtained in the continuous case and for the gaussian regression framework. In the second chapter of Part II, several results concerningbracketting entropies of spaces of k-monotone sequences are presented.Part III : Estimating the number of species in a population and tests of k-monotonicityThe last part deals with the problem of estimating the number ofpresent species in a given area at a given time, based on theabundances of species that have been observed. A definition of ak-monotone abundance distribution is proposed. It allows to relatethe probability of observing zero species to the truncated abundancedistribution. Two approaches are proposed. The first one is based on the Least-Squares estimator under constraint of k-monotonicity, the second oneis based on the empirical distribution. Both estimators are comparedusing a simulation study. Because the estimator of the number ofspecies depends on the value of the degree of monotonicity k, we proposea procedure for choosing this parameter, based on nested testingprocedures. The asymptotic levels and power of the testing procedureare calculated, and the behaviour of the method in practical cases isassessed on the basis of a simulation study.

Dans cette thèse, nous nous intéressons à deux méthodes permettant de reconstruire un signal parcimonieux largement sous-échantillonné : l’échantillonnage de signaux à taux d’innovation fini et l’acquisition comprimée.Il a été montré récemment qu’en utilisant un noyau de pré-filtrage adapté, les signaux impulsionnels peuvent être parfaitement reconstruits bien qu’ils soient à bande non-limitée. En présence de bruit, la reconstruction est réalisée par une procédure d’estimation de tous les paramètres du signal d’intérêt. Dans cette thèse, nous considérons premièrement l’estimation des amplitudes et retards paramétrisant une somme finie d'impulsions de Dirac filtrée par un noyau quelconque et deuxièmement l’estimation d’une somme d’impulsions de forme quelconque filtrée par un noyau en somme de sinus cardinaux (SoS). Le noyau SoS est intéressant car il est paramétrable par un jeu de paramètres à valeurs complexes et vérifie les conditions nécessaires à la reconstruction. En se basant sur l’information de Fisher Bayésienne relative aux paramètres d’amplitudes et de retards et sur des outils d’optimisation convexe, nous proposons un nouveau noyau d’échantillonnage.L’acquisition comprimée permet d’échantillonner un signal en-dessous de la fréquence d’échantillonnage de Shannon, si le vecteur à échantillonner peut être approximé comme une combinaison linéaire d’un nombre réduit de vecteurs extraits d’un dictionnaire sur-complet. Malheureusement, dans des conditions réalistes, le dictionnaire (ou base) n’est souvent pas parfaitement connu, et est donc entaché d’une erreur (DB). L’estimation par dictionnaire, se basant sur les mêmes principes, permet d’estimer des paramètres à valeurs continues en les associant selon une grille partitionnant l’espace des paramètres. Généralement, les paramètres ne se trouvent pas sur la grille, ce qui induit un erreur d’estimation même à haut rapport signal sur bruit (RSB). C’est le problème de l’erreur de grille (EG). Dans cette thèse nous étudions les conséquences des modèles d’erreur DB et EG en terme de performances bayésiennes et montrons qu’un biais est introduit même avec une estimation parfaite du support et à haut RSB. La BCRB est dérivée pour les modèles DB et EG non structurés, qui bien qu’ils soient très proches, ne sont pas équivalents en terme de performances. Nous donnons également la borne de Cramér-Rao moyennée (BCRM) dans le cas d’une petite erreur de grille et étudions l’expression analytique de l’erreur quadratique moyenne bayésienne (BEQM) sur l’estimation de l’erreur de grille à haut RSB. Cette dernière est confirmée en pratique dans le contexte de l’estimation de fréquence pour différents algorithmes de reconstruction parcimonieuse.Nous proposons deux nouveaux estimateurs : le Bias-Correction Estimator (BiCE) et l’Off-Grid Error Correction (OGEC) permettant de corriger l'erreur de modèle induite par les erreurs DB et EG, respectivement. Ces deux estimateurs principalement basés sur une projection oblique des mesures sont conçus comme des post-traitements, destinés à réduire le biais d’estimation suite à une pré-estimation effectuée par n’importe quel algorithme de reconstruction parcimonieuse. Les biais et variances théoriques du BiCE et du OGEC sont dérivés afin de caractériser leurs efficacités statistiques.Nous montrons, dans le contexte difficile de l’échantillonnage des signaux impulsionnels à bande non-limitée que ces deux estimateurs permettent de réduire considérablement l’effet de l'erreur de modèle sur les performances d’estimation. Les estimateurs BiCE et OGEC sont tout deux des schémas (i) génériques, car ils peuvent être associés à tout estimateur parcimonieux de la littérature, (ii) rapides, car leur coût de calcul reste faible comparativement au coût des estimateurs parcimonieux, et (iii) ont de bonnes propriétés statistiques. / In this thesis, we are interested in two different low rate sampling schemes that challenge Shannon’s theory: the sampling of finite rate of innovation signals and compressed sensing.Recently it has been shown that using appropriate sampling kernel, finite rate of innovation signals can be perfectly sampled even though they are non-bandlimited. In the presence of noise, reconstruction is achieved by a model-based estimation procedure. In this thesis, we consider the estimation of the amplitudes and delays of a finite stream of Dirac pulses using an arbitrary kernel and the estimation of a finite stream of arbitrary pulses using the Sum of Sincs (SoS) kernel. In both scenarios, we derive the Bayesian Cramér-Rao Bound (BCRB) for the parameters of interest. The SoS kernel is an interesting kernel since it is totally configurable by a vector of weights. In the first scenario, based on convex optimization tools, we propose a new kernel minimizing the BCRB on the delays, while in the second scenario we propose a family of kernels which maximizes the Bayesian Fisher Information, i.e., the total amount of information about each of the parameter in the measures. The advantage of the proposed family is that it can be user-adjusted to favor either of the estimated parameters.Compressed sensing is a promising emerging domain which outperforms the classical limit of the Shannon sampling theory if the measurement vector can be approximated as the linear combination of few basis vectors extracted from a redundant dictionary matrix. Unfortunately, in realistic scenario, the knowledge of this basis or equivalently of the entire dictionary is often uncertain, i.e. corrupted by a Basis Mismatch (BM) error. The related estimation problem is based on the matching of continuous parameters of interest to a discretized parameter set over a regular grid. Generally, the parameters of interest do not lie in this grid and there exists an estimation error even at high Signal to Noise Ratio (SNR). This is the off-grid (OG) problem. The consequence of the BM and the OG mismatch problems is that the estimation accuracy in terms of Bayesian Mean Square Error (BMSE) of popular sparse-based estimators collapses even if the support is perfectly estimated and in the high Signal to Noise Ratio (SNR) regime. This saturation effect considerably limits the effective viability of these estimation schemes.In this thesis, the BCRB is derived for CS model with unstructured BM and OG. We show that even though both problems share a very close formalism, they lead to different performances. In the biased dictionary based estimation context, we propose and study analytical expressions of the Bayesian Mean Square Error (BMSE) on the estimation of the grid error at high SNR. We also show that this class of estimators is efficient and thus reaches the Bayesian Cramér-Rao Bound (BCRB) at high SNR. The proposed results are illustrated in the context of line spectra analysis for several popular sparse estimator. We also study the Expected Cramér-Rao Bound (ECRB) on the estimation of the amplitude for a small OG error and show that it follows well the behavior of practical estimators in a wide SNR range.In the context of BM and OG errors, we propose two new estimation schemes called Bias-Correction Estimator (BiCE) and Off-Grid Error Correction (OGEC) respectively and study their statistical properties in terms of theoretical bias and variances. Both estimators are essentially based on an oblique projection of the measurement vector and act as a post-processing estimation layer for any sparse-based estimator and mitigate considerably the BM (OG respectively) degradation. The proposed estimators are generic since they can be associated to any sparse-based estimator, fast, and have good statistical properties. To illustrate our results and propositions, they are applied in the challenging context of the compressive sampling of finite rate of innovation signals.

Cette thèse porte sur l'étude des performances d'estimateurs en traitement du signal, et s'attache en particulier à étudier les bornes inférieures de l'erreur quadratique moyenne (EQM) pour l'estimation de points de rupture, afin de caractériser le comportement d'estimateurs, tels que celui du maximum de vraisemblance (dans le contexte fréquentiste), mais surtout du maximum a posteriori ou de la moyenne conditionnelle (dans le contexte bayésien). La difficulté majeure provient du fait que, pour un signal échantillonné, les paramètres d'intérêt (à savoir les points de rupture) appartiennent à un espace discret. En conséquence, les résultats asymptotiques classiques (comme la normalité asymptotique du maximum de vraisemblance) ou la borne de Cramér-Rao ne s'appliquent plus. Quelques résultats sur la distribution asymptotique du maximum de vraisemblance provenant de la communauté mathématique sont actuellement disponibles, mais leur applicabilité à des problèmes pratiques de traitement du signal n'est pas immédiate. Si l'on décide de concentrer nos efforts sur l'EQM des estimateurs comme indicateur de performance, un travail important autour des bornes inférieures de l'EQM a été réalisé ces dernières années. Plusieurs études ont ainsi permis de proposer des inégalités plus précises que la borne de Cramér-Rao. Ces dernières jouissent en outre de conditions de régularité plus faibles, et ce, même en régime non asymptotique, permettant ainsi de délimiter la plage de fonctionnement optimal des estimateurs. Le but de cette thèse est, d'une part, de compléter la caractérisation de la zone asymptotique (en particulier lorsque le rapport signal sur bruit est élevé et/ou pour un nombre d'observations infini) dans un contexte d'estimation de points de rupture. D'autre part, le but est de donner les limites fondamentales de l'EQM d'un estimateur dans la plage non asymptotique. Les outils utilisés ici sont les bornes inférieures de l’EQM de la famille Weiss-Weinstein qui est déjà connue pour être plus précise que la borne de Cramér-Rao dans les contextes, entre autres, de l’analyse spectrale et du traitement d’antenne. Nous fournissons une forme compacte de cette famille dans le cas d’un seul et de plusieurs points de ruptures puis, nous étendons notre analyse aux cas où les paramètres des distributions sont inconnus. Nous fournissons également une analyse de la robustesse de cette famille vis-à-vis des lois a priori utilisées dans nos modèles. Enfin, nous appliquons ces bornes à plusieurs problèmes pratiques : données gaussiennes, poissonniennes et processus exponentiels. / This thesis deals with the study of estimators' performance in signal processing. The focus is the analysis of the lower bounds on the Mean Square Error (MSE) for abrupt change-point estimation. Such tools will help to characterize performance of maximum likelihood estimator in the frequentist context but also maximum a posteriori and conditional mean estimators in the Bayesian context. The main difficulty comes from the fact that, when dealing with sampled signals, the parameters of interest (i.e., the change points) lie on a discrete space. Consequently, the classical large sample theory results (e.g., asymptotic normality of the maximum likelihood estimator) or the Cramér-Rao bound do not apply. Some results concerning the asymptotic distribution of the maximum likelihood only are available in the mathematics literature but are currently of limited interest for practical signal processing problems. When the MSE of estimators is chosen as performance criterion, an important amount of work has been provided concerning lower bounds on the MSE in the last years. Then, several studies have proposed new inequalities leading to tighter lower bounds in comparison with the Cramér-Rao bound. These new lower bounds have less regularity conditions and are able to handle estimators’ MSE behavior in both asymptotic and non-asymptotic areas. The goal of this thesis is to complete previous results on lower bounds in the asymptotic area (i.e. when the number of samples and/or the signal-to-noise ratio is high) for change-point estimation but, also, to provide an analysis in the non-asymptotic region. The tools used here will be the lower bounds of the Weiss-Weinstein family which are already known in signal processing to outperform the Cramér-Rao bound for applications such as spectral analysis or array processing. A closed-form expression of this family is provided for a single and multiple change points and some extensions are given when the parameters of the distributions on each segment are unknown. An analysis in terms of robustness with respect to the prior influence on our models is also provided. Finally, we apply our results to specific problems such as: Gaussian data, Poisson data and exponentially distributed data.

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.

Cette thèse concerne les codes utilisés pour les télécommunications sans-fil multi-antennes. Les résultats portent notamment sur des constructions explicites ainsi que sur des bornes numériques et théoriques pour les cardinaux de ces codes. Le premier chapitre introduit brièvement les différents contextes multi-antennes et les modélisations qui leur sont associées. Les chapitres 2,3 et 4 traitent respectivement des codes dans les espaces grassmanniens, des codes dans les matrices unitaires et des codes dans les algèbres à division. / This thesis deals with codes used for multi-antennas wireless telecommunications. The results concern explicit constructions and bounds on the cardinalities of such codes (analytical and numerical bounds) . The first chapter introduce various modelisations of the multi-antennas wireless system and the related mathematical problems. Chapters 2,3,4 deal respectively with codes in Grassmannian spaces, code in unitary matrices and code in division algebras.

Cette thèse s'inscrit dans les domaines de l'apprentissage statistique et de la statistique séquentielle. Le cadre principal est celui des problèmes de bandit stochastique à plusieurs bras. Dans une première partie, on commence par revisiter les bornes inférieures sur le regret. On obtient ainsi des bornes non-asymptotiques dépendantes de la distribution que l'on prouve de manière très simple en se limitant à quelques propriétés bien connues de la divergence de Kullback-Leibler. Puis, on propose des algorithmes pour la minimisation du regret dans les problèmes de bandit stochastique paramétrique dont les bras appartiennent à une certaine famille exponentielle ou non-paramétrique en supposant seulement que les bras sont à support dans l'intervalle unité, pour lesquels on prouve l'optimalité asymptotique (au sens de la borne inférieure de Lai et Robbins) et l'optimalité minimax. On analyse aussi la complexité pour l'échantillonnage séquentielle visant à identifier la distribution ayant la moyenne la plus proche d'un seuil fixé, avec ou sans l'hypothèse que les moyennes des bras forment une suite croissante. Ce travail est motivé par l'étude des essais cliniques de phase I, où l'hypothèse de croissance est naturelle. Finalement, on étend l'inégalité de Fano qui contrôle la probabilité d'évènements disjoints avec une moyenne de divergences de Kullback-leibler à des variables aléatoires arbitraires bornées sur l'intervalle unité. Plusieurs nouvelles applications en découlent, les plus importantes étant une borne inférieure sur la vitesse de concentration de l'a posteriori Bayésien et une borne inférieure sur le regret pour un problème de bandit non-stochastique. / The topics addressed in this thesis lie in statistical machine learning and sequential statistic. Our main framework is the stochastic multi-armed bandit problems. In this work we revisit lower bounds on the regret. We obtain non-asymptotic, distribution-dependent bounds and provide simple proofs based only on well-known properties of Kullback-Leibler divergence. These bounds show in particular that in the initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. Then, we propose algorithms for regret minimization in stochastic bandit models with exponential families of distributions or with distribution only assumed to be supported by the unit interval, that are simultaneously asymptotically optimal (in the sense of Lai and Robbins lower bound) and minimax optimal. We also analyze the sample complexity of sequentially identifying the distribution whose expectation is the closest to some given threshold, with and without the assumption that the mean values of the distributions are increasing. This work is motivated by phase I clinical trials, a practically important setting where the arm means are increasing by nature. Finally we extend Fano's inequality, which controls the average probability of (disjoint) events in terms of the average of some Kullback-Leibler divergences, to work with arbitrary unit-valued random variables. Several novel applications are provided, in which the consideration of random variables is particularly handy. The most important applications deal with the problem of Bayesian posterior concentration (minimax or distribution-dependent) rates and with a lower bound on the regret in non-stochastic sequential learning.