Changeset 12623

Timestamp:

07/07/15 08:48:06 (5 years ago)

Author:

gkronber

Message:

#2261: comments

File:

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

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

@@ -240 +240 @@
     }
 
-    // routine for building the tree for the row idx stored in internalIdx between startIdx and 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)
@@ -248 +248 @@
       // split - two pass
 
-      // store which index goes where
+      // store which index goes into which partition 
       for (int k = startIdx; k <= endIdx; k++) {
         if (x[bestVarIdx][internalIdx[k]] <= threshold)
@@ -319 +319 @@
       }
 
-      double bestImprovement = 1.0 / rows * sumY * sumY;
+      // see description of calculation in FindBestThreshold
+      double bestImprovement = 1.0 / rows * sumY * sumY; // any improvement must be larger than this baseline
       double bestThreshold = double.PositiveInfinity;
       bestVar = RegressionTreeModel.TreeNode.NO_VARIABLE;
@@ -353 +354 @@
     }
 
-    // TODO: assumption is that the Average(y) = 0
     private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
       if (string.IsNullOrEmpty(bestVar)) return;
       // update variable relevance
-      double err = sumY * sumY / rows;
-      double errAfterSplit = bestImprovement;
-
-      double delta = (errAfterSplit - err); // relative reduction in squared error
+      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)) {
@@ -385 +384 @@
       double nr = rows;
 
-      bestImprovement = 1.0 / rows * sumY * sumY;
+      bestImprovement = 1.0 / rows * sumY * sumY; // this is the baseline for the improvement
       bestThreshold = double.NegativeInfinity;
       // for all thresholds
@@ -403 +402 @@
           // without partitioning the variance is var(y) = E(y²) - E(y)²  
           //    = 1/n * sum(y²) - (1/n * sum(y))²
-          //      -------------
+          //      -------------   ---------------
+          //         constant       baseline for improvement
+          // 
           // 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))²)