0
$\begingroup$

Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that:

For every $n$, there exists a dense NN of depth 2, such that it contains all functions from ${±1}^n$ to ${±1}$. (given sign activation functions and some other very simple assumptions).

Check section 20.3 for the proof.

So, if neural net can approximate any function then it has a $\mathcal V \mathcal C $ dimension of infinite (considering the $n$ dimesnional set of points as our universe)

Thus it can realise all types of functions or its hypothesis set contains all set of functions and hence cannot have prior knowledge. (prior knowledge in the sense used in the No Free Lunch theorem).

Are my deductions correct? Or did I make mistaken assumptions? Are there actually any prior beliefs in a neural network which I am missing. A detailed explanation would be nice.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – nbro Apr 13 at 22:39
1
$\begingroup$

I think your deduction is mostly correct.

Neural networks of depth are universal function approximators. This means that in principal, for any function of the form you describe, there's a NN that approximates it.

However, a particular NN architecture of fixed width and depth, with fixed connections is not a universal approximator for all functions. Only an infinitely wide NN is, and that's a theoretical construct, not something you can make in practice.

Typically, a practitioner using a NN injects their prior beliefs about the problem by selecting an architecture. For example, it is common to use the ImageNet or ResNet architectures for image processing tasks. Those architectures are less effective on other types of tasks. For instance, it should be clear that they are ineffective on say, a time-series analysis task.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think this is correct, and this is more or less what I've been trying to say in the comments (that are now in this chat room). I think the wrong conclusion is "Thus it can realise all types of functions or its hypothesis set contains all set of functions and hence cannot have prior knowledge.". I think it's the other way around: if you incorporate some bias, then you may not be able to approximate some functions. $\endgroup$ – nbro Apr 13 at 22:50
  • $\begingroup$ So in theory it still should have infinite VC dimension, just like in theory of UAT a super wide NN will have arbitrarily low error? $\endgroup$ – DuttaA Apr 13 at 22:51
  • $\begingroup$ @DuttaA Yes. In fact, the two ideas are really sides of the same coin: If you can make the error arbitrarily low for any function by making an NN infinitely wide, then it follows that, for a binary function (where we just clip, say, >0.5 outputs of the NN to 1), you can always learn it. However, the class of models you're learning is "NNs of arbitrary width", which is not a class we know how to optimize nicely. $\endgroup$ – John Doucette Apr 13 at 22:55
  • $\begingroup$ @JohnDoucette Thanks for the clarification, just another question, why does arbitrarily wide not optimize nicely? (without taking into consideration computation cost) $\endgroup$ – DuttaA Apr 13 at 22:57

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.