This note covers Lecture 06, slides 1–18, with the main material presented in slides 1–17. This part of the lecture centers on a fundamental question: how can we determine whether a feature is useful for predicting a class label? The lecture begins with the prediction task and considers what it means for a feature to provide useful information. It then introduces uncertainty as a way to formalize this idea. Within this framework, entropy measures the uncertainty in the class label, while mutual information measures how much that uncertainty is reduced after observing a feature. These quantities can therefore be used to compare and rank features before fitting a classifier.

In organizing these notes, I also included several derivations and simple Python examples to illustrate the relationships among entropy, mutual information, and feature scoring, and to make the underlying calculations more concrete.

1. Supervised Classification and Feature Selection (Slides 3–8)

1.1 Data and Notation for Supervised Classification

In supervised classification, we learn from training samples that pair an input vector with an observed class label. A dataset of these pairs has the form:

Here, $n$ is the number of samples, $d$ is the number of features, and $K$ is the number of classes. The superscript $r$ identifies a sample, while the subscript $i$ in $x_i^{(r)}$ identifies a feature of that sample.

When discussing the distributions underlying these observations, we use uppercase $X_i$ and $Y$ for the feature and label random variables, and lowercase symbols for their values. The binary examples use class labels $0$ and $1$.

From these labeled samples, we learn a mapping $f:\mathcal{X}\to\mathcal{Y}$ that predicts the label associated with a new input.

1.2 The Purpose of Feature Selection

In the email example on slide 6, we represent each email using indicators of whether particular words or phrases occur. Some of these indicators help distinguish spam from other emails, whereas others are equally common across classes and contribute little to that distinction.

Feature selection retains a subset of these original variables rather than using every available input. This differs from PCA, which combines inputs to construct new coordinates. By keeping a smaller set of clearly defined variables, we can more readily identify the information used by the model.

To decide which variables to retain, we need to assess how much each one tells us about the label. Before we observe a feature, we use the overall label distribution to describe the uncertainty in our prediction. Once we know the feature’s value, we instead use the label distribution conditional on that value. The criterion on slide 8 compares the uncertainty in these two cases and evaluates the feature by the average reduction.

2. Measuring Uncertainty with Entropy (Slides 9–11)

2.1 From the Label Distribution to a Measure of Uncertainty

We begin with the uncertainty that remains before we use any features. At this stage, our prediction depends only on the probabilities of the possible classes, which we denote by:

If most of the probability is assigned to one class, predicting that class will often be correct, even without observing an input. By contrast, when all classes are equally likely, the label distribution gives us no reason to favor one class over another, so the label is more uncertain.

To quantify this uncertainty, we assign an outcome with probability $p_k$ the information content $-\log_2 p_k$, which is larger for less likely outcomes. Averaging this quantity over the possible labels gives Shannon entropy:

All logarithms use base 2, so discrete entropy and mutual information are measured in bits. For zero-probability outcomes, we use the convention $0\log_2 0=0$.

On slide 9, the coding interpretation gives the same expression another meaning. Here, $-\log_2 p_k$ is the ideal length associated with an outcome, and entropy averages these lengths to describe the theoretical limit on the number of bits per symbol in efficient lossless encoding.

2.2 High and Low Entropy

The contrast between concentrated and uniform distributions corresponds to the low- and high-entropy cases on slide 10. For a fixed set of $K$ possible classes, entropy satisfies:

When one class has probability 1, the label is certain and entropy reaches the lower bound. At the other extreme, all classes have probability $\frac{1}{K}$, giving the upper bound $H(Y)=\log_2 K$. In particular, two equally likely classes give a label entropy of 1 bit.

We can see the same pattern in the six-toss coin example from slide 11. The table lists several empirical distributions and their entropies, including the balanced case:

For the second row, substituting the observed proportions of heads and tails into the entropy formula, we have:

These calculations describe the empirical distributions obtained from the observations. Thus, six tails give zero empirical entropy, but they do not establish that the coin’s true probability of heads is zero.

3. Continuous Variables and Differential Entropy (Slide 9)

The entropy formula above sums over discrete outcomes, but some variables, such as attendance, can be modeled as continuous. Slide 9 introduces differential entropy for this case. If $f_Z$ is the probability density of a continuous variable $Z$, its differential entropy is:

Here, lowercase $h$ distinguishes differential entropy from discrete entropy. Because $f_Z(z)$ is a density rather than the probability of the point $z$, probabilities must be obtained by integrating over a range of values. For example:

For classification, however, a continuous feature $X_i$ does not make the label $Y$ continuous. We still measure label uncertainty with $H(Y)$; it is the average over feature values that must be computed using a density.

4. Conditional Entropy (Slide 12)

4.1 Fixing the Observed Feature Value

To measure uncertainty after observing a feature, we replace the overall label probabilities with conditional probabilities. When we observe $X=x$, the relevant label distribution is $P(Y=y\mid X=x)$. Applying the entropy definition to this distribution gives

This calculation describes the uncertainty after one particular observation. Other values of $X$ may leave different amounts of uncertainty about $Y$, so a single observation does not yet describe the feature as a whole.

4.2 Averaging over Possible Feature Values

To obtain one measure for the feature, we average the label entropies across its possible values, weighting each by the probability of observing that value. For discrete $X$, this gives

When $X$ is continuous, we perform the same averaging with its density, replacing the outer sum with an integral:

The inner sum remains unchanged because the label is still discrete; only the average over feature values becomes an integral. When the target is also continuous, the inner calculation changes as well. That case, also shown on slide 12, is covered in Supplement A.

5. A Joint Distribution Worked Step by Step (Slides 13–14)

We can obtain both the conditional probabilities and their averaging weights from a joint probability table. Slides 13–14 use the following joint distribution, shown here with its marginal probabilities:

Each interior cell contains a joint probability, so the upper-left entry $1/4$ represents $P(X=0,Y=0)$. To obtain the conditional probability $P(Y=0\mid X=0)$, we must divide this entry by its row total. The row and column totals give the marginal probabilities of $X$ and $Y$, respectively.

