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

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.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.DataAnalysis;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;

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 BestTrainingQualityName = "Best R² (Training)";
    private readonly string BestTrainingSolutionName = "Best solution (Training)";
    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 AverageSentenceLengthName = "Avg. Sentence Length among Distinct";
    private readonly string OverwrittenSentencesName = "Sentences overwritten";
    private readonly string AnalyzersParameterName = "Analyzers";


    private readonly string SearchDataStructureParameterName = "Search Data Structure";
    private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";

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

    protected IValueParameter<IntValue> MaxTreeSizeParameter {
      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
    }
    public int MaxTreeSize {
      get { return MaxTreeSizeParameter.Value.Value; }
      set { MaxTreeSizeParameter.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 SymbolString BestTrainingSentence;

    #endregion

    public Dictionary<int, int> DistinctSentencesLength { get; private set; }  // Semantically distinct sentences and their length in a run.
    public HashSet<int> ArchivedPhrases { get; private set; }
    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; }

    private readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();

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

    public GrammarEnumerationAlgorithm() {
      Problem = new RegressionProblem() {
        ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenFunctionNine(seed: 1234).GenerateRegressionData()
      };

      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(6)));
      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(1000)));
      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.Stack)));

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

      foreach (var analyzer in Analyzers) {
        Analyzers.SetItemCheckedState(analyzer, false);
      }
      Analyzers.CheckedItemsChanged += AnalyzersOnCheckedItemsChanged;
    }

    public GrammarEnumerationAlgorithm(GrammarEnumerationAlgorithm original, Cloner cloner) : base(original, cloner) { }
    #endregion

    protected override void Run(CancellationToken cancellationToken) {
      #region init
      InitResults();

      ArchivedPhrases = new HashSet<int>();

      DistinctSentencesLength = new Dictionary<int, int>();
      AllGeneratedSentencesCount = 0;
      OverwrittenSentencesCount = 0;
      PhraseExpansionCount = 0;

      Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());

      OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
      var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
      var phrase0Hash = Grammar.CalcHashCode(phrase0);
      #endregion

      OpenPhrases.Store(phrase0Hash, phrase0);
      while (OpenPhrases.Count > 0) {
        if (cancellationToken.IsCancellationRequested) break;

        StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
        SymbolString currPhrase = fetchedPhrase.SymbolString;

        OnPhraseFetched(fetchedPhrase.Hash, currPhrase);

        ArchivedPhrases.Add(fetchedPhrase.Hash);

        // expand next nonterminal symbols
        int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
        NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;

        foreach (Production productionAlternative in expandedSymbol.Alternatives) {
          PhraseExpansionCount++;

          SymbolString newPhrase = new SymbolString(currPhrase.Count + productionAlternative.Count);
          newPhrase.AddRange(currPhrase);
          newPhrase.RemoveAt(nonterminalSymbolIndex);     // TODO: removeat and insertRange are both O(n)
          newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);

          if (newPhrase.Count <= MaxTreeSize) {
            var phraseHash = Grammar.CalcHashCode(newPhrase);

            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);

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

              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);

              if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count) {
                if (DistinctSentencesLength.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only

                DistinctSentencesLength[phraseHash] = newPhrase.Count;
                EvaluateSentence(newPhrase);

                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
              }
              UpdateView();

            } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
              OpenPhrases.Store(phraseHash, newPhrase);
            }
          }
        }
      }

      UpdateView(force: true);
      UpdateFinalResults();
    }

    #region Evaluation of generated models.

    // Evaluate sentence within an algorithm run.
    private void EvaluateSentence(SymbolString symbolString) {
      SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(symbolString);
      SymbolicRegressionModel model = new SymbolicRegressionModel(
        Problem.ProblemData.TargetVariable,
        tree,
        expressionTreeLinearInterpreter);

      var probData = Problem.ProblemData;
      var target = probData.TargetVariableTrainingValues;
      var estVals = model.GetEstimatedValues(probData.Dataset, probData.TrainingIndices);
      OnlineCalculatorError error;
      var r2 = OnlinePearsonsRSquaredCalculator.Calculate(target, estVals, out error);
      if (error != OnlineCalculatorError.None) r2 = 0.0;

      var bestR2 = ((DoubleValue)Results[BestTrainingQualityName].Value).Value;
      if (r2 > bestR2) {
        ((DoubleValue)Results[BestTrainingQualityName].Value).Value = r2;
        BestTrainingSentence = symbolString;
      }
    }

    #endregion

    #region Visualization in HL
    // Initialize entries in result set.
    private void InitResults() {
      BestTrainingSentence = null;

      Results.Add(new Result(BestTrainingQualityName, new DoubleValue(-1.0)));

      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(AverageSentenceLengthName, new DoubleValue(1.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 = DistinctSentencesLength.Count;
        ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
        ((DoubleValue)Results[AverageSentenceLengthName].Value).Value = DistinctSentencesLength.Select(pair => pair.Value).Average();
        ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
      }
    }

    // Generate all Results after an algorithm run.
    private void UpdateFinalResults() {
      SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence);
      SymbolicRegressionModel model = new SymbolicRegressionModel(
        Problem.ProblemData.TargetVariable,
        tree,
        new SymbolicDataAnalysisExpressionTreeLinearInterpreter());

      IRegressionSolution bestTrainingSolution = new RegressionSolution(model, Problem.ProblemData);
      Results.AddOrUpdateResult(BestTrainingSolutionName, bestTrainingSolution);
    }
    #endregion

    #region events
    private void AnalyzersOnCheckedItemsChanged(object sender, CollectionItemsChangedEventArgs<IGrammarEnumerationAnalyzer> collectionItemsChangedEventArgs) {
      foreach (IGrammarEnumerationAnalyzer grammarEnumerationAnalyzer in collectionItemsChangedEventArgs.Items) {
        if (Analyzers.ItemChecked(grammarEnumerationAnalyzer)) {
          grammarEnumerationAnalyzer.Register(this);
        } else {
          grammarEnumerationAnalyzer.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
}