3 ms·

This often cited fact is a red herring. Lots of things can compute (or rather approximate) any functions. Piece-wise constant functions obviously can approximat

This often cited fact is a red herring. Lots of things can compute (or rather approximate) any functions. Piece-wise constant functions obviously can approximate anything, but nobody's giddy about using piece-wise constant functions for any numerical purpose (if they do, and they often do, they don't point with pride of their new application of the piece-wise constant functions "universal approximation theorem"). Polynomials, trigonometric polynomials, splines (i.e piecewise polynomials), radial basis functions, and on and on. Just put neural networks to a test against splines, and see how they fare. Take your favorite function, let's say sin(x) and try to approximate it with a neural net with 1000 nodes, or with splines with 20 nodes. You don't stand a chance to match the quality of the spline approximation. Edit: here's a short python snippet to show how much better a spline with 20 nodes is vs a neural network with 1000 nodes for approximating the sin function import numpy as np from sklearn.neural_network import MLPRegressor from scipy.interpolate import UnivariateSpline N = 10000 X_train = 2*np.pi*np.random.uniform(size=N) Y_train = np.sin(X_train) sin_NN = MLPRegressor(hidden_layer_sizes= (1000,)).fit(X_train.reshape(N,1), Y_train) spline_nodes = np.linspace(0,2*np.pi, 20, endpoint=True) sin_spl = UnivariateSpline(spline_nodes, np.sin(spline_nodes), s=0) X_test = np.linspace(0,2*np.pi, 5000, endpoint=True) Y_test = np.sin(X_test) rmse_NN = np.mean((Y_test-sin_NN.predict(X_test.reshape(-1,1)))**2) rmse_spl = np.mean((Y_test-sin_spl(X_test))**2) print("RMSE for NN approx: ", rmse_NN) print("RMSE for spline approx: ", rmse_spl) >> RMSE for NN approx: 0.00011776185865537907 >> RMSE for spline approx: 9.540536500968638e-10

gowld 5y ago
Universality shows potential, not optimality. the article covers this.
srean 5y ago
Indeed. I cannot upvote this enough New fanboys of DNN seem so enamored by the universal approximation property and cite it at the slightest provocation. There is no dearth of universal approximators, that's not what makes DNN special. The special thing is how does simple training procedures seem to find these approximations that generalize well (or doesnt as shown by the adversarial examples).
leoff 5y ago
Since you are nitpicking, you could well use a sinusoid activation function on the Neural Network, and reach an even smaller loss value.
- credit_guy 5y ago
  Not sure I understand your point. Do you want to use a bunch of sine functions to approximate a sine function? What would that show? Splines don't know anything about the nature of a function. They approximate any function with piecewise polynomials. Maybe you are trying to say that the default activation function (relu) in sklearn is not smooth. No problem, you can add activation='tanh' inside the definition of the NN, and check the RMSE. Turns out it's for some reason worse.
  - marginalia_nu 5y ago
    I assume they're referring to Fourier expansion. In general you can use a pretty wide set of functions to approximate an arbitrary function. You can do it with polynomials (Taylor expansion), and many others as long as they form a Hilbert space. Producing a given function from a linear combination of other functions isn't groundbreaking in the least.
Veedrac 5y ago
> >> RMSE for NN approx: 0.00011776185865537907 Error is approximately 0.0001 because `tol`, the parameter that tells optimization to finish, is 0.0001. Set tol=0, and then beta_2=1-1e-15, epsilon=1e-30 to maximize stability from the optimizer, and I got RMSE for the neural network to go below 5e-7. This is all very academic because stochastic gradient descent is a horrific tool to be using for this purpose. You aren't wrong about that.
- credit_guy 5y ago
  Fair enough, I wrote the snippet in 5 min and didn't check the tolerance parameter. But with your improved choice of parameters, the NN is still about 1000 times worse than the cubic spline, despite having 50 times as many nodes.
  - Veedrac 5y ago
    I don't think these numbers are meaningful. It's not far off from a degree-2 interpolation already, and I got a hidden layer size of 20 to an error of 7e-5 by just letting it optimise for longer and picking a seed that worked well, which is basically the same error as a degree-1 interpolation that gets 5e-5. Like sure the spline is doing better, but that's not why we care, it's not like there's a general sense in which spline interpolations are going to be better than the optimal fit from a larger neural network, they're just a simpler, faster, more numerically stable way of solving simpler problems. An optimiser designed for 1D interpolation of small neural networks, for all I know, might get extremely accurate results.
