Changeset 12619

Timestamp:

07/06/15 18:33:24 (9 years ago)

Author:

gkronber

Message:

#2261: replace recursion by a stack to prepare for unbalanced tree expansion

Location:

branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees

Files:

• GradientBoostedTreesAlgorithm.cs (modified) (1 diff)
• RegressionTreeBuilder.cs (modified) (9 diffs)

branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs

@@ -242 +242 @@
 
           var classificationSolution = new DiscriminantFunctionClassificationSolution(model, classificationProblemData);
-          Results.Add(new Result("Solution (classification)", classificationSolution));
+          Results.Add(new Result("Solution", classificationSolution));
         } else {
           // otherwise we produce a regression solution

branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs

@@ -24 +24 @@
 using System.Collections.Generic;
 using System.Diagnostics;
-using System.Diagnostics.Contracts;
 using System.Linq;
 using HeuristicLab.Core;
@@ -64 +63 @@
     private int curTreeNodeIdx; // the index where the next tree node is stored
 
-    private readonly IList<RegressionTreeModel.TreeNode> nodeQueue; 
+    private class Partition {
+      public int TreeNodeIdx { get; set; }
+      public int Depth { get; set; }
+      public int StartIdx { get; set; }
+      public int EndIndex { get; set; }
+      public bool Left { get; set; }
+    }
+    private readonly IList<Partition> queue;
 
     // prepare and allocate buffer variables in ctor
@@ -88 +94 @@
       outx = new double[rows];
       outSortedIdx = new int[rows];
-      nodeQueue = new List<RegressionTreeModel.TreeNode>();
+      queue = new List<Partition>();
 
       x = new double[nCols][];
@@ -120 +126 @@
 
       var model = CreateRegressionTreeForGradientBoosting(y, maxDepth, problemData.TrainingIndices.ToArray(), seLoss.GetLineSearchFunc(y, zeros, ones), r, m);
+
       return new GradientBoostedTreesModel(new[] { new ConstantRegressionModel(yAvg), model }, new[] { 1.0, 1.0 });
     }
@@ -125 +132 @@
     // specific interface that allows to specify the target labels and the training rows which is necessary when for gradient boosted trees
     public IRegressionModel CreateRegressionTreeForGradientBoosting(double[] y, int maxDepth, int[] idx, LineSearchFunc lineSearch, double r = 0.5, double m = 0.5) {
-      Contract.Assert(maxDepth > 0);
-      Contract.Assert(r > 0);
-      Contract.Assert(r <= 1.0);
-      Contract.Assert(y.Count() == this.y.Length);
-      Contract.Assert(m > 0);
-      Contract.Assert(m <= 1.0);
+      Debug.Assert(maxDepth > 0);
+      Debug.Assert(r > 0);
+      Debug.Assert(r <= 1.0);
+      Debug.Assert(y.Count() == this.y.Length);
+      Debug.Assert(m > 0);
+      Debug.Assert(m <= 1.0);
 
       this.y = y; // y is changed in gradient boosting
@@ -172 +179 @@
 
       // start and end idx are inclusive
-      CreateRegressionTreeForIdx(maxDepth, 0, effectiveRows - 1, lineSearch);
+      queue.Add(new Partition() { TreeNodeIdx = -1, Depth = maxDepth, StartIdx = 0, EndIndex = effectiveRows - 1 });
+      CreateRegressionTreeForIdx(lineSearch);
+
       return new RegressionTreeModel(tree);
     }
 
-    // recursive routine for building the tree for the row idx stored in internalIdx between startIdx and endIdx
+    private void CreateRegressionTreeForIdx(LineSearchFunc lineSearch) {
+      while (queue.Any()) {
+        var f = queue[0]; // actually a stack
+        queue.RemoveAt(0);
+
+        var depth = f.Depth;
+        var startIdx = f.StartIdx;
+        var endIdx = f.EndIndex;
+
+        Debug.Assert(endIdx - startIdx >= 0);
+        Debug.Assert(startIdx >= 0);
+        Debug.Assert(endIdx < internalIdx.Length);
+
+        double threshold;
+        string bestVariableName;
+
+        // stop when only one row is left or no split is possible
+        if (depth <= 1 || endIdx - startIdx == 0 || !FindBestVariableAndThreshold(startIdx, endIdx, out threshold, out bestVariableName)) {
+          CreateLeafNode(startIdx, endIdx, lineSearch);
+          if (f.TreeNodeIdx >= 0) if (f.Left) {
+              tree[f.TreeNodeIdx].leftIdx = curTreeNodeIdx;
+            } else {
+              tree[f.TreeNodeIdx].rightIdx = curTreeNodeIdx;
+            }
+          curTreeNodeIdx++;
+        } else {
+          int splitIdx;
+          CreateInternalNode(f.StartIdx, f.EndIndex, bestVariableName, threshold, out splitIdx);
+
+          // connect to parent tree
+          if (f.TreeNodeIdx >= 0) if (f.Left) {
+              tree[f.TreeNodeIdx].leftIdx = curTreeNodeIdx;
+            } else {
+              tree[f.TreeNodeIdx].rightIdx = curTreeNodeIdx;
+            }
+
+          Debug.Assert(splitIdx + 1 <= endIdx);
+          Debug.Assert(startIdx <= splitIdx);
+
+          queue.Insert(0, new Partition() { TreeNodeIdx = curTreeNodeIdx, Left = false, Depth = depth - 1, StartIdx = splitIdx + 1, EndIndex = endIdx });
+          queue.Insert(0, new Partition() { TreeNodeIdx = curTreeNodeIdx, Left = true, Depth = depth - 1, StartIdx = startIdx, EndIndex = splitIdx }); // left part before right part (stack organization)
+          curTreeNodeIdx++;
+
+        }
+      }
+    }
+
+
+    private void CreateLeafNode(int startIdx, int endIdx, LineSearchFunc lineSearch) {
+      // max depth reached or only one element    
+      tree[curTreeNodeIdx].varName = RegressionTreeModel.TreeNode.NO_VARIABLE;
+      tree[curTreeNodeIdx].val = lineSearch(internalIdx, startIdx, endIdx);
+    }
+
+    // routine for building the tree for the row idx stored in internalIdx between startIdx and endIdx
     // the lineSearch function calculates the optimal prediction value for tree leaf nodes 
     // (in the case of squared errors it is the average of target values for the rows represented by the node)
     // startIdx and endIdx are inclusive
