Change search
ReferencesLink to record
Permanent link

Direct link
Learning bounded tree-width Bayesian networks using integer linear programming
KTH, Centres, Science for Life Laboratory, SciLifeLab. KTH, Centres, SeRC - Swedish e-Science Research Centre.
KTH, Centres, Science for Life Laboratory, SciLifeLab. KTH, Centres, SeRC - Swedish e-Science Research Centre.
2014 (English)In: Journal of machine learning research, ISSN 1532-4435, E-ISSN 1533-7928, Vol. 33, 751-759 p.Article in journal (Refereed) PublishedText
Abstract [en]

In many applications one wants to compute conditional probabilities given a Bayesian network. This inference problem is NP-hard in general but becomes tractable when the network has low tree-width. Since the inference problem is common in many application areas, we provide a practical algorithm for learning bounded tree-width Bayesian networks. We cast this problem as an integer linear program (ILP). The program can be solved by an anytime algorithm which provides upper bounds to assess the quality of the found solutions. A key component of our program is a novel integer linear formulation for bounding tree-width of a graph. Our tests clearly indicate that our approach works in practice, as our implementation was able to find an optimal or nearly optimal network for most of the data sets.

Place, publisher, year, edition, pages
Microtome Publishing , 2014. Vol. 33, 751-759 p.
Keyword [en]
Artificial intelligence, Forestry, Inference engines, Integer programming, Learning algorithms, Optimization, Trees (mathematics), Any-time algorithms, Application area, Conditional probabilities, Inference problem, Integer Linear Programming, Integer linear programs, Linear formulation, Optimal networks, Bayesian networks
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-187580ScopusID: 2-s2.0-84955497631OAI: oai:DiVA.org:kth-187580DiVA: diva2:937144
Conference
22 April 2014 through 25 April 2014
Funder
Swedish Research Council, 2013-4993
Note

QC 20160615

Available from: 2016-06-15 Created: 2016-05-25 Last updated: 2016-06-15Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Lagergren, Jens
By organisation
Science for Life Laboratory, SciLifeLabSeRC - Swedish e-Science Research Centre
In the same journal
Journal of machine learning research
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link