Forest Learning From Data and its Universal Coding

DOI10.1109/TIT.2018.2869215MaRDI QIDQ4562324zbMATH OpenOpenAlexFDO

Authors Joe Suzuki

Publication date 19 December 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.00566

Mathematics Subject Classification ID

Multivariate analysis (62H99) Information theory (general) (94A15)

Abstract: This paper considers structure learning from data with $n$ samples of $p$ variables, assuming that the structure is a forest, using the Chow-Liu algorithm. Specifically, for incomplete data, we construct two model selection algorithms that complete in $O(p^2)$ steps: one obtains a forest with the maximum posterior probability given the data, and the other obtains a forest that converges to the true one as $n$ increases. We show that the two forests are generally different when some values are missing. Additionally, we present estimations for benchmark data sets to demonstrate that both algorithms work in realistic situations. Moreover, we derive the conditional entropy provided that no value is missing, and we evaluate the per-sample expected redundancy for the universal coding of incomplete data in terms of the number of non-missing samples.

Recommendations

• End-to-end learning of decision trees and forests
• Decision forests: a unified framework for classification, regression, density estimation, manifold learning and semi-supervised learning
• Universal Enumerative Coding for Tree Models
• Factorization Forests
• Learning Decision Trees Using the Fourier Spectrum
• LATIN 2004: Theoretical Informatics
• Deep reservoir neural networks for trees

Cited in

(1)

• End-to-end learning of decision trees and forests

This page was built for publication: Forest Learning From Data and its Universal Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4562324)