Changeset 11832

Timestamp:

01/27/15 16:34:34 (10 years ago)

Author:

gkronber

Message:

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

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericContextualGrammarPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericFunctionApproximationGrammarPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs (modified) (5 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.Test/TestSymbRegInstances.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Feature.cs (added)
• HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs (modified) (6 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs (modified) (1 diff)
• Main/Program.cs (modified) (12 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs

@@ -9 +9 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   public class BernoulliPolicyActionInfo : IBanditPolicyActionInfo {
-    private double knownValue;
-    public bool Disabled { get { return NumSuccess == -1; } }
     public int NumSuccess { get; private set; }
     public int NumFailure { get; private set; }
@@ -16 +14 @@
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
-          return NumSuccess / (double)(Tries);
+        return NumSuccess / (double)(Tries);
       }
     }
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       //Debug.Assert(reward.IsAlmost(0.0) || reward.IsAlmost(1.0));
 
@@ -29 +24 @@
       else NumFailure++;
     }
-    public void Disable(double reward) {
-      this.NumSuccess = -1;
-      this.NumFailure = -1;
-      this.knownValue = reward;
-    }
     public void Reset() {
       NumSuccess = 0;
       NumFailure = 0;
-      knownValue = 0.0;
     }
     public void PrintStats() {
-      Console.WriteLine("expected value {0,5:F2} disabled {1}", Value, Disabled);
+      Console.WriteLine("expected value {0,5:F2}", Value);
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs

@@ -21 +21 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         var theta = Rand.BetaRand(random, aInfo.NumSuccess + alpha, aInfo.NumFailure + beta);
         if (theta > maxTheta) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs

@@ -14 +14 @@
     public double Value {
       get {
-          return Tries > 0 ? SumReward / Tries : 0.0;
+        return Tries > 0 ? SumReward / Tries : 0.0;
       }
     }
     public DefaultPolicyActionInfo() {
-      MaxReward = double.MinValue;
+      MaxReward = 0.0;
     }
 
@@ -33 +33 @@
     }
 
+    public override string ToString() {
+      return string.Format("{0:F3} {1:F3} {2}", Value, MaxReward, Tries);
+    }
+
     public static Func<DefaultPolicyActionInfo, double> AverageReward {
       get {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs

@@ -31 +31 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
 
         var tries = aInfo.Tries;

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs

@@ -8 +8 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   public class MeanAndVariancePolicyActionInfo : IBanditPolicyActionInfo {
-    private bool disabled;
-    public bool Disabled { get { return disabled; } }
     private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
-    private double knownValue;
     public int Tries { get { return estimator.N; } }
     public double SumReward { get { return estimator.Sum; } }
@@ -18 +15 @@
     public double Value {
       get {
-        if (disabled) return knownValue;
-        else
-          return AvgReward;
+        return AvgReward;
       }
     }
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       estimator.UpdateReward(reward);
     }
 
-    public void Disable(double reward) {
-      disabled = true;
-      this.knownValue = reward;
-    }
-
     public void Reset() {
-      disabled = false;
-      knownValue = 0.0;
       estimator.Reset();
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs

@@ -14 +14 @@
       var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
 
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       int aIdx = -1;
@@ -21 +21 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs

@@ -12 +12 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       double bestQ = double.NegativeInfinity;
       int aIdx = -1;
@@ -18 +18 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         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

@@ -67 +67 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\GenericFunctionApproximationGrammarPolicy.cs" />
+    <Compile Include="GrammarPolicies\QLearningGrammarPolicy.cs" />
+    <Compile Include="GrammarPolicies\GenericContextualGrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj

@@ -31 +31 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="ALGLIB-3.7.0, Version=3.7.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\ALGLIB-3.7.0.dll</HintPath>
+    </Reference>
+    <Reference Include="AutoDiff-1.0">
+      <HintPath>..\..\..\trunk\sources\bin\AutoDiff-1.0.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.Common-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

@@ -5 +5 @@
 using System.Security.AccessControl;
 using System.Text;
+using AutoDiff;
 using HeuristicLab.Common;
 using HeuristicLab.Problems.DataAnalysis;
@@ -13 +14 @@
   // provides bridge to HL regression problem instances
   public class SymbolicRegressionProblem : IProblem {
+
     private const string grammarString = @"
         G(E):
-        E -> V | V+E | V-E | V*E | V/E | (E)
+        E -> V | V+E | V-E | V*E | V/E | (E) | C | C+E | C-E | C*E | C/E 
+        C -> 0..9
         V -> <variables>
         ";
-
+    // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
 
     private readonly IGrammar grammar;
-    private readonly ExpressionInterpreter interpreter;
 
     private readonly int N;
@@ -27 +29 @@
     private readonly double[] y;
     private readonly int d;
-
-
-    public SymbolicRegressionProblem(string partOfName) {
+    private readonly double[] erc;
+
+
+    public SymbolicRegressionProblem(Random random, string partOfName) {
       var instanceProvider = new RegressionRealWorldInstanceProvider();
       var dds = instanceProvider.GetDataDescriptors().OfType<RegressionDataDescriptor>();
@@ -50 +53 @@
         i++;
       }
+      // initialize ERC values
+      erc = Enumerable.Range(0, 10).Select(_ => Rand.RandNormal(random) * 10).ToArray();
 
       char firstVar = 'a';
       char lastVar = Convert.ToChar(Convert.ToByte('a') + d - 1);
       this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
-      this.interpreter = new ExpressionInterpreter();
-
     }
 
@@ -69 +72 @@
 
     public double Evaluate(string sentence) {
-      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])));
-    }
-
-
-    // right now only + and * is supported
-    public string CanonicalRepresentation(string terminalPhrase) {
-      //return terminalPhrase;
-      var terms = terminalPhrase.Split('+');
-      return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
-        .OrderBy(term => term));
-    }
+      var interpreter = new ExpressionInterpreter();
+      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)));
+    }
+
+
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+      //var terms = phrase.Split('+');
+      //return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
+      //  .OrderBy(term => term));
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
+
+
+    /*
+    public static double OptimizeConstants(string sentence) {
+
+      List<AutoDiff.Variable> variables = new List<AutoDiff.Variable>();
+      List<AutoDiff.Variable> parameters = new List<AutoDiff.Variable>();
+      List<string> variableNames = new List<string>();
+
+      AutoDiff.Term func;
+      if (!TryTransformToAutoDiff(sentence, 0, variables, parameters, out func))
+        throw new NotSupportedException("Could not optimize constants of symbolic expression tree due to not supported symbols used in the tree.");
+      if (variableNames.Count == 0) return 0.0;
+
+      AutoDiff.IParametricCompiledTerm compiledFunc = AutoDiff.TermUtils.Compile(func, variables.ToArray(), parameters.ToArray());
+
+      List<SymbolicExpressionTreeTerminalNode> terminalNodes = tree.Root.IterateNodesPrefix().OfType<SymbolicExpressionTreeTerminalNode>().ToList();
+      double[] c = new double[variables.Count];
+
+      {
+        c[0] = 0.0;
+        c[1] = 1.0;
+        //extract inital constants
+        int i = 2;
+        foreach (var node in terminalNodes) {
+          ConstantTreeNode constantTreeNode = node as ConstantTreeNode;
+          VariableTreeNode variableTreeNode = node as VariableTreeNode;
+          if (constantTreeNode != null)
+            c[i++] = constantTreeNode.Value;
+          else if (variableTreeNode != null)
+            c[i++] = variableTreeNode.Weight;
+        }
+      }
+      double[] originalConstants = (double[])c.Clone();
+      double originalQuality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(interpreter, tree, lowerEstimationLimit, upperEstimationLimit, problemData, rows, applyLinearScaling);
+
+      alglib.lsfitstate state;
+      alglib.lsfitreport rep;
+      int info;
+
+      Dataset ds = problemData.Dataset;
+      double[,] x = new double[rows.Count(), variableNames.Count];
+      int row = 0;
+      foreach (var r in rows) {
+        for (int col = 0; col < variableNames.Count; col++) {
+          x[row, col] = ds.GetDoubleValue(variableNames[col], r);
+        }
+        row++;
+      }
+      double[] y = ds.GetDoubleValues(problemData.TargetVariable, rows).ToArray();
+      int n = x.GetLength(0);
+      int m = x.GetLength(1);
+      int k = c.Length;
+
+      alglib.ndimensional_pfunc function_cx_1_func = CreatePFunc(compiledFunc);
+      alglib.ndimensional_pgrad function_cx_1_grad = CreatePGrad(compiledFunc);
+
+      try {
+        alglib.lsfitcreatefg(x, y, c, n, m, k, false, out state);
+        alglib.lsfitsetcond(state, 0.0, 0.0, maxIterations);
+        //alglib.lsfitsetgradientcheck(state, 0.001);
+        alglib.lsfitfit(state, function_cx_1_func, function_cx_1_grad, null, null);
+        alglib.lsfitresults(state, out info, out c, out rep);
+      } catch (ArithmeticException) {
+        return originalQuality;
+      } catch (alglib.alglibexception) {
+        return originalQuality;
+      }
+
+      //info == -7  => constant optimization failed due to wrong gradient
+      if (info != -7) throw new ArgumentException();
+    }
+
+
+    private static alglib.ndimensional_pfunc CreatePFunc(AutoDiff.IParametricCompiledTerm compiledFunc) {
+      return (double[] c, double[] x, ref double func, object o) => {
+        func = compiledFunc.Evaluate(c, x);
+      };
+    }
+
+    private static alglib.ndimensional_pgrad CreatePGrad(AutoDiff.IParametricCompiledTerm compiledFunc) {
+      return (double[] c, double[] x, ref double func, double[] grad, object o) => {
+        var tupel = compiledFunc.Differentiate(c, x);
+        func = tupel.Item2;
+        Array.Copy(tupel.Item1, grad, grad.Length);
+      };
+    }
+
+    private static bool TryTransformToAutoDiff(string phrase, int symbolPos, List<AutoDiff.Variable> variables, List<AutoDiff.Variable> parameters, out AutoDiff.Term term)
+    {
+      var curSy = phrase[0];
+      if () {
+        var var = new AutoDiff.Variable();
+        variables.Add(var);
+        term = var;
+        return true;
+      }
+      if (node.Symbol is Variable) {
+        var varNode = node as VariableTreeNode;
+        var par = new AutoDiff.Variable();
+        parameters.Add(par);
+        variableNames.Add(varNode.VariableName);
+        var w = new AutoDiff.Variable();
+        variables.Add(w);
+        term = AutoDiff.TermBuilder.Product(w, par);
+        return true;
+      }
+      if (node.Symbol is Addition) {
+        List<AutoDiff.Term> terms = new List<Term>();
+        foreach (var subTree in node.Subtrees) {
+          AutoDiff.Term t;
+          if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out t)) {
+            term = null;
+            return false;
+          }
+          terms.Add(t);
+        }
+        term = AutoDiff.TermBuilder.Sum(terms);
+        return true;
+      }
+      if (node.Symbol is Subtraction) {
+        List<AutoDiff.Term> terms = new List<Term>();
+        for (int i = 0; i < node.SubtreeCount; i++) {
+          AutoDiff.Term t;
+          if (!TryTransformToAutoDiff(node.GetSubtree(i), variables, parameters, variableNames, out t)) {
+            term = null;
+            return false;
+          }
+          if (i > 0) t = -t;
+          terms.Add(t);
+        }
+        term = AutoDiff.TermBuilder.Sum(terms);
+        return true;
+      }
+      if (node.Symbol is Multiplication) {
+        AutoDiff.Term a, b;
+        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
+          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
+          term = null;
+          return false;
+        } else {
+          List<AutoDiff.Term> factors = new List<Term>();
+          foreach (var subTree in node.Subtrees.Skip(2)) {
+            AutoDiff.Term f;
+            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
+              term = null;
+              return false;
+            }
+            factors.Add(f);
+          }
+          term = AutoDiff.TermBuilder.Product(a, b, factors.ToArray());
+          return true;
+        }
+      }
+      if (node.Symbol is Division) {
+        // only works for at least two subtrees
+        AutoDiff.Term a, b;
+        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
+          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
+          term = null;
+          return false;
+        } else {
+          List<AutoDiff.Term> factors = new List<Term>();
+          foreach (var subTree in node.Subtrees.Skip(2)) {
+            AutoDiff.Term f;
+            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
+              term = null;
+              return false;
+            }
+            factors.Add(1.0 / f);
+          }
+          term = AutoDiff.TermBuilder.Product(a, 1.0 / b, factors.ToArray());
+          return true;
+        }
+      }
+      
+      if (node.Symbol is StartSymbol) {
+        var alpha = new AutoDiff.Variable();
+        var beta = new AutoDiff.Variable();
+        variables.Add(beta);
+        variables.Add(alpha);
+        AutoDiff.Term branchTerm;
+        if (TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out branchTerm)) {
+          term = branchTerm * alpha + beta;
+          return true;
+        } else {
+          term = null;
+          return false;
+        }
+      }
+      term = null;
+      return false;
+    }
+     */
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSymbRegInstances.cs

