srtree: A supporting library for tree-based symbolic regression

srtree is a Haskell library that implements a tree-based structure for expressions and supporting functions to be used in the context of symbolic regression.

The expression structure is defined as a fixed-point of a mix of unary and binary tree. This makes it easier to implement supporting functions that requires the traversal of the trees. Also, since it is a parameterized structure, we can creating partial trees to pattern math structures of interest. This structure may contain four types of nodes:

• Bin Op l r that represents a binary operator Op with two children.
• Uni Function t that represents an unary function Function with a single child.
• Var Int representing the index of a variable (i.e., x0, x1, etc.).
• Param Int representing the index of a adjustable parameter (i.e., theta0, theta1, etc.).
• Const Double representing a constant value.

The SRTree structure has instances for Num, Fractional, Floating, IsString which allows to create an expression as a valid Haskell expression such as (remember to turn on OverloadedStrings extension):

expr = "x0" * 2 + sin("x1" * pi + "x0") :: Fix SRTree

This library comes with support to many quality of life functions to handle this data structure. Such as:

• getting the arity of a node
• getting the children of a node as a list
• count the number of nodes
• number of nodes of a specific type
• counting unique tokens
• number of variables and parameters
• relabeling the parameters from 0 to p
• converting floating point constants to parameters

Additionally, the library provides supporting function to work with datasets, evaluating the expressions, calculating the derivatives, printing, generating random trees, simplifying the expression, calculating overall statistics, optimizing parameters, and model selection metrics.

Together with this library, we provide example applications (please refer to their corresponding README files):

• srsimplify: a parser and simplification tool supporting the output of many popular SR algorithms.
• srtools: a tool that can be used to evaluate symbolic regression expressions and create nice reports with confidence intervals.
• tinygp: a simple GP implementation based on tinyGP.

Organization

The library is organized as Data, Algorithm, and Text modules where the Data modules implement functions directly tied to the data structure and the Algorithm modules implement algorithms related to symbolic regression, finally, the Text modules parse string expressions from different formats and apply simplification, when requested.

Data modules

The Data modules is split into \(5\) submodules:

• Data.SRTree contains the data strucuture and basic supporting functions.
• Data.SRTree.Datasets contains functions supporting loading datasets into Massiv.Arrays (aka numpy arrays).
• Data.SRTree.Derivative contains the symbolic derivatives of the functions and operators.
• Data.SRTree.Eval contains functions to evaluate the tree given a dataset and parameters.
• Data.SRTree.Print contains supporting functions for converting trees to different string representation.
• Data.SRTree.Random contains functions to generate random trees.

Data.SRTree

The SRTree val data structure is a sum type structure that can be either a variable index, a parameter index, a constant value (of type Double), an univariate function or a binary operator. The data type is implemented as a fixed point so all the algorithms act on Fix SRTree:

t = "x0" + "t0" * sin("x1" + "t1"**2) :: Fix SRTree 

When creating the expression in a more natural notation, the variables and parameters are String composed of the first letter either x, for variables, or t for parameters (as in theta), and an integer corresponding to the index of the variable or parameter. The fixed point notation, allows us to implment recursive processing of a tree without many of the common boilerplate:

countNodes = 
  \case 
    Var _     = 1
    Const _   = 1
    Param _   = 1
    Uni _ t   = 1 + t 
    Bin _ l r = 1 + l + r

The children are parameterized by the val type parameter. This allows us to create convenient partial structures, such as:

-- + operator pointing to some structure
-- with index 1 and 2
Bin Add 1 2 

-- canonical representation of + operator 
Bin Add () ()

The main functions of this module are:

• arity: returns the arity of an operator.
• getChildren: returns the children of a Fix SRTree as a list
• countNodes: returns the number of nodes
• countOccurrences: counts the occurence of a given variable
• countVars: returns the number of unique variables appearing the expression
• relabelParams: relabels the parameters from the left leaves to the right
• constsToParams: replace Const nodes with Param nodes.

Data.SRTree.Datasets module

This module exports only the loadDataset function which takes a filename and returns the training and test sets together with the column labels. The filename must follow the format:

filename.ext:start_row:end_row:target:features

where each ':' field is optional. The fields are:

• start_row:end_row is the range of the training rows (default 0:nrows-1). every other row not included in this range will be used as validation
• target is either the name of the PVector (if the datafile has headers) or the index of the target variable
• features is a comma separated list of SRMatrix names or indices to be used as input variables of the regression model.

Example of valid names: dataset.csv, mydata.tsv, dataset.csv:20:100, dataset.tsv:20:100:price:m2,rooms,neighborhood, dataset.csv:::5:0,1,2.

Data.SRTree.Derivative module

Calculates symbolic derivatives of the expression w.r.t. the variables or the parameters. The main functions of this module are:

• deriveBy: returns the symbolic derivative w.r.t. a certain variable or a certain parameter.
• deriveByVar: shortcut to deriveBy to derive by a variable.
• deriveByParam: shortcut to deriveBy to derive by a parameter.

Data.SRTree.Eval module

Evaluates an expression given a dataset. The main functions of this module are:

• evalTree: given a data matrix and a vector of parameters, evaluates the expression tree.
• evalInverse: evaluates the inverse of a function.
• invright: evaluates the right inverse of an operator.
• invleft: evaluates the left inverse of an operator.

Data.SRTree.Print module

Support functions to convert an expression tree into a String. The main functions of this module are:

