Generative models of protein structure enable researchers to predict the behavior of proteins under different conditions. Continuous graphical models are powerful and efficient tools for modeling static and dynamic distributions, which can be used for learning generative models of molecular dynamics. In this thesis, we develop new and improved continuous graphical models, to be used in modeling of protein structure. We first present von Mises graphical models, and develop consistent and efficient algorithms for sparse structure learning and parameter estimation, and inference. We compare our model to sparse Gaussian graphical model and show it outperforms GGMs on synthetic and Engrailed protein molecular dynamics datasets. Next, we develop algorithms to estimate Mixture of von Mises graphical models using Expectation Maximization, and show that these models outperform Von Mises, Gaussian and mixture of Gaussian graphical models in terms of accuracy of prediction in imputation test of non-redundant protein structure datasets. We then use non-paranormal and nonparametric graphical models, which have extensive representation power, and compare several state of the art structure learning methods that can be used prior to nonparametric inference in reproducing kernel Hilbert space embedded graphical models. To be able to take advantage of the nonparametric models, we also propose feature space embedded belief propagation, and use random Fourier based feature approximation in our proposed feature belief propagation, to scale the inference algorithm to larger datasets. To improve the scalability further, we also show the integration of Coreset selection algorithm with the nonparametric inference, and show that the combined model scales to large datasets with very small adverse effect on the quality of predictions. Finally, we present time varying sparse Gaussian graphical models, to learn smoothly varying graphical models of molecular dynamics simulation data, and present results on CypA protein

Dá-se o nome de sistemas de reputação a mecanismos em que membros de uma comunidade emitem avaliações sobre os demais e a partir destas se inferem quais dos membros podem ou não ser considerados confiáveis. Apresentamos, nesta dissertação de mestrado, um estudo sobre estes sistemas. Modela-se o problema de calcular reputações a partir de avaliações não-confiáveis como um problema de inferência estatística, que é então analisado com o uso de uma técnica conhecida como propagação de crenças, permitindo que obtenhamos estimativas. Em seguida, utilizamo-nos da relação existente entre problemas de inferência e mecânica estatística para realizar um estudo analítico mais profundo, por meio de uma generalização do método de cavidade. São traçados diagramas de fase, em que se observam regiões de parâmetros para as quais o problema torna-se mais difícil de resolver; esta análise nos dá alguma intuição sobre o problema, possibilitando que sejam propostas melhorias aos métodos existentes para tratá-lo. / It\'s given the name of reputation system to mechanisms in which members of a community issue each other ratings and from these it is inferred which can be trusted and which can\'t. We present, in this master\'s dissertation, a study on these systems. The problem of calculating reputations from unreliable ratings is modeled as one of statistical inference, and then analyzed with the use of a technique known as belief propagation, allowing us to obtain estimatives. Next, we use the existing relation between inference problems and statistical mechanics to motivate a deeper study, by means of a generalization of the cavity method. Phase diagrams are drawn, making possible to identify regions of parameters for which the problem is harder to solve; this analysis brings insight to the problem, allowing one to propose improvements to the methods available for it\'s treatment.

Reliable communication over the noisy channel has become one of the major concerns in the field of digital wireless communications. The low density parity check codes (LDPC) has gained lot of attention recently because of their excellent error-correcting capacity. It was first proposed by Robert G. Gallager in 1960. LDPC codes belong to the class of linear block codes. Near capacity performance is achievable on a large collection of data transmission and storage.In my thesis I have focused on hardware implementation of (3, 6) - regular LDPC codes. A fully parallel decoder will require too high complexity of hardware realization. Partly parallel decoder has the advantage of effective compromise between decoding throughput and high hardware complexity. The decoding of the codeword follows the belief propagation alias probability propagation algorithm in log domain. A 9216 bit, (3, 6) regular LDPC code with code rate ½ was implemented on FPGA targeting Xilinx Virtex 4 XC4VLX80 device with package FF1148. This decoder achieves a maximum throughput of 82 Mbps. The entire model was designed in VHDL in the Xilinx ISE 9.2 environment.

