8
$\begingroup$

I've been studying the theory behind ANNs lately and I wanted to understand the 'magic' behind their capability of non-linear multi-class classification. This led me to this website which does a good job of explaining geometrically how this approximation is achieved.

Here's how I understood it (in 3D): The hidden layers can be thought of as outputting 3D step functions (or tower functions) that look like this:

Tower function

The author goes to state that multiple such towers can be used to approximate arbitrary functions, for example:

enter image description here

This seems to make sense, however the author's construction is rather contrived to provide some intuition behind the concept.

However, how exactly can this be validated given an arbitrary ANN? Here is what I wish to know/understand:

  1. AFAIK the approximation is a smooth approximation but this 'intuition' seems to provide a discrete approximation, is that correct?
  2. The number of the towers seems to be based on the number of hidden layers - the above towers are created as a result of two hidden layers. How can I verify this (with an example in 3d) with only a single hidden layer?
  3. The towers are created with some weights forced to zero but I haven't seen this to be the case with some ANNs that I've played around with. Will it really be a tower function? Can it be anything with 4 to $n$ sides and almost approximating a circle? (The author says that is the case but leaves that as a self study).

I really wish to understand this approximation capability in 3D for any arbitrary 3D function that an ANN can be approximated with a single hidden layer - I want to see how this approximation looks to formulate an intuition for multiple dimensions?

Here's what I have in mind that I think could help:

  1. Take an arbitrary 3D function like $f(x_1,x_2) = x^2_1 + x^2_2 + 3$.
  2. Generate a training set of $(x_1,x_2)$ of say 1000 data points where many points are on the curve a few above and a few below. Those on the curve are marked as the "positive class" (1) and those not as the "negative class" (0)
  3. Feed this data to an ANN and visualize the approximation with one hidden layer (with about 2-6 neurons).

Is this construction correct? Would this work? How do I go about doing this? I'm not yet adept with back-propagation to implement this by myself and am looking for more clarity and direction in this regard - existing examples showing this would be ideal.

$\endgroup$
  • 1
    $\begingroup$ There's a really good blog post on this topic here: colah.github.io/posts/2014-03-NN-Manifolds-Topology $\endgroup$ – Sycorax Feb 17 '16 at 14:36
  • $\begingroup$ @user777 - Yes, that was my "other" link along with the one in the post and for some reason I forgot to list it :) $\endgroup$ – PhD Feb 17 '16 at 19:59
8
$\begingroup$

There are two great recent articles on some of the geometric properties of deep neural networks with piecewise linear nonlinearities (which would include the ReLU activation):

  1. On the Number of Linear Regions of Deep Neural Networks by Montufar, Pascanu, Cho and Bengio.
  2. On the number of response regions of deep feed forward networks with piece-wise linear activations by Pascanu, Montufar and Bengio.

They provide some badly needed theory and rigor when it comes to neural networks.

Their analysis centers around the idea that:

deep networks are able to separate their input space into exponentially more linear response regions than their shallow counterparts, despite using the same number of computational units.

Thus we may interpret deep neural networks with piecewise linear activations as partitioning the input space into a bunch of regions, and over each region is some linear hypersurface.

In the graphic you have referenced, notice that the various (x,y)-regions have linear hypersurfaces over them (seemingly either slanted planes or flat planes). So we see the hypothesis from the above two articles in action in your referenced graphics.

Furthermore they state (emphasis from the co-authors):

deep networks are able to identify an exponential number of input neighborhoods by mapping them to a common output of some intermediary hidden layer. The computations carried out on the activations of this intermediary layer are replicated many times, once in each of the identified neighborhoods. This allows the networks to compute very complex looking functions even when they are defined with relatively few parameters.

Basically this is the mechanism that allows deep networks to have incredibly robust and diverse feature representations despite having a fewer number of parameters than their shallow counterparts. In particular, the deep neural networks can learn an exponential number of these linear regions. Take for example, Theorem 8 from the first referenced paper, which states:

Theorem 8: A maxout network with $L$ layers of width $n_0$ and rank $k$ can compute functions with at least $k^{L-1}k^{n_0}$ linear regions.

This is again for deep neural networks with piecewise linear activations, like ReLUs for example. If you used sigmoid-like activations, you would have smoother sinusoidal looking hypersurfaces. A lot of researchers now use ReLUs or some variation of ReLUs (leaky ReLUs, PReLUs, ELUs, RReLUs, the list goes on) because their piecewise linear structure allows for better gradient backpropagation vs the sigmoidal-units which can saturate (have very flat/asymptotic regions) and effectively kill gradients.

This exponentiality result is crucial, otherwise the piecewise linearity might not be able to efficiently represent the types of nonlinear functions we must learn when it comes to computer vision or other hard machine learning tasks. However, we do have this exponentiality result and therefore these deep networks can (in theory) learn all sorts of nonlinearities by approximating them with a huge number of linear regions.

As for your question about the hypersurface: you can absolutely setup a regression problem where your deep net tries to learn the $y = f(x_1, x_2)$ hypersurface. This is tantamount to just using a deep net to setup a regression problem, many deep learning packages can do this, no problem.

If you want to just test your intuition, there's a lot of great deep learning packages available these days: Theano (Lasagne, No Learn and Keras built on top of it), TensorFlow, a bunch of others I'm sure I'm leaving out. These deep learning packages will compute the backpropagation for you. However, for a smaller scale problem like the one you mentioned it really is a good idea to code up the backpropagation yourself, just to do it once, and learn how to gradient check it. But like I said, if you just want to try it out and visualize it, you can get started pretty quickly with these deep learning packages.

If one is able to properly train the network (we use enough data points, initialize it properly, training goes well, this is its own whole other issue to be frank), then one way to visualize what our network has learned, in this case, a hypersurface, is to just graph our hypersurface over an xy-mesh or grid and visualize it.

If the above intuition is correct, then using deep nets with ReLUs, our deep net will have learned an exponential number of regions, each region having its own linear hypersurface. Of course, the whole point is that because we have exponentially many, the linear approximations can become so fine and we do not perceive the jagged-ness of it all, given that we used a deep/large enough network.

$\endgroup$

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.