03 Text Classification - Chunk 11 (s.301-330)

Overview

This chunk covers decision tree learning for classification. It starts by framing a decision tree as function approximation (s.301-302), then shows how a tree can be built automatically with the greedy ID3 algorithm (s.303-310), using entropy / information gain on the Play Tennis toy data (s.311-316). It then handles continuous attributes by thresholding (s.317-320), the bias of information gain toward many-valued attributes fixed by Gain Ratio (s.321), and the alternative Gini impurity / Gini gain criterion with a worked exercise (s.322-327). It closes with the pros and cons of decision trees (s.328) and opens the overfitting section (s.329-330).

Detailed notes

1. Decision tree as function approximation (s.301-302)

Problem setting (s.301):
- Set of possible instances $X$ ; each instance $x \in X$ is a feature vector, e.g. <humidity: low, wind: weak, outlook: rain, temp: hot>.
- Unknown target function $f : X \to Y$ ; “a decision tree maps x to y”.
- Set of function hypotheses $H = {h ∣ h : X \to Y}$ ; each hypothesis is a decision tree that sorts x to a leaf and assigns the leaf’s corresponding y.
Input: training examples ${< x^{i}, y^{i} >}$ of the unknown target function $f$ (s.301).
Output: a hypothesis $h \in H$ that best approximates $f$ , i.e. “the decision tree that fits the data best” (s.301).
Quick questions (s.302), posed with $X = [x_{1}, x_{2}, x_{3}, x_{4}]$ boolean-valued (no answers on the slide):
1. How to represent $x_{1} \land x_{2} \land x_{4}$ as a decision tree?
2. How to represent $x_{1} \lor x_{3}$ ?
3. Can a decision tree represent every boolean function over any number of boolean variables?
- Added context
Answers (not on the slides): AND = a chain of tests where any “false” leads to a No leaf and only all-true reaches Yes; OR = test $x_{1}$ , if true → Yes, else test $x_{3}$ . Yes, a tree can represent any boolean function (worst case one leaf per input combination, i.e. exponential size).

2. Can a good tree be built automatically? (s.303-305)

s.303 is the section divider “Decision Tree: How to Build and Use”.
We can always come up with some decision tree for a dataset: pick any feature not used above, branch on its values, recursively. But starting with a random feature may lead to a large and complex tree (s.304).
Preference for short trees: “a simple consistent hypothesis is more likely to be true” (s.304) - an Occam’s-razor style argument.
Toy example: Play Tennis (s.305): 14 training rows with features/attributes Outlook, Temperature, Humidity, Windy (red box) and the label Play (blue box).

3. Poor vs good tree, and the build algorithm (s.306-307)

A poor decision tree (s.306) uses Wind at the root and then repeats Outlook/Humidity/Temperature tests in many places; it is large, has repeated attributes along branches and even leaves labelled “None” - the point is that a random attribute order gives a big, complex tree.
Algorithm for building a decision tree (s.307): node = root, then main loop:
1. Decide the “best” attribute/feature (say $A$ ) for the next node;
2. For each value of $A$ , create a new descendant of the node;
3. Partition the training examples to the leaf nodes;
4. IF training examples are perfectly classified THEN STOP; ELSE iterate over the new leaf nodes.
Open question on the slide: “How to select the ‘optimal’ attribute?“

4. Learning process and ID3 (s.308-310)

Finding the smallest decision tree is intractable; a simple heuristic algorithm does a good job of finding small trees: Inductive Decision Tree algorithm 3 (ID3) (s.308).
Concept - ID3 (s.309): well-known algorithm using a top-down greedy search through the hypothesis space; designed to handle large training sets with many attributes; tries to generate fairly simple trees but is not guaranteed to produce the best one.
Search heuristic (s.310): the central choice is which attribute to test at each node - the attribute most useful for classifying examples. ID3 defines a statistical property, information gain, measuring how well an attribute separates the training examples according to their target classification.

5. Information gain recap (s.311)

