Academic literature on the topic 'Algorithmes de passage en message'

Dans les dernières années, plusieurs problèmes ont été étudiés à l'interface entre la physique statistique et l'informatique. La raison étant que, souvent, ces problèmes peuvent être réinterprétés dans le langage de la physique des systèmes désordonnés, où un grand nombre de variables interagit à travers champs locales qui dépendent de l'état du quartier environnant. Parmi les nombreuses applications de l'optimisation combinatoire le routage optimal sur les réseaux de communication est l'objet de la première partie de la thèse. Nous allons exploiter la méthode de la cavité pour formuler des algorithmes efficaces de type ‘’message-passing’’ et donc résoudre plusieurs variantes du problème grâce à sa mise en œuvre numérique. Dans un deuxième temps, nous allons décrire un modèle pour approcher la version dynamique de la méthode de la cavité, ce qui permet de diminuer la complexité du problème de l'exponentielle de polynôme dans le temps. Ceci sera obtenu en utilisant le formalisme de ‘’Matrix Product State’’ de la mécanique quantique.Un autre sujet qui a suscité beaucoup d'intérêt en physique statistique de processus dynamiques est la marche aléatoire sur les réseaux. La théorie a été développée depuis de nombreuses années dans le cas que la topologie dessous est un réseau de dimension d. Au contraire le cas des réseaux aléatoires a été abordé que dans la dernière décennie, laissant de nombreuses questions encore ouvertes pour obtenir des réponses. Démêler plusieurs aspects de ce thème fera l'objet de la deuxième partie de la thèse. En particulier, nous allons étudier le nombre moyen de sites distincts visités au cours d'une marche aléatoire et caractériser son comportement en fonction de la topologie du graphe. Enfin, nous allons aborder les événements rares statistiques associées aux marches aléatoires sur les réseaux en utilisant le ‘’Large deviations formalism’’. Deux types de transitions de phase dynamiques vont se poser à partir de simulations numériques. Nous allons conclure décrivant les principaux résultats d'une œuvre indépendante développée dans le cadre de la physique hors de l'équilibre. Un système résoluble en deux particules browniens entouré par un bain thermique sera étudiée fournissant des détails sur une interaction à médiation par du bain résultant de la présence du bain<br>In the last years several problems been studied at the interface between statistical physics and computer science. The reason being that often these problems can be reinterpreted in the language of physics of disordered systems, where a big number of variables interacts through local fields dependent on the state of the surrounding neighborhood. Among the numerous applications of combinatorial optimisation the optimal routing on communication networks is the subject of the first part of the thesis. We will exploit the cavity method to formulate efficient algorithms of type message-passing and thus solve several variants of the problem through its numerical implementation. At a second stage, we will describe a model to approximate the dynamic version of the cavity method, which allows to decrease the complexity of the problem from exponential to polynomial in time. This will be obtained by using the Matrix Product State formalism of quantum mechanics. Another topic that has attracted much interest in statistical physics of dynamic processes is the random walk on networks. The theory has been developed since many years in the case the underneath topology is a d-dimensional lattice. On the contrary the case of random networks has been tackled only in the past decade, leaving many questions still open for answers. Unravelling several aspects of this topic will be the subject of the second part of the thesis. In particular we will study the average number of distinct sites visited during a random walk and characterize its behaviour as a function of the graph topology. Finally, we will address the rare events statistics associated to random walks on networks by using the large-deviations formalism. Two types of dynamic phase transitions will arise from numerical simulations, unveiling important aspects of these problems. We will conclude outlining the main results of an independent work developed in the context of out-of-equilibrium physics. A solvable system made of two Brownian particles surrounded by a thermal bath will be studied providing details about a bath-mediated interaction arising for the presence of the bath

Cette thèse s’intéresse à l’application de méthodes de physique statistique des systèmes désordonnés ainsi que de l’inférence à des problèmes issus du traitement du signal et de la théorie du codage, plus précisément, aux problèmes parcimonieux d’estimation linéaire. Les outils utilisés sont essentiellement les modèles graphiques et l’algorithme approximé de passage de messages ainsi que la méthode de la cavité (appelée analyse de l’évolution d’état dans le contexte du traitement de signal) pour son analyse théorique. Nous aurons également recours à la méthode des répliques de la physique des systèmes désordonnées qui permet d’associer aux problèmes rencontrés une fonction de coût appelé potentiel ou entropie libre en physique. Celle-ci permettra de prédire les différentes phases de complexité typique du problème, en fonction de paramètres externes tels que le niveau de bruit ou le nombre de mesures liées au signal auquel l’on a accès : l’inférence pourra être ainsi typiquement simple, possible mais difficile et enfin impossible. Nous verrons que la phase difficile correspond à un régime où coexistent la solution recherchée ainsi qu’une autre solution des équations de passage de messages. Dans cette phase, celle-ci est un état métastable et ne représente donc pas l’équilibre thermodynamique. Ce phénomène peut-être rapproché de la surfusion de l’eau, bloquée dans l’état liquide à une température où elle devrait être solide pour être à l’équilibre. Via cette compréhension du phénomène de blocage de l’algorithme, nous utiliserons une méthode permettant de franchir l’état métastable en imitant la stratégie adoptée par la nature pour la surfusion : la nucléation et le couplage spatial. Dans de l’eau en état métastable liquide, il suffit d’une légère perturbation localisée pour que se créer un noyau de cristal qui va rapidement se propager dans tout le système de proche en proche grâce aux couplages physiques entre atomes. Le même procédé sera utilisé pour aider l’algorithme à retrouver le signal, et ce grâce à l’introduction d’un noyau contenant de l’information locale sur le signal. Celui-ci se propagera ensuite via une "onde de reconstruction" similaire à la propagation de proche en proche du cristal dans l’eau. Après une introduction à l’inférence statistique et aux problèmes d’estimation linéaires, on introduira les outils nécessaires. Seront ensuite présentées des applications de ces notions. Celles-ci seront divisées en deux parties. La partie traitement du signal se concentre essentiellement sur le problème de l’acquisition comprimée où l’on cherche à inférer un signal parcimonieux dont on connaît un nombre restreint de projections linéaires qui peuvent être bruitées. Est étudiée en profondeur l’influence de l’utilisation d’opérateurs structurés à la place des matrices aléatoires utilisées originellement en acquisition comprimée. Ceux-ci permettent un gain substantiel en temps de traitement et en allocation de mémoire, conditions nécessaires pour le traitement algorithmique de très grands signaux. Nous verrons que l’utilisation combinée de tels opérateurs avec la méthode du couplage spatial permet d’obtenir un algorithme de reconstruction extrê- mement optimisé et s’approchant des performances optimales. Nous étudierons également le comportement de l’algorithme confronté à des signaux seulement approximativement parcimonieux, question fondamentale pour l’application concrète de l’acquisition comprimée sur des signaux physiques réels. Une application directe sera étudiée au travers de la reconstruction d’images mesurées par microscopie à fluorescence. La reconstruction d’images dites "naturelles" sera également étudiée. En théorie du codage, seront étudiées les performances du décodeur basé sur le passage de message pour deux modèles distincts de canaux continus. Nous étudierons un schéma où le signal inféré sera en fait le bruit que l’on pourra ainsi soustraire au signal reçu. Le second, les codes de superposition parcimonieuse pour le canal additif Gaussien est le premier exemple de schéma de codes correcteurs d’erreurs pouvant être directement interprété comme un problème d’acquisition comprimée structuré. Dans ce schéma, nous appliquerons une grande partie des techniques étudiée dans cette thèse pour finalement obtenir un décodeur ayant des résultats très prometteurs à des taux d’information transmise extrêmement proches de la limite théorique de transmission du canal<br>This thesis is interested in the application of statistical physics methods and inference to signal processing and coding theory, more precisely, to sparse linear estimation problems. The main tools are essentially the graphical models and the approximate message-passing algorithm together with the cavity method (referred as the state evolution analysis in the signal processing context) for its theoretical analysis. We will also use the replica method of statistical physics of disordered systems which allows to associate to the studied problems a cost function referred as the potential of free entropy in physics. It allows to predict the different phases of typical complexity of the problem as a function of external parameters such as the noise level or the number of measurements one has about the signal: the inference can be typically easy, hard or impossible. We will see that the hard phase corresponds to a regime of coexistence of the actual solution together with another unwanted solution of the message passing equations. In this phase, it represents a metastable state which is not the true equilibrium solution. This phenomenon can be linked to supercooled water blocked in the liquid state below its freezing critical temperature. Thanks to this understanding of blocking phenomenon of the algorithm, we will use a method that allows to overcome the metastability mimicing the strategy adopted by nature itself for supercooled water: the nucleation and spatial coupling. In supercooled water, a weak localized perturbation is enough to create a crystal nucleus that will propagate in all the medium thanks to the physical couplings between closeby atoms. The same process will help the algorithm to find the signal, thanks to the introduction of a nucleus containing local information about the signal. It will then spread as a "reconstruction wave" similar to the crystal in the water. After an introduction to statistical inference and sparse linear estimation, we will introduce the necessary tools. Then we will move to applications of these notions. They will be divided into two parts. The signal processing part will focus essentially on the compressed sensing problem where we seek to infer a sparse signal from a small number of linear projections of it that can be noisy. We will study in details the influence of structured operators instead of purely random ones used originally in compressed sensing. These allow a substantial gain in computational complexity and necessary memory allocation, which are necessary conditions in order to work with very large signals. We will see that the combined use of such operators with spatial coupling allows the implementation of an highly optimized algorithm able to reach near to optimal performances. We will also study the algorithm behavior for reconstruction of approximately sparse signals, a fundamental question for the application of compressed sensing to real life problems. A direct application will be studied via the reconstruction of images measured by fluorescence microscopy. The reconstruction of "natural" images will be considered as well. In coding theory, we will look at the message-passing decoding performances for two distincts real noisy channel models. A first scheme where the signal to infer will be the noise itself will be presented. The second one, the sparse superposition codes for the additive white Gaussian noise channel is the first example of error correction scheme directly interpreted as a structured compressed sensing problem. Here we will apply all the tools developed in this thesis for finally obtaining a very promising decoder that allows to decode at very high transmission rates, very close of the fundamental channel limit

