Changeset 12893 for branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies
- Timestamp:
- 08/24/15 13:56:27 (9 years ago)
- Location:
- branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs
r12027 r12893 32 32 private int[] actionIndexMap; // don't allocate each time 33 33 34 public bool TrySelect( Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {34 public bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) { 35 35 // fail if all states are done (corresponding state infos are disabled) 36 36 if (afterStates.All(s => Done(s))) { … … 60 60 originalIdx++; 61 61 } 62 63 62 63 64 64 // TODO: policy should be a parameter of the function approximation policy 65 65 if (random.NextDouble() < 0.2) { … … 74 74 bestIdxs.Add(i); 75 75 bestQ = activeAfterStates[i]; 76 } else if ( activeAfterStates[i].IsAlmost(bestQ)) {76 } else if (HeuristicLab.Common.Extensions.IsAlmost(activeAfterStates[i], bestQ)) { 77 77 bestIdxs.Add(i); 78 78 } … … 80 80 selectedStateIdx = actionIndexMap[bestIdxs[random.Next(bestIdxs.Count)]]; 81 81 } 82 82 83 83 return true; 84 84 } … … 133 133 //double alpha = 1.0 / GetFeatureTries(feature.Id); 134 134 //alpha = Math.Max(alpha, 0.001); 135 135 136 136 // simple setting of constant alpha = 0.01 works very well for poly-10 (100% success rate for 20 runs within 40000 evaluations)) 137 137 var alpha = 0.01; -
branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs
r12290 r12893 4 4 using System.Linq; 5 5 using System.Text; 6 using System.Text.RegularExpressions; 6 7 using System.Threading.Tasks; 8 using HeuristicLab.Algorithms.Bandits.BanditPolicies; 9 using HeuristicLab.Algorithms.DataAnalysis; 7 10 using HeuristicLab.Common; 11 using HeuristicLab.Problems.DataAnalysis; 8 12 using HeuristicLab.Problems.GrammaticalOptimization; 9 13 … … 18 22 private readonly IProblem problem; 19 23 private readonly IBanditPolicy banditPolicy; 24 public double[] OptimalPulls { get; private set; } 20 25 21 26 public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) { … … 30 35 private int[] actionIndexMap; // don't allocate each time 31 36 32 public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) { 37 public bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) { 38 //// only for debugging 39 //if (done.Count == 30000) { 40 // foreach (var pair in stateInfo) { 41 // var state = pair.Key; 42 // var info = (DefaultPolicyActionInfo)pair.Value; 43 // if (info.Tries > 0) { 44 // Console.WriteLine("{0};{1};{2};{3};{4};{5}", state, info.Tries, info.Value, info.MaxReward, 45 // optimalSolutions.Contains(problem.CanonicalRepresentation(state)) ? 1 : 0, 46 // string.Join(";", GenerateFeaturesPoly10(state))); 47 // } 48 // } 49 // System.Environment.Exit(1); 50 //} 51 33 52 // fail if all states are done (corresponding state infos are disabled) 34 53 if (afterStates.All(s => Done(s))) { … … 55 74 } 56 75 57 selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))]; 58 76 //// select terminals first 77 //var terminalAfterstates = afterStates.Select((s, i) => new { s, i }).FirstOrDefault(t => !Done(t.s) && problem.Grammar.IsTerminal(t.s)); 78 //if (terminalAfterstates != null) { 79 // selectedStateIdx = terminalAfterstates.i; 80 // return true; 81 //} 82 83 if (valueApproximation == null) { 84 // no approximation yet? --> use bandit 85 selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))]; 86 } else if (afterStates.Any(s => problem.Grammar.IsTerminal(s) && !Done(s))) { 87 selectedStateIdx = SelectionMaxValueTerminalAction(random, afterStates); 88 } else { 89 // only internal states? --> use bandit 90 selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))]; 91 } 59 92 return true; 60 93 } 61 94 95 private int SelectionMaxValueTerminalAction(System.Random random, IEnumerable<string> afterStates) { 96 int idx = 0; 97 var terminalStates = new List<string>(); 98 var originalIdx = new List<int>(); 99 foreach (var state in afterStates) { 100 if (problem.Grammar.IsTerminal(state) && !Done(state)) { 101 terminalStates.Add(state); 102 originalIdx.Add(idx); 103 } 104 idx++; 105 } 106 107 return originalIdx[SelectionMaxValueAction(random, terminalStates)]; 108 } 109 110 private IRegressionSolution valueApproximation; 111 private int SelectionMaxValueAction(System.Random random, IEnumerable<string> afterStates) { 112 113 // eps greedy 114 //if (random.NextDouble() < 0.1) return Enumerable.Range(0, afterStates.Count()).SelectRandom(random); 115 116 Dataset ds; 117 string[] variablesNames; 118 CreateDataset(afterStates, afterStates.Select<string, IBanditPolicyActionInfo>(_ => null), out ds, out variablesNames); 119 120 var v = valueApproximation.Model.GetEstimatedValues(ds, Enumerable.Range(0, ds.Rows)).ToArray(); 121 122 //boltzmann exploration 123 //double beta = 100; 124 //var w = v.Select(vi => Math.Exp(beta * vi)); 125 // 126 //return Enumerable.Range(0, v.Length).SampleProportional(random, w); 127 128 return Enumerable.Range(0, v.Length).MaxItems(i => v[i]).SelectRandom(random); 129 } 130 131 private void UpdateValueApproximation() { 132 Dataset ds; 133 string[] variableNames; 134 CreateDataset(stateInfo.Keys, stateInfo.Values, out ds, out variableNames); 135 var problemData = new RegressionProblemData(ds, variableNames.Skip(1), variableNames.First()); 136 //problemData.TestPartition.Start = problemData.TestPartition.End; // all data are training data 137 valueApproximation = GradientBoostedTreesAlgorithmStatic.TrainGbm(problemData, new SquaredErrorLoss(), 50, 0.1, 138 0.5, 0.5, 100); 139 Console.WriteLine(valueApproximation.TrainingRSquared); 140 Console.WriteLine(valueApproximation.TestRSquared); 141 } 142 143 private void CreateDataset(IEnumerable<string> states, IEnumerable<IBanditPolicyActionInfo> infos, out Dataset ds, out string[] variableNames) { 144 variableNames = new string[] { "maxValue" }.Concat(GenerateFeaturesPoly10("E").Select((_, i) => "f" + i)).ToArray(); 145 146 int rows = infos.Zip(states, (info, state) => new { info, state }).Count(i => i.info == null || (i.info.Tries == 1 && Done(i.state))); 147 int cols = variableNames.Count(); 148 149 var variableValues = new double[rows, cols]; 150 int n = 0; 151 foreach (var pair in states.Zip(infos, Tuple.Create)) { 152 var state = pair.Item1; 153 var info = (DefaultPolicyActionInfo)pair.Item2; 154 if (info == null || (info.Tries == 1 && Done(state))) { 155 if (info != null) { 156 variableValues[n, 0] = info.MaxReward; 157 } 158 int col = 1; 159 foreach (var f in GenerateFeaturesPoly10(state)) { 160 variableValues[n, col++] = f; 161 } 162 n++; 163 } 164 } 165 166 ds = new Dataset(variableNames, variableValues); 167 } 62 168 63 169 … … 72 178 } 73 179 180 private int rewardUpdatesSinceLastTraining = 0; 181 private HashSet<string> statesWritten = new HashSet<string>(); 74 182 public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) { 183 rewardUpdatesSinceLastTraining++; 184 if (rewardUpdatesSinceLastTraining == 5000) { 185 rewardUpdatesSinceLastTraining = 0; 186 //// write 187 //foreach (var pair in stateInfo) { 188 // var state = pair.Key; 189 // var info = (DefaultPolicyActionInfo)pair.Value; 190 // if (!statesWritten.Contains(state) && info.Tries > 0) { 191 // Console.WriteLine("{0};{1};{2};{3};{4}", state, info.Tries, info.Value, info.MaxReward, string.Join(";", GenerateFeaturesPoly10(state))); 192 // statesWritten.Add(state); 193 // } 194 //} 195 // 196 //Console.WriteLine(); 197 //UpdateValueApproximation(); 198 } 199 200 int lvl = 0; 75 201 foreach (var state in stateTrajectory) { 202 double alpha = 0.99; 203 OptimalPulls[lvl] = alpha * OptimalPulls[lvl] + (1 - alpha) * (problem.IsOptimalPhrase(state) ? 1.0 : 0.0); 204 lvl++; 205 76 206 GetStateInfo(state).UpdateReward(reward); 77 207 //reward *= 0.95; 78 208 // only the last state can be terminal 79 209 if (problem.Grammar.IsTerminal(state)) { … … 83 213 } 84 214 215 private IEnumerable<double> GenerateFeaturesPoly10(string state) { 216 // yield return problem.IsOptimalPhrase(state) ? 1 : 0; 217 foreach (var f in problem.GetFeatures(state)) yield return f.Value; 218 219 //if (!state.EndsWith("E")) state = state + "+E"; 220 //int len = state.Length; 221 //Debug.Assert(state[len - 1] == 'E'); 222 //foreach (var sy0 in new char[] { '+', '*' }) { 223 // foreach (var sy1 in problem.Grammar.TerminalSymbols) { 224 // foreach (var sy2 in new char[] { '+', '*' }) { 225 // yield return state.Length > 3 && state[len - 4] == sy0 && state[len - 3] == sy1 && state[len - 2] == sy2 ? 1 : 0; 226 // } 227 // } 228 //} 229 230 //yield return state.Length; 231 //foreach (var terminalSy in problem.Grammar.TerminalSymbols) { 232 // yield return state.Length > 2 && state[0] == terminalSy && state[1] == '+' ? 1 : 0; 233 // yield return state.Length > 2 && state[0] == terminalSy && state[1] == '*' ? 1 : 0; 234 //} 235 // yield return optimalSolutions.Contains(problem.CanonicalRepresentation(state)) ? 1 : 0; 236 //foreach (var term in optimalTerms) yield return Regex.Matches(problem.CanonicalRepresentation(state), term).Count == 1 ? 1 : 0; 237 //var len = state.Length; 238 //yield return len; 239 //foreach (var t in problem.Grammar.TerminalSymbols) { 240 // yield return state.Count(ch => ch == t); 241 //} 242 //// pairs 243 //foreach (var u in problem.Grammar.TerminalSymbols) { 244 // foreach (var v in problem.Grammar.TerminalSymbols) { 245 // int n = 0; 246 // for (int i = 0; i < state.Length - 1; i++) { 247 // if (state[i] == u && state[i + 1] == v) n++; 248 // } 249 // yield return n; 250 // } 251 //} 252 } 253 85 254 86 255 public void Reset() { 87 256 stateInfo.Clear(); 88 257 done.Clear(); 258 OptimalPulls = new double[300]; // max sentence length is limited anyway 89 259 } 90 260 … … 97 267 public double GetValue(string state) { 98 268 var s = CanonicalState(state); 99 if (stateInfo.ContainsKey(s)) return stateInfo[s]. Value;269 if (stateInfo.ContainsKey(s)) return stateInfo[s].MaxReward; 100 270 else return 0.0; // TODO: check alternatives 101 271 } -
branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs
r12298 r12893 28 28 private int[] actionIndexMap; // don't allocate each time 29 29 30 public bool TrySelect( Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {30 public bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) { 31 31 // fail if all states are done (corresponding state infos are disabled) 32 32 if (afterStates.All(s => Done(s))) { … … 101 101 102 102 103 private int SelectBoltzmann( Random random, IEnumerable<double> qs, double beta = 10) {103 private int SelectBoltzmann(System.Random random, IEnumerable<double> qs, double beta = 10) { 104 104 // select best 105 105 … … 122 122 } 123 123 124 private int SelectEpsGreedy( Random random, IEnumerable<double> qs, double eps = 0.2) {124 private int SelectEpsGreedy(System.Random random, IEnumerable<double> qs, double eps = 0.2) { 125 125 if (random.NextDouble() >= eps) { // eps == 0 should be equivalent to pure exploitation, eps == 1 is pure exploration 126 126 // select best … … 136 136 bestActions.Add(aIdx); 137 137 bestQ = q; 138 } else if ( q.IsAlmost(bestQ)) {138 } else if (HeuristicLab.Common.Extensions.IsAlmost(q,bestQ)) { 139 139 bestActions.Add(aIdx); 140 140 } … … 148 148 } 149 149 150 private int SelectRandom( Random random, IEnumerable<double> qs) {150 private int SelectRandom(System.Random random, IEnumerable<double> qs) { 151 151 return qs 152 152 .Select((aInfo, idx) => Tuple.Create(aInfo, idx)) -
branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GrammarPolicy.cs
r11793 r12893 24 24 } 25 25 26 public abstract bool TrySelect( Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx);26 public abstract bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx); 27 27 28 28 public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) { -
branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/RandomPolicy.cs
r11793 r12893 13 13 } 14 14 15 public override bool TrySelect( Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {15 public override bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) { 16 16 // never fail => allows re-visits of terminal states 17 17 selectedStateIdx = random.Next(afterStates.Count());
Note: See TracChangeset
for help on using the changeset viewer.