A Tighter Error Bound for Decision Tree Learning Using PAC Learnability

Pichuka, Chaithanya; Bapi, Raju S.; Bhagvati, Chakravarthy; Pujari, Arun K.; Deekshatulu, Bulusu Lakshmana

A Tighter Error Bound for Decision Tree Learning Using PAC Learnability

Chaithanya Pichuka, Raju S. Bapi, Chakravarthy Bhagvati, Arun K. Pujari, Bulusu Lakshmana Deekshatulu

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1011-1015.

Abstract

Error bounds for decision trees are generally based on depth or breadth of the tree. In this paper, we propose a bound for error rate that depends both on the depth and the breadth of a specific decision tree constructed from the training samples. This bound is derived from sample complexity estimate based on PAC learnability. The proposed bound is compared with other traditional error bounds on several machine learning benchmark data sets as well as on an image data set used in Content Based Image Retrieval (CBIR). Experimental results demonstrate that the proposed bound gives tighter estimation of the empirical error.

Chaithanya Pichuka, Raju S. Bapi, Chakravarthy Bhagvati, Arun K. Pujari, and Bulusu Lakshmana Deekshatulu. 2007. A Tighter Error Bound for Decision Tree Learning Using PAC Learnability. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 1011–1015. https://ijcai.org/proceedings/2007/163

@inproceedings{ijcai2007p163,
  title     = {A Tighter Error Bound for Decision Tree Learning Using PAC Learnability},
  author    = {Pichuka, Chaithanya and Bapi, Raju S. and Bhagvati, Chakravarthy and Pujari, Arun K. and Deekshatulu, Bulusu Lakshmana},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {1011--1015},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/163},
}

TY  - CPAPER
TI  - A Tighter Error Bound for Decision Tree Learning Using PAC Learnability
AU  - Pichuka, Chaithanya
AU  - Bapi, Raju S.
AU  - Bhagvati, Chakravarthy
AU  - Pujari, Arun K.
AU  - Deekshatulu, Bulusu Lakshmana
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 1011
EP  - 1015
UR  - https://ijcai.org/proceedings/2007/163
ER  -