Hybrid Markov Logic Networks

Jue Wang, Pedro M. DomingosAAAI 2008

Introduction

In the real world, data is rarely independent and identically distributed (i.i.d.). In complex environments like robotics, objects share intricate relationships—walls connect to other walls, and doors are situated within them. Traditionally, modeling such environments required a choice between relational models like Markov Logic Networks (MLNs), which handle discrete logic but struggle with continuous values, and Hybrid Bayesian Networks, which handle continuous data but often assume independence. Hybrid Markov Logic Networks (HMLNs) bridge this gap, providing a unified framework for joint reasoning over discrete categories and continuous measurements.

The HMLN Framework

HMLNs extend the log-linear representation of MLNs by allowing features to be either Boolean logic formulas or numeric terms. This flexibility allows the model to incorporate standard statistical distributions through clever shorthands:

  • Soft Equality: Represented as a squared difference, enabling the modeling of Gaussian (Normal) distributions.
  • Soft Inequality: Implemented via sigmoid functions to represent "fuzzy" logic constraints, such as "the distance should be roughly greater than $t$."

Inference Algorithms

The authors introduced two primary algorithms to handle the unique challenges of HMLNs:

  1. Hybrid MaxWalkSAT (HMWS): Designed for finding the most likely state (MPE inference). It alternates between MaxWalkSAT for discrete bit-flipping and L-BFGS for continuous numerical optimization, "wiggling" continuous values to find the peak probability.
  2. Hybrid MC-SAT (HMCS): A probabilistic inference algorithm that utilizes slice sampling to navigate the search space efficiently, extending the standard MC-SAT approach to hybrid domains.

Experimental Evaluation

The framework was evaluated on indoor map-building tasks using mobile robot sensor data from the Radish repository. The goal was to simultaneously classify segments (Wall, Door, Other), cluster them, and perform regression to determine exact coordinates.

MPE Performance

HMWS demonstrated significant efficiency gains over traditional methods like Simulated Annealing (SA). As shown in Figure 1, HMWS converges to a low Mean Square Error (MSE) orders of magnitude faster than SA, achieving superior accuracy in a fraction of the time.

HMWS vs SA: Mean Square Error over time for MPE inference.

Probabilistic Inference

For calculating marginal probabilities, HMCS significantly outperformed standard baselines such as Gibbs sampling and Simulated Tempering (ST). These traditional samplers often struggle with the complex constraints of relational spaces, whereas HMCS maintains high F1 scores for both segment classification and part-of relationships.

HMCS vs Baselines: F1 scores for probabilistic inference over time.

Key Insights and Results

The primary advantage of HMLNs lies in joint inference. By solving classification and regression simultaneously, the model can use the quality of a geometric fit (e.g., how well points fit a line) to inform categorical labels (e.g., identifying a "Wall"). This synergy leads to higher accuracy than pipelined approaches; in the robot mapping task, the HMLN achieved an MSE of 0.002 for wall positions, compared to 0.037 for a sequential baseline.

Conclusion

HMLNs represent a significant step forward in relational modeling by enabling joint inference across discrete and continuous variables. By combining combinatorial search with gradient-based optimization, HMLNs achieve superior accuracy and speed compared to pipelined or purely discrete approaches. Future work includes automating the discovery of logic formulas (structure learning) and scaling to even larger continuous domains.

Summary updated

BibTeX
@inproceedings{wang2008hybrid,
  author = {Jue Wang and Pedro M. Domingos},
  title = {{Hybrid Markov Logic Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure