On MAP Inference of Ferromagnetic Potts Models and Nonsymmetric Determinantal Point Processes

Talla, Aravind Reddy

doi:https://doi.org/10.21985/n2-nxy1-9q33

Work

On MAP Inference of Ferromagnetic Potts Models and Nonsymmetric Determinantal Point Processes

Public

Download PDF

Download All Files (.zip)

In the Maximum-a-Posteriori (MAP) Inference problem, for any given probability distribution, the goal is to find the point in the support of that distribution with the highest probability. Potts models and Determinantal Point Processes (DPPs) are probabilistic models that were introduced in the context of statistical physics several decades ago. They have been extensively used in several computer science applications like computer vision, recommender systems, and document summarization. Exact MAP Inference in these models correspond to NP-hard combinatorial optimization problems and so approximate inference algorithms have been extensively studied. For MAP Inference in Ferromagnetic Potts models, we provide a strong justification for the excellent performance of a linear programming relaxation approach by going beyond worst-case analysis. For MAP Inference in Nonsymmetric Determinantal Point Processes, we provide the first one-pass streaming and online algorithms.

Creator