An Approximate Algorithm for Decision Tree Design

Satoru OHTA

An Approximate Algorithm for Decision Tree Design

Satoru OHTA

Full Text Views

0

Cite this

Summary :

Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.5 pp.622-630

Publication Date: 1992/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Optimization Techniques

Cite this

Copy

Satoru OHTA, "An Approximate Algorithm for Decision Tree Design" in IEICE TRANSACTIONS on Fundamentals, vol. E75-A, no. 5, pp. 622-630, May 1992, doi: .
Abstract: Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_5_622/_p

Copy

@ARTICLE{e75-a_5_622,
author={Satoru OHTA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Approximate Algorithm for Decision Tree Design},
year={1992},
volume={E75-A},
number={5},
pages={622-630},
abstract={Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - An Approximate Algorithm for Decision Tree Design
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 622
EP - 630
AU - Satoru OHTA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1992
AB - Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.
ER -