Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Concentration Free Outlier Detection Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks

Authors : Nicola Di Mauro, Antonio Vergari, Teresa M. A. Basile, Floriana Esposito

Published in: Machine Learning and Knowledge Discovery in Databases

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Cutset Networks (CNets) are density estimators leveraging context-specific independencies recently introduced to provide exact inference in polynomial time. Learning a CNet is done by firstly building a weighted probabilistic OR tree and then estimating tractable distributions as its leaves. Specifically, selecting an optimal OR split node requires cubic time in the number of the data features, and even approximate heuristics still scale in quadratic time. We introduce Extremely Randomized Cutset Networks (XCNets), CNets whose OR tree is learned by performing random conditioning. This simple yet surprisingly effective approach reduces the complexity of OR node selection to constant time. While the likelihood of an XCNet is slightly worse than an optimally learned CNet, ensembles of XCNets outperform state-of-the-art density estimators on a series of standard benchmark datasets, yet employing only a fraction of the time needed to learn the competitors. Code and data related to this chapter are available at: https://​github.​com/​nicoladimauro/​cnet.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Ensemble-Compression: A New Method for Parallel Training of Deep Neural Networks
next chapter Deep Discrete Hashing with Self-supervised Pairwise Labels
Footnotes
1
E.g., classification can be framed as Most Probable Explanation (MPE) inference.
 
2
Source code of dCSN and XCNet in C++11 and the scripts to replicate the experiments are made available at https://​github.​com/​nicoladimauro/​cnet. All experiments have been run on a 4-core Intel Xeon E312xx (Sandy Bridge) @2.0 GHz with 8 Gb of RAM and Ubuntu 14.04.1, kernel 3.13.0-39.
 
3
The following grid search to learn CNets with dCSN, XCNet, \(\mathsf {dCSN_{PoB}}\), and \(\mathsf {XCNet_{PoB}}\) has been performed: \(\delta \in \{300,500,1000,2000\}\), \(\alpha \in \{0.1,0.2,0.5,1,2\}\) and \(\sigma =4\).
 
4
The relative decrease is computed as \(\frac{\ell _{\mathcal {D}}(\mathsf {XCNet})-\ell _{\mathcal {D}}(\mathsf {dCSN})}{\ell _{\mathcal {D}}(\mathsf {dCSN})}\cdot 100\).
 
5
Note that we report the best log-likelihood across more than one algorithmic variant, hence these results can be considered to be derived from models optimized over more parameters.
 
Literature
1.
Bekker, J., Davis, J., Choi, A., Darwiche, A., Van den Broeck, G.: Tractable learning for complex probability queries. In: NIPS (2015)
2.
Boutilier, C., Friedman, N., Goldszmidt, M., Koller, D.: Context-specific independence in Bayesian networks. In: UAI (1996)
3.
Chickering, M.: The Winmine Toolkit. Microsoft, Redmond (2002)
4.
Choi, A., Van den Broeck, G., Darwiche, A.: Tractable learning for structured probability spaces: a case study in learning preference distributions. In: IJCAI (2015)
5.
Chow, C., Liu, C.: Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory 14, 462–467 (1968)CrossRefMATH
6.
7.
Di Mauro, N., Vergari, A., Esposito, F.: Multi-label classification with cutset networks. In: PGM (2016)
8.
Di Mauro, N., Vergari, A., Basile, T.: Learning Bayesian random cutset forests. In: ISMIS (2015)
9.
Di Mauro, N., Vergari, A., Esposito, F.: Learning accurate cutset networks by exploiting decomposability. In: AIXIA (2015)
10.
Geurts, P., Ernst, D., Wehenkel, L.: Extremely randomized trees. MLJ 63, 3–42 (2006)MATH
11.
Haaren, J.V., Davis, J.: Markov network structure learning: a randomized feature generation approach. In: AAAI (2012)
12.
13.
Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge (2009)MATH
14.
Larochelle, H., Murray, I.: The neural autoregressive distribution estimator. In: AISTATS (2011)
15.
Lowd, D., Davis, J.: Learning Markov network structure with decision trees. In: ICDM (2010)
16.
Lowd, D., Domingos, P.: Naive Bayes models for probability estimation. In: ICML (2005)
17.
Lowd, D., Rooshenas, A.: Learning Markov networks with arithmetic circuits. In: AISTATS (2013)
18.
19.
Poon, H., Domingos, P.: Sum-product network: a new deep architecture. In: NIPS Workshop on Deep Learning and Unsupervised Feature Learning (2011)
20.
Rahman, T., Gogate, V.: Learning ensembles of cutset networks. In: AAAI (2016)
21.
Rahman, T., Kothalkar, P., Gogate, V.: Cutset networks: a simple, tractable, and scalable approach for improving the accuracy of Chow-Liu trees. In: ECML/PKDD (2014)
22.
Rooshenas, A., Lowd, D.: Learning sum-product networks with direct and indirect variable interactions. In: ICML, pp. 710–718 (2014)
23.
24.
Scanagatta, M., Corani, G., de Campos, C.P., Zaffalon, M.: Learning treewidth-bounded Bayesian networks with thousands of variables. In: NIPS (2016)
25.
Theis, L., van den Oord, A., Bethge, M.: A note on the evaluation of generative models. In: ICLR (2016)
26.
Vergari, A., Di Mauro, N., Esposito, F.: Simplifying, regularizing and strengthening sum-product network structure learning. In: ECML/PKDD (2015)
Metadata
Title
Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks
Authors
Nicola Di Mauro
Antonio Vergari
Teresa M. A. Basile
Floriana Esposito
Copyright Year
2017
Book
Machine Learning and Knowledge Discovery in Databases

Print ISBN: 978-3-319-71248-2

Electronic ISBN: 978-3-319-71249-9

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-71249-9_13

Premium Partner

    Image Credits