Main content

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

Show full item record

Title: Multiplicative factorization of multi-valued NIN-AND tree causal models
Author: Jin, Yiting
Department: School of Computer Science
Program: Computer Science
Advisor: Xiang, Yang
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.
Date: 2016-02

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 full item record