Methods - Differentiation, Root Finding etc

[David Samborski]

I'm writing some functions for my latest project involving computing derivatives and root finding. What does everyone think of these methods? I've used the fact that functions are first class in order to pass them along in an easy manner. 

http://play.golang.org/p/hnLbRZF0GX

Certainly some things to improve, but it seems to work pretty well. What are people thinking in terms of packages for Differentiation, Integration etc? With something like this there is a need for a central package that defines function interfaces and such.

[N Riesco]

If you're familiar with C, the following links to the GSL library may be of inspiration:

http://www.gnu.org/software/gsl/manual/html_node/One-dimensional-Root_002dFinding.html

http://bzr.savannah.gnu.org/lh/gsl/trunk/annotate/head:/roots/newton.c

Function Newton in your example doesn't do what you think, p0 needs updating within the loop.

[David Samborski]

Thanks for the links, and also for spotting that bug. Not sure how long before I would have found it, though I did have the correct algorithm in my reference, it was just me who didn't write it out correctly.

I've added created some packages that I'd like to integrate into gonum, but I wanted to know what everyone thought. Here they are.

https://github.com/Arrow/nm

There are a few things I'd like to get some opinions on. I've used some package level variables which lets people modify stuff like step size without cluttering up the function signatures. It might be better to declare objects though like a derivator struct that contains those values.

Also, I've found it useful to have a central package that has declarations like function (util.Function in my code). Also, I've placed a function in that package to check a tolerance. Thanks for any feedback.

By the way, I found a couple bindings to the c gsl library or a pure go implementation of the gsl stats package. Do we want to integrate them into gonum if it's possible?

[Brendan Tracey]

Thanks for starting this.

I think we need to think more about how all of this works before committing anything to gonum. I realize that we are moving more slowly than any of us would like, but I think it's important to avoid having too much stuff no one is happy with.

Specifically on this point, we will need a root finding method/package for sure. However, root finding is very related to optimization, and as a result the two packages should share common packages and possibly use common routines. I've started an optimization package, and there has been discussion on possibly better ways to construct it. I haven't had a chance to respond fully to the comments, but I think this package works fully into the discussion.

My major concern is that we make sure that packages are flexible, and ideally will do one thing and do one thing well, that they are orthogonal, and that they scale up to large problems. I think your current design lives up to the first criterion, but I think it fails at the last in your current root finding implementation. For a large problem, computing a 5 point central difference scheme will be very expensive. The Newton method should take in a function (or object, or something) that returns a value and a derivative. This way, for functions where the derivative is computable, it does not require any additional function evaluations. For functions where one cannot (or do not want) to compute the derivative, you can instead use a function closure combined with to compute the derivative. In this way, the two packages become orthogonal. Differentiation is a way of finding differentials of functions, and newton takes in a function that returns a value and derivative and finds its root.

More generally, I do think it's good to have a differentiation package, and I'm glad to have you start it. However, maybe in the end this should be differentiation/finitedifference (or something) as there are other techniques for finding derivatives (Complex Step, Automatic differentiation, etc.). We won't have all these methods any time soon, but it would be nice to plan for them.

On the differentiation package, It would be nice to be able to make it a little more general. There are a number of different stencils you can use (5 point, one sided, etc.), and there is a way of solving for the proper coefficients using Taylor Tables. It would be pretty cool to have that all done automatically (i.e. the user can specify a set of points and the algorithm finds the difference), with a couple of specific cases hard coded. Forward difference, backward difference, central difference, 5 point central, etc. To interface with the Newton method (and the optimization package), you'd like to have a routine which takes in a function (or object or whatever) and returns a function that gives a value and derivative. With all these methods defined, the user could specify how that finite difference is obtained by specifying one of those methods (and there could be a default). This would be an improvement over matlab where you only have a few choices, and so would increase the flexibility.

I'm not a big fan of the step size as a package variable, I would rather see it as an input (perhaps somehow defaulted). I think the specific decision on this should be discussed alongside the optimization package. It shouldn't be a package variable because you may want to have two functions being concurrently computing fzero with a different step size.  

Why do you think the type Function is necessary? 

I think it's a good idea to have a stats package, but that's probably best moved to a different thread. I'd prefer to see native go tools, but that can be open for debate.

Thanks again for the start,

Brendan

--
You received this message because you are subscribed to the Google Groups "gonum-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gonum-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[David Neumann]

