[11659] | 1 | using System;
|
---|
[11799] | 2 | using System.Collections.Concurrent;
|
---|
[11659] | 3 | using System.Collections.Generic;
|
---|
[11799] | 4 | using System.Collections.Specialized;
|
---|
[11846] | 5 | using System.Diagnostics;
|
---|
[11659] | 6 | using System.Linq;
|
---|
[11770] | 7 | using System.Net;
|
---|
[11659] | 8 | using System.Security;
|
---|
| 9 | using System.Security.AccessControl;
|
---|
| 10 | using System.Text;
|
---|
[11727] | 11 | using HeuristicLab.Common;
|
---|
[11846] | 12 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
[11659] | 13 |
|
---|
| 14 | namespace HeuristicLab.Problems.GrammaticalOptimization {
|
---|
[11846] | 15 | public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem {
|
---|
[11727] | 16 | // private const string grammarString = @"
|
---|
| 17 | // G(E):
|
---|
| 18 | // E -> V | V+E | V-E | V*E | (E)
|
---|
| 19 | // V -> a .. j
|
---|
| 20 | // ";
|
---|
[11659] | 21 | private const string grammarString = @"
|
---|
[11727] | 22 | G(E):
|
---|
[11747] | 23 | 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
|
---|
[11727] | 24 | ";
|
---|
[11659] | 25 |
|
---|
[11846] | 26 | // for tree-based GP in HL we need a different grammar for the same language
|
---|
| 27 | // E = expr, S = sum, P = product
|
---|
| 28 | private const string hlGrammarString = @"
|
---|
| 29 | G(E):
|
---|
| 30 | E -> S | P | a | b | c | d | e | f | g | h | i | j
|
---|
| 31 | S -> EE | EEE
|
---|
| 32 | P -> EE | EEE
|
---|
| 33 | ";
|
---|
| 34 | // mininmal tree for the optimal expr (40 nodes)
|
---|
| 35 | // E S
|
---|
| 36 | // E S
|
---|
| 37 | // E P
|
---|
| 38 | // E a E b
|
---|
| 39 | // E P
|
---|
| 40 | // E c E d
|
---|
| 41 | // E P
|
---|
| 42 | // E e E f
|
---|
| 43 | // E S
|
---|
| 44 | // E P
|
---|
| 45 | // E a E g E i
|
---|
| 46 | // E P
|
---|
| 47 | // E c E f E j
|
---|
[11708] | 48 |
|
---|
[11846] | 49 | private SymbolicExpressionGrammar symbExprGrammar;
|
---|
| 50 | public ISymbolicExpressionGrammar SymbolicExpressionGrammar {
|
---|
| 51 | get {
|
---|
| 52 | return symbExprGrammar;
|
---|
| 53 | }
|
---|
| 54 | }
|
---|
| 55 |
|
---|
[11659] | 56 | private readonly IGrammar grammar;
|
---|
| 57 |
|
---|
| 58 | private readonly int N;
|
---|
| 59 | private readonly double[][] x;
|
---|
| 60 | private readonly double[] y;
|
---|
| 61 |
|
---|
| 62 | public SymbolicRegressionPoly10Problem() {
|
---|
| 63 | this.grammar = new Grammar(grammarString);
|
---|
[11846] | 64 | this.symbExprGrammar = new GenericSymbExprGrammar(new Grammar(hlGrammarString));
|
---|
[11659] | 65 |
|
---|
| 66 | this.N = 500;
|
---|
| 67 | this.x = new double[N][];
|
---|
| 68 | this.y = new double[N];
|
---|
| 69 |
|
---|
| 70 | GenerateData();
|
---|
| 71 | }
|
---|
| 72 |
|
---|
| 73 | private void GenerateData() {
|
---|
| 74 | // generate data with fixed seed to make sure that data is always the same
|
---|
| 75 | var rand = new Random(31415);
|
---|
| 76 | for (int i = 0; i < N; i++) {
|
---|
| 77 | x[i] = new double[10];
|
---|
| 78 | for (int j = 0; j < 10; j++) {
|
---|
| 79 | x[i][j] = rand.NextDouble() * 2 - 1;
|
---|
| 80 | }
|
---|
| 81 | // poly-10 no noise
|
---|
[11730] | 82 | /* a*b + c*d + e*f + a*g*i + c*f*j */
|
---|
[11659] | 83 | y[i] = x[i][0] * x[i][1] +
|
---|
| 84 | x[i][2] * x[i][3] +
|
---|
| 85 | x[i][4] * x[i][5] +
|
---|
| 86 | x[i][0] * x[i][6] * x[i][8] +
|
---|
| 87 | x[i][2] * x[i][5] * x[i][9];
|
---|
| 88 | }
|
---|
| 89 | }
|
---|
| 90 |
|
---|
[11732] | 91 | public double BestKnownQuality(int maxLen) {
|
---|
[11659] | 92 | // for now only an upper bound is returned, ideally we have an R² of 1.0
|
---|
| 93 | // the optimal R² can only be reached for sentences of at least 23 symbols
|
---|
| 94 | return 1.0;
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 | public IGrammar Grammar {
|
---|
| 98 | get { return grammar; }
|
---|
| 99 | }
|
---|
| 100 |
|
---|
| 101 | public double Evaluate(string sentence) {
|
---|
[11742] | 102 | var interpreter = new ExpressionInterpreter();
|
---|
[11732] | 103 | return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
|
---|
[11659] | 104 | }
|
---|
| 105 |
|
---|
| 106 |
|
---|
[11799] | 107 | // most-recently-used caching (with limited capacity) for canonical representations
|
---|
| 108 | MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
|
---|
[11727] | 109 | // right now only + and * is supported
|
---|
[11745] | 110 | public string CanonicalRepresentation(string phrase) {
|
---|
[11799] | 111 | string canonicalPhrase;
|
---|
| 112 | if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
|
---|
| 113 | var terms = phrase.Split('+');
|
---|
| 114 | var canonicalTerms = new SortedSet<string>();
|
---|
| 115 | // only the last term might contain a NT-symbol. make sure this term is added at the end
|
---|
| 116 | for (int i = 0; i < terms.Length - 1; i++) {
|
---|
| 117 | canonicalTerms.Add(CanonicalTerm(terms[i]));
|
---|
| 118 | }
|
---|
[11745] | 119 |
|
---|
[11799] | 120 | var sb = new StringBuilder(phrase.Length);
|
---|
| 121 | foreach (var t in canonicalTerms)
|
---|
| 122 | sb.Append(t).Append('+');
|
---|
| 123 |
|
---|
| 124 | sb.Append(CanonicalTerm(terms[terms.Length - 1]));
|
---|
| 125 | canonicalPhrase = sb.ToString();
|
---|
| 126 | canonicalPhraseCache.Add(phrase, canonicalPhrase);
|
---|
| 127 | }
|
---|
| 128 | return canonicalPhrase;
|
---|
[11727] | 129 | }
|
---|
[11745] | 130 |
|
---|
[11799] | 131 | // cache the canonical form of terms for performance reasons
|
---|
| 132 | private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
|
---|
[11745] | 133 | private string CanonicalTerm(string term) {
|
---|
[11799] | 134 | string canonicalTerm;
|
---|
| 135 | if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
|
---|
| 136 | // add
|
---|
| 137 | var chars = term.ToCharArray();
|
---|
| 138 | Array.Sort(chars);
|
---|
| 139 | var sb = new StringBuilder(chars.Length);
|
---|
| 140 | // we want to have the up-case characters last
|
---|
[11806] | 141 | for (int i = chars.Length - 1; i > 0; i--) {
|
---|
| 142 | if (chars[i] != '*') {
|
---|
| 143 | sb.Append(chars[i]);
|
---|
| 144 | if (chars[i - 1] != '*') sb.Append('*');
|
---|
| 145 | }
|
---|
[11799] | 146 | }
|
---|
[11806] | 147 | if (chars[0] != '*') sb.Append(chars[0]); // last term
|
---|
[11799] | 148 | canonicalTerm = sb.ToString();
|
---|
| 149 | canonicalTermDictionary.Add(term, canonicalTerm);
|
---|
| 150 | }
|
---|
| 151 | return canonicalTerm;
|
---|
[11745] | 152 | }
|
---|
[11832] | 153 |
|
---|
| 154 | // splits the phrase into terms and creates (sparse) term-occurrance features
|
---|
| 155 | public IEnumerable<Feature> GetFeatures(string phrase) {
|
---|
| 156 | var canonicalTerms = new HashSet<string>();
|
---|
| 157 | foreach (string t in phrase.Split('+')) {
|
---|
| 158 | canonicalTerms.Add(CanonicalTerm(t));
|
---|
| 159 | }
|
---|
| 160 | return canonicalTerms.Select(entry => new Feature(entry, 1.0)).Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
|
---|
| 161 | }
|
---|
| 162 |
|
---|
[11846] | 163 | public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
|
---|
| 164 | var sb = new StringBuilder();
|
---|
| 165 |
|
---|
| 166 | TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
|
---|
| 167 |
|
---|
| 168 | return sb.ToString();
|
---|
| 169 | }
|
---|
| 170 |
|
---|
| 171 | private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
|
---|
| 172 | if (treeNode.SubtreeCount == 0) {
|
---|
| 173 | // terminal
|
---|
| 174 | sb.Append(treeNode.Symbol.Name);
|
---|
| 175 | } else {
|
---|
| 176 | string op = string.Empty;
|
---|
| 177 | switch (treeNode.Symbol.Name) {
|
---|
| 178 | case "S": op = "+"; break;
|
---|
| 179 | case "P": op = "*"; break;
|
---|
| 180 | default: {
|
---|
| 181 | Debug.Assert(treeNode.SubtreeCount == 1);
|
---|
| 182 | break;
|
---|
| 183 | }
|
---|
| 184 | }
|
---|
| 185 | // nonterminal
|
---|
| 186 | if (op == "+") sb.Append("(");
|
---|
| 187 | TreeToSentence(treeNode.Subtrees.First(), sb);
|
---|
| 188 | foreach (var subTree in treeNode.Subtrees.Skip(1)) {
|
---|
| 189 | sb.Append(op);
|
---|
| 190 | TreeToSentence(subTree, sb);
|
---|
| 191 | }
|
---|
| 192 | if (op == "+") sb.Append(")");
|
---|
| 193 | }
|
---|
| 194 | }
|
---|
[11659] | 195 | }
|
---|
| 196 | }
|
---|