Applying the information bottleneck to statistical relational learning

Fabrizio Riguzzi, Nicola Di MauroMachine Learning 2012 · DOI · OpenReview

Introduction

Statistical Relational Learning (SRL) aims to model complex domains characterized by both uncertainty and relational structure. Models like Logic Programs with Annotated Disjunction (LPADs) are often used to represent these domains, typically by mapping them to Bayesian Networks. However, learning parameters for these models is challenging when data is incomplete or contains hidden variables. The standard Expectation-Maximization (EM) algorithm frequently converges to local optima due to the non-convex nature of the likelihood landscape in the presence of latent variables.

The Relational Information Bottleneck (RIB)

To address these limitations, this work introduces the Relational Information Bottleneck (RIB). RIB adapts the Information Bottleneck (IB) principle—originally developed for signal processing—to the relational setting. The core idea is to treat parameter learning as a trade-off between data compression and information preservation.

The multivariate information bottleneck framework defined by input graph G_in and output graph G_out.

In this framework, the algorithm seeks to find a representation T that compresses the input variables X while retaining maximum information about a target variable Y. As shown in the figure above, G_in represents the encoding process, while G_out represents the decoding or predictive process.

Deterministic Annealing and Landscape Smoothing

A key advantage of RIB is its use of deterministic annealing. By introducing a Lagrange multiplier \gamma (analogous to temperature in physical systems), the algorithm can control the complexity of the optimization landscape.

Comparison of the smooth "easy" optimization landscape at low \gamma versus the complex, multi-modal "EM" landscape.

At low values of \gamma, the objective function is highly smoothed, making the global optimum easy to locate. As \gamma is gradually increased, the landscape becomes more detailed, eventually matching the original log-likelihood surface. This process allows RIB to "track" the global optimum and avoid the local traps that hinder standard EM.

Relational Considerations

RIB is specifically tailored for relational data through parameter tying. In relational models, multiple ground instances of the same rule must share the same probability parameters. RIB incorporates these constraints directly into its optimization steps. Furthermore, the authors demonstrate that the necessary derivatives for optimization can be computed without full inference over the entire grounded Bayesian network, significantly reducing the computational burden of the "E-step."

Experimental Results

The RIB algorithm was evaluated against state-of-the-art methods like Alchemy (Markov Logic Networks) and LeProbLog on several benchmarks:

  • Real-World Data: On the IMDB and Cora datasets, RIB achieved competitive or superior Area Under the Precision-Recall Curve (AUCPR) scores.
  • Synthetic Benchmarks: In tests on the "Shop" datasets with varying numbers of hidden atoms, RIB consistently outperformed EM. For the shop8 dataset, RIB's Mean Absolute Difference (MAD) from the true parameters was nearly six times lower than that of EM, demonstrating its robustness against local maxima.

Conclusion and Future Work

The Relational Information Bottleneck provides a principled approach to learning in complex relational domains with hidden variables. By leveraging deterministic annealing, it successfully bypasses the local optima that plague traditional likelihood-based methods. Future research directions include developing "lifted" versions of RIB to improve scalability by operating directly on relational templates and extending the framework to handle cyclic dependencies.

Summary updated

Abstract

In this paper we propose to apply the Information Bottleneck (IB) approach to the sub-class of Statistical Relational Learning (SRL) languages that are reducible to Bayesian networks. When the resulting networks involve hidden variables, learning these languages requires the use of techniques for learning from incomplete data such as the Expectation Maximization (EM) algorithm. Recently, the IB approach was shown to be able to avoid some of the local maxima in which EM can get trapped when learning with hidden variables. Here we present the algorithm Relational Information Bottleneck (RIB) that learns the parameters of SRL languages reducible to Bayesian Networks. In particular, we present the specialization of RIB to a language belonging to the family of languages based on the distribution semantics, Logic Programs with Annotated Disjunction (LPADs). This language is prototypical for such a family and its equivalent Bayesian networks contain hidden variables. RIB is evaluated on the IMDB, Cora and artificial datasets and compared with LeProbLog, EM, Alchemy and PRISM. The experimental results show that RIB has good performances especially when some logical atoms are unobserved. Moreover, it is particularly suitable when learning from interpretations that share the same Herbrand base.
BibTeX
@article{riguzzi2012applying,
  author = {Fabrizio Riguzzi and Nicola Di Mauro},
  title = {{Applying the information bottleneck to statistical relational learning}},
  journal = {Machine Learning},
  year = {2012},
  doi = {10.1007/s10994-011-5247-6},
}
Figure