Changeset 15606


Ignore:
Timestamp:
01/12/18 16:27:39 (20 months ago)
Author:
gkronber
Message:

#2796: comments and typos

Location:
branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/ApproximateDoubleEqualityComparer.cs

    r15414 r15606  
    33
    44namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
     5  // unused?
    56  internal class ApproximateDoubleEqualityComparer : IEqualityComparer<double> {
    67    public bool Equals(double x, double y) {
     
    910      var yl = (ulong)BitConverter.DoubleToInt64Bits(y);
    1011
    11       xl = xl & 0xFFFFFFFFFFFFFFE0;
     12      xl = xl & 0xFFFFFFFFFFFFFFE0; // ignore least significant bits
    1213      yl = yl & 0xFFFFFFFFFFFFFFE0;
    1314
     
    1819      var bits = (ulong)BitConverter.DoubleToInt64Bits(obj);
    1920
    20       bits = bits & 0xFFFFFFFFFFFFFFE0;
     21      bits = bits & 0xFFFFFFFFFFFFFFE0; // ignore least significant bits
    2122
    2223      return (int)bits;
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Automaton.cs

    r15441 r15606  
    2727
    2828namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
    29   // this is the core class for generating expressions.
    30   // it represents a finite state automaton, each state transition can be associated with an action (e.g. to produce code).
    31   // the automaton determines the possible structures for expressions.
     29  // This is the core class for generating expressions.
     30  // It represents a finite state automaton, each state transition can be associated with an action (e.g. to produce code).
     31  // The automaton determines the possible structures for expressions.
    3232  //
    33   // to understand this code it is worthwile to generate a graphical visualization of the automaton (see PrintAutomaton).
    34   // If the code is compiled in debug mode the automaton produces a Graphviz file into the folder of the application
     33  // To understand this code, it is worthwhile to generate a graphical visualization of the automaton (see PrintAutomaton).
     34  // If the code is compiled in debug mode, the automaton produces a Graphviz file into the folder of the application
    3535  // whenever an instance of the automaton is constructed.
    3636  //
     
    139139    }
    140140
    141     // postfix notation
     141    // Produce postfix notation for expression:
    142142    // Expr -> 0 Term { '+' Term } '+' 'exit'
    143143    // Term -> c Fact { '*' Fact } '*'
     
    366366      followStates[StateExprEnd] = new List<int>(); // no follow states
    367367
    368       // order all followstates (the first follow state leads to the final state)
     368      // order all follow states (the first follow state leads to the final state)
    369369      foreach (var list in followStates) {
    370370        if (list != null)
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/ExprHashSymbolic.cs

    r15440 r15606  
    2424using System.Linq;
    2525
     26// code for hashing of expressions based on symbolic analysis of monomials and polynomials.
     27// slow, but easy to implement correctly.
    2628namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
    2729  internal enum UnaryFunctionType { Log, Exp, Inv };
     
    141143
    142144  // calculates a hash-code for expressions.
    143 
    144145  public static class ExprHashSymbolic {
    145146
     
    153154
    154155    static ExprHashSymbolic() {
    155       const string symbols = "abcdefghijklmnopqrstuvwxyz";
     156      const string symbols = "abcdefghijklmnopqrstuvwxyz"; // limited to 26 variables -> TODO
    156157
    157158      varSymbols = new SymbolFactor[MaxVariables];
     
    167168    }
    168169
     170 
     171  // takes an array of code and transforms it into a polynomial for hashing.
     172  // slow!
    169173    private static int Eval(byte[] code, int nParams) {
    170174      // The hash code calculation already preserves commutativity, associativity and distributivity of operations.
     
    181185      // - exp(x1) * exp(x1) is equivalent to exp(x1)
    182186      //
    183       // The following experssions must not hash to the same value.
    184       // - exp(x1) + exp(x1) is different from exp(x1)
    185       // - log(x1) + log(x1) is different from log(x1)
    186       // - 1/x1 + 1/x1 is different from 1/x1
    187       // - TODO list all
    188 
    189       // think about speed later (TODO)
     187      // The following expressions must not hash to the same value.
     188      // - exp(x1) + exp(x1) is different from exp(x1), because c1*exp(c2*x1) + c3*exp(c4*x1) cannot be simplified to c5*exp(c6*x1) for all values of c2 and c4
     189      // - log(x1) + log(x1) is different from log(x1), same as above
     190      // - 1/x1 + 1/x1 is different from 1/x1, same as above 1/(x1 + c1) + 1/(x1 + c2)
     191      // - TODO: list further exceptions
     192   
    190193
    191194      var stack = new Polynomial[MaxStackSize];
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/ExpressionEvaluator.cs

    r15403 r15606  
    2525
    2626namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
    27   // evalutes expressions (on vectors)
     27  // evaluates expressions (on vectors)
    2828  internal class ExpressionEvaluator {
    2929    // manages it's own vector buffers
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionAlgorithm.cs

    r15439 r15606  
    3535namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
    3636  // TODO: support pause (persisting/cloning the state)
    37   [Item("MCTS Symbolic Regression", "Monte carlo tree search for symbolic regression.")]
     37  [Item("Symbolic Regression Tree Search", "tree search for symbolic regression.")]
    3838  [StorableClass]
    3939  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
     
    277277      int n = 0;
    278278
    279       // cancelled before we acutally started
     279      // canceled before we actually started
    280280      cancellationToken.ThrowIfCancellationRequested();
    281281
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs

    r15441 r15606  
    4848    //      - standardization of variables is possible (or might be necessary) as we adjust numeric parameters of the expression anyway
    4949    //      - to simplify the problem we can restrict the set of functions e.g. we assume which functions are necessary for the problem instance
    50     //        -> several steps: (a) polyinomials, (b) rational polynomials, (c) exponential or logarithmic functions, rational functions with exponential and logarithmic parts
     50    //        -> several steps: (a) polynomials, (b) rational polynomials, (c) exponential or logarithmic functions, rational functions with exponential and logarithmic parts
    5151    // 3) efficiency and effectiveness for real-world problems
    5252    //    - e.g. Tower problem
     
    5656    // TODO: The samples of x1*... or x2*... do not give any information about the relevance of the interaction term x1*x2 in general!
    5757    //       --> E.g. if x1, x2 ~ N(0, 1) or U(-1, 1) this is trivial to show
    58     //       --> Therefore, looking at rollout statistics for arm selection is useless in the general case!
     58    //       --> Therefore, looking at roll-out statistics for arm selection (MCTS-style) is useless in the general case!
    5959    //       --> It is necessary to rely on other features for the arm selection.
    6060    //       --> TODO: Which heuristics can we apply?
     
    6464    //       and later we find the a longer form x1 + x1 + x2 where the number of variable references
    6565    //       exceeds the maximum in the automaton this leads to an error (see unit tests)
    66     // ~~obsolete TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
    67     // ~~obsolete TODO: Why is the algorithm so slow for rather greedy policies (e.g. low C value in UCB)?
    68     // ~~obsolete TODO: check if we can use a quality measure with range [-1..1] in policies
    6966    // TODO: unit tests for benchmark problems which contain log / exp / x^-1 but without numeric constants
    7067    // TODO: check if transformation of y is correct and works (Obj 2)
     
    7774    // TODO: analyze / improve perf of ExprHashing (canonical form for expressions)
    7875    // TODO: support empty test partition
    79     // TODO: the algorithm should be invariant to linear transformations of the space (y = f(x') = f( Ax ) ) for invertible transformations A --> unit tests
     76    // TODO: the algorithm should be invariant to linear transformations of the space (y = f(x') = f( Ax ) ) for invertible transformations A --> see unit tests
    8077    #region static API
    8178
     
    10299      internal readonly Tree tree;
    103100      internal readonly Func<byte[], int, double> evalFun;
    104       // MCTS might get stuck. Track statistics on the number of effective rollouts
     101      // MCTS might get stuck. Track statistics on the number of effective roll-outs
    105102      internal int totalRollouts;
    106103      internal int effectiveRollouts;
     
    228225      }
    229226
    230       // takes the code of the best solution and creates and equivalent symbolic regression model
     227      // takes the code of the best solution and creates and equivalent symbolic regression models
    231228      public ISymbolicRegressionModel BestModel {
    232229        get {
     
    539536      // State equivalence is checked through ExprHash (based on the generated code through the path).
    540537
    541       // We switch between rollout-mode and expansion mode
    542       // Rollout-mode means we are navigating an existing path through the tree (using a rollout policy, e.g. UCB)
    543       // Expansion mode means we expand the graph, creating new nodes and edges (using an expansion policy, e.g. shortest route to a complete expression)
    544       // In expansion mode we might re-enter the graph and switch back to rollout-mode
    545       // We do this until we reach a complete expression (final state)
    546 
    547       // Loops in the graph are prevented by checking that the level of a child must be larger than the level of the parent
     538      // We switch between rollout-mode and expansion mode.
     539      // Rollout-mode means we are navigating an existing path through the tree (using a rollout policy, e.g. UCB).
     540      // Expansion mode means we expand the graph, creating new nodes and edges (using an expansion policy, e.g. shortest route to a complete expression).
     541      // In expansion mode we might re-enter the graph and switch back to rollout-mode.
     542      // We do this until we reach a complete expression (final state).
     543
     544      // Loops in the graph are prevented by checking that the level of a child must be larger than the level of the parent.
    548545      // Sub-graphs which have been completely searched are marked as done.
    549546      // Roll-out could lead to a state where all follow-states are done. In this case we call the rollout ineffective.
     
    806803
    807804    // for debugging only
    808 
     805    #region debugging
    809806
    810807    private static string TraceTree(Tree tree, State state) {
     
    894891      return sb.ToString();
    895892    }
     893  #endregion
    896894  }
    897895}
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/SymbolicExpressionGenerator.cs

    r14185 r15606  
    2828namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
    2929
    30   // translates byte code to a symbolic expression tree
     30  // helper class.
     31  // Translates byte code into a symbolic expression tree, e.g. for the final solution.
    3132  internal class SymbolicExpressionTreeGenerator {
    3233    const int MaxStackSize = 100;
  • branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Tree.cs

    r15438 r15606  
    2727    public bool Done { get; set; }
    2828    public int visits;
    29     //   {
    30     //   get { return actionStatistics.Done; }
    31     //   set { actionStatistics.Done = value; }
    32     // }
    33     // public IActionStatistics actionStatistics;
    34     // public Tree[] children;
    3529  }
    3630}
Note: See TracChangeset for help on using the changeset viewer.