We can use linear classifiers to make non$-$linear predictions. The easiest way to do this is to first map all the examples to different feature vectors where typically is much larger than $.$ We would then simply use a linear classifier on the new $($higher dimensional$)$ feature vectors, pretending that they were the original input vectors. As a result, all the linear classifiers we have learned remain applicable, yet produce non$-$linear classifiers in the original coordinates.

There are many ways to create such feature vectors. One common way is to use polynomial terms of the original coordinates as the components of the feature vectors. We have seen two examples in the video above. We will recall the $1-$dimensional example here and see another $2-$dimensional example in the problem below.

Example: Given $3$ training examples with that are not linearly separable in $1-$dimensional space as shown below,

define the feature map which maps each example in $1-$dimensional space to a corresponding feature vector in $2-$dimensional space.

Then, instead of using we use as the training examples $($where are the labels$)$:

The new training set is linearly separable in the $2-$dimensional $-$space, and we can train a $$linear classifier" that is linear in the $-$coordinates.

Another $2-$Dimensional Example

$1$ point possible $($graded$)$

Given the training examples with above, where a boundary between the positively$-$labeled examples and the negatively$-$labeled examples is an ellipse, which of the following feature vector$($s$)$ will guarantee that the training set $($where are the labels$)$ are linearly separable?

Hint: You'll likely find it helpful to review equations for ellipses. We implicitly include bias terms, so that our decision boundaries do not have to meet the origin in feature space.

$($Choose all that apply.$)$