Markovian processes have long been used to model stochastic environments. Reinforcement learning has emerged as a framework to solve sequential planning and decision making problems in such environments. In recent years, attempts were made to apply methods from reinforcement learning to construct adaptive treatment strategies, where a sequence of individualized treatments is learned from clinical data. Although these methods have proved to be useful in problems concerning sequential decision making, they cannot be applied in their current form to medical domains, as they lack widely accepted notions of confidence measures. Moreover, policies provided by most methods in reinforcement learning are often highly prescriptive and leave little room for the doctor's input. Without the ability to provide flexible guidelines and statistical guarantees, it is unlikely that these methods can gain ground within the medical community. This thesis introduces the new concept of non-deterministic policies to capture the user's decision making process. We use this concept to provide flexible choice to user among near-optimal solutions, and provide statistical guarantees for decisions with uncertainties. We provide two algorithms to propose flexible options to the user, while making sure the performance is always close to optimal. We then show how to provide confidence measures over the value function of Markovian processes, and finally use them to find sets of actions that will almost surly include the optimal one. / Les processus markoviens ont été depuis longtemps utilisés pour modéliser les environnements stochastiques. L'apprentissage par renforcement a émergé comme un framework convenable pour résoudre les problèmes de planification séquentiels et de prise de décision dans de tels environnements.Récemment, des méthodes basées sur l'apprentissage par renforcement ont été appliquées pour développer des stratégies de traitement adaptables où l'objectif est d'apprendre une séquence de traitements individuelle à partir de données cliniques. Malgré que ces méthodes se sont avérées utiles pour des problèmes de prise de décision séquentielle, elles nepeuvent pas être appliquées avec leur forme actuelle dans le domaine médical puisqu'elles ne fournissent pas les garanties généralement requises dans ce genre de domaine. D'un autre côté, les politiques retournées par la plupart des méthodes d'apprentissage par renforcement sont souvent très rigides et ne laissent pas d'interval de manoeuvre suffisant pour les médecins.Cette thèse présente un nouveau concept de politiques non-déterministes pour représenter le processus de prise de décision de l'utilisateur. Nous développons deux algorithmes qui proposent des options flexibles à l'utilisateur tout en s'assurant que la performance soit toujours proche de l'optimal. Nous montrons ensuite comment fournir des mesures de confiance sur la fonction de valeur des processus markoviens et finalement nous utilisons ces mesures pour identifier un ensemble d'actions qui vont presque sûrement inclure l'action optimale.

Internet is a tremendous success and is an indispensable part of our everyday activities. However, Internet does not provide sufficient integrity to ensure the end hosts accountable for the communication. In this thesis, we present a new social accountable framework for the Internet that leverages the trusted links found on online social networks to hold the people and organizations accountable for their actions. Our framework is incrementally deployable without modifying the operating systems or applications running on the hosts. We provide the full design and discuss how different types of applications can be mapped onto the proposed framework. A prototype of this social accountable framework is partially implemented to evaluate the performance of the framework. / L'Internet est un succès extraordinaire et est une pièce indispensable de notre vie quotidienne. Cependent, l'Internet ne fourni pas assez d'integrité pour assurer que les hébergeurs finaux soient responsables pour les communications. Dans cette thèse, nous présentons un nouveau cadre social responsable pour l'Internet qui exploite les liens de confiance trouvés sur les réseaux sociaux pour tenir les utilisateurs et les organisations responsables pour leurs actions. Notre cadre se déploit de facon itérative sans la modification du système d'exploitation ou les applications qui y exécutent. Nous présentons le plan complet et élaborons comment différent types d'applications peuvent s'adapter au cadre proposé. Un prototype de ce cadre social responsable est partiellement mis en application pour évaluer sa performance.

We prove that the decision problem for finite mathematical state- ments, though recursive, is infeasible in seemingly any realistic model of computation. In particular, we construct of a set of finite mathematical statements which can only be feasibly solved by programs long enough to explicitly encode a decision for each statement. This result was published in Hungarian, in 1973, by Michael Makkai and appears here for the first time in English. In this paper we: 1) elucidate Makkai's proof as an adaptation of Gödel's first incompleteness proof, 2) strengthen his 1973 result and 3) reflect on this result from the perspectives of computational complexity and algorithmic information theory (Kolmogorov complexity). / Nous avons démontré que le problème quand à prendre des décisions concernant des énoncés mathématiques finis, bien que récursif, est infaisable accordé à n'importe quel modèle de calcul. Plus précisément, nous avons établi un ensemble de problèmes mathématiques ne pouvant être résolus que par des programmes assez long qui suggéreraient la décision finale implicitement, au fil des calculs. Ce fait a d'abord été publié en 1973 par un Hongrois du nom de Michael Makkai, et il sera expliqué en anglais pour la toute première fois ici. Dans ce travail, nous 1) éluciderons la démonstration faite par Makkai basé sur l'adaptation de la première démonstration du théorème incomplétude de Gödel, 2) appuierons les résultats trouvés en 1973 par Makkai et 3) tirerons des conclusions sur ses résultats en utilisant la théorie de la complexité et la théorie algorithmique de l'information, aussi appelée complexité de Kolmogorov.

A model is an abstraction of the real system. To design complex systems, modelling is preferred to the traditional methods for its capability to analyse and simulate before implementation, and its tools for code generation which allows for defect-free code. The domain specific modelling and metamodels (the abstraction of models) provide the modellers domain specific syntax and environments. The meta-metamodel (the abstraction of metamodels) defines a unified description of various domain metamodels. Metamodelling architectures provide the guideline of organizing models and metamodels. So far, many metamodelling standards and tools have been developed.However, two drawbacks have prevented us from having a well-defined metamodelling tool. The first is that current linear architectures fail to appropriately separate the views of different roles in metamodelling. The second is the missing executability at the root of metamodelling since most existing meta-metamodels are designed to describe the structural information rather than the behavioural.In this project, we used a two-dimensional metamodelling architecture with logical and physical classifications that separates the view of modellers and that of tool developers. We designed a general-purpose, self-describable, executable meta-metamodel ArkM3 which includes an action language and thereby enables executability. With this architecture and this meta-metamodel, we enabled a general-purpose, comprehensive, bootstrapped metamodelling tool. To demonstrate our design, we built Ark, the kernel of AToMPM (A Tool for Multi-Paradigm Metamodelling), an updated version of AToM3 (A Tool for Multi-Formalism and MetaModelling). We also presented a case study that models a Readers/Writers System Petri Net model. / Un modèle est une abstraction dun système réel. Pour la conception de systèmes complexes, la modélisation est préférée aux méthodes traditionnelles, parce que la modélisation permet danalyser et de simuler avant la mise en oeuvre. De plus, les outils de génération de code fournis par la modlisation aident à produire des codes sans défaut. La modélisation dans des domaines spécifiques et des méta-modèles (l'abstraction des modèles) fournissent des syntaxes et des environnements spécifiques aux modélisateurs. Le méta-métamodèle (l'abstraction de métamodèles) normalise la description des métamodèles. Les architectures de métamodélisation fournissent les directives à suivre afin dorganiser les modèles et les métamodèles. Jusqu'à ce jour, de nombreuses normes et doutils en métamodélisation ont été développés.Cependant, deux inconvénients demeurent et préviennent la création dun outil de métamodélisation bien défini. Le premier est que les architectures actuelles sont linéaires. Ceci qui ne les permettent pas de différencier adéquatement l'aspect des différents rôles dans la métamodélisation. Le second est quelles nont pas de caractère exécéable à partir de la racine de la métamodélisation, puisque la plupart des méta-méamodèles sont conçus pour décrire des informations structurelles plutôt que comportementaux.Dans ce projet, nous avons utilisé une architecture à deux dimensions avec la classification logique et physique, séparant ainsi le point de vue des modélisateurs et celui des développeurs d'outils. Nous avons conçu ArkM3, un méta-métamodèle universel, auto-descriptible et exécutable. Il inclut également un langage d'action, ce qui le rend exécutable. En combinant cette architecture et ce méta-métamodèle rend possible de mettre sur pied un outil universel damorçage de métamodélisation. Pour démontrer notre conception, nous avons construit le noyau de AToMPM (A Tool for Multi-Paradigm Metamodelling), une version mise à jour de AToM3 (A Tool for Multi-Formalism and MetaModelling). Nous présentons également une étude de cas selon un système de Petri Net "Readers/Writers".

