How can the xor function be formed with a single hidden layer of neural network?

Question

I was recently viewing Andrew Ng's deep learning specialization lectures and I came forward to the following image

It is pretty obvious how the above function( x1 XOR x2 XOR x3..... XOR xn) can be implemented using multiple layers of a neural network. Ng told in the lecture that it is also possible to implement the above function using just a single hidden layer of NN. Is it possible ? If so , how? Also , what will be the time complexity difference between a single hidden layer of NN vs multiple layers of NN for the above function?

Answer 1

He's "hand waving" here. The logic goes like this. You have N logical inputs, which means that the truth table has N dimensions with two values each, so its volume is $2^N$. Hence, he says, you need $2^n$ neurons in the hidden layer, followed by one output. Imagine multi-class classification network such as softmax.

That's how he's saying that you need a very wide $2^N$ node hidden layer, instead of a deep one with only $N\log_2 N$ nodes. What he's not talking about is the problem of separability, i.e. why would you need $2^N$ neurons in the hidden layer.

Answer 2

You can do a single hidden layer NN, or do a multi-layer NN. To do a single hidden layer, you need $2^N$ hidden units, each unit is matching with one of the possible enumerations of the $N$ inputs (each input can be $0$ or $1$, so total enumerations is $2^N$). For a multi-layer NN, you are building a binary tree so complexity is $O(\log N)$.

Note during the lecture Andrew Ng said for single layer you can technically only use $2^{N-1}$ hidden units. I believe this is a mistake but I hope someone can confirm.