Author name cluster

Adnan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

IJCAI Conference 2005 Conference Paper

Compiling Bayesian Networks with Local Structure

Mark Chavira
Adnan

Recent work on compiling Bayesian networks has reduced the problem to that of factoring CNF encodings of these networks, providing an expressive framework for exploiting local structure. For networks that have local structure, large CPTs, yet no excessive determinism, the quality of the CNF encodings and the amount of local structure they capture can have a significant effect on both the offline compile time and online inference time. We examine the encoding of such Bayesian networks in this paper and report on new findings that allow us to significantly scale this compilation approach. In particular, we obtain order–of–magnitude improvements in compile time, compile some networks successfully for the first time, and obtain orders– of–magnitude improvements in online inference for some networks with local structure, as compared to baseline jointree inference, which does not exploit local structure.

PDF

IJCAI Conference 2005 Conference Paper

DPLL with a Trace: From SAT to Knowledge Compilation

Jinbo Huang
Adnan

We show that the trace of an exhaustive DPLL search can be viewed as a compilation of the propositional theory. With different constraints imposed or lifted on the DPLL algorithm, this compilation will belong to the language of d-DNNF, FBDD, and OBDD, respectively. These languages are decreasingly succinct, yet increasingly tractable, supporting such polynomial-time queries as model counting and equivalence testing. Our contribution is thus twofold. First, we provide a uniform framework, supported by empirical evaluations, for compiling knowledge into various languages of interest. Second, we show that given a particular variant of DPLL, by identifying the language membership of its traces, one gains a fundamental understanding of the intrinsic complexity and computational power of the search algorithm itself. As interesting examples, we unveil the “hidden power” of several recent model counters, point to one of their potential limitations, and identify a key limitation of DPLLbased procedures in general.

PDF

IJCAI Conference 2005 Conference Paper

Sensitivity Analysis in Markov Networks

Hei Chan
Adnan

This paper explores the topic of sensitivity analysis in Markov networks, by tackling questions similar to those arising in the context of Bayesian networks: the tuning of parameters to satisfy query constraints, and the bounding of query changes when perturbing network parameters. Even though the distribution induced by a Markov network corresponds to ratios of multi-linear functions, whereas the distribution induced by a Bayesian network corresponds to multi-linear functions, the results we obtain for Markov networks are as effective computationally as those obtained for Bayesian networks. This similarity is due to the fact that conditional probabilities have the same functional form in both Bayesian and Markov networks, which turns out to be the more influential factor. The major difference we found, however, is in how changes in parameter values should be quantified, as such parameters are interpreted differently in Bayesian networks and Markov networks.

PDF