Structure templates for symbolic regression

[dpiringe]

Implementing a new problem type with a structure template parameter for symbolic regression. The following components are necessary:

• MultiEncoding
• Views
• Parser for structure: to parse an infix expression
• Evaluator: based on IABoundEstimator
• Interpreter: builds a full expression, based on structure template parameter and (multiple) evolved sub-expressions

[dpiringe]

r18054

• branched trunk

[dpiringe]

r18061

• added a new type of problem called StructuredSymbolicRegressionSingleObjectiveProblem, represents a first construct for future implementations

[dpiringe]

r18062

• added a new Symbol SubFunctionSymbol for sub functions
• modified InfixExpressionParser to support SubFunctionSymbol (parsing of variableNames still in work)
• modified StructuredSymbolicRegressionSingleObjectiveProblem to extract sub functions and add them to MultiEncoding

[dpiringe]

r18063

• added view components and classes for sub functions

[dpiringe]

r18065

• modified InfixExpressionParser to fully support SubFunctionSymbol
  • created a SubFunctionTreeNode to store the function arguments
• modified StructureTemplateView to regenerate the content state
• first implementation for the main tree build up logic

[dpiringe]

r18066

• added a simple way of evaluation (using r^{2 evaluator)}
• added a simple analyzing logic for "Best Tree"
• added a connection to SubFunction in SubFunctionTreeNode

[dpiringe]

r18067

• changed the StructureTemplateView -> nodes of type SubFunctionTreeNode are now clickable
  • still need to overhaul the UI elements
• added a way to parse SubFunctionTreeNode with a unique name in InfixExpressionParser

[dpiringe]

r18068

• modified the StructureTemplateView to enable colorful tree nodes of type SubFunctionTreeNode
• refactored SubFunctionTreeNode, SubFunction and StructureTemplate

[dpiringe]

r18069

• added linear scaling support for structure template parameter

[dpiringe]

r18071

• added linear scaling logic in Evaluate and (for UI reasons) Analyze
• added logic forSubFunctionSymbol (modified OpCodes) -> the SubFunctionTreeNode is display in the tree but has no effect on evaluation (works like a flag)
  • works now with SymbolicDataAnalysisExpressionTreeInterpreter
• default grammar for SubFunction is now ArithmeticExpressionGrammar instead of LinearScalingGrammar

[chaider]

r18072

• Added info text in StructureTemplateView
• Fixed cloning constructors
• Added check if linear scaling nodes are set

[dpiringe]

r18073

• fixed a bug: parsing an expression now resets the viewHost content, this prevents to view old content of non-existing sub-functions

[chaider]

r18074

-Fixed cloning of StructureTemplate

[dpiringe]

r18075

• added a hidden interpreter parameter for StructuredSymbolicRegressionSingleObjectiveProblem
• fixed a bug which crashed the application by changing ProblemData with different variables
• fixed a bug which crashed the application by running the problem with an empty StructureTemplate
• added a better output of exceptions of type AggregateException
• added and resize event handler to repaint nodes of type SubFunctionTreeNode
• code cleanup

[dpiringe]

r18076

• added new parameters
• added the builded tree into the scope, this allows operators to use the final tree
• added new operators

[dpiringe]

r18081

• changed the visibility of the following parameters: EstimationLimitsParameter, EvaluatorParameter and BestTrainingSolutionParameter
• added first steps to set an evaluator as parameter
  • added a new parameter TreeEvaluatorParameter
  • added a temporary logic to static evaluator method Calculate
  • tried to change a lot of necessary parameters to use the method Evaluate, this caused a lot of problems -> reverted all changes

[dpiringe]

r18084

• added a new problem data provider AsadzadehProvider and the correspondig instance Asadzadeh1
  • implements the test setup of paper Symbolic regression based hybrid semiparametric modelling of processes: An example case of a bending process
• used the Asadzadeh1 instance in StructuredSymbolicRegressionSingleObjectiveProblem for default setup
• added the SubFunctionSymbol in DerivativeCalculator and IntervalArithBoundsEstimator

