190 Pages
English
Gain access to the library to view online
Learn more

Approximate inference algorithms in large networked systems [Elektronische Ressource] / Chongning Na

Gain access to the library to view online
Learn more
190 Pages
English

Subjects

Informations

Published by
Published 01 January 2010
Reads 19
Language English
Document size 5 MB

Exrait

¨ ¨TECHNISCHE UNIVERSITAT MUNCHEN
Lehrstuhl fur¨ Netzwerktheorie und Signalverarbeitung
Approximateinferencealgorithmsinlarge
networkedsystems
Chongning Na
Vollstandiger¨ Abdruck der von der Fakultat¨ fur¨ Elektrotechnik und Infor-
mationstechnik der Technischen Universitat¨ Munchen¨ zur Erlangung des
akademischen Grades eines
Doktor-Ingenieurs
genehmigten Dissertation.
Vorsitzender: Univ.-Prof.Dr.-Ing.EckehardSteinbach
Prufer¨ der Dissertation:
1. Univ.-Prof.Dr.techn.JosefA.Nossek
2. UnivDr.-Ing.habil.GerhardRigoll
Die Dissertation wurde am 27.11.2009 bei der Technischen Universitat¨
M¨ unchen eingereicht und durch die Fakultat¨ fur¨ Elektrotechnik und In-
formationstechnik am26.04.2010 angenommen.Acknowledgements
During the course of my Ph.D., I have received assistant and support from my supervi-
sors, colleagues, family and friends. I am grateful for this opportunity to acknowledge
these people and their kindly contributions.
First and foremost I want to express my deep gratitude to my advisor Dr. Dragan
Obradovic for his dedicated guidance, enlightening suggestions and enthusiastic discus-
sions from the initial to the final level. I am very fortunate to work with him. I am also
thankful for his offering of the research position at Siemens AG, Corporate Technology for
me, with which I am able to finish my Ph.D. and participate several interesting projects.
Using these opportunities, I have grown tremendously as a researcher. I would like to
thank Professor Josef A. Nossek who also supervised my thesis, gave me many useful
advises and shared his vision and experience with me. I could not wish for a better or
friendlier supervisor.
I would like express my gratitude to Dr. Ruxandra Lupas Scheiterer for her generous
encouragement and help. She patiently taught me many important skills, from writing
good articles to making impressive presentations. I believe that I will benefit from those
skills throughout my research career. I would like to thank my colleagues, Dr. Andrei
Szabo, Dr. Marco Pellegrino and Dr. Philipp Wolfrum for their suggestions and support
in my work. I am thankful for the help and friendship of all my officemates.
I would like to thank Siemens AG, Corporate Technology for funding my Ph.D. research.
I appreciated the support from Professor Bernd Schurmann¨ and Dr. Thomas Runkler.
During my stay at Siemens, I had the opportunity to work on several industrial projects
which gave me valuable experiences.
On a personal level, I am most grateful to my family, my parents Na Lvguan and Guo
Lianqing, my sister Na Yichao and my brother-in-law Cai Xiaochuan. They have always
loved and supported me. I know they are very happy and proud for me when I am getting
this degree. I am grateful to my close friends Fu Bo, Wang Hui, Sun Yiming and Liu Junqi.
They made my life in Munich an enjoyable experience and their sincere friendship was
invaluable to me.
Last but not least, I thank the MSCE program and all the professors who have supported
this program. It was this master program which brought me to Germany and offered me
the invaluable opportunity to study at the Technical University of Munich, which will be
a precious experience both for my career and life.
IIIContents
ListofFigures VII
ListofTables X
Abstract 1
1. Introduction 3
1.1 Background . . . . . .... ... .... ... .... .... ... .... ... 3
1.2 Problem statement . .... ... .... ... .... .... ... .... ... 5
1.3 Contributions and overview of the thesis . . .... .... ... .... ... 6
2. GraphicalModels 9
2.1 Bayesian networks . .... ... .... ... .... .... ... .... ... 9
2.2 Markov random fields . . . . . . .... ... .... .... ... .... ... 12
2.3 Factor graphs . . . . .... ... .... ... .... .... ... .... ... 13
2.4 Conversion between different graphs . . . . .... .... ... .... ... 14
2.4.1 Conversion from Bayesian networks to Markov random fields . . . . 15
2.4.2 from to factor graphs . . .... ... 16
2.4.3 Conversion from Markov random fields to factor graphs .... ... 16
2.5 Some remarks on graphical models . . . . . . .... .... ... .... ... 17
2.5.1 A comparison of different graphs . . . .... .... ... .... ... 18
2.5.2 Parameter estimation based on graphical models . . . . .... ... 19
2.5.3 Independence property . .... ... .... .... ... .... ... 19
2.5.4 Benefits from using graphical models .... .... ... .... ... 20
2.A Judgement of conditional independence using Bayes rule . . . . .... ... 20
2.B Summary of notations . . . . . . .... ... .... .... ... .... ... 24
IIIIV Contents
3. InferenceAlgorithms 27
3.1 Problem formulation .... ... .... ... .... .... ... .... ... 28
3.2 Exact inference . . . . .... ... .... ... .... .... ... .... ... 28
3.2.1 Brute force and variable elimination approach . . . . . . .... ... 29
3.2.2 Belief propagation on graphical models . . . .... ... .... ... 31
3.2.3 Junction tree algorithm . . .... ... .... .... ... .... ... 33
3.3 Approximate inference . . . . . . .... ... .... .... ... .... ... 38
3.3.1 Loopy belief propagation .... ... .... .... ... .... ... 38
3.3.2 Variational inference . . . .... ... .... .... ... .... ... 39
3.4 Extensions and discussions . . . .... ... .... .... ... .... ... 42
3.A Sum-product algorithm on a tree .... ... .... .... ... .... ... 43
3.A.1 Evaluation of marginals in factor graphs . . .... ... .... ... 44
3.A.2 A sum-product algorithm example . . .... .... ... .... ... 47
4. ProbabilisticInferenceinNetworkedSystems 51
4.1 Distributed inference .... ... .... ... .... .... ... .... ... 53
4.1.1 Problem formulation . . . .... ... .... .... ... .... ... 53
4.1.2 General assumptions . . . .... ... .... .... ... .... ... 53
4.1.3 General inference procedure . . . . . .... .... ... .... ... 54
4.1.4 Example of distributed inference . . . .... .... ... .... ... 55
4.2 Function and message approximation in inference . .... ... .... ... 63
4.2.1 Fourier domain belief propagation . . .... .... ... .... ... 65
4.2.2 Non-parametric belief pr . . .... .... ... .... ... 72
4.3 State estimation for dynamical systems . . . .... .... ... .... ... 77
4.3.1 Problem formulation . . . .... ... .... .... ... .... ... 78
4.3.2 Graphical model for dynamical systems . . . .... ... .... ... 78
4.3.3 Inference in dynamical systems . . . . .... .... ... .... ... 79
4.4 Remark and discussions . . . . . .... ... .... .... ... .... ... 85
4.A Property of Gaussian density functions . . . .... .... ... .... ... 86
4.A.1 Derivation of Gaussian integral . . . . .... .... ... .... ... 86
4.A.2 of product . . . . .... .... ... .... ... 87Contents V
5. BeliefPropagationForSensorLocalization 89
5.1 Background . . . . . .... ... .... ... .... .... ... .... ... 90
5.2 System model . . . . .... ... .... ... .... .... ... .... ... 91
5.3 Probabilistic model for sensor localization . . .... .... ... .... ... 91
5.4 Belief propagation for sensor . . .... .... ... .... ... 92
5.5 Fourier domain belief propagation for sensor localization . . . . .... ... 94
5.5.1 Discretization of the space domain . . .... .... ... .... ... 95
5.5.2 Simplified transmission based on Fourier series approximation . . . 97
5.5.3 computation and transmission based on FDBP . . . . . . 98
5.6 Non-parametric belief propagation for sensor localization . . . . .... ...100
5.7 Simulation results . . .... ... .... ... .... .... ... .... ...102
5.7.1 A simple scenario . . . . . .... ... .... .... ... .... ...103
5.7.2 Simulation in a large scale sensor network . .... ... .... ...104
5.8 Discussions . . . . . .... ... .... ... .... .... ... .... ...105
6. ClockSynchronizationOfNetworkedNodes 111
6.1 Background . . . . . .... ... .... ... .... .... ... .... ...112
6.1.1 Characteristics of clocks . .... ... .... .... ... .... ...112
6.1.2 Network topology . . . . .... ... .... .... ... .... ...113
6.1.3 PTP messages .... ... .... ... .... .... ... .... ...114
6.1.4 Peer to peer transparent clock . . . . . .... .... ... .... ...115
6.1.5 Peer to peer line delay estimation . . .... .... ... .... ...117
6.2 Notations.... ... .... ... .... ... .... .... ... .... ...124
6.3 Simulation settings . .... ... .... ... .... .... ... .... ...125
6.4 Standard synchronization algorithm . . . . . .... .... ... .... ...126
6.5 Probabilistic model for clock synchronization .... .... ... .... ...128
6.5.1 Probabilistic model . . . . .... ... .... .... ... .... ...129
6.5.2 Model analysis . . . . . . .... ... .... .... ... .... ...131
6.5.3 State space model and centralized master time estimation . . . . . . 135
6.5.4 The sum-product algorithm for master time . .... ...139
6.5.5 Sequential Kalman filter for master time estimation . . . .... ...145
6.6 Numerical evaluation of synchronization algorithms . . . . . . .... ...151
6.6.1 Synchronization with constant clock frequency . . . . . . .... ...151
6.6.2 Synchr under adverse environmental effects . . .... ...153
6.7 Discussions . . . . . .... ... .... ... .... .... ... .... ...160
6.A Connection between SKF and the standard synchronization algorithm . . . 161VI Contents
7. ConclusionsandFutureWork 165
7.1 Summary and contributions . . . .... ... .... .... ... .... ...165
7.2 Discussion on future directions . .... ... .... .... ... .... ...166
7.2.1 Measurement of the error caused by approximation . . . .... ...166
7.2.2 Distributed inference . . . .... ... .... .... ... .... ...166
7.2.3 Other potential applications . . . . . . .... .... ... .... ...167
Bibliography 169ListofFigures
2.1 Bayesian Network Example . . . .... ... .... .... ... .... ... 10
2.2 Conditional independence property in a three node Bayesian network . . . 11
2.3 A Markov random field example. .... ... .... .... ... .... ... 13
2.4 A factor graph example . . . . . .... ... .... .... ... .... ... 14
2.5 Factor graph vs Forney style factor graph . . .... .... ... .... ... 15
2.6 Conversion from a Bayesian network to a Markov random field .... ... 16
2.7 from a to a factor graph . . . . . .... ... 17
2.8 Conversion from a Markov random field to a factor graph . . . .... ... 18
2.9 Bayesian network with parameters. . . . . . . .... .... ... .... ... 19
2.10 Three node Bayesian network: head to head . .... .... ... .... ... 20
2.11 Three node tail to tail . . . .... .... ... .... ... 21
2.12 Three node Bayesian network: tail to head . . .... .... ... .... ... 22
2.13 Three node head to tail . . .... .... ... .... ... 23
3.1 Markov random field for the example in (3.5) .... .... ... .... ... 30
3.2 Procedure of node elimination . . .... ... .... .... ... .... ... 30
3.3 Message passing on a factor graph . . . . . . .... .... ... .... ... 32
3.4 Clique elimination in a undirected graph . . .... .... ... .... ... 34
3.5 Generating a junction tree from a complete cluster graph . . . . .... ... 35
3.6 Message passing in a junction tree . . . . . . .... .... ... .... ... 36
3.7 Junction tree with separators . . .... ... .... .... ... .... ... 37
3.8 Message passing in Forney style factor graph .... .... ... .... ... 43
3.9 Directed graph representing (3.33) . . . . . . .... .... ... .... ... 44
3.10 Illustration of marginal calculation . . . . . . .... .... ... .... ... 45
3.11 An example of the sum-product algorithm in factor graph . . . .... ... 47
VIIVIII List of Figures
4.1 Topology of the network and the spatial correlation .... ... .... ... 56
4.2 Assignment of factors, scheme 1 .... ... .... .... ... .... ... 57
4.3 Junction tree for assignment scheme 1 . . . . .... .... ... .... ... 57
4.4 Message passing for scheme 1 . . .... .... ... .... ... 57
4.5 Complexity of inference based on assignment scheme 1 . . . . . .... ... 58
4.6 Assignment of factors, scheme 2 .... ... .... .... ... .... ... 58
4.7 Junction tree for assignment scheme 2 . . . . .... .... ... .... ... 59
4.8 Message passing for scheme 2 . . .... .... ... .... ... 59
4.9 Complexity of inference based on assignment scheme 2 . . . . . .... ... 60
4.10 Data transmission to the fusion center . . . . .... .... ... .... ... 60
4.11 Factor graph for centralized inference . . . . .... .... ... .... ... 61
4.12 Message passing for inference . . .... .... ... .... ... 61
4.13 Complexity of centralized inference . . . . . .... .... ... .... ... 62
4.14 Transmission of the final results . .... ... .... .... ... .... ... 62
4.15 A FDBP example . . .... ... .... ... .... .... ... .... ... 71
4.16 An NBP . . .... ... .... ... .... .... ... .... ... 73
4.17 Subgraph with simpler structure .... ... .... .... ... .... ... 77
4.18 An example of 2TBN .... ... .... ... .... .... ... .... ... 80
4.19 Interface algorithm . .... ... .... ... .... .... ... .... ... 83
4.20 Boyen and Koller algorithm . . . .... ... .... .... ... .... ... 85
5.1 Pairwise potential function . . . .... ... .... .... ... .... ... 94
5.2 Messages in BP in sensor localization . . . . . .... .... ... .... ... 94
5.3 Sensor distribution . .... ... .... ... .... .... ... .... ...103
5.4 Comparison of different approximation methods . . .... ... .... ...106
5.5 Results of Fourier series appr with different sampling rate . . . . 107
5.6 Results of Gaussian interpolation with different variances . . . . .... ...107
5.7 The localization results after 1 iteration . . . .... .... ... .... ...108
5.8 The results after 2 iterations . . . .... .... ... .... ...108
5.9 The localization results after 4 . . . .... .... ... .... ...109
5.10 The results after 7 iterations . . . .... .... ... .... ...109
6.1 Network topology . . .... ... .... ... .... .... ... .... ...114
6.2 Synchronization messages in PTP protocol . .... .... ... .... ...115
6.3 System model and the propagation of PTP messages.... ... .... ...116