For example, on the linear separability Wikipedia article, the following example is given:

Data set with two linear decision boundaries

They say "The following example would need two straight lines and thus is not linearly separable".

On the other hand, in Bishop's 'Pattern Recognition and Machine Learning' book, he says "Data sets whose classes can be separated exactly by linear decision surfaces are said to be linearly separable".

Under Bishop's definition of linear separability, I think the Wikipedia example would be linearly separable, even though the author of this Wikipedia article says otherwise. This is because Bishop says that we can use multiple linear decision surfaces (hyperplanes) to separate the classes, and it's still considered to be linearly separable data. Bishop implies this by referring to linear decision surfaces, plural, not singular.

Logically, I agree with Bishop. After all, the classes in the Wikipedia example are being separated by linear decision surfaces. So how can one then turn around and say the data set isn't linearly separable? Well, perhaps you could enforce the rule that a data set is only linearly separable if we can separate $N$ classes with $N-1$ decision surfaces. But why would you define linear separability in this way?

So, is the Wikipedia example linearly separable or not?

  • $\begingroup$ First, the plural in "linear decision surfaces" may have been intended to match the plural in "data sets" rather than indicate multiple decision boundaries. It may also have been intended for multiclass problems? (And in that scenario, you might even want a stricter definition of linear separability, in which all hyperplanes should be parallel, i.e. there's a linear score and classes are determined by ranges of scores?) If you allow any number of hyperplanes, then every dataset is linearly separable (barring samples with identical independent variables but different dependent variable). $\endgroup$ – Ben Reiniger Jan 2 '20 at 3:11

In simple terms: Linearly separable = a linear classifier could do the job. You could fit one straight line to correctly classify your data.

Technically, any problem can be broken down to a multitude of small linear decision surfaces; i.e. you approximate a non-linear function with a high number of small linear boundaries. That's what Neural Networks are doing with ReLU activations btw, but nobody would say that Neural Networks are linear models.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.