Le domaine maritime littoral constitue un milieu fragile, placé à l'interface Terre/Mer où s'exercent de nombreuses pressions issues des milieux terrestres, maritimes et atmosphériques. Les approches globales de Gestion Intégrée des Zones Côtières (GIZC) ont pour but de pallier les lacunes des politiques précédentes au niveau des interactions simultanées des différents acteurs du littoral. Cette approche requiert un Modèle Numérique de Terrain (MNT) littoral continu ainsi que des données maritimes et terrestres cohérentes entre elles. En raison d'acquisitions ou de productions différentes pour les MNT terrestres et maritimes, l'ensemble du relief n'est pas traité de manière ni homogène ni continue. De plus les techniques d'intégration des MNT actuelles entraînent des lissages des reliefs, voire la perte des éléments caractéristiques. Des outils et une nouvelle méthodologie d'intégration de MNT ont donc été définis. Les outils utilisent la distance de Fréchet pour calculer une distance maximale d'écartement entre les points homologues de deux lignes. La valeur de cette distance donne une mesure de ressemblance de forme qui sert de base à leur appariement ultérieur. La méthodologie de fusion proposée dans cette thèse se veut générique tout en s'appuyant sur les lignes caractéristiques spécifiques du paysage. Elle effectue un enchaînement de traitements répartis en trois étapes majeures : 1) transformations cartographiques et analyse des zones de recouvrement ; 2) segmentation et extraction de lignes caractéristiques ; 3) appariement et fusion à l'aide de déformations élastiques. Ces outils d'intégration ont été testés sur des données réelles en 2D pour la comparaison du trait de côte, puis validés sur des MNT simulés 3D.

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique. / Despite constant progress in terms of available computational power, memory and amount of data, machine learning algorithms need to be efficient in how they use them. Although minimizing cost is an obvious major concern, another motivation is to attempt to design algorithms that can learn as efficiently as intelligent species. This thesis tackles the problem of efficient learning through various papers dealing with a wide range of machine learning algorithms: this topic is seen both from the point of view of computational efficiency (processing power and memory required by the algorithms) and of statistical efficiency (n umber of samples necessary to solve a given learning task).The first contribution of this thesis is in shedding light on various statistical inefficiencies in existing algorithms. Indeed, we show that decision trees do not generalize well on tasks with some particular properties (chapter 3), and that a similar flaw affects typical graph-based semi-supervised learning algorithms (chapter 5). This flaw is a form of curse of dimensionality that is specific to each of these algorithms. For a subclass of neural networks, called sum-product networks, we prove that using networks with a single hidden layer can be exponentially less efficient than when using deep networks (chapter 4). Our analyses help better understand some inherent flaws found in these algorithms, and steer research towards approaches that may potentially overcome them. We also exhibit computational inefficiencies in popular graph-based semi-supervised learning algorithms (chapter 5) as well as in the learning of mixtures of Gaussians with missing data (chapter 6). In both cases we propose new algorithms that make it possible to scale to much larger datasets. The last two chapters also deal with computational efficiency, but in different ways. Chapter 7 presents a new view on the contrastive divergence algorithm (which has been used for efficient training of restricted Boltzmann machines). It provides additional insight on the reasons why this algorithm has been so successful. Finally, in chapter 8 we describe an application of machine learning to video games, where computational efficiency is tied to software and hardware engineering constraints which, although often ignored in research papers, are ubiquitous in practice.

Les analyses effectuées dans le cadre de ce mémoire ont été réalisées à l'aide du module MatchIt disponible sous l’environnent d'analyse statistique R. / Statistical analyzes of this thesis were performed using the MatchIt package available in the statistical analysis environment R. / L’estimation sans biais de l’effet causal d’une intervention nécessite la comparaison de deux groupes homogènes. Il est rare qu’une étude observationnelle dispose de groupes comparables et même une étude expérimentale peut se retrouver avec des groupes non comparables. Les chercheurs ont alors recours à des techniques de correction afin de rendre les deux groupes aussi semblables que possible. Le problème consiste alors à choisir la méthode de correction appropriée. En ce qui nous concerne, nous limiterons nos recherches à une famille de méthodes dites d’appariement. Il est reconnu que ce qui importe lors d’un appariement est l’équilibre des deux groupes sur les caractéristiques retenues. Autrement dit, il faut que les variables soient distribuées de façon similaire dans les deux groupes. Avant même de considérer la distribution des variables entre les deux groupes, il est nécessaire de savoir si les données en question permettent une inférence causale. Afin de présenter le problème de façon rigoureuse, le modèle causal contrefactuel sera exposé. Par la suite, les propriétés formelles de trois méthodes d’appariement seront présentées. Ces méthodes sont l’appariement par la distance de Mahalanobis, de l’appariement par le score de propension et de l’appariement génétique. Le choix de la technique d’appariement appropriée reposera sur quatre critères empiriques dont le plus important est la différence des moyennes standardisées. Les résultats obtenus à l’aide des données de l’Enquête longitudinale et expérimentale de Montréal (ÉLEM) indiquent que des trois techniques d’appariement, l’appariement génétique est celui qui équilibre mieux les variables entre les groupes sur tous les critères retenus. L’estimation de l’effet de l’intervention varie sensiblement d’une technique à l’autre, bien que dans tous les cas cet effet est non significatif. Ainsi, le choix d’une technique d’appariement influence l’estimation de l’effet d’une intervention. Il est donc impérieux de choisir la technique qui permet d’obtenir un équilibre optimal des variables selon les données à la disposition du chercheur. / The unbiased estimate of the causal effect of an intervention requires the comparison of two homogeneous groups. It is rare that an observational study has comparable groups and even an experiment may end up with non-comparable groups. The researchers then used correction techniques to make the two groups as similar as possible. The problem then is to choose the appropriate correction method. In our case, we will restrict our research to a family of so-called matching methods. It is recognized that what matters in a match is the balance between the two groups on selected characteristics. In other words, it is necessary that the variables are distributed similarly in both groups. Even before considering the distribution of variables between the two groups, it is necessary to know whether the data in question allow for causal inference. To present the problem rigorously, the counterfactual causal model will be exposed. Thereafter, the formal properties of three matching methods will be presented. Those methods are the Mahalanobis matching, the propensity score matching and genetic matching. The choice of the appropriate matching technique is based on four empirical criteria which the most important is the standardized mean difference. Results obtained using data from the Montréal Longitudinal and Experimental Study indicate that of the three matching techniques, genetic matching is the one that better balance the variables between groups on all criteria. The estimate of the effect of intervention varies substantially from one technique to another, although in all cases this effect is non significant. Thus, the selection of a matching technique influences the estimation of the effect of an intervention. Therefore, it is imperative to choose the technique that provides an optimal balance of the variables based on data available to the researcher.

