Changeset 15784


Ignore:
Timestamp:
02/16/18 18:36:17 (19 months ago)
Author:
lkammere
Message:

#2886: Add basic implementation for inverse factors.

Location:
branches/2886_SymRegGrammarEnumeration
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

    r15772 r15784  
    2424    public NonterminalSymbol SinFactor;
    2525
     26    public NonterminalSymbol InvExpr;
     27    public NonterminalSymbol InvTerm;
     28    public NonterminalSymbol InvFactor;
     29
    2630    public NonterminalSymbol SimpleExpr;
    2731    public NonterminalSymbol SimpleTerm;
     
    3236    public TerminalSymbol Exp;
    3337    public TerminalSymbol Sin;
     38    public TerminalSymbol Inv;
    3439
    3540    // For infix notation
     
    7075      SinFactor = new NonterminalSymbol("SinFactor");
    7176
     77      InvExpr = new NonterminalSymbol("InvExpr");
     78      InvTerm = new NonterminalSymbol("InvTerm");
     79      InvFactor = new NonterminalSymbol("InvFactor");
     80
    7281      SimpleExpr = new NonterminalSymbol("SimpleExpr");
    7382      SimpleTerm = new NonterminalSymbol("SimpleTerm");
     
    7887      Exp = new TerminalSymbol("exp");
    7988      Sin = new TerminalSymbol("sin");
     89      Inv = new TerminalSymbol("inv");
    8090
    8191      OpeningBracket = new TerminalSymbol("(");
     
    94104      Term.AddProduction(Factor, Term, Multiplication);
    95105      Term.AddProduction(Factor);
     106      Term.AddProduction(InvExpr, Inv);
    96107
    97108      Factor.AddProduction(Var);
     
    109120      SimpleTerm.AddProduction(Var, SimpleTerm, Multiplication);
    110121      SimpleTerm.AddProduction(Var);
     122
     123      InvExpr.AddProduction(InvTerm, InvExpr, Addition);
     124      InvExpr.AddProduction(InvTerm);
     125
     126      InvTerm.AddProduction(InvFactor, InvTerm, Multiplication);
     127      InvTerm.AddProduction(InvFactor);
     128
     129      InvFactor.AddProduction(Var);
     130      InvFactor.AddProduction(LogFactor);
     131      InvFactor.AddProduction(SinFactor);
    111132      #endregion
    112133
     
    144165    private int[] GetSubtreeHashes(Stack<Symbol> parseStack) {
    145166      Symbol currentSymbol = parseStack.Pop();
    146 
    147       // MULTIPLICATION
    148       if (ReferenceEquals(currentSymbol, Multiplication)) {
    149         List<int> childHashes = new List<int>();
    150 
    151         // First subtree
    152         if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
    153           childHashes.AddRange(GetSubtreeHashes(parseStack));
    154         } else {
    155           childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
    156         }
    157         // Second subtree
    158         if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
    159           childHashes.AddRange(GetSubtreeHashes(parseStack));
    160         } else {
    161           childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
    162         }
    163 
    164         // Sort due to commutativity
    165         childHashes.Sort();
    166         return childHashes.ToArray();
    167       }
    168167
    169168      // ADDITION
     
    191190      }
    192191
    193       // LOG, EXP, SIN
     192      // MULTIPLICATION
     193      if (ReferenceEquals(currentSymbol, Multiplication)) {
     194        List<int> childHashes = new List<int>();
     195
     196        // First subtree
     197        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
     198          childHashes.AddRange(GetSubtreeHashes(parseStack));
     199        } else {
     200          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
     201        }
     202        // Second subtree
     203        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
     204          childHashes.AddRange(GetSubtreeHashes(parseStack));
     205        } else {
     206          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
     207        }
     208
     209        // Sort due to commutativity
     210        childHashes.Sort();
     211
     212        // Cancel out inverse factors.
     213        var inversChildHashes = childHashes
     214          .Select(ch => AggregateHashes(Inv, ch.ToEnumerable()))
     215          .ToList();
     216
     217        return childHashes // If this factor cancels out another one, then remove BOTH. Otherwise, keep the factor.
     218          .Where(ch => !inversChildHashes.Remove(ch))
     219          .ToArray();
     220      }
     221
     222      // LOG, EXP, SIN, INV
    194223      if (ReferenceEquals(currentSymbol, Log) || ReferenceEquals(currentSymbol, Exp) ||
    195           ReferenceEquals(currentSymbol, Sin)) {
     224          ReferenceEquals(currentSymbol, Sin) || ReferenceEquals(currentSymbol, Inv)) {
    196225        return AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)).ToEnumerable().ToArray();
    197226      }
     
    205234
    206235      int start;
    207       if (ReferenceEquals(operatorSym, Addition) && hashesArray.Count() <= 1) {
     236      if ((ReferenceEquals(operatorSym, Addition) || ReferenceEquals(operatorSym, Multiplication)) && hashesArray.Count() <= 1) {
    208237        start = 0;
    209238      } else {
     
    257286      } else if (ReferenceEquals(currentSymbol, Sin)) {
    258287        parsedSubTree = sinSy.CreateTreeNode();
     288        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
     289
     290      } else if (ReferenceEquals(currentSymbol, Inv)) {
     291        parsedSubTree = divSy.CreateTreeNode();
     292        ConstantTreeNode dividend = (ConstantTreeNode)constSy.CreateTreeNode();
     293        dividend.Value = 1.0;
     294        parsedSubTree.AddSubtree(dividend);
    259295        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
    260296
     
    293329        result.AddRange(rightPart);
    294330
    295       } else if (ReferenceEquals(head, Log) || ReferenceEquals(head, Exp) || ReferenceEquals(head, Sin)) {
     331      } else if (ReferenceEquals(head, Log) || ReferenceEquals(head, Exp)
     332              || ReferenceEquals(head, Sin) || ReferenceEquals(head, Inv)) {
    296333        result.Add(head);
    297334        result.Add(OpeningBracket);
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

    r15776 r15784  
    9494      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
    9595
    96       Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.RandomList)));
     96      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.Stack)));
    9797    }
    9898
  • branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

    r15776 r15784  
    11using System;
     2using System.Collections;
     3using System.Collections.Generic;
    24using System.Linq;
    35using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
    46using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
     7using HeuristicLab.Common;
    58using HeuristicLab.Core;
    69using HeuristicLab.Problems.DataAnalysis;
     
    5255    [TestMethod]
    5356    [TestProperty("Goal", "structure search")]
    54     public void MctsSymbReg_NoConstants_Nguyen1() {
     57    public void NoConstants_Nguyen1() {
    5558      // x³ + x² + x
    56       alg.MaxTreeSize = 15;
    57       alg.Problem.ProblemData = new NguyenFunctionOne(Seed).GenerateRegressionData(); 
     59      alg.MaxTreeSize = 12;
     60      alg.Problem.ProblemData = new NguyenFunctionOne(Seed).GenerateRegressionData();
    5861
    5962      alg.Start();
     
    8386    //[TestMethod]
    8487    [TestProperty("Goal", "structure search")]
    85     public void MctsSymbReg_NoConstants_Nguyen2() {
     88    public void NoConstants_Nguyen2() {
    8689      // x^4 + x³ + x² + x
    8790      alg.MaxTreeSize = 20;
     
    9598    //[TestMethod]
    9699    [TestProperty("Goal", "structure search")]
    97     public void MctsSymbReg_NoConstants_Nguyen3() {
     100    public void NoConstants_Nguyen3() {
    98101      // x^5 + x^4 + x^3 + x^2 + x
    99102      alg.MaxTreeSize = 32;
     
    105108    }
    106109
    107     [TestMethod]                             
    108     [TestProperty("Goal", "structure search")]
    109     public void MctsSymbReg_NoConstants_Nguyen6() {
     110    [TestMethod]
     111    [TestProperty("Goal", "structure search")]
     112    public void NoConstants_Nguyen6() {
    110113      // sin(x) + sin(x + x²)
    111       alg.MaxTreeSize = 15;
     114      alg.MaxTreeSize = 13;
    112115      alg.Problem.ProblemData = new NguyenFunctionSix(Seed).GenerateRegressionData();
    113116
    114117      alg.Start();
    115       EvaluateGrammarEnumeration();
    116     }
    117 
    118     [TestMethod]
    119     [TestProperty("Goal", "structure search")]
    120     public void MctsSymbReg_NoConstants_Nguyen9() {
     118
     119      TerminalSymbol varSymbol = alg.Grammar.Var.VariableTerminalSymbols.First();
     120      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
     121      TerminalSymbol addSymbol = alg.Grammar.Addition;
     122      TerminalSymbol sinSymbol = alg.Grammar.Sin;
     123
     124      SymbolString targetSolution = new SymbolString(new[] {
     125        varSymbol, sinSymbol,
     126        varSymbol, varSymbol, mulSymbol, varSymbol, addSymbol, sinSymbol, addSymbol
     127      });
     128
     129      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
     130      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
     131
     132      Assert.IsTrue(alg.DistinctSentences.ContainsKey(actualSolutionHash), "Actual solution was not generated!");
     133
     134      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
     135
     136      EvaluateGrammarEnumeration();
     137    }
     138
     139    [TestMethod]
     140    [TestProperty("Goal", "structure search")]
     141    public void NoConstants_Nguyen9() {
    121142      // sin(x) + sin(y²)
    122143      alg.MaxTreeSize = 10;
     
    133154      alg.MaxTreeSize = 10;
    134155      alg.Problem.ProblemData = new PolyTen(Seed).GenerateRegressionData();
     156
     157      alg.Start();
     158      EvaluateGrammarEnumeration();
     159    }
     160
     161    [TestMethod]
     162    [TestProperty("Goal", "structure search")]
     163    public void NoConstants_Inverse() {
     164      // 1 / (log(x)*x + x)
     165      alg.MaxTreeSize = 12;
     166
     167      var x = Enumerable.Range(0, 100).Select(_ => rand.NextDouble() + 1.1).ToList();
     168      var y = x.Select(xi => 1 / (Math.Log(xi) * xi + xi)).ToList();
     169      alg.Problem.ProblemData = new RegressionProblemData(new Dataset(new List<string>() { "x", "y" }, new List<IList>() { x, y }), "x".ToEnumerable(), "y");
    135170
    136171      alg.Start();
     
    210245      var ys = ds.GetDoubleValues("Y").ToArray();
    211246      var x1 = ds.GetDoubleValues("X1").ToArray();
    212       var x2 = ds.GetDoubleValues("X2").ToArray();
     247      var x2 = ds.GetDoubleValues("X2").ToArray();                                           
    213248      var x3 = ds.GetDoubleValues("X3").ToArray();
    214249      var x4 = ds.GetDoubleValues("X4").ToArray();
  • branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

    r15746 r15784  
    106106    }
    107107
     108    [TestMethod]
     109    [TestCategory("TreeHashing")]
     110    public void InverseFactorCancelationSimple() {
     111      SymbolString s1 = new SymbolString(new Symbol[] { varA, grammar.Inv, varB, grammar.Multiplication, varA, grammar.Multiplication, varA, grammar.Multiplication });
     112      SymbolString s2 = new SymbolString(new Symbol[] { varA, varB, grammar.Multiplication });
     113
     114      int hash1 = grammar.CalcHashCode(s1);
     115      int hash2 = grammar.CalcHashCode(s2);
     116
     117      Assert.AreEqual(hash1, hash2);
     118    }
     119
     120    [TestMethod]
     121    [TestCategory("TreeHashing")]
     122    public void InverseFactorCancelationComplex() {
     123      SymbolString s1 = new SymbolString(new Symbol[] { varA, grammar.Sin, varA, varA, grammar.Multiplication, varA, grammar.Addition, grammar.Sin, grammar.Addition });
     124      SymbolString s2 = new SymbolString(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });
     125
     126      int hash1 = grammar.CalcHashCode(s1);
     127      int hash2 = grammar.CalcHashCode(s2);
     128
     129      Assert.AreEqual(hash1, hash2);
     130    }
    108131
    109132    #region parser
Note: See TracChangeset for help on using the changeset viewer.