Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11832


Ignore:
Timestamp:
01/27/15 16:34:34 (8 years ago)
Author:
gkronber
Message:

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

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
3 added
27 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs

    r11747 r11832  
    99namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
    1010  public class BernoulliPolicyActionInfo : IBanditPolicyActionInfo {
    11     private double knownValue;
    12     public bool Disabled { get { return NumSuccess == -1; } }
    1311    public int NumSuccess { get; private set; }
    1412    public int NumFailure { get; private set; }
     
    1614    public double Value {
    1715      get {
    18         if (Disabled) return knownValue;
    19         else
    20           return NumSuccess / (double)(Tries);
     16        return NumSuccess / (double)(Tries);
    2117      }
    2218    }
    2319    public void UpdateReward(double reward) {
    24       Debug.Assert(!Disabled);
    2520      //Debug.Assert(reward.IsAlmost(0.0) || reward.IsAlmost(1.0));
    2621
     
    2924      else NumFailure++;
    3025    }
    31     public void Disable(double reward) {
    32       this.NumSuccess = -1;
    33       this.NumFailure = -1;
    34       this.knownValue = reward;
    35     }
    3626    public void Reset() {
    3727      NumSuccess = 0;
    3828      NumFailure = 0;
    39       knownValue = 0.0;
    4029    }
    4130    public void PrintStats() {
    42       Console.WriteLine("expected value {0,5:F2} disabled {1}", Value, Disabled);
     31      Console.WriteLine("expected value {0,5:F2}", Value);
    4332    }
    4433  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs

    r11742 r11832  
    2121      foreach (var aInfo in myActionInfos) {
    2222        aIdx++;
    23         if (aInfo.Disabled) continue;
    2423        var theta = Rand.BetaRand(random, aInfo.NumSuccess + alpha, aInfo.NumFailure + beta);
    2524        if (theta > maxTheta) {
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs

    r11806 r11832  
    1414    public double Value {
    1515      get {
    16           return Tries > 0 ? SumReward / Tries : 0.0;
     16        return Tries > 0 ? SumReward / Tries : 0.0;
    1717      }
    1818    }
    1919    public DefaultPolicyActionInfo() {
    20       MaxReward = double.MinValue;
     20      MaxReward = 0.0;
    2121    }
    2222
     
    3333    }
    3434
     35    public override string ToString() {
     36      return string.Format("{0:F3} {1:F3} {2}", Value, MaxReward, Tries);
     37    }
     38
    3539    public static Func<DefaultPolicyActionInfo, double> AverageReward {
    3640      get {
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs

    r11742 r11832  
    3131      foreach (var aInfo in myActionInfos) {
    3232        aIdx++;
    33         if (aInfo.Disabled) continue;
    3433
    3534        var tries = aInfo.Tries;
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs

    r11806 r11832  
    88namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
    99  public class MeanAndVariancePolicyActionInfo : IBanditPolicyActionInfo {
    10     private bool disabled;
    11     public bool Disabled { get { return disabled; } }
    1210    private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
    13     private double knownValue;
    1411    public int Tries { get { return estimator.N; } }
    1512    public double SumReward { get { return estimator.Sum; } }
     
    1815    public double Value {
    1916      get {
    20         if (disabled) return knownValue;
    21         else
    22           return AvgReward;
     17        return AvgReward;
    2318      }
    2419    }
    2520
    2621    public void UpdateReward(double reward) {
    27       Debug.Assert(!Disabled);
    2822      estimator.UpdateReward(reward);
    2923    }
    3024
    31     public void Disable(double reward) {
    32       disabled = true;
    33       this.knownValue = reward;
    34     }
    35 
    3625    public void Reset() {
    37       disabled = false;
    38       knownValue = 0.0;
    3926      estimator.Reset();
    4027    }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs

    r11806 r11832  
    1414      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
    1515
    16       int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
     16      int totalTries = myActionInfos.Sum(a => a.Tries);
    1717
    1818      int aIdx = -1;
     
    2121      foreach (var aInfo in myActionInfos) {
    2222        aIdx++;
    23         if (aInfo.Disabled) continue;
    2423        double q;
    2524        if (aInfo.Tries == 0) {
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs

    r11806 r11832  
    1212    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
    1313      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
    14       int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
     14      int totalTries = myActionInfos.Sum(a => a.Tries);
    1515      double bestQ = double.NegativeInfinity;
    1616      int aIdx = -1;
     
    1818      foreach (var aInfo in myActionInfos) {
    1919        aIdx++;
    20         if (aInfo.Disabled) continue;
    2120        double q;
    2221        if (totalTries <= 1 || aInfo.Tries <= 1 || aInfo.Tries <= Math.Ceiling(8 * Math.Log(totalTries))) {
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj

    r11806 r11832  
    6767    <Compile Include="Bandits\IBandit.cs" />
    6868    <Compile Include="Bandits\TruncatedNormalBandit.cs" />
     69    <Compile Include="GrammarPolicies\GenericFunctionApproximationGrammarPolicy.cs" />
     70    <Compile Include="GrammarPolicies\QLearningGrammarPolicy.cs" />
     71    <Compile Include="GrammarPolicies\GenericContextualGrammarPolicy.cs" />
    6972    <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
    7073    <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj

    r11732 r11832  
    3131  </PropertyGroup>
    3232  <ItemGroup>
     33    <Reference Include="ALGLIB-3.7.0, Version=3.7.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     34      <SpecificVersion>False</SpecificVersion>
     35      <HintPath>..\..\..\trunk\sources\bin\ALGLIB-3.7.0.dll</HintPath>
     36    </Reference>
     37    <Reference Include="AutoDiff-1.0">
     38      <HintPath>..\..\..\trunk\sources\bin\AutoDiff-1.0.dll</HintPath>
     39    </Reference>
    3340    <Reference Include="HeuristicLab.Common-3.3">
    3441      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

    r11806 r11832  
    55using System.Security.AccessControl;
    66using System.Text;
     7using AutoDiff;
    78using HeuristicLab.Common;
    89using HeuristicLab.Problems.DataAnalysis;
     
    1314  // provides bridge to HL regression problem instances
    1415  public class SymbolicRegressionProblem : IProblem {
     16
    1517    private const string grammarString = @"
    1618        G(E):
    17         E -> V | V+E | V-E | V*E | V/E | (E)
     19        E -> V | V+E | V-E | V*E | V/E | (E) | C | C+E | C-E | C*E | C/E
     20        C -> 0..9
    1821        V -> <variables>
    1922        ";
    20 
     23    // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
    2124
    2225    private readonly IGrammar grammar;
    23     private readonly ExpressionInterpreter interpreter;
    2426
    2527    private readonly int N;
     
    2729    private readonly double[] y;
    2830    private readonly int d;
    29 
    30 
    31     public SymbolicRegressionProblem(string partOfName) {
     31    private readonly double[] erc;
     32
     33
     34    public SymbolicRegressionProblem(Random random, string partOfName) {
    3235      var instanceProvider = new RegressionRealWorldInstanceProvider();
    3336      var dds = instanceProvider.GetDataDescriptors().OfType<RegressionDataDescriptor>();
     
    5053        i++;
    5154      }
     55      // initialize ERC values
     56      erc = Enumerable.Range(0, 10).Select(_ => Rand.RandNormal(random) * 10).ToArray();
    5257
    5358      char firstVar = 'a';
    5459      char lastVar = Convert.ToChar(Convert.ToByte('a') + d - 1);
    5560      this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
    56       this.interpreter = new ExpressionInterpreter();
    57 
    5861    }
    5962
     
    6972
    7073    public double Evaluate(string sentence) {
    71       return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])));
    72     }
    73 
    74 
    75     // right now only + and * is supported
    76     public string CanonicalRepresentation(string terminalPhrase) {
    77       //return terminalPhrase;
    78       var terms = terminalPhrase.Split('+');
    79       return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
    80         .OrderBy(term => term));
    81     }
     74      var interpreter = new ExpressionInterpreter();
     75      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)));
     76    }
     77
     78
     79    public string CanonicalRepresentation(string phrase) {
     80      return phrase;
     81      //var terms = phrase.Split('+');
     82      //return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
     83      //  .OrderBy(term => term));
     84    }
     85
     86    public IEnumerable<Feature> GetFeatures(string phrase)
     87    {
     88      throw new NotImplementedException();
     89    }
     90
     91
     92    /*
     93    public static double OptimizeConstants(string sentence) {
     94
     95      List<AutoDiff.Variable> variables = new List<AutoDiff.Variable>();
     96      List<AutoDiff.Variable> parameters = new List<AutoDiff.Variable>();
     97      List<string> variableNames = new List<string>();
     98
     99      AutoDiff.Term func;
     100      if (!TryTransformToAutoDiff(sentence, 0, variables, parameters, out func))
     101        throw new NotSupportedException("Could not optimize constants of symbolic expression tree due to not supported symbols used in the tree.");
     102      if (variableNames.Count == 0) return 0.0;
     103
     104      AutoDiff.IParametricCompiledTerm compiledFunc = AutoDiff.TermUtils.Compile(func, variables.ToArray(), parameters.ToArray());
     105
     106      List<SymbolicExpressionTreeTerminalNode> terminalNodes = tree.Root.IterateNodesPrefix().OfType<SymbolicExpressionTreeTerminalNode>().ToList();
     107      double[] c = new double[variables.Count];
     108
     109      {
     110        c[0] = 0.0;
     111        c[1] = 1.0;
     112        //extract inital constants
     113        int i = 2;
     114        foreach (var node in terminalNodes) {
     115          ConstantTreeNode constantTreeNode = node as ConstantTreeNode;
     116          VariableTreeNode variableTreeNode = node as VariableTreeNode;
     117          if (constantTreeNode != null)
     118            c[i++] = constantTreeNode.Value;
     119          else if (variableTreeNode != null)
     120            c[i++] = variableTreeNode.Weight;
     121        }
     122      }
     123      double[] originalConstants = (double[])c.Clone();
     124      double originalQuality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(interpreter, tree, lowerEstimationLimit, upperEstimationLimit, problemData, rows, applyLinearScaling);
     125
     126      alglib.lsfitstate state;
     127      alglib.lsfitreport rep;
     128      int info;
     129
     130      Dataset ds = problemData.Dataset;
     131      double[,] x = new double[rows.Count(), variableNames.Count];
     132      int row = 0;
     133      foreach (var r in rows) {
     134        for (int col = 0; col < variableNames.Count; col++) {
     135          x[row, col] = ds.GetDoubleValue(variableNames[col], r);
     136        }
     137        row++;
     138      }
     139      double[] y = ds.GetDoubleValues(problemData.TargetVariable, rows).ToArray();
     140      int n = x.GetLength(0);
     141      int m = x.GetLength(1);
     142      int k = c.Length;
     143
     144      alglib.ndimensional_pfunc function_cx_1_func = CreatePFunc(compiledFunc);
     145      alglib.ndimensional_pgrad function_cx_1_grad = CreatePGrad(compiledFunc);
     146
     147      try {
     148        alglib.lsfitcreatefg(x, y, c, n, m, k, false, out state);
     149        alglib.lsfitsetcond(state, 0.0, 0.0, maxIterations);
     150        //alglib.lsfitsetgradientcheck(state, 0.001);
     151        alglib.lsfitfit(state, function_cx_1_func, function_cx_1_grad, null, null);
     152        alglib.lsfitresults(state, out info, out c, out rep);
     153      } catch (ArithmeticException) {
     154        return originalQuality;
     155      } catch (alglib.alglibexception) {
     156        return originalQuality;
     157      }
     158
     159      //info == -7  => constant optimization failed due to wrong gradient
     160      if (info != -7) throw new ArgumentException();
     161    }
     162
     163
     164    private static alglib.ndimensional_pfunc CreatePFunc(AutoDiff.IParametricCompiledTerm compiledFunc) {
     165      return (double[] c, double[] x, ref double func, object o) => {
     166        func = compiledFunc.Evaluate(c, x);
     167      };
     168    }
     169
     170    private static alglib.ndimensional_pgrad CreatePGrad(AutoDiff.IParametricCompiledTerm compiledFunc) {
     171      return (double[] c, double[] x, ref double func, double[] grad, object o) => {
     172        var tupel = compiledFunc.Differentiate(c, x);
     173        func = tupel.Item2;
     174        Array.Copy(tupel.Item1, grad, grad.Length);
     175      };
     176    }
     177
     178    private static bool TryTransformToAutoDiff(string phrase, int symbolPos, List<AutoDiff.Variable> variables, List<AutoDiff.Variable> parameters, out AutoDiff.Term term)
     179    {
     180      var curSy = phrase[0];
     181      if () {
     182        var var = new AutoDiff.Variable();
     183        variables.Add(var);
     184        term = var;
     185        return true;
     186      }
     187      if (node.Symbol is Variable) {
     188        var varNode = node as VariableTreeNode;
     189        var par = new AutoDiff.Variable();
     190        parameters.Add(par);
     191        variableNames.Add(varNode.VariableName);
     192        var w = new AutoDiff.Variable();
     193        variables.Add(w);
     194        term = AutoDiff.TermBuilder.Product(w, par);
     195        return true;
     196      }
     197      if (node.Symbol is Addition) {
     198        List<AutoDiff.Term> terms = new List<Term>();
     199        foreach (var subTree in node.Subtrees) {
     200          AutoDiff.Term t;
     201          if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out t)) {
     202            term = null;
     203            return false;
     204          }
     205          terms.Add(t);
     206        }
     207        term = AutoDiff.TermBuilder.Sum(terms);
     208        return true;
     209      }
     210      if (node.Symbol is Subtraction) {
     211        List<AutoDiff.Term> terms = new List<Term>();
     212        for (int i = 0; i < node.SubtreeCount; i++) {
     213          AutoDiff.Term t;
     214          if (!TryTransformToAutoDiff(node.GetSubtree(i), variables, parameters, variableNames, out t)) {
     215            term = null;
     216            return false;
     217          }
     218          if (i > 0) t = -t;
     219          terms.Add(t);
     220        }
     221        term = AutoDiff.TermBuilder.Sum(terms);
     222        return true;
     223      }
     224      if (node.Symbol is Multiplication) {
     225        AutoDiff.Term a, b;
     226        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
     227          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
     228          term = null;
     229          return false;
     230        } else {
     231          List<AutoDiff.Term> factors = new List<Term>();
     232          foreach (var subTree in node.Subtrees.Skip(2)) {
     233            AutoDiff.Term f;
     234            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
     235              term = null;
     236              return false;
     237            }
     238            factors.Add(f);
     239          }
     240          term = AutoDiff.TermBuilder.Product(a, b, factors.ToArray());
     241          return true;
     242        }
     243      }
     244      if (node.Symbol is Division) {
     245        // only works for at least two subtrees
     246        AutoDiff.Term a, b;
     247        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
     248          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
     249          term = null;
     250          return false;
     251        } else {
     252          List<AutoDiff.Term> factors = new List<Term>();
     253          foreach (var subTree in node.Subtrees.Skip(2)) {
     254            AutoDiff.Term f;
     255            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
     256              term = null;
     257              return false;
     258            }
     259            factors.Add(1.0 / f);
     260          }
     261          term = AutoDiff.TermBuilder.Product(a, 1.0 / b, factors.ToArray());
     262          return true;
     263        }
     264      }
     265     
     266      if (node.Symbol is StartSymbol) {
     267        var alpha = new AutoDiff.Variable();
     268        var beta = new AutoDiff.Variable();
     269        variables.Add(beta);
     270        variables.Add(alpha);
     271        AutoDiff.Term branchTerm;
     272        if (TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out branchTerm)) {
     273          term = branchTerm * alpha + beta;
     274          return true;
     275        } else {
     276          term = null;
     277          return false;
     278        }
     279      }
     280      term = null;
     281      return false;
     282    }
     283     */
    82284  }
    83285}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSymbRegInstances.cs

    r11732 r11832  
    1212    public void TestGetDataDescriptors() {
    1313
    14       var problem = new SymbolicRegressionProblem("Tower");
     14      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
    1515
    1616    }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

    r11803 r11832  
    4343  </ItemGroup>
    4444  <ItemGroup>
     45    <Compile Include="Feature.cs" />
     46    <Compile Include="Problems\KryptosProblem.cs" />
    4547    <Compile Include="Problems\EvenParityProblem.cs" />
    4648    <Compile Include="Problems\ExpressionInterpreter.cs" />
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs

    r11806 r11832  
    99    IGrammar Grammar { get; }
    1010    double Evaluate(string sentence);
    11     string CanonicalRepresentation(string terminalPhrase); // canonical state must use correct syntax (must be a valid input for evaluate)
     11    string CanonicalRepresentation(string phrase); // canonical state must use correct syntax (must be a valid input for evaluate)
     12    IEnumerable<Feature> GetFeatures(string phrase);
    1213  }
    1314}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs

    r11803 r11832  
    5050    }
    5151
    52     public string CanonicalRepresentation(string terminalPhrase) {
     52    public string CanonicalRepresentation(string phrase) {
    5353      throw new NotImplementedException();
    54       return terminalPhrase;
     54      return phrase;
     55    }
     56
     57    public IEnumerable<Feature> GetFeatures(string phrase)
     58    {
     59      throw new NotImplementedException();
    5560    }
    5661  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs

    r11803 r11832  
    33using System.Diagnostics.Eventing.Reader;
    44using System.Linq;
     5using System.Runtime.CompilerServices;
    56using System.Runtime.Remoting.Messaging;
    67using System.Text;
     
    1011namespace HeuristicLab.Problems.GrammaticalOptimization {
    1112  public class ExpressionInterpreter {
     13    private static readonly double[] emptyErc = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
     14
    1215    private string sentence;
    1316    private int syIdx;
     
    1518    // Expr -> Term { ('+' | '-' | '^' ) Term }
    1619    // Term -> Fact { ('*' | '/') Fact }
    17     // Fact -> '!' Expr | '(' Expr ')' | Var
     20    // Fact -> '!' Expr | '(' Expr ')' | Var | const
    1821    // Var -> 'a'..'z'
     22    // const -> '0' .. '9'
     23
     24    // constants are Koza-style ephemeral random constants (ERC). for now we only allow up to 10 constants.
     25    // The constant symbols '0' .. '9' are treated as ERC indices
    1926
    2027    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
    2128
    2229    public bool Interpret(string sentence, bool[] vars) {
     30      return Interpret(sentence, vars, emptyErc);
     31    }
     32
     33    public bool Interpret(string sentence, bool[] vars, double[] erc) {
    2334      InitLex(sentence);
    2435      var d = new double[vars.Length];
    2536      for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
    26       return !(Expr(d).IsAlmost(0));
     37      return !(Expr(d, erc).IsAlmost(0));
    2738    }
    2839
    2940    public double Interpret(string sentence, double[] vars) {
     41      return Interpret(sentence, vars, emptyErc);
     42    }
     43
     44    public double Interpret(string sentence, double[] vars, double[] erc) {
    3045      InitLex(sentence);
    31       return Expr(vars);
     46      return Expr(vars, erc);
    3247    }
    3348
     
    5166    }
    5267
    53     private double Expr(double[] d) {
     68    private double Expr(double[] d, double[] erc) {
    5469      var r = 0.0;
    55       r = Term(d);
     70      r = Term(d, erc);
    5671      var curSy = CurSy();
    5772      while (curSy == '+' || curSy == '-' || curSy == '^') {
    5873        if (curSy == '+') {
    5974          NewSy();
    60           r += Expr(d);
     75          r += Expr(d, erc);
    6176        } else if (curSy == '-') {
    6277          NewSy();
    63           r -= Expr(d);
     78          r -= Expr(d, erc);
    6479        } else {
    6580          NewSy();
    66           var e = Expr(d);
     81          var e = Expr(d, erc);
    6782          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
    6883        }
     
    7287    }
    7388
    74     private double Term(double[] d) {
     89    private double Term(double[] d, double[] erc) {
    7590      var r = 0.0;
    76       r = Fact(d);
     91      r = Fact(d, erc);
    7792      var curSy = CurSy();
    7893      while (curSy == '*' || curSy == '/') {
    7994        if (curSy == '*') {
    8095          NewSy();
    81           r *= Term(d);
     96          r *= Term(d, erc);
    8297        } else {
    8398          NewSy();
    84           r /= Term(d);
     99          r /= Term(d, erc);
    85100        }
    86101        curSy = CurSy();
     
    89104    }
    90105
    91     private double Fact(double[] d) {
     106    private double Fact(double[] d, double[] erc) {
    92107      double r = 0.0;
    93108      var curSy = CurSy();
    94109      if (curSy == '!') {
    95110        NewSy();
    96         r = Not(Expr(d));
     111        r = Not(Expr(d, erc));
    97112      } else if (curSy == '(') {
    98113        NewSy();
    99         r = Expr(d);
     114        r = Expr(d, erc);
    100115        if (CurSy() != ')') throw new ArgumentException();
    101116        NewSy();
    102       } else /* if (curSy >= 'a' && curSy <= 'z') */ {
     117      } else if (curSy >= 'a' && curSy <= 'z') {
    103118        int o = (byte)curSy - (byte)'a';
    104119        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
    105120        if (o < 0 || o >= d.Length) throw new ArgumentException();
    106121        r = d[o];
     122        NewSy();
     123      } else /* if (curSy >= '0' && curSy <= '9') */ {
     124        int o = (byte)curSy - (byte)'0';
     125        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
     126        if (o < 0 || o >= 10) throw new ArgumentException();
     127        r = erc[o];
    107128        NewSy();
    108129      }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs

    r11803 r11832  
    129129    }
    130130
    131     public string CanonicalRepresentation(string terminalPhrase) {
     131    public string CanonicalRepresentation(string phrase) {
    132132      // as the ordering of phrases does not matter we can reorder the phrases
    133133      // and remove duplicates
    134       var numPhrases = terminalPhrase.Length / phraseLen;
     134      var numPhrases = phrase.Length / phraseLen;
    135135      var phrases = new SortedSet<string>();
    136136      for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
    137137        var sentenceIdx = phraseIdx * phraseLen;
    138         var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
    139         phrase = CanonicalPhrase(phrase);
    140         if (!phrases.Contains(phrase)) phrases.Add(phrase);
     138        var subphrase = phrase.Substring(sentenceIdx, phraseLen);
     139        subphrase = CanonicalPhrase(subphrase);
     140        if (!phrases.Contains(subphrase)) phrases.Add(subphrase);
    141141      }
    142       var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
     142      var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
    143143      remainder = CanonicalPhrase(remainder);
    144144      if (!phrases.Contains(remainder)) phrases.Add(remainder);
     
    146146      return string.Join("", phrases);
    147147    }
     148
     149    public IEnumerable<Feature> GetFeatures(string phrase)
     150    {
     151      throw new NotImplementedException();
     152    }
     153
     154    public override string ToString() {
     155      return string.Format("\"FindPhrasesProblem {0} {1} {2} {3:F2} {4} {5:F2} {6}\"", numPhrases, phraseLen,
     156        optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets);
     157    }
    148158  }
    149159}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs

    r11803 r11832  
    3939    }
    4040
    41     public string CanonicalRepresentation(string terminalPhrase) {
    42       return terminalPhrase;
     41    public string CanonicalRepresentation(string phrase) {
     42      return phrase;
     43    }
     44
     45    public IEnumerable<Feature> GetFeatures(string phrase)
     46    {
     47      throw new NotImplementedException();
    4348    }
    4449  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs

    r11803 r11832  
    8080    }
    8181
    82     public string CanonicalRepresentation(string terminalPhrase) {
    83       return terminalPhrase;
     82    public string CanonicalRepresentation(string phrase) {
     83      return phrase;
     84    }
     85
     86    public IEnumerable<Feature> GetFeatures(string phrase)
     87    {
     88      throw new NotImplementedException();
    8489    }
    8590  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs

    r11803 r11832  
    3535    }
    3636
    37     public string CanonicalRepresentation(string terminalPhrase) {
     37    public string CanonicalRepresentation(string phrase) {
     38      //throw new NotImplementedException();
     39      return phrase;
     40    }
     41
     42    public IEnumerable<Feature> GetFeatures(string phrase)
     43    {
    3844      throw new NotImplementedException();
    39       return terminalPhrase;
    4045    }
    4146  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

    r11806 r11832  
    113113    }
    114114
    115     public string CanonicalRepresentation(string terminalPhrase) {
     115    public string CanonicalRepresentation(string phrase) {
    116116      if (phrasesAsSets) {
    117117        var sb = new StringBuilder();
    118         var numPhrases = terminalPhrase.Length / phraseLen;
     118        var numPhrases = phrase.Length / phraseLen;
    119119        for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
    120120          var sentenceIdx = phraseIdx * phraseLen;
    121           var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
    122           phrase = CanonicalPhrase(phrase);
    123           sb.Append(phrase);
     121          var subphrase = phrase.Substring(sentenceIdx, phraseLen);
     122          subphrase = CanonicalPhrase(subphrase);
     123          sb.Append(subphrase);
    124124        }
    125125
    126         var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
     126        var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
    127127        remainder = CanonicalPhrase(remainder);
    128128        sb.Append(remainder);
     
    130130        return sb.ToString();
    131131      } else
    132         return terminalPhrase;
     132        return phrase;
     133    }
     134
     135    public IEnumerable<Feature> GetFeatures(string phrase)
     136    {
     137      throw new NotImplementedException();
    133138    }
    134139  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs

    r11803 r11832  
    2929      throw new NotImplementedException();
    3030    }
    31     public string CanonicalRepresentation(string terminalPhrase) {
    32       return terminalPhrase;
     31    public string CanonicalRepresentation(string phrase) {
     32      return phrase;
    3333    }
    3434
     35    public IEnumerable<Feature> GetFeatures(string phrase)
     36    {
     37      throw new NotImplementedException();
     38    }
    3539  }
    3640}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs

    r11803 r11832  
    7777
    7878    // in each position there could be multiple correct and incorrect symbols
    79     public string CanonicalRepresentation(string terminalPhrase) {
     79    public string CanonicalRepresentation(string phrase) {
    8080      var sb = new StringBuilder();
    81       for (int i = 0; i < terminalPhrase.Length; i++) {
    82         if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
     81      for (int i = 0; i < phrase.Length; i++) {
     82        if (optimalSymbolsForPos[i].Contains(phrase[i])) {
    8383          sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
    8484        } else {
    85           sb.Append(terminalPhrase[i]);
     85          sb.Append(phrase[i]);
    8686        }
    8787      }
    8888      return sb.ToString();
    8989    }
     90
     91    public IEnumerable<Feature> GetFeatures(string phrase)
     92    {
     93      throw new NotImplementedException();
     94    }
    9095  }
    9196}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs

    r11806 r11832  
    3434      return regex.Matches(sentence).Count;
    3535    }
    36     public string CanonicalRepresentation(string terminalPhrase) {
     36    public string CanonicalRepresentation(string phrase) {
    3737      throw new NotImplementedException();
    38       return terminalPhrase;
     38      return phrase;
    3939    }
    4040
     41    public IEnumerable<Feature> GetFeatures(string phrase)
     42    {
     43      throw new NotImplementedException();
     44    }
    4145  }
    4246}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

    r11803 r11832  
    2929      throw new NotImplementedException();
    3030    }
    31     public string CanonicalRepresentation(string terminalPhrase) {
     31    public string CanonicalRepresentation(string phrase) {
    3232      throw new NotImplementedException();
    33       return terminalPhrase;
     33      return phrase;
    3434    }
    3535
     36    public IEnumerable<Feature> GetFeatures(string phrase)
     37    {
     38      throw new NotImplementedException();
     39    }
    3640  }
    3741}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs

    r11806 r11832  
    102102    }
    103103
    104     public string CanonicalRepresentation(string terminalPhrase) {
    105       var sb = new StringBuilder(terminalPhrase);
    106       string canonicalPhrase = terminalPhrase;
     104    public string CanonicalRepresentation(string phrase) {
     105      var sb = new StringBuilder(phrase);
     106      string canonicalPhrase = phrase;
    107107      string oldPhrase;
    108108      do {
     
    112112      } while (canonicalPhrase != oldPhrase);
    113113      return sb.ToString();
     114    }
     115
     116    public IEnumerable<Feature> GetFeatures(string phrase) {
     117      return Enumerable.Repeat(new Feature(CanonicalRepresentation(phrase), 1.0), 1);
    114118    }
    115119  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs

    r11806 r11832  
    120120      return canonicalTerm;
    121121    }
     122
     123    // splits the phrase into terms and creates (sparse) term-occurrance features
     124    public IEnumerable<Feature> GetFeatures(string phrase) {
     125      var canonicalTerms = new HashSet<string>();
     126      foreach (string t in phrase.Split('+')) {
     127        canonicalTerms.Add(CanonicalTerm(t));
     128      }
     129      return canonicalTerms.Select(entry => new Feature(entry, 1.0)).Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
     130    }
     131
    122132  }
    123133}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

    r11806 r11832  
    2424      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
    2525
    26       RunDemo();
    27       //RunGridTest();
     26      //RunDemo();
     27      RunGridTest();
    2828    }
    2929
    3030    private static void RunGridTest() {
    31       int maxIterations = 50000; // for poly-10 with 50000 evaluations no successful try with hl yet
     31      int maxIterations = 70000; // for poly-10 with 50000 evaluations no successful try with hl yet
    3232      //var globalRandom = new Random(31415);
    3333      var localRandSeed = 31415;
    34       var reps = 10;
     34      var reps = 30;
    3535
    3636      var policyFactories = new Func<IBanditPolicy>[]
     
    109109      {
    110110        //(rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
    111         (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
    112         (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
    113         (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
    114         (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
    115         //(rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
     111        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
     112        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
     113        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
     114        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
     115        (rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
    116116      };
    117117
    118118      foreach (var instanceFactory in instanceFactories) {
    119         foreach (var useCanonical in new bool[] { true /*, false */ }) {
    120           foreach (var randomTries in new int[] { 0, /* 1, 10, /* 5, 100 /*, 500, 1000 */}) {
     119        foreach (var useCanonical in new bool[] { true /*, false */}) {
     120          foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
    121121            foreach (var policyFactory in policyFactories) {
    122122              var myRandomTries = randomTries;
     
    142142                var problem = instance.Item1;
    143143                var maxLen = instance.Item2;
    144                 var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
    145                   new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
     144                //var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
     145                //  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
     146                var alg = new SequentialSearch(problem, maxLen, myLocalRand,
     147                  myRandomTries,
     148                  new GenericFunctionApproximationGrammarPolicy(problem,
     149                    useCanonical));
    146150                //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
    147151                //var alg = new AlternativesContextSampler(problem, 25);
     
    150154                  iterations++;
    151155                  globalStatistics.AddSentence(sentence, quality);
    152                   if (iterations % 10000 == 0) {
    153                     Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4}", i, myRandomTries, policyFactory(), useCanonical, globalStatistics);
     156                  if (iterations % 1000 == 0) {
     157                    Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4} {5}", i, myRandomTries, policyFactory(), useCanonical, problem.ToString(), globalStatistics);
    154158                  }
    155159                };
     
    190194
    191195
    192       int maxIterations = 100000;
     196      int maxIterations = 1000000;
    193197      int iterations = 0;
    194198      var sw = new Stopwatch();
     
    199203
    200204      //var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
     205      // var phraseLen = 3;
     206      // var numPhrases = 5;
     207      // var problem = new RoyalPhraseSequenceProblem(random, 10, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: false);
     208
    201209      //var phraseLen = 3;
    202210      //var numPhrases = 5;
    203       //var problem = new RoyalPhraseSequenceProblem(random, 15, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: true);
    204 
    205       // var phraseLen = 3;
    206       // var numPhrases = 5;
    207       // var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 200, correctReward: 1.0, decoyReward: 0.5, phrasesAsSets: true);
     211      //var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 0, correctReward: 1.0, decoyReward: 0, phrasesAsSets: false);
    208212
    209213      // good results for symb-reg
     
    213217      // - GenericThompsonSamplingPolicy("")
    214218      // - UCTPolicy(0.10) (5 of 5 runs, 35000 iters avg.), 10 successful runs of 10 with rand-tries 0, bei 40000 iters 9 / 10, bei 30000 1 / 10
     219      // 2015 01 22: symb-reg: grid test on find-phrases problem showed good results for UCB1TunedPolicy and SequentialSearch with canonical states
     220      // - symb-reg: consistent results with UCB1Tuned. finds optimal solution in ~50k iters (new GenericGrammarPolicy(problem, new UCB1TunedPolicy(), true));
     221      // 2015 01 23: grid test with canonical states:
     222      // - UCTPolicy(0.10) und UCBNormalPolicy 10/10 optimale Lösungen bei max. 50k iters, etwas schlechter: generic-thompson with variable sigma und bolzmannexploration (100)
     223
    215224
    216225      // good results for artificial ant:
     
    219228      // - GaussianModelWithUnknownVariance (and Q= 0.99-quantil) also works well for Ant
    220229      // 2015 01 19: grid test with canonical states (non-canonical slightly worse)
    221       // - Threshold Ascent (best 100, 0.01; all variants relatively good)
    222       // - Policies where the variance has a large weight compared to the mean? (Gaussian(compatible), Gaussian with fixed variance, UCT with large c, alle TA)
    223 
    224       //var problem = new SymbolicRegressionPoly10Problem();
    225 
    226       var problem = new SantaFeAntProblem();
    227       //var problem = new SymbolicRegressionProblem("Tower");
     230      // - ant: Threshold Ascent (best 100, 0.01; all variants relatively good)
     231      // - ant: Policies where the variance has a large weight compared to the mean? (Gaussian(compatible), Gaussian with fixed variance, UCT with large c, alle TA)
     232      // - ant: UCB1Tuned with canonical states also works very well for the artificial ant! constistent solutions in less than 10k iters     
     233
     234      var problem = new SymbolicRegressionPoly10Problem();
     235      //var problem = new SantaFeAntProblem();
     236      //var problem = new SymbolicRegressionProblem(random, "Tower");
    228237      //var problem = new PalindromeProblem();
    229238      //var problem = new HardPalindromeProblem();
     
    234243      //var alg = new MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
    235244      //var alg = new SequentialSearch(problem, 23, random, 0,
    236       //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new ModifiedUCTPolicy(0.1), true));
    237       var alg = new SequentialSearch(problem, 17, random, 0,
    238         new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericTDPolicy(problem, true));
     245      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.QLearningGrammarPolicy(problem, new BoltzmannExplorationPolicy(10),
     246      //    1, 1, true));
     247      //var alg = new SequentialSearch(problem, 23, random, 0,
     248      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericContextualGrammarPolicy(problem, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), true));
     249      var alg = new SequentialSearch(problem, 23, random, 0,
     250        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericFunctionApproximationGrammarPolicy(problem, true));
    239251      //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
    240252      //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
     
    249261
    250262      alg.FoundNewBestSolution += (sentence, quality) => {
    251         //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
     263        //Console.WriteLine("{0}", globalStatistics);
    252264        //Console.ReadLine();
    253265      };
     
    255267        iterations++;
    256268        globalStatistics.AddSentence(sentence, quality);
     269
    257270        if (iterations % 1000 == 0) {
    258271          if (iterations % 10000 == 0) Console.Clear();
     
    260273          alg.PrintStats();
    261274        }
     275
    262276        //Console.WriteLine(sentence);
    263277
    264         if (iterations % 10000 == 0) {
    265           //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
    266         }
     278        //if (iterations % 10000 == 0) {
     279        //  Console.WriteLine("{0}", globalStatistics);
     280        //}
    267281      };
    268282
Note: See TracChangeset for help on using the changeset viewer.