@@ -12 +12 @@
     public void TestGetDataDescriptors() {
 
-      var problem = new SymbolicRegressionProblem("Tower");
+      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
 
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

@@ -43 +43 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Feature.cs" />
+    <Compile Include="Problems\KryptosProblem.cs" />
     <Compile Include="Problems\EvenParityProblem.cs" />
     <Compile Include="Problems\ExpressionInterpreter.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs

@@ -9 +9 @@
     IGrammar Grammar { get; }
     double Evaluate(string sentence);
-    string CanonicalRepresentation(string terminalPhrase); // canonical state must use correct syntax (must be a valid input for evaluate)
+    string CanonicalRepresentation(string phrase); // canonical state must use correct syntax (must be a valid input for evaluate)
+    IEnumerable<Feature> GetFeatures(string phrase);
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs

@@ -50 +50 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs

@@ -3 +3 @@
 using System.Diagnostics.Eventing.Reader;
 using System.Linq;
+using System.Runtime.CompilerServices;
 using System.Runtime.Remoting.Messaging;
 using System.Text;
@@ -10 +11 @@
 namespace HeuristicLab.Problems.GrammaticalOptimization {
   public class ExpressionInterpreter {
+    private static readonly double[] emptyErc = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+
     private string sentence;
     private int syIdx;
@@ -15 +18 @@
     // Expr -> Term { ('+' | '-' | '^' ) Term } 
     // Term -> Fact { ('*' | '/') Fact }
-    // Fact -> '!' Expr | '(' Expr ')' | Var
+    // Fact -> '!' Expr | '(' Expr ')' | Var | const
     // Var -> 'a'..'z'
+    // const -> '0' .. '9'
+
+    // constants are Koza-style ephemeral random constants (ERC). for now we only allow up to 10 constants.
+    // The constant symbols '0' .. '9' are treated as ERC indices
 
     // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
 
     public bool Interpret(string sentence, bool[] vars) {
+      return Interpret(sentence, vars, emptyErc);
+    }
+
+    public bool Interpret(string sentence, bool[] vars, double[] erc) {
       InitLex(sentence);
       var d = new double[vars.Length];
       for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
-      return !(Expr(d).IsAlmost(0));
+      return !(Expr(d, erc).IsAlmost(0));
     }
 
     public double Interpret(string sentence, double[] vars) {
+      return Interpret(sentence, vars, emptyErc);
+    }
+
+    public double Interpret(string sentence, double[] vars, double[] erc) {
       InitLex(sentence);
-      return Expr(vars);
+      return Expr(vars, erc);
     }
 
@@ -51 +66 @@
     }
 
-    private double Expr(double[] d) {
+    private double Expr(double[] d, double[] erc) {
       var r = 0.0;
-      r = Term(d);
+      r = Term(d, erc);
       var curSy = CurSy();
       while (curSy == '+' || curSy == '-' || curSy == '^') {
         if (curSy == '+') {
           NewSy();
-          r += Expr(d);
+          r += Expr(d, erc);
         } else if (curSy == '-') {
           NewSy();
-          r -= Expr(d);
+          r -= Expr(d, erc);
         } else {
           NewSy();
-          var e = Expr(d);
+          var e = Expr(d, erc);
           r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
         }
@@ -72 +87 @@
     }
 
-    private double Term(double[] d) {
+    private double Term(double[] d, double[] erc) {
       var r = 0.0;
-      r = Fact(d);
+      r = Fact(d, erc);
       var curSy = CurSy();
       while (curSy == '*' || curSy == '/') {
         if (curSy == '*') {
           NewSy();
-          r *= Term(d);
+          r *= Term(d, erc);
         } else {
           NewSy();
-          r /= Term(d);
+          r /= Term(d, erc);
         }
         curSy = CurSy();
@@ -89 +104 @@
     }
 
-    private double Fact(double[] d) {
+    private double Fact(double[] d, double[] erc) {
       double r = 0.0;
       var curSy = CurSy();
       if (curSy == '!') {
         NewSy();
-        r = Not(Expr(d));
+        r = Not(Expr(d, erc));
       } else if (curSy == '(') {
         NewSy();
-        r = Expr(d);
+        r = Expr(d, erc);
         if (CurSy() != ')') throw new ArgumentException();
         NewSy();
-      } else /* if (curSy >= 'a' && curSy <= 'z') */ {
+      } else if (curSy >= 'a' && curSy <= 'z') {
         int o = (byte)curSy - (byte)'a';
         //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
         if (o < 0 || o >= d.Length) throw new ArgumentException();
         r = d[o];
+        NewSy();
+      } else /* if (curSy >= '0' && curSy <= '9') */ {
+        int o = (byte)curSy - (byte)'0';
+        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
+        if (o < 0 || o >= 10) throw new ArgumentException();
+        r = erc[o];
         NewSy();
       }

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

@@ -129 +129 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       // as the ordering of phrases does not matter we can reorder the phrases
       // and remove duplicates
-      var numPhrases = terminalPhrase.Length / phraseLen;
+      var numPhrases = phrase.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);
+        var subphrase = phrase.Substring(sentenceIdx, phraseLen);
+        subphrase = CanonicalPhrase(subphrase);
+        if (!phrases.Contains(subphrase)) phrases.Add(subphrase);
       }
-      var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+      var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
       remainder = CanonicalPhrase(remainder);
       if (!phrases.Contains(remainder)) phrases.Add(remainder);
@@ -146 +146 @@
       return string.Join("", phrases);
     }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
+
+    public override string ToString() {
+      return string.Format("\"FindPhrasesProblem {0} {1} {2} {3:F2} {4} {5:F2} {6}\"", numPhrases, phraseLen,
+        optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets);
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs

@@ -39 +39 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs

@@ -80 +80 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs

@@ -35 +35 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
+      //throw new NotImplementedException();
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
       throw new NotImplementedException();
-      return terminalPhrase;
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

@@ -113 +113 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       if (phrasesAsSets) {
         var sb = new StringBuilder();
-        var numPhrases = terminalPhrase.Length / phraseLen;
+        var numPhrases = phrase.Length / phraseLen;
         for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
           var sentenceIdx = phraseIdx * phraseLen;
-          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
-          phrase = CanonicalPhrase(phrase);
-          sb.Append(phrase);
+          var subphrase = phrase.Substring(sentenceIdx, phraseLen);
+          subphrase = CanonicalPhrase(subphrase);
+          sb.Append(subphrase);
         }
 
-        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+        var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
         remainder = CanonicalPhrase(remainder);
         sb.Append(remainder);
@@ -130 +130 @@
         return sb.ToString();
       } else
-        return terminalPhrase;
+        return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs

@@ -29 +29 @@
       throw new NotImplementedException();
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs

@@ -77 +77 @@
 
     // in each position there could be multiple correct and incorrect symbols
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       var sb = new StringBuilder();
-      for (int i = 0; i < terminalPhrase.Length; i++) {
-        if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
+      for (int i = 0; i < phrase.Length; i++) {
+        if (optimalSymbolsForPos[i].Contains(phrase[i])) {
           sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
         } else {
-          sb.Append(terminalPhrase[i]);
+          sb.Append(phrase[i]);
         }
       }
       return sb.ToString();
     }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs

@@ -34 +34 @@
       return regex.Matches(sentence).Count;
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

@@ -29 +29 @@
       throw new NotImplementedException();
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs

@@ -102 +102 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      var sb = new StringBuilder(terminalPhrase);
-      string canonicalPhrase = terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      var sb = new StringBuilder(phrase);
+      string canonicalPhrase = phrase;
       string oldPhrase;
       do {
@@ -112 +112 @@
       } while (canonicalPhrase != oldPhrase);
       return sb.ToString();
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase) {
+      return Enumerable.Repeat(new Feature(CanonicalRepresentation(phrase), 1.0), 1);
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs

@@ -120 +120 @@
       return canonicalTerm;
     }
+
+    // splits the phrase into terms and creates (sparse) term-occurrance features
+    public IEnumerable<Feature> GetFeatures(string phrase) {
+      var canonicalTerms = new HashSet<string>();
+      foreach (string t in phrase.Split('+')) {
+        canonicalTerms.Add(CanonicalTerm(t));
+      }
+      return canonicalTerms.Select(entry => new Feature(entry, 1.0)).Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
+    }
+
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

@@ -24 +24 @@
       CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
 
-      RunDemo();
-      //RunGridTest();
+      //RunDemo();
+      RunGridTest();
     }
 
     private static void RunGridTest() {
-      int maxIterations = 50000; // for poly-10 with 50000 evaluations no successful try with hl yet
+      int maxIterations = 70000; // for poly-10 with 50000 evaluations no successful try with hl yet
       //var globalRandom = new Random(31415);
       var localRandSeed = 31415;
-      var reps = 10;
+      var reps = 30;
 
       var policyFactories = new Func<IBanditPolicy>[]
@@ -109 +109 @@
       {
         //(rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
-        //(rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
+        (rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
       };
 
       foreach (var instanceFactory in instanceFactories) {
-        foreach (var useCanonical in new bool[] { true /*, false */ }) {
-          foreach (var randomTries in new int[] { 0, /* 1, 10, /* 5, 100 /*, 500, 1000 */}) {
+        foreach (var useCanonical in new bool[] { true /*, false */}) {
+          foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
             foreach (var policyFactory in policyFactories) {
               var myRandomTries = randomTries;
@@ -142 +142 @@
                 var problem = instance.Item1;
                 var maxLen = instance.Item2;
-                var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
-                  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
+                //var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
+                //  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
+                var alg = new SequentialSearch(problem, maxLen, myLocalRand,
+                  myRandomTries,
+                  new GenericFunctionApproximationGrammarPolicy(problem,
+                    useCanonical));
                 //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
                 //var alg = new AlternativesContextSampler(problem, 25);
@@ -150 +154 @@
                   iterations++;
                   globalStatistics.AddSentence(sentence, quality);
-                  if (iterations % 10000 == 0) {
-                    Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4}", i, myRandomTries, policyFactory(), useCanonical, globalStatistics);
+                  if (iterations % 1000 == 0) {
+                    Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4} {5}", i, myRandomTries, policyFactory(), useCanonical, problem.ToString(), globalStatistics);
                   }
                 };
@@ -190 +194 @@
 
 
-      int maxIterations = 100000;
+      int maxIterations = 1000000;
       int iterations = 0;
       var sw = new Stopwatch();
@@ -199 +203 @@
 
       //var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
+      // var phraseLen = 3;
+      // var numPhrases = 5;
+      // var problem = new RoyalPhraseSequenceProblem(random, 10, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: false);
+
       //var phraseLen = 3;
       //var numPhrases = 5;
-      //var problem = new RoyalPhraseSequenceProblem(random, 15, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: true);
-
-      // var phraseLen = 3;
-      // var numPhrases = 5;
-      // var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 200, correctReward: 1.0, decoyReward: 0.5, phrasesAsSets: true);
+      //var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 0, correctReward: 1.0, decoyReward: 0, phrasesAsSets: false);
 
       // good results for symb-reg
@@ -213 +217 @@
       // - GenericThompsonSamplingPolicy("")
       // - 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
+      // 2015 01 22: symb-reg: grid test on find-phrases problem showed good results for UCB1TunedPolicy and SequentialSearch with canonical states
+      // - symb-reg: consistent results with UCB1Tuned. finds optimal solution in ~50k iters (new GenericGrammarPolicy(problem, new UCB1TunedPolicy(), true));
+      // 2015 01 23: grid test with canonical states:
+      // - UCTPolicy(0.10) und UCBNormalPolicy 10/10 optimale Lösungen bei max. 50k iters, etwas schlechter: generic-thompson with variable sigma und bolzmannexploration (100)
+
 
       // good results for artificial ant:
@@ -219 +228 @@
       // - GaussianModelWithUnknownVariance (and Q= 0.99-quantil) also works well for Ant
       // 2015 01 19: grid test with canonical states (non-canonical slightly worse)
-      // - Threshold Ascent (best 100, 0.01; all variants relatively good)
-      // - Policies where the variance has a large weight compared to the mean? (Gaussian(compatible), Gaussian with fixed variance, UCT with large c, alle TA)
-
-      //var problem = new SymbolicRegressionPoly10Problem();
-
-      var problem = new SantaFeAntProblem();
-      //var problem = new SymbolicRegressionProblem("Tower"); 
+      // - ant: Threshold Ascent (best 100, 0.01; all variants relatively good)
+      // - 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)
+      // - ant: UCB1Tuned with canonical states also works very well for the artificial ant! constistent solutions in less than 10k iters      
+
+      var problem = new SymbolicRegressionPoly10Problem();
+      //var problem = new SantaFeAntProblem();
+      //var problem = new SymbolicRegressionProblem(random, "Tower"); 
       //var problem = new PalindromeProblem();
       //var problem = new HardPalindromeProblem();
@@ -234 +243 @@
       //var alg = new MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
       //var alg = new SequentialSearch(problem, 23, random, 0,
-      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new ModifiedUCTPolicy(0.1), true));
-      var alg = new SequentialSearch(problem, 17, random, 0,
-        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericTDPolicy(problem, true));
+      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.QLearningGrammarPolicy(problem, new BoltzmannExplorationPolicy(10),
+      //    1, 1, true));
+      //var alg = new SequentialSearch(problem, 23, random, 0,
+      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericContextualGrammarPolicy(problem, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), true));
+      var alg = new SequentialSearch(problem, 23, random, 0,
+        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericFunctionApproximationGrammarPolicy(problem, true));
       //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
       //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
@@ -249 +261 @@
 
       alg.FoundNewBestSolution += (sentence, quality) => {
-        //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
+        //Console.WriteLine("{0}", globalStatistics);
         //Console.ReadLine();
       };
@@ -255 +267 @@
         iterations++;
         globalStatistics.AddSentence(sentence, quality);
+
         if (iterations % 1000 == 0) {
           if (iterations % 10000 == 0) Console.Clear();
@@ -260 +273 @@
           alg.PrintStats();
         }
+
         //Console.WriteLine(sentence);
 
-        if (iterations % 10000 == 0) {
-          //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
-        }
+        //if (iterations % 10000 == 0) {
+        //  Console.WriteLine("{0}", globalStatistics);
+        //}
       };