Comp Sci Why can't Perceptron implement XOR gate?

[shivajikobardan]

Homework Statement

perceptron xor gate

Relevant Equations

xor gate truth table

As you can see this is perceptron training rule. I want to learn how it can't implement xor. After 1 epoch/iteration, I get w1=0, w2=0,b=0. does this keeps on repeating? Anyone can implement this algorithm to code in python? Would be nice to see what happens in long run.

 

[pbuk]

• That is not a binary perceptron, it has a tri-state output in {-1, 0, 1}.
• The condition for the output state y = -1 is incorrect; can you see why?
• It is true that you cannot implement XOR with a single binary perceptron: can you think why?
  
  Spoiler

  how can you get $b + \sum w_i x_i$ to be < $\theta$ when x = (0, 0) and x = (1, 1)?
• If the weights are unchanged at the end of an epoch and you run exactly the same training data in the next epoch then obviously the weights will be the same at the end of that epoch as well. We do something between epochs to prevent this, can you remember or work out what this is?

 

[shivajikobardan]

• That is not a binary perceptron, it has a tri-state output in {-1, 0, 1}.

yeah -1,0,1 are values

• The condition for the output state y = -1 is incorrect; can you see why?

why?

• It is true that you cannot implement XOR with a single binary perceptron: can you think why?
  
  Spoiler

  how can you get $b + \sum w_i x_i$ to be < $\theta$ when x = (0, 0) and x = (1, 1)?

• If the weights are unchanged at the end of an epoch and you run exactly the same training data in the next epoch then obviously the weights will be the same at the end of that epoch as well. We do something between epochs to prevent this, can you remember or work out what this is?

oh yeah that's what i thought. idk what we do between epochs? do we randomize? but i don't think i need to go to that depth tho.

 

[pbuk]

yeah -1,0,1 are values

And the first line of the question is "this algorithm is suitable for bipolar input vectors with a bipolar target". Do you see the problem?

why?

Because values $- \theta \le y_{in} \lt \theta$ satisfy the condtions for both $y = 0$ and $y = -1$.

idk what we do between epochs? do we randomize? but i don't think i need to go to that depth tho.

What do you mean "go to that depth"? You need to keep training until you achieve convergence, in this case when $y = t$ for all training data. And yes, between each training epoch you randomize the order of the training data.

Of course if you are trying to create an XOR with a single binary perceptron you will never achieve convergence for the reason hinted at above.