If each example is a point in a space of features, a classifier divides that
space into regions, one per class. The decision boundary is the border between them
(Witten et al., 2017, p. 69). For a linear model it is a hyperplane: w·x + b = 0. Witten and
colleagues give an example with iris flowers, where a straight line separates setosa from
versicolor by petal length and width: 2.0 − 0.5·LENGTH − 0.8·WIDTH = 0
(2017, pp. 69–70).
Each species draws different boundaries.
- The Perceptron and logistic regression: lines or hyperplanes. They cannot solve XOR, whose classes cannot be separated by a line (Witten et al., 2017, p. 77; Minsky & Papert, 1969).
- The Decision tree (ID3/C4.5): boxes with sides parallel to the axes, because each node compares one attribute with a constant (Witten et al., 2017, p. 70).
- k-nearest neighbors: polygonal boundaries that follow the stored examples.
- The Support vector machine: the maximum-margin hyperplane, as far as possible from both classes, and curved in the original space if the kernel trick is used (Witten et al., 2017, pp. 253–256).
- The multilayer perceptron and deep networks: learned curved boundaries. Chollet (2021) illustrates this with two sheets of paper crumpled into a ball: the network "uncrumples" them layer by layer until a plane separates them (2021, sec. 2.3.6).
Overfitting. A boundary that is too flexible contorts itself to enclose every training example and generalizes badly (Witten et al., 2017, p. 255); hence Chollet (2021) insists that the data should densely cover the region near the boundaries (2021, sec. 5.1.2).
A philosophical angle. Buckner (2024) describes category learning as the search for transformations that separate each category's region enough for a linear boundary to be drawn between them, like brushing tangled hair until a comb can pass through (2024, pp. 115, 118). The image connects with old debates about concepts: trees recall definitions by necessary and sufficient conditions; kNN, prototype and exemplar theories. And it raises a problem of vagueness in reverse: the boundary is always sharp, even when the category is not; output probabilities are the only trace of gradedness.