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

Timestamp:

07/07/15 11:57:37 (9 years ago)

Author:

gkronber

Message:

#2261 implemented node expansion using a priority queue (and changed parameter MaxDepth to MaxSize). Moved unit tests to a separate project.

File:

• branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs (modified) (12 diffs)

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

@@ -54 +54 @@
     private readonly int[][] sortedIdx; // random selection from sortedIdxAll (for r < 1.0)
 
-    private int calls = 0;
-
     // helper arrays which are allocated to maximal necessary size only once in the ctor
     private readonly int[] internalIdx, which, leftTmp, rightTmp;
@@ -64 +62 @@
     private int curTreeNodeIdx; // the index where the next tree node is stored
 
-    private class Partition {
-      public int ParentNodeIdx { get; set; }
-      public int Depth { get; set; }
-      public int StartIdx { get; set; }
-      public int EndIndex { get; set; }
-      public bool Left { get; set; }
-    }
-    private readonly SortedList<double, Partition> queue;
+    // This class represents information about potential splits.
+    // For each node generated the best splitting variable and threshold as well as
+    // the improvement from the split are stored in a priority queue
+    private class PartitionSplits {
+      public int ParentNodeIdx { get; set; } // the idx of the leaf node representing this partition 
+      public int StartIdx { get; set; } // the start idx of the partition
+      public int EndIndex { get; set; } // the end idx of the partition
+      public string SplittingVariable { get; set; } // the best splitting variable
+      public double SplittingThreshold { get; set; } // the best threshold
+      public double SplittingImprovement { get; set; } // the improvement of the split (for priority queue)
+    }
+
+    // this list hold partitions with the information about the best split (organized as a sorted queue)
+    private readonly IList<PartitionSplits> queue;
 
     // prepare and allocate buffer variables in ctor
@@ -95 +99 @@
       outx = new double[rows];
       outSortedIdx = new int[rows];
-      queue = new SortedList<double, Partition>();
+      queue = new List<PartitionSplits>(100);
 
       x = new double[nCols][];
@@ -117 +121 @@
     // r is fraction of rows to use for training
     // m is fraction of variables to use for training
