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

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 19
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

¨ ¨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 ap