= Decision tree
= Deterministic Boolean query algorithm
{synonym}
A <decision tree> represents a <deterministic computation> of a known <Boolean function> $f:\{0,1\}^n\to\{0,1\}$ by inspecting <input> <bits>. Each internal <vertex> of its <binary tree> names a coordinate $i$ to query, its two outgoing <edges> carry answers 0 and 1, and each leaf carries the <output> 0 or 1. Starting at the <root of a tree>, read the named <bit>, follow its answer <edge>, and repeat until a leaf is reached. Correctness requires the leaf's label to equal $f(x)$ for every <input> $x$.<Complexity Measures and Decision Tree Complexity: A Survey by Harry Buhrman and Ronald de Wolf>[Buhrman and de Wolf, Complexity Measures and Decision Tree Complexity: A Survey, section 3.1, manuscript p. 5: deterministic trees and D(f)]{ref}
The next coordinate, or the decision to stop, can depend on earlier answers: this is adaptive querying. The same <input> always follows the same <graph path>; adaptivity does not require randomness. A correct leaf must have the same <output> for every completion of the observed <bits>. Thus a <decision tree> can stop as soon as the observations form a <query certificate>. Querying an already known coordinate adds no information, so we use <decision trees> without repeated coordinates on a <graph path>; an efficient tree also removes queries made after the <output> is already forced.
The motivation is exact computation with shortcuts. If inspecting an <input> entry is expensive, the question is how much of the <input> must actually be read. The <decision-tree query cost> counts these inspections, while local calculations on known values are free in this model; this cost need not equal an implementation's <time complexity>. Here the <Boolean function> is specified in advance and must be computed exactly on every <input>. <Decision tree learning> instead fits a predictor from data, with a different objective.
Back to article page
