supernova.'s blog

Neural Networks and Polynomial Interpolation
By supernova., history, 6 years ago, In English

Hello everyone!

I know this topic is a little bit far from usual competitive programming, but I was wondering if anyone here could help me in understanding this little concept.

I've been into machine learning lately, and I was wondering about the difference between a "Learning Function" and "Polynomial Interpolation". Consider a dataset where we have a set of points (x0, x1, ..., xn) and their corresponding images (y0, y1, ..., yn). Now if we want to have a neural network that learns the function f(x) = y, isn't that the same as constructing an interpolating polynomial that fits the points? Or is there a hidden difference between the two concepts?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The main reason for using a neural network is that they are so powerful in classifying points using a non linear boundary and we don't have to find the right set of polynomial that works . The whole training algorithm takes care on it's own.

You are correct in saying that we can use polynomial interpolation to fit the points but finding the right degree becomes cumbersome and as the degree increases the number of features also grows very fast. Suppose you have n features and you try to approximate with a d degree polynomial. Then the total number of polynomial features is the number of ways you can have x1p1..xnpn such that p1 + p2... pn = d.

This is mitigated by the use of neural networks

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think polynomial interpolation is the right word though, I am not sure what op meant, but polynomial interpolation means you have to fit the curve exactly with 0 errors. I think what u meant here is polynomial curve fitting.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah , I don't think polynomial interpolation can be used directly . It will cause serious over-fitting.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        yeah, I am just pointing out so op wont be confused by the term :)

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much that was really helpful!

    One more question though (Sorry ;P) ... So Neural Networks are actually constructing a function that fits the data? We just don't know the degree and it does that automatically?

    What about "extrapolation" vs "generalization"? What is the difference between the two terms?

    Edit: I just read that extrapolation is actually curve fitting.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So Neural Networks are actually constructing a function that fits the data? We just don't know the degree and it does that automatically?

      Yes, the goal of neural networks is to find a function that fits the data best(in terms of lowest error defined by us). It is mostly not polynomial as there are activation function such as tanh, relu or sigmoid, and it usually is really messy to write it as a function(assuming your neural net is quite deep). Yes, it does it automatically by finding the lowest error with algorithms such as gradient descent.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Using polynomial interpolation would be overfitting in most of the machine learning problems.

→ Reply