GIF-Projekt 1180/2011: Efficient Inference for Probabilistic Relational Models using Symmetries and Linear Programming Relaxations -

Link:

 

Description:

A key goal of modern computer science is to model complex, noisy domains such as language, images, social and semantic networks, among others. As more data becomes available, it becomes possible to consider more detailed and accurate models. Such models can then be used in a variety of important applications, from semantic analysis of texts to object recognition in images. To achieve this grand challenge, one needs to depart from the typical machine learning view of static feature representation, and consider complex, noisy relations between objects. The field of statistical relational learning (SRL) offers an elegant way to model and learn such models. Using SRL in practice, however, means solving inference problems in huge models. For example, say we know that some people in a social network are friends and some are smokers, how can we infer whether others are smokers and friends? For thousands of people this seems like a daunting computational task. However, such tasks often have strong symmetries (i.e.,repeated structures) that should intuitively translate into fewer computations. In recent years there has indeed been a growing interest in “lifting” algorithms, that use such symmetries. However, performing fast and accurate inference on SRLs is yet to become a reality. In this project, we propose a novel approach to designing “symmetry aware” algorithms, which we believe will significantly improve the capabilities of SRL models. We build on linear programming (LP) relaxations as the key underlying framework. LP relaxations have been proven very effective for inference in graphical models, largely due to their theoretical properties (e.g., optimality certificates), algorithmic elegance (availability of message passing algorithms), and empirical effectiveness. The underlying idea of the LP approach is to replace a difficult optimization problem with an LP that approximates it. However, despite the popularity of LP relaxations in the graphical models community, they have seen very little use within the SRL literature. In the project, we will develop the theory and algorithms needed for applying LPs to SRL, while making effective use of symmetries. Our approach will combine insights from the theory of LP relaxations, convex optimization, message passing and group theory. We expect it to result in new inference algorithms for SRL that exploit symmetries effectively, inherit the advantages of LP relaxations such as convergence guarantees, and scale to realistic models, thus having a significant impact on a wide range of fields, from computational biology to social network analysis. As part of the project, we will also apply our methods to challenging real world tasks, such as analysis of images using background world knowledge derived from text. Taken together, the project will result in a new framework for effective computation in structured domains, a better understanding of theoretical aspects of symmetry in computation, and the ability to construct detailed structured models from large amounts of data in multiple applied domains.

Partners:

 

Staff Members:

Kersting, Kristian
Mladenov, Martin

Software:

 

Publications: