# 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.*

More recently, we extended LVE and LJT to compute a *most probable explanation* (also known as total abduction), including safe MAP queries (partial abduction). There also exists 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.

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 version of the junction tree algorithm.

# Publikationen

### 2018

- Marcel Gehrke, Tanya Braun, Ralf Möller:
**Lifted Dynamic Junction Tree Algorithm**

wird veröffentlicht in: Proceedings of the International Conference on Conceptual Structures, 2018

- Tanya Braun, Ralf Möller:
**Lifted Most Probable Explanation**

wird veröffentlicht in: Proceedings of the International Conference on Conceptual Structures, 2018, Springer

- 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, GKR 2017, Melbourne, Australia, August 21, 2017, 2018, Springer

### 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

- 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

### 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

- Tanya Braun, Ralf Möller:
**Lifted Junction Tree Algorithm**

IFIS, Universität zu Lübeck, 2016,*Long version of the KI 2016 conference paper*

**:**@techreport{BrMoe2016, Author = {Tanya Braun and Ralf M\"oller}, Title = {{Lifted Junction Tree Algorithm}}, Year = {2016}, Institution = {IFIS, Universit{\"a}t zu L{\"u}beck}, Note = {Long version of the KI 2016 conference paper} }