Changeset 12024

Timestamp:

02/17/15 16:03:49 (10 years ago)

Author:

gkronber

Message:

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

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• HeuristicLab.Common/ExpressionExtender.cs (modified) (9 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs (modified) (2 diffs)
• Test/TestCanonicalExpressions.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

@@ -11 +11 @@
 namespace HeuristicLab.Algorithms.Bandits {
   // helper to create canonical forms of expressions
-  // NOTE: Not implemented yet (see unit test for divisions)
   // TODO: change symbolicregressionpoly10problem to use this class
   // this does not support expressions with constants (in transformations we assume constant opt is used)
@@ -19 +18 @@
     // supports the grammar
     // G(E):
-    //     E -> V | V+E | V-E | V*E | V%E | V/E | (E) 
+    //     E -> V | V+E | V-E | V*E | V%E | (E) 
     //     V -> <variables>
     //     ";
 
-    // might produce expressions of the form |/x
+    // might produce expressions of the form /x (= 1/x)
     // the pipe symbol | is used for the constant one (in comparison to other constants)
     private string sentence;
@@ -31 +30 @@
       InitLex(phrase);
       var e = CanonicalExpr();
-      return e.ToString(); 
+      return e.ToString();
     }
 
@@ -97 +96 @@
           if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) {
             foreach (var invF in f.Expr.Terms.First().Factors) {
-              if (invF.ToString() == "|") continue;
+              if (invF.ToString() == "1") continue;
               invF.Invert();
               factors.Add(invF);
@@ -173 +172 @@
       var results = new List<Factor>(factors);
       foreach (var f in factorsArr) {
-        if (f.ToString() == "|") results.Remove(f);
-        if (f.ToString() == "|/(|)") results.Remove(f);
+        if (f.ToString() == "1") results.Remove(f);
+        if (f.ToString() == "1/(1)") results.Remove(f);
         if (f.IsInverse) {
           // find matching
@@ -185 +184 @@
             results.Remove(match);
             if (!results.Any())
-              results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one
+              results.Insert(idx, new Factor('1')); // when the factor is the last one then insert a one
 
             // also mark as cancelled in the factorsArr
             idx = Array.IndexOf(factorsArr, match);
-            factorsArr[idx] = new Factor('|');
+            factorsArr[idx] = new Factor('1');
           }
         }
       }
-      // remove all unnecessary "1* factors"
-
-      if (results.Count == 0) results.Add(new Factor('|'));
+      if (results.Count == 0) results.Add(new Factor('1'));
       return results;
     }
@@ -230 +227 @@
           var countComp = Factors.Count().CompareTo(other.Factors.Count());
           if (countComp != 0) return countComp;
-          return string.Join("", Factors).CompareTo(string.Join("", other.Factors));
+          foreach (var pair in Factors.Zip(other.Factors, Tuple.Create)) {
+            var fComp = pair.Item1.CompareTo(pair.Item2);
+            if (fComp != 0) return fComp;
+          }
+          return 0;
         }
       }
@@ -304 +305 @@
         var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
         if (IsInverse) {
-          return "|/" + s;
+          return "/" + s;
         } else return s;
       }
@@ -356 +357 @@
 
       public override string ToString() {
-        // if (Inverse && Terms.Count > 1)
-        //   return "(" + string.Join("+", Terms) + ")";
-        // else if (Inverse && Terms.Count == 1) {
-        //   return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
-        // } else
         return string.Join("+", Terms);
       }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs

@@ -95 +95 @@
       if (f != null) factors.Add(f);
       var curSy = CurSy();