Malgré les récentes avancées des Systèmes de Cartographie Mobile, la reconstruction automatique d’objets à partir des données acquises est encore un point crucial. Dans cette thèse, nous nous intéresserons en particulier à la reconstruction tridimensionnelle du marquage au sol à partir d’images acquises sur le réseau routier par une base stéréoscopique horizontale d’un système de cartographie mobile, dans un contexte urbain dense. Une nouvelle approche s’appuyant sur la connaissance de la géométrie 3D des marquages au sol est présentée, conduisant à une précision de reconstruction 3D centimétrique avec un faible niveau de généralisation. Deux objets de la signalisation routière horizontale sont étudiés : les passages piétons et les lignes blanches discontinues. La stratégie générale est composée de trois grandes étapes. La première d’entre elles permet d’obtenir des chaînes de contours 3D. Les contours sont extraits dans les images gauche et droite. Ensuite, un algorithme reposant sur une optimisation par programmation dynamique est mis en oeuvre pour apparier les points de contours des deux images. Un post-traitement permet un appariement sub-pixellique, et, les chaînes de contours 3D sont finalement obtenues par une triangulation photogrammétrique classique. La seconde étape fait intervenir les spécifications géométriques des marquages au sol pour réaliser un filtrage des chaînes de contours 3D. Elle permet de déterminer des candidats pour les objets du marquage au sol. La dernière étape peut être vue comme une validation permettant de rejeter ou d’accepter ces hypothèses. Les candidats retenus sont alors reconstruits finement. Pour chaque bande d’un passage piéton ou d’une ligne discontinue, le modèle est un quasi-parallélogramme. Une contrainte de planéité est imposée aux sommets de chaque bande, ce qui n’est pas le cas pour l’ensemble des bandes formant un marquage au sol particulier. La méthode est évaluée sur un ensemble de 150 paires d’images acquises en centre ville dans des conditions normales de trafic. Les résultats montrent la validité de notre stratégie en terme de robustesse, de complétude et de précision géométrique. La méthode est robuste et permet de gérer les occultations partielles ainsi que les marquages usés ou abîmés. Le taux de détection atteint 90% et la précision de reconstruction 3D est de l’ordre de 2 à 4 cm. Finalement, une application de la reconstruction des marquages au sol est présentée : le géoréférencement du système d’acquisition. La majorité des systèmes de cartographie mobile utilisent des capteurs de géoréférencement direct comme un couplage GPS/INS pour leur localisation. Cependant, en milieu urbain dense, les masques et les multi-trajets corrompent les mesures et conduisent à une précision d’environ 50 cm. Afin d’améliorer la qualité de localisation, nous cherchons à apparier les images terrestres avec des images aériennes calibrées de la même zone. Les marquages au sol sont alors utilisés comme objets d’appariement. La validité de la méthode est démontrée sur un exemple de passage piéton / Despite advances in ground-based Mobile Mapping System (MMS), automatic feature reconstruction seems far from being reached. In this thesis, we focus on 3D roadmark reconstruction from images acquired by road looking cameras of a MMS stereo-rig in dense urban context. A new approach is presented, that uses 3D geometric knowledge of roadmarks and provides a centimetric 3D accuracy with a low level of generalisation. Two classes of roadmarks are studied: zebra-crossing and dashed-lines. The general strategy consists in three main steps. The first step provides 3D linked-edges. Edges are extracted in the left and right images. Then a matching algorithm that is based on dynamic programming optimisation matches the edges between the two images. A sub-pixel matching is computed by post processing and 3D linked-edges are provided by classical photogrammetric triangulation. The second step uses the known specification of roadmarks to perform a signature based filtering of 3D linked-edges. This step provides hypothetical candidates for roadmark objects. The last step can be seen as a validation step that rejects or accepts the candidates. The validated candidates are finely reconstructed. The adopted model consists of a quasi parallelogram for each strip of zebra-crossing or dashed-line. Each strip is constrained to be flat but the roadmark as a whole is not planar. The method is evaluated on a set of 150 stereo-pairs acquired in a real urban area under normal traffic conditions. The results show the validity of the approach in terms of robustness, completeness and geometric accuracy. The method is robust and deals properly with partially occluded roadmarks as well as damaged or eroded ones. The detection rate reaches 90% and the 3D accuracy is about 2-4 cm. Finally an application of reconstructed roadmarks is presented. They are used in georeferencing of the system. Most of the MMSs use direct georeferencing devices such as GPS/INS for their localisation. However in urban areas masks and multi-path errors corrupt the measurements and provide only 50 cm accuracy. In order to improve the localisation quality, we aim at matching ground-based images with calibrated aerial images of the same area. For this purpose roadmarks are used as matching objects. The validity of this method is demonstrated on a zebra-crossing example

