4
$\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!

$\endgroup$
  • 2
    $\begingroup$ If you don't know the function (just its output), then numerical differentiation is your only option. $\endgroup$ – Carlo Beenakker Oct 25 '17 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 Oct 25 '17 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 Oct 25 '17 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 May 25 at 15:11
7
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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 Nov 13 '17 at 20:53
  • 1
    $\begingroup$ @DendiSuhubdy Is this any better than all the other automatic differentiation libraries for python? $\endgroup$ – Igor Rivin Nov 14 '17 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 Nov 14 '17 at 4:20
  • 1
    $\begingroup$ @DendiSuhubdy Cool! Thanks for the pointer! $\endgroup$ – Igor Rivin Nov 14 '17 at 4:26
4
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a great alternative approach. The reference to "density derivative estimation" in YCC's survey is particularly helpful. Thanks! $\endgroup$ – JohnA Oct 25 '17 at 21:12
  • $\begingroup$ @JohnAustin Note that you can do automatic differentiation in either approach $\endgroup$ – Steve Huntsman Oct 25 '17 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 Oct 25 '17 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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Allan Jul 3 '18 at 4:59

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.