-    public IRegressionModel CreateRegressionTree(int maxDepth, double r = 0.5, double m = 0.5) {
+    public IRegressionModel CreateRegressionTree(int maxSize, double r = 0.5, double m = 0.5) {
       // subtract mean of y first
       var yAvg = y.Average();
@@ -126 +130 @@
       var ones = Enumerable.Repeat(1.0, y.Length);
 
-      var model = CreateRegressionTreeForGradientBoosting(y, maxDepth, problemData.TrainingIndices.ToArray(), seLoss.GetLineSearchFunc(y, zeros, ones), r, m);
+      var model = CreateRegressionTreeForGradientBoosting(y, maxSize, problemData.TrainingIndices.ToArray(), seLoss.GetLineSearchFunc(y, zeros, ones), r, m);
 
       return new GradientBoostedTreesModel(new[] { new ConstantRegressionModel(yAvg), model }, new[] { 1.0, 1.0 });
@@ -132 +136 @@
 
     // 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) {
-      Debug.Assert(maxDepth > 0);
+    public IRegressionModel CreateRegressionTreeForGradientBoosting(double[] y, int maxSize, int[] idx, LineSearchFunc lineSearch, double r = 0.5, double m = 0.5) {
+      Debug.Assert(maxSize > 0);
       Debug.Assert(r > 0);
       Debug.Assert(r <= 1.0);
@@ -174 +178 @@
       }
 
-      // prepare array for the tree nodes (a tree of maxDepth=1 has 1 node, a tree of maxDepth=d has 2^d - 1 nodes)      
-      int numNodes = (int)Math.Pow(2, maxDepth) - 1;
-      this.tree = new RegressionTreeModel.TreeNode[numNodes];
+      this.tree = new RegressionTreeModel.TreeNode[maxSize];
+      this.queue.Clear();
       this.curTreeNodeIdx = 0;
 
+      // start out with only one leaf node (constant prediction)
+      // and calculate the best split for this root node and enqueue it into a queue sorted by improvement throught the split
       // start and end idx are inclusive
-      queue.Add(calls++, new Partition() { ParentNodeIdx = -1, Depth = maxDepth, StartIdx = 0, EndIndex = effectiveRows - 1 });
-      CreateRegressionTreeForIdx(lineSearch);
-
-      return new RegressionTreeModel(tree);
-    }
-
-    private void CreateRegressionTreeForIdx(LineSearchFunc lineSearch) {
-      while (queue.Any()) {
-        var f = queue.First().Value; // actually a stack
-        queue.RemoveAt(0);
-
-        var depth = f.Depth;
+      CreateLeafNode(0, effectiveRows - 1, lineSearch);
+
+      // process the priority queue to complete the tree
+      CreateRegressionTreeFromQueue(maxSize, lineSearch);
+
+      return new RegressionTreeModel(tree.ToArray());
+    }
+
+
+    // processes potential splits from the queue as long as splits are left and the maximum size of the tree is not reached
+    private void CreateRegressionTreeFromQueue(int maxNodes, LineSearchFunc lineSearch) {
+      while (queue.Any() && curTreeNodeIdx + 1 < maxNodes) { // two nodes are created in each loop
+        var f = queue[queue.Count - 1]; // last element has the largest improvement
+        queue.RemoveAt(queue.Count - 1);
+
         var startIdx = f.StartIdx;
         var endIdx = f.EndIndex;
@@ -199 +207 @@
         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.ParentNodeIdx >= 0) if (f.Left) {
-              tree[f.ParentNodeIdx].leftIdx = curTreeNodeIdx;
-            } else {
-              tree[f.ParentNodeIdx].rightIdx = curTreeNodeIdx;
-            }
-          curTreeNodeIdx++;
-        } else {
-          int splitIdx;
-          CreateInternalNode(f.StartIdx, f.EndIndex, bestVariableName, threshold, out splitIdx);
-
-          // connect to parent tree
-          if (f.ParentNodeIdx >= 0) if (f.Left) {
-              tree[f.ParentNodeIdx].leftIdx = curTreeNodeIdx;
-            } else {
-              tree[f.ParentNodeIdx].rightIdx = curTreeNodeIdx;
-            }
-
-          Debug.Assert(splitIdx + 1 <= endIdx);
-          Debug.Assert(startIdx <= splitIdx);
-
-          queue.Add(calls++, new Partition() { ParentNodeIdx = curTreeNodeIdx, Left = true, Depth = depth - 1, StartIdx = startIdx, EndIndex = splitIdx }); // left part before right part (stack organization)
-          queue.Add(calls++, new Partition() { ParentNodeIdx = curTreeNodeIdx, Left = false, Depth = depth - 1, StartIdx = splitIdx + 1, EndIndex = endIdx });
-          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 partition of rows 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)
+        // transform the leaf node into an internal node
+        tree[f.ParentNodeIdx].VarName = f.SplittingVariable;
+        tree[f.ParentNodeIdx].Val = f.SplittingThreshold;
+
+        // split partition into left and right
+        int splitIdx;
+        SplitPartition(f.StartIdx, f.EndIndex, f.SplittingVariable, f.SplittingThreshold, out splitIdx);
+        Debug.Assert(splitIdx + 1 <= endIdx);
+        Debug.Assert(startIdx <= splitIdx);
+
+        // create two leaf nodes (and enqueue best splits for both)
+        tree[f.ParentNodeIdx].LeftIdx = CreateLeafNode(startIdx, splitIdx, lineSearch);
+        tree[f.ParentNodeIdx].RightIdx = CreateLeafNode(splitIdx + 1, endIdx, lineSearch);
+      }
+    }
+
+
+    // returns the index of the newly created tree node
+    private int CreateLeafNode(int startIdx, int endIdx, LineSearchFunc lineSearch) {
+      tree[curTreeNodeIdx].VarName = RegressionTreeModel.TreeNode.NO_VARIABLE;
+      tree[curTreeNodeIdx].Val = lineSearch(internalIdx, startIdx, endIdx);
+
+      EnqueuePartitionSplit(curTreeNodeIdx, startIdx, endIdx);
+      curTreeNodeIdx++;
+      return curTreeNodeIdx - 1;
+    }
+
+
+    // calculates the optimal split for the partition [startIdx .. endIdx] (inclusive) 
+    // which is represented by the leaf node with the specified nodeIdx
+    private void EnqueuePartitionSplit(int nodeIdx, int startIdx, int endIdx) {
+      double threshold, improvement;
+      string bestVariableName;
+      // only enqueue a new split if there are at least 2 rows left and a split is possible
+      if (startIdx < endIdx &&
+        FindBestVariableAndThreshold(startIdx, endIdx, out threshold, out bestVariableName, out improvement)) {
+        var split = new PartitionSplits() {
+          ParentNodeIdx = nodeIdx,
+          StartIdx = startIdx,
+          EndIndex = endIdx,
+          SplittingThreshold = threshold,
+          SplittingVariable = bestVariableName
+        };
+        InsertSortedQueue(split);
+      }
+    }
+
+
+    // routine for splitting a partition of rows stored in internalIdx between startIdx and endIdx into
+    // a left partition and a right partition using the given splittingVariable and threshold
+    // the splitIdx is the last index of the left partition 
+    // splitIdx + 1 is the first index of the right partition
     // startIdx and endIdx are inclusive