5.1 Joint Entropy of a Variable Pair

Before conditioning on either variable, we can apply the entropy definition to the pair $(X,Y)$ as a single outcome. Its possible values are $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$, so the joint entropy on slide 13 is:

The zero-probability outcome contributes zero and is omitted from the expanded sum.

5.2 Computing $H(Y\mid X)$ by Row Normalization and Averaging

To condition on $X=x$, we restrict attention to the corresponding row and divide each entry by that row’s total probability:

For the first row, where $X=0$, we have:

The two labels are equally likely within this row, so $H(Y\mid X=0)=1$. In the second row, where $X=1$, the conditional probabilities are $1$ and $0$, giving $H(Y\mid X=1)=0$.

Since each row occurs with probability $1/2$, we weight the two entropies equally:

The same row probability appears in both stages of the calculation. It first normalizes the row into a conditional distribution, then weights that distribution’s entropy in the overall average.

5.3 Computing $H(X\mid Y)$ by Column Normalization and Averaging

For the reverse calculation, we condition on $Y$ and work with columns instead of rows. When $Y=0$, normalizing the first column, we have:

In the second column, where $Y=1$, $X$ must be 0, so the conditional entropy is zero. We then average the two column entropies using their respective column probabilities:

These results show that $H(Y\mid X)$ and $H(X\mid Y)$ need not be equal, since they measure uncertainty about different variables after different observations.

6. Mutual Information (Slide 15)

6.1 Mutual Information and Information Gain

We measure the information supplied by a feature by comparing the label entropy $H(Y)$ with the average entropy $H(Y\mid X)$ that remains after observing it. Their difference is the mutual information:

In the feature-selection setting, the lecture also refers to this reduction as information gain. For a discrete label, it satisfies:

The lower bound occurs when $X$ and $Y$ are independent, because observing $X$ leaves the label distribution unchanged. At the other extreme, a feature that completely determines the label leaves $H(Y\mid X)=0$, so its information gain equals $H(Y)$.

Returning to the joint distribution in Section 5, we first compute the label entropy from its marginal probabilities:

Subtracting the conditional entropy calculated earlier, we have:

The reduction applies to the average over observations, not necessarily to each observation separately. In this example, observing $X=0$ raises label entropy from about $0.8113$ bits to $1$ bit, whereas observing $X=1$ removes the uncertainty entirely. Averaging these two cases leaves $0.5$ bits of uncertainty. The inequality $H(Y\mid X)\leq H(Y)$ holds even though the first observation makes the label less certain.

6.2 Symmetry of Mutual Information

Although conditional entropy need not be symmetric, mutual information is. To see why, we use the factorization $p(x,y)=p_X(x)p(y\mid x)$ to expand the joint entropy:

Factoring the same joint distribution in the reverse direction gives $H(X,Y)=H(Y)+H(X\mid Y)$. These two forms of the entropy chain rule let us express mutual information in terms of the marginal and joint entropies:

The two conditional entropies may differ, but each is subtracted from the entropy of its own target variable. In our example, $H(X)=1$, so the reverse calculation gives $1-0.6887\approx0.3113$ bits, matching the result obtained from the label entropy.

7. Deriving the Feature Score (Slides 16–17)

7.1 Connecting $p(x_i\mid y)$ and $p(y\mid x_i)$

The definition above uses the label distribution after observing a feature. The algorithm on slide 16 instead estimates how the feature is distributed within each class. We can recover the required label probabilities from these class-conditional distributions using Bayes’ rule.

For a continuous feature $X_i$ and a discrete label $Y$, we use the notation:

Here, $\pi_k$ is a class probability, while $f_{i\mid k}$ and $f_i$ are the class-conditional and marginal feature densities. The product $\pi_k f_{i\mid k}(x)$ represents the joint distribution of feature value $x$ and class $k$. Summing these products over the classes gives the marginal density:

Dividing the class-specific joint term by this marginal density gives the conditional label probability through Bayes’ rule:

7.2 Expanding the Difference between the Two Entropies

We first rewrite the label entropy so that both entropies use the same weighting term. Each class-conditional density integrates to 1, so inserting that integral leaves the label entropy unchanged:

For the conditional entropy, we substitute the label probabilities from Bayes’ rule. Using $f_i(x)P(Y=k\mid X_i=x)=\pi_k f_{i\mid k}(x)$, we have:

Both expressions now use the same weights, so subtracting them leaves a difference of logarithms. Combining those logarithms, we have:

The final line is the feature score on slides 16–17. The derivation applies to classes with $\pi_k>0$, and the density ratio is evaluated where the relevant densities are positive. Terms with zero weight contribute zero.

The ratio compares how common a feature value is within a class with how common it is overall. If every class satisfies $f_{i\mid k}(x)=f_i(x)$, the numerator and denominator agree, so the logarithmic terms vanish and the score is zero. Individual logarithmic terms can otherwise be negative, even though the complete weighted score is nonnegative.

7.3 The Attendance Example

Slide 17 illustrates these distributions using Attendance as the feature and Statistics Score as the target. To estimate the feature score, we distinguish the three quantities by the observations used to calculate them:

In particular, we estimate $f_{i\mid6}(x)$ by first selecting students with a score of 6 and then estimating the attendance distribution within that group.

The classification setup treats a score of 6 as one discrete class. Although the illustrative table includes decimal scores, the slides do not specify how those scores are discretized or grouped. The figures illustrate the estimation process but do not provide enough information to compute a numerical mutual information value.

8. Applying Feature Selection (Slides 16–17)

The feature score depends on probabilities and densities that are usually unknown. We estimate them from labeled training data and then use the estimates to score each feature separately.

Step 1. Estimate the class probabilities. We denote the number of training samples in class $k$ by $n_k$ and estimate the class probability from its relative frequency:

