IBIA: Bayesian Inference via Incremental Build-Infer-Approximate operations on Clique Trees

• URL: http://arxiv.org/abs/2202.12003v1
• Date: Thu, 24 Feb 2022 10:30:31 GMT
• Title: IBIA: Bayesian Inference via Incremental Build-Infer-Approximate operations on Clique Trees
• Authors: Shivani Bathla and Vinita Vasudevan
• Abstract summary: We propose an alternative approach for approximate inference based on an incremental build-infer-approximate paradigm. We show that our algorithm for incremental construction of clique trees always generates a valid CT and our approximation technique automatically maintains consistency of within-clique beliefs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Exact inference in Bayesian networks is intractable and has an exponential dependence on the size of the largest clique in the corresponding clique tree, necessitating approximations. Techniques for approximate inference typically use iterative BP in graphs with bounded cluster sizes. We propose an alternative approach for approximate inference based on an incremental build-infer-approximate (IBIA) paradigm. In the build stage of this approach, bounded-clique size partitions are obtained by building the clique tree (CT) incrementally. Nodes are added to the CT as long as the sizes are within a user-specified clique size constraint. Once the clique size constraint is reached, the infer and approximate part of the algorithm finds an approximate CT with lower clique sizes to which new nodes can be added. This step involves exact inference to calibrate the CT and a combination of exact and approximate marginalization for approximation. The approximate CT serves as a starting point for the construction of CT for the next partition. The algorithm returns a forest of calibrated clique trees corresponding to all partitions. We show that our algorithm for incremental construction of clique trees always generates a valid CT and our approximation technique automatically maintains consistency of within-clique beliefs. The queries of interest are prior and posterior singleton marginals and the partition function. More than 500 benchmarks were used to test the method and the results show a significant reduction in error when compared to other approximate methods, with competitive runtimes.

Related papers

• Counterfactual Maps: What They Are and How to Find Them [6.859102414696437]
  Counterfactual explanations are a central tool in interpretable machine learning, yet computing them exactly for complex models remains challenging.<n>For tree ensembles, predictions are piecewise constant over a large collection of axis-aligned hyperrectangles, implying that an optimal counterfactual for a point corresponds to its projection onto the nearest rectangle with an alternative label under a chosen metric.<n>In this work, we revisit counterfactual generation through the lens of nearest-region search and introduce counterfactual maps, a global representation of recourse for tree ensembles.
  arXiv  Detail & Related papers  (2026-02-09T19:20:16Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Learning-Augmented Hierarchical Clustering [29.438861266606573]
  We consider the problem of hierarchical clustering given auxiliary information from natural oracles.<n>We show that a splitting oracle enables algorithms to outperform standard HC approaches.<n>Our approaches extend to sublinear settings, in which we show new streaming and PRAM algorithms with improved guarantees.
  arXiv  Detail & Related papers  (2025-06-05T18:22:40Z)
• Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders [77.84801537608651]
  Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than embedding-based models (dual-encoders) at estimating query-item relevance. We propose a sparse-matrix factorization based method that efficiently computes latent query and item embeddings to approximate CE scores and performs k-NN search with the approximate CE similarity.
  arXiv  Detail & Related papers  (2024-05-06T17:14:34Z)
• Prompt Based Tri-Channel Graph Convolution Neural Network for Aspect Sentiment Triplet Extraction [63.0205418944714]
  Aspect Sentiment Triplet Extraction (ASTE) is an emerging task to extract a given sentence's triplets, which consist of aspects, opinions, and sentiments. Recent studies tend to address this task with a table-filling paradigm, wherein word relations are encoded in a two-dimensional table. We propose a novel model for the ASTE task, called Prompt-based Tri-Channel Graph Convolution Neural Network (PT-GCN), which converts the relation table into a graph to explore more comprehensive relational information.
  arXiv  Detail & Related papers  (2023-12-18T12:46:09Z)
• Target before Shooting: Accurate Anomaly Detection and Localization under One Millisecond via Cascade Patch Retrieval [49.45246833329707]
  We re-examine the "matching" nature of Anomaly Detection (AD) We propose a new AD framework that simultaneously enjoys new records of AD accuracy and dramatically high running speed.
  arXiv  Detail & Related papers  (2023-08-13T11:49:05Z)
• Approximate inference of marginals using the IBIA framework [0.0]
  Exact inference of marginals in probabilistic graphical models (PGM) is known to be intractable. We propose a new algorithm for marginal inference that is based on the incremental build-infer-approximate (IBIA) paradigm. Our method gives either better or comparable accuracy than existing variational and sampling based methods, with smaller runtimes.
  arXiv  Detail & Related papers  (2023-06-01T04:24:21Z)
• IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function [0.0]
  Exact computation of the partition function is known to be intractable. We propose a novel incremental build-infer-approximate framework for approximate inference. We show that the framework can be used to efficiently compute the partition function.
  arXiv  Detail & Related papers  (2023-04-13T09:40:23Z)
• Optimal Extended Neighbourhood Rule $k$ Nearest Neighbours Ensemble [1.8843687952462742]
  A new optimal extended neighborhood rule based ensemble method is proposed in this paper. The ensemble is compared with state-of-the-art methods on 17 benchmark datasets using accuracy, Cohen's kappa, and Brier score (BS)
  arXiv  Detail & Related papers  (2022-11-21T09:13:54Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Deep Affinity Net: Instance Segmentation via Affinity [48.498706304017674]
  Deep Affinity Net is an effective affinity-based approach accompanied with a new graph partitioning algorithm Cascade-GAEC. It achieves the best single-shot result as well as the fastest running time among all affinity-based models. It also outperforms the region-based method Mask R-CNN.
  arXiv  Detail & Related papers  (2020-03-15T15:22:56Z)

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.