An algorithm for identifying agent-k-linked allocations in economies with indivisibilities

We consider envy-free (and budget-balanced) rules that are least manipulable with respect to agents counting or with respect to utility gains. Recently it has been shown that for any profile of quasi-linear preferences, the outcome of any such least manipulable envy-free rule can be obtained via agent-k-linked allocations. This note provides an algorithm for identifying agent-k-linked allocations.

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.

A study of chymotrypsin immobilization conditions for improved peptide mapping

La cartographie peptidique est une technique de grande importance utilisée lors de l’identification des protéines et la caractérisation des modifications post-traductionnelles des protéines. Deux méthodes sont utilisées afin de couper les protéines en peptides pour la cartographie : les méthodes chimiques et les méthodes enzymatiques. Dans ce projet, l’enzyme chymotrypsine a été utilisée pour l’hydrolyse (la digestion) des liens peptidiques. Cependant, l’autoprotéolyse des enzymes peut augmenter la complexité des échantillons, rendant ainsi ardue l’obtention de pics résolus suite à l’apparition de pics non-désirés dans la carte peptidique. Par conséquent, nous avons utilisé la réticulation des enzymes protéolytiques par réaction avec le glutaraldéhyde (GA) donnant une enzyme insoluble afin de réduire l’autoprotéolyse. L’immobilisation de la chymotrypsine par GA a été effectuée selon une méthode rapportée précédemment par le groupe Waldron. L’électrophorèse capillaire (CE) couplée à l’absorption UV-visible a été utilisée pour la séparation et la détection de peptides et pour obtenir ainsi une cartographie peptidique. Deux tampons différents ont été évalués afin d’obtenir les meilleures conditions pour la digestion de substrats protéiques par la chymotrypsine libre (soluble) ou la GAchymotrypsine et l’analyse par CE. Les cartes des peptides autoprotéolytiques ont été comparées entre les deux formats de chymotrypsine. Afin d’améliorer la cartographie peptidique, nous avons évalué trois méthodes de conditionnement du capillaire CE et deux méthodes pour stopper la digestion. Le bicarbonate d’ammonium s’est avéré être le tampon optimal pour la digestion en solution et l’utilisation d’un bain d’acétone et de glace sèche s’est avérée être la méthode optimale pour stopper la digestion. Une solution de SDS, 25 mM, dans l’étape de rinçage a été utilisée après chaque analyse CE et a permis d’améliorer la résolution des cartes peptidiques. La comparaison entre l’autoprotéolyse de la chymotrypsine libre et de celle immobilisé par GA a été effectuée par des tests utilisant une gamme de six différentes combinaisons de conditions afin d’évaluer le temps (30 et 240 min) et la température de digestion (4, 24 et 37°C). Dans ces conditions, nos résultats ont confirmé que le GA-chymotrypsine réduit l’autoprotéolyse par rapport à l’enzyme libre. La digestion (à 37°C/240 min) de deux substrats modèles par la chymotrypsine libre et immobilisée en fonction de la température de dénaturation du substrat a été étudiée. iii Avant la digestion, les substrats (l’albumine de sérum bovine, BSA, et la myoglobine) ont été dénaturés par chauffage pendant 45 min à trois températures différentes (60, 75 et 90°C). Les résultats ont démontré que la dénaturation par chauffage du BSA et de la myoglobine n’a pas amélioré la cartographie peptidique pour la GA-chymotrypsine, tandis que la digestion de ceux-ci en présence de la chymotrypsine libre a amélioré de façon quantifiable à des températures élevées. Ainsi, le chauffage du substrat à 90°C avec l’enzyme soluble facilite le dépliement partiel du substrat et sa digestion limitée, ce qui a été mieux pour la myoglobine que pour la BSA.

A robust algorithm for segmenting fluorescence images and its application to single-molecule counting

La microscopie par fluorescence de cellules vivantes produit de grandes quantités de données. Ces données sont composées d’une grande diversité au niveau de la forme des objets d’intérêts et possèdent un ratio signaux/bruit très bas. Pour concevoir un pipeline d’algorithmes efficaces en traitement d’image de microscopie par fluorescence, il est important d’avoir une segmentation robuste et fiable étant donné que celle-ci constitue l’étape initiale du traitement d’image. Dans ce mémoire, je présente MinSeg, un algorithme de segmentation d’image de microscopie par fluorescence qui fait peu d’assomptions sur l’image et utilise des propriétés statistiques pour distinguer le signal par rapport au bruit. MinSeg ne fait pas d’assomption sur la taille ou la forme des objets contenus dans l’image. Par ce fait, il est donc applicable sur une grande variété d’images. Je présente aussi une suite d’algorithmes pour la quantification de petits complexes dans des expériences de microscopie par fluorescence de molécules simples utilisant l’algorithme de segmentation MinSeg. Cette suite d’algorithmes a été utilisée pour la quantification d’une protéine nommée CENP-A qui est une variante de l’histone H3. Par cette technique, nous avons trouvé que CENP-A est principalement présente sous forme de dimère.

Welfare criteria from choice: the sequential solution

We study the problem of deriving a complete welfare ordering from a choice function. Under the sequential solution, the best alternative is the alternative chosen from the universal set; the second best is the one chosen when the best alternative is removed; and so on. We show that this is the only completion of Bernheim and Rangel's (2009) welfare relation that satisfies two natural axioms: neutrality, which ensures that the names of the alternatives are welfare-irrelevant; and persistence, which stipulates that every choice function between two welfare-identical choice functions must exhibit the same welfare ordering.

A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.

Monoacylglycerol, alpha/beta-hydrolase domain-6, and the regulation of insulin secretion and energy metabolism