Because these probabilities depend only on the labels, the same estimates are used for every feature and need to be computed only once.

Step 2. Estimate the feature distributions. For feature $i$, we use all observations to estimate $f_i$, then restrict the data to observations satisfying $y^{(r)}=k$ to estimate $f_{i\mid k}$. The lecture allows either parametric or nonparametric density estimation. For discrete features, we can use relative frequencies; for continuous features, we can use histograms or kernel density estimation.

For example, suppose a histogram bin $B_j$ has width $\Delta_j$ and contains $n_j$ samples, of which class $k$ contributes $n_{jk}$. If all classes use the same bins, the density estimates for $x\in B_j$ are

In each estimate, dividing by the sample count converts the bin count to a proportion, and dividing by the bin width converts that proportion to a density. The class-conditional estimate uses $n_k$ rather than $n$ because it describes only the samples in class $k$. This normalization is also needed for the attendance histogram on slide 17, whose vertical axis shows student counts rather than densities.

Step 3. Compute the information score. With the distributions estimated, we substitute them into $I(X_i;Y)$. For discrete features, we sum over the possible values; for continuous features, we evaluate the integral or use a numerical approximation.

Step 4. Rank and select. Repeating the calculation for $i=1,\ldots,d$ gives one score per feature. We then rank the features and retain those with high scores, such as the top $m$. The slides do not specify a universal value of $m$.

The result is a selected set of inputs. These inputs must still be used to train a classifier before we can predict labels for new samples.

9. A Small Reproducible Example

The following example uses eight observations to reproduce the joint probability table from the lecture. The counts for $(X,Y)=(0,0),(0,1),(1,0),(1,1)$ are $2,2,4,0$, respectively, so dividing each count by eight recovers the probabilities used in Section 5.

For comparison, feature $Z$ divides the same observations into two groups, each with three labels of 0 and one label of 1. Since both groups have the same label proportions, observing either value of $Z$ leaves the empirical label distribution unchanged.

The implementation uses only the Python standard library and follows the conditional-entropy calculation above. It first groups observations by the conditioning variable, computes the label entropy within each group, and then averages those entropies with weights proportional to group size.

from collections import Counter, defaultdict
from collections.abc import Hashable, Sequence
from math import log2


def entropy(values: Sequence[Hashable]) -> float:
    """Compute entropy from empirical frequencies."""
    n = len(values)
    if n == 0:
        raise ValueError("At least one observation is required.")
    return -sum(
        (count / n) * log2(count / n)
        for count in Counter(values).values()
    )


def conditional_entropy(
    target: Sequence[Hashable], given: Sequence[Hashable]
) -> float:
    """Compute H(target | given) by grouping and averaging."""
    n = len(target)
    if n == 0 or len(given) != n:
        raise ValueError("Inputs must have the same nonzero length.")
    groups = defaultdict(list)
    for target_value, given_value in zip(target, given):
        groups[given_value].append(target_value)
    return sum(
        (len(group) / n) * entropy(group)
        for group in groups.values()
    )


def mutual_information(
    feature: Sequence[Hashable], labels: Sequence[Hashable]
) -> float:
    """Compute I(feature; labels) = H(labels) - H(labels | feature)."""
    return entropy(labels) - conditional_entropy(labels, feature)


x = [0, 0, 1, 1, 0, 0, 1, 1]
y = [0, 1, 0, 0, 0, 1, 0, 0]
z = [0, 0, 0, 0, 1, 1, 1, 1]

print(f"H(X) = {entropy(x):.4f}")
print(f"H(Y) = {entropy(y):.4f}")
print(f"H(X, Y) = {entropy(list(zip(x, y))):.4f}")
print(f"H(Y | X) = {conditional_entropy(y, x):.4f}")
print(f"H(X | Y) = {conditional_entropy(x, y):.4f}")
print(f"I(X; Y) = {mutual_information(x, y):.4f}")
print(f"I(Z; Y) = {mutual_information(z, y):.4f}")

For these observations, the code produces the following entropy and mutual information values, in bits:

H(X) = 1.0000
H(Y) = 0.8113
H(X, Y) = 1.5000
H(Y | X) = 0.5000
H(X | Y) = 0.6887
I(X; Y) = 0.3113
I(Z; Y) = 0.0000

Based on these scores, selecting one feature would retain $X$ rather than $Z$. Although $X$ reduces label uncertainty, it does not remove it completely. By contrast, $Z$ leaves the label distribution unchanged and is independent of $Y$ in this empirical dataset.

Because this implementation counts exact observed values, it estimates discrete distributions. Treating every distinct floating-point measurement as a separate category would not replace the density-estimation step needed for continuous features.

Supplement A: The Scope of Differential Entropy

The main discussion assumes a discrete label $Y$, but slide 12 also considers a continuous target. If we denote that target by $Z$ and assume that $X$ is also continuous, the conditional differential entropy is

The inner integral computes the target’s differential entropy at a fixed $x$, and the outer integral averages that quantity over $x$ using its density.

Unlike discrete entropy, differential entropy depends on the measurement scale and can be negative [2]. For example, if $Z$ is uniform on $[0,a]$, then

which is negative when $0<a<1$. Differential entropy therefore cannot be interpreted directly as the number of bits needed to encode an exact real-valued observation.

Supplement B: Further Interpretation and Practical Considerations

We can also interpret mutual information by expressing the entropy difference in terms of the joint and marginal distributions. For discrete variables, expanding the logarithms gives [3]

This expression is the Kullback–Leibler divergence between the joint distribution and the product of its marginals. It is nonnegative and equals zero if and only if the variables are independent. The dependence measured by mutual information can be nonlinear, but it does not establish a causal relationship.

Although this score measures how informative each feature is on its own, ranking individual features does not guarantee the best subset. Several high-scoring features may contain overlapping information, while other information may appear only when features are combined. When using the selected features to evaluate a predictive model, we must fit the selection procedure on training data so that test labels do not influence which features are retained.

