Changeset 12620

Timestamp:

07/06/15 20:38:56 (9 years ago)

Author:

gkronber

Message:

#2261: corrected check if a split is useful, added a unit test class and added an elaborate comment on split quality calculation

Location:

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

Files:

• GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs (modified) (2 diffs)
• GradientBoostedTrees/RegressionTreeBuilder.cs (modified) (13 diffs)
• GradientBoostedTrees/Test.cs (added)
• HeuristicLab.Algorithms.DataAnalysis-3.4.csproj (modified) (2 diffs)

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

@@ -186 +186 @@
 
       // init
-      var problemData = Problem.ProblemData;
+      var problemData = (IRegressionProblemData)Problem.ProblemData.Clone();
       var lossFunction = ApplicationManager.Manager.GetInstances<ILossFunction>()
         .Single(l => l.ToString() == LossFunctionParameter.Value.Value);
@@ -245 +245 @@
         } else {
           // otherwise we produce a regression solution
-          Results.Add(new Result("Solution", new RegressionSolution(state.GetModel(), (IRegressionProblemData)problemData.Clone())));
+          Results.Add(new Result("Solution", new RegressionSolution(state.GetModel(), problemData)));
         }
       }

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

@@ -22 +22 @@
 
 using System;
+using System.Collections;
 using System.Collections.Generic;
 using System.Diagnostics;
@@ -53 +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
@@ -64 +65 @@
 
     private class Partition {
-      public int TreeNodeIdx { get; set; }
+      public int ParentNodeIdx { get; set; }
       public int Depth { get; set; }
       public int StartIdx { get; set; }
@@ -70 +71 @@
       public bool Left { get; set; }
     }
-    private readonly IList<Partition> queue;
+    private readonly SortedList<double, Partition> queue;
 
     // prepare and allocate buffer variables in ctor
@@ -94 +95 @@
       outx = new double[rows];
       outSortedIdx = new int[rows];
-      queue = new List<Partition>();
+      queue = new SortedList<double, Partition>();
 
       x = new double[nCols][];
@@ -179 +180 @@
 
       // start and end idx are inclusive
-      queue.Add(new Partition() { TreeNodeIdx = -1, Depth = maxDepth, StartIdx = 0, EndIndex = effectiveRows - 1 });
+      queue.Add(calls++, new Partition() { ParentNodeIdx = -1, Depth = maxDepth, StartIdx = 0, EndIndex = effectiveRows - 1 });
       CreateRegressionTreeForIdx(lineSearch);
 
@@ -187 +188 @@
     private void CreateRegressionTreeForIdx(LineSearchFunc lineSearch) {
       while (queue.Any()) {
-        var f = queue[0]; // actually a stack
+        var f = queue.First().Value; // actually a stack
         queue.RemoveAt(0);
 
@@ -204 +205 @@
         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;
+          if (f.ParentNodeIdx >= 0) if (f.Left) {
+              tree[f.ParentNodeIdx].leftIdx = curTreeNodeIdx;
             } else {
-              tree[f.TreeNodeIdx].rightIdx = curTreeNodeIdx;
+              tree[f.ParentNodeIdx].rightIdx = curTreeNodeIdx;
             }
           curTreeNodeIdx++;
@@ -215 +216 @@
 
           // connect to parent tree
-          if (f.TreeNodeIdx >= 0) if (f.Left) {
-              tree[f.TreeNodeIdx].leftIdx = curTreeNodeIdx;
+          if (f.ParentNodeIdx >= 0) if (f.Left) {
+              tree[f.ParentNodeIdx].leftIdx = curTreeNodeIdx;
             } else {
-              tree[f.TreeNodeIdx].rightIdx = curTreeNodeIdx;
+              tree[f.ParentNodeIdx].rightIdx = curTreeNodeIdx;
             }
 
@@ -224 +225 @@
           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)
+          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++;
 
@@ -318 +319 @@
       }
 
-      double bestImprovement = 0.0;
+      double bestImprovement = 1.0 / rows * sumY * sumY;
       double bestThreshold = double.PositiveInfinity;
       bestVar = RegressionTreeModel.TreeNode.NO_VARIABLE;
@@ -384 +385 @@
       double nr = rows;
 
-      bestImprovement = 0.0;
+      bestImprovement = 1.0 / rows * sumY * sumY;
       bestThreshold = double.NegativeInfinity;
       // for all thresholds
@@ -398 +399 @@
 
         if (x[i] < x[i + 1]) { // don't try to split when two elements are equal
+
+          // goal is to find the split with leading to minimal total variance of left and right parts
+          // without partitioning the variance is var(y) = E(y²) - E(y)²  
+          //    = 1/n * sum(y²) - (1/n * sum(y))²
+          //      -------------
+          // if we split into right and left part the overall variance is the weigthed combination nl/n * var(y_l) + nr/n * var(y_r)  
+          //    = nl/n * (1/nl * sum(y_l²) - (1/nl * sum(y_l))²) + nr/n * (1/nr * sum(y_r²) - (1/nr * sum(y_r))²)
+          //    = 1/n * sum(y_l²) - 1/nl * 1/n * sum(y_l)² + 1/n * sum(y_r²) - 1/nr * 1/n * sum(y_r)²
+          //    = 1/n * (sum(y_l²) + sum(y_r²)) - 1/n * (sum(y_l)² / nl + sum(y_r)² / nr)
+          //    = 1/n * sum(y²) - 1/n * (sum(y_l)² / nl + sum(y_r)² / nr)
+          //      -------------
+          //       not changed by split (and the same for total variance without partitioning)
+          //
+          //   therefore we need to find the maximum value (sum(y_l)² / nl + sum(y_r)² / nr) (ignoring the factor 1/n)
+          //   and this value must be larger than 1/n * sum(y)² to be an improvement over no split 
+
           double curQuality = sl * sl / nl + sr * sr / nr;
-          // curQuality = nl*nr / (nl+nr) * Sqr(sl / nl - sr / nr) // greedy function approximation page 12 eqn (35)
 
           if (curQuality > bestImprovement) {

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

@@ -199 +199 @@
       <Private>False</Private>
     </Reference>
+    <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework, Version=10.1.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL" />
     <Reference Include="System" />
     <Reference Include="System.Core">
@@ -289 +290 @@
     <Compile Include="GradientBoostedTrees\RegressionTreeBuilder.cs" />
     <Compile Include="GradientBoostedTrees\RegressionTreeModel.cs" />
+    <Compile Include="GradientBoostedTrees\Test.cs" />
     <Compile Include="Interfaces\IGaussianProcessClassificationModelCreator.cs" />
     <Compile Include="Interfaces\IGaussianProcessRegressionModelCreator.cs" />