Fast Converging Anytime Model Counting

• URL: http://arxiv.org/abs/2212.09390v1
• Date: Mon, 19 Dec 2022 12:01:28 GMT
• Title: Fast Converging Anytime Model Counting
• Authors: Yong Lai, Kuldeep S. Meel, Roland H. C. Yap
• Abstract summary: This paper designs a new anytime approach called PartialKC for approximate model counting. Our empirical analysis demonstrates that PartialKC achieves significant scalability and accuracy over prior state-of-the-art approximate counters. Interestingly, the empirical results show that PartialKC reaches convergence for many instances and therefore provides exact model counting performance comparable to state-of-the-art exact counters.
• Score: 34.295512073482186
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Model counting is a fundamental problem which has been influential in many applications, from artificial intelligence to formal verification. Due to the intrinsic hardness of model counting, approximate techniques have been developed to solve real-world instances of model counting. This paper designs a new anytime approach called PartialKC for approximate model counting. The idea is a form of partial knowledge compilation to provide an unbiased estimate of the model count which can converge to the exact count. Our empirical analysis demonstrates that PartialKC achieves significant scalability and accuracy over prior state-of-the-art approximate counters, including satss and STS. Interestingly, the empirical results show that PartialKC reaches convergence for many instances and therefore provides exact model counting performance comparable to state-of-the-art exact counters.

Related papers

• Model Counting in the Wild [31.05707402954459]
  We conduct a rigorous assessment of the scalability of model counters in the wild. We evaluate six state-of-the-art model counters on these instances to assess scalability and runtime performance. Our analysis highlights the challenges and opportunities for portfolio-based approaches in model counting.
  arXiv  Detail & Related papers  (2024-08-13T17:49:46Z)
• Exact and general decoupled solutions of the LMC Multitask Gaussian Process model [28.32223907511862]
  The Linear Model of Co-regionalization (LMC) is a very general model of multitask gaussian process for regression or classification. Recent work has shown that under some conditions the latent processes of the model can be decoupled, leading to a complexity that is only linear in the number of said processes. We here extend these results, showing from the most general assumptions that the only condition necessary to an efficient exact computation of the LMC is a mild hypothesis on the noise model.
  arXiv  Detail & Related papers  (2023-10-18T15:16:24Z)
• Precision-Recall Divergence Optimization for Generative Modeling with GANs and Normalizing Flows [54.050498411883495]
  We develop a novel training method for generative models, such as Generative Adversarial Networks and Normalizing Flows. We show that achieving a specified precision-recall trade-off corresponds to minimizing a unique $f$-divergence from a family we call the textitPR-divergences. Our approach improves the performance of existing state-of-the-art models like BigGAN in terms of either precision or recall when tested on datasets such as ImageNet.
  arXiv  Detail & Related papers  (2023-05-30T10:07:17Z)
• Evaluating Representations with Readout Model Switching [18.475866691786695]
  In this paper, we propose to use the Minimum Description Length (MDL) principle to devise an evaluation metric. We design a hybrid discrete and continuous-valued model space for the readout models and employ a switching strategy to combine their predictions. The proposed metric can be efficiently computed with an online method and we present results for pre-trained vision encoders of various architectures.
  arXiv  Detail & Related papers  (2023-02-19T14:08:01Z)
• Counting Like Human: Anthropoid Crowd Counting on Modeling the Similarity of Objects [92.80955339180119]
  mainstream crowd counting methods regress density map and integrate it to obtain counting results. Inspired by this, we propose a rational and anthropoid crowd counting framework.
  arXiv  Detail & Related papers  (2022-12-02T07:00:53Z)
• Posterior Coreset Construction with Kernelized Stein Discrepancy for Model-Based Reinforcement Learning [78.30395044401321]
  We develop a novel model-based approach to reinforcement learning (MBRL) It relaxes the assumptions on the target transition model to belong to a generic family of mixture models. It can achieve up-to 50 percent reduction in wall clock time in some continuous control environments.
  arXiv  Detail & Related papers  (2022-06-02T17:27:49Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Distributional Depth-Based Estimation of Object Articulation Models [21.046351215949525]
  We propose a method that efficiently learns distributions over articulation model parameters directly from depth images. Our core contributions include a novel representation for distributions over rigid body transformations. We introduce a novel deep learning based approach, DUST-net, that performs category-independent articulation model estimation.
  arXiv  Detail & Related papers  (2021-08-12T17:44:51Z)
• Closed-form Continuous-Depth Models [99.40335716948101]
  Continuous-depth neural models rely on advanced numerical differential equation solvers. We present a new family of models, termed Closed-form Continuous-depth (CfC) networks, that are simple to describe and at least one order of magnitude faster.
  arXiv  Detail & Related papers  (2021-06-25T22:08:51Z)
• Amortized Bayesian model comparison with evidential deep learning [0.12314765641075436]
  We propose a novel method for performing Bayesian model comparison using specialized deep learning architectures. Our method is purely simulation-based and circumvents the step of explicitly fitting all alternative models under consideration to each observed dataset. We show that our method achieves excellent results in terms of accuracy, calibration, and efficiency across the examples considered in this work.
  arXiv  Detail & Related papers  (2020-04-22T15:15:46Z)

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.