2
$\begingroup$

Can someone explain to me with a proof or example why you can't linearly separate XOR (and therefore need a neural network, the context I'm looking at it in)?

I understand why it's not linearly separable if you draw it graphically (e.g. here), but I can't seem to find a formal proof somewhere, I wanted to try and understand it with either an equation or example written down. I'm wondering if one exists (I guess it has to do with contradictions?), but I can't seem to find it? I have seen this, but it's more a reason than a proof.

$\endgroup$
0
2
$\begingroup$

Before proving that XOR cannot be linearly separable, we first need to prove a lemma:

Lemma 1

Lemma: If 3 points are collinear and the middle point has a different label than the other two, then these 3 points cannot be linearly separable.

enter image description here

Proof: Let us label the points as point $A$, $B$, and $C$. $A$ and $C$ have the same label, and $B$ has a different label. They are all collinear with line $\mathcal{L}$.

Assume the contradiction, so a line can linearly separate $A$, $B$, and $C$. This means a line must cross between segment $AB$, and segment $BC$ to linearly separate these three points (by definition of linear separability). Let us label the point where the line crosses segment $AB$ and point $Y$, and the point where the line corsses segment $BC$ and point $Z$.

However, since segments $AB$ and $BC$ are collinear to line $\mathcal{L}$, points $Y$ and $Z$ also falls on line $\mathcal{L}$. Since only one unique line can cross 2 points, it must be that the only line that passes segments $AB$ and $BC$ and (therefore separates points $A$, $B$, and $C$) is line $\mathcal{L}$.

However, line $\mathcal{L}$ cannot linearly separate $A$, $B$, and $C$, since line $\mathcal{L}$ also crosses them. Therefore, no line exists can separate $A$, $B$, and $C$.

Main proof

enter image description here

Consider these 4 points that represent a XOR table. Let us label them clock-wise, so the top-left point as $A$, top-right point as $B$, bottom-right point as $C$, and bottom-left point as $D$. So $A$ and $C$ have the same label, and $B$ and $D$ have the same label. We want to show that points $A, B, C$ and $D$ cannot be linearly separable.

Assume the contradiction, and that there is a line that can separate these 4 points.

Imagine a fifth point that lies in the center, and let us label this as point $E$.

Since $E$ lies in the center, the three points $A, E$ and $C$ are collinear. Similarly, since $E$ lies in the center, the three points $B, E$ and $D$ are collinear.

Because we assume a line can linearly separate $A, B, C$ and $D$, then this line must label point $E$ as some label. If $E$ shares the same label as $A$ and $C$, then the points $B, E$ and $D$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable. Likewise, if $E$ shares the same label as $B$ and $D$, then the points $A, E$ and $C$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable.

Therefore it is impossible to give a label to $E$ while satisfying linear separability. As a result, our assumption must be false, and the four points $A, B, C$ and $D$ cannot be linearly separable.

$\endgroup$
1
  • $\begingroup$ It may be worth mentioning the perceptron and how it relates to your proof (i.e. is the perceptron only a linear model, i.e. a line?). The original post contained the word "perceptron" in the title, so I guess we're talking about the perceptron here. $\endgroup$
    – nbro
    Dec 17 '20 at 11:38
0
$\begingroup$

Here is a similar contradiction based answer using basic coordinate geometry.

Is there a proof to explain why $XOR$ cannot be linearly separable?

Let us suppose, if possible, that the $XOR$ function, given by following table, is linearly separable. \begin{array}{|c|c|c|} \hline x& y & x \text{ xor } y\\ \hline 0&0&0\\ \hline 0&1&1\\ \hline 1&0&1\\ \hline 1&1&0\\ \hline \end{array} This ensures the existence of a line $L:ax+by+c=0$ such that the points $(0,0)$ $\&$ $(1,1)$ both lie on the same side of $L$ and the points $(0,1)$ $\&$ $(1,0)$ also lie on same side of $L$ but opposite to that of $(0,0)$ $\&$ $(1,1).$
Also from basic coordinate geometry, we know that if the points $(x_1,y_1)$ $\&$ $(x_2,y_2)$ lie on same side of a line given by $px+qy+r=0$ then, $$(px_1+qy_1+r)\cdot(px_2+qy_2+r)>0$$ and if they are on opposite sides of the line then, $$(px_1+qy_1+r)\cdot(px_2+qy_2+r)<0$$ Since $(0,0)$ and $(1,1)$ lie on same side of $L$, so \begin{equation} c\cdot(a+b+c)>0 \tag{1} \end{equation} And, as $(1,0)$ and $(1,1)$ lie on different sides of $L$, so \begin{equation} (a+c)\cdot(a+b+c)<0. \tag{2} \end{equation} Similarly as $(0,1)$ and $(1,1)$ lie on different sides of $L$, \begin{equation} (b+c)\cdot(a+b+c)<0 \tag{3} \end{equation} On adding equations $(2)$ and $(3)$ we get, $$(a+b+2c)\cdot(a+b+c)<0$$ $$\implies (a+b+c)\cdot(a+b+c)+c\cdot(a+b+c)<0$$ $$\implies (a+b+c)^2+c\cdot(a+b+c)<0$$ Since $(a+b+c)^2\geq0$ for any choice of numbers $a,b,c,$ so $$c\cdot(a+b+c)<-(a+b+c)^2\leq0$$ $$c\cdot(a+b+c)<0$$ which is a contradiction of equation $(1)$, proving the non-existence any such line $L.$

The $XOR$ function is not linearly separable.

$\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.