Quantity	Formula (as on slide)	Intuition
Concept - Entropy	$E (X) = - \sum_{i = 1}^{K} p (X = X_{i}) lo g_{2} p (X = X_{i})$	uncertainty of X, information contained in X, expected information bits required to represent X
Conditional entropy	$E (X ∣ Y) = \sum_{i} p (Y = Y_{i}) E (X ∣ Y = Y_{i})$	given y, how much uncertainty remains in X
Mutual information = Concept - Information Gain	$I (X, Y) = E (X) - E (X ∣ Y) = E (Y) - E (Y ∣ X)$	how much knowing Y reduces uncertainty about X, and vice versa

6. Worked example: splitting Play Tennis by information gain (s.312-314)

Root data: $S = [9 +, 5 -]$ (9 Yes, 5 No), $E = - \frac{9}{14} lo g_{2} \frac{9}{14} - \frac{5}{14} lo g_{2} \frac{5}{14} = 0.940$ (s.312). Candidate splits compared: Humidity (high / normal) and Outlook (sunny / overcast / rainy). Rows labelled $E (X)$ , $E (X ∣ Y)$ , $I (X, Y)$ guide the computation.
Child entropies (s.313):
- Humidity=high: $S = [3 +, 4 -]$ , $E = 0.985$ ; Humidity=normal: $S = [6 +, 1 -]$ , $E = 0.592$ .
- Outlook=sunny: $S = [2 +, 3 -]$ , $E = 0.971$ ; overcast: $S = [4 +, 0 -]$ , $E = 0.0$ ; rainy: $S = [3 +, 2 -]$ , $E = 0.971$ (with $E = - \frac{3}{5} lo g_{2} \frac{3}{5} - \frac{2}{5} lo g_{2} \frac{2}{5} = 0.971$ ).
Information gain (s.314):
- Humidity: $I = 0.940 - 0.5 \cdot 0.985 - 0.5 \cdot 0.592 = 0.151$ .
- Outlook: $I = 0.940 - 0.357 \cdot 0.971 \cdot 2 = 0.247$ .
- Outlook wins over Humidity (higher gain), so Outlook becomes the root.
Next step (s.315): the sunny branch has $S = [2 +, 3 -]$ , $E = 0.971$ and still needs a split - “Next attributes to split?” The slide highlights the 5 sunny rows in the table with dashed boxes (rows 1-2, 8-9, 11). The same procedure is repeated recursively on each impure branch.

7. Prediction with a decision tree (s.316)

Using Outlook only to build the tree: leaves are sunny $S = [2 +, 3 -]$ , overcast $S = [4 +, 0 -]$ , rainy $S = [3 +, 2 -]$ (+: yes, -: no).
Classify by majority vote at the leaf: sunny → no, overcast → yes, rainy → yes.

8. Continuous attributes (s.317-320)

Two options (s.317): (a) discretize in advance real-valued attributes into ranges such as big, medium, small; (b) for continuous attribute $A$ , split on a threshold $A < c$ , partitioning the examples into $A < c$ and $A \geq c$ . The information gain of such splits is easily computed and compared with discrete-feature splits to pick the best split.
Continuous value attribute (s.318): example table “Personal GPS tracking in 30 seconds window” with columns total distance, average accuracy, average speed, average acceleration and Mode (stop / walk). Define a discrete attribute that partitions the continuous value into intervals. Example: speeds in sample [3, 0.5, 10, 4, 0.3, 0.1, 1], test “Speed < 3?” → [0.5, 0.3, 0, 2, 1] vs [3, 10, 4]. (The slide’s “<3” list does not exactly match the sample list, e.g. it shows 0 and 2 instead of 0.1; reproduced as written.)
Training examples with continuous Temp. and Humidity (s.319): Day D1-D14 with Outlook, Temp., Humidity, Wind (Weak/Strong) and Play (Tennis).
Threshold-finding algorithm (s.320): the single threshold with highest gain is found by examining candidate choices:

