# How do we define a linearly separable problem?

When we talk about Perceptrons, we say that they are limited for approximating functions that are linearly separable, while Neural Networks that use non-linear transformations are not.

I am having trouble understanding this idea of linear separability. Specifically, does it apply only for binary classification or it generalizes for N classes? If so, how does a linear decision boundary for lets say 4 classes even look like?

1.) Perceptron is a non-linear transformation!

2.) Linear seperable function is only defined for boolean functions, see Wikipedia. Therefore, yes, the statement is meant only for binary classification.

3.) For general functions, see the universal approximation theorem.

• As Debasish Jana points out, using the kernel trick allows to use a higher-dimensional space where the binary classification problem becomes linearly seperable (see en.wikipedia.org/wiki/Kernel_method and en.wikipedia.org/wiki/Kernel_perceptron). Sep 15, 2020 at 22:07
• Note also that using a deep network, the output of the last hidden layer is the input mapped to a higher-dimensional space. Using a sigmoid function on the output layer corresponds to a normal linear logistic regression on the high-dimensional data, per output-node. Sep 15, 2020 at 22:16
• given the correct loss is used, of course Sep 15, 2020 at 22:23

I will try to explain this problem in a classification scenario. Say we begin with two classes of images say dog and cat. And we are asked to classify the images whether the given test image is dog or cat. Imagine the images that we are given is $$8 \times 8$$. So each image is represented by an $$8 \times 8=64$$ dimensional vector. For the training dataset, one such training image will form a data point in this 64-dimensional space. After lots of training data of cat and dog images say 1000 training cat images and 1000 training dog images, we get 2000 such points in the 64-dimensional space. If in that space, the points can be classified using a 64-dimensional hyperplane, then it's linearly separable in an easy way. If not, we can use kernel which is a nonlinear function of the given image, which will transfer the 64-dimensional space into a higher space (more than 64, where we can find linear separability. In a word, each problem is linearly separable. For more information, you can go through Linear Support Vector Machine and Kernel Support Vector Machines.

• Hi, thanks for spending time to answer my question! Unfortunately it is NOT the answer I was looking for. First of all, you did not address my question. Is linear separability property that applies only to binary classification or can it be generalized to N classes? Second, I think that you are wrong about hyperplane in your example. Dimensionality of a hyperplane is by definition 1 less then the ambient space. So in your example, hyperplane that represents decision boundary should be 63 dimensions, not 64. Jan 24, 2020 at 15:41
• Answer to the first question: Yes. It can be generalized to N classes. Jan 28, 2020 at 15:45
• Second question: You are absolutely right that the hyperplane will be of 63 dimensions. Jan 28, 2020 at 15:46