1
$\begingroup$

This is a question given as homework. $X = \{(1 0), (0 1), (1, 1)\}$. We have to find all the dichotomies of $X$ and specify which ones are affine and linear separable. In addition, we need to specify the linear and affine separating hyperplane if it exists.

The definition of a dichotomy of $X$ is $(X^+, X_-)$ such that the disjoint union is $X$.

The definition of linear(affine) separable is: A dichotomy in $R^2$ is linear(affine) separable iff there exists $w$ in $R^2$ (and $b$ in $R$) such that $X^+ = \{x \in X\text{ such that }w^T.x(+b) > 0\}$ and $X_- = \{x \in X\text{ such that }w^T.x(+b) <0\}$

I proceeded as follows: Clearly, there are 8 dichotomies. 6 of them are linear separable which can be determined by plotting these points and a line through the origin. Since linear separable implies affine separable, so all 6 are also affine separable.

Two are not linear separable but are affine separable. These are: $X^+ = \{(1 0), (0 1)\}$ and $X_- = \{(1, 1)\}$ and $X^+ = \{(1, 1)\}$ and $X_- = \{(1 0), (0 1)\}$.

My question is: how do I find the linear and affine separating hyperplane (if it exists) for all 8 dichotomies? I think that they should be lines of the form $x = h$ or $y = k$? Won't they depend on the choice of w? Please help me out.

  • 0
    They need not be ordered pairs. A dichotomy of a set is defined as two subsets whose disjoint union in the set itself. I drew pictures to see whether or not the dichotomy is linear or affine separable(if the line through the origin separates the two sets, it is linearly separable and if any line separates the two sts, it is affinely. But how does one see the hyperplanes?2012-06-26

1 Answers 1

1

No, they need not be lines of the form $x=h$ or $y=k$. They can be arbitrary lines in the affine case, and arbitrary lines through the origin in the linear case.

It seems you understand how to see geometrically whether the sets are affine or linear separable and you just need to convert this into an analytic specification of the separating lines.

For the linear case, the equation is $w^\top\cdot x=0$. You can view this as expressing that $x$ is orthogonal to $w$. Thus, if you can see which line separates the subsets, just select a vector that's orthogonal to it.

For the affine case, the equation is $w^\top\cdot x+b=0$. You can write this as $w^\top\cdot (x-x_0)=0$, where $x_0$ is any vector on the line. Thus, $w$ is a vector orthogonal to the line, and $b=-w^\top x_0$ for some $x_0$ on the line.