I would separate the function and the derivative since often you want to calculate only one of those values at some point in an algorithm.

I also think that a numerical differentiation package should provide several functions which take a mathematical function as a function object (and some parameters) and return an approximation of the derivative as a function object. This should be totally decoupled of any other package.

As for something like root finding, a solver could take two arguments, the function and the derivative with the derivative being optional, i.e., it can be set to nil.

If no derivative is provided it is probably better to use an algorithm that does not neet any derivatives instead of approximating them, but I am not sure about that.

Regarding the optimization stuff, I think it is a good idea to provide several independent packages for optimization, for example

- unconstraint optimization (steepest descent, conjugate gradient, quasi newton etc.)

- general convex optimization (e.g. projected gradient method, (quasi-)newton for simple box constraints)

- linear/conic/semidefinite programming (interior point/barrier methods)

- non-convex optimization (branch and bound, etc.)

- integer programming (not my area of expertise) 

The problem is that there is no official matrix package yet, and if you go beyond one dimensional optimization you might need some advanced operations.

I think it is time for someone push a matrix package onto gonum so that we have something to work with.

I can also do it if no one else wants to ...

[David Samborski]

Thanks Brendan and Dave for the feedback. There are a lot of good points in there, so I've been mulling them a bit. I sort of see two issues at the moment. Package structure and general types (like function or how differentials fit with other packages). Here are my thoughts on each of these issues.

Package Structure

As Brendan pointed out, we should impose certain requirements on our package structure.

1) Flexibility

2) Good at one thing idiom

3) Orthogonality

4) Scalability

I would also add one more.

5) Readability (for example force.Pound instead of unit.Pound): This should be for precision and accuracy from the user's perspective.

For the differentiation package, I don't see a need to split it up further, though maybe the names of ThreePoint(...) and FivePoint(...) aren't the greatest. I would suggest a shorter name if possible, and I was thinking "deriv" or "derive". I think having all the differentiation algorithms start with "derive.(Algo Name)" is probably a good idea and less confusing.

For the root finding package, I'd suggest keeping it separate from optimize, though as you say, optimize will depend on it quite heavily. The main reason I say this is because I wouldn't have looked in optimize for Newton's method. That's due to the fact that I haven't worked with optimization methods much, but that's bound to happen so I think it's a good argument to make. I think as long as the orthogonality is well satisfied by how these algorithm's fit together, it shouldn't be a problem. That segs well into the next issue.

General Types

I think we should have a "general" or "utilities" package that defines some basic interfaces and types. I think Function is important, but the more I think about it, the more I think it should be an interface. Here's how I see the interfaces working.

http://play.golang.org/p/Dw3J45K-EK

This becomes easy to add types since you need to satisfy the interface, then you can use any algorithm you choose that requires that interface. It's trivial if you already have your function and derivative (should already be defined). There is a bit of a circular declaration issue. util declares the interfaces, differentiation depends on the interfaces, and util wants to declare types using differentiation. But I think that's solvable by moving the interfaces into a sub directory.

As for how algorithms will store their parameters before computation, I think we should define structs that contain parameters like step size. One of the things that separates go is it's ability to do concurrent computation. We should aim to have our solvers be self contained such that they can be passed to different goroutines to be called. My example above doesn't do this, but I intend to add it to my code in the previous post.

For optimize and matrix, I probably don't have much to add. For optimize it's because I don't have much experience, and for matrix I think others generally have it covered (though I agree a basic package should be added to gonum).

If there was anything I didn't cover it was me who missed it. I think all the points were valid, it was just a lot to cover. I probably won't work on this much over the weekend, but I might check in later today. The weekend is a wash for me, but I'll get back into it next week.

Dave

[Brendan Tracey]

On Thursday, June 20, 2013 1:01:58 PM UTC-7, David Samborski wrote:

Thanks Brendan and Dave for the feedback. There are a lot of good points in there, so I've been mulling them a bit. I sort of see two issues at the moment. Package structure and general types (like function or how differentials fit with other packages). Here are my thoughts on each of these issues.

Package Structure

As Brendan pointed out, we should impose certain requirements on our package structure.

1) Flexibility

2) Good at one thing idiom

3) Orthogonality

4) Scalability

I would also add one more.

5) Readability (for example force.Pound instead of unit.Pound): This should be for precision and accuracy from the user's perspective.