Un grand nombre des problèmes d'optimisation, ainsi que des problèmes inverses, combinatoires ou hors équilibre qui apparaissent en physique statistique des systèmes complexes, peuvent être représentés comme un ensemble des variables en interaction sur un certain réseau. Bien que la recette universelle pour traiter ces problèmes n'existe pas, la compréhension qualitative et quantitative des problèmes complexes sur des graphes a fait des grands progrès au cours de ces dernières années. Un rôle particulier a été joué par des concepts empruntés de la physique des verres de spin et la théorie des champs, qui ont eu beaucoup de succès en ce qui concerne la description des propriétés statistiques des systèmes complexes et le développement d'algorithmes efficaces pour des problèmes concrets.En première partie de cette thèse, nous étudions des problèmes de diffusion sur des réseaux, avec la dynamique hors équilibre. En utilisant la méthode de cavité sur des trajectoires dans le temps, nous montrons comment dériver des équations dynamiques dites "message-passing'' pour une large classe de modèles avec une dynamique unidirectionnelle -- la propriété clef qui permet de résoudre le problème. Ces équations sont asymptotiquement exactes pour des graphes localement en arbre et en général représentent une bonne approximation pour des réseaux réels. Nous illustrons cette approche avec une application des équations dynamiques pour résoudre le problème inverse d'inférence de la source d'épidémie dans le modèle "susceptible-infected-recovered''.Dans la seconde partie du manuscrit, nous considérons un problème d'optimisation d'appariement planaire optimal sur une ligne. En exploitant des techniques de la théorie de champs et des arguments combinatoires, nous caractérisons une transition de phase topologique qui se produit dans un modèle désordonné simple, le modèle de Bernoulli. Visant une application à la physique des structures secondaires de l'ARN, nous discutons la relation entre la transition d'appariement parfait-imparfait et la transition de basse température connue entre les états fondu et vitreux de biopolymère; nous proposons également des modèles généralisés qui suggèrent une correspondance exacte entre la matrice des contacts et la séquence des nucléotides, permettant ainsi de donner un sens à la notion des alphabets effectifs non-entiers. / A large number of optimization, inverse, combinatorial and out-of-equilibrium problems, arising in the statistical physics of complex systems, allow for a convenient representation in terms of disordered interacting variables defined on a certain network. Although a universal recipe for dealing with these problems does not exist, the recent years have seen a serious progress in understanding and quantifying an important number of hard problems on graphs. A particular role has been played by the concepts borrowed from the physics of spin glasses and field theory, that appeared to be extremely successful in the description of the statistical properties of complex systems and in the development of efficient algorithms for concrete problems.In the first part of the thesis, we study the out-of-equilibrium spreading problems on networks. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing equations for a large class of models with unidirectional dynamics -- the key property that makes the problem solvable. These equations are asymptotically exact for locally tree-like graphs and generally provide a good approximation for real-world networks. We illustrate the approach by applying the dynamic message-passing equations for susceptible-infected-recovered model to the inverse problem of inference of epidemic origin. In the second part of the manuscript, we address the optimization problem of finding optimal planar matching configurations on a line. Making use of field-theory techniques and combinatorial arguments, we characterize a topological phase transition that occurs in the simple Bernoulli model of disordered matching. As an application to the physics of the RNA secondary structures, we discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition at low temperatures, and suggest generalized models that incorporate a one-to-one correspondence between the contact matrix and the nucleotide sequence, thus giving sense to the notion of effective non-integer alphabets.