for (each continuous feature A){
   Sort the examples according to their value for A;
   for (each ordered pair Xi, Xi+1 in the sorted list)
      if (the category of Xi and Xi+1 are different)
          find the midpoint of Xi and Xi+1 denoted c_i to define threshold A < c_i
}

Worked example on Temp: sorted values 64, 65, 68, 69, 70, 71, 72, 72, 75, 75, 80, 81, 83, 85 with classes + - + + + - - + + + - + + -. Candidate thresholds for Temp: 64.5, 66.5, 70.5, 72, 77.5, 80.5, 84 (a midpoint only where the class changes between neighbours).

9. Attributes with many values - Gain Ratio (s.321)

Information gain is biased toward attributes with many values. Example: using Day as the attribute splits the data perfectly into subsets of size 1 (D1: 0/1, D2: 0/1, D3: 1/0, D4: 1/0, D5: 1/0 … D14: 0/1 as yes/no counts, from the 9 yes / 5 no data), but it won’t work for new data.
Use GainRatio instead: Concept - Gain Ratio $G ain R a t i o (S, A) = \frac{G ain ( S , A )}{S pl i t I n f or ma t i o n ( S , A )}, S pl i t I n f or ma t i o n (S, A) = - \sum_{i \in V a l u es (A)} \frac{∣ S _{i} ∣}{∣ S ∣} lo g_{2} \frac{∣ S _{i} ∣}{∣ S ∣}$ SplitInformation penalizes attributes with many values. Legend: $A$ candidate attribute; $i$ possible values of $A$ ; $S$ set of examples ${X}$ ; $S_{i}$ subset where $X_{A} = i$ .

10. Gini impurity and Gini gain (s.322-327)

Gini impurity (s.322), “corresponding to entropy”: randomly pick a datapoint, then randomly classify it according to the class distribution in the dataset; the probability of classifying it incorrectly is the Gini impurity. $G = \sum_{i = 1}^{K} p (i) (1 - p (i))$ $K$ = total classes, $p (i)$ = probability of picking a sample with class $i$ . Example dataset (2-D scatter, 5 blue + 5 green): $G = 0.5 \cdot 0.5 + 0.5 \cdot 0.5 = 0.5$ .
Weighted Gini of a split (s.323, titled “Gin Impurity” on the slide): for a split with a left and right branch compute $G I_{L e f t}$ and $G I_{R i g h t}$ (marked ”?” for the student), then $G I (X) = 0.4 \cdot G I_{L e f t} (X) + 0.6 \cdot G I_{R i g h t} (X)$ - “weighting the impurity of each branch by how many elements it has”. The two plots show vertical split lines at $x = 2$ and $x \approx 1.5$ .
Gini gain (s.324): $G_{or i g ina l} = 0.5$ .
- Split at $x = 2$ : $G = 0.5 \cdot 0 + 0.5 \cdot 0 = 0$ → Gain $= 0.5 - 0 = 0.5$ .
- Split at $x = 1.5$ : left branch pure (0.4 weight), right branch has 1 blue + 5 green: $G_{r i g h t} = \frac{1}{6} (1 - \frac{1}{6}) + \frac{5}{6} (1 - \frac{5}{6}) = \frac{5}{18} = 0.278$ ; $G = 0.4 \cdot 0 + 0.6 \cdot 0.278 = 0.167$ → Gain $= 0.5 - 0.167 = 0.333$ .
- Rule: when training a decision tree, the best split is chosen by maximizing the Gini gain = original impurity minus the weighted impurities of the branches. (Concept - Gini Impurity)
Exercise (s.325): “Calculate Gini Gain for Outlook” on the Play Tennis table.
Solution (s.326): contingency table Outlook × Play (total 14): sunny 5, overcast 4, rainy 5 (the slide’s table lists sunny 3 yes/2 no and rainy 2 yes/3 no, which is swapped relative to the data on s.313 - [2+,3-] sunny, [3+,2-] rainy - but the Gini values are identical).
- $G (P l a y) = \frac{9}{14} (1 - \frac{9}{14}) + \frac{5}{14} (1 - \frac{5}{14}) = 0.4591$
- Sunny (prob 5/14): $G_{s} = \frac{3}{5} (1 - \frac{3}{5}) + \frac{2}{5} (1 - \frac{2}{5}) = 0.48$
- Overcast (prob 4/14): $G_{o} = 1 (1 - 1) = 0$
- Rainy (prob 5/14): $G_{r} = \frac{2}{5} (1 - \frac{2}{5}) + \frac{3}{5} (1 - \frac{2}{5}) = 0.48$ (as written on slide; second term should read $1 - \frac{3}{5}$ , same value)
- Gini Gain $= G (P l a y) - \frac{5}{14} G_{s} - \frac{4}{14} G_{o} - \frac{5}{14} G_{r} = 0.4591 - 0.171 - 0 - 0.171 = 0.117$ .
Other attributes (s.327): Gini Gain(Temperature) $= 0.459 - 0.4405 = 0.0185$ ; Gini Gain(Humidity) $= 0.459 - 0.3674 = 0.0916$ ; Gini Gain(Windy) $= 0.459 - 0.4286 = 0.0304$ . Outlook (0.117) is highest → chosen as the root, consistent with information gain.

