3
$\begingroup$

Let $X \subset \mathbb{R}^m$ be a finite set of points, classified by a function $f:X \to \{-1, 1\}$. We say that a hyperplane $H = \{x \in \mathbb{R}^m : \langle x, v \rangle + c = 0\}$ is a separating hyperplane for $X$ when $\forall\ x \in X, sign(\langle x, v \rangle + c) = f(x)$.

Let $S, T \in \mathbb{R}^m$ be separating hyperplanes, determined by the equations $\langle x, w \rangle + b = 0$ and $\langle x, w^* \rangle + b^* = 0$, respectively.

Do there necessarily exist continuous functions $\phi:[0, 1] \to \mathbb{R}^m$ and $\psi:[0, 1] \to \mathbb{R}$, such that $$\begin{align}\phi(0) &= w\\\phi(1) &= w^*\\\psi(0) &= b\\\psi(1) &= b^*\end{align}$$ and such that $\forall\ k \in [0, 1], H_k = \{x \in \mathbb{R}^m : \langle x, \phi(k) \rangle + \psi(k) = 0\}$ is a separating hyperplane?

In other words, given two separating hyperplanes, can one go from one to the other continously (a-la homotopy), only passing through other separating hyperplanes?

The question arises from wondering if one could use a single layer Perceptron (trained by the Perceptron learning algorithm) to approximate the SVM solution for a given training set $X$. The latter is more expensive to compute than the former, so it would be interesting if there were a way to go from one to the other.

$\endgroup$
  • $\begingroup$ As written, the answer is no. Suppose $0 \in X$, and you have two separating hyperplanes $H_1 = \{ x : \langle x,v\rangle + 1 = 0\}$ and $H_2 = \{ x : \langle x, \varepsilon - w\rangle - 1 = 0\}$ where $\varepsilon$ is a small perturbation (could be $0$). Any path from $1$ to $-1$ would pass through $0$, and thus produce a Hyperplane intersecting $X$. If you require your hyperplanes being given in a specific form, say $\langle x,w\rangle = 1$, I'd think you have a path. $\endgroup$ – Daniel Fischer Nov 13 '13 at 19:30
  • $\begingroup$ I think there's a minor flaw in your counterexample. If you take linear functions $f_1 = \langle x, v \rangle + 1$ and $f_2 = \langle x, \varepsilon - w \rangle -1$, you'll see that values of these fucntions at $0$ have different signs. But it shouldn't be so: ${\rm sgn} f_1(0) = {\rm sgn} f_2(0) = f(0)$. $\endgroup$ – Evgeny Nov 14 '13 at 3:34
1
$\begingroup$

If I am not wrong with calculations, this set is even convex, not only path-connected.
Let $H_0$ and $H_1$ be two separating hyperplanes generated by linear functions $f_0 = \langle x, v_0 \rangle + w_0$ and $f_1 = \langle x, v_1 \rangle + w_1$: $H_0 = \lbrace x: f_0(x) = 0 \rbrace$, $H_1 = \lbrace x: f_1 (x) = 0 \rbrace$. Consider a linear function $f_\alpha = (1 - \alpha) f_0 + \alpha f_1 = \langle x, (1- \alpha) v_0 + \alpha v_1 \rangle + (1-\alpha)w_0 + \alpha w_1$. Since for any $x$ follows ${\rm sgn} f_0 (x) = {\rm sgn} f_1 (x) = f(x)$, then convex combination $f_\alpha$ of $f_0$ and $f_1$ has the same sign as $f(x)$. So, $H_\alpha = \lbrace x : f_\alpha(x) = 0 \rbrace $ is separating hyperplane.

$\endgroup$
  • $\begingroup$ This works :) Thanks! $\endgroup$ – Federico Lebrón Nov 14 '13 at 4: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.