• showExpr and printExpr: converts/print the expression into math notation .
• showPython and printPython: converts/print to a numpy notation.
• showLatex and printLatex: converts/print to a LaTeX notation.
• showTikz and printTikz: converts/print to a TikZ notation.

Data.SRTree.Random module

Auxiliary functions to create random trees. The main functions of this module are:

• randomTree: creates a random tree with a certain number of nodes.
• randomTreeBalanced: creates a (almost) balanced random tree with a certain number of nodes.

Text modules

The Text module is split into \(2\) modules:

• Text.ParseSR: contains the main parsers for different SR algorithms output.
• Text.ParseSR.IO: auxiliary functions to handle files containing many expressions.

Text.ParseSR module

The only important function of this module is parseSR that parses an string expression from a given algorithm to a certain output. It also converts variable names to x0, x1,...

Text.ParseSR.IO module

The two main functions of this module are:

• withInput: that reads the stdin or a text file and parse all expressions
• withOutput: that writes the parsed expression into stdout or a file with one of the choices of output format.

These functions handle any errors with an Either type and they can be safely pipelined together. Any invalid expression will be printed as "invalid expression ".

Algorithm modules

The Algorithm modules are split into \(5\) submodules:

• Algorithm.SRTree.AD contains automatic differentiation functions.
• Algorithm.SRTree.ConfidenceIntervals contains functions to calculate the confidence intervals of parameters and predictions of a symbolic expression using Laplace approximation or profile likelihood.
• Algorithm.SRTree.Likelihood contains functions support different likelihood functions and their derivatives (gradient and hessian).
• Algorithm.SRTree.ModelSelection implements different model selection criteria such as AIC, BIC, MDL.
• Algorithm.SRTree.Opt implements functions to optimize the parameters of an expression supporting different likelihood functions.

Algorithm.SRTree.AD module

The main functions of this module are:

• forwardMode: returns the prediction errors vector multiplied by the Jacobian matrix using forward mode AD.
• forwardModeUnique: same as above, but assuming each parameter index appear only once in the tree.
• reverseModeUnique: same as above, but using reverse mode
• forwardModeUniqueJac: same as forwardModeUnique but returns the Jacobian (does not mutiply by the error).

Algorithm.SRTree.Likelihood module

The main functions of this module are:

• sse, mse, rmse: calculates the sum-of-square, mean squared, root of mean squared errors.
• nll: returns the negative log-likelihood given a distribution and the associated error (Nothing if unknown)
• gradNLL: returns the gradient of the negative log-likelihood.
• gradNLLNonUnique: same as above but assumes non-unique parameters
• hessianNLL: returns the hessian of the neg log-likelihood.

Algorithm.SRTree.Opt module

The main functions of this module are:

• minimizeNLL: minimizes the negative log-likelihood of a distribution.
• minimizeNLLNonUnique: same as above but assumes repeated occurrences of parameters.
• minimizeNLLWithFixedParam: minimizes the neg log-likelihood but fixing the value of a single parameter.
• minimizeGaussian, minimizePoisson, minimizeBinomial: shortcut to minimize these three distributions.

Algorithm.SRTree.ModelSelection module

The main functions of this module are:

• bic: Bayesian Information Criteria
• aic: Akaike Information Criteria
• mdl: Minimum Description Length as described in Bartlett, Deaglan J., Harry Desmond, and Pedro G. Ferreira. "Exhaustive symbolic regression." IEEE Transactions on Evolutionary Computation (2023)
• mdlLattice: as described in Bartlett, Deaglan, Harry Desmond, and Pedro Ferreira. "Priors for symbolic regression." Proceedings of the Companion Conference on Genetic and Evolutionary Computation. 2023.
• mdlFreq : MDL weighted by the frequency of occurrence of functions

Algorithm.SRTree.ConfidenceIntervals module

The main functions of this module are:

• paramCI: calculates the parameters confidence intervals.
• predictionCI: calculates the predictions confidence intervals

EqSat modules

The EqSat modules are split into \(4\) submodules:

• Algorithm.EqSat.Simplify contains function supporting algebraic simplification with equality saturation.
• Algorithm.EqSat contains the main equality saturation function.
• Algorithm.EqSat.EGraph contains the e-graph data structure and supporting functions.
• Algorithm.EqSat.EqSatDB contains supporting functions to pattern matching and insert equivalent expressions into an e-graph.

Algorithm.EqSat module

The main functions of this module are:

• eqSat : runs equality saturation over a single expression.
• getBest : returns the best expression given the cost function used to generate the e-graph
• recalculateBest : recalculates the cost of each e-class using a new cost function
• runEqSat : runs equality saturation inside EGraphST monad. Use this if you want to return the e-graph.

Algorithm.EqSat.EGraph module

The main functions of this module are:

• fromTree : creates an e-graph from an expression tree.
• fromTrees : creates an e-graph from multiple expressions
• fromTreeWith : inserts a new expression into the e-graph
• findRootClasses : returns the roots of the e-graph, if any .
• getExpressionFrom : returns a single expression from a given e-class always picking the first e-node as the path
• getAllExpressionsFrom : returns all expressions from the given e-class
• getRndExpressionFrom : returns a random expression from this e-class

Algorithm.EqSat.EqSatDB module

The main functions of this module are:

• TODO: create auxiliary functions to apply substution rules inside an EGraphST monad .

Algorithm.EqSat.Simplify module

The main functions of this module are:

• simplifyEqSatDefault : simplifies an expression using the default parameters
• simplifyEqSat : simplifies with custom parameters

TODO:

• support more advanced functions
• support conditional branching (IF-THEN-ELSE)