Changeset 11730 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization

Timestamp:

01/02/15 16:08:21 (9 years ago)

Author:

gkronber

Message:

#2283: several major extensions for grammatical optimization

Location:

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

Files:

• AlternativesContextSampler.cs (modified) (7 diffs)
• AlternativesSampler.cs (modified) (4 diffs)
• ExhaustiveBreadthFirstSearch.cs (modified) (3 diffs)
• ExhaustiveDepthFirstSearch.cs (modified) (2 diffs)
• MctsSampler.cs (modified) (7 diffs)
• RandomSearch.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs

@@ -17 +17 @@
     private readonly Random random;
     private readonly int contextLen;
+    private readonly Func<Random, int, IPolicy> policyFactory;
 
-    public AlternativesContextSampler(IProblem problem, int maxLen) {
+    public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, Func<Random, int, IPolicy> policyFactory) {
       this.maxLen = maxLen;
       this.problem = problem;
-      this.random = new Random(31415);
-      this.contextLen = 25;
+      this.random = random;
+      this.contextLen = contextLen;
+      this.policyFactory = policyFactory;
     }
 
@@ -29 +31 @@
       InitPolicies(problem.Grammar);
       for (int i = 0; i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         DistributeReward(quality);
 
@@ -45 +47 @@
     private Dictionary<string, IPolicy> ntPolicy;
     private List<Tuple<string, int>> updateChain;
+
     private void InitPolicies(IGrammar grammar) {
       this.ntPolicy = new Dictionary<string, IPolicy>();
@@ -50 +53 @@
     }
 
-    private string SampleSentence(IGrammar grammar) {
+    private Sequence SampleSentence(IGrammar grammar) {
       updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -67 +69 @@
 
         var alts = g.GetAlternatives(nt);
-        string selectedAlt;
+        Sequence selectedAlt;
         // if the choice is restricted then one of the allowed alternatives is selected randomly
         if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
@@ -76 +78 @@
         } else {
           // all alts are allowed => select using bandit policy
+          var ntIdx = phrase.FirstNonTerminalIndex;
           var startIdx = Math.Max(0, ntIdx - contextLen);
           var endIdx = Math.Min(startIdx + contextLen, ntIdx);
-          var lft = phrase.Substring(startIdx, endIdx - startIdx + 1);
+          var lft = phrase.Subsequence(startIdx, endIdx - startIdx + 1).ToString();
           lft = problem.Hash(lft);
           if (!ntPolicy.ContainsKey(lft)) {
-            ntPolicy.Add(lft, new UCB1TunedPolicy(g.GetAlternatives(nt).Count()));
+            ntPolicy.Add(lft, policyFactory(random, g.GetAlternatives(nt).Count()));
           }
           var selectedAltIdx = ntPolicy[lft].SelectAction();
@@ -89 +92 @@
 
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        done = phrase.IsTerminal; // terminal phrase means we are done
       }
       return phrase;

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs

@@ -27 +27 @@
       InitPolicies(problem.Grammar);
       for (int i = 0; i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         DistributeReward(quality);
 
@@ -52 +52 @@
     }
 
-    private string SampleSentence(IGrammar grammar) {
+    private Sequence SampleSentence(IGrammar grammar) {
       updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -69 +68 @@
 
         var alts = g.GetAlternatives(nt);
-        string selectedAlt;
+        Sequence selectedAlt;
         // if the choice is restricted then one of the allowed alternatives is selected randomly
         if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
@@ -84 +83 @@
 
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        done = phrase.IsTerminal; // terminal phrase means we are done
       }
       return phrase;

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs

@@ -11 +11 @@
 
     private readonly int maxLen;
-    private readonly Queue<string> bfsQueue = new Queue<string>();
+    private readonly Queue<Sequence> bfsQueue = new Queue<Sequence>();
     private readonly IProblem problem;
 
@@ -21 +21 @@
     public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      bfsQueue.Enqueue(problem.Grammar.SentenceSymbol.ToString());
+      bfsQueue.Enqueue(new Sequence(problem.Grammar.SentenceSymbol));
       var sentences = GenerateLanguage(problem.Grammar);
       var sentenceEnumerator = sentences.GetEnumerator();
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current;
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        var sentence = sentenceEnumerator.Current.ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -37 +37 @@
 
     // create sentences lazily
-    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
       while (bfsQueue.Any()) {
         var phrase = bfsQueue.Dequeue();
 
-        char nt;
+        char nt = phrase.FirstNonTerminal;
         int ntIdx;
-        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
+
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {
-          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
-          if (newPhrase.All(grammar.IsTerminal) && newPhrase.Length <= maxLen) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
             yield return newPhrase;
           } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs

@@ -11 +11 @@
 
     private readonly int maxLen;
-    private readonly Stack<string> stack = new Stack<string>();
+    private readonly Stack<Sequence> stack = new Stack<Sequence>();
+    private readonly IProblem problem;
 
-    public ExhaustiveDepthFirstSearch(int maxLen) {
+    public ExhaustiveDepthFirstSearch(IProblem problem, int maxLen) {
       this.maxLen = maxLen;
+      this.problem = problem;
     }
 
-    public void Run(IProblem problem, int maxIterations) {
+    public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      stack.Push(problem.Grammar.SentenceSymbol.ToString());
+      stack.Push(new Sequence(problem.Grammar.SentenceSymbol));
       var sentences = GenerateLanguage(problem.Grammar);
       var sentenceEnumerator = sentences.GetEnumerator();
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current;
+        var sentence = sentenceEnumerator.Current.ToString();
         var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
@@ -35 +37 @@
 
     // create sentences lazily
-    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
       while (stack.Any()) {
         var phrase = stack.Pop();
 
-        char nt;
-        int ntIdx;
-        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {
-          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
-          if (newPhrase.All(grammar.IsTerminal) && newPhrase.Length <= maxLen) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
             yield return newPhrase;
           } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs

@@ -10 +10 @@
   public class MctsSampler {
     private class TreeNode {
+      public string ident;
       public int randomTries;
+      public int policyTries;
       public IPolicy policy;
       public TreeNode[] children;
       public bool done = false;
 
+      public TreeNode(string id) {
+        this.ident = id;
+      }
+
       public override string ToString() {
-        return string.Format("Node(random-tries: {0}, done: {1}, policy: {2})", randomTries, done, policy);
+        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, randomTries + policyTries, done, policy);
       }
     }
+
 
     public event Action<string, double> FoundNewBestSolution;
@@ -27 +34 @@
     private readonly Random random;
     private readonly int randomTries;
-    private readonly Func<int, IPolicy> policyFactory;
+    private readonly Func<Random, int, IPolicy> policyFactory;
 
     private List<Tuple<TreeNode, int>> updateChain;
     private TreeNode rootNode;
 
+    public int treeDepth;
+    public int treeSize;
+
     public MctsSampler(IProblem problem, int maxLen, Random random) :
-      this(problem, maxLen, random, 10, (numActions) => new EpsGreedyPolicy(random, numActions, 0.1)) {
+      this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) {
 
     }
 
-    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<int, IPolicy> policyFactory) {
+    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<Random, int, IPolicy> policyFactory) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -47 +57 @@
     public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      InitPolicies();
+      InitPolicies(problem.Grammar);
       for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
+        var sentence = SampleSentence(problem.Grammar).ToString();
         var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         Debug.Assert(quality >= 0 && quality <= 1.0);
@@ -61 +71 @@
         }
       }
+
+      // clean up
+      InitPolicies(problem.Grammar); GC.Collect();
     }
 
-    private void InitPolicies() {
-      this.updateChain = new List<Tuple<TreeNode, int>>();
-      rootNode = new TreeNode();
+    public void PrintStats() {
+      var n = rootNode;
+      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries);
+      while (n.policy != null) {
+        Console.WriteLine();
+        Console.WriteLine("{0,5}->{1,-50}", n.ident, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.ident))));
+        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.randomTries + ch.policyTries))));
+        //n.policy.PrintStats();
+        n = n.children.OrderByDescending(c => c.policyTries).First();
+      }
+      Console.ReadLine();
     }
 
