Complexité de la communication sur un canal avec délai

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque.

Recyclage des candidats dans l'algorithme Metropolis à essais multiples

Les méthodes de Monte Carlo par chaînes de Markov (MCCM) sont des méthodes servant à échantillonner à partir de distributions de probabilité. Ces techniques se basent sur le parcours de chaînes de Markov ayant pour lois stationnaires les distributions à échantillonner. Étant donné leur facilité d’application, elles constituent une des approches les plus utilisées dans la communauté statistique, et tout particulièrement en analyse bayésienne. Ce sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Depuis l’apparition de la première méthode MCCM en 1953 (la méthode de Metropolis, voir [10]), l’intérêt pour ces méthodes, ainsi que l’éventail d’algorithmes disponibles ne cessent de s’accroître d’une année à l’autre. Bien que l’algorithme Metropolis-Hastings (voir [8]) puisse être considéré comme l’un des algorithmes de Monte Carlo par chaînes de Markov les plus généraux, il est aussi l’un des plus simples à comprendre et à expliquer, ce qui en fait un algorithme idéal pour débuter. Il a été sujet de développement par plusieurs chercheurs. L’algorithme Metropolis à essais multiples (MTM), introduit dans la littérature statistique par [9], est considéré comme un développement intéressant dans ce domaine, mais malheureusement son implémentation est très coûteuse (en termes de temps). Récemment, un nouvel algorithme a été développé par [1]. Il s’agit de l’algorithme Metropolis à essais multiples revisité (MTM revisité), qui définit la méthode MTM standard mentionnée précédemment dans le cadre de l’algorithme Metropolis-Hastings sur un espace étendu. L’objectif de ce travail est, en premier lieu, de présenter les méthodes MCCM, et par la suite d’étudier et d’analyser les algorithmes Metropolis-Hastings ainsi que le MTM standard afin de permettre aux lecteurs une meilleure compréhension de l’implémentation de ces méthodes. Un deuxième objectif est d’étudier les perspectives ainsi que les inconvénients de l’algorithme MTM revisité afin de voir s’il répond aux attentes de la communauté statistique. Enfin, nous tentons de combattre le problème de sédentarité de l’algorithme MTM revisité, ce qui donne lieu à un tout nouvel algorithme. Ce nouvel algorithme performe bien lorsque le nombre de candidats générés à chaque itérations est petit, mais sa performance se dégrade à mesure que ce nombre de candidats croît.

Improving sampling, optimization and feature extraction in Boltzmann machines

