Why are SVMs / Softmax classifiers considered linear while neural networks are non-linear?

Question

My understanding is that neural networks are definitely not linear classifiers, as the point of functions like ReLU is to introduce non-linearity.

However, here's where my understanding starts to break down. A classifier, like Softmax or SVM is considered to be a "linear classifier". I'm using the definitions from CS 231N. There may be another definition of an SVM, but I'm not considering that.

In a linear classifier we have the following: $W \cdot x$ where

• $W$ is the weights
• $x$ is the input vector.

The output is a vector of scores. 1 score per label.

An SVM classifier uses hinge loss to update the weights:

A softmax classifier normalizes the output values using the softmax function and then uses cross-entropy loss to update the weights:

From the lecture CS231n Winter 2016: Lecture 2: Data-driven approach, kNN, Linear Classification 1, we have the following image to help visualize what a linear classifier does:

Essentially, each image can be considered a point in 3072 dimensional space, and we are drawing lines through this space. On one side of the "car" line, the car score for a given point will go up. On the other side of the "car" line, the car score for a given point will go down.

However, this doesn't seem to be that much different from ReLU (Taken from this post: https://stats.stackexchange.com/questions/158549/why-are-activation-functions-needed-in-neural-networks):

So what is the fundamental difference between a "linear" classifier like Softmax / SVM and a multi-layer neural network? Why can't a SVM classifier learn any function but a neural network can?

Answer 1

I was confused because the images look similar even though in reality the problems the 2 images are solving are completely different:

• The first image shows a linear classifier assigning scores for each of $C$ classes to an input image
• The second image shows a binary classifier (I think) scoring an item as ether white or purple (or something like that)

Consider a single class in the linear classifier. The linear classifier can only draw a single line through $N$ dimensional space. Items on one side of this line have negative car scores. Items on the other side have positive car scores.

For example:

Here, the 2nd image in the row represents the SVM's attempt to extract all the features of a car into a single image. As images are "closer" to this image, the SVM will give them a higher car score. As images are farther away from this image, the SVM will give them a lower car score.

The SVM cannot extract individual features, it has to smush them all into a single line in $D$ dimensional space (where $D$ is the number of pixels). That line can be represented as:

On the other hand. A multi-layer neural network, for example:

Can now partition the space into a 100 different ways. The example is a bit convoluted, since the neural net is classifying 1 thing into several buckets instead of doing binary classification, but the principle is the same. Maybe 10 out of a 100 neurons in the second layer are dedicated to partitioning the space of images with regard to cars.