Changeset 12893 for branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs

Timestamp:

08/24/15 13:56:27 (9 years ago)

Author:

gkronber

Message:

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs (modified) (7 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs

@@ -4 +4 @@
 using System.Linq;
 using System.Text;
+using System.Text.RegularExpressions;
 using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Common;
+using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.GrammaticalOptimization;
 
@@ -18 +22 @@
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
+    public double[] OptimalPulls { get; private set; }
 
     public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
@@ -30 +35 @@
     private int[] actionIndexMap; // don't allocate each time
 
-    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+    public bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      //// only for debugging
+      //if (done.Count == 30000) {
+      //  foreach (var pair in stateInfo) {
+      //    var state = pair.Key;
+      //    var info = (DefaultPolicyActionInfo)pair.Value;
+      //    if (info.Tries > 0) {
+      //      Console.WriteLine("{0};{1};{2};{3};{4};{5}", state, info.Tries, info.Value, info.MaxReward,
+      //        optimalSolutions.Contains(problem.CanonicalRepresentation(state)) ? 1 : 0,
+      //        string.Join(";", GenerateFeaturesPoly10(state)));
+      //    }
+      //  }
+      //  System.Environment.Exit(1);
+      //}
+
       // fail if all states are done (corresponding state infos are disabled)
       if (afterStates.All(s => Done(s))) {
@@ -55 +74 @@
       }
 
-      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
-
+      //// select terminals first
+      //var terminalAfterstates = afterStates.Select((s, i) => new { s, i }).FirstOrDefault(t => !Done(t.s) && problem.Grammar.IsTerminal(t.s));
+      //if (terminalAfterstates != null) {
+      //  selectedStateIdx = terminalAfterstates.i;
+      //  return true;
+      //}
+
+      if (valueApproximation == null) {
+        // no approximation yet? --> use bandit
+        selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+      } else if (afterStates.Any(s => problem.Grammar.IsTerminal(s) && !Done(s))) {
+        selectedStateIdx = SelectionMaxValueTerminalAction(random, afterStates);
+      } else {
+        // only internal states? --> use bandit
+        selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+      }
       return true;
     }
 
+    private int SelectionMaxValueTerminalAction(System.Random random, IEnumerable<string> afterStates) {
+      int idx = 0;
+      var terminalStates = new List<string>();
+      var originalIdx = new List<int>();
+      foreach (var state in afterStates) {
+        if (problem.Grammar.IsTerminal(state) && !Done(state)) {
+          terminalStates.Add(state);
+          originalIdx.Add(idx);
+        }
+        idx++;
+      }
+
+      return originalIdx[SelectionMaxValueAction(random, terminalStates)];
+    }
+
+    private IRegressionSolution valueApproximation;
+    private int SelectionMaxValueAction(System.Random random, IEnumerable<string> afterStates) {
+
+      // eps greedy
+      //if (random.NextDouble() < 0.1) return Enumerable.Range(0, afterStates.Count()).SelectRandom(random);
+
+      Dataset ds;
+      string[] variablesNames;
+      CreateDataset(afterStates, afterStates.Select<string, IBanditPolicyActionInfo>(_ => null), out ds, out variablesNames);
+
+      var v = valueApproximation.Model.GetEstimatedValues(ds, Enumerable.Range(0, ds.Rows)).ToArray();
+
+      //boltzmann exploration
+      //double beta = 100;
+      //var w = v.Select(vi => Math.Exp(beta * vi));
+      //
+      //return Enumerable.Range(0, v.Length).SampleProportional(random, w);
+
+      return Enumerable.Range(0, v.Length).MaxItems(i => v[i]).SelectRandom(random);
+    }
+
+    private void UpdateValueApproximation() {
+      Dataset ds;
+      string[] variableNames;
+      CreateDataset(stateInfo.Keys, stateInfo.Values, out ds, out variableNames);
+      var problemData = new RegressionProblemData(ds, variableNames.Skip(1), variableNames.First());
+      //problemData.TestPartition.Start = problemData.TestPartition.End; // all data are training data
+      valueApproximation = GradientBoostedTreesAlgorithmStatic.TrainGbm(problemData, new SquaredErrorLoss(), 50, 0.1,
+        0.5, 0.5, 100);
+      Console.WriteLine(valueApproximation.TrainingRSquared);
+      Console.WriteLine(valueApproximation.TestRSquared);
+    }
+
+    private void CreateDataset(IEnumerable<string> states, IEnumerable<IBanditPolicyActionInfo> infos, out Dataset ds, out string[] variableNames) {
+      variableNames = new string[] { "maxValue" }.Concat(GenerateFeaturesPoly10("E").Select((_, i) => "f" + i)).ToArray();
+
+      int rows = infos.Zip(states, (info, state) => new { info, state }).Count(i => i.info == null || (i.info.Tries == 1 && Done(i.state)));
+      int cols = variableNames.Count();
+
+      var variableValues = new double[rows, cols];
+      int n = 0;
+      foreach (var pair in states.Zip(infos, Tuple.Create)) {
+        var state = pair.Item1;
+        var info = (DefaultPolicyActionInfo)pair.Item2;
+        if (info == null || (info.Tries == 1 && Done(state))) {
+          if (info != null) {
+            variableValues[n, 0] = info.MaxReward;
+          }
+          int col = 1;
+          foreach (var f in GenerateFeaturesPoly10(state)) {
+            variableValues[n, col++] = f;
+          }
+          n++;
+        }
+      }
+
+      ds = new Dataset(variableNames, variableValues);
+    }
 
 
@@ -72 +178 @@
     }
 