Le cycle glycérolipides/acides gras libres (GL/FFA) est une voie métabolique clé qui relie le métabolisme du glucose et des acides gras et il est composé de deux processus métaboliques appelés lipogenèse et lipolyse. Le cycle GL/FFA, en particulier la lipolyse des triglycérides, génère diverses molécules de signalisation pour réguler la sécrétion d'insuline dans les cellules bêta pancréatiques et la thermogenèse non-frissonnante dans les adipocytes. Actuellement, les lipides provenant spécifiquement de la lipolyse impliqués dans ce processus sont mal connus. L’hydrolyse des triglycérides dans les cellules β est réalisée par les actions successives de la triglycéride lipase adipocytaire pour produire le diacylglycérol, ensuite par la lipase hormono-sensible pour produire le monoacylglycérol (MAG) et enfin par la MAG lipase (MAGL) qui relâche du glycerol et des acides gras. Dans les cellules bêta, la MAGL classique est très peu exprimée et cette étude a démontré que l’hydrolyse de MAG dans les cellules β est principalement réalisée par l'α/β-Hydrolase Domain-6 (ABHD6) nouvellement identifiée. L’inhibition d’ABHD6 par son inhibiteur spécifique WWL70, conduit à une accumulation des 1-MAG à longues chaines saturées à l'intérieur des cellules, accompagnée d’une augmentation de la sécrétion d'insuline stimulée par le glucose (GSIS). Baisser les niveaux de MAG en surexprimant ABHD6 dans la lignée cellulaire bêta INS832/13 réduit la GSIS, tandis qu’une augmentation des niveaux de MAG par le « knockdown » d’ABHD6 améliore la GSIS. L'exposition aiguë des monoacylglycérols exogènes stimule la sécrétion d'insuline de manière dose-dépendante et restaure la GSIS supprimée par un inhibiteur de lipases appelé orlistat. En outre, les souris avec une inactivation du gène ABHD6 dans tous les tissus (ABHD6-KO) et celles avec une inactivation du gène ABHD6 spécifiquement dans la cellule β présentent une GSIS stimulée, et leurs îlots montrent une augmentation de la production de monoacylglycérol et de la sécrétion d'insuline en réponse au glucose. L’inhibition d’ABHD6 chez les souris diabétiques (modèle induit par de faibles doses de streptozotocine) restaure la GSIS et améliore la tolérance au glucose. De plus, les résultats montrent que les MAGs non seulement améliorent la GSIS, mais potentialisent également la sécrétion d’insuline induite par les acides gras libres ainsi que la sécrétion d’insuline induite par divers agents et hormones, sans altération de l'oxydation et l'utilisation du glucose ainsi que l'oxydation des acides gras. Nous avons démontré que le MAG se lie à la protéine d’amorçage des vésicules appelée Munc13-1 et l’active, induisant ainsi l’exocytose de l'insuline. Sur la base de ces observations, nous proposons que le 1-MAG à chaines saturées agit comme facteur de couplage métabolique pour réguler la sécrétion d'insuline et que ABHD6 est un modulateur négatif de la sécrétion d'insuline. En plus de son rôle dans les cellules bêta, ABHD6 est également fortement exprimé dans les adipocytes et son niveau est augmenté avec l'obésité. Les souris dépourvues globalement d’ABHD6 et nourris avec une diète riche en gras (HFD) montrent une faible diminution de la prise alimentaire, une diminution du gain de poids corporel et de la glycémie à jeun et une amélioration de la tolérance au glucose et de la sensibilité à l'insuline et ont une activité locomotrice accrue. En outre, les souris ABHD6-KO affichent une augmentation de la dépense énergétique et de la thermogenèse induite par le froid. En conformité avec ceci, ces souris présentent des niveaux élevés d’UCP1 dans les adipocytes blancs et bruns, indiquant le brunissement des adipocytes blancs. Le phénotype de brunissement est reproduit dans les souris soit en les traitant de manière chronique avec WWL70 (inhibiteur d’ABHD6) ou des oligonucléotides anti-sense ciblant l’ABHD6. Les tissus adipeux blanc et brun isolés de souris ABHD6-KO montrent des niveaux très élevés de 1-MAG, mais pas de 2-MAG. L'augmentation des niveaux de MAG soit par administration exogène in vitro de 1-MAG ou par inhibition ou délétion génétique d’ABHD6 provoque le brunissement des adipocytes blancs. Une autre évidence indique que les 1-MAGs sont capables de transactiver PPARα et PPARγ et que l'effet de brunissement induit par WWL70 ou le MAG exogène est aboli par les antagonistes de PPARα et PPARγ. L’administration in vivo de l’antagoniste de PPARα GW6471 à des souris ABHD6-KO inverse partiellement les effets causés par l’inactivation du gène ABHD6 sur le gain de poids corporel, et abolit l’augmentation de la thermogenèse, le brunissement du tissu adipeux blanc et l'oxydation des acides gras dans le tissu adipeux brun. L’ensemble de ces observations indique que ABHD6 régule non seulement l’homéostasie de l'insuline et du glucose, mais aussi l'homéostasie énergétique et la fonction des tissus adipeux. Ainsi, 1-MAG agit non seulement comme un facteur de couplage métabolique pour réguler la sécrétion d'insuline en activant Munc13-1 dans les cellules bêta, mais régule aussi le brunissement des adipocytes blancs et améliore la fonction de la graisse brune par l'activation de PPARα et PPARγ. Ces résultats indiquent que ABHD6 est une cible prometteuse pour le développement de thérapies contre l'obésité, le diabète de type 2 et le syndrome métabolique.