Inference for Probabilistic Dependency Graphs

• URL: http://arxiv.org/abs/2311.05580v1
• Date: Thu, 9 Nov 2023 18:40:12 GMT
• Title: Inference for Probabilistic Dependency Graphs
• Authors: Oliver E. Richardson, Joseph Y. Halpern, and Christopher De Sa
• Abstract summary: Probabilistic dependency graphs (PDGs) are a flexible class of probabilistic models. We present the first tractable inference algorithm for PDGs with discrete variables.
• Score: 42.03917543423699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Probabilistic dependency graphs (PDGs) are a flexible class of probabilistic graphical models, subsuming Bayesian Networks and Factor Graphs. They can also capture inconsistent beliefs, and provide a way of measuring the degree of this inconsistency. We present the first tractable inference algorithm for PDGs with discrete variables, making the asymptotic complexity of PDG inference similar that of the graphical models they generalize. The key components are: (1) the observation that, in many cases, the distribution a PDG specifies can be formulated as a convex optimization problem (with exponential cone constraints), (2) a construction that allows us to express these problems compactly for PDGs of boundeed treewidth, (3) contributions to the theory of PDGs that justify the construction, and (4) an appeal to interior point methods that can solve such problems in polynomial time. We verify the correctness and complexity of our approach, and provide an implementation of it. We then evaluate our implementation, and demonstrate that it outperforms baseline approaches. Our code is available at http://github.com/orichardson/pdg-infer-uai.

Related papers

• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  We study the problem of learning Cartesian product graphs under Laplacian constraints. We establish statistical consistency for the penalized maximum likelihood estimation. We also extend our method for efficient joint graph learning and imputation in the presence of structural missing values.
  arXiv  Detail & Related papers  (2024-02-12T22:48:30Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Incremental Inference on Higher-Order Probabilistic Graphical Models Applied to Constraint Satisfaction Problems [0.0]
  dissertation presents three contributions to the PGM literature. First is a comparison between factor graphs and cluster graphs on graph colouring problems such as Sudokus. Second is an application of cluster graphs to a practical problem in cartography: land cover classification boosting. Third is a PGMs formulation for constraint satisfaction problems and an algorithm called purge-and-merge to solve such problems too complex for traditional PGMs.
  arXiv  Detail & Related papers  (2022-02-25T19:13:47Z)
• Loss as the Inconsistency of a Probabilistic Dependency Graph: Choose Your Model, Not Your Loss Function [0.0]
  We show that many standard loss functions arise as the inconsistency of a natural PDG describing the appropriate scenario. We also show that the PDG inconsistency captures a large class of statistical divergences. We observe that inconsistency becomes the log partition function (free energy) in the setting where PDGs are factor graphs.
  arXiv  Detail & Related papers  (2022-02-24T01:51:21Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm [0.0]
  purge-and-merge algorithm is designed to nudge a malleable graph structure towards a tree structure by selectively merging factors. This approach is evaluated on a number of constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro. Although these tasks were limited to the binary logic of CSP, we believe it holds promise for extension to general PGM inference.
  arXiv  Detail & Related papers  (2021-09-30T21:20:52Z)
• Probabilistic Dependency Graphs [14.505867475659274]
  We introduce Probabilistic Dependency Graphs (PDGs) PDGs can capture inconsistent beliefs in a natural way. We show how PDGs are an especially natural modeling tool.
  arXiv  Detail & Related papers  (2020-12-19T22:29:49Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.