Spelling suggestions: "subject:"model counting"" "subject:"godel counting""
1 |
Exploiting Structure in Backtracking Algorithms for Propositional and Probabilistic ReasoningLi, Wei January 2010 (has links)
Boolean propositional satisfiability (SAT) and probabilistic reasoning represent
two core problems in AI. Backtracking based algorithms have been applied in both
problems. In this thesis, I investigate structure-based techniques for solving real world
SAT and Bayesian networks, such as software testing and medical diagnosis instances.
When solving a SAT instance using backtracking search, a sequence of decisions
must be made as to which variable to branch on or instantiate next. Real world problems
are often amenable to a divide-and-conquer strategy where the original instance
is decomposed into independent sub-problems. Existing decomposition techniques
are based on pre-processing the static structure of the original problem. I propose
a dynamic decomposition method based on hypergraph separators. Integrating this
dynamic separator decomposition into the variable ordering of a modern SAT solver
leads to speedups on large real world SAT problems.
Encoding a Bayesian network into a CNF formula and then performing weighted
model counting is an effective method for exact probabilistic inference. I present two
encodings for improving this approach with noisy-OR and noisy-MAX relations. In
our experiments, our new encodings are more space efficient and can speed up the
previous best approaches over two orders of magnitude.
The ability to solve similar problems incrementally is critical for many probabilistic
reasoning problems. My aim is to exploit the similarity of these instances by
forwarding structural knowledge learned during the analysis of one instance to the
next instance in the sequence. I propose dynamic model counting and extend the dynamic
decomposition and caching technique to multiple runs on a series of problems
with similar structure. This allows us to perform Bayesian inference incrementally as
the evidence, parameter, and structure of the network change. Experimental results
show that my approach yields significant improvements over previous model counting
approaches on multiple challenging Bayesian network instances.
|
2 |
Exploiting Structure in Backtracking Algorithms for Propositional and Probabilistic ReasoningLi, Wei January 2010 (has links)
Boolean propositional satisfiability (SAT) and probabilistic reasoning represent
two core problems in AI. Backtracking based algorithms have been applied in both
problems. In this thesis, I investigate structure-based techniques for solving real world
SAT and Bayesian networks, such as software testing and medical diagnosis instances.
When solving a SAT instance using backtracking search, a sequence of decisions
must be made as to which variable to branch on or instantiate next. Real world problems
are often amenable to a divide-and-conquer strategy where the original instance
is decomposed into independent sub-problems. Existing decomposition techniques
are based on pre-processing the static structure of the original problem. I propose
a dynamic decomposition method based on hypergraph separators. Integrating this
dynamic separator decomposition into the variable ordering of a modern SAT solver
leads to speedups on large real world SAT problems.
Encoding a Bayesian network into a CNF formula and then performing weighted
model counting is an effective method for exact probabilistic inference. I present two
encodings for improving this approach with noisy-OR and noisy-MAX relations. In
our experiments, our new encodings are more space efficient and can speed up the
previous best approaches over two orders of magnitude.
The ability to solve similar problems incrementally is critical for many probabilistic
reasoning problems. My aim is to exploit the similarity of these instances by
forwarding structural knowledge learned during the analysis of one instance to the
next instance in the sequence. I propose dynamic model counting and extend the dynamic
decomposition and caching technique to multiple runs on a series of problems
with similar structure. This allows us to perform Bayesian inference incrementally as
the evidence, parameter, and structure of the network change. Experimental results
show that my approach yields significant improvements over previous model counting
approaches on multiple challenging Bayesian network instances.
|
3 |
Effects of groups in demand for consultation dental / Efeitos de grupos na demanda por consultas odontolÃgicasWilliam Sheldon Maia Xavier 14 February 2012 (has links)
nÃo hà / The purpose of this study is to identify the existence of group effects, known as peer effects, at the demand for dental appointments in collective contracts that are
exclusively dental health plans. This paper compares the number of dental appointments of each person with the amount of dental appointments in the group, despising the history appoint of the analyzed individual. In order to test empirically if the group effect is important, a model of traditional counting was used, with the introduction of the variable that indicates of group effect, particularly, the model of binomial negative counting for panel with random effects, embracing both the effect of over-dispersion and the time dependence of the use for the same person. The companies were divided into five groups according to their size, as follows: 2 to 20, 21 to 50, 51 to 100, 101 to 200 and more than 200 beneficiaries. The results showed that the group effects increased successively according to the size of the company, in which companies with more than 200 beneficiaries were the ones most affected. / O objetivo deste estudo à identificar a existÃncia de efeitos de grupo, ou peer effect, na demanda por consultas odontolÃgicas dentro de contratos coletivos de planos saÃde exclusivamente odontolÃgicos. O trabalho compara a quantidade de consultas
odontolÃgicas de cada indivÃduo com a quantidade de consultas odontolÃgicas do grupo, desconsiderando o histÃrico de consultas do indivÃduo analisado. Para testar empiricamente se o efeito de grupo à importante, foram utilizados modelos de
contagem tradicionais com a introduÃÃo da variÃvel indicadora de efeito de grupo, em particular, o modelo de contagem binomial negativo para painel com efeito aleatÃrio para acomodar tanto o efeito sobre-dispersÃo quanto à dependÃncia
temporal do uso para o mesmo indivÃduo. As empresas foram divididas em 5 grupos de acordo com seu porte, sendo: 2 a 20, 21 a 50, 51 a 100, 101 a 200 e mais de 200 beneficiÃrios. Os resultados mostraram que os efeitos de grupo aumentaram
sucessivamente de acordo com o aumento do porte da empresa, sendo as empresas com mais de 200 beneficiÃrios aquelas mais afetadas pelos efeitos de grupo.
|
4 |
On Tractability and Consistency of Probabilistic Inference in Relational DomainsMalhotra, Sagar 10 July 2023 (has links)
Relational data is characterised by the rich structure it encodes in the dependencies between the individual entities of a given domain. Statistical Relational Learning (SRL) combines first-order logic and probability to learn and reason over relational domains by creating parametric probability distributions over relational structures. SRL models can succinctly represent the complex dependencies in relational data and admit learning and inference under uncertainty. However, these models are significantly limited when it comes to the tractability of learning and inference. This limitation emerges from the intractability of Weighted First Order Model Counting (WFOMC), as both learning and inference in SRL models can be reduced to instances of WFOMC. Hence, fragments of first-order logic that admit tractable WFOMC, widely known as domain-liftable, can significantly advance the practicality and efficiency of SRL models. Recent works have uncovered another limitation of SRL models, i.e., they lead to unintuitive behaviours when used across varying domain sizes, violating fundamental consistency conditions expected of sound probabilistic models. Such inconsistencies also mean that conventional machine learning techniques, like training with batched data, cannot be soundly used for SRL models. In this thesis, we contribute to both the tractability and consistency of probabilistic inference in SRL models. We first expand the class of domain-liftable fragments with counting quantifiers and cardinality constraints. Unlike the algorithmic approaches proposed in the literature, we present a uniform combinatorial approach, admitting analytical combinatorial formulas for WFOMC. Our approach motivates a new family of weight functions allowing us to express a larger class of probability distributions without losing domain-liftability. We further expand the class of domain-liftable fragments with constraints inexpressible in first-order logic, namely acyclicity and connectivity constraints. Finally, we present a complete characterization for a statistically consistent (a.k.a projective) models in the two-variable fragment of a widely used class of SRL models, namely Markov Logic Networks.
|
Page generated in 0.0901 seconds