Extended Lifted Inference with Joint Formulas

Udi Apsel, Ronen I. BrafmanUAI 2011

TL;DR

This paper introduces two novel operators, "joint formula conversion" and "just-different counting conversion," to extend the applicability of First-Order Variable Elimination (FOVE) for probabilistic inference in relational models. This allows for more efficient lifted inference in complex scenarios and enables the first lifted solution for decision-making under uncertainty using first-order influence diagrams.

What Problem Does This Paper Address?

Probabilistic graphical models are powerful for representing complex dependencies, but scaling them to real-world problems often requires dealing with relational data. First-Order Variable Elimination (FOVE) offers a way to perform "lifted inference" directly on these relational models, avoiding the computationally expensive step of grounding them into propositional models. However, existing FOVE operators have limitations, often forcing a fallback to propositional inference for certain model structures. This paper aims to overcome these limitations by introducing new operators that expand the range of problems amenable to efficient lifted inference and by extending lifted inference to decision-making under uncertainty in relational settings.

Methods

The paper introduces two primary novel techniques:

  • Joint Formula Conversion: This operator couples pairs of atomic formulas into a single "joint formula." This new formula's range is a Cartesian product of the original formulas' ranges. The key idea is that while efficient lifting operators might not apply to the individual formulas, they might apply to the combined joint formula. This effectively "prepares" the model for subsequent lifting operations that would otherwise be impossible.
  • Just-Different Counting Conversion: This is a generalization of existing counting conversion operators. It specifically handles "just-different atoms," which are atoms where the assignment of one variable restricts the assignment of another in a specific, non-arbitrary way. This allows for more efficient counting operations in scenarios involving such dependencies.

These new operators are integrated into the existing FOVE framework, enabling lifted inference for a broader class of models. Furthermore, the paper adapts these techniques to solve Maximum Expected Utility (MEU) queries in first-order influence diagrams, providing the first lifted solution for this problem.

Datasets

Not discussed in the paper. The paper focuses on algorithmic contributions and evaluates them on synthetic models.

Key Insights and Ideas

  • Dependencies can be beneficial for lifting: Counter-intuitively, introducing dependencies (via joint formulas) can enable the application of lifting operators that would otherwise be inapplicable, leading to significant computational gains.
  • Bridging the gap to decision theory: The paper successfully extends lifted inference from pure probabilistic reasoning to decision-making under uncertainty (MEU), a crucial step for applying these techniques to real-world planning and decision problems.
  • Generalization is key: The "just-different counting conversion" generalizes existing methods, showing a path towards more comprehensive lifted inference capabilities.
  • Lifted MEU is a generalization: The authors highlight that MPE and belief assessment are special cases of MEU, suggesting that their lifted MEU framework could potentially encompass other lifted inference tasks.

Key Results

The paper demonstrates significant speedups over propositional inference methods through experimental evaluations on various models. For instance, in Figure 3, introducing joint formulas transforms an intractable propositional inference problem into a quickly solvable lifted one. Figure 4 and 5 show that lifted MEU computation scales polynomially with domain size, whereas propositional MEU scales exponentially, highlighting the practical advantage of their approach. The authors claim their lifted MEU solution is the first of its kind.

Limitations and Future Work

  • Heuristics for operator selection: While the paper presents new operators, the optimal strategy for deciding when to apply them within a larger inference process (especially in the context of a greedy algorithm) is still an area for further research.
  • Generalization of joint formulas: The paper focuses on pairs of formulas for joint conversion. Extending this to larger sets of formulas could unlock further lifting opportunities.
  • Broader applicability: The authors suggest that the notion of joint formulas is generic and could be adopted by other relational models, such as relational MDPs, indicating a promising avenue for future work.
  • Lifted MAP estimation: The paper posits that lifted MAP estimation can be defined as a private case of lifted MEU, suggesting this as a potential future application of their framework.

Summary updated

BibTeX
@inproceedings{apsel2011extended,
  author = {Udi Apsel and Ronen I. Brafman},
  title = {{Extended Lifted Inference with Joint Formulas}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}

Loading related content...

Figure