0
$\begingroup$

I am trying to get a better understanding of the application of function approximation with machine learning. My question is simple, how does function approximation with ML compare to traditional interpolation methods?
EDIT: I had a misunderstanding with interpolation and approximation. My question would be better suited to comparing approximation methods with function approximation in machine learning.

$\endgroup$
1
  • 1
    $\begingroup$ What have you found out from the literature so far? Please edit the question to add relevant context. In its present form this question does not demonstrate any research effort. $\endgroup$ – njuffa May 22 at 19:33
7
$\begingroup$

First of all, interpolation and approximation are slightly different from each other.

Given a sufficiently smooth function $f$ (sufficiently smooth just means that I am covering my bases, there are many theorems in approximation theory considering different function classes, from discontinuous -measure zero- functions to infinitely smooth or analytic or entire functions)

  1. $g$ is called an approximant iff $\| f-g\|<\varepsilon$ for some prescribed (user-defined) $\varepsilon>0$.
    1. Notice that I didn't specify the norm, it is up to the researcher and the availability of theorems of existence for approximants given the properties of $f$.
    2. While (1.1) stands true, the choice of norm is very important. Consider the function $$g(x) = f(x) + \begin{cases} 10^9 &, x=0 \\ 0 &,x\neq 0\end{cases}.$$ Now, $\|g-f\|_2=0$ but $\|g-f\|_{\infty}=10^9$. So it is the perfect approximant in one sense, while it is worthless in another sense.
    3. Notice that $g$ does not have to match $f$ at all. For example, $g(x) = f(x) - \varepsilon/2$ is an approximant to $f$ as $\| f -g \|_{\infty}=\varepsilon/2\leq \varepsilon$ but $g(x)\neq f(x)$ for any $x$.
  2. $h$ is called an interpolant of $f$ iff $h(x_i) = f(x_i)$ from a given set of points $\{x_i\}_{i=0}^n$.
    1. The difference between approximation and interpolation is slight, but it boils down to the norm condition. We expect approximants to satisfy an error tolerance, but interpolants are not guaranteed to do that. See the discussion below.
    2. A benefit of the interpolation is the fact that the interpolant matches the function value at the interpolation points. This may be desirable in some applications (see computer graphics, signatures, ...).
    3. The approximation quality of interpolation very much depends on the interpolation points. A silly example I like to give my students: take $\sin(\pi x)$ with the sampling points $\{x_i\}=\{0,1,\dots,10\}$, find the $10$-th degree interpolating polynomial. (Leaving this as an exercise to the reader as well)

(The discussion makes it look like we have to work on $\mathbb{R}$ independent of our interest, but that is not true; you can work on an arbitrary interval and so on. It was just more convenient for me to write it that way. Usually, we limit ourselves to a neighbourhood of finite size)

For further discussion, let's take polynomial interpolation vs. approximation.

The polynomial interpolant $p(x)$ to a function $f(x)$ satisfies the condition $p(x_i)=f(x_i)$ for the interpolation points $x_i$. This is called the interpolation condition, and if it is satisfied we say that $p$ interpolates $f$. So far, $p$ looks like an approximation to $f$. Further, you can consider error bounds and see that if $f$ is sufficiently smooth, there is a relation between the degree of the polynomial $n$ and the $n$-th derivative of $f$ which seems to suggest that the error should go to zero as $n$ goes to infinity. However, this is wrong; for example, we know that if the monomial polynomial basis is used to interpolate $f$ then due to Runge's phenomenon we can not say if the interpolant is a good approximant. This is not a unique problem to monomial basis; it is known that for every polynomial basis (determined by interpolation points) there is a smooth function which will cause issues like this. You may think that but then I can use trigonometric functions to interpolate, in which case you would encounter Gibbs phenomenon. So an interpolant is not necessarily an approximant thanks to these counter-examples, but if the function and its derivatives are nice, then the interpolants of the function can be used as approximants.

We still have to answer the question "can we use polynomials as approximants to sufficiently smooth functions?". The answer is yes thanks to Weierstrass theorem. Is that polynomial approximant an interpolant? Probably no. Do we know how to find it? Not really.

This is where machine learning comes in. Before neural networks became viable due to the technological advances in computing units, people would use curve fitting techniques to predict results from the data collected. In that sense, curve fitting is one of the grandfathers of neural networks. There are analogous theorems to Weierstrass thm., for example Universal Approximation Theorems, which says that neural networks are dense in some function families (continuous function space, Sobolev function spaces,...). As a result, neural networks are approximants in a similar sense to polynomial approximants. There is a neural network which approximates the function to our error tolerance, but we don't know how to find it. Is it shallow or deep? Is it supposed to be wide or slim? What activation function do we use? (Analogous problems for polynomials would be the degree of the polynomial, the amount of data to use, etc.)

The last question to answer is "do/can neural networks interpolate?". In practice, no. You wouldn't want that either. Any reasonable application has the assumption that there is some noise in your data, and you really don't want to fit the noise (overfitting). However, you can easily write polynomial interpolation as a neural network, train it, and voilà, you got an interpolating neural network.

$\endgroup$
6
  • $\begingroup$ The answer here is excellent but I would also encourage you to check out (Gilbert Strang’s recent book)[math.mit.edu/~gs/learningfromdata/] that addresses this somewhat as well in some depth. $\endgroup$ – Kyle Mandli May 22 at 22:48
  • $\begingroup$ Thanks for clarifying my misunderstanding. Outside of least squares what methods do we have for approximating functions that do not also suffer from the phenomenon described above? I looked into function approximation methods and I found: Chebyshev approximation, Fourier Series, Remez's algorithm. However all of these methods build upon the idea of solving a polynomial or trigonometric function within some oscillatory error bound, so I would assume these methods also suffer from Gibbs and Runge's phenomenon. $\endgroup$ – Frosty May 22 at 22:49
  • $\begingroup$ I am not well-versed in approximation theory, my expertise is general scientific computing with a lot of focus on numerical linear algebra. But to my best knowledge, all approximation techniques (including interpolation) suffer from something. It may be that we know that there is an approximant but don't know how to find it, or we know how to find a potential approximant but there are examples for which our algorithms do not work. That said, linear and non-linear regression techniques are popular; mainly you choose a basis (model) and try to fit the model to the data. Aside from that, IDK much $\endgroup$ – Abdullah Ali Sivas May 23 at 0:41
  • 1
    $\begingroup$ ... continued: and to state my definition off the top of my head: I'd say interpolation is a special kind of approximation where the error functional is evaluated in a collocation-style, i.e. via the deviation at certain points, and the number of parameters is not larger than the number of unknowns (in order to exactly match the interpolation conditions). $\endgroup$ – davidhigh May 23 at 7:22
  • 1
    $\begingroup$ @davidhigh, done. Thanks for the suggestion. I think it improved the answer quite a bit. $\endgroup$ – Abdullah Ali Sivas May 23 at 8:20

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.