Why can't Perceptron implement XOR gate?

  • Context: Comp Sci 
  • Thread starter Thread starter shivajikobardan
  • Start date Start date
  • Tags Tags
    Gate
Click For Summary

Discussion Overview

The discussion centers around the inability of a single binary perceptron to implement an XOR gate. Participants explore the perceptron training rule, the nature of output states, and the conditions necessary for training convergence. The scope includes theoretical aspects of neural networks and practical implications for coding the algorithm.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant notes that after one epoch of training, the weights remain at zero, questioning if this will continue indefinitely.
  • Another participant asserts that a single binary perceptron cannot implement XOR and prompts others to consider why this is the case.
  • There is a discussion about the perceptron's output states, with some participants pointing out that the condition for the output state y = -1 is incorrect.
  • Participants discuss the necessity of changing the order of training data between epochs to prevent weights from remaining unchanged.
  • One participant expresses uncertainty about the need to randomize training data and questions the depth of understanding required for convergence.
  • Another participant emphasizes the importance of training until convergence, specifically when the output matches the target for all training data.

Areas of Agreement / Disagreement

Participants generally agree that a single binary perceptron cannot implement XOR, but the discussion contains multiple viewpoints on the reasons behind this limitation and the training process itself remains unresolved.

Contextual Notes

There are unresolved assumptions regarding the definitions of output states and the conditions for convergence. The discussion also highlights the dependency on the training data's order and the implications of using a tri-state output.

shivajikobardan
Messages
637
Reaction score
54
Homework Statement
perceptron xor gate
Relevant Equations
xor gate truth table
1645020070348.png

1645020094661.png


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.
 
Reply
  • Like
Likes   Reactions: PhDeezNutz
Physics news on Phys.org
  • 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?
    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?
 
Reply
  • Informative
  • Like
Likes   Reactions: PhDeezNutz, berkeman and shivajikobardan
pbuk said:
  • That is not a binary perceptron, it has a tri-state output in {-1, 0, 1}.
yeah -1,0,1 are values
pbuk said:
  • The condition for the output state y = -1 is incorrect; can you see why?
why?
pbuk said:
  • It is true that you cannot implement XOR with a single binary perceptron: can you think why?
    how can you get ## b + \sum w_i x_i ## to be < ## \theta ## when x = (0, 0) and x = (1, 1)?

pbuk said:
  • 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.
 
shivajikobardan said:
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?

shivajikobardan said:
why?
Because values ## - \theta \le y_{in} \lt \theta ## satisfy the condtions for both ## y = 0 ## and ## y = -1 ##.

shivajikobardan said:
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.
 
Last edited:
Reply
  • Like
Likes   Reactions: berkeman

Similar threads

Comp Sci Training YOLOv9 on custom dataset
  • · Replies 3 ·
Replies
3
Views
3K
Comp Sci Validating Braces Placement for Expression Evaluation
  • · Replies 10 ·
Replies
10
Views
2K
Designing a Two-Bit Adder Using Verilog Primitive Gates
  • · Replies 1 ·
Replies
1
Views
5K
XOR algorithm to find the missing number in a given array
  • · Replies 13 ·
Replies
13
Views
5K
Engineering Issue with shift registers — PIPO, PISO, SIPO and SISO
  • · Replies 10 ·
Replies
10
Views
4K
Comp Sci What is the difference between GET vs POST vs PUT? Mainly POST vs PUT?
  • · Replies 4 ·
Replies
4
Views
1K
Comp Sci Fortran variable value changing randomly
  • · Replies 5 ·
Replies
5
Views
2K
Is it possible to implement an XOR gate using only NOR gates?
  • · Replies 11 ·
Replies
11
Views
4K
Comp Sci [Fortran] making a more efficient bilinear interpolation
  • · Replies 11 ·
Replies
11
Views
6K
Python Re: Python’s Sympy Module and the Cayley-Hamilton Theorem
  • · Replies 3 ·
Replies
3
Views
1K