Lifted Junction Tree Algorithm

We look at probabilistic first-order formalisms where the domain objects are known. In these formalisms, the standard approach for inference with first-order constructs include lifted variable elimination (LVE) for single queries. To handle multiple queries efficiently, the junction tree algorithm takes advantage of the underlying knowledge base being constant. To benefit from these advantages in the first-order setting, we transfer the idea of lifting to the junction tree algorithm and introduce the lifted junction tree algorithm (LJT). It aims at reducing computations by introducing a first-order cluster representation of a knowledge base, called first-order junction trees, which compactly represents symmetries, and using LVE in its computations.

So far, we have extended the original LJT

  • to include the lifting tool of counting to lift even more computations, 
  • to identify and prevent unnecessary groundings,
  • to effectively handle evidence in a lifted manner, and
  • to answer conjunctive queries.

We also work on a dynamic version of LJT (LDJT) to handle sequential data, e.g., in the form of time series. For more information, please refer to LDJT. We further apply the lifting idea to extend LVE, LJT, and LDJT

  • to compute a most probable explanation (also known as total abduction), including safe MAP queries (partial abduction),
  • to answer parameterised queries for a lifted query answering, and
  • to compute a maximum expected utility.

Given multiple queries, e.g., in machine learning applications, our approach enables us to compute answers faster than existing approaches tailored for single queries and the propositional algorithms.

Publikationen

2018

  • Marcel Gehrke, Tanya Braun, Ralf Möller: Towards Preventing Unnecessary Groundings in the Lifted Dynamic Junction Tree Algorithm
    wird veröffentlicht in: Proceedings of KI 2018: Advances in Artificial Intelligence, 2018, Springer
    BibTeX
  • Tanya Braun, Ralf Möller: Fusing First-order Knowledge Compilation and the Lifted Junction Tree Algorithm
    wird veröffentlicht in: Proceedings of KI 2018: Advances in Artificial Intelligence, 2018, Springer
    BibTeX
  • Tanya Braun, Ralf Möller: Parameterised Queries and Lifted Query Answering
    in: Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018
    BibTeX
  • Tanya Braun, Ralf Möller: Fusing First-order Knowledge Compilation and the Lifted Junction Tree Algorithm
    in: 8th International Workshop on Statistical Relational AI, 2018
    BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Preventing Unnecessary Groundings in the Lifted Dynamic Junction Tree Algorithm
    in: 8th International Workshop on Statistical Relational AI, 2018
    BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Answering Hindsight Queries with Lifted Dynamic Junction Trees
    in: 8th International Workshop on Statistical Relational AI, 2018
    BibTeX:
    @inproceedings{GehBrMo18b,
      author = {Marcel Gehrke and Tanya Braun and Ralf M\"oller}, 
      title = {{Answering Hindsight Queries with Lifted Dynamic Junction Trees}}, 
      booktitle = {8th International Workshop on Statistical Relational AI}, 
      year = {2018}
    }
  • Marcel Gehrke, Tanya Braun, Ralf Möller, Alexander Waschkau, Christoph Strumann, Jost Steinhäuser: Towards Lifted Maximum Expected Utility
    in: Proceedings of the Joint Workshop on Artificial Intelligence in Health in Conjunction with the 27th IJCAI, the 23rd ECAI, the 17th AAMAS, and the 35th ICML, 2018, Springer
    BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Lifted Dynamic Junction Tree Algorithm
    in: Proceedings of the International Conference on Conceptual Structures, 2018, Springer, p.55-69
    BibTeX
  • Tanya Braun, Ralf Möller: Lifted Most Probable Explanation
    in: Proceedings of the International Conference on Conceptual Structures, 2018, Springer, p.39-54,
    BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller, Alexander Waschkau, Christoph Strumann, Jost Steinhäuser: Towards Lifted Maximum Expected Utility
    IFIS, Universität zu Lübeck, 2018, Technical Report
    BibTeX
  • Tanya Braun, Ralf Möller: Counting and Conjunctive Queries in the Lifted Junction Tree Algorithm - Extended Version
    in: Postproceedings of the 5th International Workshop on Graph Structures for Knowledge Representation and Reasoning, 2018, Springer
    DOI BibTeX
nach oben

2017

  • Tanya Braun, Ralf Möller: Preventing Groundings and Handling Evidence in the Lifted Junction Tree Algorithm
    in: KI 2017: Advances in Artificial Intelligence. KI 2017 - 40th Annual German Conference on AI, Dortmund, Germany, September 25-29, 2017, 2017, Springer, LNCS, Vol.10505, p.85-98
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Counting and Conjunctive Queries in the Lifted Junction Tree Algorithm
    in: Graph Structures for Knowledge Representation and Reasoning - 5th International Workshop (GKR 2017), Melbourne, Australia, 2017, 21. August
    Website BibTeX
nach oben

2016

  • Tanya Braun, Ralf Möller: Lifted Junction Tree Algorithm
    in: KI 2016: Advances in Artificial Intelligence - 39th Annual German Conference on AI, Klagenfurt, Austria, September 26-30, 2016, 2016, Gerhard Friedrich, Malte Helmert, Franz Wotawa (Ed.), Springer, Lecture Notes in Computer Science, Vol.9904, p.30-42
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Lifted Junction Tree Algorithm
    IFIS, Universität zu Lübeck, 2016, Long version of the KI 2016 conference paper
    BibTeX
nach oben