MAIE5421 Chap.5 Decision Trees and Support Vector Machines
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.
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
- 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.
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.
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.
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.