For continuous features, we can construct the estimated marginal density directly from the class-conditional estimates, weighting each by its estimated class probability:

This is the relationship obtained by the count estimates in Section 8 when all classes use the same histogram bins. Adding the class-specific counts within a bin recovers its total count and gives the mixture identity above.

References

1. Kai Wang. CSE/ISyE 6740 Lecture 06: Feature Selection and Decision Tree, September 14, 2026, slides 1–18. The coin and joint-distribution examples above are adapted from slides 11 and 13–14. Course slides.
2. Tsachy Weissman, with lecture notes by Hanchel Cheng, Kyle Chiang, and Ashwin Siripurapu. EE376A Information Theory, Lecture 9, February 5, 2015, Section 3.1. Supplementary reference for the distinction between discrete and differential entropy. Stanford lecture notes.
3. Tsachy Weissman, with teaching assistants Idoia Ochoa and Kedar Tatwawadi. EE376A: Information Theory — Lecture Notes, Stanford University, February 25, 2016, Chapter 2, especially Sections 2.2–2.3, pp. 10–11 and Eq. (2.44). Lecture notes.

1. Where This Picks Up

Course Materials I (slides 1–18) covered feature selection: given a labeled dataset, how do we measure whether a single feature $X_i$ is informative about the label $Y$, using entropy $H(Y)$, conditional entropy $H(Y \mid X_i)$, and mutual information $I(X_i, Y) = H(Y) - H(Y \mid X_i)$? Slide 18 is a one-line transition slide with no new content. Starting at slide 19, the lecture reuses that exact same information-gain idea for a new purpose: building a decision tree, a full predictive model rather than just a ranking of features.

2. The Classification Setup

Formally, we are given a dataset \(D = \{(x^1, y^1), (x^2, y^2), \ldots, (x^n, y^n)\}, \qquad x \in \mathbb{R}^d, \quad y \in \{1, 2, \ldots, K\}\) Each $x^i$ is a $d$-dimensional feature vector and $y^i$ is one of $K$ discrete class labels. The learning problem is: given a new feature vector $x$ that was not in the training set, infer its label $y$. Formally, we want to learn a function mapping $f : X \to Y$ from the training data, and then apply $f$ to new inputs.

This is a very generic setup: many different model families can be used to define $f$ (nearest neighbors, support vector machines, neural networks, decision trees, and so on), and they can disagree quite a bit on the shape of the decision boundary they draw between classes, even when they are trained on the exact same points. The lecture illustrates this with a scikit-learn comparison figure that runs ten classifiers on the same three toy 2D datasets: every method separates the red and blue points reasonably well, but a decision tree’s boundary looks visibly different from, say, a nearest-neighbor or a Gaussian-process boundary: it is made of axis-aligned rectangular blocks rather than smooth curves (see the scikit-learn classifier-comparison gallery, cited in the lecture as the source of that figure). That “blocky, axis-aligned” shape is a direct consequence of how a decision tree makes its predictions, which is the subject of the rest of this note.

3. Decision Trees as Hypotheses

A decision tree represents $f$ as a tree of yes/no questions about the features:

• Every internal node tests one attribute/feature $x_i$.
• Every branch out of a node corresponds to one possible outcome of that test (for a real-valued feature, this will mean a branch for “above a threshold” and a branch for “at or below it”; see Section 6).
• Every leaf node stores a class label $y$.

To predict the label of a new input $x$, we traverse the tree from the root to a leaf: at each internal node we look at the value of the feature it tests, follow the matching branch, and repeat, until we land on a leaf, whose label is the tree’s output.

A tiny example (not from the slides, just for illustration) makes the traversal concrete: suppose a 2-level tree first asks “is $x_i \le v$?” and then, on the “yes” branch, asks “is $x_j \le u$?”:

                 [ x_i <= v ? ]
                 /            \
              yes              no
               |                |
      [ x_j <= u ? ]        (leaf: red)
       /          \
     yes            no
      |              |
  (leaf: blue)   (leaf: red)

A new point with $x_i \le v$ and $x_j > u$ would walk left, then right, and be classified red. This is exactly the “blocky” boundary from Section 2: every leaf owns a rectangular region of feature space carved out by the thresholds on the path leading to it.

4. Why Not Just Find the Smallest Tree?

Many different trees can be built that correctly classify the same training set, including, in the extreme, a tree that grows one branch per training point and simply memorizes labels. Between all the trees that fit the data, we would prefer the smallest one: a compact tree is easier to interpret, and (by the same intuition as picking the fewest useful features in Course Materials I) is less likely to be fitting noise.

Unfortunately, finding the provably smallest decision tree consistent with a dataset is an NP-complete problem (Hyafil & Rivest, 1976). Since we cannot afford to search over all possible tree shapes, the lecture instead uses a greedy heuristic:

1. Start from an empty tree.
2. Split on whichever remaining attribute looks like the single best choice right now (by information gain).
3. Recurse: repeat the same procedure independently inside each branch created by that split.

This does not guarantee the globally smallest tree: it is a “take the best next step and never look back” strategy, but it is cheap to compute and works well in practice, which is exactly the trade-off greedy algorithms usually make against exact/optimal ones.

5. Growing the Tree by Recursion

Concretely, at any node with the (sub)dataset $D$ it is responsible for, the algorithm is:

1. Initialization: start from an empty tree holding dataset $D$.
2. For every remaining attribute (feature) $X_i$, compute its information gain against the current $D$, reusing the exact same quantity from Course Materials I: \(I(X_i, Y) = H(Y) - H(Y \mid X_i)\)
3. Pick the best attribute: \(i := \arg\max_i \, I(X_i, Y) = \arg\max_i \, \big[H(Y) - H(Y \mid X_i)\big]\)
4. Split the tree (and the dataset) into one branch per value of $X_i$: if $X_i$ takes values $v_1, v_2, \ldots$ in $D$, create sub-datasets $D_{{X_i = v_1}}, D_{{X_i = v_2}}, \ldots$, one per branch.
5. Recurse independently on each sub-dataset, exactly as if it were a brand-new, smaller classification problem.

