Changeset 4328

Timestamp:

08/26/10 12:46:41 (14 years ago)

Author:

gkronber

Message:

Overhauled pruning operator. #1142

File:

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

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

@@ -32 +32 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using System;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
 
 namespace HeuristicLab.Problems.DataAnalysis.Regression.Symbolic.Analyzers {
@@ -272 +273 @@
       double maxPruningRatio, double qualityGainWeight) {
 
+      int originalSize = tree.Size;
+
+      // min size of the resulting pruned tree
+      int minPrunedSize = (int)(originalSize * (1 - maxPruningRatio));
+
+      // 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));
-      int originalSize = tree.Size;
-
-      int minPrunedSize = (int)(originalSize * (1 - maxPruningRatio));
-      // tree for branch evaluation
-      SymbolicExpressionTree templateTree = (SymbolicExpressionTree)tree.Clone();
-      while (templateTree.Root.SubTrees[0].SubTrees.Count > 0) templateTree.Root.SubTrees[0].RemoveSubTree(0);
-
       SymbolicExpressionTree prunedTree = tree;
-      double currentQuality = quality.Value;
       for (int iteration = 0; iteration < iterations; iteration++) {
-        SymbolicExpressionTree iterationBestTree = prunedTree;
-        double bestGain = double.PositiveInfinity;
-        int maxPrunedBranchSize = (int)(prunedTree.Size * maxPruningRatio);
-
-        for (int i = 0; i < tournamentSize; i++) {
-          var clonedTree = (SymbolicExpressionTree)prunedTree.Clone();
-          int clonedTreeSize = clonedTree.Size;
-          var prunePoints = (from node in clonedTree.Root.SubTrees[0].IterateNodesPostfix()
-                             from subTree in node.SubTrees
-                             let subTreeSize = subTree.GetSize()
-                             where subTreeSize <= maxPrunedBranchSize
-                             where clonedTreeSize - subTreeSize >= minPrunedSize
-                             select new { Parent = node, Branch = subTree, SubTreeIndex = node.SubTrees.IndexOf(subTree) })
-                 .ToList();
-          if (prunePoints.Count > 0) {
-            var selectedPrunePoint = prunePoints.SelectRandom(random);
-            templateTree.Root.SubTrees[0].AddSubTree(selectedPrunePoint.Branch);
-            IEnumerable<double> branchValues = interpreter.GetSymbolicExpressionTreeValues(templateTree, problemData.Dataset, rows);
-            double branchMean = branchValues.Average();
-            templateTree.Root.SubTrees[0].RemoveSubTree(0);
-
-            selectedPrunePoint.Parent.RemoveSubTree(selectedPrunePoint.SubTreeIndex);
-            var constNode = CreateConstant(branchMean);
-            selectedPrunePoint.Parent.InsertSubTree(selectedPrunePoint.SubTreeIndex, constNode);
-
-            double prunedQuality = evaluator.Evaluate(interpreter, clonedTree,
-        lowerEstimationLimit, upperEstimationLimit, problemData.Dataset, problemData.TargetVariable.Value, rows);
-            double prunedSize = clonedTree.Size;
-            // 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 ? 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
-            double gain = (qualityDeteriation * qualityGainWeight) /
-                           (originalSize / prunedSize);
-            if (gain < bestGain) {
-              bestGain = gain;
-              iterationBestTree = clonedTree;
-              currentQuality = prunedQuality;
-            }
+        // 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;
         }
-        prunedTree = iterationBestTree;
-      }
-
-      quality.Value = currentQuality;
-      tree.Root = prunedTree.Root;
+        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();
     }