Changeset 11832 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems

Timestamp:

01/27/15 16:34:34 (9 years ago)

Author:

gkronber

Message:

linear value function approximation and good results for poly-10 benchmark

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems

Files:

• EvenParityProblem.cs (modified) (1 diff)
• ExpressionInterpreter.cs (modified) (6 diffs)
• FindPhrasesProblem.cs (modified) (2 diffs)
• HardPalindromeProblem.cs (modified) (1 diff)
• PalindromeProblem.cs (modified) (1 diff)
• RoyalPairProblem.cs (modified) (1 diff)
• RoyalPhraseSequenceProblem.cs (modified) (2 diffs)
• RoyalRoadProblem.cs (modified) (1 diff)
• RoyalSequenceProblem.cs (modified) (1 diff)
• RoyalSymbolProblem.cs (modified) (1 diff)
• RoyalTreeProblem.cs (modified) (1 diff)
• SantaFeAntProblem.cs (modified) (2 diffs)
• SymbolicRegressionPoly10Problem.cs (modified) (1 diff)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs

@@ -50 +50 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

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

@@ -3 +3 @@
 using System.Diagnostics.Eventing.Reader;
 using System.Linq;
+using System.Runtime.CompilerServices;
 using System.Runtime.Remoting.Messaging;
 using System.Text;