-      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
+      while (curSy == '*' || curSy == '%') { // division and protected division symbols are handled in the same way
         if (curSy == '*') {
           NewSy();
@@ -135 +135 @@
         r = variables[varIdx];
         NewSy();
-      } else if (curSy == '|') {
-        // pipe symbol is used in the expressionextender to represent constant one (|/x). 
+      } else if (curSy == '/') {
+        // /-symbol used in the expressionextender to represent inverse (1/x). 
         // this is necessary because we also use symbols 0..9 as indices for ERCs
-        r = 1.0;
         NewSy();
+        r = 1.0 / Fact(variables, constants);
       } else if (curSy >= '0' && curSy <= '9') {
         int o = (byte)curSy - (byte)'0';

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

@@ -126 +126 @@
 
     public double Evaluate(string sentence) {
+      var extender = new ExpressionExtender();
+      sentence = extender.CanonicalRepresentation(sentence);
       if (useConstantOpt)
         return OptimizeConstantsAndEvaluate(sentence);
       else {
-        var extender = new ExpressionExtender();
 
         Debug.Assert(SimpleEvaluate(sentence) == SimpleEvaluate(extender.CanonicalRepresentation(sentence)));
@@ -152 +153 @@
 
     public IEnumerable<Feature> GetFeatures(string phrase) {
+      // throw new NotImplementedException();
       phrase = CanonicalRepresentation(phrase);
-      return new Feature[] { new Feature(phrase, 1.0) };
+      return phrase.Split('+').Distinct().Select(t => new Feature(t, 1.0));
+      // return new Feature[] { new Feature(phrase, 1.0) };
     }
 

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs

@@ -92 +92 @@
       r = Fact(d, erc);
       var curSy = CurSy();
-      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
+      while (curSy == '*' || curSy == '%') {
         if (curSy == '*') {
           NewSy();
@@ -124 +124 @@
         r = d[o];
         NewSy();
-      } else if (curSy == '|') {
-        // pipe symbol is used in the expressionextender to represent constant one (|/x). 
+      } else if (curSy == '/') {
+        // /-symbol is used in the expressionextender to represent inverse (1/x). 
         // this is necessary because we also use symbols 0..9 as indices for ERCs
-        r = 1.0;
         NewSy();
+        r = 1.0 / Fact(d, erc);
       } else /* if (curSy >= '0' && curSy <= '9') */ {
         int o = (byte)curSy - (byte)'0';

branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

@@ -67 +67 @@
       Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
       Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
-      Assert.AreEqual("|/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
+      Assert.AreEqual("/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
     }
     [TestMethod]
     public void TestDivisionExpansion() {
       var extender = new ExpressionExtender();
-      Assert.AreEqual("a*|/c+b*|/c", extender.CanonicalRepresentation("(b+a)%c"));
-      Assert.AreEqual("a*|/c*|/d+b*|/c*|/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
-      Assert.AreEqual("a*|/(c+d)+b*|/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
-      Assert.AreEqual("a*b*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
+      Assert.AreEqual("a*/c+b*/c", extender.CanonicalRepresentation("(b+a)%c"));
+      Assert.AreEqual("a*/c*/d+b*/c*/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
+      Assert.AreEqual("a*/(c+d)+b*/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
+      Assert.AreEqual("a*b*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
 
-      Assert.AreEqual("a*b*|/(a+b)*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
-      Assert.AreEqual("a*b*|/(c+d)*|/(a*|/e+b*|/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
+      Assert.AreEqual("a*b*/(a+b)*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
+      Assert.AreEqual("a*b*/(c+d)*/(a*/e+b*/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
       // a*b*e%(c+d)%(a+b)
     }
@@ -84 +84 @@
     public void TestDivisionCancellation() {
       var extender = new ExpressionExtender();
-      Assert.AreEqual("|", extender.CanonicalRepresentation("a%a"));
+      Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
-      Assert.AreEqual("|/a", extender.CanonicalRepresentation("(a%a)%a"));
-      Assert.AreEqual("|/a", extender.CanonicalRepresentation("a%a%a"));
+      Assert.AreEqual("/a", extender.CanonicalRepresentation("(a%a)%a"));
+      Assert.AreEqual("/a", extender.CanonicalRepresentation("a%a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
-      Assert.AreEqual("|", extender.CanonicalRepresentation("(a+b)%(b+a)"));
-      Assert.AreEqual("|/a+|/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
-      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)"));
-      Assert.AreEqual("|", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
-      Assert.AreEqual("|", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
+      Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
+      Assert.AreEqual("/a+/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
+      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)"));
+      Assert.AreEqual("1", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
+      Assert.AreEqual("1", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
     }