Approximate inference using DC programming for collective graphical models

• Main Authors: NGUYEN, Duc Thien, Akshat KUMAR, LAU, Hoong Chuin, SHELDON, Daniel
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: Approximate inference; Concave-convex procedure; Difference of convex functions; Entropy approximations; Generic optimization; Inference problem; Message passing algorithm; Optimization problems; Artificial Intelligence and Robotics; Computer Sciences; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3400; https://ink.library.smu.edu.sg/context/sis_research/article/4401/viewcontent/ApproximateInterference.pdf
• Institution: Singapore Management University

Collective graphical models (CGMs) provide a framework for reasoning about a population of independent and identically distributed individuals when only noisy and aggregate observations are given. Previous approaches for inference in CGMs work on a junction-tree representation, thereby highly limiting their scalability. To remedy this, we show how the Bethe entropy approximation naturally arises for the inference problem in CGMs. We reformulate the resulting optimization problem as a difference-of-convex functions program that can capture different types of CGM noise models. Using the concave-convex procedure, we then develop a scalable message-passing algorithm. Empirically, our approach is highly scalable and accurate for large graphs, more than an order-of-magnitude faster than a generic optimization solver, and is guaranteed to converge unlike the previous message-passing approach NLBP that fails in several loopy graphs.