11. Pros and cons of decision trees (s.328)

Pros: easy to understand (output is very easy to understand); data exploration (feature selection); less data cleaning required (not influenced by scale and missing values to a fair degree); data type is not a constraint (handles numerical and categorical variables); non-parametric method (no assumptions about the space distribution and the classifier structure); in nature can handle multiclass directly.
Cons: overfitting - “one of the most practical difficulty for decision tree models”; not ideal for continuous variables - decision trees lose information when they categorize variables into categories.

12. Overfitting (s.329-330)

s.329 is the section divider “Decision Tree: Overfitting”.
s.330 “Recap on Overfitting”: a 2-D scatter of orange vs blue points with a very irregular decision region (orange/blue background) with thin tendrils snaking around individual points. Takeaway: the model fits training noise with an overly complex boundary (no text explanation on slide; interpretation is added context).

Added context

The slide on s.330 carries no text; reading it as an illustration of overfitting follows its title “Recap on Overfitting”. The detailed treatment (pruning etc.) is expected in the next chunk.

Figures & diagrams

s.301 Play Tennis table + small tree: Outlook root; sunny → Humidity (high → No, normal → Yes); overcast → Yes; rain → Windy (true → No, false → Yes). Takeaway: a tree is a hypothesis mapping feature vectors to labels.
s.305 Play Tennis table with the feature columns boxed in red (Features/Attributes) and the Play column in blue (Label).
s.306 Poor decision tree: Wind root; Strong → Outlook (Sunny → Humidity, Overcast → Yes, Rain → No); Weak → Temperature (Hot → Outlook, Mild → Humidity → Outlook, Cool → Yes); several leaves “None”. Takeaway: bad attribute order → big, redundant tree.
s.307 Boxed pseudo-code of the tree-building main loop.
s.312-314 Two candidate splits (Humidity vs Outlook) annotated with $S$ counts, entropies, and gain values; “Outlook wins over Humidity”.
s.315 Outlook node with the sunny branch ( $S = [2 +, 3 -]$ , $E = 0.971$ ) pointing to ”?”; dashed boxes in the table mark the sunny rows.
s.316 Outlook-only tree with leaf counts and majority-vote labels.
s.318 GPS table (stop/walk) for continuous features.
s.320 Sorted Temp row with class signs and arrows marking candidate thresholds.
s.321 Day-attribute tree with 14 children D1…D14, each with a yes/no count (e.g. 0/1, 1/0), “9 yes / 5 no” at the top.
s.322-324 Scatter plots (x, y axes 0-3; blue vs green points) with vertical split lines, used to compute Gini impurity and gain.
s.330 Overfitted decision regions (orange/blue).

