Linear classifiers are linear hyperplanes in feature space that partition the space in (two) classes. Examples: least squares classifiers, logistic regression, etc.
Today we will look at non-linear discriminative classifiers.
Usually, a classification problem, where you establish a linear boundary, would look like:
Of course, not all problems look like this. Sometimes we might prefer other type of classifiers, e.g.,
Hence, in a lot of cases non-linear classifiers are preferred. Moreover, in feature spaces with a lot of features, linear classifiers might not work very well.
To seek non-linearly separable problems, one does not need to go into complicated situations. The well-known Exclusive OR (XOR) Boolean function is a typical example of such a problem.
It is apparent from this figure that no single straight line exists that separates the two classes.
A decision tree is a greedy space partitioning approach to nonlinear classification that leads to an “intuitive” classifier, but typically has high variance.
Let’s construct the following 2D data set:
For simplicity, we are going to use discrete features, with possible values low, medium or high for feature 1, and low or high for feature 2.
From the data, we see that most class blue objects are medium and low, and most of the other objects with different values are class orange.
As previously, we want to construct a classifier which minimizes the empirical risk:
