Main content

Multiplicative factorization of multi-valued NIN-AND tree causal models

Show simple item record

dc.contributor.advisor Xiang, Yang
dc.contributor.author Jin, Yiting
dc.date.accessioned 2016-03-30T17:38:45Z
dc.date.available 2016-03-30T17:38:45Z
dc.date.copyright 2016-02
dc.date.created 2016-02-29
dc.date.issued 2016-03-30
dc.identifier.uri http://hdl.handle.net/10214/9580
dc.description.abstract Bayesian networks (BNs) are compact representations of uncertain knowledge, which combine probability theory and graph theory. However, the size of each conditional probability table (CPT) in BNs still grows exponentially on the number of causes. Causal independence models (CIMs) are proposed to tackle this issue by exploiting causal independency among variables. However CIMs are not directly utilizable by common inference algorithms including lazy propagation. Multiplicative factorization (MF) is proposed as an efficient representation of CIMs, which makes CIMs applicable to lazy propagation. MF of CIMs such as noisy-OR, noisy-MAX and binary NIN-AND trees are proposed. Noisy-OR models are over binary variables and only model reinforcement. Noisy-MAX models are over multi-valued variables but only model reinforcement. Binary NIN-AND trees model both reinforcing and undermining causal interactions as well as their recursive mixtures but only for binary variables. Multi-valued NIN-AND trees generalize binary NIN-AND tree models, so they can now be applied to multi-valued variables. In order to take advantage of the generality and expressiveness of multi-valued NIN-AND trees as well as the efficiency of MF, we propose MF of multi-valued NIN-AND trees. MF of multi-valued NINAND trees involves four types of MFs: MF of dual NIN-AND gates, MF of direct NIN-AND gates, extended MF of dual NIN-AND gates and extended MF of direct NIN-AND gates. For each type of MF, we show its configuration by an example as well as the general form. We also analyze the correctness of each type of MF. MF of multi-valued NIN-AND trees preserves the linear complexity of NIN-AND tree models. The order of multiplication and marginalization is unconstrained as well. At last, we conduct a set of experiments comparing between the lazy propagation with MF applied and the standard lazy propagation. By comparing the posteriors from both types of inferences, we demonstrate the soundness of MF. We also show the efficiency of MF in terms of space consumption and runtime. en_US
dc.language.iso en en_US
dc.subject Artificial intelligence en_US
dc.subject Bayesian networks en_US
dc.subject Causal independence models en_US
dc.subject NIN-AND tree en_US
dc.subject Inference with Bayesian networks en_US
dc.title Multiplicative factorization of multi-valued NIN-AND tree causal models en_US
dc.type Thesis en_US
dc.degree.programme Computer Science en_US
dc.degree.name Master of Science en_US
dc.degree.department School of Computer Science en_US
dc.rights.license All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.


Files in this item

Files Size Format View
Jin_Yiting_201603_Msc.pdf 1.512Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record