flowchart TD
    A[Training data at node] --> B{All examples perfectly classified?}
    B -- yes --> C[STOP - make leaf]
    B -- no --> D[Compute gain of each attribute<br/>information gain or Gini gain]
    D --> E[Pick best attribute A]
    E --> F[Create one child per value of A]
    F --> G[Partition examples to children]
    G --> A

flowchart LR
    Root[Outlook] -->|sunny S=2+,3-| H[Humidity?]
    Root -->|overcast S=4+,0-| Y[Yes]
    Root -->|rainy S=3+,2-| W[Windy?]

Key terms

Formulas

Entropy: $E (X) = - \sum_{i = 1}^{K} p (X = X_{i}) lo g_{2} p (X = X_{i})$ (s.311)
Conditional entropy: $E (X ∣ Y) = \sum_{i} p (Y = Y_{i}) E (X ∣ Y = Y_{i})$ (s.311)
Information gain: $I (X, Y) = E (X) - E (X ∣ Y) = E (Y) - E (Y ∣ X)$ (s.311)
Root entropy for Play Tennis: $E = - \frac{9}{14} lo g_{2} \frac{9}{14} - \frac{5}{14} lo g_{2} \frac{5}{14} = 0.940$ (s.312)
Gain ratio: $G ain R a t i o (S, A) = \frac{G ain ( S , A )}{S pl i t I n f or ma t i o n ( S , A )}$ ; $S pl i t I n f or ma t i o n (S, A) = - \sum_{i} \frac{∣ S _{i} ∣}{∣ S ∣} lo g_{2} \frac{∣ S _{i} ∣}{∣ S ∣}$ (s.321)
Gini impurity: $G = \sum_{i = 1}^{K} p (i) (1 - p (i))$ (s.322)
Weighted split impurity: $G I = \frac{∣ L ∣}{∣ S ∣} G I_{L e f t} + \frac{∣ R ∣}{∣ S ∣} G I_{R i g h t}$ (e.g. 0.4/0.6, s.323)
Gini gain = $G_{or i g ina l} - weighted branch impurity$ (s.324)
Numbers: IG(Humidity)=0.151, IG(Outlook)=0.247 (s.314); Gini gain Outlook 0.117, Temperature 0.0185, Humidity 0.0916, Windy 0.0304 (s.326-327).

Likely exam questions

Discuss how a decision tree is built (the ID3 main loop). Start at the root; choose the best attribute (highest information gain); create a child per attribute value; partition the examples; stop if the examples are perfectly classified, else repeat on the new leaves (s.307-310).
Why is ID3 called greedy, and does it find the optimal tree? It does a top-down greedy search choosing the locally best attribute at each node; finding the smallest tree is intractable, so ID3 gives fairly simple trees but no guarantee of the best (s.308-309).
Define entropy, conditional entropy and information gain and explain their intuition. See table in section 5 (s.311).
Compute the information gain of Humidity and Outlook on Play Tennis and decide the root. $E = 0.940$ ; IG(Humidity)=0.151, IG(Outlook)=0.247; Outlook wins (s.312-314).
How are continuous attributes handled? Discretize in advance into ranges, or use thresholds $A < c$ ; sort values, take midpoints where the class changes, compute the gain of each candidate and keep the best (s.317-320).
What is the problem with information gain on attributes with many values and how is it solved? Biased toward many-valued attributes (e.g. Day gives size-1 subsets, useless on new data); use Gain Ratio, dividing by SplitInformation, which penalizes many values (s.321).
Define Gini impurity and Gini gain; calculate Gini gain for Outlook. $G = \sum p (i) (1 - p (i))$ ; $G (P l a y) = 0.4591$ ; gain $= 0.117$ (s.322-326).
Compare entropy/information gain with Gini impurity.

Aspect	Entropy / information gain	Gini impurity / Gini gain
Measure	uncertainty in bits, $- \sum p lo g_{2} p$	probability of misclassifying a random sample, $\sum p (1 - p)$
Max for 2 balanced classes	1 bit (added context)	0.5
Split rule	maximize information gain	maximize Gini gain
Result on Play Tennis	Outlook best	Outlook best (0.117)

How does a decision tree classify a new example? Sort it down the tree to a leaf and predict the leaf’s majority class (s.316).
List advantages and disadvantages of decision trees. See s.328.

Common confusions

Entropy vs Gini: both measure impurity and both pick Outlook here, but entropy uses logs (max 1 for two classes) and Gini uses $\sum p (1 - p)$ (max 0.5).
Information gain vs gain ratio: gain alone favours many-valued attributes (Day); gain ratio divides by SplitInformation to penalize them.
Weights in the gain formula: the weighted child entropy uses the fraction of examples going to each branch (Humidity 7/14 each = 0.5; Outlook 5/14 = 0.357), not equal weights per branch in general.
Thresholds are midpoints between neighbours of different class only - not between every pair of values (s.320).
Greedy ≠ optimal: ID3 does not guarantee the smallest tree (s.309).
Multiclass: decision trees handle it directly; no one-vs-rest needed (s.328).

Slide coverage

Slide	Content	Covered in
301	Function approximation: problem setting, input/output, Play Tennis table + tree	§1, Figures
302	Quick questions: AND / OR / any boolean function	§1
303	Divider: Decision Tree: How to Build and Use	§2
304	Can a good tree be built automatically; prefer short trees	§2
305	Toy example Play Tennis: features vs label	§2
306	Poor decision tree (Wind root)	§3
307	Algorithm for building a decision tree	§3
308	Learning process: smallest tree intractable, ID3	§4
309	ID3 properties	§4
310	Search heuristic in ID3: information gain	§4
311	Information gain recap: entropy, conditional entropy, mutual information	§5
312	Information gain splitting: root entropy 0.940, Humidity vs Outlook	§6
313	Child entropies for each split	§6
314	IG values 0.151 vs 0.247, Outlook wins	§6
315	Next step: split sunny branch	§6
316	Prediction by majority vote	§7
317	Continuous attributes: discretize or threshold	§8
318	GPS continuous attribute example	§8
319	Training examples with continuous Temp/Humidity	§8
320	Threshold algorithm + Temp thresholds	§8
321	Many-valued attributes, Gain Ratio	§9
322	Gini impurity definition and formula	§10
323	Weighted Gini of a split	§10
324	Gini gain example (0.5 and 0.333)	§10
325	Exercise: Gini gain for Outlook	§10
326	Exercise solution: 0.117	§10
327	Gini gain for Temperature, Humidity, Windy	§10
328	Decision tree pros and cons	§11
329	Divider: Decision Tree: Overfitting	§12
330	Recap on overfitting: irregular decision regions	§12

Previous: 03 Text Classification - Chunk 10 (s.271-300) | Next: 03 Text Classification - Chunk 12 (s.331-360) | Up: 03 Text Classification - Index

Khaled Notes

Explorer

03 Text Classification - Chunk 11 (s.301-330)

03 Text Classification - Chunk 11 (s.301-330)

Overview

Detailed notes

1. Decision tree as function approximation (s.301-302)

2. Can a good tree be built automatically? (s.303-305)

3. Poor vs good tree, and the build algorithm (s.306-307)

4. Learning process and ID3 (s.308-310)

5. Information gain recap (s.311)

6. Worked example: splitting Play Tennis by information gain (s.312-314)

7. Prediction with a decision tree (s.316)

8. Continuous attributes (s.317-320)

9. Attributes with many values - Gain Ratio (s.321)

10. Gini impurity and Gini gain (s.322-327)

11. Pros and cons of decision trees (s.328)

12. Overfitting (s.329-330)

Figures & diagrams

Key terms

Formulas

Likely exam questions

Common confusions

Slide coverage

Graph View

Table of Contents

Backlinks