Agreed. The trick is in balancing these requirements (especially balancing 1 and 5 can be difficult), which is why I like having this group.

 

For the differentiation package, I don't see a need to split it up further,

Agreed, except what I said above about there being many ways of automatic differentiation, http://en.wikipedia.org/wiki/Automatic_differentiation , so it might be worth having 

gonum/differentiation/finitedifference ( though maybe just fd) 

so that later we can also have

gonum/differentiation/complexstep

I'm not sure what the right answer is, just pointing out a possible issue.

 

though maybe the names of ThreePoint(...) and FivePoint(...) aren't the greatest. I would suggest a shorter name if possible, and I was thinking "deriv" or "derive". I think having all the differentiation algorithms start with "derive.(Algo Name)" is probably a good idea and less confusing.

Maybe just "diff"? Deriv can be confused with a proof. Diff can be confused with subtraction, but I don't think we'd ever need a package for subtraction. Maybe there are different names in other fields, but I would vote for "Forward/Backward/Central difference", which are the names wikipedia has

http://en.wikipedia.org/wiki/Finite_difference 

 

For the root finding package, I'd suggest keeping it separate from optimize, though as you say, optimize will depend on it quite heavily. The main reason I say this is because I wouldn't have looked in optimize for Newton's method.

Agreed. This also matches the Matlab convention with Fzero being one tool and Fminunc being another.

 

That's due to the fact that I haven't worked with optimization methods much, but that's bound to happen so I think it's a good argument to make. I think as long as the orthogonality is well satisfied by how these algorithm's fit together, it shouldn't be a problem. That segs well into the next issue.

Yea, my point was more that the convensions between the two packages should match. For example, on the next point, our equivalents of Fmin and Fzero should use the same Functioner interfaces, rather than one taking a type and the other taking a function handle. 

 

General Types

I think we should have a "general" or "utilities" package that defines some basic interfaces and types. I think Function is important, but the more I think about it, the more I think it should be an interface. Here's how I see the interfaces working.

http://play.golang.org/p/Dw3J45K-EK

I think something like this is the right answer as well. In the current optimization package, I have Eval() and Deriv() rather than Function and Deriv.

It is important that we be as picky as possible with minimizing function evaluations. In my experience, for problems where optimization is the bottleneck, it's the cost of the function itself that dominates rather than all the rest of the optimization code. For the problems I work with, reducing the number of function evaluations is more important than, say, simplicity and legibility of code. It's easiest to write a code that just uses finite difference to compute the derivative, but I cannot use that tool for the kinds of problems I run.

That was a bit of a tangent, but I bring it up because I'm not sure what to do about Eval() and Deriv(). On the one hand, it's good to separate them out because some codes don't need to compute the function value and the derivative, and it's good to save the computation when possible. On the other hand, some codes share significant computational overlap between computing the evaluation and the derivative, and so calling both at once would be more efficient that calling each separately. There are tricks that can be done to avoid this, and I think we should think about how those tricks would work so that there's a common assumption throughout gonum. Either that, or we could have

Evaler interface{

Eval(float64) float64

}

Deriver interface{

Deriv(float64) float64

}

EvalAndDeriver interface{

EvalAndDeriv(float64) (float64, float64)

}

It's not clear to me at the moment what the best way forward is.

 

This becomes easy to add types since you need to satisfy the interface, then you can use any algorithm you choose that requires that interface. It's trivial if you already have your function and derivative (should already be defined). There is a bit of a circular declaration issue. util declares the interfaces, differentiation depends on the interfaces, and util wants to declare types using differentiation. But I think that's solvable by moving the interfaces into a sub directory.

As for how algorithms will store their parameters before computation, I think we should define structs that contain parameters like step size. One of the things that separates go is it's ability to do concurrent computation. We should aim to have our solvers be self contained such that they can be passed to different goroutines to be called. My example above doesn't do this, but I intend to add it to my code in the previous post.

Yep. It's also nice because it allows default arguments

CentralDifference(Evaler, Settings)

and Settings could be got from

diff.DefaultSettings() *Settings

That way specific arguments can be adjusted by the caller as needed.

 

For optimize and matrix, I probably don't have much to add. For optimize it's because I don't have much experience, and for matrix I think others generally have it covered (though I agree a basic package should be added to gonum).

