A new constraint-based algorithm to learn Bayesian network structure from data: Control of Spurious Pairwise Information (CSPI)

A Bayesian network is a directed acyclic graphical representation of a set of variables. This representation occupies the middle ground between a causal network and a simple list of pairwise correlations by including information about dependencies between variables. There are applications of Bayesian networks in many fields, such as financial risk management, bioinformatics and audio-visual perception, to name just a few. However, learning the network structure from data requires an exponential number of conditional independence tests; several algorithms have been proposed in order to reduce the runtime of this procedure. We present a new constraint-based algorithm for learning Bayesian network structure from data, based on Control of Spurious Pairwise Information (CSPI). We limit the computational cost of learning by trading an increase in complexity of the initial steps for a substantial reduction in the complexity of conditional pairwise independence testing. We employ a logging and rollback strategy to reduce the number of missing edges. We show that the CSPI algorithm outperforms several other algorithms in complexity and/or accuracy on benchmark datasets.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science (UMKC)

Grantor dc:publisher

University of Missouri--Kansas City

Year dc:date.issued

2011

Author dc:creator

• Andrade, Pablo de Morais

Advisor dc:contributor.advisor

• Dinakarpandian, Deendayal

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10355/10841

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/10841