Non-parametric belief propagation (NBP) is a well-known message passing method for cooperative localization in wireless networks. However, due to the over-counting problem in the networks with loops, NBP’s convergence is not guaranteed, and its estimates are typically less accurate. One solution for this problem is non-parametric generalized belief propagation based on junction tree. However, this method is intractable in large-scale networks due to the high-complexity of the junction tree formation, and the high-dimensionality of the particles. Therefore, in this article, we propose the non-parametric generalized belief propagation based on pseudo-junction tree (NGBP-PJT). The main difference comparing with the standard method is the formation of pseudo-junction tree, which represents the approximated junction tree based on thin graph. In addition, in order to decrease the number of high-dimensional particles, we use more informative importance density function, and reduce the dimensionality of the messages. As by-product, we also propose NBP based on thin graph (NBP-TG), a cheaper variant of NBP, which runs on the same graph as NGBP-PJT. According to our simulation and experimental results, NGBP-PJT method outperforms NBP and NBP-TG in terms of accuracy, computational, and communication cost in reasonably sized networks. / COOPLOC / FP7-ICT WHERE2

Wide-band spectrum sensing is an approach for finding spectrum holes within a wideband signal with less complexity/delay than the conventional approaches. In this thesis, we propose four different algorithms for detecting the holes in a wide-band spectrum and finding the sparsity level of compressive signals. The first algorithm estimates the spectrum in an efficient manner and uses this estimation to find the holes. The second algorithm detects the spectrum holes by reconstructing channel energies instead of reconstructing the spectrum itself. In this method, the signal is fed into a number of filters. The energies of the filter outputs are used as the compressed measurement to reconstruct the signal energy. The third algorithm employs two information theoretic algorithms to find the sparsity level of a compressive signal and the last algorithm employs belief propagation for detecting the sparsity level.

Wide-band spectrum sensing is an approach for finding spectrum holes within a wideband signal with less complexity/delay than the conventional approaches. In this thesis, we propose four different algorithms for detecting the holes in a wide-band spectrum and finding the sparsity level of compressive signals. The first algorithm estimates the spectrum in an efficient manner and uses this estimation to find the holes. The second algorithm detects the spectrum holes by reconstructing channel energies instead of reconstructing the spectrum itself. In this method, the signal is fed into a number of filters. The energies of the filter outputs are used as the compressed measurement to reconstruct the signal energy. The third algorithm employs two information theoretic algorithms to find the sparsity level of a compressive signal and the last algorithm employs belief propagation for detecting the sparsity level.

Computer networks are constantly being attacked by malicious entities for various reasons. Network based attacks include but are not limited to, Distributed Denial of Service (DDoS), DNS based attacks, Cross-site Scripting (XSS) etc. Such attacks have exploited either the network protocol or the end-host software vulnerabilities for perpetration. Current network traffic analysis techniques employed for detection and/or prevention of these anomalies suffer from significant delay or have only limited scalability because of their huge resource requirements. This dissertation proposes more scalable techniques for network anomaly detection. We propose using DNS analysis for detecting a wide variety of network anomalies. The use of DNS is motivated by the fact that DNS traffic comprises only 2-3% of total network traffic reducing the burden on anomaly detection resources. Our motivation additionally follows from the observation that almost any Internet activity (legitimate or otherwise) is marked by the use of DNS. We propose several techniques for DNS traffic analysis to distinguish anomalous DNS traffic patterns which in turn identify different categories of network attacks. First, we present MiND, a system to detect misdirected DNS packets arising due to poisoned name server records or due to local infections such as caused by worms like DNSChanger. MiND validates misdirected DNS packets using an externally collected database of authoritative name servers for second or third-level domains. We deploy this tool at the edge of a university campus network for evaluation. Secondly, we focus on domain-fluxing botnet detection by exploiting the high entropy inherent in the set of domains used for locating the Command and Control (C&C) server. We apply three metrics namely the Kullback-Leibler divergence, the Jaccard Index, and the Edit distance, to different groups of domain names present in Tier-1 ISP DNS traces obtained from South Asia and South America. Our evaluation successfully detects existing domain-fluxing botnets such as Conficker and also recognizes new botnets. We extend this approach by utilizing DNS failures to improve the latency of detection. Alternatively, we propose a system which uses temporal and entropy-based correlation between successful and failed DNS queries, for fluxing botnet detection. We also present an approach which computes the reputation of domains in a bipartite graph of hosts within a network, and the domains accessed by them. The inference technique utilizes belief propagation, an approximation algorithm for marginal probability estimation. The computation of reputation scores is seeded through a small fraction of domains found in black and white lists. An application of this technique, on an HTTP-proxy dataset from a large enterprise, shows a high detection rate with low false positive rates.

