Minimizing Depth of Decision Trees with Hypotheses

Mohammad Azad; Igor Chikalov; Shahid Hussain; Mikhail Moshkov

doi:10.1007/978-3-030-87334-9_11

Minimizing Depth of Decision Trees with Hypotheses

Mohammad Azad, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. Such decision trees are similar to ones studied in exact learning, where membership and equivalence queries are allowed. We present dynamic programming algorithms for minimization of the depth of above decision trees and discuss results of computer experiments on various data sets and randomly generated Boolean functions.

Original language	English (US)
Title of host publication	Rough Sets
Publisher	Springer International Publishing
Pages	123-133
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-030-87334-9_11
State	Published - Sep 16 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-09-21
Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors are greatly indebted to anonymous reviewers for useful comments and suggestions.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-87334-9_11

https://repository.kaust.edu.sa/bitstream/10754/671321/1/depth.pdf

Cite this

@inproceedings{b9aad399ba7e46d6b9538c7b1ecab0d1,

title = "Minimizing Depth of Decision Trees with Hypotheses",

abstract = "In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. Such decision trees are similar to ones studied in exact learning, where membership and equivalence queries are allowed. We present dynamic programming algorithms for minimization of the depth of above decision trees and discuss results of computer experiments on various data sets and randomly generated Boolean functions.",

author = "Mohammad Azad and Igor Chikalov and Shahid Hussain and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2021-09-21 Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors are greatly indebted to anonymous reviewers for useful comments and suggestions.",

year = "2021",

month = sep,

day = "16",

doi = "10.1007/978-3-030-87334-9_11",

language = "English (US)",

pages = "123--133",

booktitle = "Rough Sets",

publisher = "Springer International Publishing",

}

TY - GEN

T1 - Minimizing Depth of Decision Trees with Hypotheses

AU - Azad, Mohammad

AU - Chikalov, Igor

AU - Hussain, Shahid

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2021-09-21 Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors are greatly indebted to anonymous reviewers for useful comments and suggestions.

PY - 2021/9/16

Y1 - 2021/9/16

N2 - In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. Such decision trees are similar to ones studied in exact learning, where membership and equivalence queries are allowed. We present dynamic programming algorithms for minimization of the depth of above decision trees and discuss results of computer experiments on various data sets and randomly generated Boolean functions.

AB - In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. Such decision trees are similar to ones studied in exact learning, where membership and equivalence queries are allowed. We present dynamic programming algorithms for minimization of the depth of above decision trees and discuss results of computer experiments on various data sets and randomly generated Boolean functions.

UR - http://hdl.handle.net/10754/671321

UR - https://link.springer.com/10.1007/978-3-030-87334-9_11

U2 - 10.1007/978-3-030-87334-9_11

DO - 10.1007/978-3-030-87334-9_11

M3 - Conference contribution

SP - 123

EP - 133

BT - Rough Sets

PB - Springer International Publishing

ER -

Minimizing Depth of Decision Trees with Hypotheses

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this