Graphical models and message-passing algorithms for network-constrained decision problems
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://dspace.mit.edu/handle/1721.1/43061 http://hdl.handle.net/1721.1/43061 |
| _version_ | 1826198773708095488 |
|---|---|
| author | Kreidl, O. Patrick |
| author2 | Alan S. Willsky. |
| author_facet | Alan S. Willsky. Kreidl, O. Patrick |
| author_sort | Kreidl, O. Patrick |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T11:09:34Z |
| format | Thesis |
| id | mit-1721.1/43061 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:09:34Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/430612019-04-12T14:37:38Z Graphical models and message-passing algorithms for network-constrained decision problems Kreidl, O. Patrick Alan S. Willsky. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Includes bibliographical references (p. [201]-210). Inference problems, typically posed as the computation of summarizing statistics (e.g., marginals, modes, means, likelihoods), arise in a variety of scientific fields and engineering applications. Probabilistic graphical models provide a scalable framework for developing efficient inference methods, such as message-passing algorithms that exploit the conditional independencies encoded by the given graph. Conceptually, this framework extends naturally to a distributed network setting: by associating to each node and edge in the graph a distinct sensor and communication link, respectively, the iterative message-passing algorithms are equivalent to a sequence of purely-local computations and nearest-neighbor communications. Practically, modern sensor networks can also involve distributed resource constraints beyond those satisfied by existing message-passing algorithms, including e.g., a fixed small number of iterations, the presence of low-rate or unreliable links, or a communication topology that differs from the probabilistic graph. The principal focus of this thesis is to augment the optimization problems from which existing message-passing algorithms are derived, explicitly taking into account that there may be decision-driven processing objectives as well as constraints or costs on available network resources. The resulting problems continue to be NP-hard, in general, but under certain conditions become amenable to an established team-theoretic relaxation technique by which a new class of efficient message-passing algorithms can be derived. From the academic perspective, this thesis marks the intersection of two lines of active research, namely approximate inference methods for graphical models and decentralized Bayesian methods for multi-sensor detection. (cont)The respective primary contributions are new message-passing algorithms for (i) "online" measurement processing in which global decision performance degrades gracefully as network constraints become arbitrarily severe and for (ii) "offline" strategy optimization that remain tractable in a larger class of detection objectives and network constraints than previously considered. From the engineering perspective, the analysis and results of this thesis both expose fundamental issues in distributed sensor systems and advance the development of so-called "self-organizing fusion-layer" protocols compatible with emerging concepts in ad-hoc wireless networking. by O. Patrick Kreidl. Ph.D. 2009-07-01T16:53:08Z 2009-07-01T16:53:08Z 2008 2008 Thesis http://dspace.mit.edu/handle/1721.1/43061 http://hdl.handle.net/1721.1/43061 244102978 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/43061 http://dspace.mit.edu/handle/1721.1/7582 210 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kreidl, O. Patrick Graphical models and message-passing algorithms for network-constrained decision problems |
| title | Graphical models and message-passing algorithms for network-constrained decision problems |
| title_full | Graphical models and message-passing algorithms for network-constrained decision problems |
| title_fullStr | Graphical models and message-passing algorithms for network-constrained decision problems |
| title_full_unstemmed | Graphical models and message-passing algorithms for network-constrained decision problems |
| title_short | Graphical models and message-passing algorithms for network-constrained decision problems |
| title_sort | graphical models and message passing algorithms for network constrained decision problems |
| topic | Electrical Engineering and Computer Science. |
| url | http://dspace.mit.edu/handle/1721.1/43061 http://hdl.handle.net/1721.1/43061 |
| work_keys_str_mv | AT kreidlopatrick graphicalmodelsandmessagepassingalgorithmsfornetworkconstraineddecisionproblems |