The lecture’s running example is predicting Atlanta apartment rental price from a dataset $D$ of listings. Suppose “number of bedrooms” turns out to have the highest information gain at the root, so the tree first splits three ways on $X_i \in {0, 1, 2}$. Each branch now owns a sub-dataset (e.g. $D_{{X_i = 2}}$ contains only the 2-bedroom listings), and recursion treats that sub-dataset as its own fresh problem. If “number of bathrooms” $X_j$ has the best information gain within that sub-dataset, the $X_i = 2$ branch splits again on $X_j \in {0, 1, 2}$, and so on down the tree:

                        Root
                          |
             X_i: number of bedrooms?
        /              |               \
   X_i = 0          X_i = 1           X_i = 2
                                          |
                                X_j: number of bathrooms?
                                /         |         \
                           X_j = 0    X_j = 1     X_j = 2

Notice that the same information-gain rule from Course Materials I is being applied over and over, just on shrinking, increasingly specific subsets of the data: that reuse is exactly what makes this a recursive algorithm in the computer-science sense, not merely a repeated one.

6. Real-Valued Features Need a Different Kind of Split

The scheme above works cleanly for a feature like “number of bedrooms” that only takes a handful of distinct values. It breaks down for a real-valued feature such as room size or distance to school: giving every distinct numeric value its own branch would mean an unbounded number of branches (in principle, infinitely many). A hypothesis with that many branches is not really learning anything general: with enough branches, every leaf ends up containing at most one training example, which is memorization, not generalization, and it will overfit any dataset.

The fix is to give up on branching per exact value and instead use a binary threshold split: pick a threshold $t$ and split attribute $X_i$ into just two branches, $X_i < t$ and $X_i \ge t$. Because this only “costs” one comparison rather than enumerating every value, we can even split on the same feature more than once along a single root-to-leaf path, at different thresholds, e.g. first splitting room size at 1000 ft², and later, further down that branch, splitting the remaining listings again at 600 ft²:

                     Root
                       |
             X_i: number of bedrooms?
                       |
                   X_i = 2
                       |
           X_j: room size > 1000 ft²?
              /                  \
      (< 1000 ft²)           (>= 1000 ft², leaf)
             |
   X_k: room size > 600 ft²?
       /              \
 (< 600 ft², leaf)  (>= 600 ft², leaf)

7. Choosing the Threshold

Picking a good threshold $t$ sounds like it requires searching over the real line, but it does not: only a finite number of candidate thresholds are ever worth checking. Sort the training examples by the value of $X_i$; as $t$ sweeps from one sorted value to the next, the resulting left/right split (and therefore its information gain) only changes at points where $t$ crosses over a training example. Furthermore, if two adjacent sorted examples have the same label, there is nothing to gain by placing a threshold between them (both examples would already end up on the same side no matter which of the two neighboring gaps you pick, so the split’s quality is identical). So the only candidate thresholds worth testing are the midpoints between adjacent, sorted examples whose labels differ.

With candidate thresholds in hand, the information gain formula from Section 5 simply gets an extra condition attached to it: \(I(X_i > t, Y) = H(Y) - H(Y \mid X_i > t)\) and we search jointly over both the feature and the threshold: \(i, t := \arg\max_{i,\,t} \; I(X_i > t, Y) = \arg\max_{i,\,t} \; \big[H(Y) - H(Y \mid X_i > t)\big]\)

Worked example. To make this concrete, here is a small toy dataset (not from the slides) of 6 students, “hours studied” versus pass/fail on a quiz:

Overall there are 4 fails and 2 passes, so (using the same entropy formula as Course Materials I): \(H(Y) = -\tfrac{4}{6}\log_2\tfrac{4}{6} - \tfrac{2}{6}\log_2\tfrac{2}{6} \approx 0.918 \text{ bits}\) Reading down the sorted list, the label changes between hours 3 and 4 (Fail → Pass), between 4 and 5 (Pass → Fail), and between 5 and 6 (Fail → Pass): three label changes, so there are exactly three candidate thresholds: $t \in {3.5,\ 4.5,\ 5.5}$. The two gaps between same-label neighbors (1–2 and 2–3, both Fail) are skipped. Computing the gain at each candidate:

So $t = 3.5$ is chosen: it gives the largest reduction in entropy ($\approx 0.459$ bits), even though it does not perfectly separate the classes: the “5 hours, Fail” student ends up on the “Pass-leaning” side. That imperfection is exactly why the algorithm recurses: the right branch ${4,5,6}$ is not yet pure, so it becomes its own sub-problem and the same search (over remaining thresholds, or other features if there were any) runs again inside it, exactly as described in Section 5.

8. Putting It Together: the Full Algorithm

Combining Sections 5 through 7, the complete recursive learning procedure is:

1. Initialization: start from an empty tree with dataset $D$.
2. For every attribute $X_i$, testing every candidate threshold $t$ if it is real-valued, compute the information gain $I(X_i > t, Y) = H(Y) - H(Y \mid X_i > t)$ (or the plain $I(X_i, Y)$ from Section 5 if $X_i$ is categorical).
3. Pick the best (attribute, threshold) pair: $i, t := \arg\max_{i,t} I(X_i > t, Y)$.
4. Split the tree and the dataset at node $X_i > t$ (or by value, for a categorical attribute).
5. Create subtrees and recurse through all of them, until a stopping condition (Section 9) is met.

9. When Do We Stop Recursing?

Three candidate stopping rules come up, and only two of them are actually correct.

• Base Case One (stop): if every point remaining in this subtree already has the same label, there is nothing left to split, make a leaf with that label.
• Base Case Two (stop): if every point remaining in this subtree has identical input features (but, e.g., conflicting labels), no attribute can possibly separate them any further, make a leaf (for example, using the majority label).
• Base Case Three (a bad idea): “if every remaining attribute individually has small information gain, stop.” This sounds reasonable (if nothing helps, why keep going?) but it is a trap.