L’apprentissage supervisé de réseaux hiérarchiques à grande échelle connaît présentement un succès fulgurant. Malgré cette effervescence, l’apprentissage non-supervisé représente toujours, selon plusieurs chercheurs, un élément clé de l’Intelligence Artificielle, où les agents doivent apprendre à partir d’un nombre potentiellement limité de données. Cette thèse s’inscrit dans cette pensée et aborde divers sujets de recherche liés au problème d’estimation de densité par l’entremise des machines de Boltzmann (BM), modèles graphiques probabilistes au coeur de l’apprentissage profond. Nos contributions touchent les domaines de l’échantillonnage, l’estimation de fonctions de partition, l’optimisation ainsi que l’apprentissage de représentations invariantes. Cette thèse débute par l’exposition d’un nouvel algorithme d'échantillonnage adaptatif, qui ajuste (de fa ̧con automatique) la température des chaînes de Markov sous simulation, afin de maintenir une vitesse de convergence élevée tout au long de l’apprentissage. Lorsqu’utilisé dans le contexte de l’apprentissage par maximum de vraisemblance stochastique (SML), notre algorithme engendre une robustesse accrue face à la sélection du taux d’apprentissage, ainsi qu’une meilleure vitesse de convergence. Nos résultats sont présent ́es dans le domaine des BMs, mais la méthode est générale et applicable à l’apprentissage de tout modèle probabiliste exploitant l’échantillonnage par chaînes de Markov. Tandis que le gradient du maximum de vraisemblance peut-être approximé par échantillonnage, l’évaluation de la log-vraisemblance nécessite un estimé de la fonction de partition. Contrairement aux approches traditionnelles qui considèrent un modèle donné comme une boîte noire, nous proposons plutôt d’exploiter la dynamique de l’apprentissage en estimant les changements successifs de log-partition encourus à chaque mise à jour des paramètres. Le problème d’estimation est reformulé comme un problème d’inférence similaire au filtre de Kalman, mais sur un graphe bi-dimensionnel, où les dimensions correspondent aux axes du temps et au paramètre de température. Sur le thème de l’optimisation, nous présentons également un algorithme permettant d’appliquer, de manière efficace, le gradient naturel à des machines de Boltzmann comportant des milliers d’unités. Jusqu’à présent, son adoption était limitée par son haut coût computationel ainsi que sa demande en mémoire. Notre algorithme, Metric-Free Natural Gradient (MFNG), permet d’éviter le calcul explicite de la matrice d’information de Fisher (et son inverse) en exploitant un solveur linéaire combiné à un produit matrice-vecteur efficace. L’algorithme est prometteur: en terme du nombre d’évaluations de fonctions, MFNG converge plus rapidement que SML. Son implémentation demeure malheureusement inefficace en temps de calcul. Ces travaux explorent également les mécanismes sous-jacents à l’apprentissage de représentations invariantes. À cette fin, nous utilisons la famille de machines de Boltzmann restreintes “spike & slab” (ssRBM), que nous modifions afin de pouvoir modéliser des distributions binaires et parcimonieuses. Les variables latentes binaires de la ssRBM peuvent être rendues invariantes à un sous-espace vectoriel, en associant à chacune d’elles, un vecteur de variables latentes continues (dénommées “slabs”). Ceci se traduit par une invariance accrue au niveau de la représentation et un meilleur taux de classification lorsque peu de données étiquetées sont disponibles. Nous terminons cette thèse sur un sujet ambitieux: l’apprentissage de représentations pouvant séparer les facteurs de variations présents dans le signal d’entrée. Nous proposons une solution à base de ssRBM bilinéaire (avec deux groupes de facteurs latents) et formulons le problème comme l’un de “pooling” dans des sous-espaces vectoriels complémentaires.

Video-based postural sway analysis in a controlled environment

À mesure que la population des personnes agées dans les pays industrialisés augmente au fil de années, les ressources nécessaires au maintien du niveau de vie de ces personnes augmentent aussi. Des statistiques montrent que les chutes sont l’une des principales causes d’hospitalisation chez les personnes agées, et, de plus, il a été démontré que le risque de chute d’une personne agée a une correlation avec sa capacité de maintien de l’équilibre en étant debout. Il est donc d’intérêt de développer un système automatisé pour analyser l’équilibre chez une personne, comme moyen d’évaluation objective. Dans cette étude, nous avons proposé l’implémentation d’un tel système. En se basant sur une installation simple contenant une seule caméra sur un trépied, on a développé un algorithme utilisant une implémentation de la méthode de détection d’objet de Viola-Jones, ainsi qu’un appariement de gabarit, pour suivre autant le mouvement latéral que celui antérieur-postérieur d’un sujet. On a obtenu des bons résultats avec les deux types de suivi, cependant l’algorithme est sensible aux conditions d’éclairage, ainsi qu’à toute source de bruit présent dans les images. Il y aurait de l’intérêt, comme développement futur, d’intégrer les deux types de suivi, pour ainsi obtenir un seul ensemble de données facile à interpréter.

Étude de dispositifs électroniques moléculaires à l'aide de modèles simples