À une époque où l'utilisation des données a atteint un niveau sans précédent, l'apprentissage machine, et plus particulièrement l'apprentissage profond basé sur des réseaux de neurones artificiels, a été responsable de très importants progrès pratiques. Leur utilisation est désormais omniprésente dans de nombreux domaines d'application, de la classification d'images à la reconnaissance vocale en passant par la prédiction de séries temporelles et l'analyse de texte. Pourtant, la compréhension de nombreux algorithmes utilisés en pratique est principalement empirique et leur comportement reste difficile à analyser. Ces lacunes théoriques soulèvent de nombreuses questions sur leur efficacité et leurs potentiels risques. Établir des fondements théoriques sur lesquels asseoir les observations numériques est devenu l'un des défis majeurs de la communauté scientifique.La principale difficulté qui se pose lors de l’analyse de la plupart des algorithmes d'apprentissage automatique est de traiter analytiquement et numériquement un grand nombre de variables aléatoires en interaction. Dans ce manuscrit, nous revisitons une approche basée sur les outils de la physique statistique des systèmes désordonnés. Développés au long d’une riche littérature, ils ont été précisément conçus pour décrire le comportement macroscopique d'un grand nombre de particules, à partir de leurs interactions microscopiques. Au cœur de ce travail, nous mettons fortement à profit le lien profond entre la méthode des répliques et les algorithmes de passage de messages pour mettre en lumière les diagrammes de phase de divers modèles théoriques, en portant l’accent sur les potentiels écarts entre seuils statistiques et algorithmiques. Nous nous concentrons essentiellement sur des tâches et données synthétiques générées dans le paradigme enseignant-élève. En particulier, nous appliquons ces méthodes à champ moyen à l'analyse Bayes-optimale des machines à comité, à l'analyse des bornes de généralisation de Rademacher pour les perceptrons, et à la minimisation du risque empirique dans le contexte des modèles linéaires généralisés. Enfin, nous développons un cadre pour analyser des modèles d'estimation avec des informations à priori structurées, produites par exemple par des réseaux de neurones génératifs avec des poids aléatoires<br>At a time when the use of data has reached an unprecedented level, machine learning, and more specifically deep learning based on artificial neural networks, has been responsible for very important practical advances. Their use is now ubiquitous in many fields of application, from image classification, text mining to speech recognition, including time series prediction and text analysis. However, the understanding of many algorithms used in practice is mainly empirical and their behavior remains difficult to analyze. These theoretical gaps raise many questions about their effectiveness and potential risks. Establishing theoretical foundations on which to base numerical observations has become one of the fundamental challenges of the scientific community. The main difficulty that arises in the analysis of most machine learning algorithms is to handle, analytically and numerically, a large number of interacting random variables. In this manuscript, we revisit an approach based on the tools of statistical physics of disordered systems. Developed through a rich literature, they have been precisely designed to infer the macroscopic behavior of a large number of particles from their microscopic interactions. At the heart of this work, we strongly capitalize on the deep connection between the replica method and message passing algorithms in order to shed light on the phase diagrams of various theoretical models, with an emphasis on the potential differences between statistical and algorithmic thresholds. We essentially focus on synthetic tasks and data generated in the teacher-student paradigm. In particular, we apply these mean-field methods to the Bayes-optimal analysis of committee machines, to the worst-case analysis of Rademacher generalization bounds for perceptrons, and to empirical risk minimization in the context of generalized linear models. Finally, we develop a framework to analyze estimation models with structured prior informations, produced for instance by deep neural networks based generative models with random weights