+    private int rewardUpdatesSinceLastTraining = 0;
+    private HashSet<string> statesWritten = new HashSet<string>();
     public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      rewardUpdatesSinceLastTraining++;
+      if (rewardUpdatesSinceLastTraining == 5000) {
+        rewardUpdatesSinceLastTraining = 0;
+        //// write
+        //foreach (var pair in stateInfo) {
+        //  var state = pair.Key;
+        //  var info = (DefaultPolicyActionInfo)pair.Value;
+        //  if (!statesWritten.Contains(state) && info.Tries > 0) {
+        //    Console.WriteLine("{0};{1};{2};{3};{4}", state, info.Tries, info.Value, info.MaxReward, string.Join(";", GenerateFeaturesPoly10(state)));
+        //    statesWritten.Add(state);
+        //  }
+        //}
+        //
+        //Console.WriteLine();
+        //UpdateValueApproximation();
+      }
+
+      int lvl = 0;
       foreach (var state in stateTrajectory) {
+        double alpha = 0.99;
+        OptimalPulls[lvl] = alpha * OptimalPulls[lvl] + (1 - alpha) * (problem.IsOptimalPhrase(state) ? 1.0 : 0.0);
+        lvl++;
+
         GetStateInfo(state).UpdateReward(reward);
-
+        //reward *= 0.95;
         // only the last state can be terminal
         if (problem.Grammar.IsTerminal(state)) {
@@ -83 +213 @@
     }
 
+    private IEnumerable<double> GenerateFeaturesPoly10(string state) {
+      // yield return problem.IsOptimalPhrase(state) ? 1 : 0;
+      foreach (var f in problem.GetFeatures(state)) yield return f.Value;
+
+      //if (!state.EndsWith("E")) state = state + "+E";
+      //int len = state.Length;
+      //Debug.Assert(state[len - 1] == 'E');
+      //foreach (var sy0 in new char[] { '+', '*' }) {
+      //  foreach (var sy1 in problem.Grammar.TerminalSymbols) {
+      //    foreach (var sy2 in new char[] { '+', '*' }) {
+      //      yield return state.Length > 3 && state[len - 4] == sy0 && state[len - 3] == sy1 && state[len - 2] == sy2 ? 1 : 0;
+      //    }
+      //  }
+      //}
+
+      //yield return state.Length;
+      //foreach (var terminalSy in problem.Grammar.TerminalSymbols) {
+      //  yield return state.Length > 2 && state[0] == terminalSy && state[1] == '+' ? 1 : 0;
+      //  yield return state.Length > 2 && state[0] == terminalSy && state[1] == '*' ? 1 : 0;
+      //}
+      // yield return optimalSolutions.Contains(problem.CanonicalRepresentation(state)) ? 1 : 0;
+      //foreach (var term in optimalTerms) yield return Regex.Matches(problem.CanonicalRepresentation(state), term).Count == 1 ? 1 : 0;
+      //var len = state.Length;
+      //yield return len;
+      //foreach (var t in problem.Grammar.TerminalSymbols) {
+      //  yield return state.Count(ch => ch == t);
+      //}
+      //// pairs
+      //foreach (var u in problem.Grammar.TerminalSymbols) {
+      //  foreach (var v in problem.Grammar.TerminalSymbols) {
+      //    int n = 0;
+      //    for (int i = 0; i < state.Length - 1; i++) {
+      //      if (state[i] == u && state[i + 1] == v) n++;
+      //    }
+      //    yield return n;
+      //  }
+      //}
+    }
+
 
     public void Reset() {
       stateInfo.Clear();
       done.Clear();
+      OptimalPulls = new double[300]; // max sentence length is limited anyway
     }
 
@@ -97 +267 @@
     public double GetValue(string state) {
       var s = CanonicalState(state);
-      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].MaxReward;
       else return 0.0; // TODO: check alternatives
     }