ansaurus

Question

Answer 1

+1 A:

Higher-order functions are discrete. They don't have the Cartesian quality of having arguments that have well-defined mappings to points in some n-dimensional space.

However, with your clarification on the answer, there are several things that can be said. Symbolically differentiating some higher-order functions would be possible, but only for certain calling patterns that resolve to well-known functions.

Probably, numerical differentiation would be more fruitful, as it can estimate the derivative by repeatedly evaluating the given function.

Also, functions that are totally general - and your example is heading that way, with use of relatively arbitrary functions - eventually you'll hit Turing completeness, which will mean that no amount of cleverness on the part of a symbolic differentiator will be able to automatically differentiate the function.

Barry Kelly 2008-11-26 15:28:29

take a look at the edit - i posted an example. this is for my own curiosity, but i can see systems which need derivatives which would use higher-order functions.

Claudiu 2008-11-26 15:35:08

hm... i think you have a flawed argument about turing completeness, there. there are transformations you can do to any arbitrary code - this doesn't mean they are bounded by turing completeness.

Claudiu 2008-11-28 21:38:03

Claudiu, Turing completness is a hard bound that prevents you from knowing everything about functions in a sufficiently expressive language. If you have a function which doesn't even return a value (i.e. does not terminate), how can you expect to get its slope at a point?

Barry Kelly 2008-11-28 23:39:28

Turing completeness is basically the hard limit to automatic analysis of code. What would the slope of a function that never returns mean, anyway? In what way would the derivative be correct?

Barry Kelly 2008-11-28 23:41:47

Higher order functions are not inherantly discrete: they are just functions that maps functions to functions. Indeed, the derivative itself is a perfectly valid higher order function. I also don't know what you mean by the "Cartesian quality of having arguments that have well-defined mappings to points in some n-dimensional space". Every function has a well defined mapping from it's arguments to an output domain - that's what defines a function. The problem here relates more to defining a derivative for the function space; it's not clear what the derivative of a list of items would even be.

Adam Wright 2010-04-30 19:31:12

@Adam - what I meant was that functions aren't points in some continuous space. What do you get when you subtract one function from another, and divide it by the distance between the functions? What does that even mean? That's what I meant by discrete, as opposed to continuous locations in some space, where distance has a meaning and slope can be measured.

Barry Kelly 2010-05-01 01:43:11

Sure they are - e.g., they space of continuous functions is Banach (i.e. a topological space, on which continuity is well defined). As they are Banach, they come complete with a norm allowing us to define concepts of "distance" in some way - and even a notion of derivative (in this example, the Frechet derivative). I'll agree that these are pretty abstract definitions, and not what the poster wanted, but circles back to my point - getting the definitions right, i.e. what property does the poster expect of his "derivative"?

Adam Wright 2010-05-01 21:14:41

@Adam - and that is useful precisely to the degree that map, sum etc. are continuous functions. In other words, I'm not sure what you're trying to prove, apart from being unhelpful.

Barry Kelly 2010-05-02 00:39:05

I'm trying to help you update your answer without jumping in and editing it (the entire first paragraph is just mathematically wrong), and the questioner update his question with more of what he actually wants.

Adam Wright 2010-05-02 11:35:51

Just to clarify, I'm not disagreeing with the general thrust of your answer - just that, as it's accepted, a few specifics could be clearer. I would edit it, but I don't like altering other peoples answers.

Adam Wright 2010-05-02 11:56:04

Answer 2

+2 A:

A good AD system will breeze through that without any difficulty. If the AD code performs source to source translation then it may have trouble with the sum. But if it's an AD system that works by overloading the arithmetic operators then the AD code won't actually 'see' the sum function, just the + operations that the sum function calls.

2010-04-30 19:14:16

ansaurus

tags:

views:

answers:

Derivative of a Higher-Order Function

related questions