Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption

Jose M. Peña; Johan Björkegren; Jesper Tegnér

doi:10.1007/11518655_13

Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption

Jose M. Peña
, Johan Björkegren
, Jesper Tegnér

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

21 Scopus citations

Abstract

We propose an algorithm for learning the Markov boundary of a random variable from data without having to learn a complete Bayesian network. The algorithm is correct under the faithfulness assumption, scalable and data efficient. The last two properties are important because we aim to apply the algorithm to identify the minimal set of random variables that is relevant for probabilistic classification in databases with many random variables but few instances. We report experiments with synthetic and real databases with 37, 441 and 139352 random variables showing that the algorithm performs satisfactorily.

Original language	English
Title of host publication	Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings
Publisher	Springer Verlag
Pages	136-147
Number of pages	12
ISBN (Print)	3540273263, 9783540273264
DOIs	https://doi.org/10.1007/11518655_13
State	Published - 2005
Externally published	Yes
Event	8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005 - Barcelona, Spain Duration: 6 Jul 2005 → 8 Jul 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3571 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005
Country/Territory	Spain
City	Barcelona
Period	6/07/05 → 8/07/05

Access to Document

10.1007/11518655_13

Cite this

Peña, J. M., Björkegren, J., & Tegnér, J. (2005). Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings (pp. 136-147). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3571 LNAI). Springer Verlag. https://doi.org/10.1007/11518655_13

Peña, Jose M. ; Björkegren, Johan ; Tegnér, Jesper. / Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption. Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings. Springer Verlag, 2005. pp. 136-147 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{68a44e45e73f474e8d498573a1ed89ec,

title = "Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption",

abstract = "We propose an algorithm for learning the Markov boundary of a random variable from data without having to learn a complete Bayesian network. The algorithm is correct under the faithfulness assumption, scalable and data efficient. The last two properties are important because we aim to apply the algorithm to identify the minimal set of random variables that is relevant for probabilistic classification in databases with many random variables but few instances. We report experiments with synthetic and real databases with 37, 441 and 139352 random variables showing that the algorithm performs satisfactorily.",

author = "Pe{\~n}a, \{Jose M.\} and Johan Bj{\"o}rkegren and Jesper Tegn{\'e}r",

year = "2005",

doi = "10.1007/11518655\_13",

language = "English",

isbn = "3540273263",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "136--147",

booktitle = "Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings",

address = "Germany",

note = "8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005 ; Conference date: 06-07-2005 Through 08-07-2005",

}

Peña, JM, Björkegren, J & Tegnér, J 2005, Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption. in Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3571 LNAI, Springer Verlag, pp. 136-147, 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005, Barcelona, Spain, 6/07/05. https://doi.org/10.1007/11518655_13

Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption. / Peña, Jose M.; Björkegren, Johan; Tegnér, Jesper.
Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings. Springer Verlag, 2005. p. 136-147 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3571 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption

AU - Peña, Jose M.

AU - Björkegren, Johan

AU - Tegnér, Jesper

PY - 2005

Y1 - 2005

N2 - We propose an algorithm for learning the Markov boundary of a random variable from data without having to learn a complete Bayesian network. The algorithm is correct under the faithfulness assumption, scalable and data efficient. The last two properties are important because we aim to apply the algorithm to identify the minimal set of random variables that is relevant for probabilistic classification in databases with many random variables but few instances. We report experiments with synthetic and real databases with 37, 441 and 139352 random variables showing that the algorithm performs satisfactorily.

AB - We propose an algorithm for learning the Markov boundary of a random variable from data without having to learn a complete Bayesian network. The algorithm is correct under the faithfulness assumption, scalable and data efficient. The last two properties are important because we aim to apply the algorithm to identify the minimal set of random variables that is relevant for probabilistic classification in databases with many random variables but few instances. We report experiments with synthetic and real databases with 37, 441 and 139352 random variables showing that the algorithm performs satisfactorily.

UR - https://www.scopus.com/pages/publications/26944438313

U2 - 10.1007/11518655_13

DO - 10.1007/11518655_13

M3 - Conference contribution

AN - SCOPUS:26944438313

SN - 3540273263

SN - 9783540273264

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 136

EP - 147

BT - Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings

PB - Springer Verlag

T2 - 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005

Y2 - 6 July 2005 through 8 July 2005

ER -

Peña JM, Björkegren J, Tegnér J. Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 8th European Conference, ECSQARU 2005, Proceedings. Springer Verlag. 2005. p. 136-147. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11518655_13

Scalable, efficient and correct learning of markov boundaries under the faithfulness assumption

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this