This memo describes the initial results of a project to create aself-supervised algorithm for learning object segmentation from videodata. Developmental psychology and computational experience havedemonstrated that the motion segmentation of objects is a simpler,more primitive process than the detection of object boundaries bystatic image cues. Therefore, motion information provides a plausiblesupervision signal for learning the static boundary detection task andfor evaluating performance on a test set. A video camera andpreviously developed background subtraction algorithms canautomatically produce a large database of motion-segmented images forminimal cost. The purpose of this work is to use the information insuch a database to learn how to detect the object boundaries in novelimages using static information, such as color, texture, and shape.This work was funded in part by the Office of Naval Research contract#N00014-00-1-0298, in part by the Singapore-MIT Alliance agreement of11/6/98, and in part by a National Science Foundation Graduate StudentFellowship.

RNA (Ribonuceic Acid) sequencing technology is a powerful technology used to give re- searchers essential information about the functionality of genes. The transcriptomic study and downstream analysis highlight the functioning of the genes associated with a specific biological process/treatment. In practice, differentially expressed genes associated with a particular treatment or genotype are subjected to downstream analysis to find some critical set of genes. This critical set of genes/ genes pathways infers the effect of the treatment in a cell or tissue. This disserta- tion describes the multiple stages framework of finding these critical sets of genes using different analysis methodologies and inference algorithms. RNA sequencing technology helps to find the differentially expressed genes associated with the treatments and genotypes. The preliminary step of RNA-seq analysis consists of extracting the mRNA(messenger RNA) followed by mRNA libraries’ preparation and sequencing using the Illumina HiSeq 2000 platform. The later stage analysis starts with mapping the RNA sequencing data (obtained from the previous step) to the genome annotations and counting each annotated gene’s reads to produce the gene expression data. The second step involves using the statistical method such as linear model fit, clustering, and probabilistic graphical modeling to analyze genes and gene networks’ role in treatment responses. In this dissertation, an R software package is developed that compiles all the RNA sequencing steps and the downstream analysis using the R software and Linux environment. Inference methodology based on loopy belief propagation is conducted on the gene networks to infer the differential expression of the gene in the further step. The loopy belief propagation algorithm uses a computational modeling framework that takes the gene expression data and the transcriptional Factor interacting with the genes. The inference method starts with constructing a gene-Transcriptional Factor network. The construction of the network uses an undirected proba- bilistic graphical modeling approach. Later the belief message is propagated across all the nodes of the graphs. The analysis and inference methods explained in the dissertation were applied to the Arabidopsis plant with two different genotypes subjected to two different stress treatments. The results for the analysis and inference methods are reported in the dissertation.

<p>We present a detailed study on application of factor<br />graphs and the belief propagation (BP) algorithm to the<br />power system state estimation (SE) problem. We start<br />from the BP solution for the linear DC model, for which<br />we provide a detailed convergence analysis. Using BPbased<br />DC model we propose a fast real-time state<br />estimator for the power system SE. The proposed<br />estimator is easy to distribute and parallelize, thus<br />alleviating computational limitations and allowing for<br />processing measurements in real time. The presented<br />algorithm may run as a continuous process, with each<br />new measurement being seamlessly processed by the<br />distributed state estimator. In contrast to the matrixbased<br />SE methods, the BP approach is robust to illconditioned<br />scenarios caused by significant differences<br />between measurement variances, thus resulting in a<br />solution that eliminates observability analysis. Using the<br />DC model, we numerically demonstrate the performance<br />of the state estimator in a realistic real-time system<br />model with asynchronous measurements. We note that<br />the extension to the non-linear SE is possible within the<br />same framework.<br />Using insights from the DC model, we use two different<br />approaches to derive the BP algorithm for the non-linear<br />model. The first method directly applies BP methodology,<br />however, providing only approximate BP solution for the<br />non-linear model. In the second approach, we make a key<br />further step by providing the solution in which the BP is<br />applied sequentially over the non-linear model, akin to<br />what is done by the Gauss-Newton method. The resulting<br />iterative Gauss-Newton belief propagation (GN-BP)<br />algorithm can be interpreted as a distributed Gauss-<br />Newton method with the same accuracy as the<br />centralized SE, however, introducing a number of<br />advantages of the BP framework. The thesis provides<br />extensive numerical study of the GN-BP algorithm,<br />provides details on its convergence behavior, and gives a<br />number of useful insights for its implementation.<br />Finally, we define the bad data test based on the BP<br />algorithm for the non-linear model. The presented model<br />establishes local criteria to detect and identify bad data<br />measurements. We numerically demonstrate that the<br />BP-based bad data test significantly improves the bad<br />data detection over the largest normalized residual test.</p> / <p>Glavni rezultati ove teze su dizajn i analiza novih<br />algoritama za re&scaron;avanje problema estimacije stanja<br />baziranih na faktor grafovima i &bdquo;Belief Propagation&ldquo; (BP)<br />algoritmu koji se mogu primeniti kao centralizovani ili<br />distribuirani estimatori stanja u elektroenergetskim<br />sistemima. Na samom početku, definisan je postupak za<br />re&scaron;avanje linearnog (DC) problema kori&scaron;ćenjem BP<br />algoritma. Pored samog algoritma data je analiza<br />konvergencije i predloženo je re&scaron;enje za unapređenje<br />konvergencije. Algoritam se može jednostavno<br />distribuirati i paralelizovati, te je pogodan za estimaciju<br />stanja u realnom vremenu, pri čemu se informacije mogu<br />prikupljati na asinhroni način, zaobilazeći neke od<br />postojećih rutina, kao npr. provera observabilnosti<br />sistema. Pro&scaron;irenje algoritma za nelinearnu estimaciju<br />stanja je moguće unutar datog modela.<br />Dalje se predlaže algoritam baziran na probabilističkim<br />grafičkim modelima koji je direktno primenjen na<br />nelinearni problem estimacije stanja, &scaron;to predstavlja<br />logičan korak u tranziciji od linearnog ka nelinearnom<br />modelu. Zbog nelinearnosti funkcija, izrazi za određenu<br />klasu poruka ne mogu se dobiti u zatvorenoj formi, zbog<br />čega rezultujući algoritam predstavlja aproksimativno<br />re&scaron;enje. Nakon toga se predlaže distribuirani Gaus-<br />Njutnov metod baziran na probabilističkim grafičkim<br />modelima i BP algoritmu koji postiže istu tačnost kao i<br />centralizovana verzija Gaus-Njutnovog metoda za<br />estimaciju stanja, te je dat i novi algoritam za otkrivanje<br />nepouzdanih merenja (outliers) prilikom merenja<br />električnih veličina. Predstavljeni algoritam uspostavlja<br />lokalni kriterijum za otkrivanje i identifikaciju<br />nepouzdanih merenja, a numerički je pokazano da<br />algoritam značajno pobolj&scaron;ava detekciju u odnosu na<br />standardne metode.</p>

On s'intéresse à la construction et l'estimation - à partir d'observations incomplètes - de modèles de variables aléatoires à valeurs réelles sur un graphe. Ces modèles doivent être adaptés à un problème de régression non standard où l'identité des variables observées (et donc celle des variables à prédire) varie d'une instance à l'autre. La nature du problème et des données disponibles nous conduit à modéliser le réseau sous la forme d'un champ markovien aléatoire, choix justifié par le principe de maximisation d'entropie de Jaynes. L'outil de prédiction choisi dans ces travaux est l'algorithme Belief Propagation - dans sa version classique ou gaussienne - dont la simplicité et l'efficacité permettent son utilisation sur des réseaux de grande taille. Après avoir fourni un nouveau résultat sur la stabilité locale des points fixes de l'algorithme, on étudie une approche fondée sur un modèle d'Ising latent où les dépendances entre variables réelles sont encodées à travers un réseau de variables binaires. Pour cela, on propose une définition de ces variables basée sur les fonctions de répartition des variables réelles associées. Pour l'étape de prédiction, il est nécessaire de modifier l'algorithme Belief Propagation pour imposer des contraintes de type bayésiennes sur les distributions marginales des variables binaires. L'estimation des paramètres du modèle peut aisément se faire à partir d'observations de paires. Cette approche est en fait une manière de résoudre le problème de régression en travaillant sur les quantiles. D'autre part, on propose un algorithme glouton d'estimation de la structure et des paramètres d'un champ markovien gaussien, basé sur l'algorithme Iterative Proportional Scaling. Cet algorithme produit à chaque itération un nouveau modèle dont la vraisemblance, ou une approximation de celle-ci dans le cas d'observations incomplètes, est supérieure à celle du modèle précédent. Cet algorithme fonctionnant par perturbation locale, il est possible d'imposer des contraintes spectrales assurant une meilleure compatibilité des modèles obtenus avec la version gaussienne de Belief Propagation. Les performances des différentes approches sont illustrées par des expérimentations numériques sur des données synthétiques. / In this work, we focus on the design and estimation - from partial observations - of graphical models of real-valued random variables. These models should be suited for a non-standard regression problem where the identity of the observed variables (and therefore of the variables to predict) changes from an instance to the other. The nature of the problem and of the available data lead us to model the network as a Markov random field, a choice consistent with Jaynes' maximum entropy principle. For the prediction task, we turn to the Belief Propagation algorithm - in its classical or Gaussian flavor - which simplicity and efficiency make it usable on large scale networks. After providing a new result on the local stability of the algorithm's fixed points, we propose an approach based on a latent Ising model, where dependencies between real-valued variables are encoded through a network of binary variables. To this end, we propose a definition of these variables using the cumulative distribution functions of the real-valued variables. For the prediction task, it is necessary to modify the Belief Propagation algorithm in order to impose Bayesian-like constraints on marginal distributions of the binary variables. Estimation of the model parameters can easily be performed using only pairwise observations. In fact, this approach is a way to solve the regression problem by working on quantiles.Furthermore, we propose a greedy algorithm for estimating both the structure and the parameters of a Gauss-Markov random field based on the Iterative Proportional Scaling procedure. At each iteration, the algorithm yields a new model which likelihood, or an approximation of it in the case of partial observations,is higher than the one of the previous model. Because of its local perturbation principle, this algorithm allows us to impose spectral constraints, increasing the compatibility with the Gaussian Belief Propagation algorithm. The performances of all approaches are empirically illustrated on synthetic data.

The topic of Markov Random Fields (MRFs) has been well studied in the past, and has found practical use in various image processing, and machine learning applications. Where coding is concerned, MRF specific schemes have been largely unexplored. In this thesis, an overview is given of recent developments and challenges in the lossless coding of MRFs. Specifically, we concentrate on difficulties caused by computational intractability due to the partition function of the MRF. One proposed solution to this problem is to segment the MRF with a cutset, and encode the components separately. Using this method, arithmetic coding is possible via the Belief Propagation (BP) algorithm. We consider two cases of the BP algorithm: MRFs with only simple cliques, and MRFs with complex cliques. In the latter case, we study a minimum radius condition requirement for ensuring that all cliques are accounted for during coding. This condition also simplifies the process of conditioning on observed sites. Finally, using these results, we develop a systematic procedure of clustering and choosing cutsets. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2013-08-12 14:50:00.596

Evidence suggests that high-level feedback plays an important role in visual perception by shaping the response in lower cortical levels (Sillito et al. 2006, Angelucci and Bullier 2003, Bullier 2001, Harrison et al. 2007). A notable example of this is reflected by the retinotopic activation of V1 and V2 neurons in response to illusory contours, such as Kanizsa figures, which has been reported in numerous studies (Maertens et al. 2008, Seghier and Vuilleumier 2006, Halgren et al. 2003, Lee 2003, Lee and Nguyen 2001). The illusory contour activity emerges first in lateral occipital cortex (LOC), then in V2 and finally in V1, strongly suggesting that the response is driven by feedback connections. Generative models and Bayesian belief propagation have been suggested to provide a theoretical framework that can account for feedback connectivity, explain psychophysical and physiological results, and map well onto the hierarchical distributed cortical connectivity (Friston and Kiebel 2009, Dayan et al. 1995, Knill and Richards 1996, Geisler and Kersten 2002, Yuille and Kersten 2006, Deneve 2008a, George and Hawkins 2009, Lee and Mumford 2003, Rao 2006, Litvak and Ullman 2009, Steimer et al. 2009). The present study explores the role of feedback in object perception, taking as a starting point the HMAX model, a biologically inspired hierarchical model of object recognition (Riesenhuber and Poggio 1999, Serre et al. 2007b), and extending it to include feedback connectivity. A Bayesian network that captures the structure and properties of the HMAX model is developed, replacing the classical deterministic view with a probabilistic interpretation. The proposed model approximates the selectivity and invariance operations of the HMAX model using the belief propagation algorithm. Hence, the model not only achieves successful feedforward recognition invariant to position and size, but is also able to reproduce modulatory effects of higher-level feedback, such as illusory contour completion, attention and mental imagery. Overall, the model provides a biophysiologically plausible interpretation, based on state-of-theart probabilistic approaches and supported by current experimental evidence, of the interaction between top-down global feedback and bottom-up local evidence in the context of hierarchical object perception.