File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: On convergence and accuracy of Gaussian belief propagation

TitleOn convergence and accuracy of Gaussian belief propagation
Authors
Issue Date2014
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Su, Q. [蘇勤亮]. (2014). On convergence and accuracy of Gaussian belief propagation. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5351001
AbstractGaussian belief propagation (BP) is known to be an efficient message-passing algorithm for calculating approximate marginal probability density function (PDF) from a high dimensional Gaussian PDF. When Gaussian BP converges, it is known that the mean calculated by Gaussian BP (Gaussian BP mean) is the mean of exact marginal PDF, while the variance calculated by Gaussian BP (Gaussian BP variance) is an approximation to the variance of exact marginal PDF. Since Gaussian BP is not guaranteed to converge, it is important to know under what conditions Gaussian BP converges. Moreover, due to the unknown accuracy of Gaussian BP variance, it is also meaningful to analyze and improve its accuracy. In this thesis, the issues of convergence and accuracy in Gaussian BP are focused on. First, the convergence condition of Gaussian BP variances is investigated. In particular, by analyzing the message updating functions of Gaussian BP, the necessary and sufficient convergence condition of Gaussian BP variances is derived under both synchronous and asynchronous schedulings. The relationship between the proposed convergence condition and the existing one is also established analytically. Comparing to the existing best convergence condition which is sufficient only and requires computing the spectral radius of an infinite dimensional matrix, the proposed condition not only fills in the necessary part of the existing condition, but also can be verified efficiently. Next, based on the convergence condition of Gaussian BP variances, the necessary and sufficient convergence conditions of beliefs (parameterized by Gaussian BP variance and mean) are derived in the scenarios of synchronous scheduling with or without damping. The results theoretically confirm the extensively reported conjecture that damping is helpful to improve the convergence of Gaussian BP. Under asynchronous scheduling, a sufficient convergence condition of beliefs is also derived. Relationships between the proposed convergence conditions and existing ones are established analytically, demonstrating that the existing conditions are implied by the proposed ones. Finally, the accuracy of Gaussian BP variances is analyzed and improved. In particular, an explicit error expression of Gaussian BP variances is first derived. By novel representation of this error expression, a distributed message-passing algorithm is proposed to improve the accuracy of Gaussian BP variance. It is proved that the upper bound of the residual error in the improved variance monotonically decreases as the number of nodes in a particular set increases, and eventually vanishes to zero as the remaining graph becomes loop-free after removal of the selected nodes.
DegreeDoctor of Philosophy
SubjectComputer algorithms
Machine learning
Signal processing
Dept/ProgramElectrical and Electronic Engineering
Persistent Identifierhttp://hdl.handle.net/10722/221527

 

DC FieldValueLanguage
dc.contributor.authorSu, Qinliang-
dc.contributor.author蘇勤亮-
dc.date.accessioned2015-11-27T23:15:00Z-
dc.date.available2015-11-27T23:15:00Z-
dc.date.issued2014-
dc.identifier.citationSu, Q. [蘇勤亮]. (2014). On convergence and accuracy of Gaussian belief propagation. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5351001-
dc.identifier.urihttp://hdl.handle.net/10722/221527-
dc.description.abstractGaussian belief propagation (BP) is known to be an efficient message-passing algorithm for calculating approximate marginal probability density function (PDF) from a high dimensional Gaussian PDF. When Gaussian BP converges, it is known that the mean calculated by Gaussian BP (Gaussian BP mean) is the mean of exact marginal PDF, while the variance calculated by Gaussian BP (Gaussian BP variance) is an approximation to the variance of exact marginal PDF. Since Gaussian BP is not guaranteed to converge, it is important to know under what conditions Gaussian BP converges. Moreover, due to the unknown accuracy of Gaussian BP variance, it is also meaningful to analyze and improve its accuracy. In this thesis, the issues of convergence and accuracy in Gaussian BP are focused on. First, the convergence condition of Gaussian BP variances is investigated. In particular, by analyzing the message updating functions of Gaussian BP, the necessary and sufficient convergence condition of Gaussian BP variances is derived under both synchronous and asynchronous schedulings. The relationship between the proposed convergence condition and the existing one is also established analytically. Comparing to the existing best convergence condition which is sufficient only and requires computing the spectral radius of an infinite dimensional matrix, the proposed condition not only fills in the necessary part of the existing condition, but also can be verified efficiently. Next, based on the convergence condition of Gaussian BP variances, the necessary and sufficient convergence conditions of beliefs (parameterized by Gaussian BP variance and mean) are derived in the scenarios of synchronous scheduling with or without damping. The results theoretically confirm the extensively reported conjecture that damping is helpful to improve the convergence of Gaussian BP. Under asynchronous scheduling, a sufficient convergence condition of beliefs is also derived. Relationships between the proposed convergence conditions and existing ones are established analytically, demonstrating that the existing conditions are implied by the proposed ones. Finally, the accuracy of Gaussian BP variances is analyzed and improved. In particular, an explicit error expression of Gaussian BP variances is first derived. By novel representation of this error expression, a distributed message-passing algorithm is proposed to improve the accuracy of Gaussian BP variance. It is proved that the upper bound of the residual error in the improved variance monotonically decreases as the number of nodes in a particular set increases, and eventually vanishes to zero as the remaining graph becomes loop-free after removal of the selected nodes.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.subject.lcshComputer algorithms-
dc.subject.lcshMachine learning-
dc.subject.lcshSignal processing-
dc.titleOn convergence and accuracy of Gaussian belief propagation-
dc.typePG_Thesis-
dc.identifier.hkulb5351001-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineElectrical and Electronic Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5351001-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats