search

SymbolicML / DynamicExpressions.jl

Ridiculously fast symbolic expressions
https://ai.damtp.cam.ac.uk/dynamicexpressions
Apache License 2.0
106 stars 15 forks source link

Algebra for `AbstractExpression` objects; and `StructuredExpression` #92

Closed MilesCranmer closed 3 months ago

MilesCranmer commented 4 months ago

Algebra for AbstractExpression objects

This lets you create new expressions with regular mathematical operators. Unlike the equivalent interface for Node <: AbstractExpressionNode, this does not rely on the admittedly hacky global LATEST_OPERATORS, but on the actual internal operators stored in the expression. Thus, this is much more robust.

For example, say we create two expressions, f and g, via parse_expression:

julia> using DynamicExpressions

julia> kws = (;
           binary_operators=[+, -, *, /],
           unary_operators=[-, cos, exp],  # Use - as a unary operator too
           variable_names=["x", "y"],
       )
(binary_operators = Function[+, -, *, /], unary_operators = Function[-, cos, exp], variable_names = ["x", "y"])

julia> f = parse_expression(:(x * x - cos(2.5f0 * y + -0.5f0)); kws...)
(x * x) - cos((2.5 * y) + -0.5)

julia> g = parse_expression(:(exp(-(y * y))); kws...)
exp(-(y * y))

we can compose these using any of the declared operators, into a new expression type:

julia> f + g
((x * x) - cos((2.5 * y) + -0.5)) + exp(-(y * y))

julia> (f + g)(randn(2, 100));  # Evaluate as normal (without needing to pass operators)

julia> f + g |> typeof
Expression{Float32, Node{Float32}, @NamedTuple{operators::OperatorEnum{Tuple{typeof(+), typeof(-), typeof(*), typeof(/)}, Tuple{typeof(-), typeof(cos), typeof(exp)}}, variable_names::Vector{String}}}

Note that this requires the type of the expression to be identical for this to work. So, for example, since OperatorEnum types the functions, each expression much have a priori declared the right operators!

This also means you can't use operators outside the enum:

julia> f \ g
ERROR: ArgumentError: Operator \ not found in operators for expression type Expression{Float32, Node{Float32}, @NamedTuple{operators::OperatorEnum{Tuple{typeof(+), typeof(-), typeof(*), typeof(/)}, Tuple{typeof(-), typeof(cos), typeof(exp)}}, variable_names::Vector{String}}} with binary operators (+, -, *, /)
Stacktrace:
...

StructuredExpression

This also introduces a StructuredExpression, which builds on the above point. It lets you declare an expression with fixed expression structure. You could also think of this as lazily building the expression based on a static expression.

The nice part about this is it works directly on other AbstractExpression, putting them into a NamedTuple, and then puts them together when calling get_tree. For example, using the previous example:

using DynamicExpressions
kws = (;
    binary_operators=[+, -, *, /],
    unary_operators=[-, cos, exp],
    variable_names=["x", "y"],
)
f = parse_expression(:(x * x - cos(2.5f0 * y + -0.5f0)); kws...)
g = parse_expression(:(exp(-(y * y))); kws...)
# ^ Regular `Expression` type

We can create f_plus_g which a fixed + operation in the middle. This function is fixed into the expression type itself, so this should be very fast:

julia> f_plus_g = StructuredExpression((; f, g), trees -> trees.f + trees.g)
((x * x) - cos((2.5 * y) + -0.5)) + exp(-(y * y))

Note the string printout – this is because get_tree calls the structure function, patching together the tree! But the overall structure is fixed.

We can look at the individual components:

julia> get_contents(f_plus_g) |> keys
(:f, :g)

julia> get_contents(f_plus_g).f
(x * x) - cos((2.5 * y) + -0.5)

julia> get_contents(f_plus_g).g
exp(-(y * y))

and get the function that puts them together:

julia> get_metadata(f_plus_g).structure
#3 (generic function with 1 method)

which takes a named tuple as input.

This is all type stable, and should be a nice feature for SymbolicRegression.jl!

It also already has get_constants and set_constants! declared – these simply loop through the individual sub-expressions and get or set constants.

cc @gca30 @AlCap23 @avik-pal in case of interest

github-actions[bot] commented 4 months ago

Benchmark Results

master 845e66a0a07696... master/845e66a0a07696...
eval/ComplexF32/evaluation 7.47 ± 0.49 ms 7.45 ± 0.49 ms 1
eval/ComplexF64/evaluation 9.63 ± 0.74 ms 9.6 ± 0.66 ms 1
eval/Float32/derivative 10.7 ± 1.6 ms 10.8 ± 1.7 ms 0.991
eval/Float32/derivative_turbo 10.7 ± 1.6 ms 10.9 ± 1.7 ms 0.985
eval/Float32/evaluation 2.75 ± 0.23 ms 2.78 ± 0.22 ms 0.988
eval/Float32/evaluation_bumper 0.586 ± 0.014 ms 0.533 ± 0.013 ms 1.1
eval/Float32/evaluation_turbo 0.693 ± 0.029 ms 0.702 ± 0.027 ms 0.988
eval/Float32/evaluation_turbo_bumper 0.584 ± 0.014 ms 0.53 ± 0.013 ms 1.1
eval/Float64/derivative 13.9 ± 0.56 ms 14.1 ± 0.67 ms 0.986
eval/Float64/derivative_turbo 13.9 ± 0.49 ms 14.1 ± 0.55 ms 0.985
eval/Float64/evaluation 2.89 ± 0.23 ms 2.93 ± 0.24 ms 0.987
eval/Float64/evaluation_bumper 1.28 ± 0.045 ms 1.19 ± 0.045 ms 1.08
eval/Float64/evaluation_turbo 1.18 ± 0.063 ms 1.19 ± 0.061 ms 0.993
eval/Float64/evaluation_turbo_bumper 1.28 ± 0.042 ms 1.19 ± 0.042 ms 1.08
utils/combine_operators/break_sharing 0.039 ± 0.00055 ms 0.0397 ± 0.00067 ms 0.985
utils/convert/break_sharing 23.1 ± 1 μs 22.9 ± 1 μs 1.01
utils/convert/preserve_sharing 0.125 ± 0.0031 ms 0.124 ± 0.003 ms 1
utils/copy/break_sharing 23.3 ± 1 μs 23.6 ± 1.1 μs 0.988
utils/copy/preserve_sharing 0.124 ± 0.0031 ms 0.125 ± 0.0028 ms 0.992
utils/count_constant_nodes/break_sharing 8.53 ± 0.14 μs 9.1 ± 0.15 μs 0.937
utils/count_constant_nodes/preserve_sharing 0.109 ± 0.0027 ms 0.111 ± 0.003 ms 0.981
utils/count_depth/break_sharing 10.4 ± 0.12 μs 10.1 ± 0.13 μs 1.04
utils/count_nodes/break_sharing 8.5 ± 0.12 μs 9.15 ± 0.15 μs 0.928
utils/count_nodes/preserve_sharing 0.111 ± 0.0029 ms 0.113 ± 0.0033 ms 0.985
utils/get_set_constants!/break_sharing 0.0332 ± 0.00089 ms 0.0338 ± 0.0011 ms 0.984
utils/get_set_constants!/preserve_sharing 0.223 ± 0.004 ms 0.224 ± 0.0057 ms 0.997
utils/get_set_constants_parametric 0.0478 ± 0.0016 ms 0.0482 ± 0.0019 ms 0.991
utils/has_constants/break_sharing 4.4 ± 0.055 μs 4.02 ± 0.062 μs 1.09
utils/has_operators/break_sharing 2.1 ± 0.032 μs 1.77 ± 0.018 μs 1.18
utils/hash/break_sharing 25.8 ± 0.44 μs 26.2 ± 0.38 μs 0.986
utils/hash/preserve_sharing 0.13 ± 0.0024 ms 0.131 ± 0.0025 ms 0.993
utils/index_constant_nodes/break_sharing 22.9 ± 0.72 μs 22.1 ± 0.9 μs 1.03
utils/index_constant_nodes/preserve_sharing 0.124 ± 0.0028 ms 0.128 ± 0.003 ms 0.966
utils/is_constant/break_sharing 3.56 ± 0.056 μs 4.04 ± 0.054 μs 0.881
utils/simplify_tree/break_sharing 0.176 ± 0.0015 ms 0.167 ± 0.0015 ms 1.05
utils/simplify_tree/preserve_sharing 0.31 ± 0.0045 ms 0.297 ± 0.0058 ms 1.04
utils/string_tree/break_sharing 0.396 ± 0.019 ms 0.394 ± 0.014 ms 1
utils/string_tree/preserve_sharing 0.527 ± 0.025 ms 0.521 ± 0.015 ms 1.01
time_to_load 0.219 ± 0.0039 s 0.24 ± 0.003 s 0.913
coveralls commented 4 months ago