Dans cette thèse, nous dépassons le cadre binaire de l’évaluation et nous nous plaçons dans celui de plusieurs traitements, à l’instar de Brodaty et al. [2001], Larson [2000], Imbens [1999]. Les estimations effectuées portent sur les politiques de l’emploi en vigueur en France pendant la période 1997-1999. Trois programmes sont étudies : CIE (Contrat Initiative Emploi) emploi subventionné dans le secteur marchand, CES (Contrat Emploi-Solidarité) création d’emploi dans le secteur non marchand et SIFE (Stage d’Insertion par la Formation et l’Emploi). L’efficacité de ces dispositifs est évaluée non seulement sur le taux de retour à l’emploi des bénéficiaires mais aussi sur divers autres critères qui répondent à différentes questions intéressantes économiquement et économétriquement : i) la politique active de l’emploi atteint-elle les demandeurs d’emploi les plus prioritaires parmi les prioritaires ? ii) Comment les entreprises utilisent-elles les programmes de la politique active (effet d’aubaine, de substitution,...) ? iii) Pouvons-nous mesurer la qualité d’un contrat aidé ? Comment évaluer l’efficacité relative d’un contrat aidé (plus spécifiquement) non marchand comparativement à celui du secteur marchand ?, impact marginal, effet propre, bien-être, , etc. / We evaluate the ALMP’s with a particular attention to the differentiation of impacts by categories of programmes and categories of beneficiaries. These two forms of heterogeneity can in fact lead to erroneous evaluations or too partial:i) The heterogeneity of programmes proposed, in particular their characteristics (type of contract, duration, remuneration, training, etc.) are an important source of complexity in behavior of self-selection of job seekers: behaviors can be multiples and strategic.ii) The heterogeneity of target-populations (low-skilled, youth, women, priority category, first-job seekers, etc.) is an important source of complexity in the behavior selection of employment advisor.There is finally no reason that different types of programmes have the same average effect on various public as well. We evaluate so ALMP’s on multiple criteria of effectiveness (heterogeneity of criteria).

Cette thèse de doctorat examine les principales défaillances du marché du travail qui entraînent que les travailleurs n’arrivent pas à obtenir la pleine rémunération potentielle qui corresponde à leur capital humain. Il y a « inefficacité salariale » lorsque le salaire obtenu est inférieur au maximum atteignable. Dans un tel cas, les salariés reçoivent un salaire injuste par rapport au capital humain disposé. Cela décourage à investir dans son capital humain ce qui aura tendance à réduire la productivité totale, à affaiblir la compétitivité et à nuire à la croissance économique du pays. La contribution que nous apportons à travers ce travail est de trois ordres. Dans un premier temps, nous proposons un nouveau regard par rapport à l’intégration des jeunes sur le marché du travail. Plutôt que d’examiner si les individus obtiennent un contrat de travail stable ou non, nous adoptons une approche qui s’intéresse à la qualité de l’appariement « emploi – compétences » de jeunes entrant fraîchement dans la vie active. Nos travaux fournissent des résultats empiriques qui mettent en évidence les différentes théories de recherche d’emploi. Dans un second temps, en raison du considérable défi que représente l'identification et l'évaluation des pratiques discriminatoires sur le marché du travail, nous proposons une approche innovatrice et efficace pour examiner le phénomène du plafond de verre (barrière invisible à l’accès des postes de décision mieux rémunérés). Dans la dernière partie de cette thèse, nous proposons un modèle économétrique théorique qui améliore la correction du problème de biais de sélection pour les modèles de frontière stochastique. / This doctoral thesis addresses issues related to employees’ imperfect information on the labour market and discrimination, generally all direct consequences of labour underpayment or “earnings inefficiency”. Workers are in a situation of earnings inefficiency when they do not receive the full potential remuneration corresponding to their human capital endowment: unfair pay for greater stock of human capital. This situation is problematic from a policy-makers point of view as it could weaken work incentives, discourage investments in human capital, and harm economic growth and competitiveness. It could also widen inequality within the society and contribute to the increase in relative poverty.The contribution we make through this work is threefold. First, we examine the integration of young people into the labour market from a new angle. Instead of examining whether individuals obtain stable employment or not, we use an approach that focuses on the quality of the job matching for young people entering the workforce and lacking labour market information. This first chapter provides empirical evidence on job search theories. In a second chapter, because of the considerable challenge of identifying and assessing discriminatory practices in the labour market, we propose an innovative and effective approach to examine the phenomenon of the glass ceiling (an invisible barrier to management positions associated with higher earnings). Finally, the last part of this doctoral thesis is devoted to improving the econometric approach we use. We propose a theoretical econometric model that improves correction for sample selection bias with stochastic frontier models.

