Probabilistic Relational Models

Principle Investigator: Prof. Dr. Ralf Möller

Research Associate: Dr. Tanya Braun

A probabilistic relational model (PRM) or a relational probability model is a model in which the probabilities are specified on the relations, independently of the actual individuals. Different individuals share the probability parameters.

Lifted Junction Tree Algorithm

We look at probabilistic relational formalisms where the domain objects are known. In these formalisms, standard approaches for inference use lifted variable elimination (LVE) to answer single queries, which leads to inefficiencies for multiple queries. To answer multiple queries efficiently, the well-known junction tree algorithm builds a cluster representation of the underlying model for faster query answering. To benefit from the idea behind junction trees in the relational setting, we have transferred the concept of lifting to the junction tree algorithm, presenting the lifted junction tree algorithm (LJT). LJT saves computations using a compact first-order cluster representation and LVE as a subroutine in its computations.

While before either the number of known objects has proven to limit the junction tree algorithm or the number of queries lead to inefficient repetition for LVE, LJT allows for efficient repeated inference by incorporating relational aspects of a model as well as avoiding duplicate calculations. In many settings, LJT even outperforms FOKC, another well-known algorithm for exact repeated inference. FOKC stands for first-order knowledge compilation, which solves a weighted first-order model counting problem by building a first-order circuit, in which FOKC computes weighted model counts.

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 through an additional merging step called fusion,
  • to effectively handle evidence in a lifted manner, and
  • to answer conjunctive queries that span more than one cluster.

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 (compact form of a conjunctive query with isomorphic query terms) for a lifted query answering,
  • to handle uncertain evidence (observations of events with probability p < 1.0), and
  • to compute a maximum expected utility.

Not only LVE works as a subroutine. LJT allows for any inference algorithms as a subroutine as long as an algorithm fulfils certain requirements for evidence handling and message passing. The subroutine algorithm determines what type of queries LJT can answer. We have published a version of LJT that combines LVE and FOKC as subroutines into LJTKC.

Description of the Input Files for the JAIR Submission

Please find here a manuscript describing the input files used for the evaluation of LJT, LVE and FOKC as well as JT and VE:

Download the manuscript

Implementation

A prototype implementation of LJT based on BLOG and the LVE implementation by Taghipour as well as some documentation is available:

The web pages around the implementation have been prepared by Moritz Hoffmann.

Publikationen

2024

  • Malte Luttermann, Mattis Hartwig, Tanya Braun, Ralf Möller, Marcel Gehrke: Lifted Causal Inference in Relational Domains
    wird veröffentlicht in: Proceedings of the Third Conference on Causal Learning and Reasoning (CLeaR-24), 2024, PMLR
    BibTeX
  • Malte Luttermann, Tanya Braun, Ralf Möller, Marcel Gehrke: Colour Passing Revisited: Lifted Model Construction with Commutative Factors
    in: Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24), 2024, AAAI Press
    BibTeX
  • Magnus Bender, Tanya Braun, Ralf Möller, Marcel Gehrke: ReFrESH – Relation-preserving Feedback-reliant Enhancement of Subjective Content Descriptions
    in: 18th IEEE International Conference on Semantic Computing, (ICSC 2024), February 5-7, 2024, IEEE, p.17-24
    Website BibTeX
  • Magnus Bender, Tanya Braun, Ralf Möller, Marcel Gehrke: Unsupervised Estimation of Subjective Content Descriptions in an Information System
    in: International Journal of Semantic Computing, 2024, Vol.18, (1)
    DOI BibTeX
nach oben

2023

  • Magnus Bender, Tanya Braun, Ralf Möller, Marcel Gehrke: LESS is More: LEan Computing for Selective Summaries
    in: KI 2023: Advances in Artificial Intelligence, 2023, Springer Nature Switzerland, p.1-14
    Website BibTeX
  • Nadja Redzuan, Marcel Gehrke, Ralf Möller, Tanya Braun: On Domain-specific Topic Modelling Using the Case of a Humanities Journal
    in: Proceedings of the Workshop on Humanities-Centred Artificial Intelligence (CHAI 2023), , CEUR Workshop Proceedings
    BibTeX
  • Magnus Bender, Tanya Braun, Ralf Möller, Marcel Gehrke: Unsupervised Estimation of Subjective Content Descriptions
    in: 17th IEEE International Conference on Semantic Computing, (ICSC 2023), February 1-3, 2023, IEEE
    Website BibTeX
nach oben