If there was anything I didn't cover it was me who missed it. I think all the points were valid, it was just a lot to cover. I probably won't work on this much over the weekend, but I might check in later today. The weekend is a wash for me, but I'll get back into it next week.

That's the problem. So many things to do, so little time to do it.

[Dan Kortschak]

Sorry to harp on this, but as a non-British/non-American resident, I
want to again (more seriously) point out the issues with using Imperial
metrics.

The issues (apart from the difficulties in using the units in a safe and
sensible way as demonstrated on a number of occasions throughout
history) are the highlighted in David's list below: specifically items 3
and 5 (5 may be subjective to a degree given cultural background).

3. If we provide SI units, then Imperial units are not orthogonal.

5. This is really two issues: 1. Having more than one way of expressing
a unit reduces readability for all concerned and the interaction of
packages from different locales becomes difficult to disentangle (do we
want Go to be responsible for another Mars crash?); and 2. For people
not raised in Imperial units, the non-systematic nature of the 'system'
allows easy confusion (eased by the suggestion in 5. below), e.g. is a
pound a unit of force or of mass - SI has very clear definitions of
these.

I would like to suggest that to allow for all of the issues raised below
in the context of the problems above that we have a unit
internationalisation package or packages that people who need (for
whatever reason) to use non-SI unit to be able to import. I see this as
a family of unsafe-unit type packages. This this approach we can focus
on the actual dimensions and not the representation.

Dan

[David Samborski]

Structure

I think we both agree to create:

/util or /utilities or /general

/root   and

/diff

I'd lean towards keeping the forward difference under the base directory in root, though you have a point for the automatic differentiation. I don't mind having just that under something like /diff/autodiff . What do you think? I also like the forward/backward/central convention. The only reason I had 3 point and 5 point was because that's what my numerical methods book was calling them.

Can you show an example of the types of problems you're thinking of? I agree we should minimize the number of function calls if possible. I'd lean towards passing functions around as this is more likely to minimize these calls. Or at least we can control it a bit more. If we get user's to create their own eval(float64)float64 functions, they might do unnecessary indirection. It might happen the other way too, but they need to create less, so they're more likely to do it properly. 

I think we should have an interface that supports evaluating the function and derivative through separate functions, then another that evaluates them together. If you have an optimize function (just to say) that could benefit from that, create one function that accepts the seperate function interface, and one that accepts the combined function interface. Or combine it in one with a type switch.

As for the general package. I'm leaning to calling it "util" as it's short and makes it clear that it's for general purpose utility functions. Can I ask to have "util", "root" and "diff" created?

Btw, Dan I was trying to thank you in my last message. Sorry for the typo. That's what I get for trying to write it too quick.

[Brendan Tracey]

On Thursday, June 27, 2013 3:02:27 PM UTC-4, David Samborski wrote:

Structure

I think we both agree to create:

/util or /utilities or /general

/root   and

/diff

I'd lean towards keeping the forward difference under the base directory in root, though you have a point for the automatic differentiation. I don't mind having just that under something like /diff/autodiff . What do you think?

That's probably fine. Autodiff is a lot more intrusive (and a lot harder to code) than finite-difference, so it's okay to be in a subpackage.

 

I also like the forward/backward/central convention. The only reason I had 3 point and 5 point was because that's what my numerical methods book was calling them.

Cool. I do think we should have a taylor series routine to do arbitrary stencils (maybe arbirary points even), and just explicitly code up a small number (3-8), maybe Forward/Central/Backward for the two point stencil and for 2nd derivatives.

 

Can you show an example of the types of problems you're thinking of?

Really any problem where the objective takes more than a couple of seconds the runtime is dominated by the function calls rather than the algorithm itself.

In the neural net algorithm, computing the derivative requires computing the objective function, as one example. Many other problems (say, a polynomial), the function value and derivative are computed without common computation (well, even in the polynomial case you could cache x, x^2, x^3, etc.)

 

I agree we should minimize the number of function calls if possible.

I would go stronger and say "above most else". Even if we don't provide the best routines, we should try to make it so the user can supply their own routine if there's some trick for their problem that makes it easier. This is why, for example, we should allow the derivative computation with a function call rather than finite difference. Not only is it better to eliminate function calls, but maybe in my problem I know the derivative reduces to x^2 (whatever), so I barely need to compute anything. Similarly, certain types of optimization algorithms work much better on some functions rather than others. We should make it easy to create new optimization algorithms. I'm not sure that this really applies to root-finding, but it might.

 

