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.
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.
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
shop8dataset, 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