Ice hockey is a sport characterized by high speeds, sharp turns and abrupt stops. As a result of these explosive and agile movements, the interaction of the foot and ankle with the skate boot is fundamental for optimal stability and propulsion. The purpose of this study was to determine the nature of this mechanical coupling in both a conventional and prototype skate models. In phase one, a Biodex System 4 Pro dynamometer was used to isolate the foot and ankle / boot dynamics in sagittal and frontal plane movements. Three footwear conditions were evaluated (control shoe, a skate boot in production and a modified skate boot prototype). In phase two, lower body kinematics were assessed using 3D motion capture to determine if the above skate models would yield different joint movement coordination during skating push-offs using the two skate boot models. When comparing the three foot conditions, there was a significantly greater range of motion observed in the shoe control and modified skate boot than the regular skate boot (65.2 deg vs. 52.4 deg vs. 35.7 deg, p < 0.05). The total work done was only significant in the shoe control over the regular skate boot (16 kJ vs. 8.9 kJ, p < 0.05). In phase two, only the maximum plantar flexion was greater with the modified skate (11.3 deg vs. 1.3 deg, p < 0.05). The biodex dynamometer was able to discern differences between the three types of footwear using the dependent variables selected. Using a combination of the active and passive modes, this system has provided a valuable measurement of quantifying boot stiffness characteristics. / Une vitesse de jeu rapide, les virages brusques ainsi que les arrêts soudains sont des caractéristiques bien particulières au hockey sur glace. Considérant ces mouvements explosifs et agiles, l'interaction entre le pied, la cheville ainsi que la botte du patin devient fondamentale pour obtenir une propulsion et une stabilité optimale. Le but de cette études était de déterminer la nature cette interaction mécanique pour un modèle de patin a glace conventionnel ainsi que pour un prototype. Dans un premier temps, un dynamomètre Biodex System 4 a été utilisé pour isoler de façon dynamique le pied et la cheville/patin dans les plans sagittal et frontal. Trois conditions expérimentales ont été évaluées (soulier contrôle, patin commercialisé ainsi qu'un patin modifié). Par la suite, la cinématique des membres inférieurs fut mesurée en utilisant une système de capture du mouvement pour déterminer si les différentes botte de patin affecteraient la coordination motrice lors d'un départ.En comparant les trois conditions de botte, une différence significative a été observée pour l'amplitude de mouvement entre le soulier et le patin modifié et le patin commercial (65.2° vs. 52.4° vs. 35.7°, p < 0.05). Le travail total était seulement significatif entre le soulier et le patin commercial (16 kJ vs 8.9 kJ, p < 0.05). Pour la deuxième phase, seulement la flexion plantaire maximale était plus grande avec le patin modifié 11.3° vs. 1.3°, p < 0.05).Le dynamomètre Biodex a pu clairement discerner des différences entre les différentes conditions de botte pour les variables dépendantes sélectionnées. En utilisant les modes passifs et actifs, le système a permis de générer une méthode de quantification caractéristique de la rigidité de bottes.

