0
$\begingroup$

The 2 dimensions xor problem can be converted to 4 equations which is possible to prove that are not possible to solve

  x1       x2     output
  0         0         0
  0         1         1
  1         0         1
  1         1         0

w1*0 + w2*0 <= 0
w1*0 + w2*1 > 0
w1*1 + w2*0 > 0
w1*1 + w2*1 <= 0

How can I prove that the XOR problem for dimension d is not lineary seperable? How to relate to an even d and an odd d?

I thought of the following answer: Lets observe all of the equations of the form:

0*w1 + .. + 1*wi + .. + 0*wd > 0, for each i=1..d

These equations obligate wi > 0, for each i.

Now lets take the last equation.

1*w1 + 1*w2 + ... + 1*wd <= 0 (only when d is even)

This equation force wi<=0 for all i.

So:

wi > 0, for each i.
wi<=0 for all i.

Cannot be solved because. On the odd - d case, we'll have to consider the all of the equations with 1 zero (d equations), and it will get to the same contradiction.

But - i'm not sure it's the good-practice way.

Thanks

$\endgroup$
1
$\begingroup$

Your answer for 2 dimensions can be true even for $d>2$.

Consider the vectors:
$(1, 0, 0, ..., 0)$
$(0, 1, 0, ..., 0)$
$(1, 1, 0, ..., 0)$

You can't have $w1, w2$ s.t.
$w_1>0, w_2 >0$
$w_1 + w_2 \leq 0$

edit:
this is for the equations that you posted for when $b=0$,
for $b \neq 0$, see Arthur's answer

$\endgroup$
0
$\begingroup$

If $XOR_d(x_1,x_2,\ldots,x_d)$ is the (linear) XOR function on $d$ variables (defined as 1 iff an odd number of the inputs are 1), then define the two functions $$ f(x_1)=XOR_d(x_1,0,0,\ldots,0)=w_1x_1+a\\ g(x_1)=XOR_d(x_1,0,0,\ldots,0,1)=w_1x_1+b $$ But $f$ is (strictly) increasing and $g$ is (strictly) decreasing, which is impossible.

$\endgroup$
  • $\begingroup$ I didn't understad your proof, what do you mean by first item of x1? where are the equations? Thanks $\endgroup$ – JohnSnowTheDeveloper Nov 3 '18 at 8:17

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.