New Message Passing Methods for Min-Max and Sum-Product Inference
Christopher Srinivasa · TSpace (University of Toronto) · 2018
Message passing algorithms powered by the distributive law of mathematics are efficient in finding approximate solutions to NP-hard inference problems. This thesis proposes new message passing algorithms to enable and improve performance in two important modes of inference. First is min-max inference which seeks the assignment that minimizes the worse-case outcome. Examples include well known NP-hard combinatorial problems such as min-max clustering, the asymmetric K-center problem, K-packing, the bottleneck traveling salesman problem, and makespan minimization. Within min-max inference two algorithms are proposed. The first is Min-Max Propagation (MMP), a min-max version of Belief Propagation (BP) obtained by noting that min and max operators satisfy the distributive law. With MMP, it is shown that for any high-order function which can be minimized in O(ω), the message update can be computed using an efficient O(K(ω + log(K)) procedure, where K is the number of variables. The second algorithm reduces min-max inference to a sequence of Constraint Satisfaction Problems (CSPs). Both approaches perform well on NP-hard combinatorial problems. The second mode of interest is sum-product inference. Here, loopy BP performs poorly when the underlying mass contains multiple disjoint modes, capturing only one mode when it reaches a fixed point. As such, a message passing procedure that attempts to model all the fixed points of BP by defining a distribution over BP messages is considered; namely Survey Propagation (SP). Unfortunately SP is intractable beyond CSPs because, to perform general SP updates, one has to operate on distributions over a continuous domain. To efficiently extend the application of SP to marginalization in binary pairwise graphical models an approximation scheme is proposed. This scheme has O(DKlog(DK)τ ) complexity per iteration, where τ is the complexity of BP per iteration, D is the maximum node degree and K is a resolution constant controlling the approximations fidelity. Experiments show that this method can track many BP fixed points, achieving a high marginalization accuracy within a few iterations, in difficult settings where BP is often non-convergent and inaccurate.