5
$\begingroup$

Of all possible classifiers (including SVMs, locally weighted regression, softmax regression, lots others I'm sure I don't know about, etc.), are they all linear in some high dimensional space?

E.g. An SVM with a Gaussian kernel is linear in infinite-dimensional space.

$\endgroup$
  • 1
    $\begingroup$ The question really is linear with respect to what? logistic regression is "non-linear", but it is linear in parameters. Polynomial terms are non-linear, but linear in parameters. Neural networks aren't linear in parameters, but could be in terms of variables (potentially). You should think about what you mean by "linear" and try to figure out whether all classifiers would meet that definition of linear. $\endgroup$ – Ryan Apr 10 '18 at 20:55
  • $\begingroup$ this has also been discussed on stats.se: stats.stackexchange.com/questions/215696 $\endgroup$ – jld Apr 11 '18 at 15:08
  • $\begingroup$ @Chaconne thank you for your comment. That post you linked was very informative. $\endgroup$ – sidrane Apr 15 '18 at 17:27
  • $\begingroup$ @Ryan what I mean by linear, is if we can project into any higher-dimensional feature space (using a potentially nonlinear mapping), can we draw a single separating hyperplane between the classes of data? And the answer linked by Chaconne indicates that generally, yes you can. The exception is in classifiers that combine multiple "smaller" or "weaker" classifiers together, e.g. K-means, decision trees, boosting, and others like it. $\endgroup$ – sidrane Apr 15 '18 at 17:31
1
$\begingroup$

The answer is yes!

One can use Cover's theorem to prove it.

Remark 1: by "linear in some high dimensional space" we assume here, for any classifier, an existence of an equivalent linear classifier in higher dimensions (i.e., a decision hyperplane that yeilds identical results to the original classifier for any possible input).

Remark 2: it is definitely true for any classifier on a countable domain (e.g., all possible 8bit RGB 256x256 images is quite large but still a countable domain).

For classifiers on uncountable domains (like fields of real numbers), the answer would depend if Cover's theorem holds for infinitely large number of points. However, I'd rather not be worried about that, since all real-world classifiers implemented on classical computers are discrete :-)

Remark 3: Of course, classifier must be deterministic...

$\endgroup$

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.