The XOR warning. Consider a label defined as $Y = X_1 \operatorname{XOR} X_2$:

Splitting on $X_1$ alone sends one 0-label and one 1-label into each branch (rows 1,2 vs. rows 3,4 are an even mix), so $H(Y \mid X_1) = H(Y)$ and the information gain is exactly zero. By symmetry, splitting on $X_2$ alone also gives zero gain. Judged one feature at a time, neither attribute looks even slightly useful. And yet splitting on both $X_1$ and $X_2$ in sequence perfectly separates the four rows into four pure leaves: the label is completely determined once both features are known. Base Case Three would stop right at the point where a single low-information split is about to reveal a perfectly informative pair of splits, because it only ever asks “does the next one split help?” instead of “could two splits from here help?”. The lesson is that information can be hidden in the interaction between features even when no individual feature carries any of it, so stopping on individually-low gain silently throws away real signal.

10. Strengths, Typical Uses, and the Overfitting Problem

Decision trees are one of the most widely used tools in machine learning, for a few concrete reasons that follow directly from everything above:

• Interpretable: the tree itself (the sequence of feature/threshold tests) is a human-readable explanation of the prediction, unlike, say, the weights of a neural network.
• Cheap to train and to use: even though the optimal tree is NP-hard to find (Section 4), the greedy heuristic only ever computes information gain a bounded number of times per node, and prediction is just one root-to-leaf walk.
• Flexible beyond plain classification: the same “split on the best question, then recurse” idea generalizes to regression (a leaf can output the average of the $y$-values that land in it instead of a majority class, with the splitting criterion swapped from entropy to something like variance reduction) and even density estimation, though this extension is only briefly gestured at in the summary slide and is developed further in general references on decision trees, e.g. the Decision tree learning overview.

The same flexibility that makes threshold splits powerful (Sections 6–7) is also the source of their biggest weakness: decision trees will overfit. Nothing in the greedy algorithm stops it from growing branches deep enough to isolate individual noisy training points (much like the “one branch per value” hypothesis that motivated switching to threshold splits in the first place, just reached one threshold at a time instead of all at once), so a fully grown tree can reach 100% training accuracy while generalizing poorly. The lecture mentions three standard remedies:

• Fixed depth / early stopping: stop growing once the tree reaches a maximum depth (or a minimum number of examples per node), even if the leaves are not yet pure, deliberately trading some training accuracy for a simpler, less overfit tree.
• Pruning: grow the tree out fully first, then remove branches after the fact if they do not actually help accuracy on held-out data.
• Ensembles of trees (random forests): train many different trees (e.g. on resampled data and/or feature subsets) and combine their predictions, rather than trusting any single greedy tree.

11. Recap

A decision tree predicts by walking root-to-leaf through a sequence of feature tests; because finding the smallest tree consistent with the data is NP-hard, it is built greedily, one information-gain-maximizing split at a time, recursing into each resulting sub-dataset exactly as in Course Materials I’s feature-scoring idea. Real-valued features are handled with binary threshold splits rather than one branch per value, and although this looks like it requires searching infinitely many thresholds, only the midpoints between adjacent, differently-labeled sorted examples ever need to be checked. Recursion stops once a subtree is pure or has no further distinguishing features, but never simply because every individual attribute looks unhelpful, since interacting features (the XOR case) can hide gain that only appears after a second split. Trees are cheap, interpretable, and flexible, but their flexibility also lets them overfit, which is why fixed depth, pruning, and ensembles like random forests are used alongside them in practice.

Sources

• Wang, K. CSE/ISyE 6740: Computational Data Analysis, Lecture 6: “Feature Selection and Decision Tree,” Georgia Tech, Fall 2026 (09/14/2026), slides 18–29. All formulas, the Atlanta rental-price example, the threshold-split diagrams, and the XOR stopping-condition example are adapted from this lecture; the worked “hours studied” threshold table in Section 7 is an original example constructed for this write-up, not taken from the slides.
• Hyafil, L., & Rivest, R. L. (1976). “Constructing Optimal Binary Decision Trees is NP-Complete.” Information Processing Letters, 5(1), 15–17. (Cited in the lecture as the source of the NP-completeness result in Section 4.)
• scikit-learn developers. “Classifier comparison.” scikit-learn documentation. https://scikit-learn.org/stable/auto_examples/classification/plot_classifier_comparison.html: source of the multi-classifier decision-boundary comparison described in Section 2 (referenced, not reproduced, here).
• “Decision tree learning.” Wikipedia. https://en.wikipedia.org/wiki/Decision_tree_learning : background reading on regression/density-estimation extensions mentioned in Section 10.
• “Decision tree pruning.” Wikipedia. https://en.wikipedia.org/wiki/Decision_tree_pruning: background reading on the pruning remedy mentioned in Section 10.

Assignment pending

Develop an optional extension, application, or related topic assigned for this lecture.

The course team will assign this section through a GitHub issue.

Random forests: intuition, advantages, and usage

1. From one decision tree to a forest

Lecture 06 builds a classification tree by repeatedly choosing a feature and threshold that reduce label uncertainty. Its final slide identifies ensembles as one way to address overfitting. A random forest develops that idea: train many randomized decision trees, then combine their predictions. This note explains the additional machinery rather than repeating the lecture’s tree-building algorithm.

A deep tree can fit complex interactions, but its splits can change substantially when the training data change slightly. This is high variance. Averaging helps when different trees make different errors. If every tree learned the same splits, adding trees would contribute little.

A forest therefore introduces diversity in two places:

1. Bootstrap samples: each tree receives a different resampled training set.
2. Random feature subsets: each node searches for its split among a randomly selected subset of features.

The objective is to retain useful individual trees while reducing how similarly they behave. Breiman’s original paper formalizes random forests using randomized tree predictors [1].

