Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number

Janne H. Korhonen; Pekka Parviainen

Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number

Janne H. Korhonen, Pekka Parviainen

Department of Computer Science

University of Helsinki

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

16 Citations (Scopus)

Abstract

Both learning and inference tasks on Bayesian networks are NP-hard in general. Bounded tree-width Bayesian networks have recently received a lot of attention as a way to circumvent this complexity issue; however, while inference on bounded tree-width networks is tractable, the learning problem remains NP-hard even for tree-width~2. In this paper, we propose bounded vertex cover number Bayesian networks as an alternative to bounded tree-width networks. In particular, we show that both inference and learning can be done in polynomial time for any fixed vertex cover number bound k, in contrast to the general and bounded tree-width cases; on the other hand, we also show that learning problem is W[1]-hard in parameter k. Furthermore, we give an alternative way to learn bounded vertex cover number Bayesian networks using integer linear programming (ILP), and show this is feasible in practice.

Original language	English
Title of host publication	The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015
Editors	Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, Roman Garnett
Pages	622-630
Publication status	Published - 2015
MoE publication type	A4 Conference publication
Event	IEEE Conference on Neural Information Processing Systems - Montreal, Canada Duration: 7 Dec 2015 → 12 Dec 2015 Conference number: 28

Publication series

Name	Advances in neural information processing systems
ISSN (Print)	1049-5258

Conference

Conference	IEEE Conference on Neural Information Processing Systems
Abbreviated title	NIPS
Country/Territory	Canada
City	Montreal
Period	07/12/2015 → 12/12/2015

Access to Document

https://proceedings.neurips.cc/paper/2015/hash/66368270ffd51418ec58bd793f2d9b1b-Abstract.html

Cite this

Korhonen, J. H., & Parviainen, P. (2015). Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, & R. Garnett (Eds.), The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015 (pp. 622-630). (Advances in neural information processing systems). https://proceedings.neurips.cc/paper/2015/hash/66368270ffd51418ec58bd793f2d9b1b-Abstract.html

Korhonen, Janne H. ; Parviainen, Pekka. / Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number. The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015. editor / Corinna Cortes ; Neil D. Lawrence ; Daniel D. Lee ; Masashi Sugiyama ; Roman Garnett. 2015. pp. 622-630 (Advances in neural information processing systems).

@inproceedings{31cba88636a44aabad6ecae569b2f61b,

title = "Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number",

abstract = "Both learning and inference tasks on Bayesian networks are NP-hard in general. Bounded tree-width Bayesian networks have recently received a lot of attention as a way to circumvent this complexity issue; however, while inference on bounded tree-width networks is tractable, the learning problem remains NP-hard even for tree-width~2. In this paper, we propose bounded vertex cover number Bayesian networks as an alternative to bounded tree-width networks. In particular, we show that both inference and learning can be done in polynomial time for any fixed vertex cover number bound k, in contrast to the general and bounded tree-width cases; on the other hand, we also show that learning problem is W[1]-hard in parameter k. Furthermore, we give an alternative way to learn bounded vertex cover number Bayesian networks using integer linear programming (ILP), and show this is feasible in practice.",

author = "Korhonen, {Janne H.} and Pekka Parviainen",

note = "VK: Kaski, S.; HIIT; COIN; TRITON; IEEE Conference on Neural Information Processing Systems, NIPS ; Conference date: 07-12-2015 Through 12-12-2015",

year = "2015",

language = "English",

series = "Advances in neural information processing systems",

pages = "622--630",

editor = "Corinna Cortes and Lawrence, {Neil D.} and Lee, {Daniel D.} and Masashi Sugiyama and Roman Garnett",

booktitle = "The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015",

}

Korhonen, JH & Parviainen, P 2015, Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number. in C Cortes, ND Lawrence, DD Lee, M Sugiyama & R Garnett (eds), The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015. Advances in neural information processing systems, pp. 622-630, IEEE Conference on Neural Information Processing Systems, Montreal, Quebec, Canada, 07/12/2015. <https://proceedings.neurips.cc/paper/2015/hash/66368270ffd51418ec58bd793f2d9b1b-Abstract.html>

Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number. / Korhonen, Janne H.; Parviainen, Pekka.
The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015. ed. / Corinna Cortes; Neil D. Lawrence; Daniel D. Lee; Masashi Sugiyama; Roman Garnett. 2015. p. 622-630 (Advances in neural information processing systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number

AU - Korhonen, Janne H.

AU - Parviainen, Pekka

N1 - Conference code: 28

PY - 2015

Y1 - 2015

N2 - Both learning and inference tasks on Bayesian networks are NP-hard in general. Bounded tree-width Bayesian networks have recently received a lot of attention as a way to circumvent this complexity issue; however, while inference on bounded tree-width networks is tractable, the learning problem remains NP-hard even for tree-width~2. In this paper, we propose bounded vertex cover number Bayesian networks as an alternative to bounded tree-width networks. In particular, we show that both inference and learning can be done in polynomial time for any fixed vertex cover number bound k, in contrast to the general and bounded tree-width cases; on the other hand, we also show that learning problem is W[1]-hard in parameter k. Furthermore, we give an alternative way to learn bounded vertex cover number Bayesian networks using integer linear programming (ILP), and show this is feasible in practice.

AB - Both learning and inference tasks on Bayesian networks are NP-hard in general. Bounded tree-width Bayesian networks have recently received a lot of attention as a way to circumvent this complexity issue; however, while inference on bounded tree-width networks is tractable, the learning problem remains NP-hard even for tree-width~2. In this paper, we propose bounded vertex cover number Bayesian networks as an alternative to bounded tree-width networks. In particular, we show that both inference and learning can be done in polynomial time for any fixed vertex cover number bound k, in contrast to the general and bounded tree-width cases; on the other hand, we also show that learning problem is W[1]-hard in parameter k. Furthermore, we give an alternative way to learn bounded vertex cover number Bayesian networks using integer linear programming (ILP), and show this is feasible in practice.

UR - https://papers.nips.cc/paper/6003-tractable-bayesian-network-structure-learning-with-bounded-vertex-cover-number

M3 - Conference article in proceedings

T3 - Advances in neural information processing systems

SP - 622

EP - 630

BT - The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS), Montreal, 6.-12.12.2015

A2 - Cortes, Corinna

A2 - Lawrence, Neil D.

A2 - Lee, Daniel D.

A2 - Sugiyama, Masashi

A2 - Garnett, Roman

T2 - IEEE Conference on Neural Information Processing Systems

Y2 - 7 December 2015 through 12 December 2015

ER -

Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this