Changeset 11755 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs

Timestamp:

01/13/15 20:02:29 (9 years ago)

Author:

gkronber

Message:

#2283: implemented synthetic benchmark problems (modeling symb-reg) with configurable hardness

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs (modified) (6 diffs)

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

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Data.Odbc;
 using System.Diagnostics;
 using System.Linq;
@@ -17 +18 @@
   // - number of decoy (sub-optimal) phrases
   // - reward for decoy phrases (must be smaller than reward for optimal phrases)
+  // - phrasesAsSets: a switch to determine wether symbols in a phrase can be shuffled (sets) or if the ordering is relevant (non-sets)
+
+  // this problem should be similar to symbolic regression and should be easier for approaches using a state esimation value and the canoncial state 
+  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
   public class FindPhrasesProblem : IProblem {
 
     private readonly IGrammar grammar;
-    private readonly int alphabetSize;
     private readonly int numPhrases;
     private readonly int phraseLen;
@@ -27 +31 @@
     private readonly double correctReward;
     private readonly double decoyReward;
+    private readonly bool phrasesAsSets;
     private readonly SortedSet<string> optimalPhrases;
     private readonly SortedSet<string> decoyPhrases;
 
     public FindPhrasesProblem(Random rand, int alphabetSize, int numPhrases, int phraseLen, int numOptimalPhrases, int numDecoyPhrases = 1,
-      double correctReward = 1.0, double decoyReward = 0.0) {
+      double correctReward = 1.0, double decoyReward = 0.0, bool phrasesAsSets = false) {
       if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
       if (numPhrases <= 0) throw new ArgumentException();
@@ -39 +44 @@
       if (correctReward <= decoyReward) throw new ArgumentException();
 
-      this.alphabetSize = alphabetSize;
       this.numPhrases = numPhrases;
       this.phraseLen = phraseLen;
       this.correctReward = correctReward;
       this.decoyReward = decoyReward;
+      this.phrasesAsSets = phrasesAsSets;
 
       // create grammar
@@ -54 +59 @@
       this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
 
-      this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
-      for (int i = 0; i < sequenceLen; i++) {
-        optimalPhrasesForPos[i] = new SortedSet<string>();
-        for (int j = 0; j < k; j++) {
-          string phrase = "";
-          do {
-            for (int l = 0; l < phraseLen; l++) {
-              phrase += terminalSymbols.SelectRandom(rand);
-            }
-          } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
-          optimalPhrasesForPos[i].Add(phrase);
+      // generate optimal phrases
+      optimalPhrases = new SortedSet<string>();
+      while (optimalPhrases.Count < numOptimalPhrases) {
+        string phrase = "";
+        for (int l = 0; l < phraseLen; l++) {
+          phrase += terminalSymbols.SelectRandom(rand);
         }
+        phrase = CanonicalPhrase(phrase);
+
+        // don't allow dups
+        if (!optimalPhrases.Contains(phrase)) optimalPhrases.Add(phrase);
       }
 
-      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * sequenceLen) == 1.0);
+      // generate decoy phrases
+      decoyPhrases = new SortedSet<string>();
+      while (decoyPhrases.Count < numDecoyPhrases) {
+        string phrase = "";
+        for (int l = 0; l < phraseLen; l++) {
+          phrase += terminalSymbols.SelectRandom(rand);
+        }
+        phrase = CanonicalPhrase(phrase);
+
+        // don't allow dups
+        if (!optimalPhrases.Contains(phrase) && !decoyPhrases.Contains(phrase)) decoyPhrases.Add(phrase);
+      }
+
+      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * numPhrases) == 1.0);
     }
 
     public double BestKnownQuality(int maxLen) {
-      return Math.Min(maxLen / phraseLen, sequenceLen) * correctReward; // integer division
+      return Math.Min(maxLen / phraseLen, numPhrases) * correctReward; // integer division
     }
 
     public string BestKnownSolution {
-      get {
-        string solution = "";
-        for (int i = 0; i < sequenceLen; i++) {
-          solution += optimalPhrasesForPos[i].First();
-        }
-        return solution;
-      }
+      get { return string.Join("", optimalPhrases.Take(numPhrases)); }
     }
 
@@ -92 +103 @@
       // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
       Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      // as long as only correct symbols are found we increase the reward by +1
-      // on the first incorrect symbol we return
-      var reward = 0.0;
-      for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
-        if (optimalPhrasesForPos[i].Contains(sentence.Substring(i * phraseLen, phraseLen))) {
-          reward += correctReward;
-        } else {
-          // alternatively reduce reward by number of remaining phrases
-          return Math.Max(0.0, reward + incorrectReward * (sentence.Length / phraseLen - i));
-          // stop on first incorrect symbol and return reward
-          //return reward;
-        }
+
+
+      // split the sentence in phrases
+      // phrases must not overlap in the sentence, multiple occurences of a phrase are not counted
+      // the order of phrases is not relevant
+      var numPhrases = sentence.Length / phraseLen;
+      var phrases = new SortedSet<string>();
+      for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
+        var sentenceIdx = phraseIdx * phraseLen;
+        var phrase = sentence.Substring(sentenceIdx, phraseLen);
+        phrase = CanonicalPhrase(phrase);
+        if (!phrases.Contains(phrase)) phrases.Add(phrase);
       }
+
+      // add reward for each correct phrase that occurs in the sentence 
+      // add reward for each decoy phrase that occurs in the sentence
+      var reward = phrases.Intersect(optimalPhrases).Count() * correctReward
+               + phrases.Intersect(decoyPhrases).Count() * decoyReward;
+
+
+
       return reward;
     }
 
+    private string CanonicalPhrase(string phrase) {
+      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
+      else return phrase;
+    }
+
     public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+      // as the ordering of phrases does not matter we can reorder the phrases
+      // and remove duplicates
+      var numPhrases = terminalPhrase.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);
+      }
+      return string.Join("", phrases);
     }
   }