source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs @ 15910

Last change on this file since 15910 was 15910, checked in by lkammere, 17 months ago

#2886: Fix length parameter when priorizing phrases and add weighting parameter to control exploration/exploitation during search, fix copy constructors in Analyzers

File size: 17.1 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Threading;
5using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
6using HeuristicLab.Collections;
7using HeuristicLab.Common;
8using HeuristicLab.Core;
9using HeuristicLab.Data;
10using HeuristicLab.Optimization;
11using HeuristicLab.Parameters;
12using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
13using HeuristicLab.Problems.DataAnalysis;
14
15namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
16  [Item("Grammar Enumeration Symbolic Regression", "Iterates all possible model structures for a fixed grammar.")]
17  [StorableClass]
18  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
19  public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
20    #region properties and result names
21    private readonly string SearchStructureSizeName = "Search Structure Size";
22    private readonly string GeneratedPhrasesName = "Generated/Archived Phrases";
23    private readonly string GeneratedSentencesName = "Generated Sentences";
24    private readonly string DistinctSentencesName = "Distinct Sentences";
25    private readonly string PhraseExpansionsName = "Phrase Expansions";
26    private readonly string AverageSentenceComplexityName = "Avg. Sentence Complexity among Distinct";
27    private readonly string OverwrittenSentencesName = "Sentences overwritten";
28    private readonly string AnalyzersParameterName = "Analyzers";
29    private readonly string ExpansionsPerSecondName = "Expansions per second";
30
31
32    private readonly string OptimizeConstantsParameterName = "Optimize Constants";
33    private readonly string ErrorWeightParameterName = "Error Weight";
34    private readonly string SearchDataStructureParameterName = "Search Data Structure";
35    private readonly string MaxComplexityParameterName = "Max. Complexity";
36    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
37
38    public override bool SupportsPause { get { return false; } }
39
40    protected IValueParameter<BoolValue> OptimizeConstantsParameter {
41      get { return (IValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
42    }
43
44    public bool OptimizeConstants {
45      get { return OptimizeConstantsParameter.Value.Value; }
46      set { OptimizeConstantsParameter.Value.Value = value; }
47    }
48
49    protected IValueParameter<IntValue> MaxComplexityParameter {
50      get { return (IValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
51    }
52    public int MaxComplexity {
53      get { return MaxComplexityParameter.Value.Value; }
54      set { MaxComplexityParameter.Value.Value = value; }
55    }
56
57    protected IValueParameter<DoubleValue> ErrorWeightParameter {
58      get { return (IValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
59    }
60    public double ErrorWeight {
61      get { return ErrorWeightParameter.Value.Value; }
62      set { ErrorWeightParameter.Value.Value = value; }
63    }
64
65    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
66      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
67    }
68    public int GuiUpdateInterval {
69      get { return GuiUpdateIntervalParameter.Value.Value; }
70      set { GuiUpdateIntervalParameter.Value.Value = value; }
71    }
72
73    protected IValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
74      get { return (IValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
75    }
76    public StorageType SearchDataStructure {
77      get { return SearchDataStructureParameter.Value.Value; }
78      set { SearchDataStructureParameter.Value.Value = value; }
79    }
80
81    public IFixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>> AnalyzersParameter {
82      get { return (IFixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>)Parameters[AnalyzersParameterName]; }
83    }
84
85    public ICheckedItemCollection<IGrammarEnumerationAnalyzer> Analyzers {
86      get { return AnalyzersParameter.Value; }
87    }
88
89    public SymbolString BestTrainingSentence { get; set; }     // Currently set in RSquaredEvaluator: quite hacky, but makes testing much easier for now...
90    #endregion
91
92    public Dictionary<int, int> DistinctSentencesComplexity { get; private set; }  // Semantically distinct sentences and their length in a run.
93    public HashSet<int> ArchivedPhrases { get; private set; }
94    internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree. 
95
96    #region execution stats
97    public int AllGeneratedSentencesCount { get; private set; }
98
99    public int OverwrittenSentencesCount { get; private set; } // It is not guaranteed that shorter solutions are found first.
100                                                               // When longer solutions are overwritten with shorter ones,
101                                                               // this counter is increased.
102    public int PhraseExpansionCount { get; private set; }      // Number, how many times a nonterminal symbol is replaced with a production rule.
103    #endregion
104
105    public Grammar Grammar { get; private set; }
106
107
108    #region ctors
109    public override IDeepCloneable Clone(Cloner cloner) {
110      return new GrammarEnumerationAlgorithm(this, cloner);
111    }
112
113    public GrammarEnumerationAlgorithm() {
114      Problem = new RegressionProblem() {
115        ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()
116      };
117
118      Parameters.Add(new ValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
119      Parameters.Add(new ValueParameter<DoubleValue>(ErrorWeightParameterName, "Defines, how much weight is put on a phrase's r² value when priorizing phrases during search.", new DoubleValue(0.8)));
120      Parameters.Add(new ValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
121      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
122      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue)));
123
124      var availableAnalyzers = new IGrammarEnumerationAnalyzer[] {
125        new SearchGraphVisualizer(),
126        new SentenceLogger(),
127        new RSquaredEvaluator()
128      };
129      Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>(
130        AnalyzersParameterName,
131        new CheckedItemCollection<IGrammarEnumerationAnalyzer>(availableAnalyzers).AsReadOnly()));
132
133      foreach (var analyzer in Analyzers) {
134        Analyzers.SetItemCheckedState(analyzer, false);
135      }
136      Analyzers.SetItemCheckedState(Analyzers.First(analyzer => analyzer is RSquaredEvaluator), true);
137      //Analyzers.SetItemCheckedState(Analyzers.First(analyzer => analyzer is SentenceLogger), true);
138    }
139
140    public GrammarEnumerationAlgorithm(GrammarEnumerationAlgorithm original, Cloner cloner) : base(original, cloner) {
141
142
143    }
144    #endregion
145
146    protected override void Run(CancellationToken cancellationToken) {
147      #region init
148      InitResults();
149
150      foreach (IGrammarEnumerationAnalyzer grammarEnumerationAnalyzer in Analyzers) {
151        if (Analyzers.ItemChecked(grammarEnumerationAnalyzer)) {
152          grammarEnumerationAnalyzer.Register(this);
153        } else {
154          grammarEnumerationAnalyzer.Deregister(this);
155        }
156      }
157
158      Analyzers.OfType<RSquaredEvaluator>().First().OptimizeConstants = OptimizeConstants;
159
160      ArchivedPhrases = new HashSet<int>();
161
162      DistinctSentencesComplexity = new Dictionary<int, int>();
163      AllGeneratedSentencesCount = 0;
164      OverwrittenSentencesCount = 0;
165      PhraseExpansionCount = 0;
166
167      Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
168
169      OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
170      var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
171      var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0);
172      #endregion
173
174      int maxSentenceLength = GetMaxSentenceLength();
175
176      OpenPhrases.Store(phrase0Hash, 0.0, phrase0);
177      while (OpenPhrases.Count > 0) {
178        if (cancellationToken.IsCancellationRequested) break;
179
180        StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
181        SymbolString currPhrase = fetchedPhrase.SymbolString;
182
183        OnPhraseFetched(fetchedPhrase.Hash, currPhrase);
184
185        ArchivedPhrases.Add(fetchedPhrase.Hash);
186
187        // expand next nonterminal symbols
188        int nonterminalSymbolIndex = currPhrase.NextNonterminalIndex();
189        NonterminalSymbol expandedSymbol = (NonterminalSymbol)currPhrase[nonterminalSymbolIndex];
190        var appliedProductions = Grammar.Productions[expandedSymbol];
191
192        for (int i = 0; i < appliedProductions.Count; i++) {
193          PhraseExpansionCount++;
194
195          SymbolString newPhrase = currPhrase.DerivePhrase(nonterminalSymbolIndex, appliedProductions[i]);
196          int newPhraseComplexity = Grammar.GetComplexity(newPhrase);
197
198          if (newPhraseComplexity <= MaxComplexity) {
199            var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase);
200
201            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
202
203            if (newPhrase.IsSentence()) {
204              AllGeneratedSentencesCount++;
205
206              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
207
208              // Is the best solution found? (only if RSquaredEvaluator is activated)
209              if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName)) {
210                double r2 = ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value;
211                if (r2.IsAlmost(1.0)) {
212                  UpdateView(force: true);
213                  return;
214                }
215              }
216
217              if (!DistinctSentencesComplexity.ContainsKey(phraseHash) || DistinctSentencesComplexity[phraseHash] > newPhraseComplexity) {
218                if (DistinctSentencesComplexity.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
219
220                DistinctSentencesComplexity[phraseHash] = newPhraseComplexity;
221                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
222              }
223              UpdateView();
224
225            } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
226              double phrasePriority = GetPriority(newPhrase, maxSentenceLength);
227              OpenPhrases.Store(phraseHash, phrasePriority, newPhrase);
228            }
229          }
230        }
231      }
232      UpdateView(force: true);
233    }
234
235    protected double GetPriority(SymbolString phrase, int maxSentenceLength) {
236      double relLength = (double)phrase.Count() / maxSentenceLength;
237
238      double r2 = Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
239      double error = 1.0 - r2;
240
241      return relLength + ErrorWeight * error;
242    }
243
244    private int GetMaxSentenceLength() {
245      SymbolString s = new SymbolString(Grammar.StartSymbol);
246
247      while (Grammar.GetComplexity(s) <= MaxComplexity) {
248        int expandedSymbolIndex = s.NextNonterminalIndex();
249        NonterminalSymbol expandedSymbol = (NonterminalSymbol)s[expandedSymbolIndex];
250
251        var productions = Grammar.Productions[expandedSymbol];
252        var longestProduction = productions // Find production with most terminal symbols to expand as much as possible...
253          .OrderBy(CountTerminals)          // but with lowest complexity/nonterminal count to keep complexity low.                                                                                     
254          .ThenByDescending(CountNonTerminals)
255          .First();
256
257        s = s.DerivePhrase(expandedSymbolIndex, longestProduction);
258      }
259
260      return s.Count();
261    }
262
263    private int CountTerminals(Production p) {
264      return p.Count(s => s is TerminalSymbol);
265    }
266
267    private int CountNonTerminals(Production p) {
268      return p.Count(s => s is NonterminalSymbol);
269    }
270
271    #region Visualization in HL
272    // Initialize entries in result set.
273    private void InitResults() {
274      Results.Add(new Result(GeneratedPhrasesName, new IntValue(0)));
275      Results.Add(new Result(SearchStructureSizeName, new IntValue(0)));
276      Results.Add(new Result(GeneratedSentencesName, new IntValue(0)));
277      Results.Add(new Result(DistinctSentencesName, new IntValue(0)));
278      Results.Add(new Result(PhraseExpansionsName, new IntValue(0)));
279      Results.Add(new Result(OverwrittenSentencesName, new IntValue(0)));
280      Results.Add(new Result(AverageSentenceComplexityName, new DoubleValue(1.0)));
281      Results.Add(new Result(ExpansionsPerSecondName, "In Thousand expansions per second", new IntValue(0)));
282    }
283
284    // Update the view for intermediate results in an algorithm run.
285    private int updates;
286    private void UpdateView(bool force = false) {
287      updates++;
288
289      if (force || updates % GuiUpdateInterval == 1) {
290        ((IntValue)Results[GeneratedPhrasesName].Value).Value = ArchivedPhrases.Count;
291        ((IntValue)Results[SearchStructureSizeName].Value).Value = OpenPhrases.Count;
292        ((IntValue)Results[GeneratedSentencesName].Value).Value = AllGeneratedSentencesCount;
293        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesComplexity.Count;
294        ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
295        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Select(pair => pair.Value).Average();
296        ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
297        ((IntValue)Results[ExpansionsPerSecondName].Value).Value = (int)((PhraseExpansionCount /
298                                                                          ExecutionTime.TotalSeconds) / 1000.0);
299      }
300    }
301    #endregion
302
303    #region events
304    public event EventHandler<PhraseEventArgs> PhraseFetched;
305    private void OnPhraseFetched(int hash, SymbolString symbolString) {
306      if (PhraseFetched != null) {
307        PhraseFetched(this, new PhraseEventArgs(hash, symbolString));
308      }
309    }
310
311    public event EventHandler<PhraseAddedEventArgs> PhraseDerived;
312    private void OnPhraseDerived(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
313      if (PhraseDerived != null) {
314        PhraseDerived(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
315      }
316    }
317
318    public event EventHandler<PhraseAddedEventArgs> SentenceGenerated;
319    private void OnSentenceGenerated(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
320      if (SentenceGenerated != null) {
321        SentenceGenerated(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
322      }
323    }
324
325    public event EventHandler<PhraseAddedEventArgs> DistinctSentenceGenerated;
326    private void OnDistinctSentenceGenerated(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
327      if (DistinctSentenceGenerated != null) {
328        DistinctSentenceGenerated(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
329      }
330    }
331
332    #endregion
333
334  }
335
336  #region events for analysis
337
338  public class PhraseEventArgs : EventArgs {
339    public int Hash { get; }
340
341    public SymbolString Phrase { get; }
342
343    public PhraseEventArgs(int hash, SymbolString phrase) {
344      Hash = hash;
345      Phrase = phrase;
346    }
347  }
348
349  public class PhraseAddedEventArgs : EventArgs {
350    public int ParentHash { get; }
351    public int NewHash { get; }
352
353    public SymbolString ParentPhrase { get; }
354    public SymbolString NewPhrase { get; }
355
356    public Symbol ExpandedSymbol { get; }
357
358    public Production ExpandedProduction { get; }
359
360    public PhraseAddedEventArgs(int parentHash, SymbolString parentPhrase, int newHash, SymbolString newPhrase, Symbol expandedSymbol, Production expandedProduction) {
361      ParentHash = parentHash;
362      ParentPhrase = parentPhrase;
363      NewHash = newHash;
364      NewPhrase = newPhrase;
365      ExpandedSymbol = expandedSymbol;
366      ExpandedProduction = expandedProduction;
367    }
368  }
369
370  #endregion
371}
Note: See TracBrowser for help on using the repository browser.