This dissertation has its focus on two different topics: 1. non-asymptotic analysis of polar codes as a new paradigm in error correcting codes with very promising features, and 2. network properties for wireless networks of practical size. In its first part, we investigate properties of polar codes that can be potentially useful in real-world applications. We start with analyzing the performance of finite-length polar codes over the binary erasure channel (BEC), while assuming belief propagation (BP) as the decoding method. We provide a stopping set analysis for the factor graph of polar codes, where we find the size of the minimum stopping set. Our analysis along with bit error rate (BER) simulations demonstrates that finite-length polar codes show superior error floor performance compared to the conventional capacity-approaching coding techniques. Motivated by good error floor performance, we introduce a modified version of BP decoding while employing a guessing algorithm to improve the BER performance. Each application may impose its own requirements on the code design. To be able to take full advantage of polar codes in practice, a fundamental question is which practical requirements are best served by polar codes. For example, we will see that polar codes are inherently well-suited for rate-compatible applications and they can provably achieve the capacity of time-varying channels with a simple rate-compatible design. This is in contrast to LDPC codes for which no provably universally capacity-achieving design is known except for the case of the erasure channel. This dissertation investigates different approaches to applications such as UEP, rate-compatible coding, and code design over parallel sub-channels (non-uniform error correction). Furthermore, we consider the idea of combining polar codes with other coding schemes, in order to take advantage of polar codes' best properties while avoiding their shortcomings. Particularly, we propose, and then analyze, a polar code-based concatenated scheme to be used in Optical Transport Networks (OTNs) as a potential real-world application The second part of the dissertation is devoted to the analysis of finite wireless networks as a fundamental problem in the area of wireless networking. We refer to networks as being finite when the number of nodes is less than a few hundred. Today, due to the vast amount of literature on large-scale wireless networks, we have a fair understanding of the asymptotic behavior of such networks. However, in real world we have to face finite networks for which the asymptotic results cease to be valid. Here we study a model of wireless networks, represented by random geometric graphs. In order to address a wide class of the network's properties, we study the threshold phenomena. Being extensively studied in the asymptotic case, the threshold phenomena occurs when a graph theoretic property (such as connectivity) of the network experiences rapid changes over a specific interval of the underlying parameter. Here, we find an upper bound for the threshold width of finite line networks represented by random geometric graphs. These bounds hold for all monotone properties of such networks. We then turn our attention to an important non-monotone characteristic of line networks which is the Medium Access (MAC) layer capacity, defined as the maximum number of possible concurrent transmissions. Towards this goal, we provide a linear time algorithm which finds a maximal set of concurrent non-interfering transmissions and further derive lower and upper bounds for the cardinality of the set. Using simulations, we show that these bounds serve as reasonable estimates for the actual value of the MAC-layer capacity.

No description available.

No description available.

A Factor Graph (FG -- http://en.wikipedia.org/wiki/Factor_graph) is a structure used to find solutions to problems that can be represented as a Probabilistic Graphical Model (PGM). They consist of interconnected variable nodes and factor nodes, which iteratively compute and pass messages to each other. FGs can be applied to solve decoding of forward error correcting codes, Markov chains and Markov Random Fields, Kalman Filtering, Fourier Transforms, and even some games such as Sudoku. In this paper, a framework is presented for rapid prototyping of hardware implementations of FG-based applications. The FG developer specifies aspects of the application, such as graphical structure, factor computation, and message passing algorithm, and the framework returns a design. A system of Python scripts and Verilog Hardware Description Language templates together are used to generate the HDL source code for the application. The generated designs are vendor/platform agnostic, but currently target the Xilinx Virtex-6-based ML605. The framework has so far been primarily applied to construct Low Density Parity Check (LDPC) decoders. The characteristics of a large basket of generated LDPC decoders, including contemporary 802.11n decoders, have been examined as a verification of the system and as a demonstration of its capabilities. As a further demonstration, the framework has been applied to construct a Sudoku solver. / Master of Science

Large-dimensional communication systems are likely to play an important role in modern wireless communications, where dimensions can be in space, time, frequency and their combinations. Large dimensions can bring several advantages with respect to the performance of communication systems. Harnessing such large-dimension benefits in practice, however, is challenging. In particular, optimum signal detection gets prohibitively complex for large dimensions. Consequently, low-complexity detection techniques that scale well for large dimensions while achieving near-optimal performance are of interest. Belief Propagation (BP) is a technique that solves inference problems using graphical models. BP has been successfully employed in a variety of applications including computational biology, statistical signal/image processing, machine learning and artificial intelligence. BP is well suited in several communication problems as well; e.g., decoding of turbo codes and low-density parity check codes (LDPC), and multiuser detection. We propose a BP based algorithm for detection in large-dimension linear vector channels employing binary phase shift keying (BPSK) modulation, by adopting a Markov random field (MRF)graphical model of the system. The proposed approach is shown to achieve i)detection at low complexities that scale well for large dimensions, and ii)improved bit error performance for increased number of dimensions (a behavior we refer to as the ’large-system behavior’). As one application of the BP based approach, we demonstrate the effectiveness of the proposed BP algorithm for decoding non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA)having large dimensions. We further improve the performance of the proposed algorithm through damped belief propagation, where messages that are passed from one iteration to the next are formed as a weighted combination of messages from the current iteration and the previous iteration. Next, we extend the proposed BP approach to higher order modulation. through a novel scheme of interference cancellation. This proposed scheme exhibits large system behavior in terms of bit error performance, while being scalable to large dimensions in terms of complexity. Finally, as another application of the BP based approach, we illustrate the adoption and performance of the proposed BP algorithm for low-complexity near-optimal equalization in severely delay-spread UWBMIMO-ISI channels that are characterized by large number (tens to hundreds)of multipath components.