-    private void CreateRegressionTreeForIdx(int maxDepth, int startIdx, int endIdx, LineSearchFunc lineSearch) {
-      Contract.Assert(endIdx - startIdx >= 0);
-      Contract.Assert(startIdx >= 0);
-      Contract.Assert(endIdx < internalIdx.Length);
-
-      // TODO: stop when y is constant
-      // TODO: use priority queue of nodes to be expanded (sorted by improvement) instead of the recursion to maximum depth
-      if (maxDepth <= 1 || endIdx - startIdx == 0) {
-        // max depth reached or only one element    
-        tree[curTreeNodeIdx].varName = RegressionTreeModel.TreeNode.NO_VARIABLE;
-        tree[curTreeNodeIdx].val = lineSearch(internalIdx, startIdx, endIdx);
-        curTreeNodeIdx++;
-      } else {
-        int i, j;
-        double threshold;
-        string bestVariableName;
-        FindBestVariableAndThreshold(startIdx, endIdx, out threshold, out bestVariableName);
-
-        // if bestVariableName is NO_VARIABLE then no split was possible anymore
-        if (bestVariableName == RegressionTreeModel.TreeNode.NO_VARIABLE) {
-          // max depth reached or only one element    
-          tree[curTreeNodeIdx].varName = RegressionTreeModel.TreeNode.NO_VARIABLE;
-          tree[curTreeNodeIdx].val = lineSearch(internalIdx, startIdx, endIdx);
-          curTreeNodeIdx++;
-        } else {
-
-
-          int bestVarIdx = varName2Index[bestVariableName];
-          // split - two pass
-
-          // store which index goes where
-          for (int k = startIdx; k <= endIdx; k++) {
-            if (x[bestVarIdx][internalIdx[k]] <= threshold)
-              which[internalIdx[k]] = -1; // left partition
-            else
-              which[internalIdx[k]] = 1; // right partition
+    private void CreateInternalNode(int startIdx, int endIdx, string splittingVar, double threshold, out int splitIdx) {
+      int bestVarIdx = varName2Index[splittingVar];
+      // split - two pass
+
+      // store which index goes where
+      for (int k = startIdx; k <= endIdx; k++) {
+        if (x[bestVarIdx][internalIdx[k]] <= threshold)
+          which[internalIdx[k]] = -1; // left partition
+        else
+          which[internalIdx[k]] = 1; // right partition
+      }
+
+      // partition sortedIdx for each variable
+      int i;
+      int j;
+      for (int col = 0; col < nCols; col++) {
+        i = 0;
+        j = 0;
+        int k;
+        for (k = startIdx; k <= endIdx; k++) {
+          Debug.Assert(Math.Abs(which[sortedIdx[col][k]]) == 1);
+
+          if (which[sortedIdx[col][k]] < 0) {
+            leftTmp[i++] = sortedIdx[col][k];
+          } else {
+            rightTmp[j++] = sortedIdx[col][k];
           }
-
-          // partition sortedIdx for each variable
-          for (int col = 0; col < nCols; col++) {
-            i = 0;
-            j = 0;
-            int k;
-            for (k = startIdx; k <= endIdx; k++) {
-              Debug.Assert(Math.Abs(which[sortedIdx[col][k]]) == 1);
-
-              if (which[sortedIdx[col][k]] < 0) {
-                leftTmp[i++] = sortedIdx[col][k];
-              } else {
-                rightTmp[j++] = sortedIdx[col][k];
-              }
-            }
-            Debug.Assert(i > 0); // at least on element in the left partition
-            Debug.Assert(j > 0); // at least one element in the right partition
-            Debug.Assert(i + j == endIdx - startIdx + 1);
-            k = startIdx;
-            for (int l = 0; l < i; l++) sortedIdx[col][k++] = leftTmp[l];
-            for (int l = 0; l < j; l++) sortedIdx[col][k++] = rightTmp[l];
-          }
-
-          // partition row indices
-          i = startIdx;
-          j = endIdx;
-          while (i <= j) {
-            Debug.Assert(Math.Abs(which[internalIdx[i]]) == 1);
-            Debug.Assert(Math.Abs(which[internalIdx[j]]) == 1);
-            if (which[internalIdx[i]] < 0) i++;
-            else if (which[internalIdx[j]] > 0) j--;
-            else {
-              Debug.Assert(which[internalIdx[i]] > 0);
-              Debug.Assert(which[internalIdx[j]] < 0);
-              // swap
-              int tmp = internalIdx[i];
-              internalIdx[i] = internalIdx[j];
-              internalIdx[j] = tmp;
-              i++;
-              j--;
-            }
-          }
-          Debug.Assert(j < i);
-          Debug.Assert(i >= startIdx);
-          Debug.Assert(j <= endIdx);
-
-          var parentIdx = curTreeNodeIdx;
-          tree[parentIdx].varName = bestVariableName;
-          tree[parentIdx].val = threshold;
-          curTreeNodeIdx++;
-
-          // create left subtree
-          tree[parentIdx].leftIdx = curTreeNodeIdx;
-          CreateRegressionTreeForIdx(maxDepth - 1, startIdx, j, lineSearch);
-
-          // create right subtree
-          tree[parentIdx].rightIdx = curTreeNodeIdx;
-          CreateRegressionTreeForIdx(maxDepth - 1, i, endIdx, lineSearch);
-        }
-      }
-    }
-
-    private void FindBestVariableAndThreshold(int startIdx, int endIdx, out double threshold, out string bestVar) {
-      Contract.Assert(startIdx < endIdx + 1); // at least 2 elements
+        }
+        Debug.Assert(i > 0); // at least on element in the left partition
+        Debug.Assert(j > 0); // at least one element in the right partition
+        Debug.Assert(i + j == endIdx - startIdx + 1);
+        k = startIdx;
+        for (int l = 0; l < i; l++) sortedIdx[col][k++] = leftTmp[l];
+        for (int l = 0; l < j; l++) sortedIdx[col][k++] = rightTmp[l];
+      }
+
+      // partition row indices
+      i = startIdx;
+      j = endIdx;
+      while (i <= j) {
+        Debug.Assert(Math.Abs(which[internalIdx[i]]) == 1);
+        Debug.Assert(Math.Abs(which[internalIdx[j]]) == 1);
+        if (which[internalIdx[i]] < 0) i++;
+        else if (which[internalIdx[j]] > 0) j--;
+        else {
+          Debug.Assert(which[internalIdx[i]] > 0);
+          Debug.Assert(which[internalIdx[j]] < 0);
+          // swap
+          int tmp = internalIdx[i];
+          internalIdx[i] = internalIdx[j];
+          internalIdx[j] = tmp;
+          i++;
+          j--;
+        }
+      }
+      Debug.Assert(j + 1 == i);
+      Debug.Assert(i <= endIdx);
+      Debug.Assert(startIdx <= j);
+
+      tree[curTreeNodeIdx].varName = splittingVar;
+      tree[curTreeNodeIdx].val = threshold;
+      splitIdx = j;
+    }
+
+    private bool FindBestVariableAndThreshold(int startIdx, int endIdx, out double threshold, out string bestVar) {
+      Debug.Assert(startIdx < endIdx + 1); // at least 2 elements
 
       int rows = endIdx - startIdx + 1;
-      Contract.Assert(rows >= 2);
+      Debug.Assert(rows >= 2);
 
       double sumY = 0.0;
@@ -292 +320 @@
       double bestImprovement = 0.0;
       double bestThreshold = double.PositiveInfinity;
-      bestVar = string.Empty;
+      bestVar = RegressionTreeModel.TreeNode.NO_VARIABLE;
 
       for (int col = 0; col < effectiveVars; col++) {
@@ -314 +342 @@
         }
       }
-
-      UpdateVariableRelevance(bestVar, sumY, bestImprovement, rows);
-
-      threshold = bestThreshold;
-    }
-
-    // assumption is that the Average(y) = 0
+      if (bestVar == RegressionTreeModel.TreeNode.NO_VARIABLE) {
+        threshold = bestThreshold;
+        return false;
+      } else {
+        UpdateVariableRelevance(bestVar, sumY, bestImprovement, rows);
+        threshold = bestThreshold;
+        return true;
+      }
+    }
+
+    // TODO: assumption is that the Average(y) = 0
     private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
       if (string.IsNullOrEmpty(bestVar)) return;
@@ -345 +377 @@
     // if all elements of x are equal the routing fails to produce a threshold
     private static void FindBestThreshold(double[] x, int[] sortedIdx, int rows, double[] y, double sumY, out double bestThreshold, out double bestImprovement) {
-      Contract.Assert(rows >= 2);
+      Debug.Assert(rows >= 2);
 
       double sl = 0.0;