2. How a tree in the forest is trained

Let the training set be $D={(x_i,y_i)}_{i=1}^{n}$, with $x_i\in\mathbb{R}^{d}$ and $y_i\in{1,\ldots,C}$. Let $B$ be the number of trees and $m$ the number of candidate features at a node.

Bootstrap sampling

For each tree, draw $n$ training indices independently and uniformly with replacement from ${1,\ldots,n}$. Some observations appear multiple times; others are absent. For example, five draws from indices ${1,2,3,4,5}$ might give $(2,2,5,1,5)$.

For one observation, the probability of being absent from a tree’s sample is

Thus a bootstrap sample of size $n$ contains about $0.632n$ distinct observations in expectation for large $n$, not all $n$ distinct observations. The remaining observations are that tree’s out-of-bag (OOB) observations.

Random feature selection at each node

At a node, sample a candidate subset $M\subseteq{1,\ldots,d}$ of size $m$. Search for the best feature-threshold split within $M$:

where $S$ is the node’s bootstrap data, $S_L={x\in S:x_j\le t}$, and $S_R={x\in S:x_j>t}$. For classification,

Here $p_c$ is the class fraction, counting bootstrap multiplicities. This is the lecture’s information-gain split, with a restricted feature search. Gini impurity, $1-\sum_cp_c^2$, is another common choice. Our example explicitly uses entropy [2].

The feature subset is sampled again at each node, not fixed once for the whole forest. A feature absent from one node’s candidate subset can appear later. In scikit-learn, the split search may inspect additional features if needed to find a valid partition, so max_features is a nominal search limit rather than an absolute limit in every situation [2].

Trees can often be grown deeply, but constraints such as maximum depth and minimum leaf size remain useful.

Training pseudocode

For b = 1,...,B:
    Draw n training observations with replacement.
    Grow tree b on that bootstrap sample:
        At each nonterminal node:
            Sample a new subset of candidate features.
            Search candidate thresholds on those features.
            Choose the best valid impurity-reducing split.
        Stop according to purity and tree-size constraints.
Return all B trees.

Sampling observations and averaging trees is bagging. A standard random forest adds feature randomization at each split. It does not choose all thresholds arbitrarily: it searches for a good threshold among the candidate features.

3. Combining predictions

Classification

A hard-voting description is

where $T_b(x)$ is tree $b$’s predicted class. For example, predictions $(A,B,A,A,B)$ give class $A$.

Implementation detail: scikit-learn’s RandomForestClassifier instead averages each tree’s class-probability vector, then selects its largest entry [2]:

A tree’s probability is the class fraction in the leaf reached by $x$. Probability averaging and hard voting need not agree when leaves are impure. Forest probabilities are estimates, not automatically calibrated confidence statements.

Regression

For a continuous response, average the numerical predictions:

For example, predictions $(10,12,11)$ produce $11$. The trees use a regression split criterion, such as squared-error reduction, rather than class entropy.

4. Why averaging and randomness help

The following calculation is an illustrative variance model, not a general classification-error formula. Fix an input $x$. Suppose predictions $Z_b=T_b(x)$ each have variance $\sigma_T^2$ and every distinct pair has correlation $\rho$. Then

The randomness here can represent changing training samples and tree randomization. The equal-variance/equal-correlation assumptions simplify the explanation.

• Increasing $B$ reduces the $(1-\rho)/B$ term.
• If $\rho=1$, averaging gives no variance reduction.
• If $\rho=0$, variance is $\sigma_T^2/B$.
• With fixed positive $\rho$, the variance approaches a nonzero floor.

For example, take $\sigma_T^2=1$ and $B=100$. Correlation $0.8$ gives variance $0.802$, while correlation $0.1$ gives $0.109$. Diversity matters, not just tree count. Bootstrap sampling and restricted feature searches aim to reduce correlation. Restricting features too aggressively can also weaken each tree.

For squared-error regression,

This decomposition assumes prediction is evaluated on a fresh response independent of training, conditional on $x$. A forest primarily targets estimator variance; it cannot remove irreducible noise or repair every source of bias. For classification, averaging probability estimates offers a related intuition, but the variance identity is not itself a formula for misclassification error. Forests can still overfit or fail under distribution shift.

5. Advantages, tradeoffs, and important settings

Forests are useful baselines for tabular data. Standard axis-aligned regression forests predict averages of leaf responses and generally extrapolate poorly beyond the observed response range. Numerical category codes should not be mistaken for meaningful ordered measurements; encode categorical inputs appropriately for the implementation.

These controls are documented in the estimator reference [2]. Increasing the number of trees does not progressively deepen each tree; it is different from increasing max_depth.

Computational perspective. If one fitted tree has $L$ nodes, storing $B$ comparable trees costs $O(BL)$. A prediction traverses each tree, giving roughly $O(Bh)$ node decisions for depth $h$. Training depends on split search, sample sizes at nodes, and depth. With $m$ candidate features and a presorted linear-scan assumption, balanced trees suggest $O(Bmn\log n)$ split work. Re-sorting values independently at every node can add another logarithmic factor; highly unbalanced trees can be worse. This is an explanatory bound, not a universal runtime guarantee for scikit-learn.

6. Out-of-bag evaluation and feature importance

Out-of-bag predictions

For observation $i$, let $\mathcal B_i$ contain only trees whose bootstrap samples did not include it. Average those trees’ probabilities:

Compare the resulting OOB predictions with the training labels. Every observation is evaluated using a subset of trees that did not train on it. With too few trees, some observations may have no OOB trees. OOB estimates are useful internal diagnostics; repeated tuning against them can still overfit the evaluation. Keep a final test set, and use grouped or temporal evaluation when observations are not iid [2, 3].

Two notions of feature importance

Impurity importance (feature_importances_) summarizes each feature’s weighted impurity reductions across the trees. It is fast, but continuous or high-cardinality features can be favored because they offer more candidate splits.