La sécurité des personnes et des équipements est un élément capital dans le domaine des transports routiers et ferroviaires. Depuis quelques années, les Passages à Niveau (PN) ont fait l’objet de davantage d'attention afin d'accroître la sécurité des usagers sur cette portion route/rail considérée comme dangereuse. Nous proposons dans cette thèse un système de vision stéréoscopique pour la détection automatique des situations dangereuses. Un tel système permet la détection et la localisation d'obstacles sur ou autour du PN. Le système de vision proposé est composé de deux caméras supervisant la zone de croisement. Nous avons développé des algorithmes permettant à la fois la détection d'objets, tels que des piétons ou des véhicules, et la localisation 3D de ces derniers. L'algorithme de détection d'obstacles se base sur l'Analyse en Composantes Indépendantes et la propagation de croyance spatio-temporelle. L'algorithme de localisation tridimensionnelle exploite les avantages des méthodes locales et globales, et est composé de trois étapes : la première consiste à estimer une carte de disparité à partir d'une fonction de vraisemblance basée sur les méthodes locales. La deuxième étape permet d'identifier les pixels bien mis en correspondance ayant des mesures de confiances élevées. Ce sous-ensemble de pixels est le point de départ de la troisième étape qui consiste à ré-estimer les disparités du reste des pixels par propagation de croyance sélective. Le mouvement est introduit comme une contrainte dans l'algorithme de localisation 3D permettant l'amélioration de la précision de localisation et l'accélération du temps de traitement. / Within the past years, railways undertakings became interested in the assessment of Level Crossings (LC) safety. We propose in this thesis an Automatic Video-Surveillance system (AVS) at LC for an automatic detection of specific events. The system allows automatically detecting and 3D localizing the presence of one or more obstacles which are motionless at the level crossing. Our research aims at developing an AVS using the passive stereo vision principles. The proposed imaging system uses two cameras to detect and localize any kind of object lying on a railway level crossing. The cameras are placed so that the dangerous zones are well (fully) monitored. The system supervises and estimates automatically the critical situations by detecting objects in the hazardous zone defined as the crossing zone of a railway line by a road or path. The AVS system is used to monitor dynamic scenes where interactions take place among objects of interest (people or vehicles). After a classical image grabbing and digitizing step, the processing is composed of the two following modules: moving and stationary objects detection and 3-D localization. The developed stereo matching algorithm stems from an inference principle based on belief propagation and energy minimization. It takes into account the advantages of local methods for reducing the complexity of the inference step achieved by the belief propagation technique which leads to an improvement in the quality of results. The motion detection module is considered as a constraint which allows improving and speeding up the 3D localization algorithm.

Detecting and tracking moving objects are important topics in computer vision research. Classical methods perform well in applications of steady cameras. However, these techniques are not suitable for the applications of moving cameras because the unconstrained nature of realistic environments and sudden camera movement makes cues to object positions rather fickle. A major difficulty is that every pixel moves and new background keeps showing up when a handheld or car-mounted camera moves. In this dissertation, a novel estimation method of camera motion parameters will be discussed first. Based on the estimated camera motion parameters, two detection algorithms are developed using Bayes' rule and belief propagation. Next, an MCMC-based feature-guided particle filtering method is presented to track detected moving objects. In addition, two detection algorithms without using camera motion parameters will be further discussed. These two approaches require no pre-defined class or model to be trained in advance. The experiment results will demonstrate robust detecting and tracking performance in object sizes and positions.