2021/10/18 by Marcel Gehrke, Gehrke, Marcel
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Error Correcting Code Techniques #FOS: Computer and information sciences #Machine Learning and Algorithms #Topic Modeling
paper · pdf · doi:10.48550/arxiv.2110.09197
openalex publication_date 2021/10/18 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
For static lifted inference algorithms, completeness, i.e., domain\nliftability, is extensively studied. However, so far no domain liftability\nresults for temporal lifted inference algorithms exist. In this paper, we close\nthis gap. More precisely, we contribute the first completeness and complexity\nanalysis for a temporal lifted algorithm, the socalled lifted dynamic junction\ntree algorithm (LDJT), which is the only exact lifted temporal inference\nalgorithm out there. To handle temporal aspects efficiently, LDJT uses\nconditional independences to proceed in time, leading to restrictions w.r.t.\nelimination orders. We show that these restrictions influence the domain\nliftability results and show that one particular case while proceeding in time,\nhas to be excluded from FO12 . Additionally, for the complexity of LDJT, we\nprove that the lifted width is in even more cases smaller than the\ncorresponding treewidth in comparison to static inference.\n