Because of its decentralized nature and the lack of the required cooperations among the Internet autonomous systems, the current Internet is unable to provide end-to-end QoS guarantees to the application layer. The Service Overlay Network (SON) is a proposed solution to this end-to-end QoS provisioning problem. With its special overlay structure,the Service Overlay Network is able to provide reliable end-to-end QoS support on top of the Internet infrastructure. By considering the SON as a network with virtual connections and bandwidth allocations, we derive a series of new results for the SON. First, by referring to the reliability theory, we obtain a general form for the end-to-end blocking function. With the general blocking function, we investigate the two optimization approaches for designing a SON, namely the Maximum Profit (MP) approach that maximizes the prot and the Minimum Cost (MC) approach that minimizes the investment. Our study reveals that though the two approaches have been shown to be equivalent in many other settings, they are different in the SON environment. Our result indicates that the MP approach is a more appropriate approach for designing a SON, and the result is independent of the routing algorithm employed. Second, we develop a novel event dependent routing scheme that is efficient enough to be incorporated into the optimal capacity allocation problem. This allows the SON design problem to be formulated and solved as a MP optimization problem. Then we improve the optimization methodology by decomposing the main SON design problem into a number of sub-problems and we solve the main design problem by solving the sub-problems which involve finding the link shadow prices of the network links. It is exactly because we are using the maximum profit approach, the idea of link shadow price could be incorporatedto solve the design problem. A fast macro-state convolution scheme based on the link shadow price is developed to provide a traffic differentiation module to the optimization formulation. This additional module allows the optimization framework consider traffic connections based on the (monetary) contributions they offer to the network. Like many other telecommunications services, SON is believed to exhibit positive net-work externalities - once the network reaches a "critical mass", it will continue to grow in a self-reinforcing manner. The optimal pricing of the SON services is therefore another crucial piece of information for the SON to achieve success. We study a set of Lagrange i imultipliers and show that the SON service charges are closely related to the set of multipliers. When the service levels are not hard requirements, by using the multipliers as the service charges, the resulting network will be on the Pareto frontier of a multi-criteria optimization problem that maximizes both the operator utility and the user utility. This piece of work provides information from the problem formulation, to the actual design process, to the simplication and enhancement of the design process, and finally to the set of optimal prices which the operator could charge. It essentially provides comprehensive information for deploying the SON network. / En raison de son caractere decentralise et le manque de cooperations necessaires entre les l'Internet des systemes autonomes, l'Internet actuel est incapable de fournir de bout en bout QoS garantit a la couche application. L'Overlay Service Network (SON) est une solution proposee a ce QoS de bout-en-bout probleme. Grace a sa structure speciale de recouvrement, l'Overlay Service Network est en mesure de fournir des informations ables de bout en bout la qualite de service support au-dessus de l'infrastructure Internet. En considerant la SON en reseau avec des connexions virtuelles et la bande passante allocations, nous obtenons une serie de nouveaux resultats pour le SON. Tout d'abord, en se referant a la theorie de la abilite, nous obtenons une forme generale pour la fin-en-bout fonction de blocage. Avec l'general fonction de blocage, nous examinons les deux approches d'optimisation pour la conception une SON, soit le maximum Profit (MP) approche qui maximise le profit et le Cout minimum (MC) approche qui minimise l'investissement. Notre etude revele que si les deux approches se sont revelees etre l'equivalent dans de nombreux autres parametres, ils sont differents dans l'environnement SON. Nos resultats montrent que l'approche MP est une approche plus appropriee pour la conception d'un SON, et le resultat est independant de l'algorithme de routage utilise. Deuxiemement, nous developpons un nouvel evenement depend regime de routage qui est assez efficace pour etre incorpores dans le probleme d'allocation de la capacite optimale. Cela permet au probleme de conception Fils pour etre formule et resolu comme un probleme d'optimisation MP. Ensuite, nous avons d'ameliorer la methodologie d'optimisation en decomposant le probleme de conception principale fils dans un certain nombre de sous problemes et nous resolvons le probleme de conception principale en resolvant les problemes sous-qui impliquent la constatation du prix fictifs lien des liens du reseau. C'est justement parce que nous utilisons la recherche du profit maximum, l'idee de prix fictif lien pourrait etre constituee pour resoudre le probleme de conception. Un schema de convolution rapide macro-etat base sur le prix fictif lien est developpe pour fournir une differenciation du trafic module d'optimisation de la formulation. Ce module additionnel permet l'optimisation examiner le cadre des connexions de trafic sur la base des contributions (monetaires), ils offrent au reseau. Comme beaucoup d'autres services de telecommunications, SON est estime a exposer nette positive externalites de travail - une fois que le reseau atteint une "masse critique", il va continuer a croitre dans un auto-renforcement maniere. La tarification optimale des services de SON est donc un autre element crucial de l'information pour le SON pour reussir. Nous etudions une serie de multiplicateurs Lagrange et montrent que les frais de service SON sont etroitement liees a l'ensemble des multiplicateurs. Lorsque les niveaux de service ne sont pas des exigences dur, en utilisant les multiplicateurs que les frais de service, le reseau qui en resulte sera sur la frontiere de Pareto d'un probleme d'optimisation multi-criteres qui maximise la fois l'utilite operateur et l'utilite de l'utilisateur. Ce travail fournit des informations a partir de la formulation du probleme, a l'actuel la conception de processus, de la simplification et l'amelioration du processus de conception, et enfin a l'ensemble des prix optimal o l'operateur peut charger. Il fournit essentiellement des informations completes pour le deploiement du reseau SON. Ce travail fournit des informations a partir de la formulation du probleme, a l'actuel la conception de processus, de la simplification et l'amelioration du processus de conception, et enfn a l'ensemble des prix optimal o l'operateur peut charger. Il fournit essentiellement des informations completes pour le deploiement du reseau SON.