-    private string SampleSentence(IGrammar grammar) {
-      updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+    private void InitPolicies(IGrammar grammar) {
+      this.updateChain = new List<Tuple<TreeNode, int>>();
+
+      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
+      treeDepth = 0;
+      treeSize = 0;
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      var startPhrase = new Sequence(grammar.SentenceSymbol);
+      return CompleteSentence(grammar, startPhrase);
+    }
+
+    private Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
       TreeNode n = rootNode;
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal;
       int selectedAltIdx = -1;
+      var curDepth = 0;
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -90 +120 @@
         if (n.randomTries < randomTries) {
           n.randomTries++;
+
+          treeDepth = Math.Max(treeDepth, curDepth);
+
           return g.CompleteSentenceRandomly(random, phrase, maxLen);
         } else if (n.randomTries == randomTries && n.policy == null) {
-          n.policy = policyFactory(alts.Count());
-          n.children = alts.Select(_ => new TreeNode()).ToArray(); // create a new node for each alternative
+          n.policy = policyFactory(random, alts.Count());
+          //n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
+          n.children = alts.Select(alt => new TreeNode(string.Empty)).ToArray(); // create a new node for each alternative
+
+          treeSize += n.children.Length;
         }
-
+        n.policyTries++;
         // => select using bandit policy
         selectedAltIdx = n.policy.SelectAction();
-        string selectedAlt = alts.ElementAt(selectedAltIdx);
+        Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
+
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
         updateChain.Add(Tuple.Create(n, selectedAltIdx));
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        curDepth++;
+
+        done = phrase.IsTerminal;
         if (!done) {
           // prepare for next iteration
@@ -116 +154 @@
       n.children[selectedAltIdx].done = true;
 
+      treeDepth = Math.Max(treeDepth, curDepth);
       return phrase;
     }
@@ -127 +166 @@
         var policy = node.policy;
         var action = e.Item2;
+        //policy.UpdateReward(action, reward / updateChain.Count);
         policy.UpdateReward(action, reward);
 

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs

@@ -13 +13 @@
     private readonly int maxLen;
     private readonly Random random;
+    private readonly IProblem problem;
 
-    public RandomSearch(int maxLen) {
+    public RandomSearch(IProblem problem, Random random, int maxLen) {
       this.maxLen = maxLen;
-      this.random = new Random(31415);
+      this.random = random;
+      this.problem = problem;
     }
 
-    public void Run(IProblem problem, int maxIterations) {
+    public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
       for (int i = 0; i < maxIterations; i++) {
-        var sentence = CreateSentence(problem.Grammar);
-        var quality = problem.Evaluate(sentence);
+        var sentence = CreateSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -33 +35 @@
     }
 
-    private string CreateSentence(IGrammar grammar) {
-      var sentence = grammar.SentenceSymbol.ToString();
+    private Sequence CreateSentence(IGrammar grammar) {
+      var sentence = new Sequence(grammar.SentenceSymbol);
       return grammar.CompleteSentenceRandomly(random, sentence, maxLen);
     }