Nous assistons ces dernières années à une émergence constante de nouvelles applications, notamment pour les services audiovisuels. Ces applications imposent au réseau un certain nombre de contraintes pour qu’elles puissent fonctionner correctement. Le développement de mécanismes permettant d’offrir une garantie à ces contraintes, est donc devenu un objectif crucial. La norme IEEE 802.16j est l’une des solutions sans fil qui propose plus de ressources afin de supporter les nouveaux services de télécommunications. Dans la présente thèse, nous focalisons notre étude sur la problématique de la qualité de service dans les réseaux WiMAX relais. Nos contributions se regroupent à travers les étapes ci-dessous : Nous proposons un protocole de routage multicast pour les services IPTV (HDTV, SD-TV, Web-TV et Mobile-TV). Ce protocole repose d’une part sur un nouveau mécanisme de construction de l’arbre multicast basé sur les nombres premiers et d’autre part, sur une nouvelle méthode d’agrégation basée sur le standard de compression Vidéo «SVC». L’objectif est de supporter l’hétérogénéité des utilisateurs tout en optimisant la consommation des ressources. Par ailleurs, nous étudions le problème d’ordonnancement dans les réseaux WiMAX. Nous proposons un algorithme d’ordonnancement adaptatif AWRR, ce dernier se base sur une technique à charge pondérée. L’objectif est d’ajuster dynamiquement le poids de chaque classe de service, en prenant en compte la charge de la file d’attente et les contraintes de la QoS. Enfin, nous nous intéressons à l’étude de la problématique du chemin optimal contraint. Nous proposons une solution déterministe basée sur une fonction de coût. Notre fonction permet aussi d’assurer le contrôle d’admission, elle se base sur deux fonctions de coût élémentaires qui prennent en compte quatre critères de QoS. / Over recent years, new applications steadily developed in a tremendous space, especially in audiovisual services area. The present applications have some of constraints to work properly. The developments of mechanism which enable to overcome these constraints become a critical issue in this area. The IEEE 802.16j standard is one of wireless communication technology which offering more resources to support new telecommunication services. In this thesis, we focus our research on the problem of quality of service (QoS) inWiMAX relay networks. Our contributions are classified as follows : we proposed a multicast routing protocol for IPTV services (such as HD-TV, SD-TV, Web-TV and Mobile-TV). This proposed protocol used a new multicast tree construction mechanism based-on prime numbers. We also developed a new aggregation method based on standard video compression called Scalable Video Coding (SVC). Our goal is to support user’s heterogeneity while optimizing resources consumption. In addition, we studied the problem of scheduling inWiMAX networks.We proposed an adaptive scheduling algorithm AWRR for IPTV services. The aim of this method is to support QoS constraints by using two schedulers, and assigning a dynamic value to each service queue. Finally, we interested to study about the problem of path selection. We proposed a solution based on a deterministic cost function. This function also ensures admission control based on two basic cost functions which include four QoS criteria. This thesis has been prepared in the MIPS/GRTC laboratory, University of Haute Alsace, under a research contract external (CRE) framework with France Telecom R&D. All proposed mechanisms were evaluated by the simulator QualNet, Matlab and mathematical analysis.

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

L’enjeu de planification de vol à bord d’un hélicoptère en tenant compte des différents paramètres environnementaux constitue un facteur clé dans le secteur aéronautique afin d’assurer une mission en toute sécurité avec un coût réduit. Ce défi concerne à la fois la phase de préparation de la mission sur une station au sol mais aussi en cours de vol pour faire face à un évènement imprévu. Nous citons un premier exemple de mission de type recherche et sauvetage qui dispose d’un temps limité pour localiser et rechercher des personnes en danger. Pour ce faire, le plan de vol généré doit suivre le relief du terrain à des altitudes relativement basses entre des points de passage désignés. L’objectif est de permettre au pilote de localiser une victime dans une durée bornée. Un deuxième type de mission comme l’assistance médicale a la particularité d’assurer un vol qui favorise le confort du passager ainsi qu’une route qui minimise le temps de vol selon la criticité de la situation. Pendant la phase dynamique, lorsqu’il s’agit d’un événement complexe telle qu’une panne moteur, une replanification de la mission devient nécessaire afin de trouver un chemin aérien qui permet d’atterrir en toute sécurité dans les plus brefs délais. Dans un autre exemple comme l’évitement d’obstacle dynamique ou de zone dangereuse, il s’agit de calculer un autre plan de vol pour atteindre la destination. Cependant à ce jour, les pilotes ne bénéficient pas de système d’autoroutage 3D permettant la replanification dynamique de mission face à une situation d’urgence. Face au défi de génération d’un plan de vol optimal, nos réflexions profondes ont abouti à la proposition d’un nouveau système de planification de chemin, pour des aéronefs, dédié à la préparation de mission avant le vol ainsi qu’à la replanification dynamique en cours de vol face à une situation d’urgence. Le système de planification peut être déployé sur une station au sol ou bien intégré comme fonction avionique au sein de l’aéronef. Les résultats obtenus ont abouti à un brevet déposé devant l’INPI et à plusieurs actions de transfert technologique au sein d’Airbus Hélicoptères. Le système s’appuie sur des techniques de discrétisation de l’espace et de calcul du plus court chemin afin de générer automatiquement des solutions flexibles en terme de profil de chemin en respectant plusieurs contraintes liées à l’appareil, le terrain et l’environnement. La solution proposée est générique et capable de s’adapter selon le type de l’aéronef, le type de la mission et la fonction objectif à minimiser. Le système de planification peut offrir des solutions avec différents compromis entre le temps d’exécution et la qualité du chemin selon le temps disponible qui peut être corrélé avec la criticité de la situation. Le fonctionnement du système de planification de chemin se compose principalement de deux phases : le prétraitement et le routage. La phase de prétraitement permet une discrétisation multi-altitude de l’espace 3D selon une précision donnée et la génération automatique d’un graphe de navigation avec une connexité paramétrable. La phase de routage 3D calcule le chemin en prenant en considération un ensemble de contraintes telles que les limitations angulaires en horizontal et en vertical et une fonction objectif à minimiser tels que la distance, le carburant, le temps, etc. Lors de la phase d’exploration du graphe, le système de planification peut communiquer avec le modèle de performance de l’appareil afin de minimiser une fonction coût liée à la performance et de s’assurer au fur et à mesure de la faisabilité de la mission. La génération automatique des plans de vol et la replanification dynamique représentent une brique essentielle pour concevoir des systèmes d’assistance au pilote ainsi que des aéronefs autonomes. / Helicopter flight planning is a key factor in the aeronautics domain in order to ensure a safe mission at a reduced cost taking into consideration different environmental parameters like terrain, weather, emergency situations, etc. This challenge concerns both the mission preparation phase using a ground station and also during the flight to cope with a complex event (mechanical failure, dynamic obstacle, bad weather conditions, etc.). We quote as a first example a Search and Rescue mission that should be performed in limited time to locate persons in danger. To achieve that, the generated flight path must follow the terrain profile at relatively low altitudes crossing the predefined waypoints. The objective is to allow the pilot to locate a victim in a short time. Another example for a mission of medical assistance where the helicopter should ensure the comfort of patients as well as minimizing the flight time to respect critical situations. During the flight, when a complex event occurs such as engine failure, re-planning the mission becomes necessary in order to find a new path that could guarantee safe landing. Unfortunately, pilots do not benefit from an embedded 3D path planning system that enables dynamic mission re-planning in case of emergency. To tackle the challenge of generating an optimal flight plan, we proposed new path planning system dedicated to mission preparation and dynamic path re-planning during critical situations. The planning system can be deployed on a ground station or embedded as an avionic function in the aircraft. The achieved results are registered as a patent at National Institute of Intellectual Property and deployed inside Airbus Helicopters through several technology transfers. The system relies on 3D space discretization and shortest path planning techniques to generate automatically flexible path profiles that respect several. The proposed solution is generic and is able to adapt to the aircraft model, mission and the objective function to be minimized. The path planning system can offer solutions with different tradeoffs between timing and path quality within the available runtime depending on the criticality of the situation. The functioning of the path planning system consists mainly of two phases : preprocessing and routing phase. The preprocessing allows a multi-altitude discretization of the 3D space according to a given precision and generate automatically a navigation graph with a configurable density. The 3D routing phase calculates the path by considering a set of constraints such as horizontal and vertical angular limitations and the objective function such as distance, fuel, time, etc. During the graph exploration phase, the path planning system can communicate with the aircraft performance model to evaluate a given criterion. Automatic flight path generation is an essential building block for designing pilot assistance systems and autonomous aircraft. In summary, we succeeded to reach the industrial expectations namely : the evaluation of mission feasibility, performances improvement, navigation workload reduction, as well as improving the flight safety. In order to realize the proposed solution, we designed a new tool for automatic 3D flight path planning. We named our tool DTANAV : Demonstration Tool for Aircraft NAVigation. It allows to apply the proposed planning process on real scenarios. Through the tool interface, the user has the possibility to set the parameters related to the mission (starting point, end point, aircraft model, navigation ceiling, etc.). Other algorithmic parameters are defined in order to control the quality and the profile of the generated solution.

Le maintien de la connectivité à travers les paysages urbains, par nature très fragmentés, est un enjeu majeur de conservation de la biodiversité urbaine. On observe une prise en compte croissante de la connectivité dans les politiques d’aménagement du territoire, notamment avec l’établissement de la trame verte et bleue. De multiples outils cartographiques permettent de mettre en évidence les continuités écologiques (zones de forte connectivité), mais leur validation fonctionnelle fait souvent défaut. L’objectif de cette thèse est de valider les prédictions d’un modèle de chemin de moindre coût, sur plusieurs villes et avec différents modèles biologiques. Les espèces étudiées présentent différents modes et capacités de dispersion (vol, marche, reptation) et des exigences écologiques spécifiques (préférences pour les milieux herbacés ou boisés). Des protocoles de validation basés sur l’écologie du mouvement et la génétique du paysage sont appliqués, dans un souci de réplication (au sein de plusieurs villes) et de contrôle de la variabilité inter-individuelle. Nos résultats montrent des mouvements accrus au sein des continuités écologiques comparés à ceux observés en contextes paysagers prédits comme non connectés : les hérissons transloqués s’y déplacent sur des distances plus longues, plusieurs passereaux répondent à la repasse de chant sur de plus longues distances et les papillons de nuit montrent des taux de recapture beaucoup plus élevés. Par ailleurs, les analyses indirectes réalisées sur l’escargot petit-gris montrent une relation assez faible entre la différenciation génétique des populations et les modèles de connectivité. Ce travail fournit des arguments scientifiques pour soutenir la mise en place de continuités écologiques en milieu urbain. / Maintaining connectivity across urban landscape, intrinsically fragmented, is a major issue of urban biodiversity conservation. Connectivity is increasingly taken into account by policy and stakeholders, especially through the establishment of the blue-green infrastructure. Multiple mapping tools allow to detect ecological networks (highly connected areas), however their functionnal validation is often lacking. The objective of this study is to validate least cost path analysis predictions in several cities with different biological models. Studied species vary in terms of dispersal means and capacities (flight, walk, crawling) and habitat requirement (e.g. herbaceous or forested habitats). Several protocols based on movement ecology and landscape genetic are applied, focusing on replication (within and among cities) and control of inter-individual variability. Our results indicate that movement is increased in predicted ecological networks when compared with areas predicted as poorly connected: the translocated hedgehogs travelled longer distances, several passerine responded to song playback over longer distances, and moths showed increased recapture rates. Indirect analysis on the garden snail showed a weak relation between population genetic differentiation and connectivity models. This work provides scientific support for the establishment of ecological networks in urban landscapes.

Ce travail de thèse s’est tout d’abord attaché à comprendre comment la prise en compte du temps de téléchargement, autrement dit, de la latence, lors de la mise en cache ou de la transmission de données pouvait contribuer aux performances du téléchargement dans les réseaux de caches dont ICN. Nous y introduisons un mécanisme distribué novateur qui décide de l’opportunité de conserver un objet en considérant que plus il a été long à télécharger plus intéressant il semble de le soumettre au cache sous-jacent. Nous montrons que ce nouveau mécanisme surpasse en de nombreux points l’état de l’art, que ce soit du point de vue de la réduction du temps moyen de téléchargement à partir de caches LRU, et de son écart-type (jusqu’à −60% ), que de celui de la vitesse de convergence vers ceux-ci. Dans une seconde phase, nous avons optimisé conjointement les fonctions de mises en cache et de distribution multi-chemin de requêtes de contenus. Troisièmement, nous avons étudié l’équité vis-à-vis des contenus au sein des réseaux de caches et plus particulièrement, d’ICN. Il en ressort que seule suffit une allocation équitable de la bande passante entre les contenus pour que l’équité d’ICN soit complète. Notre dernière contribution vise à aider au passage à l’échelle d’ICN dans contexte où deviennent réalités l’Internet des Objets et son espace de nommage illimité. Nous avons proposé une approche nouvelle au routage dans les réseaux centrés sur l’information, nommée AFFORD, qui combine apprentissage automatique et diffusion aléatoire. / This thesis investigates how making content caching and forwarding latency-aware can improve data delivery performance in Information-Centric Networks (ICN). We introduce a new mechanism that leverages retrieval time observations to decide whether to store an object in a network cache, based on the expected delivery time improvement. We demonstrate that our distributed latency-aware caching mechanism, LAC+, outperforms state of the art proposals and results in a reduction of the content mean delivery time and standard deviation of LRU caches by up to 60%, along with a fast convergence to these figures. In a second phase, we conjointly optimize the caching function and the multipath request forwarding strategies. To this purpose, we introduce the mixed forwarding strategy LB-Perf, directing the most popular content towards the same next hops to foster egress caches convergence, while load-balancing the others. Third, we address ICN fairness to contents. We show that traditional ICN caching, which favors the most popular objects, does not prevent the network from being globally fair, content-wise. The incidence of our findings comforts the ICN community momentum to improve LFU cache management policy and its approximations. We demonstrate that in-network caching leads to content-wise fair network capacity sharing as long as bandwidth sharing is content-wise fair. Finally, we contribute to the research effort aiming to help ICN Forwarding Information Base scale when confronted to the huge IoT era’s namespace.We propose AFFORD, a novel view on routing in named-data networking that combines machine learning and stochastic forwarding.

Les microrobots magnétiques, qui nagent en utilisant des modes de propulsion bio-inspirées, apparaissent très prometteurs pour la manipulation et la caractérisation d'objets à l'échelle microscopique dans des environnements confinés et très restreints, contrairement aux méthodes de micromanipulation classiques. La littérature propose une variété de microrobots avec des formes géométriques et des propriétés magnétiques différentes. Les commandes en mouvement proposées restent cependant simples, peu précises et insuffisamment robustes pour la réalisation de tâches réelles. De plus, il subsiste une incertitude sur le fait que tous ces micronageurs artificiels peuvent accomplir les mêmes tâches avec une performance égale. L'objectif de cette thèse consiste alors à proposer : des commandes de mouvement génériques par asservissement visuel dans l'espace pour tous les types de micronageurs avec des contraintes non holonomes afin d'améliorer les performances de ces micronageurs, un ensemble de critères de comparaison entre des robots avec une topologie ou un mode de propulsion différents pour le choix du micronageur le plus performant pour réaliser une tâche particulière. Des lois de commande de suivi de chemin dans l'espace sont synthétisées et validées expérimentalement sur des nageurs hélicoïdal et flexible sous différentes conditions. Ces robots évoluent dans un fluide à faible nombre de Reynolds, imitant respectivement le mécanisme de locomotion des bactéries et des spermatozoïdes et sont actionnés par un champ magnétique uniforme. Ces deux classes de nageurs possèdent une géométrie et un mode d'actionnement différents. Leurs performances sont ainsi comparées. / Magnetic microrobots, which swim using bio-inspired propulsion modes, appear very promising for manipulation and characterization of objects at microscopic scale inside confined and very restricted environments, unlike conventional micromanipulation methods. The literature proposes a variety of microrobots with different geometric shapes and magnetic properties. However, the motion controls proposed remain simple, imprecise and insufficiently robust for performing real tasks. In addition, there is still uncertainty that all these artificial microswimmers can accomplish the same tasks with equal performance. The objective of this thesis is thus to propose : generic motion controls by visual servoing in space for all kinds of microswimmers with nonholonomic constraints in order to improve the microswimmer performances, a set of comparison criteria between robots with a different topology or propulsion mode for choosing the most efficient microswimmer in order to perform a specific task. Path following control laws in space are synthesized and experimentally validated on helical and flexible swimmers under different conditions. These robots operate in low Reynolds number fluid, imitating respectively bacteria and spermatozoa and are actuated with uniform magnetic field. These two classes of swimmers have different actuation mode and geometric shape. Their performances are thus compared according to the task to be performed, the environment in which the robots evolve and the manufacturing constraints.

