Motivation
Knowledge acquisition asks how observations and expert judgments become a representation that can support decisions. A rule engine can apply supplied rules flawlessly while the rules themselves are too broad, contradictory or based on an omitted variable. A decision tree provides one transparent way to propose rules from labeled cases: each path records the questions asked, and each leaf records the resulting decision.
Transparency does not turn induction into deduction. A tree learned from four cases makes choices on unobserved cases too, and a pure training leaf is not proof of a universal physical law. We therefore study a finite tool completely: its input schema, split criterion, termination, rule compilation and explanation trace. We keep correctness of the tool separate from correctness of the acquired domain policy.
Definitions
Definition 27.1.1
(Training table, node and binary entropy)
A training table has finitely many rows , where assigns each of named Boolean attributes a value in and is a supplied label. Repeated rows count repeatedly. A nonempty node contains a subset of the table, with label-one fraction and binary entropy , using zero times log zero equal to zero.
Definition 27.1.2
(Information gain and leaf prediction)
Splitting on attribute partitions that subset into children of sizes . With node size , its information gain is
Empty-child terms have weight zero and require no fraction . A leaf predicts its majority label, with ties resolved as zero. An empty child receives its parent's majority as a declared fallback, not an estimate supported by observations in that child.
Definition 27.1.3
(The finite learner)
Our finite learner stops at a pure node or when no untested attribute remains. Otherwise it selects an attribute of maximum gain, breaking ties by a fixed attribute order, splits both ways and recurses without that attribute. It does not stop merely because the largest gain is zero. Every root-to-leaf path tests each attribute at most once. We use this complete finite policy to distinguish a theorem from an optional pruning heuristic.
Definition 27.1.4
(Compiled rule and explanation)
A leaf path defines a conjunction of observed attribute values. Its compiled rule has that conjunction as condition and the leaf label as conclusion. Evaluating a complete Boolean input follows exactly one path. Explanation is the tested attribute-value sequence and final leaf; it need not claim a physical cause. Partial observations require a separate policy, such as returning a label only when every completion receives the same label.
Theorem/Proposition
Theorem 27.1.5
(The entropy ledger of a finite decision tree)
For any finite tree that partitions one fixed nonempty training table, let be the fraction of all rows reaching node v and the local information gain at an internal node. Then
Every local gain is nonnegative. The total reduction is at most the root entropy and equals it exactly when every nonempty leaf is pure. This is an empirical identity about that table, not a population generalization bound.
Theorem 27.1.6
(Finite learning and exact rule compilation)
The stated learner terminates with depth at most m. Its leaf rules are mutually exclusive and exhaustive on complete Boolean inputs, and rule evaluation agrees with tree evaluation on every such input. If identical feature vectors never have conflicting training labels, the unpruned learner fits every training row, even when some intermediate gains are zero. Conflicting identical vectors cannot be fitted by any deterministic function of those attributes.
Proof sketch or proof idea
Proof
(Concavity and telescoping)
Entropy is concave: on its second derivative is , and its continuous endpoint extension preserves concavity. The parent fraction is the weighted average of child fractions, so its entropy is at least their weighted entropy. This proves gain nonnegative, including empty children through their zero weights.
Multiply each internal-node gain definition by its global weight. The negative child-entropy term then has exactly the same weight as the positive term for that child if it is internal. Summing over the finite tree cancels every internal term except the root. The remaining negative terms are the leaves, proving the ledger. Leaf entropies are nonnegative and vanish exactly for pure nonempty leaves, giving the last claims.
Proof X-ray
A local gain is only one entry in a global account
The next split can have zero gain even though later conditional splits are useful. The ledger adds gains with the probability of reaching each node. It does not require the root to explain every label distinction immediately. Stopping at zero gain is therefore an additional modeling decision, not a consequence of entropy nonnegativity.
Proof
(Termination, exclusive rules and fitting)
For termination, every recursive non-leaf call removes one remaining attribute, so depth is at most m; branching is finite. A complete input has exactly one branch at each tested attribute, hence one leaf. Its leaf condition holds. Two different leaves have a first diverging branch on the same attribute, whose required values are opposite, so no input satisfies both conditions. This proves exhaustive and mutually exclusive rule coverage and agreement with the tree.
At depth m, rows still grouped together have identical values for all attributes. Under consistent labels they are pure. Earlier pure leaves also fit their rows, so all rows are fitted. If an identical vector carries both labels, a deterministic predictor must output the same answer for both occurrences and therefore makes at least one error. A leaf majority minimizes the number of mistakes within that leaf because the two possible predictions incur respectively the opposite class counts. It does not establish which observed label was correct in the real domain.
Proof X-ray
Which hypothesis each guarantee uses
Termination uses only that each recursive call consumes one attribute, so the depth is at most . Exclusivity comes from the first branch at which two leaf paths diverge: it tests one attribute with opposite values. The fitting claim is where the hypothesis enters: only at depth are the rows still grouped guaranteed to share one feature vector, and consistent labels make such a group pure. Remove consistency and the same argument leaves a majority leaf with at least one error. Entropy plays no role in this proof; the gain rule decides which tree is built, not that these three properties hold.
Worked examples
Worked example 27.1.7
(Learning OR and accounting for every bit)
Use rows . Parent entropy is . Splitting A leaves two equally sized children with entropies one and zero, so gain is approximately bits. B has the same gain; the fixed order selects A. The A-zero child then splits on B with gain one. The weighted ledger gives , leaving pure leaves and zero training error. Root gain alone did not capture the whole explanation.
Concept lensAnalytic
Information gain as mutual information
Treat the rows of a node as an empirical distribution on pairs of attribute value and label. Then
the divergence of the joint distribution from the product of its marginals. In the OR table, and , which gives , the gain computed above. Zero gain means exactly that the attribute and the label are empirically independent in that node.
Worked example 27.1.8
(Compiling and explaining the acquired policy)
The tree has rules A equals one implies label one; A equals zero and B equals one implies label one; A equals zero and B equals zero implies label zero. Input produces trace A-zero, B-one, leaf-one. Under partial-observation semantics, knowing A equals one already forces label one for both completions of B. Knowing only A equals zero does not determine the label. The positive-rule disjunction can be simplified to , but the original path trace preserves which tests the actual tool used.
Worked example 27.1.9
(Conflicting cases reveal a representation limit)
Use rows . After every relevant split, the two identical zero-zero inputs still share a leaf with conflicting labels. Tie-to-zero incurs one error there, giving empirical error . No deterministic rule over A,B can do better than one error on those two occurrences. Knowledge acquisition should investigate label mistakes, time variation or an omitted measurement; increasing tree depth without adding information cannot separate identical vectors.
The executable companion tool implements this precise finite policy and emits the OR tree, leaf rules, predictions and a trace. Its core recursion is small:
function grow(rows, attributes, fallback = 0) {
if (rows.length === 0) return { label: fallback };
const majority = rows.filter(row => row.y === 1).length > rows.length / 2 ? 1 : 0;
if (rows.every(row => row.y === rows[0].y) || attributes.length === 0)
return { label: majority };
const test = attributes.reduce((best, name) =>
gain(rows, name) > gain(rows, best) ? name : best);
const rest = attributes.filter(name => name !== test);
return { test,
zero: grow(rows.filter(row => row[test] === 0), rest, majority),
one: grow(rows.filter(row => row[test] === 1), rest, majority) };
}
The companion supplies entropy/gain, schema validation, prediction and rule extraction as well; the displayed function is its learner, not a standalone claim that undefined helpers execute themselves. Attribute order resolves exact computed ties. Floating-point entropy arithmetic can affect extremely close comparisons, while termination and tree-to-rule equivalence hold for any selected remaining attribute. A robust application should record its exact data, schema, tie policy and output rather than describing the result only as “AI recommends.”
Empty branches especially separate tool policy from evidence. If the training table never contains some attribute combination, the recursion must still define what a complete input reaching that branch receives. Reusing the parent's majority keeps the function total but creates no new observation. An explanation interface should show that such an answer comes from a fallback leaf, so the user can tell that the conclusion is a policy extension rather than the verdict of many matching cases.
Knowledge acquisition should also keep the data version and the evidence for each label. After an expert changes one label, even the root split of the tree can change, so one cannot edit a single displayed rule and pretend it is still the original training result. Re-run the same recorded policy, compare old and new rules and cases, and let domain review decide whether to accept the change. A replayable tool makes these decisions inspectable; it does not replace them.
Common mistakes
Counterexample mode
Zero immediate gain can hide a useful interaction
For XOR on all four Boolean inputs, both A and B have zero root gain: each child is still equally mixed. Splitting A nevertheless allows B to create pure leaves in both children, giving total entropy reduction one bit. A rule that stops whenever all current gains vanish returns a constant majority and misses a perfectly representable interaction. Our learner continues until purity or attribute exhaustion; pruning is a separate choice.
Common mistake
(Reading tree rules as laws of the domain)
The tool's rules are consequences of the constructed tree, not logical consequences of the finite observations in an unrestricted world. Many other functions agree on an incomplete table and disagree elsewhere. Expert review should examine proposed conditions, possible confounders and costs of false recommendations. An acquired diagnostic policy should be tested on independent cases drawn from the intended use setting before claiming predictive accuracy.
Common mistake
(Zero for a missing value, frequency for a probability)
Do not silently map a missing sensor value to zero. In this schema zero is an observed Boolean value. The executable rejects malformed complete inputs; a partial-input interface needs its own uncertainty semantics. Likewise a leaf's label frequency is not automatically a calibrated probability, particularly after selecting the tree on the same data. Small training error and a convincing explanation trace answer different questions from external reliability. Every fallback decision should also be traceable: an empty leaf must not be described as an expert conclusion validated by data.
Summary
Finite decision-tree learning can be specified and checked completely. Entropy reductions telescope through the tree; depth decreases as attributes are consumed; compiled leaf rules exactly preserve the learned function and its traces. Those are deductive tool guarantees. Whether the acquired function represents the domain remains an inductive question requiring adequate features, trustworthy labels and new evidence.
Exercises
Exercise 27.1.10
(For XOR on the complete four-row table, compute the root entropy, both root gains, the two conditional gains after splitting on , and the weighted entropy ledger.)
Core
The rows are .
Solution(3)
- 1
Compute the root entropy and the root gains
Two rows have label zero and two have label one, so bit. Splitting on gives two children with one row of each label, each of entropy one, so . The same holds for .
- 2
Compute the conditional gains after splitting on
Key step
Each child of has two rows with different labels, and separates them into pure leaves. Each child has entropy one and its two grandchildren have entropy zero, so each conditional gain is .
Because: A zero gain at the root does not mean that the next question is useless.
- 3
Assemble the weighted ledger
Each child has global weight one half, so the ledger is . This equals the root entropy, and every leaf is pure with entropy zero. A zero first gain is consistent with a useful two-step partition.
Exercise 27.1.11
(A node has eight rows, four of each label. A split produces class counts and . Find the information gain and the majority-class training error after that split. Are those two numerical quantities interchangeable?)
Foundation
Solution(3)
- 1
Compute the gain
The parent entropy is . Each child has four rows with label fractions or , so its entropy is bit. Both children carry weight one half, hence bit.
- 2
Compute the training error
Each child predicts its majority label and makes one mistake, so the error is .
- 3
Compare the two quantities
The first is an entropy reduction in bits and the second is a misclassification fraction. Their formulas and units differ, and neither is a guaranteed future error rate.
Exercise 27.1.12
(A tree tests and returns zero when ; when it tests , returning one for and zero for . Write all leaf rules, simplify the positive condition, and evaluate the partial observation with unknown.)
Core
Solution(3)
- 1
Write the leaf rules
The three leaves give: implies label zero; and implies label one; and implies label zero.
- 2
Simplify the positive condition
Only one leaf predicts one, so the positive condition is and , that is, .
- 3
Apply the all-completions policy to
With and the label is zero, while with and the label is one. The completions disagree, so the policy returns undetermined. Treating unknown as false would answer a different question.
Because: A label is returned only if every completion of the unknown attribute gives the same label.
Exercise 27.1.13
(Two training rows have exactly the same complete feature vector but opposite labels. Prove that no deterministic tree or rule function over these features fits both. Does adding more copies of one label remove the representation conflict?)
SynthesisProof
Solution(3)
- 1
Use that a deterministic function has one output per vector
Let be any deterministic function of the features and let be the shared vector, so is a single label.
- 2
Compare with the two labels
Key step
One occurrence of carries label zero and the other label one, so differs from at least one of them. Hence makes at least one error on these two rows, and no such fits both.
- 3
Examine repeated copies
∎Adding copies of one label changes the majority and the fraction of mistakes, but both conflicting labels remain present, so one output still cannot equal both. A new informative feature or a revised interpretation of the data is needed to address the conflict itself.