source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs @ 13791

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Diagnostics;
using System.Linq;
using System.Net;
using System.Runtime.InteropServices;
using System.Security;
using System.Security.AccessControl;
using System.Text;
using HeuristicLab.Common;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem {
    //    private const string grammarString = @"
    //    G(E):
    //    E -> V | V+E | V-E | V*E | (E)
    //    V -> a .. j 
    //    ";
    //private const string grammarString = @"
    //G(E):
    //E -> a | b | c | d | e | f | g | h | i | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | i+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | i*E | j*E 
    //";
    private const string grammarString = @"
    G(E):
    E -> a | b | c | d | e | f | g | h | i | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | i+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | i*E | j*E  
    ";

    // for tree-based GP in HL we need a different grammar for the same language
    // E = expr, S = sum, P = product
    private const string hlGrammarString = @"
    G(E):
    E -> S | P | a | b | c | d | e | f | g | h | i | j
    S -> EE | EEE
    P -> EE | EEE
    ";
    // mininmal tree for the optimal expr (40 nodes)
    // E S
    //     E S
    //         E P 
    //           E a E b
    //         E P 
    //           E c E d
    //         E P 
    //           E e E f
    //     E S
    //         E P 
    //           E a E g E i
    //         E P 
    //           E c E f E j

    public IGrammar TreeBasedGPGrammar { get; private set; }

    private readonly IGrammar grammar;

    private readonly int N;
    private readonly double[][] x;
    private readonly double[] y;
    public string Name { get { return "SymbolicRegressionPoly10"; } }

    public SymbolicRegressionPoly10Problem(int n = 500) {
      this.grammar = new Grammar(grammarString);
      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);

      this.N = n;
      this.x = new double[N][];
      this.y = new double[N];

      GenerateData();
    }

    private void GenerateData() {
      // generate data with fixed seed to make sure that data is always the same
      var rand = new System.Random(31415);
      for (int i = 0; i < N; i++) {
        x[i] = new double[10];
        for (int j = 0; j < 10; j++) {
          x[i][j] = rand.NextDouble() * 2 - 1;
        }
        // poly-10 no noise
        /* a*b + c*d + e*f + a*g*i + c*f*j */
        y[i] = x[i][0] * x[i][1] +
               x[i][2] * x[i][3] +
               x[i][4] * x[i][5] +
               x[i][0] * x[i][6] * x[i][8] +
               x[i][2] * x[i][5] * x[i][9];
      }
    }

    public double BestKnownQuality(int maxLen) {
      // for now only an upper bound is returned, ideally we have an R² of 1.0
      // the optimal R² can only be reached for sentences of at least 23 symbols
      return 1.0;
    }

    public IGrammar Grammar {
      get { return grammar; }
    }

    private static double[] erc = new double[] { 0.0, 1.0 };
    public double Evaluate(string sentence) {
      var interpreter = new ExpressionInterpreter();
      return Math.Round(HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)).ToArray()), 3);
    }


    // most-recently-used caching (with limited capacity) for canonical representations
    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
    // right now only + and * is supported
    public string CanonicalRepresentation(string phrase) {
      string canonicalPhrase;
      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
        var terms = phrase.Split('+');
        var canonicalTerms = new SortedSet<string>();
        // only the last term might contain a NT-symbol. make sure this term is added at the end
        for (int i = 0; i < terms.Length - 1; i++) {
          canonicalTerms.Add(CanonicalTerm(terms[i]));
        }

        var sb = new StringBuilder(phrase.Length);
        foreach (var t in canonicalTerms)
          sb.Append(t).Append('+');

        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
        canonicalPhrase = sb.ToString();
        canonicalPhraseCache.Add(phrase, canonicalPhrase);
      }
      return canonicalPhrase;
    }

    // cache the canonical form of terms for performance reasons
    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
    private string CanonicalTerm(string term) {
      string canonicalTerm;
      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
        // add
        var chars = term.ToCharArray();
        Array.Sort(chars);
        var sb = new StringBuilder(chars.Length);
        // we want to have the up-case characters last
        for (int i = chars.Length - 1; i > 0; i--) {
          if (chars[i] != '*') {
            sb.Append(chars[i]);
            if (chars[i - 1] != '*') sb.Append('*');
          }
        }
        if (chars[0] != '*') sb.Append(chars[0]); // last term
        canonicalTerm = sb.ToString();
        canonicalTermDictionary.Add(term, canonicalTerm);
      }
      return canonicalTerm;
    }

    private double[] varIds = new double[] { };

    // splits the phrase into terms and creates (sparse) term-occurrance features
    public IEnumerable<Feature> GetFeatures(string phrase) {
      //if (phrase.EndsWith("E")) phrase = phrase.TrimEnd('*', '+', 'E');
      //yield return new Feature("$$$", 1.0); // const
      //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) });


      //if (phrase.EndsWith("E")) phrase = phrase.TrimEnd('*', '+', 'E');
      //var len = 5;
      //var start = Math.Max(0, phrase.Length - len);
      //var end = Math.Min(phrase.Length, start + len);
      //string f = phrase.Substring(start, end - start);
      //yield return new Feature(f, 1.0);
      //

      //var terms = phrase.Split('+');
      //foreach (var t in terms.Distinct()) yield return new Feature(t, 1.0);
      //
      //for (int i = 0; i < terms.Length; i++) {
      //  for (int j = i + 1; j < terms.Length; j++) {
      //    yield return new Feature(terms[i] + " " + terms[j], 1.0);
      //  }
      //}
      var t = new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j" };
      for (int t0Idx = 0; t0Idx < t.Length - 1; t0Idx++) {
        for (int t1Idx = t0Idx; t1Idx < t.Length; t1Idx++) {
          var a = t[t0Idx] + "*" + t[t1Idx];
          var b = t[t1Idx] + "*" + t[t0Idx];
          yield return new Feature(a, phrase.Contains(a) || phrase.Contains(b) ? 1 : 0);
        }
      }

      // var substrings = new HashSet<string>();
      // for (int start = 0; start <= phrase.Length - 2; start += 2) {
      //   var s = phrase.Substring(start, 3);
      //   substrings.Add(s);
      // }
      // 
      // var list = new List<string>(substrings);
      // 
      // for (int i = 0; i < list.Count; i++) {
      //   yield return new Feature(list[i], 1.0);
      //   //for (int j = i+1; j < list.Count; j++) {
      //   //  yield return new Feature(list[i] + " " + list[j], 1.0);
      //   //}
      // }

      //
      // for (int len = 1; len <= phrase.Length; len += 2) {
      //   var start = Math.Max(0, phrase.Length - len);
      //   var end = Math.Min(phrase.Length, start + len);
      //   string f = phrase.Substring(start, end - start);
      //   yield return new Feature(f, 1.0);
      // 
      // }

      //var partialInterpreter = new PartialExpressionInterpreter();
      //var vars = new double[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, };
      //var s = partialInterpreter.Interpret(phrase, vars);
      ////if (s.Any())
      ////  return new Feature[] { new Feature(s.Pop().ToString(), 1.0), };
      ////else
      ////  return new Feature[] { new Feature("$", 1.0), };
      //return s.Select(f => new Feature(f.ToString(), 1.0));
    }

    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
      var sb = new StringBuilder();

      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);

      return sb.ToString();
    }

    private static string[][] optimalTerms = new string[][]
      {
        new string[] { "a*b","b*a",},
        new string[] { "c*d","d*c",},
        new string[] { "e*f","f*e",},
        new string[] { "a*g*i","a*i*g","g*a*i","g*i*a","i*a*g","i*g*a"},
        new string[] { "c*j*f","c*f*j","j*c*f","j*f*c","f*c*j","f*j*c"},
      };

    private static int[][] permute5 = new int[][]
      {
        new int[] { 4, 3, 2, 0, 1 },
        new int[] { 4, 3, 2, 1, 0 },
        new int[] { 4, 3, 0, 2, 1 },
        new int[] { 4, 3, 1, 2, 0 },
        new int[] { 4, 3, 0, 1, 2 },
        new int[] { 4, 3, 1, 0, 2 },
        new int[] { 4, 2, 3, 0, 1 },
        new int[] { 4, 2, 3, 1, 0 },
        new int[] { 4, 0, 3, 2, 1 },
        new int[] { 4, 1, 3, 2, 0 },
        new int[] { 4, 0, 3, 1, 2 },
        new int[] { 4, 1, 3, 0, 2 },
        new int[] { 4, 2, 0, 3, 1 },
        new int[] { 4, 2, 1, 3, 0 },
        new int[] { 4, 0, 2, 3, 1 },
        new int[] { 4, 1, 2, 3, 0 },
        new int[] { 4, 0, 1, 3, 2 },
        new int[] { 4, 1, 0, 3, 2 },
        new int[] { 4, 2, 0, 1, 3 },
        new int[] { 4, 2, 1, 0, 3 },
        new int[] { 4, 0, 2, 1, 3 },
        new int[] { 4, 1, 2, 0, 3 },
        new int[] { 4, 0, 1, 2, 3 },
        new int[] { 4, 1, 0, 2, 3 },
        new int[] { 3, 4, 2, 0, 1 },
        new int[] { 3, 4, 2, 1, 0 },
        new int[] { 3, 4, 0, 2, 1 },
        new int[] { 3, 4, 1, 2, 0 },
        new int[] { 3, 4, 0, 1, 2 },
        new int[] { 3, 4, 1, 0, 2 },
        new int[] { 2, 4, 3, 0, 1 },
        new int[] { 2, 4, 3, 1, 0 },
        new int[] { 0, 4, 3, 2, 1 },
        new int[] { 1, 4, 3, 2, 0 },
        new int[] { 0, 4, 3, 1, 2 },
        new int[] { 1, 4, 3, 0, 2 },
        new int[] { 2, 4, 0, 3, 1 },
        new int[] { 2, 4, 1, 3, 0 },
        new int[] { 0, 4, 2, 3, 1 },
        new int[] { 1, 4, 2, 3, 0 },
        new int[] { 0, 4, 1, 3, 2 },
        new int[] { 1, 4, 0, 3, 2 },
        new int[] { 2, 4, 0, 1, 3 },
        new int[] { 2, 4, 1, 0, 3 },
        new int[] { 0, 4, 2, 1, 3 },
        new int[] { 1, 4, 2, 0, 3 },
        new int[] { 0, 4, 1, 2, 3 },
        new int[] { 1, 4, 0, 2, 3 },
        new int[] { 3, 2, 4, 0, 1 },
        new int[] { 3, 2, 4, 1, 0 },
        new int[] { 3, 0, 4, 2, 1 },
        new int[] { 3, 1, 4, 2, 0 },
        new int[] { 3, 0, 4, 1, 2 },
        new int[] { 3, 1, 4, 0, 2 },
        new int[] { 2, 3, 4, 0, 1 },
        new int[] { 2, 3, 4, 1, 0 },
        new int[] { 0, 3, 4, 2, 1 },
        new int[] { 1, 3, 4, 2, 0 },
        new int[] { 0, 3, 4, 1, 2 },
        new int[] { 1, 3, 4, 0, 2 },
        new int[] { 2, 0, 4, 3, 1 },
        new int[] { 2, 1, 4, 3, 0 },
        new int[] { 0, 2, 4, 3, 1 },
        new int[] { 1, 2, 4, 3, 0 },
        new int[] { 0, 1, 4, 3, 2 },
        new int[] { 1, 0, 4, 3, 2 },
        new int[] { 2, 0, 4, 1, 3 },
        new int[] { 2, 1, 4, 0, 3 },
        new int[] { 0, 2, 4, 1, 3 },
        new int[] { 1, 2, 4, 0, 3 },
        new int[] { 0, 1, 4, 2, 3 },
        new int[] { 1, 0, 4, 2, 3 },
        new int[] { 3, 2, 0, 4, 1 },
        new int[] { 3, 2, 1, 4, 0 },
        new int[] { 3, 0, 2, 4, 1 },
        new int[] { 3, 1, 2, 4, 0 },
        new int[] { 3, 0, 1, 4, 2 },
        new int[] { 3, 1, 0, 4, 2 },
        new int[] { 2, 3, 0, 4, 1 },
        new int[] { 2, 3, 1, 4, 0 },
        new int[] { 0, 3, 2, 4, 1 },
        new int[] { 1, 3, 2, 4, 0 },
        new int[] { 0, 3, 1, 4, 2 },
        new int[] { 1, 3, 0, 4, 2 },
        new int[] { 2, 0, 3, 4, 1 },
        new int[] { 2, 1, 3, 4, 0 },
        new int[] { 0, 2, 3, 4, 1 },
        new int[] { 1, 2, 3, 4, 0 },
        new int[] { 0, 1, 3, 4, 2 },
        new int[] { 1, 0, 3, 4, 2 },
        new int[] { 2, 0, 1, 4, 3 },
        new int[] { 2, 1, 0, 4, 3 },
        new int[] { 0, 2, 1, 4, 3 },
        new int[] { 1, 2, 0, 4, 3 },
        new int[] { 0, 1, 2, 4, 3 },
        new int[] { 1, 0, 2, 4, 3 },
        new int[] { 3, 2, 0, 1, 4 },
        new int[] { 3, 2, 1, 0, 4 },
        new int[] { 3, 0, 2, 1, 4 },
        new int[] { 3, 1, 2, 0, 4 },
        new int[] { 3, 0, 1, 2, 4 },
        new int[] { 3, 1, 0, 2, 4 },
        new int[] { 2, 3, 0, 1, 4 },
        new int[] { 2, 3, 1, 0, 4 },
        new int[] { 0, 3, 2, 1, 4 },
        new int[] { 1, 3, 2, 0, 4 },
        new int[] { 0, 3, 1, 2, 4 },
        new int[] { 1, 3, 0, 2, 4 },
        new int[] { 2, 0, 3, 1, 4 },
        new int[] { 2, 1, 3, 0, 4 },
        new int[] { 0, 2, 3, 1, 4 },
        new int[] { 1, 2, 3, 0, 4 },
        new int[] { 0, 1, 3, 2, 4 },
        new int[] { 1, 0, 3, 2, 4 },
        new int[] { 2, 0, 1, 3, 4 },
        new int[] { 2, 1, 0, 3, 4 },
        new int[] { 0, 2, 1, 3, 4 },
        new int[] { 1, 2, 0, 3, 4 },
        new int[] { 0, 1, 2, 3, 4 },
        new int[] { 1, 0, 2, 3, 4 },
      };


    private static HashSet<string>[] optimalSentences;
    static SymbolicRegressionPoly10Problem() {
      optimalSentences = Enumerable.Range(0, 24).Select(i => new HashSet<string>()).ToArray();

      foreach (var t0Idx in new[] { 0, 1 })
        foreach (var t1Idx in new[] { 0, 1 })
          foreach (var t2Idx in new[] { 0, 1 })
            foreach (var t3Idx in new[] { 0, 1, 2, 3, 4, 5 })
              foreach (var t4Idx in new[] { 0, 1, 2, 3, 4, 5 }) {
                foreach (var p in permute5) {
                  int[] idx = new int[] { t0Idx, t1Idx, t2Idx, t3Idx, t4Idx };
                  optimalSentences[23].Add(string.Join("+", p.Select(pi => optimalTerms[pi][idx[pi]])));
                }
              }
      for (int i = 0; i < 23; i += 2) {
        var newElements = new HashSet<string>();
        foreach (var sentence in optimalSentences[23]) {
          newElements.Add(sentence.Substring(0, i) + "E");
        }
        foreach (var e in newElements) optimalSentences[i + 1].Add(e);
      }
    }

    public bool IsOptimalPhrase(string phrase) {
      return optimalSentences[phrase.Length].Contains(phrase);
    }

    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
      if (treeNode.SubtreeCount == 0) {
        // terminal
        sb.Append(treeNode.Symbol.Name);
      } else {
        string op = string.Empty;
        switch (treeNode.Symbol.Name) {
          case "S": op = "+"; break;
          case "P": op = "*"; break;
          default: {
              Debug.Assert(treeNode.SubtreeCount == 1);
              break;
            }
        }
        // nonterminal
        if (op == "+") sb.Append("(");
        TreeToSentence(treeNode.Subtrees.First(), sb);
        foreach (var subTree in treeNode.Subtrees.Skip(1)) {
          sb.Append(op);
          TreeToSentence(subTree, sb);
        }
        if (op == "+") sb.Append(")");
      }
    }
  }
}