@@ -10 +11 @@
 namespace HeuristicLab.Problems.GrammaticalOptimization {
   public class ExpressionInterpreter {
+    private static readonly double[] emptyErc = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+
     private string sentence;
     private int syIdx;
@@ -15 +18 @@
     // Expr -> Term { ('+' | '-' | '^' ) Term } 
     // Term -> Fact { ('*' | '/') Fact }
-    // Fact -> '!' Expr | '(' Expr ')' | Var
+    // Fact -> '!' Expr | '(' Expr ')' | Var | const
     // Var -> 'a'..'z'
+    // const -> '0' .. '9'
+
+    // constants are Koza-style ephemeral random constants (ERC). for now we only allow up to 10 constants.
+    // The constant symbols '0' .. '9' are treated as ERC indices
 
     // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
 
     public bool Interpret(string sentence, bool[] vars) {
+      return Interpret(sentence, vars, emptyErc);
+    }
+
+    public bool Interpret(string sentence, bool[] vars, double[] erc) {
       InitLex(sentence);
       var d = new double[vars.Length];
       for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
-      return !(Expr(d).IsAlmost(0));
+      return !(Expr(d, erc).IsAlmost(0));
     }
 
     public double Interpret(string sentence, double[] vars) {
+      return Interpret(sentence, vars, emptyErc);
+    }
+
+    public double Interpret(string sentence, double[] vars, double[] erc) {
       InitLex(sentence);
-      return Expr(vars);
+      return Expr(vars, erc);
     }
 
@@ -51 +66 @@
     }
 
-    private double Expr(double[] d) {
+    private double Expr(double[] d, double[] erc) {
       var r = 0.0;
-      r = Term(d);
+      r = Term(d, erc);
       var curSy = CurSy();
       while (curSy == '+' || curSy == '-' || curSy == '^') {
         if (curSy == '+') {
           NewSy();
-          r += Expr(d);
+          r += Expr(d, erc);
         } else if (curSy == '-') {
           NewSy();
-          r -= Expr(d);
+          r -= Expr(d, erc);
         } else {
           NewSy();
-          var e = Expr(d);
+          var e = Expr(d, erc);
           r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
         }
@@ -72 +87 @@
     }
 
-    private double Term(double[] d) {
+    private double Term(double[] d, double[] erc) {
       var r = 0.0;
-      r = Fact(d);
+      r = Fact(d, erc);
       var curSy = CurSy();
       while (curSy == '*' || curSy == '/') {
         if (curSy == '*') {
           NewSy();
-          r *= Term(d);
+          r *= Term(d, erc);
         } else {
           NewSy();
-          r /= Term(d);
+          r /= Term(d, erc);
         }
         curSy = CurSy();
@@ -89 +104 @@
     }
 
-    private double Fact(double[] d) {
+    private double Fact(double[] d, double[] erc) {
       double r = 0.0;
       var curSy = CurSy();
       if (curSy == '!') {
         NewSy();
-        r = Not(Expr(d));
+        r = Not(Expr(d, erc));
       } else if (curSy == '(') {
         NewSy();
-        r = Expr(d);
+        r = Expr(d, erc);
         if (CurSy() != ')') throw new ArgumentException();
         NewSy();
-      } else /* if (curSy >= 'a' && curSy <= 'z') */ {
+      } else if (curSy >= 'a' && curSy <= 'z') {
         int o = (byte)curSy - (byte)'a';
         //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
         if (o < 0 || o >= d.Length) throw new ArgumentException();
         r = d[o];
+        NewSy();
+      } else /* if (curSy >= '0' && curSy <= '9') */ {
+        int o = (byte)curSy - (byte)'0';
+        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
+        if (o < 0 || o >= 10) throw new ArgumentException();
+        r = erc[o];
         NewSy();
       }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs

@@ -129 +129 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       // as the ordering of phrases does not matter we can reorder the phrases
       // and remove duplicates
-      var numPhrases = terminalPhrase.Length / phraseLen;
+      var numPhrases = phrase.Length / phraseLen;
       var phrases = new SortedSet<string>();
       for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
         var sentenceIdx = phraseIdx * phraseLen;
-        var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
-        phrase = CanonicalPhrase(phrase);
-        if (!phrases.Contains(phrase)) phrases.Add(phrase);
+        var subphrase = phrase.Substring(sentenceIdx, phraseLen);
+        subphrase = CanonicalPhrase(subphrase);
+        if (!phrases.Contains(subphrase)) phrases.Add(subphrase);
       }
-      var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+      var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
       remainder = CanonicalPhrase(remainder);
       if (!phrases.Contains(remainder)) phrases.Add(remainder);
@@ -146 +146 @@
       return string.Join("", phrases);
     }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
+
+    public override string ToString() {
+      return string.Format("\"FindPhrasesProblem {0} {1} {2} {3:F2} {4} {5:F2} {6}\"", numPhrases, phraseLen,
+        optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets);
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs

@@ -39 +39 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs

@@ -80 +80 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs

@@ -35 +35 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
+      //throw new NotImplementedException();
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
       throw new NotImplementedException();
-      return terminalPhrase;
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

@@ -113 +113 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       if (phrasesAsSets) {
         var sb = new StringBuilder();
-        var numPhrases = terminalPhrase.Length / phraseLen;
+        var numPhrases = phrase.Length / phraseLen;
         for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
           var sentenceIdx = phraseIdx * phraseLen;
-          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
-          phrase = CanonicalPhrase(phrase);
-          sb.Append(phrase);
+          var subphrase = phrase.Substring(sentenceIdx, phraseLen);
+          subphrase = CanonicalPhrase(subphrase);
+          sb.Append(subphrase);
         }
 
-        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+        var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
         remainder = CanonicalPhrase(remainder);
         sb.Append(remainder);
@@ -130 +130 @@
         return sb.ToString();
       } else
-        return terminalPhrase;
+        return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs

@@ -29 +29 @@
       throw new NotImplementedException();
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs

@@ -77 +77 @@
 
     // in each position there could be multiple correct and incorrect symbols
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       var sb = new StringBuilder();
-      for (int i = 0; i < terminalPhrase.Length; i++) {
-        if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
+      for (int i = 0; i < phrase.Length; i++) {
+        if (optimalSymbolsForPos[i].Contains(phrase[i])) {
           sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
         } else {
-          sb.Append(terminalPhrase[i]);
+          sb.Append(phrase[i]);
         }
       }
       return sb.ToString();
     }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs

@@ -34 +34 @@
       return regex.Matches(sentence).Count;
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

@@ -29 +29 @@
       throw new NotImplementedException();
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs

@@ -102 +102 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      var sb = new StringBuilder(terminalPhrase);
-      string canonicalPhrase = terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      var sb = new StringBuilder(phrase);
+      string canonicalPhrase = phrase;
       string oldPhrase;
       do {
@@ -112 +112 @@
       } while (canonicalPhrase != oldPhrase);
       return sb.ToString();
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase) {
+      return Enumerable.Repeat(new Feature(CanonicalRepresentation(phrase), 1.0), 1);
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs

@@ -120 +120 @@
       return canonicalTerm;
     }
+
+    // splits the phrase into terms and creates (sparse) term-occurrance features
+    public IEnumerable<Feature> GetFeatures(string phrase) {
+      var canonicalTerms = new HashSet<string>();
+      foreach (string t in phrase.Split('+')) {
+        canonicalTerms.Add(CanonicalTerm(t));
+      }
+      return canonicalTerms.Select(entry => new Feature(entry, 1.0)).Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
+    }
+
   }
 }