Expose recorder function for DynamicAutodiff.jl

[MilesCranmer]

This makes it so you can put derivative operators in the template structure when doing structured searches. This works with a derivative operator D that computes the derivative with respect to the i-th argument, and can be nested arbitrarily to get higher-order derivatives. However, note that nesting it multiple times could be take a while to compile though, since it will compile n^d operators for d-th order derivatives. (Runtime performance should be unaffected)

Here's an example:

using SymbolicRegression
using SymbolicRegression: D

structure = TemplateStructure{(:f, :g)}(
    ((; f, g), (x, y)) -> f(x, y) - D(f, 1)(x, y) + g(y)
)

This imposes a structure that for some symbolic $f$ and $g$, the evaluation would use $$f(x, y) - \frac{\partial f(x, y)}{\partial x} + g(y)$$.

Also helps support feature request from @gm89uk + @DeaglanBartlett. Interested to hear whether you run into any issues for it before I merge it!

[github-actions]

Benchmark Results

	master	e05da70...	master/e05da7070973f1...
search/multithreading	20.8 ± 1.4 s	20.8 ± 3.8 s	0.999
search/serial	33.7 ± 0.21 s	33.9 ± 1.7 s	0.993
utils/best_of_sample	1.89 ± 1.6 μs	1.64 ± 1.4 μs	1.15
utils/check_constraints_x10	11.1 ± 2.8 μs	11.3 ± 2.9 μs	0.983
utils/compute_complexity_x10/Float64	2.06 ± 0.11 μs	2.08 ± 0.11 μs	0.99
utils/compute_complexity_x10/Int64	2.01 ± 0.11 μs	2.01 ± 0.1 μs	1
utils/compute_complexity_x10/nothing	1.46 ± 0.13 μs	1.48 ± 0.12 μs	0.987
utils/insert_random_op_x10	5.83 ± 1.8 μs	5.82 ± 1.9 μs	1
utils/next_generation_x100	0.445 ± 0.12 ms	0.35 ± 0.12 ms	1.27
utils/optimize_constants_x10	0.0379 ± 0.0081 s	0.0363 ± 0.0084 s	1.04
utils/randomly_rotate_tree_x10	5.34 ± 0.61 μs	5.22 ± 0.58 μs	1.02
time_to_load	1.87 ± 0.022 s	1.92 ± 0.011 s	0.973

Benchmark Plots

A plot of the benchmark results have been uploaded as an artifact to the workflow run for this PR.
Go to "Actions"->"Benchmark a pull request"->[the most recent run]->"Artifacts" (at the bottom).

[coveralls]

Pull Request Test Coverage Report for Build 12223650046

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

• For more information on this, see Tracking coverage changes with pull request builds.
• To avoid this issue with future PRs, see these Recommended CI Configurations.
• For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

• 4 of 4 (100.0%) changed or added relevant lines in 1 file are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage increased (+0.004%) to 95.222%

---

Totals
Change from base Build 12219394529:	0.004%
Covered Lines:	3129
Relevant Lines:	3286

---

💛 - Coveralls

[MilesCranmer]

Turns out Zygote.jl is awful at second-order differentiation, even for tiny operators like cos. So I will switch things to ForwardDiff.jl

[Moelf]

is there any reason to use Enzyme or Mooncake for this?

[MilesCranmer]

It is probably overkill as all I'm doing is:

1. Generating a derivative operator for each current operator
2. Creating a new operator enum with those derivative operators (compiler inferrable)
3. Applying the chain rule and "shifting" the operator indices in the tree when we need to call the derivatives
4. Running regular eval_tree_array with that new operator enum

^This is nice because we can stack it as many times as we want to get higher-order derivatives (though many packages struggle with complex higher order differentiation).

So all I'm using ForwardDiff for is this:

function (d::OperatorDerivative{F,1,1})(x) where {F}
    return ForwardDiff.derivative(d.op, x)
end
function (d::OperatorDerivative{F,2,1})(x, y) where {F}
    return ForwardDiff.derivative(Fix{2}(d.op, y), x)
end
function (d::OperatorDerivative{F,2,2})(x, y) where {F}
    return ForwardDiff.derivative(Fix{1}(d.op, x), y)
end

I've had a lot of issues in getting Enzyme into SR (https://github.com/EnzymeAD/Enzyme.jl/issues?q=is:issue%20author:MilesCranmer – though have appreciated the support from the authors) so want to avoid making it a direct dependencies until it is more stable. Mooncake I haven't tried yet but the README says it is still under development so probably want to avoid.

On the other hand, ForwardDiff.jl is already an indirect dependency via Optim.jl so I feel pretty safe about using it. What do you think?

[Moelf]

On the other hand, ForwardDiff.jl is already an indirect dependency via Optim.jl so I feel pretty safe about using it. What do you think?

that's totally true, yea

[MilesCranmer]

Update: since the derivatives are general to any DynamicExpressions.jl expression, I'm going to register a separate package DynamicAutodiff.jl, then import that to SymbolicRegression.jl