First-Order Model Counting and Sampling

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=JU3RTdzlBQE


Duration: 37:24
270 views
5

Ondrej Kuzelka (Prague University)
https://simons.berkeley.edu/talks/ondrej-kuzelka-prague-university-2023-10-17
Probabilistic Circuits and Logic

First-order model counting (FOMC) is the task of counting models of a first-order logic sentence over a given set of domain elements. Its weighted variant, WFOMC, generalizes FOMC by assigning weights to the models and has applications among others in statistical relational learning. More than ten years of research by various authors has led to identification of non-trivial classes of WFOMC problems that can be solved in time polynomial in the number of domain elements. This talk is about recent developments on WFOMC and the related problem of weighted first-order model sampling (WFOMS). I will also discuss some applications of WFOMC and WFOMS, e.g., automated solving of problems from enumerative combinatorics and elementary probability theory. Finally, I will also describe how one could use the framework of WFOMS as a basis for a declarative framework for sampling combinatorial structures beyond what is provided nowadays in libraries of mainstream programming languages - this last application calls for more research on representations supporting efficient WFOMS. The talk is mostly based on the following papers: https://arxiv.org/abs/2302.02730, https://jair.org/index.php/jair/article/view/12320/26673, https://proceedings.kr.org/2021/57/kr2021-0057-van-bremen-et-al.pdf, https://ojs.aaai.org/index.php/AAAI/article/view/26449 and https://arxiv.org/abs/2302.04606.



Other Videos By Simons Institute for the Theory of Computing


2023-10-19The Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
2023-10-19Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete+Continuous Domains
2023-10-18Solving Marginal MAP Exactly by Probabilistic Circuit Transformations
2023-10-18Direct Access for Conjunctive Queries with Negation
2023-10-18Factorized Databases
2023-10-18Leveraging tree automata approximation results for efficient sampling and counting...
2023-10-18Efficient Enumeration Algorithms via Circuits
2023-10-17Lower Bounds for Tractable Arithmetic Circuits
2023-10-17Tractable Bounding of Counterfactual Queries by Knowledge Compilation
2023-10-17Combined Approximations for Probabilistic Query Evaluation: An Intensional Approach
2023-10-17First-Order Model Counting and Sampling
2023-10-17AND/OR Search Spaces for Anytime Probabilistic Reasoning
2023-10-17Credal Models for Uncertainty and Logic Treatment
2023-10-16Model Counting Meets Distinct Estimation
2023-10-16The Intensional-Extensional Problem in Probabilistic Databases
2023-10-16Compiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
2023-10-13Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
2023-10-13Resizable Sketches
2023-10-13A Simple Quantum Sketch With Applications to Graph Algorithms
2023-10-12Insights from Engineering Sketches for Production and Using Sketches at Scale
2023-10-12A Near-Linear Time Algorithm for the Chamfer Distance


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Probabilistic Circuits and Logic
Ondrej Kuzelka