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.

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.

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.

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.