2022

  • Marcel Gehrke, Ralf Möller, Tanya Braun: Who did it? Identifying the Most Likely Origins of Events
    in: Proceedings of the 11th International Conference on Probabilistic Graphical Models (PGM 2022), 2022, p.217-228
    Website BibTeX
  • Tanya Braun, Marcel Gehrke: Explainable and Explorable Decision Support
    in: Proceedings of the 27th International Conference on Conceptual Structures (ICCS 2022), Münster, Germany, September 12-15, 2022, 2022
    DOI Website BibTeX
  • Tanya Braun, Marcel Gehrke, Florian Lau, Ralf Möller: Lifting in Multi-agent Systems under Uncertainty
    in: 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022), Eindhoven, Netherlands, August 1-5, 2022, 2022
    Website BibTeX
  • Mareike Stender, Mattis Hartwig, Tanya Braun, Ralf Möller: Increasing State Estimation Accuracy in the Inference Algorithm on a Hybrid Factor Graph Model
    in: The 35. International FLAIRS Conference Proceedings, 2022, May
    Website BibTeX
  • Moritz Hoffmann, Tanya Braun, Ralf Möller: Lifted Division for Lifted Hugin Belief Propagation,
    in: AISTATS-22 Proceedings of the 25th International Conference on Artificial Intelligence and Statistics,, 2022,, PMLR, p.6501-6510
    Website BibTeX
nach oben

2021

  • Tanya Braun, Stefan Fischer, Florian Lau, Ralf Möller: Lifting DecPOMDPs for Nanoscale Systems -- A Work in Progress
    in: 10th International Workshop on Statistical Relational AI at the 1st International Joint Conference on Learning and Reasoning, 2021
    BibTeX
  • Florian Marwitz, Tanya Braun, Ralf Möller: A First Step Towards Even More Sparse Encodings of Probability Distributions
    in: ILP-21 Proceedings of the 30th International Conference on Inductive Logic Programming, 2021
    BibTeX
  • Tanya Braun, Marcel Gehrke, Tom Hanika, Nathalie Hernandez (Eds.): ICCS-21 Proceedings of the 26th International Conference on Conceptual Structures
    Springer, 2021
    DOI BibTeX
  • Mattis Hartwig, Tanya Braun, Ralf Möller: Handling Overlaps When Lifting Gaussian Bayesian Networks
    in: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), 2021, IJCAI Organization, Montreal, Kanada, p.4228-4234
    DOI BibTeX
  • Mareike Stender, Jan Graßhoff, Tanya Braun, Ralf Möller, Philipp Rostalski: A Hybrid Factor Graph Model for Biomedical Activity Detection
    in: IEEE EMBS - International Conference on Biomedical and Health Informatics (BHI 2021), Athens, Greece, July 27-30, 2021, 2021, IEEE, p.1-4
    DOI BibTeX
  • Nils Finke, Tanya Braun, Marcel Gehrke, Ralf Möller: Concept Drift Detection in Dynamic Probabilistic Relational Models
    in: The International FLAIRS Conference Proceedings, 2021, Vol.34
    DOI BibTeX
  • Nils Finke, Tanya Braun, Marcel Gehrke, Ralf Möller: Dynamic Domain Sizes in Temporal Probabilistic Relational Models
    in: The International FLAIRS Conference Proceedings, 2021, Vol.34
    DOI BibTeX
nach oben

2020

  • Günther Görz, Tanya Braun, Ute Schmid (Eds.): Handbuch der Künstlichen Intelligenz, 6. Auflage
    De Gruyter, 2020
    Website BibTeX
  • Nils Finke, Marcel Gehrke, Tanya Braun, Tristan Potten, Ralf Möller: Investigating Matureness of Probabilistic Graphical Models for Dry-Bulk Shipping
    in: Proceedings of the 10th International Conference on Probabilistic Graphical Models, 2020, 23-25 Sep, Manfred Jaeger, Thomas Dyhre Nielsen volu (Ed.), PMLR, Proceedings of Machine Learning Research, p.197-208
    DOI BibTeX
  • Tristan Potten, Tanya Braun: Benchmarking Inference Algorithms for Probabilistic Relational Models
    in: ICCS-20 Proceedings of the 25th International Conference on Conceptual Structures, 2020, Best Short Paper Award
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Simon Polovina: Restricting the Maximum Number of Actions for Decision Support under Uncertainty
    in: ICCS-20 Proceedings of the 25th International Conference on Conceptual Structures, 2020
    DOI BibTeX
  • Mehwish Alam, Tanya Braun, Bruno Yun (Eds.),: ICCS-20 Proceedings of the 25th International Conference on Conceptual Structures,
    Springer,, 2020,
    DOI BibTeX
  • Marcel Gehrke, Ralf Möller, Tanya Braun: Taming Reasoning in Temporal Probabilistic Relational Models
    in: Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020), 2020, p.2592 - 2599
    DOI BibTeX
  • Stefan Lüdtke, Marcel Gehrke, Tanya Braun, Ralf Möller, Thomas Kirste: Lifted Marginal Filtering for Asymmetric Models by Clustering-based Merging
    in: Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020), 2020
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Lifting Queries for Lifted Inference
    in: Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020), 2020
    DOI BibTeX
  • Tanya Braun,: Rescued from a Sea of Queries: Exact Inference in Probabilistic Relational Models,
    University of Lübeck,, 2020,, PhD thesis
    BibTeX
  • Tanya Braun, Ralf Möller: Exploring Unknown Universes in Probabilistic Relational Models
    in: 9th International Workshop on Statistical Relational AI at the 34th AAAI Conference on Artificial Intelligence, 2020, Springer International Publishing, Vol.abs/2001.02021, p.91–-103
    Website BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Taming Reasoning in Temporal Probabilistic Relational Models
    in: 9th International Workshop on Statistical Relational AI at the 34th AAAI Conference on Artificial Intelligence, 2020
    Website BibTeX
