15

How do we decide if a classifier is linear or non linear ?

What property/characteristic makes a classifier linear or non linear ?

Eg: Why SVM is a linear classifier ? Why Logistic Regression is linear classifier even though it uses logistic function which is a non linear function ?

mach
  • 1,545
  • 3
  • 10
  • 12
  • 1
    The linearity of the classifier refers to its decision boundary. Is it a hyperplane or not? (And SVM's is generally not linear.) – Emre Oct 25 '15 at 01:36
  • Thanks @Emre , so as per your answer, if the feature space is say 6 dimensional and the decision boundary is 5 dimensional then it is a linear classifier. Am I right ? – mach Oct 25 '15 at 01:48
  • So it doesn't depend on the sixth one? It could still be nonlinear in the other five. – Emre Oct 25 '15 at 01:54

1 Answers1

12

A classifier is linear if its decision boundary on the feature space is a linear function: positive and negative examples are separated by an hyperplane.

This is what a SVM does by definition without the use of the kernel trick.

Also logistic regression uses linear decision boundaries. Imagine you trained a logistic regression and obtained the coefficients $\beta_i$. You might want to classify a test record $\mathbf{x} =(x_1,\dots,x_k)$ if $P(\mathbf{x}) > 0.5$. Where the probability is obtained with your logistic regression by: $$P(\mathbf{x}) = \frac{1}{1+e^{-(\beta_0 + \beta_1 x_1 + \dots + \beta_k x_k)}}$$ If you work out the math you see that $P(\mathbf{x}) > 0.5$ defines a hyperplane on the feature space which separates positive from negative examples.

With $k$NN you don't have an hyperplane in general. Imagine some dense region of positive points. The decision boundary to classify test instances around those points will look like a curve - not a hyperplane.

Simone
  • 6,513
  • 2
  • 26
  • 52
  • Thanks ... but with a hyperplane we can classify into only two classes ( ie positive or negative) , then how do these classifiers (Logistic which is binary) handle multilabel classifications ? – mach Oct 25 '15 at 02:07
  • 1
    Yes hyperplanes deal with binary classification problems. There are two ways to use hyperplanes for multiclass classification: one vs one, and one vs all. Have a look at this wiki page: https://en.m.wikipedia.org/wiki/Multiclass_classification – Simone Oct 25 '15 at 02:14
  • @Simone as you said a classifier is linear if its decision boundary is linear function in the feature space. Could you please look at these [question](https://stats.stackexchange.com/questions/533517/what-is-the-relation-between-linear-classifier-and-linear-decission-boundary-or) , how to relate a classifier and a decision boundary. Also if a classifier is given , how do we judge whether its a linear or non linear. – Girish Kumar Chandora Jul 07 '21 at 04:18
  • @mach if you get the concept then please try to explain this doubt too - [question](https://stats.stackexchange.com/questions/533517/what-is-the-relation-between-linear-classifier-and-linear-decission-boundary-or) – Girish Kumar Chandora Jul 07 '21 at 04:23