Les réseaux ad hoc mobiles (MANETs) sont des systèmes de communication sans fil rapidement déployables et qui fonctionnent avec une coordination minimale, ceci afin d'éviter les pertes d'efficacité spectrale induites par la signalisation. Les stratégies de transmissions coopératives présentent un intérêt pour les MANETs, mais la nature distribuée de tels protocoles peut augmenter le niveau d'interférence avec un impact autant plus sévère que l'on cherche à pousser les limites des efficacités énergétique et spectrale. L'impact de l'interférence doit alors être réduit par l'utilisation d'algorithmes de traitement du signal au niveau de la couche PHY, avec une complexité calculatoire raisonnable. Des avancées récentes sur les techniques de conception de récepteurs numériques itératifs proposent d'exploiter l'inférence bayésienne approximée et des techniques de passage de message associés afin d'améliorer le potentiel des turbo-détecteurs plus classiques. Entre autres, la propagation d'espérance (EP) est une technique flexible, qui offre des compromis attractifs de complexité et de performance dans des situations où la propagation de croyance conventionnel est limité par sa complexité calculatoire. Par ailleurs, grâce à des techniques émergentes de l'apprentissage profond, de telles structures itératives peuvent être projetés vers des réseaux de détection profonds, où l'apprentissage des hyper-paramètres algorithmiques améliore davantage les performances. Dans cette thèse nous proposons des égaliseurs à retour de décision à réponse impulsionnelle finie basée sur la propagation d'espérance (EP) qui apportent des améliorations significatives, en particulier pour des applications à haute efficacité spectrale vis à vis des turbo-détecteurs conventionnels, tout en ayant l'avantage d'être asymptotiquement prédictibles. Nous proposons un cadre générique pour la conception de récepteurs dans le domaine fréquentiel, afin d'obtenir des architectures de détection avec une faible complexité calculatoire. Cette approche est analysée théoriquement et numériquement, avec un accent mis sur l'égalisation des canaux sélectifs en fréquence, et avec des extensions pour de la détection dans des canaux qui varient dans le temps ou pour des systèmes multi-antennes. Nous explorons aussi la conception de détecteurs multi-utilisateurs, ainsi que l'impact de l'estimation du canal, afin de comprendre le potentiel et le limite de cette approche. Pour finir, nous proposons une méthode de prédiction performance à taille finie, afin de réaliser une abstraction de lien pour l'égaliseur domaine fréquentiel à base d'EP. L'impact d'un modélisation plus fine de la couche PHY est évalué dans le contexte de la diffusion coopérative pour des MANETs tactiques, grâce à un simulateur flexible de couche MAC<br>Mobile ad hoc networks (MANETs) are rapidly deployable wireless communications systems, operating with minimal coordination in order to avoid spectral efficiency losses caused by overhead. Cooperative transmission schemes are attractive for MANETs, but the distributed nature of such protocols comes with an increased level of interference, whose impact is further amplified by the need to push the limits of energy and spectral efficiency. Hence, the impact of interference has to be mitigated through with the use PHY layer signal processing algorithms with reasonable computational complexity. Recent advances in iterative digital receiver design techniques exploit approximate Bayesian inference and derivative message passing techniques to improve the capabilities of well-established turbo detectors. In particular, expectation propagation (EP) is a flexible technique which offers attractive complexity-performance trade-offs in situations where conventional belief propagation is limited by computational complexity. Moreover, thanks to emerging techniques in deep learning, such iterative structures are cast into deep detection networks, where learning the algorithmic hyper-parameters further improves receiver performance. In this thesis, EP-based finite-impulse response decision feedback equalizers are designed, and they achieve significant improvements, especially in high spectral efficiency applications, over more conventional turbo-equalization techniques, while having the advantage of being asymptotically predictable. A framework for designing frequency-domain EP-based receivers is proposed, in order to obtain detection architectures with low computational complexity. This framework is theoretically and numerically analysed with a focus on channel equalization, and then it is also extended to handle detection for time-varying channels and multiple-antenna systems. The design of multiple-user detectors and the impact of channel estimation are also explored to understand the capabilities and limits of this framework. Finally, a finite-length performance prediction method is presented for carrying out link abstraction for the EP-based frequency domain equalizer. The impact of accurate physical layer modelling is evaluated in the context of cooperative broadcasting in tactical MANETs, thanks to a flexible MAC-level simulator

Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matrices<br>In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion

La réalité mixe, les jeux en ligne massivement multijoueur (MMOGs), les mondes virtuels et le cyberespace sont des concepts extrêmement attractifs. Mais leur déploiement à large échelle reste difficile et il est en conséquence souvent évité.La contribution principale de la thèse réside dans le système distribué Kiwano, qui permet à un nombre illimité d'avatars de peupler et d'interagir simultanément dans un même monde contigu. Dans Kiwano nous utilisons la triangulation de Delaunay pour fournir à chaque avatar un nombre constant de voisins en moyenne, indépendamment de leur densité ou distribution géographique. Le nombre d'interactions entre les avatars et les calculs inhérents sont bornés, ce qui permet le passage à l'échelle du système.La charge est repartie sur plusieurs machines qui regroupent sur un même nœud les avatars voisins de façon contiguë dans le graphe de Delaunay. L'équilibrage de la charge se fait de manière contiguë et dynamique, en suivant la philosophie des réseaux pair-à-pair (peer-to-peer overlays). Cependant ce principe est adapté au contexte de l'informatique dématérialisée (cloud computing).Le nombre optimal d'avatars par CPU et les performances de notre système ont été évalués en simulant des dizaines de milliers d'avatars connectés à la même instance de Kiwano tournant à travers plusieurs centres de traitement de données.Nous proposons également trois applications concrètes qui utilisent Kiwano : Manycraft est une architecture distribuée capable de supporter un nombre arbitrairement grand d'utilisateurs cohabitant dans le même espace Minecraft, OneSim, qui permet à un nombre illimité d'usagers d'être ensemble dans la même région de Second Life et HybridEarth, un monde en réalité mixte où avatars et personnes physiques sont présents et interagissent dans un même espace: la Terre<br>Virtual worlds attract millions of users and these popular applications --supported by gigantic data centers with myriads of processors-- are routinely accessed. However, surprisingly, virtual worlds are still unable to host simultaneously more than a few hundred users in the same contiguous space.The main contribution of the thesis is Kiwano, a distributed system enabling an unlimited number of avatars to simultaneously evolve and interact in a contiguous virtual space. In Kiwano we employ the Delaunay triangulation to provide each avatar with a constant number of neighbors independently of their density or distribution. The avatar-to-avatar interactions and related computations are then bounded, allowing the system to scale. The load is constantly balanced among Kiwano's nodes which adapt and take in charge sets of avatars according to their geographic proximity. The optimal number of avatars per CPU and the performances of our system have been evaluated simulating tens of thousands of avatars connecting to a Kiwano instance running across several data centers, with results well beyond the current state-of-the-art.We also propose Kwery, a distributed spatial index capable to scale dynamic objects of virtual worlds. Kwery performs efficient reverse geolocation queries on large numbers of moving objects updating their position at arbitrary high frequencies. We use a distributed spatial index on top of a self-adaptive tree structure. Each node of the system hosts and answers queries on a group of objects in a zone, which is the minimal axis-aligned rectangle. They are chosen based on their proximity and the load of the node. Spatial queries are then answered only by the nodes with meaningful zones, that is, where the node's zone intersects the query zone.Kiwano has been successfully implemented for HybridEarth, a mixed reality world, Manycraft, our scalable multiplayer Minecraft map, and discussed for OneSim, a distributed Second Life architecture. By handling avatars separately, we show interoperability between these virtual worlds.With Kiwano and Kwery we provide the first massively distributed and self-adaptive solutions for virtual worlds suitable to run in the cloud. The results, in terms of number of avatars per CPU, exceed by orders of magnitude the performances of current state-of-the-art implementations. This indicates Kiwano to be a cost effective solution for the industry. The open API for our first implementation is available at \url{http://kiwano.li}

