Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userContamination Source Detection in Water Distribution Networks using Belief Propagation
58
0
0.0
(
0
)
Added by
Alejandro Lage-Castellanos
Publication date
2018
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a Bayesian approach for the Contamination Source Detection problem in Water Distribution Networks. Given an observation of contaminants in one or more nodes in the network, we try to give probable explanation for it assuming that contamination is a rare event. We introduce extra variables to characterize the place and pattern of the first contamination event. Then we write down the posterior distribution for these extra variables given the observation obtained by the sensors. Our method relies on Belief Propagation for the evaluation of the marginals of this posterior distribution and the determination of the most likely origin. The method is implemented on a simplified binary forward-in-time dynamics. Simulations on data coming from the realistic simulation software EPANET on two networks show that the simplified model is nevertheless flexible enough to capture crucial information about contaminant sources.
rate research
Read More
We study the inference of the origin and the pattern of contamination in water distribution networks. We assume a simplified model for the dyanmics of the contamination spread inside a water distribution network, and assume that at some random location a sensor detects the presence of contaminants. We transform the source location problem into an optimization problem by considering discrete times and a binary contaminated/not contaminated state for the nodes of the network. The resulting problem is solved by Mixed Integer Linear Programming. We test our results on random networks as well as in the Modena city network.
Learned neural solvers have successfully been used to solve combinatorial optimization and decision problems. More general counting variants of these problems, however, are still largely solved with hand-crafted solvers. To bridge this gap, we introduce belief propagation neural networks (BPNNs), a class of parameterized operators that operate on factor graphs and generalize Belief Propagation (BP). In its strictest form, a BPNN layer (BPNN-D) is a learned iterative operator that provably maintains many of the desirable properties of BP for any choice of the parameters. Empirically, we show that by training BPNN-D learns to perform the task better than the original BP: it converges 1.7x faster on Ising models while providing tighter bounds. On challenging model counting problems, BPNNs compute estimates 100s of times faster than state-of-the-art handcrafted methods, while returning an estimate of comparable quality.
The community detection problem requires to cluster the nodes of a network into a small number of well-connected communities. There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming belief-propagation (StreamBP) approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data.
Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortcoming that it works poorly in the common case of networks that contain short loops. Here we provide a solution to this long-standing problem, deriving a belief propagation method that allows for fast calculation of probability distributions in systems with short loops, potentially with high density, as well as giving expressions for the entropy and partition function, which are notoriously difficult quantities to compute. Using the Ising model as an example, we show that our approach gives excellent results on both real and synthetic networks, improving significantly on standard message passing methods. We also discuss potential applications of our method to a variety of other problems.
This paper proposes a belief propagation (BP)-based algorithm for sequential detection and estimation of multipath components (MPCs) parameters based on radio signals. Under dynamic channel conditions with moving transmitter and/or receiver, the number of MPCs reflected from visible geometric features, the MPC dispersion parameters (delay, angle, Doppler frequency, etc), and the number of false alarm contributions are unknown and time-varying. We develop a Bayesian model for sequential detection and estimation of MPC dispersion parameters, and represent it by a factor graph enabling the use of BP for efficient computation of the marginal posterior distributions. At each time instance, a snapshot-based channel estimator provides parameter estimates of a set of MPCs which are used as noisy measurements by the proposed BP-based algorithm. It performs joint probabilistic data association, estimation of the time-varying MPC parameters, and the mean number of false alarm measurements by means of the sum-product algorithm rules. The results using synthetic measurements show that the proposed algorithm is able to cope with a high number of false alarm measurements originating from the snapshot-based channel estimator and to sequentially detect and estimate MPCs parameters with very low signal-to-noise ratio (SNR). The performance of the proposed algorithm compares well to existing algorithms for high SNR MPCs, but significantly it outperforms them for medium or low SNR MPCs. In particular, we show that our algorithm outperforms the Kalman enhanced super resolution tracking (KEST) algorithm, a state-of-the-art sequential channel parameters estimation method. Furthermore, results with real radio measurements demonstrate the excellent performance of the algorithm in realistic and challenging scenarios.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