-    private void CreateInternalNode(int startIdx, int endIdx, string splittingVar, double threshold, out int splitIdx) {
+    private void SplitPartition(int startIdx, int endIdx, string splittingVar, double threshold, out int splitIdx) {
       int bestVarIdx = varName2Index[splittingVar];
       // split - two pass
@@ -303 +319 @@
       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) {
+    private bool FindBestVariableAndThreshold(int startIdx, int endIdx, out double threshold, out string bestVar, out double improvement) {
       Debug.Assert(startIdx < endIdx + 1); // at least 2 elements
 
@@ -345 +359 @@
       }
       if (bestVar == RegressionTreeModel.TreeNode.NO_VARIABLE) {
-        threshold = bestThreshold;
+        // not successfull
+        threshold = double.PositiveInfinity;
+        improvement = double.NegativeInfinity;
         return false;
       } else {
         UpdateVariableRelevance(bestVar, sumY, bestImprovement, rows);
+        improvement = bestImprovement;
         threshold = bestThreshold;
         return true;
       }
-    }
-
-    private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
-      if (string.IsNullOrEmpty(bestVar)) return;
-      // update variable relevance
-      double baseLine = 1.0 / rows * sumY * sumY; // if best improvement is equal to baseline then the split had no effect
-
-      double delta = (bestImprovement - baseLine);
-      double v;
-      if (!sumImprovements.TryGetValue(bestVar, out v)) {
-        sumImprovements[bestVar] = delta;
-      }
-      sumImprovements[bestVar] = v + delta;
     }
 
@@ -429 +433 @@
 
 
+    private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
+      if (string.IsNullOrEmpty(bestVar)) return;
+      // update variable relevance
+      double baseLine = 1.0 / rows * sumY * sumY; // if best improvement is equal to baseline then the split had no effect
+
+      double delta = (bestImprovement - baseLine);
+      double v;
+      if (!sumImprovements.TryGetValue(bestVar, out v)) {
+        sumImprovements[bestVar] = delta;
+      }
+      sumImprovements[bestVar] = v + delta;
+    }
+
     public IEnumerable<KeyValuePair<string, double>> GetVariableRelevance() {
       // values are scaled: the most important variable has relevance = 100
@@ -437 +454 @@
         .OrderByDescending(t => t.Value);
     }
+
+
+    // insert a new parition split (find insertion point and start at first element of the queue)
+    // elements are removed from the queue at the last position
+    // O(n), splits could be organized as a heap to improve runtime (see alglib tsort)
+    private void InsertSortedQueue(PartitionSplits split) {
+      // find insertion position
+      int i = 0;
+      while (i < queue.Count && queue[i].SplittingImprovement < split.SplittingImprovement) { i++; }
+
+      queue.Insert(i, split);
+    }
   }
 }