Permutation importance measures how much a chosen evaluation score decreases when a feature’s values are shuffled, ideally on held-out validation data. It describes reliance by this fitted model, not causation or an intrinsic property of the feature. Correlated features can substitute for each other, making individual permutation importances appear small [4]. If importance is used for feature selection, perform that selection inside training/validation folds rather than using the final test set.

7. Reproducible example: classify wine cultivars

The built-in Wine dataset contains 178 observations, 13 numerical features, and three classes [5]. It requires no external download. We compare one tree with a forest using the same train/test split and the same entropy criterion.

Evaluation plan: reserve a stratified 30% test set; run five-fold stratified cross-validation only on the remaining training set; then fit each fixed configuration on all training data and evaluate the held-out test set. Stratification approximately preserves class proportions. All settings below are fixed in advance: the test scores are not used to choose them. No feature scaling or preprocessing is needed here.

The code was run with scikit-learn 1.7.2. Fixed seeds support reproducibility, but exact numbers can change with library versions. To reproduce the reported environment, use Python 3.12, scikit-learn==1.7.2, and numpy==2.5.4.

import numpy as np
import sklearn
from sklearn.base import clone
from sklearn.datasets import load_wine
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score, f1_score
from sklearn.model_selection import (
    StratifiedKFold, cross_val_score, train_test_split,
)
from sklearn.tree import DecisionTreeClassifier

X, y = load_wine(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.30, stratify=y, random_state=42,
)
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
models = {
    "Single tree": DecisionTreeClassifier(
        criterion="entropy", random_state=42,
    ),
    "Random forest": RandomForestClassifier(
        n_estimators=300,
        criterion="entropy",
        max_features="sqrt",
        min_samples_leaf=2,
        bootstrap=True,
        oob_score=True,
        random_state=42,
        n_jobs=1,
    ),
}
print(f"scikit-learn {sklearn.__version__}; NumPy {np.__version__}")
print(f"Train: {len(y_train)}; Test: {len(y_test)}")
for name, model in models.items():
    scores = cross_val_score(
        clone(model), X_train, y_train, cv=cv,
        scoring="accuracy", n_jobs=1,
    )
    model.fit(X_train, y_train)
    pred = model.predict(X_test)
    print(
        f"{name}: CV={scores.mean():.3f} +/- {scores.std():.3f}; "
        f"train={model.score(X_train, y_train):.3f}; "
        f"test={accuracy_score(y_test, pred):.3f}; "
        f"macro-F1={f1_score(y_test, pred, average='macro'):.3f}"
    )
print(f"Forest OOB accuracy: {models['Random forest'].oob_score_:.3f}")
print("First three predictions:", models["Random forest"].predict(X_test[:3]))
print(
    "First probability vector:",
    np.round(models["Random forest"].predict_proba(X_test[:1])[0], 3),
)

n_estimators=300 supplies many randomized trees. With 13 features, max_features="sqrt" nominally considers three at a split. min_samples_leaf=2 avoids single-observation leaves; the forest therefore differs from the baseline in both aggregation and leaf-size control. This is a practical comparison, not an ablation isolating one cause of improvement. n_jobs=1 keeps the example’s resource use modest; trees can also be trained in parallel.

Training accuracy measures fit to observed data; cross-validation measures performance across training partitions. Test accuracy is the final held-out classification fraction. Macro-F1 computes F1 separately for each class and averages them equally. The standard deviation across five CV folds describes fold-to-fold variability; it is not a confidence interval [3].

Results from the verified run

The split contained 124 training and 54 test observations.

The forest’s OOB accuracy was 0.976. The first three predicted labels were [0, 1, 0]; the first probability vector, rounded to three decimals, was [0.949, 0.036, 0.015].

Both models fit the training observations perfectly, while their held-out behavior differed. The forest performed better in this run, and its training-only CV scores were also higher. Nevertheless, this is one small dataset and one test split: 100% test accuracy means all 54 held-out observations were correct, not that future error is zero. The forest and baseline also differ in minimum leaf size, so these results cannot attribute the difference solely to bootstrapping or feature randomization. The similar OOB and CV scores are reassuring here, but these estimates use different fitting/evaluation procedures and need not agree in general.

predict returns class labels; predict_proba returns one column per class in the order of classes_. For other applications, choose metrics reflecting the error costs, such as recall or balanced accuracy for an imbalanced task. If tuning parameters, perform the search within the training set (for example, with GridSearchCV) and evaluate the selected procedure once on the final test set.

8. Takeaways

• Bootstrap resampling varies the observations used by each tree; feature subsampling varies the candidate splits.
• Aggregation is most useful when individual trees are informative without making identical errors.
• More trees improve ensemble stability but do not remove all bias, overfitting, or distribution shift.
• OOB scores and feature importances are useful diagnostics with distinct limitations.
• A sound comparison needs a baseline, a reproducible split, appropriate metrics, and protection against test-set leakage.

References

1. Leo Breiman (2001). Random Forests. Machine Learning, 45, 5-32. Original random-forest formulation and discussion of tree strength and dependence.
2. scikit-learn 1.7. RandomForestClassifier. Algorithm settings, probability aggregation, OOB attributes, and implementation details.
3. scikit-learn 1.7. Cross-validation: evaluating estimator performance. Train/test separation and validation strategies.
4. scikit-learn. Permutation feature importance. Impurity-importance bias, held-out permutation evaluation, and correlated-feature limitations.
5. scikit-learn 1.7. load_wine. Dataset dimensions, class labels, and original data attribution.
6. Kai Wang (2026). Lecture 06: Feature Selection and Decision Tree, CSE/ISyE 6740, Georgia Institute of Technology. Connection: greedy threshold splits, entropy/information gain, and the final slide’s introduction of ensembles as an extension.

Preparation disclosure

This draft was prepared with assistance from OpenAI Codex for organization, explanations, equations, and the example code. The example was executed and its reported results checked during preparation.