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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
using HeuristicLab.Collections;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.DataAnalysis;

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
  [Item("Grammar Enumeration Symbolic Regression", "Iterates all possible model structures for a fixed grammar.")]
  [StorableClass]
  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
  public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
    #region properties and result names
    private readonly string VariableImportanceWeightName = "Variable Importance Weight";
    private readonly string SearchStructureSizeName = "Search Structure Size";
    private readonly string GeneratedPhrasesName = "Generated/Archived Phrases";
    private readonly string GeneratedSentencesName = "Generated Sentences";
    private readonly string DistinctSentencesName = "Distinct Sentences";
    private readonly string PhraseExpansionsName = "Phrase Expansions";
    private readonly string AverageSentenceComplexityName = "Avg. Sentence Complexity among Distinct";
    private readonly string OverwrittenSentencesName = "Sentences overwritten";
    private readonly string AnalyzersParameterName = "Analyzers";
    private readonly string ExpansionsPerSecondName = "Expansions per second";

    private readonly string OptimizeConstantsParameterName = "Optimize Constants";
    private readonly string ErrorWeightParameterName = "Error Weight";
    private readonly string SearchDataStructureParameterName = "Search Data Structure";
    private readonly string MaxComplexityParameterName = "Max. Complexity";
    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
    private readonly string GrammarSymbolsParameterName = "Grammar Symbols";

    public override bool SupportsPause { get { return true; } }

    protected IValueParameter<DoubleValue> VariableImportanceWeightParameter {
      get { return (IValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }
    }

    protected double VariableImportanceWeight {
      get { return VariableImportanceWeightParameter.Value.Value; }
    }

    protected IValueParameter<BoolValue> OptimizeConstantsParameter {
      get { return (IValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
    }

    public bool OptimizeConstants {
      get { return OptimizeConstantsParameter.Value.Value; }
      set { OptimizeConstantsParameter.Value.Value = value; }
    }

    protected IValueParameter<IntValue> MaxComplexityParameter {
      get { return (IValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
    }
    public int MaxComplexity {
      get { return MaxComplexityParameter.Value.Value; }
      set { MaxComplexityParameter.Value.Value = value; }
    }

    protected IValueParameter<DoubleValue> ErrorWeightParameter {
      get { return (IValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
    }
    public double ErrorWeight {
      get { return ErrorWeightParameter.Value.Value; }
      set { ErrorWeightParameter.Value.Value = value; }
    }

    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
    }
    public int GuiUpdateInterval {
      get { return GuiUpdateIntervalParameter.Value.Value; }
      set { GuiUpdateIntervalParameter.Value.Value = value; }
    }

    protected IValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
      get { return (IValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
    }
    public StorageType SearchDataStructure {
      get { return SearchDataStructureParameter.Value.Value; }
      set { SearchDataStructureParameter.Value.Value = value; }
    }

    public IFixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>> AnalyzersParameter {
      get { return (IFixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>)Parameters[AnalyzersParameterName]; }
    }

    public ICheckedItemCollection<IGrammarEnumerationAnalyzer> Analyzers {
      get { return AnalyzersParameter.Value; }
    }

    public IFixedValueParameter<ReadOnlyCheckedItemCollection<EnumValue<GrammarRule>>> GrammarSymbolsParameter {
      get { return (IFixedValueParameter<ReadOnlyCheckedItemCollection<EnumValue<GrammarRule>>>)Parameters[GrammarSymbolsParameterName]; }
    }

    public ReadOnlyCheckedItemCollection<EnumValue<GrammarRule>> GrammarSymbols {
      get { return GrammarSymbolsParameter.Value; }
    }

    public SymbolString BestTrainingSentence { get; set; }     // Currently set in RSquaredEvaluator: quite hacky, but makes testing much easier for now...
    #endregion

    [Storable]
    public Dictionary<int, int> DistinctSentencesComplexity { get; private set; }  // Semantically distinct sentences and their length in a run.

    [Storable]
    public HashSet<int> ArchivedPhrases { get; private set; }

    [Storable]
    internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree.  

    #region execution stats
    public int AllGeneratedSentencesCount { get; private set; }

    public int OverwrittenSentencesCount { get; private set; } // It is not guaranteed that shorter solutions are found first. 
                                                               // When longer solutions are overwritten with shorter ones, 
                                                               // this counter is increased.
    public int PhraseExpansionCount { get; private set; }      // Number, how many times a nonterminal symbol is replaced with a production rule.
    #endregion

    public Grammar Grammar { get; private set; }

    #region ctors
    public override IDeepCloneable Clone(Cloner cloner) {
      return new GrammarEnumerationAlgorithm(this, cloner);
    }

    public GrammarEnumerationAlgorithm() {
      Parameters.Add(new ValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0)));
      Parameters.Add(new ValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
      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)));
      Parameters.Add(new ValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue)));

      var availableAnalyzers = new IGrammarEnumerationAnalyzer[] {
        new SearchGraphVisualizer(),
        new SentenceLogger(),
        new RSquaredEvaluator()
      };
      Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>(
        AnalyzersParameterName,
        new CheckedItemCollection<IGrammarEnumerationAnalyzer>(availableAnalyzers).AsReadOnly()));

      Analyzers.CheckedItemsChanged += Analyzers_CheckedItemsChanged;

      foreach (var analyzer in Analyzers) {
        Analyzers.SetItemCheckedState(analyzer, false);
      }
      Analyzers.SetItemCheckedState(Analyzers.First(analyzer => analyzer is RSquaredEvaluator), true);

      var grammarSymbols = Enum.GetValues(typeof(GrammarRule))
        .Cast<GrammarRule>()
        .Select(v => new EnumValue<GrammarRule>(v));

      Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<EnumValue<GrammarRule>>>(
        GrammarSymbolsParameterName,
        new ReadOnlyCheckedItemCollection<EnumValue<GrammarRule>>(new CheckedItemCollection<EnumValue<GrammarRule>>(grammarSymbols))
      ));
      foreach (EnumValue<GrammarRule> grammarSymbol in GrammarSymbols) {
        GrammarSymbols.SetItemCheckedState(grammarSymbol, true);
      }

      // set a default problem
      Problem = new RegressionProblem() {
        ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()
      };
    }

    public GrammarEnumerationAlgorithm(GrammarEnumerationAlgorithm original, Cloner cloner) : base(original, cloner) {
      foreach (var analyzer in Analyzers.CheckedItems)
        analyzer.Register(this);
      Analyzers.CheckedItemsChanged += Analyzers_CheckedItemsChanged;

      DistinctSentencesComplexity = new Dictionary<int, int>(original.DistinctSentencesComplexity);
      ArchivedPhrases = new HashSet<int>(original.ArchivedPhrases);
      OpenPhrases = cloner.Clone(original.OpenPhrases);

      AllGeneratedSentencesCount = original.AllGeneratedSentencesCount;
      OverwrittenSentencesCount = original.OverwrittenSentencesCount;
      PhraseExpansionCount = original.PhraseExpansionCount;
      Grammar = cloner.Clone(original.Grammar);

      if (original.variableImportance != null)
        variableImportance = new Dictionary<VariableTerminalSymbol, double>(original.variableImportance);
    }
    #endregion

    private Dictionary<VariableTerminalSymbol, double> variableImportance;

    public override void Prepare() {
      DistinctSentencesComplexity = new Dictionary<int, int>();
      ArchivedPhrases = new HashSet<int>();
      AllGeneratedSentencesCount = 0;
      OverwrittenSentencesCount = 0;
      PhraseExpansionCount = 0;

      Analyzers.OfType<RSquaredEvaluator>().First().OptimizeConstants = OptimizeConstants;
      Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray(), GrammarSymbols.CheckedItems.Select(v => v.Value));
      OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy

      base.Prepare(); // this actually clears the results which will get reinitialized on Run()
    }

    private Dictionary<VariableTerminalSymbol, double> CalculateVariableImportances() {
      variableImportance = new Dictionary<VariableTerminalSymbol, double>();

      RandomForestRegression rf = new RandomForestRegression();
      rf.Problem = Problem;
      rf.Start();
      IRegressionSolution rfSolution = (RandomForestRegressionSolution)rf.Results["Random forest regression solution"].Value;
      var rfImpacts = RegressionSolutionVariableImpactsCalculator.CalculateImpacts(
        rfSolution,
        RegressionSolutionVariableImpactsCalculator.DataPartitionEnum.Training,
        RegressionSolutionVariableImpactsCalculator.ReplacementMethodEnum.Shuffle);

      // save the normalized importances
      var sum = rfImpacts.Sum(x => x.Item2);
      foreach (Tuple<string, double> rfImpact in rfImpacts) {
        VariableTerminalSymbol varSym = Grammar.VarTerminals.First(v => v.StringRepresentation == rfImpact.Item1);
        variableImportance[varSym] = rfImpact.Item2 / sum;
      }
      return variableImportance;
    }

    protected override void Run(CancellationToken cancellationToken) {
      // do not reinitialize the algorithm if we're resuming from pause
      if (previousExecutionState != ExecutionState.Paused) {
        CalculateVariableImportances();
        InitResults();
        var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
        var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0);
        OpenPhrases.Store(new SearchNode(phrase0Hash, 0.0, 0.0, phrase0));
      }

      int maxSentenceLength = GetMaxSentenceLength();
      var errorWeight = ErrorWeight;
      var variableImportanceWeight = VariableImportanceWeight;
      // main search loop
      while (OpenPhrases.Count > 0) {
        if (cancellationToken.IsCancellationRequested)
          break;

        SearchNode fetchedSearchNode = OpenPhrases.GetNext();
        SymbolString currPhrase = fetchedSearchNode.SymbolString;

        OnPhraseFetched(fetchedSearchNode.Hash, currPhrase);

        ArchivedPhrases.Add(fetchedSearchNode.Hash);

        // expand next nonterminal symbols
        int nonterminalSymbolIndex = currPhrase.NextNonterminalIndex();
        NonterminalSymbol expandedSymbol = (NonterminalSymbol)currPhrase[nonterminalSymbolIndex];
        var appliedProductions = Grammar.Productions[expandedSymbol];

        for (int i = 0; i < appliedProductions.Count; i++) {
          PhraseExpansionCount++;

          SymbolString newPhrase = currPhrase.DerivePhrase(nonterminalSymbolIndex, appliedProductions[i]);
          int newPhraseComplexity = Grammar.GetComplexity(newPhrase);

          if (newPhraseComplexity > MaxComplexity)
            continue;

          var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase);

          OnPhraseDerived(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);

          if (newPhrase.IsSentence()) {
            AllGeneratedSentencesCount++;

            OnSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);

            // Is the best solution found? (only if RSquaredEvaluator is activated)
            if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName)) {
              double r2 = ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value;
              if (r2.IsAlmost(1.0)) {
                UpdateView(force: true);
                return;
              }
            }

            if (!DistinctSentencesComplexity.ContainsKey(phraseHash) || DistinctSentencesComplexity[phraseHash] > newPhraseComplexity) {
              if (DistinctSentencesComplexity.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only

              DistinctSentencesComplexity[phraseHash] = newPhraseComplexity;
              OnDistinctSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
            }
            UpdateView();

          } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {

            double r2 = GetR2(newPhrase, fetchedSearchNode.R2);
            double phrasePriority = GetPriority(newPhrase, r2, maxSentenceLength, errorWeight, variableImportanceWeight);

            SearchNode newSearchNode = new SearchNode(phraseHash, phrasePriority, r2, newPhrase);
            OpenPhrases.Store(newSearchNode);
          }
        }
      }
      UpdateView(force: true);
    }

    protected double GetPriority(SymbolString phrase, double r2, int maxSentenceLength, double errorWeight, double variableImportanceWeight) {
      var distinctVars = phrase.OfType<VariableTerminalSymbol>().Distinct();

      var sum = 0d;
      foreach (var v in distinctVars) {
        sum += variableImportance[v];
      }
      var phraseVariableImportance = 1 - sum;

      double relLength = (double)phrase.Count() / maxSentenceLength;
      double error = 1.0 - r2;

      return relLength + errorWeight * error + variableImportanceWeight * phraseVariableImportance;
    }

    private double GetR2(SymbolString phrase, double parentR2) {
      int length = phrase.Count();

      // If the only nonterminal symbol is Expr, we can need to evaluate the sentence. Otherwise
      // the phrase has the same r2 as its parent, from which it was derived.
      for (int i = 0; i < length; i++) {
        if (phrase[i] is NonterminalSymbol && phrase[i] != Grammar.Expr) {
          return parentR2;
        }
      }

      return Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
    }

    private int GetMaxSentenceLength() {
      SymbolString s = new SymbolString(Grammar.StartSymbol);

      while (!s.IsSentence() && Grammar.GetComplexity(s) <= MaxComplexity) {
        int expandedSymbolIndex = s.NextNonterminalIndex();
        NonterminalSymbol expandedSymbol = (NonterminalSymbol)s[expandedSymbolIndex];

        var productions = Grammar.Productions[expandedSymbol];
        var longestProduction = productions // Find production with most terminal symbols to expand as much as possible...
          .OrderBy(CountTerminals)          // but with lowest complexity/nonterminal count to keep complexity low.                                                                                     
          .ThenByDescending(CountNonTerminals)
          .First();

        s = s.DerivePhrase(expandedSymbolIndex, longestProduction);
      }

      return s.Count();
    }

    private int CountTerminals(Production p) {
      return p.Count(s => s is TerminalSymbol);
    }

    private int CountNonTerminals(Production p) {
      return p.Count(s => s is NonterminalSymbol);
    }

    #region pause support
    private ExecutionState previousExecutionState;
    protected override void OnPaused() {
      previousExecutionState = this.ExecutionState;
      base.OnPaused();
    }
    protected override void OnPrepared() {
      previousExecutionState = this.ExecutionState;
      base.OnPrepared();
    }
    protected override void OnStarted() {
      previousExecutionState = this.ExecutionState;
      base.OnStarted();
    }
    protected override void OnStopped() {
      previousExecutionState = this.ExecutionState;
      base.OnStopped();
    }
    #endregion

    #region Visualization in HL
    // Initialize entries in result set.
    private void InitResults() {
      Results.Clear();
      Results.Add(new Result(GeneratedPhrasesName, new IntValue(0)));
      Results.Add(new Result(SearchStructureSizeName, new IntValue(0)));
      Results.Add(new Result(GeneratedSentencesName, new IntValue(0)));
      Results.Add(new Result(DistinctSentencesName, new IntValue(0)));
      Results.Add(new Result(PhraseExpansionsName, new IntValue(0)));
      Results.Add(new Result(OverwrittenSentencesName, new IntValue(0)));
      Results.Add(new Result(AverageSentenceComplexityName, new DoubleValue(1.0)));
      Results.Add(new Result(ExpansionsPerSecondName, "In Thousand expansions per second", new IntValue(0)));
    }

    // Update the view for intermediate results in an algorithm run.
    private int updates;
    private void UpdateView(bool force = false) {
      updates++;

      if (force || updates % GuiUpdateInterval == 1) {
        ((IntValue)Results[GeneratedPhrasesName].Value).Value = ArchivedPhrases.Count;
        ((IntValue)Results[SearchStructureSizeName].Value).Value = OpenPhrases.Count;
        ((IntValue)Results[GeneratedSentencesName].Value).Value = AllGeneratedSentencesCount;
        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesComplexity.Count;
        ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Select(pair => pair.Value).Average();
        ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
        ((IntValue)Results[ExpansionsPerSecondName].Value).Value = (int)((PhraseExpansionCount /
                                                                          ExecutionTime.TotalSeconds) / 1000.0);
      }
    }
    #endregion

    #region events

    // private event handlers for analyzers
    private void Analyzers_CheckedItemsChanged(object sender, CollectionItemsChangedEventArgs<IGrammarEnumerationAnalyzer> args) {
      // newly added items
      foreach (var item in args.Items.Except(args.OldItems).Union(args.OldItems.Except(args.Items))) {
        if (Analyzers.ItemChecked(item)) {
          item.Register(this);
        } else {
          item.Deregister(this);
        }
      }
    }

    public event EventHandler<PhraseEventArgs> PhraseFetched;
    private void OnPhraseFetched(int hash, SymbolString symbolString) {
      if (PhraseFetched != null) {
        PhraseFetched(this, new PhraseEventArgs(hash, symbolString));
      }
    }

    public event EventHandler<PhraseAddedEventArgs> PhraseDerived;
    private void OnPhraseDerived(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
      if (PhraseDerived != null) {
        PhraseDerived(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
      }
    }

    public event EventHandler<PhraseAddedEventArgs> SentenceGenerated;
    private void OnSentenceGenerated(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
      if (SentenceGenerated != null) {
        SentenceGenerated(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
      }
    }

    public event EventHandler<PhraseAddedEventArgs> DistinctSentenceGenerated;
    private void OnDistinctSentenceGenerated(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
      if (DistinctSentenceGenerated != null) {
        DistinctSentenceGenerated(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
      }
    }

    #endregion

  }

  #region events for analysis

  public class PhraseEventArgs : EventArgs {
    public int Hash { get; }

    public SymbolString Phrase { get; }

    public PhraseEventArgs(int hash, SymbolString phrase) {
      Hash = hash;
      Phrase = phrase;
    }
  }

  public class PhraseAddedEventArgs : EventArgs {
    public int ParentHash { get; }
    public int NewHash { get; }

    public SymbolString ParentPhrase { get; }
    public SymbolString NewPhrase { get; }

    public Symbol ExpandedSymbol { get; }

    public Production ExpandedProduction { get; }

    public PhraseAddedEventArgs(int parentHash, SymbolString parentPhrase, int newHash, SymbolString newPhrase, Symbol expandedSymbol, Production expandedProduction) {
      ParentHash = parentHash;
      ParentPhrase = parentPhrase;
      NewHash = newHash;
      NewPhrase = newPhrase;
      ExpandedSymbol = expandedSymbol;
      ExpandedProduction = expandedProduction;
    }
  }

  #endregion
}