The backend database system is often the performance bottleneck in multi-tier architectures. This is particularly true if there is a cluster of application servers while there is only a single database backend. A common approach to scale the database component is query result caching. The idea is to cache the results of a query submitted to the database in a cache. If the query is consequently requested again, the result can be retrieved from the cache instead of the query again being submitted to the database. Query caching can play a vital role in reducing latency by avoiding access to the database, and improving throughput by avoiding a database bottleneck. Existing approaches, however, have two limitations. First, they do not exploit the full capacity of the caches. Each application server has its own cache and frequently used objects will likely be cached in all caches, limiting the number of different objects and queries that can be cached. Furthermore, a query can only be served from the cache if previously the exact same query was posed. In this thesis, we introduce Contquer, a distributed cooperative caching algorithm that uses a distributed caching architecture where each object is only cached at one application server and each application server has access to local and remote caches. Thus, the full capacity of all caches can be exploited. Furthermore, we optimize the query cache by exploiting the cache even if only part of a query can be served from the cache. For that we analyze the containment of queries within other queries. Contquer determines when a query can be fully or partially served from the cache, and automatically generates remainder queries to the database if necessary. This thesis reports on the design and implementation of Contquer. It also conducts experiments that show that performance is improved considerably with the proposed algorithm. We conclude that the use of a distributed caching infrastructure and the ability to retrieve partial results from the cache improves performance in terms of hit-rate, throughput and latency. / Le système de base de données est souvent un point critique en terme de performance dans les architectures multi-tiers. Ceci est particulièrement vrai dans le cas d'un groupe de serveurs d'application alors qu'il y a seulement une seule base de données. Une approche commune pour améliorer la performance de base de données est la mise en cache de résultat de requêtes. L'idée est de mettre en cache les résultats d'une requête soumise à la base de données. Si cette requête est demandée à nouveau, le résultat peut être récupéré à partir du cache au lieu de soumettre la requête à nouveau à la base de données. La mise en cache de requêtes peut jouer un rôle vital dans la réduction de latence en évitant l'accès à la base de données, et d'améliorer le débit en évitant la congestion de la base de données. Les approches existantes ont cependant deux limitations. D'abord, ils n'exploitent pas la pleine capacité des caches. Chaque serveur d'application a son propre cache et des objets fréquemment utilisés seront probablement mis en cache dans tous les caches, ce qui limite le nombre d'objets et de requêtes qui peuvent être mis en cache. En outre, une requête ne peut être servie à partir du cache que si elle a déjà été servie de la base données. Dans cette thèse, nous introduisons Contquer, un algorithme de mise en cache distribué et coopérative qui utilise une architecture de mise en cache distribuée où chaque objet est uniquement mis en cache à un seul serveur d'application et que chaque serveur d'application a accès à des caches locaux et distants. Ainsi, la capacité totale de tous les caches peut être exploitée. En outre, nous optimisons le cache de requête en exploitant la mémoire cache, même si une partie seulement d'une requête peut être servie à partir du cache. Pour cela, nous analysons le confinement de requêtes dans les autres requêtes. Contquer détermine le moment où une requête peut être totalement ou partiellement servie à partir du cache, et s'il le faut génère automatiquement le reste des requêtes à la base de données. Cette thèse porte sur la conception et la mise en œuvre de Contquer. Il mène également des expériences qui montrent que la performance est considérablement améliorée avec l'algorithme proposé. Nous concluons que l'utilisation d'une infrastructure de mise en cache distribuée et la possibilité de récupérer les résultats partiels de la mémoire cache améliore la performance en termes de taux de réussite, de débit et de latence.

This dissertation addresses the problem of sequential decision making under uncertainty in large systems. The formalisms used to study this problem are fully and partially observable Markov Decision Processes (MDPs and POMDPs, respectively). The first contribution of this dissertation is a theoretical analysis of the behavior of POMDPs when only subsets of the observation set are used. One of these subsets is used to update the agent's state estimate, while the other subset contains observations the agent is interested in predicting and/or optimizing. The behaviors are formalized as three types of equivalence relations. The first groups states based on their values under optimal or general policies; the second groups states according to their ability to predict observations sequences; the third type isbased on bisimulation, which is a well known equivalence relation borrowed from concurrency theory.Bisimulation relations can be generalized to bisimulation metrics. This dissertation introduces bisimulation metrics for an MDP with temporally extended actions (formalized as options) and proposes a new bisimulation metric that provides atighter bound on the difference in optimal values. A new proof is provided for the convergence of an approximation method for computing bisimulation metrics that is based on statistical sampling, using only a finite number of samples. The newproof allows one to determine the minimum number of samples needed in order to achieve the desired quality of approximation with high probability.Although bisimulation metrics have been previously used for state space compression, this dissertation proposes using them to transfer policies from one MDP to another. In contrast to existing transfer work, the mapping between the twosystems is determined automatically by means of the bisimulation metrics. Theoretical results are provided that bound the loss in optimality incurred by the transferred policy. A number of algorithms are introduced which are evaluatedempirically in the context of planning and learning. / Cette thèse traite le problème de prises de décisions séquentielles en grand domaines. Les formalismes utilisés pour étudier ce problème sont processus de décision Markoviens entièrement ou partiellement observables (MDP et POMDPs, respectivement).La première contribution de cette thèse est une analyse théorique du comportement des POMDPs lorsque seulement sous-ensembles de l'ensemble d'observations sont utilisés. L'un de ces sous-ensembles est utilisé pour mettre à jour la confiance de l'agent sur son état actuel, tandis que l'autre est utilisé pour mesurer la performance de l'agent. Les comportements sont formalisés avec trois types de relations d'equivalence. La première relation place les états dans le même groupe en fonction de leurs valeurs en vertu des politiques optimales ou générales; la second relation place les etats dans le même groupe en fonction de leur capacité a predire sequences d'observations; la troisième relation est basé sur la bisimulation, qui est une relation d'equivalence bien connu emprunté à la théorie de la concurrence.Les relations de bisimulation peuvent être généralisés à métriques de bisimulation. Cette thèse présente métriques de bisimulation pour une MDP avec des actions prolongées (formalisées comme des options) et propose une nouvelle métrique de bisimulation qui fournit un resserrement des limites sur la différence de valeurs optimales. Une nouvelle preuve est fournie pour la convergence d'une méthode d'approximation pour le calcul le du métrique de bisimulation qui est basé sur un échantillonnage statistique. La nouvelle preuve permet de déterminer le nombre minimal d'échantillons nécessaires pour atteindre la qualité souhaitée de rapprochement avec une forte probabilité.Bien que mêtriques de bisimulation ont été précédemment utilisés pour la compression de l'espace d'état, cette thèse propose de les utiliser pour transférer des politiques d'un MDP à l'autre. Contrairement aux travaux de transfert existants,le mappage entre les deux systèmes est déterminé automatiquement par les métriques de bisimulation. Résultats théoriques sont présentés que limite la perte de l'optimalité encourus par la police transferée. Un certain nombre d'algorithmes sont introduites, qui sont évalués de façon empirique dans le contexte de la planification et de l'apprentissage.

