1
$\begingroup$

If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the data is linearly separable if and only if such a hyperplane exists.

If the data consists of $m$ pairs $(x_1, y_1), \ldots, (x_m,y_m)$, with $x_i \in \{0,1\}^n$ and $y_i \in \{0,1\}$, do we know what the worst case running time is for finding whether or not a maximum margin hyperlane exists?

$\endgroup$
1
$\begingroup$

Most of the work on SVM algorithms focuses on the soft-margin case and so isn't really applicable here.$\newcommand\R{\mathbb R}$

But the question of finding the existence of a linear separator can be solved instead as a linear program: Let $X_+$ be the matrix whose rows are the positive instances (the $x_i$ with $y_i = 1$), and $X_-$ the matrix whose rows are the negatives. Then our question is: is there a $\beta \in \R^n$ and $b \in \R$ such that $X_+ \beta > b$ and $X_- \beta < b$?

This is a linear feasibility problem in $n+1$ dimensions with $m$ linear constraints. Since your $X$ are binary, the LP can then be represented in $O(m n)$ bits; as an upper bound, Karmarkar's algorithm then runs in $$O(m^2 n^{5.5} \log(m n) \log(\log(m n)))$$ time.

Better bounds are certainly possible depending on the setting. For example, if the dimension $n$ is low, Megiddo (1984) gives an algorithm that takes fewer than $2^{2^{n+3}} m$ steps, or another which takes fewer than $\frac{2^{(n+1)^2}}{\prod_{k=1}^{n-1} k!} m (\log m)^{(n+1)^2}$.

$\endgroup$
  • $\begingroup$ Class answer. +1 $\endgroup$ – Digio Aug 27 '15 at 14:06

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.