I'd lean towards passing functions around as this is more likely to minimize these calls. Or at least we can control it a bit more. If we get user's to create their own eval(float64)float64 functions, they might do unnecessary indirection. It might happen the other way too, but they need to create less, so they're more likely to do it properly. 

I'm not sure I follow, sorry, could you elaborate?

 

I think we should have an interface that supports evaluating the function and derivative through separate functions, then another that evaluates them together. If you have an optimize function (just to say) that could benefit from that, create one function that accepts the seperate function interface, and one that accepts the combined function interface. Or combine it in one with a type switch.

Yea, I think one of those options is pretty good.

 

As for the general package. I'm leaning to calling it "util" as it's short and makes it clear that it's for general purpose utility functions. Can I ask to have "util", "root" and "diff" created?

Actually, I liked your suggestion of "general". It's much less vague than "util"

[David Samborski]

On Thursday, June 27, 2013 3:06:35 PM UTC-5, Brendan Tracey wrote:

I would go stronger and say "above most else". Even if we don't provide the best routines, we should try to make it so the user can supply their own routine if there's some trick for their problem that makes it easier. This is why, for example, we should allow the derivative computation with a function call rather than finite difference. Not only is it better to eliminate function calls, but maybe in my problem I know the derivative reduces to x^2 (whatever), so I barely need to compute anything. Similarly, certain types of optimization algorithms work much better on some functions rather than others. We should make it easy to create new optimization algorithms. I'm not sure that this really applies to root-finding, but it might.

 

I'd lean towards passing functions around as this is more likely to minimize these calls. Or at least we can control it a bit more. If we get user's to create their own eval(float64)float64 functions, they might do unnecessary indirection. It might happen the other way too, but they need to create less, so they're more likely to do it properly. 

I'm not sure I follow, sorry, could you elaborate?

 

I'm basically suggesting we should use Functioner over Evaler (though I'm not crazy about the name Functioner, just the structure). Here's a quick example I wrote up as an example of why I think it makes sense. Look how often Eval is called vs Function.

http://play.golang.org/p/QZfIo8vk-O

I'm sure with Evaler you could eliminate some of those calls, but basically the user needs to implement the Evaler interface. When they have a single function, I think it's not likely to happen (ie they'll use a basicfunc type from the "general" package). What do you think?

As for the general package. I'm leaning to calling it "util" as it's short and makes it clear that it's for general purpose utility functions. Can I ask to have "util", "root" and "diff" created?

Actually, I liked your suggestion of "general". It's much less vague than "util"

Alright, I'm good with that. I'll post in the general management thread asking for "general", "root" and "diff" packages be created. 

[Brendan Tracey]

On Thursday, June 27, 2013 4:55:03 PM UTC-4, David Samborski wrote:

On Thursday, June 27, 2013 3:06:35 PM UTC-5, Brendan Tracey wrote:

I would go stronger and say "above most else". Even if we don't provide the best routines, we should try to make it so the user can supply their own routine if there's some trick for their problem that makes it easier. This is why, for example, we should allow the derivative computation with a function call rather than finite difference. Not only is it better to eliminate function calls, but maybe in my problem I know the derivative reduces to x^2 (whatever), so I barely need to compute anything. Similarly, certain types of optimization algorithms work much better on some functions rather than others. We should make it easy to create new optimization algorithms. I'm not sure that this really applies to root-finding, but it might.

 

I'd lean towards passing functions around as this is more likely to minimize these calls. Or at least we can control it a bit more. If we get user's to create their own eval(float64)float64 functions, they might do unnecessary indirection. It might happen the other way too, but they need to create less, so they're more likely to do it properly. 

I'm not sure I follow, sorry, could you elaborate?

 

I'm basically suggesting we should use Functioner over Evaler (though I'm not crazy about the name Functioner, just the structure). Here's a quick example I wrote up as an example of why I think it makes sense. Look how often Eval is called vs Function.

http://play.golang.org/p/QZfIo8vk-O