Pull Request Test Coverage Report for Build 9765817803

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionMath.jl 30 32 93.75%
<!-- Total: 68 70 97.14% -->
Totals Coverage Status
Change from base Build 9738548135: 0.05%
Covered Lines: 2261
Relevant Lines: 2366
💛 - Coveralls
coveralls commented 4 months ago

Pull Request Test Coverage Report for Build 9766444055

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionAlgebra.jl 40 45 88.89%
<!-- Total: 78 83 93.98% -->
Totals Coverage Status
Change from base Build 9738548135: -0.05%
Covered Lines: 2271
Relevant Lines: 2379
💛 - Coveralls
github-actions[bot] commented 4 months ago

Pull Request Test Coverage Report for Build 9767219373

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionAlgebra.jl 40 45 88.89%
<!-- Total: 78 83 93.98% -->
Totals Coverage Status
Change from base Build 9767201130: -0.05%
Covered Lines: 2271
Relevant Lines: 2379
💛 - Coveralls
github-actions[bot] commented 4 months ago

Pull Request Test Coverage Report for Build 9767219373

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionAlgebra.jl 40 45 88.89%
<!-- Total: 78 83 93.98% -->
Totals Coverage Status
Change from base Build 9767201130: -0.05%
Covered Lines: 2271
Relevant Lines: 2379
💛 - Coveralls
github-actions[bot] commented 4 months ago

Pull Request Test Coverage Report for Build 9767219373

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionAlgebra.jl 40 45 88.89%
<!-- Total: 78 83 93.98% -->
Totals Coverage Status
Change from base Build 9767201130: -0.05%
Covered Lines: 2271
Relevant Lines: 2379
💛 - Coveralls
github-actions[bot] commented 4 months ago

Pull Request Test Coverage Report for Build 9799648670

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionAlgebra.jl 46 52 88.46%
<!-- Total: 84 90 93.33% -->
Totals Coverage Status
Change from base Build 9793838744: -0.08%
Covered Lines: 2278
Relevant Lines: 2387
💛 - Coveralls
coveralls commented 4 months ago

Pull Request Test Coverage Report for Build 9799648670

Details

Changes Missing Coverage Covered Lines Changed/Added Lines %
src/ExpressionAlgebra.jl 46 52 88.46%
<!-- Total: 84 90 93.33% -->
Totals Coverage Status
Change from base Build 9793838744: -0.08%
Covered Lines: 2278
Relevant Lines: 2387
💛 - Coveralls
coveralls commented 3 months ago

Pull Request Test Coverage Report for Build 10126841842

Details

Totals Coverage Status
Change from base Build 9829024598: 0.5%
Covered Lines: 2410
Relevant Lines: 2513
💛 - Coveralls