NML Computation Algorithms for Tree-Structured Multinomial Bayesian Networks. (20th January 2008)

• Record Type: Journal Article
• Authors: Kontkanen, Petri; Wettig, Hannes; Myllymäki, Petri
• Other Names: Grünwald Peter Academic Editor.
• Is Part Of: EURASIP journal on bioinformatics and systems biology. Volume 2007(2007)
• Publication Date: 2008-01-20
• Subjects: Bioinformatics -- Periodicals; Systems biology -- Periodicals; Systems Biology; Signal Processing, Computer-Assisted; Bio-informatique; Biologie systémique; Bioinformatics; Systems biology; Systems Biology; Bioinformatics; Electronic journals; Periodical; Fulltext; Internet Resources; Periodicals; Periodicals; 570.285
• DOI: 10.1155/2007/90947
• Languages: English
• ISSNs: 1687-4145

Abstract

Abstract : Typical problems in bioinformatics involve large discrete datasets. Therefore, in order to apply statistical methods in such domains, it is important to develop efficient algorithms suitable for discrete data. The minimum description length (MDL) principle is a theoretically well-founded, general framework for performing statistical inference. The mathematical formalization of MDL is based on the normalized maximum likelihood (NML) distribution, which has several desirable theoretical properties. In the case of discrete data, straightforward computation of the NML distribution requires exponential time with respect to the sample size, since the definition involves a sum over all the possible data samples of a fixed size. In this paper, we first review some existing algorithms for efficient NML computation in the case of multinomial and naive Bayes model families. Then we proceed by extending these algorithms to more complex, tree-structured Bayesian networks.