source: branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/Analyzers/SymbolicRegressionTournamentPruning.cs @ 4857

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using System;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;

namespace HeuristicLab.Problems.DataAnalysis.Regression.Symbolic.Analyzers {
  public class SymbolicRegressionTournamentPruning : SingleSuccessorOperator, ISymbolicRegressionAnalyzer {
    private const string RandomParameterName = "Random";
    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    private const string DataAnalysisProblemDataParameterName = "DataAnalysisProblemData";
    private const string SamplesStartParameterName = "SamplesStart";
    private const string SamplesEndParameterName = "SamplesEnd";
    private const string EvaluatorParameterName = "Evaluator";
    private const string MaximizationParameterName = "Maximization";
    private const string SymbolicExpressionTreeInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    private const string UpperEstimationLimitParameterName = "UpperEstimationLimit";
    private const string LowerEstimationLimitParameterName = "LowerEstimationLimit";
    private const string MaxPruningRatioParameterName = "MaxPruningRatio";
    private const string TournamentSizeParameterName = "TournamentSize";
    private const string PopulationPercentileStartParameterName = "PopulationPercentileStart";
    private const string PopulationPercentileEndParameterName = "PopulationPercentileEnd";
    private const string QualityGainWeightParameterName = "QualityGainWeight";
    private const string IterationsParameterName = "Iterations";
    private const string FirstPruningGenerationParameterName = "FirstPruningGeneration";
    private const string PruningFrequencyParameterName = "PruningFrequency";
    private const string GenerationParameterName = "Generations";
    private const string ResultsParameterName = "Results";