Automatically planning the motion of rigid bodies moving in 3D by translation and rotation in the presence of obstacles has long been a research challenge for mathematicians, algorithm designers and roboticists. The field made dramatic progress with the introduction of the probabilistic and sampling-based "roadmap" approach. However, motion planning when narrow passages are present has remained a challenge. This thesis presents a framework for experimenting with combinations of sampling strategies and local planners, and for comparing their performance on user defined input problems. Our framework also allows parallel implementations on a variable number of processing cores. We present experimental results. In particular, our framework has allowed us to find combinations of sampling strategy choice with local planner choice that can solve difficult benchmark motion planningproblems. / La planification automatique du mouvement de corps rigides en mouvement 3D par translation et rotation en présence d'obstacles a longtemps été un défi pour la recherche pour les mathématiciens, les concepteurs de l'algorithme et roboticiens. Le champ a fait d'importants progrès avec l'introduction de la méthode de "feuille de route" probabiliste basée sur l'échantillonnage. Mais la planification du mouvement en présence de passages étroits est resté un défi.Cette thése présente un cadre d'expérimentation avec des combinaisons de stratégies d'échantillonnage et les planificateurs locaux, et de comparaison de leurs performances sur des problémes définis par l'utilisateur. Notre programme peut également être exécuté parallèle sur un nombre variable de processeurs. Nous présentons des résultats expérimentaux. En particulier, notre cadre nous a permis de trouver des combinaisons de choix d'une stratégie d'échantillonnage avec choix de planificateur local qui peut résoudre des problèmes difficiles de référence.

