Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A visual proof that neural nets can compute any function

neuralnetworksanddeeplearning.com

Post reply on HN
Print view View original

11–20 of 67 posts

Re: A visual proof that neural nets can compute any function

#11

Post by GuiA »

> Consider the problem of naming a piece of music based on a short sample of the piece. That can be thought of as computing a function. Or consider the problem of translating a Chinese text into English. Again, that can be thought of as computing a function. Or consider the problem of taking an mp4 movie file and generating a description of the plot of the movie, and a discussion of the quality of the acting. Again, that can be thought of as a kind of function computation. Universality means that, in principle, neural networks can do all these things and many more.

Eesh, that seems like poor technical written, and potentially misleading. It's far from clear that these are computable functions in the first place; Penrose argues (see notably "Shadows of the Mind") that there are functions which can be computed by the human brain that are undecidable over the Church-Turing thesis.

"Just because we know a neural network exists that can (say) translate Chinese text into English, that doesn't mean we have good techniques for constructing or even recognizing such a network." seems very hand wavy - we don't know that such a neural network exists without first going through a big set of still controversial assumptions.

The rest of the article is good, but I'm not a big fan of that section. It's not a huge part, but I think this could give some students the wrong idea about what is a computable function, and what neural networks can compute.

Re: A visual proof that neural nets can compute any function

#12

Post by cLeEOGPw »

GuiA wrote: post #11

> Consider the problem of naming a piece of music based on a short sample of the piece. That can be thought of as computing a function. Or consider the problem of translating a Chinese text into English. Again, that can be thought of as computing a function. Or consider the problem of taking an mp4 movie file and generating a description of the plot of the movie, and a discussion of the quality of the acting. Again,…

By function I think he meant mapping input points to output points in an abstract plane.

So in that sense a piece of music, or a sentence in one language is a point of input, while name of music or sentence in another language is another point.

Everything is a function as long as there is a way to turn that thing into inputs that correspond to outputs.

Re: A visual proof that neural nets can compute any function

#13

Post by cLeEOGPw »

gizmo686 wrote: post #5
p1esk wrote: post #4

Earlier quoted context omitted.

What would be an example of a practical task that needs to be modeled with such a function?

Rounding

Rounding is something humans can't do either. how easily can you round a stick that is almost exactly 1.5 meters long? You would be ever sure that you are correct.

And as for rounding in mathematical way, that wouldn't be a problem for neural network, since it is a large distance from 1.4999... and 1.5000... from neural network's perspective, just like it is for you.

Re: A visual proof that neural nets can compute any function

#14

Post by GuiA »

cLeEOGPw wrote: post #12
GuiA wrote: post #11

> Consider the problem of naming a piece of music based on a short sample of the piece. That can be thought of as computing a function. Or consider the problem of translating a Chinese text into English. Again, that can be thought of as computing a function. Or consider the problem of taking an mp4 movie file and generating a description of the plot of the movie, and a discussion of the quality of the acting. Again,…

By function I think he meant mapping input points to output points in an abstract plane. So in that sense a piece of music, or a sentence in one language is a point of input, while name of music or sentence in another language is another point. Everything is a function as long as there is a way to turn that thing into inputs that correspond to outputs.

Ok, so by your reasoning let's have a function as a point of input, and whether it halts or not as a point of output.

So now we have a function, I can't wait till "we have good techniques for constructing such a network" that maps those inputs and outputs in an abstract plane :)

Re: A visual proof that neural nets can compute any function

#15

Post by cLeEOGPw »

GuiA wrote: post #14
cLeEOGPw wrote: post #12

Earlier quoted context omitted.

By function I think he meant mapping input points to output points in an abstract plane. So in that sense a piece of music, or a sentence in one language is a point of input, while name of music or sentence in another language is another point. Everything is a function as long as there is a way to turn that thing into inputs that correspond to outputs.

Ok, so by your reasoning let's have a function as a point of input, and whether it halts or not as a point of output. So now we have a function, I can't wait till "we have good techniques for constructing such a network" that maps those inputs and outputs in an abstract plane :)

That is a good example. But you are forgetting that neural networks are approximating the actual functions, so the function you described could be built with some kind of confidence level in the answer. Just like you can have some confidence that certain code will not halt from experience, neural network could also be built to do that. Not all possible functions though, unless you have infinitely large network with infinite computing power.

Re: A visual proof that neural nets can compute any function

#16

Post by shoo »

I am glad that the article mentions the Stone-Weierstrass approximation theorem [1], an analogous result for polynomials from 1885.

More recently, there's now "Chebfun" [2], an open-source Matlab library for working with highly accurate 1- and 2- dimensional polynomial approximations to arbitrary continuous functions.

Approximation theory: pretty useful, pretty well-established, under-hyped.

[1] https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theo... [2] http://www.chebfun.org/

Re: A visual proof that neural nets can compute any function

#17

Post by no_gravity »

I wonder how efficiently it can do that compared to other systems.

For example a short iterative function like this:

    function(complex c)
      complex z=0
      int steps=0
      while (z
Can calculate with extremely high accuracy if a point in the complex plane is in the mandelbrot set or not. I would assume that a NN with the same accuracy would be of enormous size. It would probably have way more neurons then there are atoms in the universe.

Re: A visual proof that neural nets can compute any function

#18

Post by JumpCrisscross »

>No matter what the function, there is guaranteed to be a neural network so that for every possible input, x, the value f(x) (or some close approximation) is output from the network

Love NNs, but accuracy is relative. At some resolution of "close approximation," every function "computes" every other function.

Re: A visual proof that neural nets can compute any function

#19

Post by 3v3rt »

no_gravity wrote: post #17

I wonder how efficiently it can do that compared to other systems. For example a short iterative function like this: function(complex c) complex z=0 int steps=0 while (z Can calculate with extremely high accuracy if a point in the complex plane is in the mandelbrot set or not. I would assume that a NN with the same accuracy would be of enormous size. It would probably have way more neurons then there are atoms in the…

I think one of the caveats was that the function should be relatively smooth and continuous, a mandelbrot set isn't very smooth is it?

Re: A visual proof that neural nets can compute any function

#20

Post by [deleted] »

JumpCrisscross wrote: post #18

> No matter what the function, there is guaranteed to be a neural network so that for every possible input, x, the value f(x) (or some close approximation) is output from the network Love NNs, but accuracy is relative. At some resolution of "close approximation," every function "computes" every other function.

[deleted]
Post reply on HN