Cette thèse en électronique moléculaire porte essentiellement sur le développement d’une méthode pour le calcul de la transmission de dispositifs électroniques moléculaires (DEMs), c’est-à-dire des molécules branchées à des contacts qui forment un dispositif électronique de taille moléculaire. D’une part, la méthode développée vise à apporter un point de vue différent de celui provenant des méthodes déjà existantes pour ce type de calculs. D’autre part, elle permet d’intégrer de manière rigoureuse des outils théoriques déjà développés dans le but d’augmenter la qualité des calculs. Les exemples simples présentés dans ce travail permettent de mettre en lumière certains phénomènes, tel que l’interférence destructive dans les dispositifs électroniques moléculaires. Les chapitres proviennent d’articles publiés dans la littérature. Au chapitre 2, nous étudions à l’aide d’un modèle fini avec la méthode de la théorie de la fonctionnelle de la densité de Kohn-Sham un point quantique moléculaire. De plus, nous calculons la conductance du point quantique moléculaire avec une implémentation de la formule de Landauer. Nous trouvons que la structure électronique et la conductance moléculaire dépendent fortement de la fonctionnelle d’échange et de corrélation employée. Au chapitre 3, nous discutons de l’effet de l’ajout d’une chaîne ramifiée à des molécules conductrices sur la probabilité de transmission de dispositifs électroniques moléculaires. Nous trouvons que des interférences destructives apparaissent aux valeurs propres de l’énergie des chaînes ramifiées isolées, si ces valeurs ne correspondent pas à des états localisés éloignés du conducteur moléculaire. Au chapitre 4, nous montrons que les dispositifs électroniques moléculaires contenant une molécule aromatique présentent généralement des courants circulaires qui sont associés aux phénomènes d’interférence destructive dans ces systèmes. Au chapitre 5, nous employons l’approche « source-sink potential » (SSP) pour étudier la transmission de dispositifs électroniques moléculaires. Au lieu de considérer les potentiels de sources et de drains exactement, nous utilisons la théorie des perturbations pour trouver une expression de la probabilité de transmission, T(E) = 1 − |r(E)|2, où r(E) est le coefficient de réflexion qui dépend de l’énergie. Cette expression dépend des propriétés de la molécule isolée, en effet nous montrons que c’est la densité orbitalaire sur les atomes de la molécule qui sont connectés aux contacts qui détermine principalement la transmission du dispositif à une énergie de l’électron incident donnée. Au chapitre 6, nous présentons une extension de l’approche SSP à un canal pour des dispositifs électroniques moléculaires à plusieurs canaux. La méthode à multiples canaux proposée repose sur une description des canaux propres des états conducteurs du dispositif électronique moléculaire (DEM) qui sont obtenus par un algorithme auto-cohérent. Finalement, nous utilisons le modèle développé afin d’étudier la transmission du 1-phényl-1,3-butadiène branché à deux rangées d’atomes couplées agissant comme contacts à gauche et à la droite.

Oxygenation-sensitive cardiovascular magnetic resonance imaging (OS-CMR) : potential confounding factors in use of OS-CMR

La résonance magnétique cardiovasculaire sensible à l'oxygénation (OS-CMR) est devenue une modalité d'imagerie diagnostique pour la surveillance de changements dans l'oxygénation du myocarde. Cette technique offre un grand potentiel en tant qu'outil diagnostic primaire pour les maladies cardiovasculaires, en particulier la détection non-invasive d'ischémie. Par contre, il existe plusieurs facteurs potentiellement confondants de cette technique, quelques-uns d'ordre méthodologique comme les paramètres de séquençage et d'autres de nature physiologiques qui sont peut compris. En raison des effets causés par le contenu tissulaire d'eau, l'état d'hydratation peut avoir un impact sur l'intensité du signal. Ceci est un des aspects physiologiques en particulier dont nous voulions quantifier l'effet confondant par la manipulation de l'état d'hydratation chez des humains et l'observation des changements de l'intensité du signal dans des images OS-CMR. Méthodes: In vitro: Du sang artériel et veineux de huit porcs a été utilisé pour évaluer la dilution en série du sang et son effet correspondant sur l'intensité du signal de la séquence OS. In vivo: Vingt-deux volontaires en santé ont subi OS-CMR. Les concentrations d'hémoglobine (Hb) ont été mesurées au niveau de base et immédiatement après une l'infusion cristalloïde rapide de 1000 mL de solution Lactate Ringer's (LRS). Les images OS-CMR ont été prises dans une vue mid-ventriculaire court axe. L'intensité du signal myocardique a été mesurée durant une rétention respiratoire volontaire maximale, suite à une période d'hyperventilation de 60 secondes. Les changements dans l'intensité du signal entre le début et la fin de la rétention de la respiration ont été exprimés relativement au niveau de base (% de changement). Résultats: L'infusion a résulté en une diminution significative de l'Hb mesurée (142.5±3.3 vs. 128.8±3.3 g/L; p<0.001), alors que l'IS a augmenté de 3.2±1.2% entre les images du niveau de base en normo- et hypervolémie (p<0.05). L'IS d'hyperventilation ainsi que les changements d'IS induits par l'apnée ont été attenués après hémodilution (p<0.05). L'évaluation quantitative T2* a démontré une corrélation négative entre le temps de T2* et la concentration d'hémoglobine (r=-0.46, p<0.005). Conclusions: Il existe plusieurs éléments confondants de la technique OS-CMR qui requièrent de l'attention et de l'optimisation pour une future implémentation clinique à grande échelle. Le statut d'hydratation en particulier pourrait être un élément confondant dans l'imagerie OS-CMR. L'hypervolémie mène à une augmentation en IS au niveau de base et atténue la réponse IS durant des manoeuvres de respiration vasoactives. Cette atténuation de l'intensité du signal devrait être tenue en compte et corrigée dans l'évaluation clinique d'images OS-CMR.

