Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm

The importance of aggregated count data, which is calculated from the data of\nmultiple individuals, continues to increase. Collective Graphical Model (CGM)\nis a probabilistic approach to the analysis of aggregated data. One of the most\nimportant operations in CGM is maximum a posteriori (MAP) inference of\nunobserved variables under given observations. Because the MAP inference\nproblem for general CGMs has been shown to be NP-hard, an approach that solves\nan approximate problem has been proposed. However, this approach has two major\ndrawbacks. First, the quality of the solution deteriorates when the values in\nthe count tables are small, because the approximation becomes inaccurate.\nSecond, since continuous relaxation is applied, the integrality constraints of\nthe output are violated. To resolve these problems, this paper proposes a new\nmethod for MAP inference for CGMs on path graphs. First we show that the MAP\ninference problem can be formulated as a (non-linear) minimum cost flow\nproblem. Then, we apply Difference of Convex Algorithm (DCA), which is a\ngeneral methodology to minimize a function represented as the sum of a convex\nfunction and a concave function. In our algorithm, important subroutines in DCA\ncan be efficiently calculated by minimum convex cost flow algorithms.\nExperiments show that the proposed method outputs higher quality solutions than\nthe conventional approach.\n