5
$\begingroup$

Suppose I have $n$ samples $(x_i, f(x_i))_{i=1}^n$ from an unknown function $f$. I need to approximate (estimate) the derivative $f'(x^*)$ at some new test point $x^*$, that is not necessarily one of the $x_i$. I am assuming nothing about the $x_i$: They can be regularly or irregularly sampled, have large gaps, etc.

Naively, numeric differentiation seems like the only option. The "other" option would be automatic differentiation, but from my understanding of this you have to actually know $f$ in order to use auto-differentiation.

Suprisingly, in all of the auto-diff tutorials I have come across, this assumption is never mentioned.

So, now I wonder if there is some way to apply auto-diff to my problem that I haven't come up with. (Or, some other method altogether besides numerical differentiation.) General references on this problem are welcome as well!

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ If you don't know the function (just its output), then numerical differentiation is your only option. $\endgroup$
    – Carlo Beenakker
    Commented Oct 25, 2017 at 13:33
  • 1
    $\begingroup$ You don't need an explicit formula for $f$ when doing automatic differentiation, but you do need to be able to compute $f$ via code that uses only arithmetic, evaluation of functions for which you can compute the exact derivative (either separately or using the automatic differentiation recursively), and, if you're careful, if-then statements. If you know only values of $f$ for a discrete set of points, you can't use automatic differentiation. This all, I think, is pretty clear from any detailed explanation of automatic differentation. $\endgroup$
    – Deane Yang
    Commented Oct 25, 2017 at 14:16
  • 2
    $\begingroup$ @Deane: These are good points. This question arose due to the recent resurgence of auto-diff, and the many many fanboy-ish tutorials that more or less claim that auto-diff is a complete replacement for numerical differentiation, without no discussion of its drawbacks. The use case I have outlined above seems to be a pretty clear limitation, and you are right that it seems impossible. $\endgroup$
    – JohnA
    Commented Oct 25, 2017 at 21:11
  • $\begingroup$ Lets say we have these f(xi) = [3,4,5,2]. i refers to index of the vector [3,4,5,2]. So f(2) = 4. We here dont know the function f. We want to calculate f(4.2) Coming to Numeric Differentiation: df(x)/dx = (f(4+0.2) - f(4))/0.2 But here we dont know what f(4.02) would be.... So how would we calcuate it? $\endgroup$
    – akshit bhatia
    Commented May 25, 2020 at 15:11

3 Answers 3

Reset to default
8
$\begingroup$

Automatic differentiation needs the structure of the function ( computation graph, or preferably a straight line program).

In your case, I am not sure how numeric differentiation helps to get a reliable result. If your parameter space is high-dimensional, you are completely screwed. If not, you can interpolate the function by a smooth function (InterpolatingFunction[] in Mathematica) and then differentiate said smooth function to get a number out. Whether or not that number has anything to do with reality is anyone's guess. To differentiate the smooth function, you can use automatic differentiation.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Check out Tangent by Google, which is an automatic differentiation package in Python. They just released the code a week ago github.com/google/tangent $\endgroup$
    – Dendi Suhubdy
    Commented Nov 13, 2017 at 20:53
  • 1
    $\begingroup$ @DendiSuhubdy Is this any better than all the other automatic differentiation libraries for python? $\endgroup$
    – Igor Rivin
    Commented Nov 14, 2017 at 0:23
  • $\begingroup$ Yes it actually uses source-code to source-code generation, compared to HIPS autograd or Pytorch Autograd needs to do taping, while for Tangent you know ahead of time what your gradients (for example w.r.t your loss function might be). $\endgroup$
    – Dendi Suhubdy
    Commented Nov 14, 2017 at 4:20
  • 1
    $\begingroup$ @DendiSuhubdy Cool! Thanks for the pointer! $\endgroup$
    – Igor Rivin
    Commented Nov 14, 2017 at 4:26
5
$\begingroup$

If your $f$ is a probability distribution, then you can use a kernel density estimate to estimate the derivative. For a bit more detail and relevant references, see section 2.2 of A Tutorial on Kernel Density Estimation and Recent Advances by Yen-Chi Chen.

Another approach that might work better in high dimensions would be to use a neural net to get an analytical approximation of the function as in Smooth function approximation using neural networks by Ferrari and Stengel.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a great alternative approach. The reference to "density derivative estimation" in YCC's survey is particularly helpful. Thanks! $\endgroup$
    – JohnA
    Commented Oct 25, 2017 at 21:12
  • $\begingroup$ @JohnAustin Note that you can do automatic differentiation in either approach $\endgroup$
    – Steve Huntsman
    Commented Oct 25, 2017 at 21:25
  • $\begingroup$ This is a really good point; I didn't even think of that! (I think that's worth adding to your answer.) $\endgroup$
    – JohnA
    Commented Oct 25, 2017 at 21:42
0
$\begingroup$

I would apply a nonlinear regression algorithm using, for example, SVMs (http://www.di.ens.fr/~mallat/papiers/svmtutorial.pdf). You can look for software like SVM (look for the las version of LIBSVM for Matlab, python and others). You can also use Gaussian Processes (http://www.gaussianprocess.org/gpml/ --it comes with open software).

Once you have your regression function, then you can simply compute its derivative. The Gaussian Process software above can compute the derivatives of the functions. Or you can simply plot your regressed function and then apply a numerical differentiation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This would not be a good idea in general, especially if the data more or less fits a line. A Gaussian process regression will generate a non-linear function, even if there are only two input/output pairs - even in this simple case, the derivatives would be incorrect. Just play around with this Gaussian process regression demonstration chifeng.scripts.mit.edu/stuff/gp-demo. Also note that Gaussian process regression will most likely not even honor the known input/output relationship, i.e., g(xi) != f(xi), for g the Gaussian regression of f, and f(xi) a known output at input xi. $\endgroup$
    – A.L.
    Commented Jul 3, 2018 at 4:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .