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

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?

  • $\begingroup$ Not so obvious to me. Could you add some context? $\endgroup$ – generic_user Oct 20 '17 at 16:40
  • $\begingroup$ What do you mean by complexity difference? The tag time-complexity is about computational complexity (roughly, computational time as a function of sample size). $\endgroup$ – Richard Hardy Oct 20 '17 at 16:47
  • $\begingroup$ @generic_user Here is the link of the video I am talking about :-coursera.org/learn/neural-networks-deep-learning/lecture/rz9xJ/… $\endgroup$ – Anukarsh Singh Oct 20 '17 at 16:47
  • $\begingroup$ @RichardHardy Sorry I was talking about with reference to time complexity only. $\endgroup$ – Anukarsh Singh Oct 20 '17 at 16:49
  • $\begingroup$ I was asking about time complexity because Andrew Ng told that the time complexity for a multi- layered neural network for the above function will be less as compared to that of a single layer of NN. $\endgroup$ – Anukarsh Singh Oct 20 '17 at 16:56

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.

  • $\begingroup$ That was such a lucid explanation. Now I got the gist of it. Thanks! $\endgroup$ – Anukarsh Singh Oct 20 '17 at 18:14

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.

  • $\begingroup$ If you can;t give a definitive answer you should give an answer. $\endgroup$ – Michael R. Chernick Feb 22 '18 at 2:14
  • $\begingroup$ sorry I'm not sure if I understand your comment. $\endgroup$ – George Han Feb 27 '18 at 15:32

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.