La réalité mixe, les jeux en ligne massivement multijoueur (MMOGs), les mondes virtuels et le cyberespace sont des concepts extrêmement attractifs. Mais leur déploiement à large échelle reste difficile et il est en conséquence souvent évité.La contribution principale de la thèse réside dans le système distribué Kiwano, qui permet à un nombre illimité d'avatars de peupler et d'interagir simultanément dans un même monde contigu. Dans Kiwano nous utilisons la triangulation de Delaunay pour fournir à chaque avatar un nombre constant de voisins en moyenne, indépendamment de leur densité ou distribution géographique. Le nombre d'interactions entre les avatars et les calculs inhérents sont bornés, ce qui permet le passage à l'échelle du système.La charge est repartie sur plusieurs machines qui regroupent sur un même nœud les avatars voisins de façon contiguë dans le graphe de Delaunay. L'équilibrage de la charge se fait de manière contiguë et dynamique, en suivant la philosophie des réseaux pair-à-pair (peer-to-peer overlays). Cependant ce principe est adapté au contexte de l'informatique dématérialisée (cloud computing).Le nombre optimal d'avatars par CPU et les performances de notre système ont été évalués en simulant des dizaines de milliers d'avatars connectés à la même instance de Kiwano tournant à travers plusieurs centres de traitement de données.Nous proposons également trois applications concrètes qui utilisent Kiwano : Manycraft est une architecture distribuée capable de supporter un nombre arbitrairement grand d'utilisateurs cohabitant dans le même espace Minecraft, OneSim, qui permet à un nombre illimité d'usagers d'être ensemble dans la même région de Second Life et HybridEarth, un monde en réalité mixte où avatars et personnes physiques sont présents et interagissent dans un même espace: la Terre<br>Virtual worlds attract millions of users and these popular applications --supported by gigantic data centers with myriads of processors-- are routinely accessed. However, surprisingly, virtual worlds are still unable to host simultaneously more than a few hundred users in the same contiguous space.The main contribution of the thesis is Kiwano, a distributed system enabling an unlimited number of avatars to simultaneously evolve and interact in a contiguous virtual space. In Kiwano we employ the Delaunay triangulation to provide each avatar with a constant number of neighbors independently of their density or distribution. The avatar-to-avatar interactions and related computations are then bounded, allowing the system to scale. The load is constantly balanced among Kiwano's nodes which adapt and take in charge sets of avatars according to their geographic proximity. The optimal number of avatars per CPU and the performances of our system have been evaluated simulating tens of thousands of avatars connecting to a Kiwano instance running across several data centers, with results well beyond the current state-of-the-art.We also propose Kwery, a distributed spatial index capable to scale dynamic objects of virtual worlds. Kwery performs efficient reverse geolocation queries on large numbers of moving objects updating their position at arbitrary high frequencies. We use a distributed spatial index on top of a self-adaptive tree structure. Each node of the system hosts and answers queries on a group of objects in a zone, which is the minimal axis-aligned rectangle. They are chosen based on their proximity and the load of the node. Spatial queries are then answered only by the nodes with meaningful zones, that is, where the node's zone intersects the query zone.Kiwano has been successfully implemented for HybridEarth, a mixed reality world, Manycraft, our scalable multiplayer Minecraft map, and discussed for OneSim, a distributed Second Life architecture. By handling avatars separately, we show interoperability between these virtual worlds.With Kiwano and Kwery we provide the first massively distributed and self-adaptive solutions for virtual worlds suitable to run in the cloud. The results, in terms of number of avatars per CPU, exceed by orders of magnitude the performances of current state-of-the-art implementations. This indicates Kiwano to be a cost effective solution for the industry. The open API for our first implementation is available at \url{http://kiwano.li}

