Changeset 12024


Ignore:
Timestamp:
02/17/15 16:03:49 (7 years ago)
Author:
gkronber
Message:

#2283: changed handling of inverse expressions in transformation of expressions to canonical form

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

    r12014 r12024  
    1111namespace HeuristicLab.Algorithms.Bandits {
    1212  // helper to create canonical forms of expressions
    13   // NOTE: Not implemented yet (see unit test for divisions)
    1413  // TODO: change symbolicregressionpoly10problem to use this class
    1514  // this does not support expressions with constants (in transformations we assume constant opt is used)
     
    1918    // supports the grammar
    2019    // G(E):
    21     //     E -> V | V+E | V-E | V*E | V%E | V/E | (E)
     20    //     E -> V | V+E | V-E | V*E | V%E | (E)
    2221    //     V -> <variables>
    2322    //     ";
    2423
    25     // might produce expressions of the form |/x
     24    // might produce expressions of the form /x (= 1/x)
    2625    // the pipe symbol | is used for the constant one (in comparison to other constants)
    2726    private string sentence;
     
    3130      InitLex(phrase);
    3231      var e = CanonicalExpr();
    33       return e.ToString(); 
     32      return e.ToString();
    3433    }
    3534
     
    9796          if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) {
    9897            foreach (var invF in f.Expr.Terms.First().Factors) {
    99               if (invF.ToString() == "|") continue;
     98              if (invF.ToString() == "1") continue;
    10099              invF.Invert();
    101100              factors.Add(invF);
     
    173172      var results = new List<Factor>(factors);
    174173      foreach (var f in factorsArr) {
    175         if (f.ToString() == "|") results.Remove(f);
    176         if (f.ToString() == "|/(|)") results.Remove(f);
     174        if (f.ToString() == "1") results.Remove(f);
     175        if (f.ToString() == "1/(1)") results.Remove(f);
    177176        if (f.IsInverse) {
    178177          // find matching
     
    185184            results.Remove(match);
    186185            if (!results.Any())
    187               results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one
     186              results.Insert(idx, new Factor('1')); // when the factor is the last one then insert a one
    188187
    189188            // also mark as cancelled in the factorsArr
    190189            idx = Array.IndexOf(factorsArr, match);
    191             factorsArr[idx] = new Factor('|');
     190            factorsArr[idx] = new Factor('1');
    192191          }
    193192        }
    194193      }
    195       // remove all unnecessary "1* factors"
    196 
    197       if (results.Count == 0) results.Add(new Factor('|'));
     194      if (results.Count == 0) results.Add(new Factor('1'));
    198195      return results;
    199196    }
     
    230227          var countComp = Factors.Count().CompareTo(other.Factors.Count());
    231228          if (countComp != 0) return countComp;
    232           return string.Join("", Factors).CompareTo(string.Join("", other.Factors));
     229          foreach (var pair in Factors.Zip(other.Factors, Tuple.Create)) {
     230            var fComp = pair.Item1.CompareTo(pair.Item2);
     231            if (fComp != 0) return fComp;
     232          }
     233          return 0;
    233234        }
    234235      }
     
    304305        var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
    305306        if (IsInverse) {
    306           return "|/" + s;
     307          return "/" + s;
    307308        } else return s;
    308309      }
     
    356357
    357358      public override string ToString() {
    358         // if (Inverse && Terms.Count > 1)
    359         //   return "(" + string.Join("+", Terms) + ")";
    360         // else if (Inverse && Terms.Count == 1) {
    361         //   return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
    362         // } else
    363359        return string.Join("+", Terms);
    364360      }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs

    r12014 r12024  
    9595      if (f != null) factors.Add(f);
    9696      var curSy = CurSy();
    97       while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
     97      while (curSy == '*' || curSy == '%') { // division and protected division symbols are handled in the same way
    9898        if (curSy == '*') {
    9999          NewSy();
     
    135135        r = variables[varIdx];
    136136        NewSy();
    137       } else if (curSy == '|') {
    138         // pipe symbol is used in the expressionextender to represent constant one (|/x).
     137      } else if (curSy == '/') {
     138        // /-symbol used in the expressionextender to represent inverse (1/x).
    139139        // this is necessary because we also use symbols 0..9 as indices for ERCs
    140         r = 1.0;
    141140        NewSy();
     141        r = 1.0 / Fact(variables, constants);
    142142      } else if (curSy >= '0' && curSy <= '9') {
    143143        int o = (byte)curSy - (byte)'0';
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

    r12014 r12024  
    126126
    127127    public double Evaluate(string sentence) {
     128      var extender = new ExpressionExtender();
     129      sentence = extender.CanonicalRepresentation(sentence);
    128130      if (useConstantOpt)
    129131        return OptimizeConstantsAndEvaluate(sentence);
    130132      else {
    131         var extender = new ExpressionExtender();
    132133
    133134        Debug.Assert(SimpleEvaluate(sentence) == SimpleEvaluate(extender.CanonicalRepresentation(sentence)));
     
    152153
    153154    public IEnumerable<Feature> GetFeatures(string phrase) {
     155      // throw new NotImplementedException();
    154156      phrase = CanonicalRepresentation(phrase);
    155       return new Feature[] { new Feature(phrase, 1.0) };
     157      return phrase.Split('+').Distinct().Select(t => new Feature(t, 1.0));
     158      // return new Feature[] { new Feature(phrase, 1.0) };
    156159    }
    157160
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs

    r12014 r12024  
    9292      r = Fact(d, erc);
    9393      var curSy = CurSy();
    94       while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
     94      while (curSy == '*' || curSy == '%') {
    9595        if (curSy == '*') {
    9696          NewSy();
     
    124124        r = d[o];
    125125        NewSy();
    126       } else if (curSy == '|') {
    127         // pipe symbol is used in the expressionextender to represent constant one (|/x).
     126      } else if (curSy == '/') {
     127        // /-symbol is used in the expressionextender to represent inverse (1/x).
    128128        // this is necessary because we also use symbols 0..9 as indices for ERCs
    129         r = 1.0;
    130129        NewSy();
     130        r = 1.0 / Fact(d, erc);
    131131      } else /* if (curSy >= '0' && curSy <= '9') */ {
    132132        int o = (byte)curSy - (byte)'0';
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

    r12014 r12024  
    6767      Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
    6868      Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
    69       Assert.AreEqual("|/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
     69      Assert.AreEqual("/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
    7070    }
    7171    [TestMethod]
    7272    public void TestDivisionExpansion() {
    7373      var extender = new ExpressionExtender();
    74       Assert.AreEqual("a*|/c+b*|/c", extender.CanonicalRepresentation("(b+a)%c"));
    75       Assert.AreEqual("a*|/c*|/d+b*|/c*|/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
    76       Assert.AreEqual("a*|/(c+d)+b*|/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
    77       Assert.AreEqual("a*b*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
     74      Assert.AreEqual("a*/c+b*/c", extender.CanonicalRepresentation("(b+a)%c"));
     75      Assert.AreEqual("a*/c*/d+b*/c*/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
     76      Assert.AreEqual("a*/(c+d)+b*/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
     77      Assert.AreEqual("a*b*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
    7878
    79       Assert.AreEqual("a*b*|/(a+b)*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
    80       Assert.AreEqual("a*b*|/(c+d)*|/(a*|/e+b*|/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
     79      Assert.AreEqual("a*b*/(a+b)*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
     80      Assert.AreEqual("a*b*/(c+d)*/(a*/e+b*/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
    8181      // a*b*e%(c+d)%(a+b)
    8282    }
     
    8484    public void TestDivisionCancellation() {
    8585      var extender = new ExpressionExtender();
    86       Assert.AreEqual("|", extender.CanonicalRepresentation("a%a"));
     86      Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
    8787      Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
    88       Assert.AreEqual("|/a", extender.CanonicalRepresentation("(a%a)%a"));
    89       Assert.AreEqual("|/a", extender.CanonicalRepresentation("a%a%a"));
     88      Assert.AreEqual("/a", extender.CanonicalRepresentation("(a%a)%a"));
     89      Assert.AreEqual("/a", extender.CanonicalRepresentation("a%a%a"));
    9090      Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
    91       Assert.AreEqual("|", extender.CanonicalRepresentation("(a+b)%(b+a)"));
    92       Assert.AreEqual("|/a+|/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
    93       Assert.AreEqual("a*|/(a*c*|/b+e*|/d*|/f)+b*|/(a*c*|/b+e*|/d*|/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
    94       Assert.AreEqual("|", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
    95       Assert.AreEqual("|", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
     91      Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
     92      Assert.AreEqual("/a+/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
     93      Assert.AreEqual("a*/(a*c*/b+e*/d*/f)+b*/(a*c*/b+e*/d*/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
     94      Assert.AreEqual("1", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
     95      Assert.AreEqual("1", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
    9696    }
    9797
Note: See TracChangeset for help on using the changeset viewer.