Asymptotic elimination of partially continuous aggregation functions in directed graphical models

DOI10.1016/J.IC.2023.105061MaRDI QIDQ6116192zbMATH OpenFDO

Authors Vera Koponen

Publication date 17 July 2023

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2106.10122

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In Statistical Relational Artificial Intelligence, a branch of AI and machine learning which combines the logical and statistical schools of AI, one uses the concept {em para-metrized probabilistic graphical model (PPGM)} to model (conditional) dependencies between random variables and to make probabilistic inferences about events on a space of "possible worlds". The set of possible worlds with underlying domain $D$ (a set of objects) can be represented by the set $mathbf{W}_D$ of all first-order structures (for a suitable signature) with domain $D$. Using a formal logic we can describe events on $mathbf{W}_D$. By combining a logic and a PPGM we can also define a probability distribution $mathbb{P}_D$ on $mathbf{W}_D$ and use it to compute the probability of an event. We consider a logic, denoted $PLA$, with truth values in the unit interval, which uses aggregation functions, such as arithmetic mean, geometric mean, maximum and minimum instead of quantifiers. However we face the problem of computational efficiency and this problem is an obstacle to the wider use of methods from Statistical Relational AI in practical applications. We address this problem by proving that the described probability will, under certain assumptions on the PPGM and the sentence $varphi$, converge as the size of $D$ tends to infinity. The convergence result is obtained by showing that every formula $varphi(x_1,ldots,x_k)$ which contains only "admissible" aggregation functions (e.g. arithmetic and geometric mean, max and min) is asymptotically equivalent to a formula $psi(x_1,ldots,x_k)$ without aggregation functions.

Cites work

• An analysis of first-order logics of probability
• An introduction to many-valued and fuzzy logic. Semantics, algebras, and derivation systems
• Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination
• Elements of finite model theory.
• Graphical models. Methods for data analysis and mining
• scientific article; zbMATH DE number 5296741 (Why is no real title available?)
• scientific article; zbMATH DE number 1392295 (Why is no real title available?)
• INDEMICS: an interactive high-performance computing framework for data-intensive epidemic modeling
• Lifted graphical models: a survey
• Probabilistic (logic) programming concepts
• Statistical relational artificial intelligence: logic, probability, and computation
• The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
• Zero-One Laws for Sparse Random Graphs

Cited in

(7)

• Inference With Aggregate Data in Probabilistic Graphical Models: An Optimal Transport Approach
• Random expansions of finite structures with bounded degree
• Probability logic and statistical relational artificial intelligence
• Random expansions of trees with bounded height
• On the relative asymptotic expressivity of inference frameworks
• A general approach to asymptotic elimination of aggregation functions and generalized quantifiers
• A convergence law for continuous logic and continuous structures with finite domains

This page was built for publication: Asymptotic elimination of partially continuous aggregation functions in directed graphical models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116192)