I'm sure with Evaler you could eliminate some of those calls, but basically the user needs to implement the Evaler interface. When they have a single function, I think it's not likely to happen (ie they'll use a basicfunc type from the "general" package). What do you think?

I haven't benchmarked it, but I'm not sure your argument is really valid. Yes, Eval is called a number of times, where as Function is only called once, but f1 is called a number of times. I would guess that these two have virtually identical run times. In any event, for this use case, even if I'm wrong the overhead from the function call is going to be negligible. This decision should be made on which of Functioner vs. Evaler is easier to read and implement rather than deciding based on a couple of FLOPS. I would guess that Functioner is easier to think about, but I'd need to try both a couple of times.

[David Samborski]

You might be right in the end. Readability will likely be the main concern for this decision. I've updated the code from my differentiation and root finding code. I've updated it with the Fuctioner and Differ interfaces, to give you something you can try out. I figure your optimization code uses the Evaler interface in any case so it will let you have a comparison. Let me know what you think.

I've also added what my thinking was for algorithm settings. The idea is for each type of algorithm you have a struct that contains information such as step size and estimate for the error (see Central). It also lends itself to your thinking about parallel computing (in the other thread). If each algorithm contains all the info needed to perform a calculation, it becomes easy to pass the pointer around and even copy it to another machine for processing.

There's also some new function definitions that I'm working on to test the diff package. Check out the reference in "all_test.go". It's a bit of an old reference, but the functions seem like good ones to test.

[David Samborski]

I'm going to upload these packages as is, but it might take me a day. I'll probably put some sort of experimental message as we haven't decided basic stuff yet, so I don't want people relying on the current API. Let me know if you've had any thoughts on the functioner vs evaler decision.

[Brendan Tracey]

Okay, how about this:

We use both. Eval is the general function, for when the optimizer/root finder needs everything. Function, Gradient, Constraint, etc. are all specific methods if the optimizer can use only parts of it. None of them are specific interface definitions, but for example, if my function is to be called by a gradient-based optimizer, I would have

type MyFun struct{}

func (m *MyFun) Eval(x []float64) (f float64, g []float64)

func (m *MyFun) Function(x []float64) (f float64)

func (m *MyFun) Gradient(x []float64) (g []float64)

Not all of these would be mandatory, for example, lbfgs needs to always evaluate both the value and the derivative, but all could be implemented in case the caller wants to use a method that can. By having Eval, the function implementer can do memoization (or whatever) to share computation knowing both the value and the derivative are needed. Similarly, if an optimizer only needs the function value, it could call Function(x) and MyFun would know it doesn't need to compute the derivative (thus saving some cycles).

For a black-box constraint-based optimization, it might look something like

func (m *MyFun) Eval(x []float64) (f float64, g []float64, c []float64)

though constraints get tricky fast, so the actual demand on the user might be more (linear constraints, box constraints, etc.) 

The important point is to have Eval() represent everything (which is often what is needed) but to keep in mind the idea of also having Function() Gradient() etc. to allow for more fine-grained control when appropriate.

[David Samborski]

I agree that we should allow users to control the amount of computation where appropriate. I think the basic algorithms should declare what behaviour is needed(for example specify a FuncDiffer to say you want both the function and the derivative). I've added an Evaler interface to package general. If an algorithm can really benefit from calculating both at the same time, you can do a type switch to an Evaler and proceed with Eval. In some cases though, your data might not be conducive to calculating both at the same time (the general case of BasicFunc is an example), in which case it would just proceed with Function() / Diff().

I'd like to leave the function signatures in the general case as returning a (func(float64) float64). This lets us easily tie different packages together (eg, we can use the floats.Apply function to apply this to a slice). More general cases could have just a simple compute function with no input or output that stores the result into a structure. This would let us build a package that can easily do distributed computing. Pass around the object until it gets to the target hardware, call it's Compute() method, wait (presumably a long time) then report back to the central computer the result or asking what to do with the result. See the Central algorithm in the diff package. That's closest to what I was imagining.

Thinking about it further, I'm almost wondering if we want to define what our data is by an interface as well. Then our functions would be of the form ( func(in Data) (out Data) ). That would separate the definition of our algorithms (ie descriptions of how to process the data) from the data themselves. Then when an algorithm cares about a certain type of data (matrix or []float) it can do a type switch and use it that way.

I'm not sure if any of this makes sense. I'm just trying to help the various packages work well together, and leave future packages with an easier time through well designed interfaces. 

Cheers,

Dave

[Brendan Tracey]

On Jul 30, 2013, at 12:49 AM, David Samborski <bloggi...@gmail.com> wrote:

I agree that we should allow users to control the amount of computation where appropriate. I think the basic algorithms should declare what behaviour is needed(for example specify a FuncDiffer to say you want both the function and the derivative). I've added an Evaler interface to package general. If an algorithm can really benefit from calculating both at the same time, you can do a type switch to an Evaler and proceed with Eval. In some cases though, your data might not be conducive to calculating both at the same time (the general case of BasicFunc is an example), in which case it would just proceed with Function() / Diff().

To be honest, I'm with Dan here; I don't really see the point of general (at least as of yet). I think there will be some amount of overlap with root and diff, but I'd rather wait until we know exactly how and what it is before we start building off of a general package. 

I'd like to leave the function signatures in the general case as returning a (func(float64) float64). This lets us easily tie different packages together (eg, we can use the floats.Apply function to apply this to a slice). More general cases could have just a simple compute function with no input or output that stores the result into a structure. This would let us build a package that can easily do distributed computing. Pass around the object until it gets to the target hardware, call it's Compute() method, wait (presumably a long time) then report back to the central computer the result or asking what to do with the result. See the Central algorithm in the diff package. That's closest to what I was imagining.

Additionally, I don't see the point of the additional level of indirection behind Funcitoner(). If the user wants an additional level of indirection, they can just add a type (I think people will have to do that anyway for most cases). In the distributed computing case, for example,

type MyOptimizable struct{}

func (m MyOptmizable) Eval(x float64) (f,g float64){

return ReallyExpensiveFunction(x)

}

The level of indirection is already there. ReallyExpensiveFunction could contain all sorts of things (lots of more go routines, TCP calls, etc.)

Thinking about it further, I'm almost wondering if we want to define what our data is by an interface as well. Then our functions would be of the form ( func(in Data) (out Data) ). That would separate the definition of our algorithms (ie descriptions of how to process the data) from the data themselves. Then when an algorithm cares about a certain type of data (matrix or []float) it can do a type switch and use it that way.

I think this is exactly why we don't want to have it as you do. MyOptimizable as defined above can do their own translation of what "x" means. This way the root package is completely separate from the expensive function. What root knows is that it has a function which takes in a float and returns a float. Its job is to find the zero location of that value. What ReallyExpensiveFunction knows is that it takes in a float and returns a value and a derivative. MyOptimizable is the interface between what those two functions mean and how they relate to each other. 

I'm not sure if any of this makes sense. I'm just trying to help the various packages work well together, and leave future packages with an easier time through well designed interfaces. 

Understood. The other thing to remember is that it's not just one-dimensional inputs and outputs. Could be float slices, byte slices, etc. For the root package, this definition makes sense (and may belong in root). For the optimization package, it has to be SisoEvaler (or something).

I am very close to having a version of the optimization package that is in a state to be talked about. There are some clever things that you can do with it as far as interfacing to other packages goes. Hopefully not too long after I'll have a version of the neural net code that I have been building which shows how to use some of those clever things. I have not found using Eval equivalents directly to be a limiting factor in any way.

Thanks for putting in the effort,

Brendan

Cheers,

Dave

On Sunday, July 28, 2013 2:36:49 PM UTC-5, Brendan Tracey wrote:

Okay, how about this:

We use both. Eval is the general function, for when the optimizer/root finder needs everything. Function, Gradient, Constraint, etc. are all specific methods if the optimizer can use only parts of it. None of them are specific interface definitions, but for example, if my function is to be called by a gradient-based optimizer, I would have

type MyFun struct{}

func (m *MyFun) Eval(x []float64) (f float64, g []float64)

func (m *MyFun) Function(x []float64) (f float64)

func (m *MyFun) Gradient(x []float64) (g []float64)

Not all of these would be mandatory, for example, lbfgs needs to always evaluate both the value and the derivative, but all could be implemented in case the caller wants to use a method that can. By having Eval, the function implementer can do memoization (or whatever) to share computation knowing both the value and the derivative are needed. Similarly, if an optimizer only needs the function value, it could call Function(x) and MyFun would know it doesn't need to compute the derivative (thus saving some cycles).

For a black-box constraint-based optimization, it might look something like

func (m *MyFun) Eval(x []float64) (f float64, g []float64, c []float64)

though constraints get tricky fast, so the actual demand on the user might be more (linear constraints, box constraints, etc.) 

The important point is to have Eval() represent everything (which is often what is needed) but to keep in mind the idea of also having Function() Gradient() etc. to allow for more fine-grained control when appropriate.