University of Illinois – Urbana-Champaign
Bean, Andrew J.
Message passing algorithms - methods and applications.
Degree: PhD, Electrical & Computer Engr, 2015, University of Illinois – Urbana-Champaign
Algorithms on graphs are used extensively in many applications and research areas. Such applications include machine learning, artificial intelligence, communications, image processing, state tracking, sensor networks, sensor fusion, distributed cooperative estimation, and distributed computation. Among the types of algorithms that employ some kind of message passing over the connections in a graph, the work in this dissertation will consider belief propagation and gossip consensus algorithms.
We begin by considering the marginalization problem on factor graphs, which is often solved or approximated with Sum-Product belief propagation (BP) over the edges of the factor graph. For the case of sensor networks, where the conservation of energy is of critical importance and communication overhead can quickly drain this valuable resource, we present techniques for specifically addressing the needs of this low power scenario. We create a number of alternatives to Sum-Product BP. The first of these is a generalization of Stochastic BP with reduced setup time. We then present Projected BP, where a subset of elements from each message is transmitted between nodes, and computational savings are realized in proportion to the reduction in size of the transmitted messages. Zoom BP is a derivative of Projected BP that focuses particularly on utilizing low bandwidth discrete channels. We give the results of experiments that show the practical advantages of our alternatives to Sum-Product BP.
We then proceed with an application of Sum-Product BP in sequential investment. We combine various insights from universal portfolios research in order to construct more sophisticated algorithms that take into account transaction costs. In particular, we use the insights of Blum and Kalai's transaction costs algorithm to take these costs into account in Cover and Ordentlich's side information portfolio and Kozat and Singer's switching portfolio. This involves carefully designing a set of causal portfolio strategies and computing a convex combination of these according to a carefully designed distribution. Universal (sublinear regret) performance bounds for each of these portfolios show that the algorithms asymptotically achieve the wealth of the best strategy from the corresponding portfolio strategy set, to first order in the exponent. The Sum-Product algorithm on factor graph representations of the universal investment algorithms provides computationally tractable approximations to the investment strategies. Finally, we present results of simulations of our algorithms and compare them to other portfolios.
We then turn our attention to gossip consensus and distributed estimation algorithms. Specifically, we consider the problem of estimating the parameters in a model of an agent's observations when it is known that the population as a whole is partitioned into a number of subpopulations, each of which has model parameters that are common among the member agents. We develop a method for determining the beneficial communication links in…
Advisors/Committee Members: Singer, Andrew C. (advisor), Singer, Andrew C. (Committee Chair), Grover, Pulkit (committee member), Raginsky, Maxim (committee member), Shanbhag, Naresh R. (committee member).
Subjects/Keywords: probabilistic graphical models; approximate inference; universal portfolios; message passing; analog to digital converters (ADC)
to Zotero / EndNote / Reference
APA (6th Edition):
Bean, A. J. (2015). Message passing algorithms - methods and applications. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/78397
Chicago Manual of Style (16th Edition):
Bean, Andrew J. “Message passing algorithms - methods and applications.” 2015. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed December 06, 2019.
MLA Handbook (7th Edition):
Bean, Andrew J. “Message passing algorithms - methods and applications.” 2015. Web. 06 Dec 2019.
Bean AJ. Message passing algorithms - methods and applications. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2015. [cited 2019 Dec 06].
Available from: http://hdl.handle.net/2142/78397.
Council of Science Editors:
Bean AJ. Message passing algorithms - methods and applications. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2015. Available from: http://hdl.handle.net/2142/78397