Des antennes multiples du côté de la station de base peuvent être utilisées pour améliorer l'efficacité spectrale et l'efficacité énergétique des technologies sans fil de nouvelle génération. En effet, le multi-entrées et sorties multiples massives (MIMO) est considéré comme une technologie prometteuse pour apporter les avantages susmentionnés pour la norme sans fil de cinquième génération, communément appelée 5G New Radio (5G NR). Dans cette monographie, nous explorerons un large éventail de sujets potentiels dans Multi-userMIMO (MU-MIMO) pertinents pour la 5G NR,• Conception de la formation de faisceaux (BF) maximisant le taux de somme et robustesse à l'état de canal partiel informations à l'émetteur (CSIT)• Analyse asymptotique des différentes techniques BF en MIMO massif et• Méthodes d'estimation de canal bayésien utilisant un apprentissage bayésien clairsemé.L'une des techniques potentielles proposées dans la littérature pour contourner la complexité matérielle et la consommation d'énergie dans le MIMO massif est la formation de faisceaux hybrides. Nous proposons une conception de phaseur analogique globalement optimale utilisant la technique du recuit déterministe, qui nous a valu le prix du meilleur article étudiant. En outre, afin d'analyser le comportement des grands systèmes des systèmes MIMO massifs, nous avons utilisé des techniques de la théorie des matrices aléatoires et obtenu des expressions de taux de somme simplifiées. Enfin, nous avons également examiné le problème de récupération de signal bayésien clairsemé en utilisant la technique appelée apprentissage bayésien clairsemé (SBL)<br>Multiple antennas at the base station side can be used to enhance the spectral efficiency and energy efficiency of the next generation wireless technologies. Indeed, massive multi-input multi-output (MIMO) is seen as one promising technology to bring the aforementioned benefits for fifth generation wireless standard, commonly known as 5G New Radio (5G NR). In this monograph, we will explore a wide range of potential topics in multi-userMIMO (MU-MIMO) relevant to 5G NR,• Sum rate maximizing beamforming (BF) design and robustness to partial channel stateinformation at the transmitter (CSIT)• Asymptotic analysis of the various BF techniques in massive MIMO and• Bayesian channel estimation methods using sparse Bayesian learning.One of the potential techniques proposed in the literature to circumvent the hardware complexity and power consumption in massive MIMO is hybrid beamforming. We propose a globally optimal analog phasor design using the technique of deterministic annealing, which won us the best student paper award. Further, in order to analyze the large system behaviour of the massive MIMO systems, we utilized techniques from random matrix theory and obtained simplified sum rate expressions. Finally, we also looked at Bayesian sparse signal recovery problem using the technique called sparse Bayesian learning (SBL). We proposed low complexity SBL algorithms using a combination of approximate inference techniques such as belief propagation (BP), expectation propagation and mean field (MF) variational Bayes. We proposed an optimal partitioning of the different parameters (in the factor graph) into either MF or BP nodes based on Fisher information matrix analysis