dahart 5y ago
This whole example is a red herring. This isn’t a splines versus NNs issue at all, you’re talking about the well known fact that choice of basis affects the ability to fit, which has nothing to do with whether you use a network. As a concrete proof, since a spline is (usually) a polynomial function, it can be defined as a linear network with as many layers as the spline’s polynomial order, in other words splines are a strict subset of the functions you can build using neural networks. You can also make a neural network out of spline neurons if you want. And you can cherry pick lots of different functions that work better for splines than other choices, and you can also cherry pick functions that perform worse for splines than other bases. Splines perform far worse on a periodic function of arbitrary domain than a Fourier fit. Your example is contrived because you artificially constrained the range to [0, 2pi].
- credit_guy 5y ago
  I'm sorry, but I have to disagree with you here. The "Universal Approximation Theorem" is not the point of neural networks. People should stop mentioning it, or if they do, they should state at the same time that there's nothing special about NNs, that numerous classes of functions possess the same property. Here's my own pitch for neural networks: NN's suck. Big time. They suck in low dimensions and they suck in high dimensions. But the curse of dimensionality is so formidable, that everything sucks in high dimension. Neural networks just happen to suck less than all other known methods. And because they suck a bit less, there are applications where they are useful, and they have no substitute.
  - abeppu 5y ago
    > Neural networks just happen to suck less than all other known methods. Or, perhaps, the best demonstrated performance of NNs exceeds the best demonstrated performance of other known methods for many tasks. But ... the amount of compute, investment in tooling, and attention that have been thrown at deep learning in the past decade is at a scale where ... do we actually know that other methods would perform worse with the same resources? Is there some alternate timeline where in 2012 someone figured out how to run MCMC for bayesian non-parametrics over much larger datasets or something, and the whole field of ML just tilted in a different direction?

gowld 5y ago

Universality shows potential, not optimality. the article covers this.

srean 5y ago

Indeed. I cannot upvote this enough New fanboys of DNN seem so enamored by the universal approximation property and cite it at the slightest provocation. There is no dearth of universal approximators, that's not what makes DNN special. The special thing is how does simple training procedures seem to find these approximations that generalize well (or doesnt as shown by the adversarial examples).

leoff 5y ago

Since you are nitpicking, you could well use a sinusoid activation function on the Neural Network, and reach an even smaller loss value.

credit_guy 5y ago
Not sure I understand your point. Do you want to use a bunch of sine functions to approximate a sine function? What would that show? Splines don't know anything about the nature of a function. They approximate any function with piecewise polynomials. Maybe you are trying to say that the default activation function (relu) in sklearn is not smooth. No problem, you can add activation='tanh' inside the definition of the NN, and check the RMSE. Turns out it's for some reason worse.
- marginalia_nu 5y ago
  I assume they're referring to Fourier expansion. In general you can use a pretty wide set of functions to approximate an arbitrary function. You can do it with polynomials (Taylor expansion), and many others as long as they form a Hilbert space. Producing a given function from a linear combination of other functions isn't groundbreaking in the least.

Veedrac 5y ago

> >> RMSE for NN approx: 0.00011776185865537907 Error is approximately 0.0001 because `tol`, the parameter that tells optimization to finish, is 0.0001. Set tol=0, and then beta_2=1-1e-15, epsilon=1e-30 to maximize stability from the optimizer, and I got RMSE for the neural network to go below 5e-7. This is all very academic because stochastic gradient descent is a horrific tool to be using for this purpose. You aren't wrong about that.

credit_guy 5y ago
Fair enough, I wrote the snippet in 5 min and didn't check the tolerance parameter. But with your improved choice of parameters, the NN is still about 1000 times worse than the cubic spline, despite having 50 times as many nodes.
- Veedrac 5y ago
  I don't think these numbers are meaningful. It's not far off from a degree-2 interpolation already, and I got a hidden layer size of 20 to an error of 7e-5 by just letting it optimise for longer and picking a seed that worked well, which is basically the same error as a degree-1 interpolation that gets 5e-5. Like sure the spline is doing better, but that's not why we care, it's not like there's a general sense in which spline interpolations are going to be better than the optimal fit from a larger neural network, they're just a simpler, faster, more numerically stable way of solving simpler problems. An optimiser designed for 1D interpolation of small neural networks, for all I know, might get extremely accurate results.

dahart 5y ago

This whole example is a red herring. This isn’t a splines versus NNs issue at all, you’re talking about the well known fact that choice of basis affects the ability to fit, which has nothing to do with whether you use a network. As a concrete proof, since a spline is (usually) a polynomial function, it can be defined as a linear network with as many layers as the spline’s polynomial order, in other words splines are a strict subset of the functions you can build using neural networks. You can also make a neural network out of spline neurons if you want. And you can cherry pick lots of different functions that work better for splines than other choices, and you can also cherry pick functions that perform worse for splines than other bases. Splines perform far worse on a periodic function of arbitrary domain than a Fourier fit. Your example is contrived because you artificially constrained the range to [0, 2pi].

credit_guy 5y ago
I'm sorry, but I have to disagree with you here. The "Universal Approximation Theorem" is not the point of neural networks. People should stop mentioning it, or if they do, they should state at the same time that there's nothing special about NNs, that numerous classes of functions possess the same property. Here's my own pitch for neural networks: NN's suck. Big time. They suck in low dimensions and they suck in high dimensions. But the curse of dimensionality is so formidable, that everything sucks in high dimension. Neural networks just happen to suck less than all other known methods. And because they suck a bit less, there are applications where they are useful, and they have no substitute.
- abeppu 5y ago
  > Neural networks just happen to suck less than all other known methods. Or, perhaps, the best demonstrated performance of NNs exceeds the best demonstrated performance of other known methods for many tasks. But ... the amount of compute, investment in tooling, and attention that have been thrown at deep learning in the past decade is at a scale where ... do we actually know that other methods would perform worse with the same resources? Is there some alternate timeline where in 2012 someone figured out how to run MCMC for bayesian non-parametrics over much larger datasets or something, and the whole field of ML just tilted in a different direction?