Dans cette thèse, nous nous intéressons à la recherche d’images similaires avec des descripteurs structurés par découpages d’images sur les graphes.Nous proposons une nouvelle approche appelée “bag-of-bags of words” (BBoW) pour la recherche d’images par le contenu (CBIR). Il s’agit d’une extension du modèle classique dit sac-de-mots (bag of words - BoW). Dans notre approche, une image est représentée par un graphe placé sur une grille régulière de pixels d’image. Les poids sur les arêtes dépendent de caractéristiques locales de couleur et texture. Le graphe est découpé en un nombre fixe de régions qui constituent une partition irrégulière de l’image. Enfin, chaque partition est représentée par sa propre signature suivant le même schéma que le BoW. Une image est donc décrite par un ensemble de signatures qui sont ensuite combinées pour la recherche d’images similaires dans une base de données. Contrairement aux méthodes existantes telles que Spatial Pyramid Matching (SPM), le modèle BBoW proposé ne repose pas sur l’hypothèse que des parties similaires d’une scène apparaissent toujours au même endroit dans des images d’une même catégorie. L’extension de cette méthode ` a une approche multi-échelle, appelée Irregular Pyramid Matching (IPM), est ´ également décrite. Les résultats montrent la qualité de notre approche lorsque les partitions obtenues sont stables au sein d’une même catégorie d’images. Une analyse statistique est menée pour définir concrètement la notion de partition stable.Nous donnons nos résultats sur des bases de données pour la reconnaissance d’objets, d’indexation et de recherche d’images par le contenu afin de montrer le caractère général de nos contributions / Image representation is a fundamental question for several computer vision tasks. The contributions discussed in this thesis extend the basic bag-of-words representations for the tasks of object recognition and image retrieval.In the present thesis, we are interested in image description by structural graph descriptors. We propose a model, named bag-of-bags of words (BBoW), to address the problems of object recognition (for object search by similarity), and especially Content-Based Image Retrieval (CBIR) from image databases. The proposed BBoW model, is an approach based on irregular pyramid partitions over the image. An image is first represented as a connected graph of local features on a regular grid of pixels. Irregular partitions (subgraphs) of the image are further built by using graph partitioning methods. Each subgraph in the partition is then represented by its own signature. The BBoW model with the aid of graphs, extends the classical bag-of-words (BoW) model by embedding color homogeneity and limited spatial information through irregular partitions of an image. Compared to existing methods for image retrieval, such as Spatial Pyramid Matching (SPM), the BBoW model does not assume that similar parts of a scene always appear at the same location in images of the same category. The extension of the proposed model to pyramid gives rise to a method we named irregular pyramid matching (IPM).The experiments demonstrate the strength of our approach for image retrieval when the partitions are stable across an image category. The statistical analysisof subgraphs is fulfilled in the thesis. To validate our contributions, we report results on three related computer vision datasets for object recognition, (localized)content-based image retrieval and image indexing. The experimental results in a database of 13,044 general-purposed images demonstrate the efficiency and effectiveness of the proposed BBoW framework.

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique. / Despite constant progress in terms of available computational power, memory and amount of data, machine learning algorithms need to be efficient in how they use them. Although minimizing cost is an obvious major concern, another motivation is to attempt to design algorithms that can learn as efficiently as intelligent species. This thesis tackles the problem of efficient learning through various papers dealing with a wide range of machine learning algorithms: this topic is seen both from the point of view of computational efficiency (processing power and memory required by the algorithms) and of statistical efficiency (n umber of samples necessary to solve a given learning task).The first contribution of this thesis is in shedding light on various statistical inefficiencies in existing algorithms. Indeed, we show that decision trees do not generalize well on tasks with some particular properties (chapter 3), and that a similar flaw affects typical graph-based semi-supervised learning algorithms (chapter 5). This flaw is a form of curse of dimensionality that is specific to each of these algorithms. For a subclass of neural networks, called sum-product networks, we prove that using networks with a single hidden layer can be exponentially less efficient than when using deep networks (chapter 4). Our analyses help better understand some inherent flaws found in these algorithms, and steer research towards approaches that may potentially overcome them. We also exhibit computational inefficiencies in popular graph-based semi-supervised learning algorithms (chapter 5) as well as in the learning of mixtures of Gaussians with missing data (chapter 6). In both cases we propose new algorithms that make it possible to scale to much larger datasets. The last two chapters also deal with computational efficiency, but in different ways. Chapter 7 presents a new view on the contrastive divergence algorithm (which has been used for efficient training of restricted Boltzmann machines). It provides additional insight on the reasons why this algorithm has been so successful. Finally, in chapter 8 we describe an application of machine learning to video games, where computational efficiency is tied to software and hardware engineering constraints which, although often ignored in research papers, are ubiquitous in practice.

La question de recherche des objets vidéo basés sur le contenu lui-même, est de plus en plus difficile et devient un élément obligatoire pour les moteurs de recherche vidéo. Cette thèse présente un cadre pour la recherche des objets vidéo définis par l'utilisateur et apporte deux grandes contributions. La première contribution, intitulée DOOR (Dynamic Object Oriented Retrieval), est un cadre méthodologique pour la recherche et récupération des instances d'objets vidéo sélectionnés par un utilisateur, tandis que la seconde contribution concerne le support offert pour la recherche des vidéos, à savoir la navigation dans les vidéo, le système de récupération de vidéos et l'interface avec son architecture sous-jacente.Dans le cadre DOOR, l'objet comporte une représentation hybride obtenues par une sur-segmentation des images, consolidé avec la construction des graphs d'adjacence et avec l'agrégation des points d'intérêt. L'identification des instances d'objets à travers plusieurs vidéos est formulée comme un problème d'optimisation de l'énergie qui peut approximer un tache NP-difficile. Les objets candidats sont des sous-graphes qui rendent une énergie optimale vers la requête définie par l'utilisateur. Quatre stratégies d'optimisation sont proposées: Greedy, Greedy relâché, recuit simulé et GraphCut. La représentation de l'objet est encore améliorée par l'agrégation des points d'intérêt dans la représentation hybride, où la mesure de similarité repose sur une technique spectrale intégrant plusieurs types des descripteurs. Le cadre DOOR est capable de s'adapter à des archives vidéo a grande échelle grâce à l'utilisation de représentation sac-de-mots, enrichi avec un algorithme de définition et d'expansion de la requête basée sur une approche multimodale, texte, image et vidéo. Les techniques proposées sont évaluées sur plusieurs corpora de test TRECVID et qui prouvent leur efficacité.La deuxième contribution, OVIDIUS (On-line VIDeo Indexing Universal System) est une plate-forme en ligne pour la navigation et récupération des vidéos, intégrant le cadre DOOR. Les contributions de cette plat-forme portent sur le support assuré aux utilisateurs pour la recherche vidéo - navigation et récupération des vidéos, interface graphique. La plate-forme OVIDIUS dispose des fonctionnalités de navigation hiérarchique qui exploite la norme MPEG-7 pour la description structurelle du contenu vidéo. L'avantage majeur de l'architecture propose c'est sa structure modulaire qui permet de déployer le système sur terminaux différents (fixes et mobiles), indépendamment des systèmes d'exploitation impliqués. Le choix des technologies employées pour chacun des modules composant de la plate-forme est argumentée par rapport aux d'autres options technologiques.