Dans un système d'inférence pair-à-pair, chaque pair peut raisonner localement mais peut également solliciter son voisinage constitué des pairs avec lesquels il partage une partie de son vocabulaire. Une caractéristique importante des systèmes d'inférence pair-à-pair est que la théorie globale (l'union des théories de tous les pairs) n'est pas connue. La première contribution majeure de cette thèse est de proposer le premier algorithme de calcul de conséquence dans un environnement pair-à-pair : DeCA. L'algorithme calcul les conséquences graduellement en partant des pairs sollicités jusqu'aux pairs de plus en plus distant. On fournit une condition suffisante sur le graphe de voisinage du système d'inférence pair-à-pair, garantissant la complétude de l'algorithme. Une autre contribution importante est l'application de ce cadre général de raisonnement distribué au contexte du web sémantique à travers les systèmes de gestion de données pair-à-pair SomeOWL et SomeRDFS. Ces systèmes permettent à chaque pair d'annoter (de catégoriser) ses données à l'aide d'ontologies simples et d'établir des liens sémantique, appelés " mappings ", entre son ontologie et celle de ses voisins. Les modèles de donnée de SomeOWL et SomeRDFS sont respectivement fondés sur les deux recommandations récentes du W3C pour le web sémantique : OWL et RDF(S). La dernière contribution de cette thèse est de fournir une étude expérimentale poussée du passage à l'échelle de l'infrastructure pair-à-pair que nous proposons, et ce sur des réseaux allant jusqu'à 1000 pairs<br>In a peer-to-peer inference system, each peer can reason locally but can also solicit some of its acquaintances, which are peers sharing part of its vocabulary. In this thesis, we consider peer-to-peer inference systems in which the local theory of each peer is a set of propositional clauses defined upon a local vocabulary. An important characteristic of peer-to-peer inference systems is that the global theory (the union of all peer theories) is not known. The first main contribution of this thesis is to provide the first consequence finding algorithm in a peer-to-peer setting: DeCA. It is anytime and computes consequences gradually from the solicited peer to peers that are more and more distant. We exhibit a sufficient condition on the acquaintance graph of the peer-to-peer inference system for guaranteeing the completeness of this algorithm. Another important contribution is to apply this general distributed reasoning setting to the setting of the Semantic Web through the SomeOWL and SomeRDFS peer-to-peer data management systems. Those systems allow each peer to annotate (categorize) its data using simple ontologies and to establish mappings with ontologies of its acquaintances. SomeOWL and SomeRDFS data models are respectively based on the two emerging W3C recommendations for the semantic web, namely OWL and RDF(S). The last contribution of this thesis is to provide an extensive experimental analysis of the scalability of the peer-to-peer infrastructure that we propose, on large networks of 1000 peers