nach oben

2019

  • Marcel Gehrke, Tanya Braun, Ralf Möller: Efficient Multiple Query Answering in Switched Probabilistic Relational Models
    in: Proceedings of AI 2019: Advances in Artificial Intelligence, 2019, Springer, Lecture Notes in Computer Science, Vol.11919, p.104-116
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Exploring Unknown Universes in Probabilistic Relational Models
    in: Proceedings of AI 2019: Advances in Artificial Intelligence, 2019, Springer, p.91-103
    DOI BibTeX
  • Marcel Gehrke, Simon Schiff, Tanya Braun, Ralf Möller: Which Patient to Treat Next? Probabilistic Stream-based Reasoning for Decision Support and Monitoring
    in: Proceedings of the ICBK 2019, 2019, IEEE, p.73-80
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Lifted Temporal Most Probable Explanation
    in: Graph-Based Representation and Reasoning - 24th International Conference on Conceptual Structures, (ICCS 2019), Marburg, Germany, July 1-4,, 2019, Springer, Lecture Notes in Computer Science, Vol.11530, p.72-85
    DOI BibTeX
  • Tanya Braun, Marcel Gehrke: Inference in Statistical Relational AI
    in: Proceedings of the International Conference on Conceptual Structures 2019, 2019, Springer, p.xvii-xix
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Lifted Temporal Maximum Expected Utility
    in: Proceedings of the 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, 2019, Springer, p.380-386
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Uncertain Evidence for Probabilistic Relational Models
    in: Proceedings of the 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, 2019, Springer, Lecture Notes in Computer Science, Vol.11489, p.80-93
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Relational Forward Backward Algorithm for Multiple Queries
    in: Proceedings of the 32nd International Florida Artificial Intelligence Research Society Conference (FLAIRS-19), 2019, AAAI Press, p.464-469
    Website BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller, Alexander Waschkau, Christoph Strumann, Jost Steinhäuser: Lifted Maximum Expected Utility
    in: Artificial Intelligence in Health, 2019, Springer International Publishing, p.131-141
    DOI BibTeX
  • Tanya Braun: StaRAI or StaRDB? - A Tutorial on Statistical Relational AI
    in: BTW-19 Proceedings Datenbanksysteme für Business, Technologie und Web - Workshopband, 2019, Gesellschaft für Informatik, p.263-266
    DOI BibTeX
nach oben

2018

  • Marcel Gehrke, Tanya Braun, Ralf Möller: Answering Multiple Conjunctive Queries with the Lifted Dynamic Junction Tree Algorithm
    in: Proceedings of the AI 2018: Advances in Artificial Intelligence, 2018, Springer, p.543-555
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Preventing Unnecessary Groundings in the Lifted Dynamic Junction Tree Algorithm
    in: Proceedings of the AI 2018: Advances in Artificial Intelligence, 2018, Springer, p.556-562
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Adaptive Inference on Probabilistic Relational Models
    in: AI 2018: Advances in Artificial Intelligence, 2018, Springer, p.487-500
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Fusing First-order Knowledge Compilation and the Lifted Junction Tree Algorithm
    in: Proceedings of KI 2018: Advances in Artificial Intelligence, 2018, Springer, p.24-37
    DOI BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Towards Preventing Unnecessary Groundings in the Lifted Dynamic Junction Tree Algorithm
    in: Proceedings of KI 2018: Advances in Artificial Intelligence, 2018, Springer, p.38-45
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Parameterised Queries and Lifted Query Answering
    in: IJCAI-18 Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018, International Joint Conferences on Artificial Intelligence Organization, p.4980-4986
    DOI 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 at the 27th International Joint Conference on Artificial Intelligence, 2018
    Website 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 at the 27th International Joint Conference on Artificial Intelligence, 2018
    Website BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller: Answering Hindsight Queries with Lifted Dynamic Junction Trees
    in: 8th International Workshop on Statistical Relational AI at the 27th International Joint Conference on Artificial Intelligence, 2018
    Website BibTeX
  • Marcel Gehrke, Tanya Braun, Ralf Möller, Alexander Waschkau, Christoph Strumann, Jost Steinhäuser: Towards Lifted Maximum Expected Utility
    in: Proceedings of the First Joint Workshop on Artificial Intelligence in Health in Conjunction with the 27th IJCAI, the 23rd ECAI, the 17th AAMAS, and the 35th ICML, 2018, CEUR-WS.org, CEUR Workshop Proceedings, Vol.2142, p.93-96
    Website 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
    DOI BibTeX
  • Tanya Braun, Ralf Möller: Lifted Most Probable Explanation
    in: Proceedings of the International Conference on Conceptual Structures, 2018, Springer, p.39-54,
    DOI 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, p.54-72,
    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