The Hong Kong University of Science and Technology · FACULTY OF COMPUTER SCIENCE

MAIE5421 Chap.5 Decision Trees and Support Vector Machines

- one subject, every graph, every model, every mark
8 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 5 of 10 · MAIE5421

Decision Trees and Support Vector Machines

Decision trees learn the questions to ask

The lecture introduces decision trees by comparison with hand-written if-else code: a tree performs classification through a hierarchy of decisions, but it builds those decisions from data. Its root node is where every sample starts, its branches carry the decision rules, and its leaves hold the final class or value.

Trees are valued for being easy to interpret, for making no assumption about how the data is distributed, and for placing the most important features near the top.

ID3 and C4.5

ID3 chooses, at every node, the attribute whose split most reduces entropy, the measure of disorder in the class labels.

The reduction is called information gain: the entropy before the split minus the size-weighted entropy of the subsets after it. The process repeats on each subset, creating a leaf wherever a subset contains a single class. C4.5 improves on it in two ways.

It divides the gain by the split information, the entropy of the attribute itself, so that attributes with many values are not unfairly favoured, and it handles continuous attributes by testing thresholds at the midpoints between sorted values and keeping the one with the best gain ratio.

Support vector machines find the widest margin

A support vector machine separates two classes with a hyperplane.

Among all separating hyperplanes it chooses the one that maximises the distance to the closest points of each class, the support vectors, which alone determine where the boundary lies. With classes coded as plus and minus one, the margin between the two supporting planes is two divided by the length of the weight vector.

The optimisation has no closed-form solution and is solved through its dual form.

Extensions that make SVMs practical

The soft-margin SVM introduces non-negative slack variables so that some points may sit inside the margin or on the wrong side, with the size of the slack recording how far each one strays.

The non-linear SVM maps inputs into a higher-dimensional feature space where a separating hyperplane can be found. Because the method is binary by design, multi-class problems use either one-vs-rest, with one classifier per class, or one-vs-one, with one classifier for each pair of classes and a vote at prediction time.

In this chapter

What this chapter covers

  • 01

    Decision trees as learned if-else rules

  • 02

    Root nodes, branches and leaves

  • 03

    Entropy as a measure of disorder

  • 04

    Information gain and the ID3 algorithm

  • 05

    Gain ratio and split information in C4.5

  • 06

    Thresholds for continuous attributes

  • 07

    Support vectors and the maximum-margin hyperplane

  • 08

    Soft margins, feature mapping and multi-class SVMs

Worked example · free

Grow the second level of the inspection-photo decision tree

Q [7 marks]. AskSia-authored practice. Eight inspection photos are labelled usable or not by lighting (bright or dim) and edge (sharp or blurred). The four dim photos are all unusable; of the four bright photos, the three sharp ones are usable and the blurred one is not. Confirm that lighting is the better root, then compute the gain of splitting the bright branch on edge. The marks shown are an AskSia study allocation and are not the University's marking scheme.
The tree learned from eight inspection photos.The tree learned from eight inspection photos. Lighting is tested first because it gives the larger information gain; dim photos are all unusable, and among bright photos the edge sharpness settles the label.dimbrightsharpblurredLighting?No (4 of 4)Edge?Yes (3 of 3)No (1 of 1)
The tree learned from eight inspection photos. Lighting is tested first because it gives the larger information gain; dim photos are all unusable, and among bright photos the edge sharpness settles the label.
  • 1Root entropy with 3 usable of 8: H = 0.954.
  • 3Gain for lighting: 0.954 - (4/8)(0.811) - (4/8)(0) = 0.549; for edge: 0.954 - (5/8)(0.971) - (3/8)(0) = 0.348. Lighting is the root.
  • 1Bright branch: 3 usable of 4, entropy 0.811.
  • 2Splitting it on edge gives two pure subsets, so the gain is 0.811 - 0 = 0.811 and both children become leaves.
Lighting gives a gain of 0.549 against 0.348 for edge, so it is the root, and its dim branch is already a pure leaf. The bright branch starts with entropy 0.811, and splitting it on edge leaves a sharp subset of three usable photos and a blurred subset of one unusable photo, both pure. The gain is therefore the whole 0.811, the tree stops, and its rule reads: usable if bright and sharp, otherwise not.
Sia tip — Any subset whose samples all share one label has entropy zero. Spot those first; they make the weighted sum shorter and become leaves immediately.
Glossary

Key terms

Root Node
The first node of a decision tree, where every sample begins and the first attribute is tested.
Leaf Node
A terminal node of a decision tree that assigns a final class or value.
Entropy
A measure of the disorder or uncertainty of a set's class labels, zero when all labels agree.
Gain Ratio
Information gain divided by the split information of an attribute, the criterion C4.5 uses to choose splits.
Split Information
The entropy of an attribute's own partition of the data, which grows with the number of distinct values.
Maximum Margin
The largest achievable distance between a separating hyperplane and the nearest points of each class.
Slack Variable
A non-negative quantity in a soft-margin SVM measuring how far a point falls inside the margin or onto the wrong side.
One-vs-One Strategy
A multi-class scheme that trains one binary classifier per pair of classes and predicts by majority vote.
FAQ

Decision Trees and Support Vector Machines FAQ

What is the difference between information gain and gain ratio?

Information gain measures how much splitting on an attribute reduces entropy. It is biased towards attributes with many distinct values, because splitting into many small subsets makes each look pure. Gain ratio, used by C4.5, divides the gain by the attribute's split information, which grows with the number of values, and so removes much of that bias.

Why does a support vector machine depend only on the support vectors?

Because the maximum-margin hyperplane is fixed by the points that lie on the margin, the closest point of each class. Points further away satisfy their constraints with room to spare and play no part in the solution, so moving them, without crossing the margin, leaves the boundary unchanged. This is also why an SVM can generalise well from relatively few points.

How many classifiers does a multi-class SVM need?

It depends on the strategy. One-vs-rest trains one binary SVM per class, each separating that class from all others, and predicts with the highest score, so N classes need N classifiers. One-vs-one trains a classifier for every pair of classes and takes a vote, which needs N(N - 1) / 2 classifiers, for example 45 for ten digit classes.

Study strategy

Assessment move

Memorise four entropy values so that you can check arithmetic at a glance: an even split of two classes gives 1, a three-to-one split gives 0.811, a four-to-one split gives 0.722, and any pure set gives 0. Then practise the SVM checks by substituting points into a given weight vector and bias, deciding for each whether it is a support vector, safely outside the margin, inside it or misclassified.

Working through Decision Trees and Support Vector Machines in MAIE5421? Sia is AskSia’s AI Computer Science tutor — ask any MAIE5421 Decision Trees and Support Vector Machines question and get a clear, step-by-step explanation grounded in how MAIE5421 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MAIE5421 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works