Bayesian Credible Intervals for Online and Active Learning of Classification Trees

Abstract : —Classification trees have been extensively studied for decades. In the online learning scenario, a whole class of algorithms for decision trees has been introduced, called incremental decision trees. In the case where subtrees may not be discarded, an incremental decision tree can be seen as a sequential decision process, consisting in deciding to extend the existing tree or not. This problem involves an trade-off between exploration and exploitation, which is addressed in recent work with the use of Hoeffding's bounds. This paper proposes to use Bayesian Credible Intervals instead, in order to get the most out of the knowledge of the output's distribution's shape. It also studies the case of Active Learning in such a tree following the Optimism in the Face of Uncertainty paradigm. Two novel algorithms are introduced for the online and active learning problems. Evaluations on real-world datasets show that these algorithms compare positively to state-of-the-art.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01225850
Contributor : Olivier Pietquin <>
Submitted on : Monday, November 9, 2015 - 3:01:20 PM
Last modification on : Wednesday, July 31, 2019 - 4:18:02 PM
Long-term archiving on : Wednesday, February 10, 2016 - 10:09:30 AM

File

ADPRL_2015_TCOP.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01225850, version 1

Citation

Timothé Collet, Olivier Pietquin. Bayesian Credible Intervals for Online and Active Learning of Classification Trees. ADPRL 2015 - Symposium on Adaptive Dynamic Programming and Reinforcement Learning., Dec 2015, Cape Town, South Africa. ⟨hal-01225850⟩

Share

Metrics

Record views

342

Files downloads

182