Applications of the Multi-Constraint Most Probable Explanation Problem

Journal Title
Journal ISSN
Volume Title

Probabilistic models are often used in practice to represent and reason about uncertainty. A key reasoning task over them is finding the most probable assignment to all the unobserved variables given observations. This task called the most probable explanation (MPE) task has several applications including finding the most likely (1) topic for a given document, (2) disease given symptoms and (3) price of gold tomorrow given historical gold prices. In this thesis, we consider a multi-constrained version of the MPE task (MCMPE) which is defined as the task of computing the most probable explanation given a set of userspecified constraints. We demonstrate three possible real-world applications of MCMPE. Our first application is about finding the most probable completion of an image under the constraint that the label assigned to the image is either flipped or remains the same. Our second application is about discovering possible adversarial attacks and involves minimally modifying an image/example such that the decision made by the classifier changes. Our final application is about estimating the robustness of a probabilistic classifier. We propose solving the MCMPE task by encoding it as a mixed linear integer programming task and using an open-source solver such as SCIP for solving the latter. We demonstrate empirically the feasibility and practicality of our proposed approach as well as its applicability on the MNIST digits and the SMS Spam Filtering datasets.

Artificial intelligence, Machine learning, Robust control, Probabilities