Given an image, expressed in the vector $\vec{v} = (v_1, \dots, v_n)\in \{0,1\}^n$

The vector $\vec{v}$ can represent images of the numbers 0 to 9. How do I know if this is linear seperable? Given the high dimension when we get big pictures, it becomes hard to reason about this, altough I think the answer is pretty straightforward.

What is a correct and (preferably) mathematical way of reasoning about this? I believe they are not linearly seperable, but I wouldn't know how to prove this.


First the question is not very clear to me. We we say "linear separable", we usually mean binary classification. Because when you draw a line or hyperplane, the data points will be divided into two parts. But in your question, it seems you want to do multi-class classification. then "linear separable" is not well defined.

I will focus on binary classification case. We can use linear programming to do it.

Details can be found in Testing for Linear Separability with Linear Programming in R.

Note, GLPK is just one solver, and R is the interface to build the problem. If you know other solvers, you can directly write other code (say python) to build MPS file or LP file to solve.

  • $\begingroup$ Well, we could start looking at just one class and its complement right? If we can show those are not linear seperable we're done. I was mostly wondering if there's a quick and elegant way to show something is not linear seperable $\endgroup$ – Rich_Rich Jan 18 '17 at 19:03

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.