    #region parameter properties
    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters[RandomParameterName]; }
    }
    public ScopeTreeLookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (ScopeTreeLookupParameter<SymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    }
    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ILookupParameter<DataAnalysisProblemData> DataAnalysisProblemDataParameter {
      get { return (ILookupParameter<DataAnalysisProblemData>)Parameters[DataAnalysisProblemDataParameterName]; }
    }
    public ILookupParameter<ISymbolicExpressionTreeInterpreter> SymbolicExpressionTreeInterpreterParameter {
      get { return (ILookupParameter<ISymbolicExpressionTreeInterpreter>)Parameters[SymbolicExpressionTreeInterpreterParameterName]; }
    }
    public IValueLookupParameter<DoubleValue> UpperEstimationLimitParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters[UpperEstimationLimitParameterName]; }
    }
    public IValueLookupParameter<DoubleValue> LowerEstimationLimitParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters[LowerEstimationLimitParameterName]; }
    }
    public IValueLookupParameter<IntValue> SamplesStartParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters[SamplesStartParameterName]; }
    }
    public IValueLookupParameter<IntValue> SamplesEndParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters[SamplesEndParameterName]; }
    }
    public IValueLookupParameter<PercentValue> RelativeNumberOfEvaluatedRowsParameters {
      get { return (IValueLookupParameter<PercentValue>)Parameters["RelativeNumberOfEvaluatedRows"]; }
    }
    public ILookupParameter<ISymbolicRegressionEvaluator> EvaluatorParameter {
      get { return (ILookupParameter<ISymbolicRegressionEvaluator>)Parameters[EvaluatorParameterName]; }
    }
    public ILookupParameter<BoolValue> MaximizationParameter {
      get { return (ILookupParameter<BoolValue>)Parameters[MaximizationParameterName]; }
    }
    public IValueLookupParameter<DoubleValue> MaxPruningRatioParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters[MaxPruningRatioParameterName]; }
    }
    public IValueLookupParameter<IntValue> TournamentSizeParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters[TournamentSizeParameterName]; }
    }
    public IValueLookupParameter<DoubleValue> PopulationPercentileStartParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters[PopulationPercentileStartParameterName]; }
    }
    public IValueLookupParameter<DoubleValue> PopulationPercentileEndParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters[PopulationPercentileEndParameterName]; }
    }
    public IValueLookupParameter<DoubleValue> QualityGainWeightParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters[QualityGainWeightParameterName]; }
    }
    public IValueLookupParameter<IntValue> IterationsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters[IterationsParameterName]; }
    }
    public IValueLookupParameter<IntValue> FirstPruningGenerationParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters[FirstPruningGenerationParameterName]; }
    }
    public IValueLookupParameter<IntValue> PruningFrequencyParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters[PruningFrequencyParameterName]; }
    }
    public ILookupParameter<IntValue> GenerationParameter {
      get { return (ILookupParameter<IntValue>)Parameters[GenerationParameterName]; }
    }
    public ILookupParameter<ResultCollection> ResultsParameter {
      get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
    }
    public IValueLookupParameter<BoolValue> ApplyPruningParameter {
      get { return (IValueLookupParameter<BoolValue>)Parameters["ApplyPruning"]; }
    }
    public IValueLookupParameter<IntValue> MinimalTreeSizeParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MinimalTreeSize"]; }
    }
    #endregion
    #region properties
    public IRandom Random {
      get { return RandomParameter.ActualValue; }
    }
    public ItemArray<SymbolicExpressionTree> SymbolicExpressionTree {
      get { return SymbolicExpressionTreeParameter.ActualValue; }
    }
    public DataAnalysisProblemData DataAnalysisProblemData {
      get { return DataAnalysisProblemDataParameter.ActualValue; }
    }
    public ISymbolicExpressionTreeInterpreter SymbolicExpressionTreeInterpreter {
      get { return SymbolicExpressionTreeInterpreterParameter.ActualValue; }
    }
    public DoubleValue UpperEstimationLimit {
      get { return UpperEstimationLimitParameter.ActualValue; }
    }
    public DoubleValue LowerEstimationLimit {
      get { return LowerEstimationLimitParameter.ActualValue; }
    }
    public IntValue SamplesStart {
      get { return SamplesStartParameter.ActualValue; }
    }
    public IntValue SamplesEnd {
      get { return SamplesEndParameter.ActualValue; }
    }
    public ISymbolicRegressionEvaluator Evaluator {
      get { return EvaluatorParameter.ActualValue; }
    }
    public BoolValue Maximization {
      get { return MaximizationParameter.ActualValue; }
    }
    public DoubleValue MaxPruningRatio {
      get { return MaxPruningRatioParameter.ActualValue; }
    }
    public IntValue TournamentSize {
      get { return TournamentSizeParameter.ActualValue; }
    }
    public DoubleValue PopulationPercentileStart {
      get { return PopulationPercentileStartParameter.ActualValue; }
    }
    public DoubleValue PopulationPercentileEnd {
      get { return PopulationPercentileEndParameter.ActualValue; }
    }
    public DoubleValue QualityGainWeight {
      get { return QualityGainWeightParameter.ActualValue; }
    }
    public IntValue Iterations {
      get { return IterationsParameter.ActualValue; }
    }
    public IntValue PruningFrequency {
      get { return PruningFrequencyParameter.ActualValue; }
    }
    public IntValue FirstPruningGeneration {
      get { return FirstPruningGenerationParameter.ActualValue; }
    }
    public IntValue Generation {
      get { return GenerationParameter.ActualValue; }
    }
    #endregion
    [StorableConstructor]
    protected SymbolicRegressionTournamentPruning(bool deserializing) : base(deserializing) { }
    public SymbolicRegressionTournamentPruning()
      : base() {
      Parameters.Add(new LookupParameter<IRandom>(RandomParameterName, "A random number generator."));
      Parameters.Add(new ScopeTreeLookupParameter<SymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to prune."));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality"));
      Parameters.Add(new LookupParameter<DataAnalysisProblemData>(DataAnalysisProblemDataParameterName, "The data analysis problem data to use for branch impact evaluation."));
      Parameters.Add(new LookupParameter<ISymbolicExpressionTreeInterpreter>(SymbolicExpressionTreeInterpreterParameterName, "The interpreter to use for node impact evaluation"));
      Parameters.Add(new ValueLookupParameter<IntValue>(SamplesStartParameterName, "The first row index of the dataset partition to use for branch impact evaluation."));
      Parameters.Add(new ValueLookupParameter<IntValue>(SamplesEndParameterName, "The last row index of the dataset partition to use for branch impact evaluation."));
      Parameters.Add(new LookupParameter<ISymbolicRegressionEvaluator>(EvaluatorParameterName, "The evaluator that should be used to determine which branches are not relevant."));
      Parameters.Add(new LookupParameter<BoolValue>(MaximizationParameterName, "The direction of optimization."));
      Parameters.Add(new ValueLookupParameter<BoolValue>("ApplyPruning"));
      Parameters.Add(new ValueLookupParameter<DoubleValue>(MaxPruningRatioParameterName, "The maximal relative size of the pruned branch.", new DoubleValue(0.5)));
      Parameters.Add(new ValueLookupParameter<IntValue>(TournamentSizeParameterName, "The number of branches to compare for pruning", new IntValue(10)));
      Parameters.Add(new ValueLookupParameter<DoubleValue>(PopulationPercentileStartParameterName, "The start of the population percentile to consider for pruning.", new DoubleValue(0.25)));
      Parameters.Add(new ValueLookupParameter<DoubleValue>(PopulationPercentileEndParameterName, "The end of the population percentile to consider for pruning.", new DoubleValue(0.75)));
      Parameters.Add(new ValueLookupParameter<DoubleValue>(QualityGainWeightParameterName, "The weight of the quality gain relative to the size gain.", new DoubleValue(1.0)));
      Parameters.Add(new ValueLookupParameter<DoubleValue>(UpperEstimationLimitParameterName, "The upper estimation limit to use for evaluation."));
      Parameters.Add(new ValueLookupParameter<DoubleValue>(LowerEstimationLimitParameterName, "The lower estimation limit to use for evaluation."));
      Parameters.Add(new ValueLookupParameter<IntValue>(IterationsParameterName, "The number of pruning iterations to apply for each tree.", new IntValue(1)));
      Parameters.Add(new ValueLookupParameter<IntValue>(FirstPruningGenerationParameterName, "The first generation when pruning should be applied.", new IntValue(1)));
      Parameters.Add(new ValueLookupParameter<IntValue>(PruningFrequencyParameterName, "The frequency of pruning operations (1: every generation, 2: every second generation...)", new IntValue(1)));
      Parameters.Add(new LookupParameter<IntValue>(GenerationParameterName, "The current generation."));
      Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName, "The results collection."));
      Parameters.Add(new ValueLookupParameter<PercentValue>("RelativeNumberOfEvaluatedRows", new PercentValue(1.0)));
      Parameters.Add(new ValueLookupParameter<IntValue>("MinimalTreeSize", new IntValue(15)));
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      #region compatibility remove before releasing 3.3.1
      if (!Parameters.ContainsKey(EvaluatorParameterName)) {
        Parameters.Add(new LookupParameter<ISymbolicRegressionEvaluator>(EvaluatorParameterName, "The evaluator which should be used to evaluate the solution on the validation set."));
      }
      if (!Parameters.ContainsKey(MaximizationParameterName)) {
        Parameters.Add(new LookupParameter<BoolValue>(MaximizationParameterName, "The direction of optimization."));
      }
      if (!Parameters.ContainsKey("ApplyPruning")) {
        Parameters.Add(new ValueLookupParameter<BoolValue>("ApplyPruning"));
      }
      if (!Parameters.ContainsKey("Quality")) {
        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality"));
      }
      if (!Parameters.ContainsKey("RelativeNumberOfEvaluatedRows")) {
        Parameters.Add(new ValueLookupParameter<PercentValue>("RelativeNumberOfEvaluatedRows", new PercentValue(1.0)));
      }
      if (!Parameters.ContainsKey("MinimalTreeSize")) {
        Parameters.Add(new ValueLookupParameter<IntValue>("MinimalTreeSize", new IntValue(15)));
      }

      #endregion
    }

    public override IOperation Apply() {
      bool pruningCondition =
        (ApplyPruningParameter.ActualValue.Value) &&
        (Generation.Value >= FirstPruningGeneration.Value) &&
        ((Generation.Value - FirstPruningGeneration.Value) % PruningFrequency.Value == 0);
      if (pruningCondition) {
        int n = SymbolicExpressionTree.Length;
        double percentileStart = PopulationPercentileStart.Value;
        double percentileEnd = PopulationPercentileEnd.Value;
        // for each tree in the given percentile
        ItemArray<SymbolicExpressionTree> trees = SymbolicExpressionTree;
        ItemArray<DoubleValue> quality = QualityParameter.ActualValue;
        bool maximization = Maximization.Value;
        var selectedTrees = (from index in Enumerable.Range(0, n)
                             orderby maximization ? -quality[index].Value : quality[index].Value
                             select new { Tree = trees[index], Quality = quality[index] })
                                                            .Skip((int)(n * percentileStart))
                                                            .Take((int)(n * (percentileEnd - percentileStart)));
        foreach (var pair in selectedTrees) {
          Prune(Random, pair.Tree, pair.Quality, Iterations.Value, TournamentSize.Value,
            DataAnalysisProblemData, SamplesStart.Value, SamplesEnd.Value, RelativeNumberOfEvaluatedRowsParameters.ActualValue.Value,
            SymbolicExpressionTreeInterpreter, Evaluator, Maximization.Value,
            LowerEstimationLimit.Value, UpperEstimationLimit.Value,
            MinimalTreeSizeParameter.ActualValue.Value, MaxPruningRatio.Value, QualityGainWeight.Value);
        }
      }
      return base.Apply();
    }

    public static void Prune(IRandom random, SymbolicExpressionTree tree, DoubleValue quality, int iterations, int tournamentSize,
      DataAnalysisProblemData problemData, int samplesStart, int samplesEnd, double relativeNumberOfEvaluatedRows,
      ISymbolicExpressionTreeInterpreter interpreter, ISymbolicRegressionEvaluator evaluator, bool maximization,
      double lowerEstimationLimit, double upperEstimationLimit,
      int minTreeSize, double maxPruningRatio, double qualityGainWeight) {

      
      int originalSize = tree.Size;
      // min size of the resulting pruned tree
      int minPrunedSize = (int)(originalSize * (1 - maxPruningRatio));
      minPrunedSize = Math.Max(minPrunedSize, minTreeSize);

      // use the same subset of rows for all iterations and for all pruning tournaments
      IEnumerable<int> rows = RandomEnumerable.SampleRandomNumbers(samplesStart, samplesEnd, (int)Math.Ceiling((samplesEnd - samplesStart) * relativeNumberOfEvaluatedRows));
      SymbolicExpressionTree prunedTree = tree;
      for (int iteration = 0; iteration < iterations; iteration++) {
        // maximally prune a branch such that the resulting tree size is not smaller than (1-maxPruningRatio) of the original tree
        int maxPrunedBranchSize = tree.Size - minPrunedSize;
        if (maxPrunedBranchSize > 0) {
          PruneTournament(prunedTree, quality, random, tournamentSize, maxPrunedBranchSize, maximization, qualityGainWeight, evaluator, interpreter, problemData.Dataset, problemData.TargetVariable.Value, rows, lowerEstimationLimit, upperEstimationLimit);
        }
      }
    }

    private class PruningPoint {
      public SymbolicExpressionTreeNode Parent { get; private set; }
      public SymbolicExpressionTreeNode Branch { get; private set; }
      public int SubTreeIndex { get; private set; }
      public PruningPoint(SymbolicExpressionTreeNode parent, SymbolicExpressionTreeNode branch, int index) {
        Parent = parent;
        Branch = branch;
        SubTreeIndex = index;
      }
    }

    private static void PruneTournament(SymbolicExpressionTree tree, DoubleValue quality, IRandom random, int tournamentSize,
      int maxPrunedBranchSize, bool maximization, double qualityGainWeight, ISymbolicRegressionEvaluator evaluator, ISymbolicExpressionTreeInterpreter interpreter,
      Dataset ds, string targetVariable, IEnumerable<int> rows, double lowerEstimationLimit, double upperEstimationLimit) {
      // make a clone for pruningEvaluation
      SymbolicExpressionTree pruningEvaluationTree = (SymbolicExpressionTree)tree.Clone();
      var prunePoints = (from node in pruningEvaluationTree.Root.SubTrees[0].IterateNodesPostfix()
                         from subTree in node.SubTrees
                         let subTreeSize = subTree.GetSize()
                         where subTreeSize <= maxPrunedBranchSize
                         where !(subTree.Symbol is Constant)
                         select new PruningPoint(node, subTree, node.SubTrees.IndexOf(subTree)))
         .ToList();
      double originalQuality = quality.Value;
      double originalSize = tree.Size;
      if (prunePoints.Count > 0) {
        double bestCoeff = double.PositiveInfinity;
        List<PruningPoint> tournamentGroup;
        if (prunePoints.Count > tournamentSize) {
          tournamentGroup = new List<PruningPoint>();
          for (int i = 0; i < tournamentSize; i++) {
            tournamentGroup.Add(prunePoints.SelectRandom(random));
          }
        } else {
          tournamentGroup = prunePoints;
        }
        foreach (PruningPoint prunePoint in tournamentGroup) {
          double replacementValue = CalculateReplacementValue(prunePoint.Branch, interpreter, ds, rows);

          // temporarily replace the branch with a constant
          prunePoint.Parent.RemoveSubTree(prunePoint.SubTreeIndex);
          var constNode = CreateConstant(replacementValue);
          prunePoint.Parent.InsertSubTree(prunePoint.SubTreeIndex, constNode);

          // evaluate the pruned tree
          double prunedQuality = evaluator.Evaluate(interpreter, pruningEvaluationTree,
  lowerEstimationLimit, upperEstimationLimit, ds, targetVariable, rows);

          double prunedSize = originalSize - prunePoint.Branch.GetSize() + 1;

          double coeff = CalculatePruningCoefficient(maximization, qualityGainWeight, originalQuality, originalSize, prunedQuality, prunedSize);
          if (coeff < bestCoeff) {
            bestCoeff = coeff;
            // clone the currently pruned tree
            SymbolicExpressionTree bestTree = (SymbolicExpressionTree)pruningEvaluationTree.Clone();

            // and update original tree and quality
            tree.Root = bestTree.Root;
            quality.Value = prunedQuality;
          }

          // restore tree that is used for pruning evaluation
          prunePoint.Parent.RemoveSubTree(prunePoint.SubTreeIndex);
          prunePoint.Parent.InsertSubTree(prunePoint.SubTreeIndex, prunePoint.Branch);
        }
      }
    }

    private static double CalculatePruningCoefficient(bool maximization, double qualityGainWeight, double originalQuality, double originalSize, double prunedQuality, double prunedSize) {
      // deteriation in quality:
      // exp: MSE : newMse < origMse (improvement) => prefer the larger improvement
      //      MSE : newMse > origMse (deteriation) => prefer the smaller deteriation
      //      MSE : minimize: newMse / origMse
      //      R²  : newR² > origR²   (improvment) => prefer the larger improvment
      //      R²  : newR² < origR²   (deteriation) => prefer smaller deteriation
      //      R²  : minimize: origR² / newR²
      double qualityDeteriation = maximization ? originalQuality / prunedQuality : prunedQuality / originalQuality;
      // size of the pruned tree is always smaller than the size of the original tree
      // same change in quality => prefer pruning operation that removes a larger tree
      return (qualityDeteriation * qualityGainWeight) / (originalSize / prunedSize);
    }

    private static double CalculateReplacementValue(SymbolicExpressionTreeNode branch, ISymbolicExpressionTreeInterpreter interpreter, Dataset ds, IEnumerable<int> rows) {
      SymbolicExpressionTreeNode start = (new StartSymbol()).CreateTreeNode();
      start.AddSubTree(branch);
      SymbolicExpressionTreeNode root = (new ProgramRootSymbol()).CreateTreeNode();
      root.AddSubTree(start);
      SymbolicExpressionTree tree = new SymbolicExpressionTree(root);
      IEnumerable<double> branchValues = interpreter.GetSymbolicExpressionTreeValues(tree, ds, rows);
      return branchValues.Average();
    }

    private static SymbolicExpressionTreeNode CreateConstant(double constantValue) {
      var node = (ConstantTreeNode)(new Constant()).CreateTreeNode();
      node.Value = constantValue;
      return node;
    }
  }
}