[dpiringe]

r18095

• added a Evaluate method, which uses the static method Calculate and evaluates a ISymbolicExpressionTree without the need of an ExecutionContext
  • implemented this new method in all single objective SymReg evaluators

[dpiringe]

r18099

• set the default template to f(_) when loading a new problem data
• fixed a bug which caused the drawing of uncolored SubFunctionTreeNodes after using the window splitter
• implemented a method to paint nodes of SubFunctionTreeNode as colored nodes for ISymbolicDataAnalysisModel

[dpiringe]

r18101

• recreated problem instance Asdzadeh1 as SheetBendingProcess
• SheetBendingProcess is located in Physics and provided by Physics/PhysicsInstanceProvider

[dpiringe]

r18103

• refactor the evaluation logic of NMSESingleObjectiveConstraintsEvaluator
• refactor the new method Evaluate for PearsonRSquaredAverageSimilarityEvaluator
• change the parameter order of some evaluate/calculate methods

[dpiringe]

r18104

• overrode the method GetActualValue in ValueLookupParameter to get the default value when the execution context is null
• reverted the linear scaling logic for NMSESingleObjectiveConstraintsEvaluator
• in SymbolicRegressionConstantOptimizationEvaluator: removed the usage of GenerateRowsToEvaluate because it uses lookup parameters
• set the value of RelativeNumberOfEvaluatedSamplesParameter for SymbolicRegressionConstantOptimizationEvaluator in StructuredSymbolicRegressionSingleObjectiveProblem if Maximization = true and the SymbolicRegressionConstantOptimizationEvaluator is configured as evaluator
• added the SubFunctionSymbol in TreeToAutoDiffTermConverter

[dpiringe]

r18133

• updated interpeters of type ISymbolicDataAnalysisExpressionTreeInterpreter to support symbols of type SubFunctionSymbol

[dpiringe]

r18134

• added a new information box for StructureTemplate in StructureTemplateView with an extended description about structure templates

[dpiringe]

r18139

• changed the item name of SubFunctionSymbol from SubFunctionSymbol to SubFunction

[mkommend]

r18146: Merged trunk changes into branch.

[mkommend]

r18149: Merged trunk changes into branch.

[mkommend]

r18150: Merged trunk changes into branch.

[dpiringe]

r18151

• fixed eventhandler reregister after deserialisazion/cloning
• added a test case for StructuredSymbolicRegressionSingleObjectiveProblem
• changed the usage of a Dictionary to List

[dpiringe]

r18152

• removed the calculation of EstimationLimits and set the interval [-inf, inf] as default
  • this parameter was never adjusted after problem construction -> caused bugs with the change of problem data
• created two new method to setup/create the MultiEncoding and SymbolicExpressionTreeEncoding
• configured the default template f(_) for a structure template

[dpiringe]

r18154

• overwrote the method SetEnabledStateOfControls for StructureTemplateView
• fixed the wrong usage of infoLabel in StructureTemplateView -> added a new label errorLabel for textual output
• deleted the resource file for StructureTemplateView

[dpiringe]

r18155

• merged trunk into branch

[dpiringe]

r18156

• adapted the unit test RunStructureTemplateRegressionSampleTest to match the results
• added the sample to the optimizer start page

[dpiringe]

r18157

• adapted formatters to support SubFunctionSymbol

[gkronber]

r18158: fixed "essential" unit tests

[gkronber]

@dpiringe, could you please also add support for "Number" to the native interpreter? I do not have the necessary dev environment installed.

[gkronber]

Please use BatchInterpreter instead of TreeInterpreter because it is more efficient.

[dpiringe]

r18161

• merged trunk into branch

[dpiringe]

Replying to gkronber:

@dpiringe, could you please also add support for "Number" to the native interpreter? I do not have the necessary dev environment installed.

implemented it in ticket #3140 and merged it back into this branch as well as trunk

[dpiringe]

Replying to gkronber:

Please use BatchInterpreter instead of TreeInterpreter because it is more efficient.

r18162: changed the parameter Interpreter in StructuredSymbolicRegressionSingleObjectiveProblem to use SymbolicDataAnalysisExpressionTreeBatchInterpreter as default interpreter

[gkronber]

Bugs / suggestion for improvments:

• values for num are not optimized / changed (tested with paramopt and batchInterpreter) -> #3140
• num values cannot be initialized to negative values (<num=-1.5>). Only via workaround: -<num=1.5>. -> #3140
• Configuration for sub-functions (grammar, size limits) should be not be lost when reparsing (especially when only a minor detail in the structure expression is changed).
• power-symbol: maybe it would be better to throw in the interpreter only when problematic arguments are actually detected (negative base with real-valued power). This would simplify entry of structure-templates. (we should create a new ticket for this.)

[dpiringe]

r18164

• fixed a bug in StructureTemplateView -> only nodes of type SubFunctionTreeNode are selectable
• added a way to keep old sub functions after parsing a new expression
  • overwrote some basic object methods for SubFunction to keep it simple
  • only old sub functions, which match the name and signature of the new ones, are saved; examples:
    • old: f(x), new: f(x) -> keep old
    • old: f(x1), new: f(x1, x2) -> use new
    • old: f1(x), new f2(x) -> use new

[dpiringe]

Replying to gkronber:

Bugs / suggestion for improvments:

• values for num are not optimized / changed (tested with paramopt and batchInterpreter) -> #3140
• num values cannot be initialized to negative values (<num=-1.5>). Only via workaround: -<num=1.5>. -> #3140
• Configuration for sub-functions (grammar, size limits) should be not be lost when reparsing (especially when only a minor detail in the structure expression is changed).
• power-symbol: maybe it would be better to throw in the interpreter only when problematic arguments are actually detected (negative base with real-valued power). This would simplify entry of structure-templates. (we should create a new ticket for this.)

added a way to keep old sub functions, see r18164

[gkronber]

r18176: merged r18165:18174 from trunk to branch (resolving conflicts in the parser)

[gkronber]

r18177: removed a special case from the Evaluate method because it can never be true. Maximization is fixed to false in this problem and therefore the ParamOptEvaluator is not available as an evaluator.

[gkronber]

r18178: copied code with minor modifications from ParameterOptimizationEvaluator into the NMSEConstraintsEvaluator because the code in ParameterOptimizationEvaluator uses R² internally and is incompatible to the NMSEEvaluator.

[gkronber]

r18179: improved parameter optimization for NMSEConstraintsEvaluator. Use LM directly instead of lsfit to improve efficiency by using vectorized callbacks.

[gkronber]

Open issue: parameters are not written back to the trees stored in the individuals after optimization. The reason is that trees from the individual are cloned and combined with the (cloned) template to construct the full tree. We should think about a way to update optimized parameters in the trees (including parameters which occur in the template).

    private ISymbolicExpressionTree BuildTree(Individual individual) {
      if (StructureTemplate.Tree == null)
        throw new ArgumentException("No structure template defined!");

      var clonedTemplate = (ISymbolicExpressionTree)StructureTemplate.Tree.Clone();

      // build main tree
      foreach (var subFunctionTreeNode in clonedTemplate.IterateNodesPrefix().OfType<SubFunctionTreeNode>()) {
        var subFunctionTree = individual.SymbolicExpressionTree(subFunctionTreeNode.Name);

        // add new tree
        var subTree = subFunctionTree.Root.GetSubtree(0)  // Start
                                          .GetSubtree(0); // Offset
        subTree = (ISymbolicExpressionTreeNode)subTree.Clone();
        subFunctionTreeNode.AddSubtree(subTree);

      }
      return clonedTemplate;
    }

[dpiringe]

r18182

• fixed missing/wrong event registration for SubFunction and StructuredSymbolicRegressionSingleObjectiveProblem

[mkommend]

r18183: Fixed bug in parameter optimization code of NMSE evaluator (tree has never been updated).

[mkommend]

r18184: Refactored structured GP problem.

[mkommend]

r18185: Removed unused view SubFunctionListView.

[mkommend]

r18187: Refactored saved trees in structure template.

[mkommend]

r18188: Fixed backwards compatibility of StructureTemplate

[mkommend]

r18189: Fixed name of MultiEncodingCreator.

[mkommend]

r18190:

• Added parameters for parameter optimization / linear scaling in StructeredSymRegProblem.
• Added license headers to StructureTemplate and StructeredSymRegProblem.
• Fixed type in NMSEConstraint evaluator.

[mkommend]

r18191: Extracted linear scaling functionality in a dedicated helper class.

[mkommend]

r18192:

• Extracted parameter optimization into dedicated helper utility.
• Implemented evaluation in the structured SymReg problem directly.

[mkommend]

r18194:

• Added handling of numeric parameters in structur GP problem by using a real vector encoding.
• Configured grammar in sub function.
• Added property for numeric parameters in structure template.

[mkommend]

r18195: Refactored creation of subfunctions in StructureTemplate.

[mkommend]

r18196: Fixed bug in adjustment of linear scaling terms.

[mkommend]

r18197: Omitted parameter optimization of variable weights in the template part of the tree.

[gkronber]

Review comments:

• RealVector cross-over raise exception when the template contains only one numeric parameters
• Entering an expression which uses an non-existant input variables (e.g. "f(xyz)") shows error when parse is pressed the first time, but succeeds if it is pressed again without change to the structure.

[mkommend]

r18198: Fixed error in structure GP if only one numeric parameter is present in the template by providing a new copy crossover for real vectors.

[mkommend]

Replying to gkronber:

Review comments:

• RealVector cross-over raise exception when the template contains only one numeric parameters

addressed in r18198

[mkommend]

r18199: Fixed parsing of variables in subfunctions.

[mkommend]

Replying to gkronber:

• Entering an expression which uses an non-existant input variables (e.g. "f(xyz)") shows error when parse is pressed the first time, but succeeds if it is pressed again without change to the structure.

addressed in r18199

The presence of variables cannot be checked during parsing of the template. Thus, this functionality has been removed and if a non existing variable is used in the template a runtime error is raised.

[gkronber]

The ItemName of the problem is ... Single Objective Problem (single-ojective). --> simplify

[mkommend]

r18200: Improved item name and description of structured symreg problem.

[gkronber]

Todo gkronber: review and merge back to trunk. Todo David: rename class, change default grammar (and configuration), fix unit test.

Topics for future development:

• Performance tuning (evaluate).
• Instead of multi-encoding use a specific new encoding.
• Improve GUI: don't show sub-functions right side of the tree but in the problem instead.
• Shape-constraints for sub-functions.
• Partial dependence plots / visualization / impact-calculation for sub-functions
• Use (restricted) type-coherent grammar instead of arithmetic grammar as a default for sub-functions
• Configuration of number of sub-trees for grammar symbols (currently 1 - 3 arguments).

Not directly related:

• Exclusion of nodes in parameter optimization should be improved, remove code duplication for parameter optimization.
• Remove code duplication for linear scaling.

[dpiringe]

r18205

• changed visibility of string constants in TypeCoherentExpressionGrammar from private to public
• changed default grammar for SubFunction

[dpiringe]

r18206

• renamed StructuredSymbolicRegressionSingleObjectiveProblem to StructureTemplateSymbolicRegressionProblem

[dpiringe]

r18207

• updated test cases for StructureTemplateSymbolicRegressionProblem
• updated optimizer template for StructureTemplateSymbolicRegressionProblem
• updated project file for HeuristicLab.Problems.DataAnalysis.Symbolic.Regression (forgot to include last commit)

[gkronber]

r18216: merged r18203:18211 from trunk to branch. Merged changes, fixed compile problem ('is not')

[gkronber]

r18220: reintegrated structure-template GP branch into trunk

[gkronber]

r18221: deleted branch which was reintegrated into trunk

[dpiringe]

r18224

• set an empty enumerable for arguments to prevent a nullable enumerable

[gkronber]

Closed on github.