Somdeb Sarkhel
Published: 2016
Total Pages:
Get eBook
This dissertation focuses on Markov logic networks (MLNs), a knowledge representation tool that elegantly unifies first-order logic (FOL) and probabilistic graphical models (PGMs). FOL enables compact representation while probability allows the user to model uncertainty in a principled manner. Unfortunately, although the representation is compact, inference in MLNs is quite challenging, as PGMs generated from MLNs typically have millions of random variables and features. As a result, even linear time algorithms are computationally infeasible. Recently, there has been burgeoning interest in developing "lifted" algorithms to scale up inference in MLNs. These algorithms exploit symmetries in the PGM associated with an MLN, detecting them in many cases by analyzing the first-order structure without constructing the PGM, and thus have time and space requirements that are sub-linear when symmetries are present and can be detected. However, previous research has focused primarily on lifted marginal inference while algorithms for optimization tasks such as maximum-a-posteriori (MAP) inference are far less advanced. This dissertation fills this void, by developing next generation algorithms for MAP inference. This dissertation presents several novel, scalable algorithms for MAP inference in MLNs. The new algorithms exploit both exact and approximate symmetries, and experimentally are orders of magnitude faster than existing algorithms on a wide variety of real-world MLNs. Specifically, this dissertation makes the following contributions: A key issue with existing lifted approaches is that one has to make substantial modifications to highly engineered, well-researched inference algorithms and software, developed in the PGM community over the last few decades. We address this problem by developing the ``lifting as pre-processing'' paradigm, where we show that lifted inference can be reduced to a series of pre-processing operations that compresses a large PGM to a much smaller PGM. Another problem with current lifted algorithms is that they only exploit exact symmetries. In many real-world problems, very few exact symmetries are present while approximate symmetries are abundant. We address this limitation by developing a general framework for exploiting approximate symmetries that elegantly trades solution quality with time and space complexity. Inference and weight learning algorithms for MLNs need to solve complex combinatorial counting problems. We propose a novel approach for formulating and efficiently solving these problems. We scale-up two approximate inference algorithms, Gibbs sampling and MaxWalkSAT and three weight learning algorithms, Contrastive Divergence, Voted Perceptron, and, Pseudo-log-likelihood learning. We propose novel approximate inference algorithms for accurate, scalable inference in PGMs having shared sub-structures but no shared parameters. We demonstrate both theoretically and experimentally that they outperform state-of-the-art approaches.