Cette thèse présente de nouvelles méthodes pour l'application de la prédiction structurée en vision numérique et en imagerie médicale.Nos nouvelles contributions suivent quatre axes majeurs.La première partie de cette thèse étudie le problème d'inférence d'ordre supérieur.Nous présentons une nouvelle famille de problèmes de minimisation d'énergie discrète, l'étiquetage parcimonieux, encourageant la parcimonie des étiquettes.C'est une extension naturelle des problèmes connus d'étiquetage de métriques aux potentiels d'ordre élevé.Nous proposons par ailleurs une généralisation du modèle Pn-Potts, le modèle Pn-Potts hiérarchique.Enfin, nous proposons un algorithme parallélisable à proposition de mouvements avec de fortes bornes multiplicatives pour l'optimisation du modèle Pn-Potts hiérarchique et l'étiquetage parcimonieux.La seconde partie de cette thèse explore le problème de classement en utilisant de l'information d'ordre élevé.Nous introduisons deux cadres différents pour l'incorporation d'information d'ordre élevé dans le problème de classement.Le premier modèle, que nous nommons SVM binaire d'ordre supérieur (HOB-SVM), optimise une borne supérieure convexe sur l'erreur 0-1 pondérée tout en incorporant de l'information d'ordre supérieur en utilisant un vecteur de charactéristiques jointes.Le classement renvoyé par HOB-SVM est obtenu en ordonnant les exemples selon la différence entre la max-marginales de l'affectation d'un exemple à la classe associée et la max-marginale de son affectation à la classe complémentaire.Le second modèle, appelé AP-SVM d'ordre supérieur (HOAP-SVM), s'inspire d'AP-SVM et de notre premier modèle, HOB-SVM.Le modèle correspond à une optimisation d'une borne supérieure sur la précision moyenne, à l'instar d'AP-SVM, qu'il généralise en permettant également l'incorporation d'information d'ordre supérieur.Nous montrons comment un optimum local du problème d'apprentissage de HOAP-SVM peut être déterminé efficacement grâce à la procédure concave-convexe.En utilisant des jeux de données standards, nous montrons empiriquement que HOAP-SVM surpasse les modèles de référence en utilisant efficacement l'information d'ordre supérieur tout en optimisant directement la fonction d'erreur appropriée.Dans la troisième partie, nous proposons un nouvel algorithme, SSVM-RP, pour obtenir un chemin de régularisation epsilon-optimal pour les SVM structurés.Nous présentons également des variantes intuitives de l'algorithme Frank-Wolfe pour l'optimisation accélérée de SSVM-RP.De surcroît, nous proposons une approche systématique d'optimisation des SSVM avec des contraintes additionnelles de boîte en utilisant BCFW et ses variantes.Enfin, nous proposons un algorithme de chemin de régularisation pour SSVM avec des contraintes additionnelles de positivité/negativité.Dans la quatrième et dernière partie de la thèse, en appendice, nous montrons comment le cadre de l'apprentissage semi-supervisé des SVM à variables latentes peut être employé pour apprendre les paramètres d'un problème complexe de recalage déformable.Nous proposons un nouvel algorithme discriminatif semi-supervisé pour apprendre des métriques de recalage spécifiques au contexte comme une combinaison linéaire des métriques conventionnelles.Selon l'application, les métriques traditionnelles sont seulement partiellement sensibles aux propriétés anatomiques des tissus.Dans ce travail, nous cherchons à déterminer des métriques spécifiques à l'anatomie et aux tissus, par agrégation linéaire de métriques connues.Nous proposons un algorithme d'apprentissage semi-supervisé pour estimer ces paramètres conditionnellement aux classes sémantiques des données, en utilisant un jeu de données faiblement annoté.Nous démontrons l'efficacité de notre approche sur trois jeux de données particulièrement difficiles dans le domaine de l'imagerie médicale, variables en terme de structures anatomiques et de modalités d'imagerie. / This thesis develops novel methods to enable the use of structured prediction in computer vision and medical imaging. Specifically, our contributions are four fold. First, we propose a new family of high-order potentials that encourage parsimony in the labeling, and enable its use by designing an accurate graph cuts based algorithm to minimize the corresponding energy function. Second, we show how the average precision SVM formulation can be extended to incorporate high-order information for ranking. Third, we propose a novel regularization path algorithm for structured SVM. Fourth, we show how the weakly supervised framework of latent SVM can be employed to learn the parameters for the challenging deformable registration problem.In more detail, the first part of the thesis investigates the high-order inference problem. Specifically, we present a novel family of discrete energy minimization problems, which we call parsimonious labeling. It is a natural generalization of the well known metric labeling problems for high-order potentials. In addition to this, we propose a generalization of the Pn-Potts model, which we call Hierarchical Pn-Potts model. In the end, we propose parallelizable move making algorithms with very strong multiplicative bounds for the optimization of the hierarchical Pn-Potts model and the parsimonious labeling.Second part of the thesis investigates the ranking problem while using high-order information. Specifically, we introduce two alternate frameworks to incorporate high-order information for the ranking tasks. The first framework, which we call high-order binary SVM (HOB-SVM), optimizes a convex upperbound on weighted 0-1 loss while incorporating high-order information using joint feature map. The rank list for the HOB-SVM is obtained by sorting samples using max-marginals based scores. The second framework, which we call high-order AP-SVM (HOAP-SVM), takes its inspiration from AP-SVM and HOB-SVM (our first framework). Similar to AP-SVM, it optimizes upper bound on average precision. However, unlike AP-SVM and similar to HOB-SVM, it can also encode high-order information. The main disadvantage of HOAP-SVM is that estimating its parameters requires solving a difference-of-convex program. We show how a local optimum of the HOAP-SVM learning problem can be computed efficiently by the concave-convex procedure. Using standard datasets, we empirically demonstrate that HOAP-SVM outperforms the baselines by effectively utilizing high-order information while optimizing the correct loss function.In the third part of the thesis, we propose a new algorithm SSVM-RP to obtain epsilon-optimal regularization path of structured SVM. We also propose intuitive variants of the Block-Coordinate Frank-Wolfe algorithm (BCFW) for the faster optimization of the SSVM-RP algorithm. In addition to this, we propose a principled approach to optimize the SSVM with additional box constraints using BCFW and its variants. In the end, we propose regularization path algorithm for SSVM with additional positivity/negativity constraints.In the fourth and the last part of the thesis (Appendix), we propose a novel weakly supervised discriminative algorithm for learning context specific registration metrics as a linear combination of conventional metrics. Conventional metrics can cope partially - depending on the clinical context - with tissue anatomical properties. In this work we seek to determine anatomy/tissue specific metrics as a context-specific aggregation/linear combination of known metrics. We propose a weakly supervised learning algorithm for estimating these parameters conditionally to the data semantic classes, using a weak training dataset. We show the efficacy of our approach on three highly challenging datasets in the field of medical imaging, which vary in terms of anatomical structures and image modalities.

Le traitement massif et automatique des données requiert le développement de techniques de filtration des informations les plus importantes. Parmi ces méthodes, celles présentant des structures parcimonieuses se sont révélées idoines pour améliorer l’efficacité statistique et computationnelle des estimateurs, dans un contexte de grandes dimensions. Elles s’expriment souvent comme solution de la minimisation du risque empirique régularisé s’écrivant comme une somme d’un terme lisse qui mesure la qualité de l’ajustement aux données, et d’un terme non lisse qui pénalise les solutions complexes. Cependant, une telle manière d’inclure des informations a priori, introduit de nombreuses difficultés numériques pour résoudre le problème d’optimisation sous-jacent et pour calibrer le niveau de régularisation. Ces problématiques ont été au coeur des questions que nous avons abordées dans cette thèse.Une technique récente, appelée «Screening Rules», propose d’ignorer certaines variables pendant le processus d’optimisation en tirant bénéfice de la parcimonie attendue des solutions. Ces règles d’élimination sont dites sûres lorsqu’elles garantissent de ne pas rejeter les variables à tort. Nous proposons un cadre unifié pour identifier les structures importantes dans ces problèmes d’optimisation convexes et nous introduisons les règles «Gap Safe Screening Rules». Elles permettent d’obtenir des gains considérables en temps de calcul grâce à la réduction de la dimension induite par cette méthode. De plus, elles s’incorporent facilement aux algorithmes itératifs et s’appliquent à un plus grand nombre de problèmes que les méthodes précédentes.Pour trouver un bon compromis entre minimisation du risque et introduction d’un biais d’apprentissage, les algorithmes d’homotopie offrent la possibilité de tracer la courbe des solutions en fonction du paramètre de régularisation. Toutefois, ils présentent des instabilités numériques dues à plusieurs inversions de matrice, et sont souvent coûteux en grande dimension. Aussi, ils ont des complexités exponentielles en la dimension du modèle dans des cas défavorables. En autorisant des solutions approchées, une approximation de la courbe des solutions permet de contourner les inconvénients susmentionnés. Nous revisitons les techniques d’approximation des chemins de régularisation pour une tolérance prédéfinie, et nous analysons leur complexité en fonction de la régularité des fonctions de perte en jeu. Il s’ensuit une proposition d’algorithmes optimaux ainsi que diverses stratégies d’exploration de l’espace des paramètres. Ceci permet de proposer une méthode de calibration de la régularisation avec une garantie de convergence globale pour la minimisation du risque empirique sur les données de validation.Le Lasso, un des estimateurs parcimonieux les plus célèbres et les plus étudiés, repose sur une théorie statistique qui suggère de choisir la régularisation en fonction de la variance des observations. Ceci est difficilement utilisable en pratique car, la variance du modèle est une quantité souvent inconnue. Dans de tels cas, il est possible d’optimiser conjointement les coefficients de régression et le niveau de bruit. Ces estimations concomitantes, apparues dans la littérature sous les noms de Scaled Lasso, Square-Root Lasso, fournissent des résultats théoriques aussi satisfaisants que celui du Lasso tout en étant indépendant de la variance réelle. Bien que présentant des avancées théoriques et pratiques importantes, ces méthodes sont aussi numériquement instables et les algorithmes actuellement disponibles sont coûteux en temps de calcul. Nous illustrons ces difficultés et nous proposons à la fois des modifications basées sur des techniques de lissage pour accroitre la stabilité numérique de ces estimateurs, ainsi qu’un algorithme plus efficace pour les obtenir. / Massive and automatic data processing requires the development of techniques able to filter the most important information. Among these methods, those with sparse structures have been shown to improve the statistical and computational efficiency of estimators in a context of large dimension. They can often be expressed as a solution of regularized empirical risk minimization and generally lead to non differentiable optimization problems in the form of a sum of a smooth term, measuring the quality of the fit, and a non-smooth term, penalizing complex solutions. Although it has considerable advantages, such a way of including prior information, unfortunately introduces many numerical difficulties both for solving the underlying optimization problem and to calibrate the level of regularization. Solving these issues has been at the heart of this thesis. A recently introduced technique, called "Screening Rules", proposes to ignore some variables during the optimization process by benefiting from the expected sparsity of the solutions. These elimination rules are said to be safe when the procedure guarantees to not reject any variable wrongly. In this work, we propose a unified framework for identifying important structures in these convex optimization problems and we introduce the "Gap Safe Screening Rules". They allows to obtain significant gains in computational time thanks to the dimensionality reduction induced by this method. In addition, they can be easily inserted into iterative algorithms and apply to a large number of problems.To find a good compromise between minimizing risk and introducing a learning bias, (exact) homotopy continuation algorithms offer the possibility of tracking the curve of the solutions as a function of the regularization parameters. However, they exhibit numerical instabilities due to several matrix inversions and are often expensive in large dimension. Another weakness is that a worst-case analysis shows that they have exact complexities that are exponential in the dimension of the model parameter. Allowing approximated solutions makes possible to circumvent the aforementioned drawbacks by approximating the curve of the solutions. In this thesis, we revisit the approximation techniques of the regularization paths given a predefined tolerance and we propose an in-depth analysis of their complexity w.r.t. the regularity of the loss functions involved. Hence, we propose optimal algorithms as well as various strategies for exploring the parameters space. We also provide calibration method (for the regularization parameter) that enjoys globalconvergence guarantees for the minimization of the empirical risk on the validation data.Among sparse regularization methods, the Lasso is one of the most celebrated and studied. Its statistical theory suggests choosing the level of regularization according to the amount of variance in the observations, which is difficult to use in practice because the variance of the model is oftenan unknown quantity. In such case, it is possible to jointly optimize the regression parameter as well as the level of noise. These concomitant estimates, appeared in the literature under the names of Scaled Lasso or Square-Root Lasso, and provide theoretical results as sharp as that of theLasso while being independent of the actual noise level of the observations. Although presenting important advances, these methods are numerically unstable and the currently available algorithms are expensive in computation time. We illustrate these difficulties and we propose modifications based on smoothing techniques to increase stability of these estimators as well as to introduce a faster algorithm.

L’écriture littéraire de Kerouac est la manifestation de sa quête spirituelle sous la forme du chemin de l’écrit. Ce n’est pas exactement la route de l’écriture de On the Road, qui s’élance vers l’horizon comme l’autoroute américaine, lorsque l’on déroule le manuscrit sur le sol ou l’on lit les lignes de gauche à droite. Il s’agit plutôt de la manière par laquelle l’écrit forme un chemin pour que cette quête spirituelle s’oriente à travers l’œuvre, à travers la création de l’œuvre. À mi-chemin entre le français et l’anglais, écrivain beat visionnaire, Jack Kerouac explore toutes les formes d’écriture, de la prose à la forme la plus brève d’écrit littéraire, le haïku, afin de répéter et répéter des exercices littéraires de l’esprit qui lui permettront d’orienter sa quête spirituelle et de la traduire en mots. Plusieurs textes font office d’exercices d’écriture sur le parcours du corpus des écrits kerouaciens, mais c’est dans Some of the Dharma qu’on retrouve l’exemple le plus percutant des sentiers littéraires à travers lesquels s’est engouffrée sa quête spirituelle. Cette thèse examine la notion de chemin et les articulations de la quête spirituelle à travers quatre chapitres. Les deux premiers chapitres traitent respectivement des textes en français publiés en 2016 sous le titre La vie est d’hommage et du problème de la spontanéité sous l’angle du spirituel. Ils préparent ainsi la réflexion du troisième chapitre où il s’agit de comprendre comment Some of the Dharma peut être conçu comme le grand carnet laïque des chemins spirituels de Kerouac. Enfin, le quatrième chapitre expose la signification de l’imbrication de la prose et de la brièveté littéraire (notamment les haïkus et les koans), appuyée sur la conception d’un présent à la fois impermanent et éternel. Cet ensemble de réflexions mène à s’interroger sur le sens spirituel de la voie littéraire dans un monde sécularisé. Les défaites spirituelles de Kerouac sont aussi nombreuses et lui ont permis de s’orienter, n’ayant pas d’autres guides spirituels que sa propre écriture et ses lectures. L’écriture littéraire est avant tout chemin et la traversée de ce chemin mène là où nous sommes toujours. Kerouac en donne un exemple saisissant que cette thèse explicite par ses propres chemins de l’écrit. / Kerouac's literary writing is the manifestation of his spiritual quest formed by the path taken by the written word. This is not exactly the road of writing in On the Road, which rushes towards the horizon like the American highway, when you unroll the manuscript on the ground or you read the lines from left to right. Rather, it is the way in which the writing forms a path for this spiritual quest to find its way through the work, through the creation of the work. Halfway between French and English, the visionary beat writer Jack Kerouac explores all forms of writing, from prose to the briefest form of literary writing, the haiku, in order to repeat and rehearse literary exercises of the mind that will allow him to orient his spiritual quest and translate it into words. Several texts serve as writing exercises on the journey through the corpus of Kerouacian writings, but it is in Some of the Dharma that we find the most striking example of the literary paths through which his spiritual quest was launched. This thesis examines the notion of the way and the articulations of the spiritual quest through four chapters. The first two chapters discuss respectively the French texts published in 2016 under the title La vie est d'hommage and the problem of spontaneity from a spiritual perspective. They prepare the reflection developed in the third chapter, where the aim is to understand how Some of the Dharma can be conceived as the great lay notebook of Kerouac’s spiritual paths. Finally, the fourth chapter explains the meaning of the interweaving of prose and literary brevity (notably haikus and koans), based on the conception of a present that is both impermanent and eternal. These reflections lead us to question the spiritual meaning of the literary path in a secularized world. Kerouac’s spiritual defeats are numerous and have allowed him to find his way, having no other spiritual guides than his own writing and reading. Literary writing is above all a way and crossing this path leads to where we are, always. Kerouac gives a striking example of this, which this thesis makes explicit through its own writing paths.

Le cinéma constitue un langage qui témoigne du réel et de l'imaginaire. Et l'image est une forme d'écriture de ce langage. L'expérience qui sera ici relatée est celle de la genèse d'une transécriture cinématographique du recueil de poésie II n'y a plus de chemin, de Jacques Brault. Par ce processus de transécriture, les images mentales générées par la lecture deviennent images cinématographiques et témoignent d'une nouvelle forme d'écriture des poèmes. La transécriture ne s'effectue cependant pas uniquement par la réalisation d'images cinématographiques. Chaque lecteur, tout comme chaque spectateur, est aussi transécrivain. Utilisant les fragments d'images proposées par le poème et comblant les vides de l'univers décrit, le lecteur imagine le poème, crée des images mentales, réalisant pour lui-même un film intérieur. Par conséquent, plus il s'engage dans cette aventure, plus il se voit forcé d'adopter le parcours intrinsèque des images qui le manipulent.