In machine learning one is usually given a data set of real high dimensional vectors X, based on which it is desired to select a hypothesis θ from the space of hypotheses Θ using a learning algorithm. An immediate assumption that is usually imposed on X is that it is a subset from the very general embedding space Rp which makes the Euclidean distance ∥•∥2 to become the default metric for the elements of X. Since various learning algorithms assume that the input space is Rp with its endowed metric ∥•∥2 as a (dis)similarity measure, it follows that selecting hypothesis θ becomes intrinsically tied to the Euclidean distance. Metric learning is the problem of selecting a specific metric dX from a certain family of metrics D based on the properties of the elements in the set X. Under some performance measure, the metric dX is expected to perform better on X than any other metric d 2 D. If the learning algorithm replaces the very general metric ∥•∥2 with the metric dX , then selecting hypothesis θ will be tied to the more specific metric dX which carries all the information on the properties of the elements in X. In this thesis I propose two algorithms for learning the metric dX ; the first for supervised learning settings, and the second for unsupervised, as well as for supervised and semi-supervised settings. In particular, I propose algorithms that take into consideration the structure and geometry of X on one hand, and the characteristics of real world data sets on the other. However, if we are also seeking dimensionality reduction, then under some mild assumptions on the topology of X, and based on the available a priori information, one can learn an embedding for X into a low dimensional Euclidean space Rp0, p0 &lt;&lt; p, where the Euclidean distance better reveals the similarities between the elements of X and their groupings (clusters). That is, as a by-product, we obtain dimensionality reduction together with metric learning. In the supervised setting, I propose PARDA, or Pareto discriminant analysis for discriminative linear dimensionality reduction. PARDA is based on the machinery of multi-objective optimization; simultaneously optimizing multiple, possibly conflicting, objective functions. This allows PARDA to adapt to the class topology in the lower dimensional space, and naturally handles the class masking problem that is inherent in Fisher's discriminant analysis framework for multiclass problems. As a result, PARDA yields significantly better classification results when compared with modern techniques for discriminative dimensionality reduction. In the unsupervised setting, I propose an algorithmic framework, denoted by ?? (note the different notation), that encapsulates spectral manifold learning algorithms and gears them for metric learning. The framework ?? captures the local structure and the local density information from each point in a data set, and hence it carries all the information on the varying sample density in the input space. The structure of ?? induces two distance metrics for its elements, the Bhattacharyya-Riemann metric dBR and the Jeffreys-Riemann metric dJR. Both metrics reorganize the proximity between the points in X based on the local structure and density around each point. As a result, when combining the metric space (??, dBR) or (??, dJR) with spectral clustering and Euclidean embedding, they yield significant improvements in clustering accuracies and error rates for a large variety of clustering and classification tasks. / Dans cette thèse, je propose deux algorithmes pour l'apprentissage de la métrique dX; le premier pour l'apprentissage supervisé, et le deuxième pour l'apprentissage non-supervisé, ainsi que pour l'apprentissage supervisé et semi-supervisé. En particulier, je propose des algorithmes qui prennent en considération la structure et la géométrie de X d'une part, et les caractéristiques des ensembles de données du monde réel d'autre part. Cependant, si on cherche également la réduction de dimension, donc sous certaines hypothèses légères sur la topologie de X, et en même temps basé sur des informations disponibles a priori, on peut apprendre une intégration de X dans un espace Euclidien de petite dimension Rp0 p0 &lt;&lt; p, où la distance Euclidienne révèle mieux les ressemblances entre les éléments de X et leurs groupements (clusters). Alors, comme un sous-produit, on obtient simultanément une réduction de dimension et un apprentissage métrique. Pour l'apprentissage supervisé, je propose PARDA, ou Pareto discriminant analysis, pour la discriminante réduction linéaire de dimension. PARDA est basé sur le mécanisme d'optimisation à multi-objectifs; optimisant simultanément plusieurs fonctions objectives, éventuellement des fonctions contradictoires. Cela permet à PARDA de s'adapter à la topologie de classe dans un espace dimensionnel plus petit, et naturellement gère le problème de masquage de classe associé au discriminant Fisher dans le cadre d'analyse de problèmes à multi-classes. En conséquence, PARDA permet des meilleurs résultats de classification par rapport aux techniques modernes de réduction discriminante de dimension. Pour l'apprentissage non-supervisés, je propose un cadre algorithmique, noté par ??, qui encapsule les algorithmes spectraux d'apprentissage formant an algorithme d'apprentissage de métrique. Le cadre ?? capture la structure locale et la densité locale d'information de chaque point dans un ensemble de données, et donc il porte toutes les informations sur la densité d'échantillon différente dans l'espace d'entrée. La structure de ?? induit deux métriques de distance pour ses éléments: la métrique Bhattacharyya-Riemann dBR et la métrique Jeffreys-Riemann dJR. Les deux mesures réorganisent la proximité entre les points de X basé sur la structure locale et la densité autour de chaque point. En conséquence, lorsqu'on combine l'espace métrique (??, dBR) ou (??, dJR) avec les algorithmes de "spectral clustering" et "Euclidean embedding", ils donnent des améliorations significatives dans les précisions de regroupement et les taux d'erreur pour une grande variété de tâches de clustering et de classification.