Quantitative functional MRI of the Cerebrovascular Reactivity to CO2

Le dioxyde de carbone (CO2) est un résidu naturel du métabolisme cellulaire, la troisième substance la plus abondante du sang, et un important agent vasoactif. À la moindre variation de la teneur en CO2 du sang, la résistance du système vasculaire cérébral et la perfusion tissulaire cérébrale subissent des changements globaux. Bien que les mécanismes exacts qui sous-tendent cet effet restent à être élucidés, le phénomène a été largement exploité dans les études de réactivité vasculaire cérébrale (RVC). Une voie prometteuse pour l’évaluation de la fonction vasculaire cérébrale est la cartographie de la RVC de manière non-invasive grâce à l’utilisation de l’Imagerie par Résonance Magnétique fonctionnelle (IRMf). Des mesures quantitatives et non-invasives de de la RVC peuvent être obtenus avec l’utilisation de différentes techniques telles que la manipu- lation du contenu artériel en CO2 (PaCO2) combinée à la technique de marquage de spin artériel (Arterial Spin Labeling, ASL), qui permet de mesurer les changements de la perfusion cérébrale provoqués par les stimuli vasculaires. Toutefois, les préoccupations liées à la sensibilité et la fiabilité des mesures de la RVC limitent de nos jours l’adoption plus large de ces méthodes modernes de IRMf. J’ai considéré qu’une analyse approfondie ainsi que l’amélioration des méthodes disponibles pourraient apporter une contribution précieuse dans le domaine du génie biomédical, de même qu’aider à faire progresser le développement de nouveaux outils d’imagerie de diagnostique. Dans cette thèse je présente une série d’études où j’examine l’impact des méthodes alternatives de stimulation/imagerie vasculaire sur les mesures de la RVC et les moyens d’améliorer la sensibilité et la fiabilité de telles méthodes. J’ai aussi inclus dans cette thèse un manuscrit théorique où j’examine la possible contribution d’un facteur méconnu dans le phénomène de la RVC : les variations de la pression osmotique du sang induites par les produits de la dissolution du CO2. Outre l’introduction générale (Chapitre 1) et les conclusions (Chapitre 6), cette thèse comporte 4 autres chapitres, au long des quels cinq différentes études sont présentées sous forme d’articles scientifiques qui ont été acceptés à des fins de publication dans différentes revues scientifiques. Chaque chapitre débute par sa propre introduction, qui consiste en une description plus détaillée du contexte motivant le(s) manuscrit(s) associé(s) et un bref résumé des résultats transmis. Un compte rendu détaillé des méthodes et des résultats peut être trouvé dans le(s) dit(s) manuscrit(s). Dans l’étude qui compose le Chapitre 2, je compare la sensibilité des deux techniques ASL de pointe et je démontre que la dernière implémentation de l’ASL continue, la pCASL, offre des mesures plus robustes de la RVC en comparaison à d’autres méthodes pulsés plus âgées. Dans le Chapitre 3, je compare les mesures de la RVC obtenues par pCASL avec l’utilisation de quatre méthodes respiratoires différentes pour manipuler le CO2 artérielle (PaCO2) et je démontre que les résultats peuvent varier de manière significative lorsque les manipulations ne sont pas conçues pour fonctionner dans l’intervalle linéaire de la courbe dose-réponse du CO2. Le Chapitre 4 comprend deux études complémentaires visant à déterminer le niveau de reproductibilité qui peut être obtenu en utilisant des méthodes plus récentes pour la mesure de la RVC. La première étude a abouti à la mise au point technique d’un appareil qui permet des manipulations respiratoires du CO2 de manière simple, sécuritaire et robuste. La méthode respiratoire améliorée a été utilisée dans la seconde étude – de neuro-imagerie – où la sensibilité et la reproductibilité de la RVC, mesurée par pCASL, ont été examinées. La technique d’imagerie pCASL a pu détecter des réponses de perfusion induites par la variation du CO2 dans environ 90% du cortex cérébral humain et la reproductibilité de ces mesures était comparable à celle d’autres mesures hémodynamiques déjà adoptées dans la pratique clinique. Enfin, dans le Chapitre 5, je présente un modèle mathématique qui décrit la RVC en termes de changements du PaCO2 liés à l’osmolarité du sang. Les réponses prédites par ce modèle correspondent étroitement aux changements hémodynamiques mesurés avec pCASL ; suggérant une contribution supplémentaire à la réactivité du système vasculaire cérébral en lien avec le CO2.

