Changeset 4297 for branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/Analyzers/SymbolicRegressionTournamentPruning.cs

Timestamp:

08/23/10 18:54:35 (14 years ago)

Author:

gkronber

Message:

Added output parameter for validation quality to validation analyzer, added input parameter for validation quality to overfitting analyzer, and fixed bugs in pruning operator. #1142

File:

• branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/Analyzers/SymbolicRegressionTournamentPruning.cs (modified) (18 diffs)

branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/Analyzers/SymbolicRegressionTournamentPruning.cs

@@ -31 +31 @@
 using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
 
 namespace HeuristicLab.Problems.DataAnalysis.Regression.Symbolic.Analyzers {
@@ -62 +63 @@
       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]; }
@@ -80 +84 @@
       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]; }
@@ -115 +122 @@
     public ILookupParameter<ResultCollection> ResultsParameter {
       get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
+    }
+    public IValueLookupParameter<BoolValue> ApplyPruningParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["ApplyPruning"]; }
     }
     #endregion
@@ -176 +186 @@
     }
     #endregion
+    [StorableConstructor]
     protected SymbolicRegressionTournamentPruning(bool deserializing) : base(deserializing) { }
     public SymbolicRegressionTournamentPruning()
@@ -181 +192 @@
       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"));
@@ -187 +199 @@
       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)));
@@ -199 +212 @@
       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)));
     }
 
@@ -210 +224 @@
         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)));
+      }
+
       #endregion
     }
@@ -215 +239 @@
     public override IOperation Apply() {
       bool pruningCondition =
+        (ApplyPruningParameter.ActualValue.Value) &&
         (Generation.Value >= FirstPruningGeneration.Value) &&
         ((Generation.Value - FirstPruningGeneration.Value) % PruningFrequency.Value == 0);
@@ -222 +247 @@
         double percentileEnd = PopulationPercentileEnd.Value;
         // for each tree in the given percentile
-        var trees = SymbolicExpressionTree
-          .Skip((int)(n * percentileStart))
-          .Take((int)(n * (percentileEnd - percentileStart)));
-        foreach (var tree in trees) {
-          Prune(Random, tree, Iterations.Value, TournamentSize.Value,
-            DataAnalysisProblemData, SamplesStart.Value, SamplesEnd.Value,
+        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,
@@ -236 +266 @@
     }
 
-    public static void Prune(IRandom random, SymbolicExpressionTree tree, int iterations, int tournamentSize,
-      DataAnalysisProblemData problemData, int samplesStart, int samplesEnd,
+    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,
       double maxPruningRatio, double qualityGainWeight) {
-      IEnumerable<int> rows = Enumerable.Range(samplesStart, samplesEnd - samplesStart);
+
+      IEnumerable<int> rows = RandomEnumerable.SampleRandomNumbers(samplesStart, samplesEnd, (int)Math.Ceiling((samplesEnd - samplesStart) * relativeNumberOfEvaluatedRows));
       int originalSize = tree.Size;
-      double originalQuality = evaluator.Evaluate(interpreter, tree,
-        lowerEstimationLimit, upperEstimationLimit, problemData.Dataset, problemData.TargetVariable.Value, rows);
 
       int minPrunedSize = (int)(originalSize * (1 - maxPruningRatio));
-
       // tree for branch evaluation
       SymbolicExpressionTree templateTree = (SymbolicExpressionTree)tree.Clone();
@@ -253 +281 @@
 
       SymbolicExpressionTree prunedTree = tree;
+      double currentQuality = quality.Value;
       for (int iteration = 0; iteration < iterations; iteration++) {
         SymbolicExpressionTree iterationBestTree = prunedTree;
@@ -261 +290 @@
           var clonedTree = (SymbolicExpressionTree)prunedTree.Clone();
           int clonedTreeSize = clonedTree.Size;
-          var prunePoints = (from node in clonedTree.IterateNodesPostfix()
+          var prunePoints = (from node in clonedTree.Root.SubTrees[0].IterateNodesPostfix()
                              from subTree in node.SubTrees
                              let subTreeSize = subTree.GetSize()
@@ -280 +309 @@
 
             double prunedQuality = evaluator.Evaluate(interpreter, clonedTree,
-        lowerEstimationLimit, upperEstimationLimit, problemData.Dataset, problemData.TargetVariable.Value, Enumerable.Range(samplesStart, samplesEnd - samplesStart));
+        lowerEstimationLimit, upperEstimationLimit, problemData.Dataset, problemData.TargetVariable.Value, rows);
             double prunedSize = clonedTree.Size;
             // deteriation in quality:
@@ -289 +318 @@
             //      R²  : newR² < origR²   (deteriation) => prefer smaller deteriation
             //      R²  : minimize: origR² / newR²
-            double qualityDeteriation = maximization ? originalQuality / prunedQuality : prunedQuality / originalQuality;
+            double qualityDeteriation = maximization ? quality.Value / prunedQuality : prunedQuality / quality.Value;
             // 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
@@ -297 +326 @@
               bestGain = gain;
               iterationBestTree = clonedTree;
+              currentQuality = prunedQuality;
             }
           }
@@ -302 +332 @@
         prunedTree = iterationBestTree;
       }
+
+      quality.Value = currentQuality;
       tree.Root = prunedTree.Root;
     }