Algorithms for Complex Explanation Queries




Journal Title

Journal ISSN

Volume Title



Recently, there has been growing interest in developing machine learning systems that are robust to minor perturbations in input and are explainable in that they are able explain why they made a particular decision to a user. In this dissertation, we focus on a widely used graph-based probabilistic representation called probabilistic graphical models (PGMs) and propose a new unified constrained optimization task called constrained most probable explanation (CMPE) problem over them. We show that in addition to the two aforementioned tasks, making models robust and explainable, many real-world tasks over PGMs can be reduced to CMPE. We thoroughly analyze the computational complexity of CMPE and develop specialized, practical algorithms for solving it. Specifically, we show that CMPE is strongly NP-hard in general and thus unlikely to admit an efficient, polynomial time algorithm. However, it is only weakly NP-hard when the PGM exhibits certain structural properties such as small k-separators. To solve CMPE and upper bound its optimal value, we present novel efficient approaches that combine graph-based partitioning techniques with approximation algorithms developed in literature on the multiple choice knapsack problem (MCKP), number partitioning problem and subset sum problem (SSP). We derive approximation and complexity guarantees for our new algorithms and demonstrate via a large scale experimental evaluation on several benchmark graphical models that compared to baselines such as random sampling and local search, our new algorithms are more accurate. We also encode CMPE as a mixed integer linear program (MILP) and show that our approach is superior to open-source MILP solvers such as SCIP.



Computer Science, Artificial Intelligence