Transformations quasi-conformes de maillages volumiques et applications en infographie

La modélisation géométrique est importante autant en infographie qu'en ingénierie. Notre capacité à représenter l'information géométrique fixe les limites et la facilité avec laquelle on manipule les objets 3D. Une de ces représentations géométriques est le maillage volumique, formé de polyèdres assemblés de sorte à approcher une forme désirée. Certaines applications, tels que le placage de textures et le remaillage, ont avantage à déformer le maillage vers un domaine plus régulier pour faciliter le traitement. On dit qu'une déformation est \emph{quasi-conforme} si elle borne la distorsion. Cette thèse porte sur l’étude et le développement d'algorithmes de déformation quasi-conforme de maillages volumiques. Nous étudions ces types de déformations parce qu’elles offrent de bonnes propriétés de préservation de l’aspect local d’un solide et qu’elles ont été peu étudiées dans le contexte de l’informatique graphique, contrairement à leurs pendants 2D. Cette recherche tente de généraliser aux volumes des concepts bien maitrisés pour la déformation de surfaces. Premièrement, nous présentons une approche linéaire de la quasi-conformité. Nous développons une méthode déformant l’objet vers son domaine paramétrique par une méthode des moindres carrés linéaires. Cette méthode est simple d'implémentation et rapide d'exécution, mais n'est qu'une approximation de la quasi-conformité car elle ne borne pas la distorsion. Deuxièmement, nous remédions à ce problème par une approche non linéaire basée sur les positions des sommets. Nous développons une technique déformant le domaine paramétrique vers le solide par une méthode des moindres carrés non linéaires. La non-linéarité permet l’inclusion de contraintes garantissant l’injectivité de la déformation. De plus, la déformation du domaine paramétrique au lieu de l’objet lui-même permet l’utilisation de domaines plus généraux. Troisièmement, nous présentons une approche non linéaire basée sur les angles dièdres. Cette méthode définit la déformation du solide par les angles dièdres au lieu des positions des sommets du maillage. Ce changement de variables permet une expression naturelle des bornes de distorsion de la déformation. Nous présentons quelques applications de cette nouvelle approche dont la paramétrisation, l'interpolation, l'optimisation et la compression de maillages tétraédriques.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay