Changeset 12607

Timestamp:

07/06/15 15:20:28 (9 years ago)

Author:

gkronber

Message:

#2261: also use line search function for the initial estimation f0, changed logistic regression loss function to match description in GBM paper, comments and code improvements

Location:

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

Files:

• GradientBoostedTreesAlgorithmStatic.cs (modified) (1 diff)
• LossFunctions/AbsoluteErrorLoss.cs (modified) (4 diffs)
• LossFunctions/ILossFunction.cs (modified) (2 diffs)
• LossFunctions/LogisticRegressionLoss.cs (modified) (4 diffs)
• LossFunctions/RelativeErrorLoss.cs (modified) (5 diffs)
• LossFunctions/SquaredErrorLoss.cs (modified) (3 diffs)

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

@@ -84 +84 @@
         activeIdx = Enumerable.Range(0, nRows).ToArray();
 
-        // prepare arrays (allocate only once)
-        double f0 = y.Average(); // default prediction (constant)
+        var zeros = Enumerable.Repeat(0.0, nRows);
+        var ones = Enumerable.Repeat(1.0, nRows);
+        double f0 = lossFunction.GetLineSearchFunc(y, zeros, ones)(activeIdx, 0, nRows - 1); // initial constant value (mean for squared errors)
         pred = Enumerable.Repeat(f0, nRows).ToArray();
         predTest = Enumerable.Repeat(f0, problemData.TestIndices.Count()).ToArray();

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

@@ -38 +38 @@
       while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
         double res = targetEnum.Current - predEnum.Current;
-        s += weightEnum.Current * Math.Abs(res);
+        s += weightEnum.Current * Math.Abs(res);  // w * |res|
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
@@ -52 +52 @@
 
       while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
-        // weight * sign(res)
+        // dL(y, f(x)) / df(x) = weight * sign(res)
         var res = targetEnum.Current - predEnum.Current;
         if (res > 0) yield return weightEnum.Current;
@@ -67 +67 @@
       var predArr = pred.ToArray();
       var weightArr = weight.ToArray();
-      // weights are not supported yet
-      // when weights are supported we need to calculate a weighted median
+      // the optimal constant value that should be added to the predictions is the median of the residuals
+      // weights are not supported yet (need to calculate a weighted median)
       Debug.Assert(weightArr.All(w => w.IsAlmost(1.0)));
 
@@ -80 +80 @@
         int nRows = endIdx - startIdx + 1;
         var res = new double[nRows];
-        for (int offset = 0; offset < nRows; offset++) {
-          var i = startIdx + offset;
+        for (int i = startIdx; i <= endIdx; i++) {
           var row = idx[i];
-          res[offset] = targetArr[row] - predArr[row];
+          res[i - startIdx] = targetArr[row] - predArr[row];
         }
         return res.Median();

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

@@ -24 +24 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
+  // returns the optimal value for the partition of rows stored in idx[startIdx] .. idx[endIdx] inclusive
   public delegate double LineSearchFunc(int[] idx, int startIdx, int endIdx);
 
+  // represents an interface for loss functions used by gradient boosting
+  // target represents the target vector  (original targets from the problem data, never changed)
+  // pred   represents the current vector of predictions (a weighted combination of models learned so far, this vector is updated after each step)
+  // weight represents a weight vector for rows (this is not supported yet -> all weights are 1)
   public interface ILossFunction {
-    // returns the weighted loss
+    // returns the weighted loss of the current prediction vector 
     double GetLoss(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight);
 
@@ -37 +42 @@
   }
 }
+
+

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

@@ -28 +28 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
+  // Greedy Function Approximation: A Gradient Boosting Machine (page 9) 
   public class LogisticRegressionLoss : ILossFunction {
     public double GetLoss(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight) {
@@ -36 +37 @@
       double s = 0;
       while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
-        // assert target == 0 or target == 1
-        if (!targetEnum.Current.IsAlmost(0.0) && !targetEnum.Current.IsAlmost(1.0))
-          throw new NotSupportedException("labels must be 0 or 1 for logistic regression loss");
-        double f = Math.Max(-7, Math.Min(7, predEnum.Current)); // threshold for exponent
-        var probPos = Math.Exp(2 * f) / (1 + Math.Exp(2 * f));
-        s += weightEnum.Current * (-targetEnum.Current * Math.Log(probPos) - (1 - targetEnum.Current) * Math.Log(1 - probPos));
+        Debug.Assert(targetEnum.Current.IsAlmost(0.0) || targetEnum.Current.IsAlmost(1.0), "labels must be 0 or 1 for logistic regression loss");
+
+        var y = targetEnum.Current * 2 - 1; // y in {-1,1}
+        s += weightEnum.Current * Math.Log(1 + Math.Exp(-2 * y * predEnum.Current));
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
 
       return s;
@@ -55 +54 @@
 
       while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
-        // assert target == 0 or target == 1
-        if (!targetEnum.Current.IsAlmost(0.0) && !targetEnum.Current.IsAlmost(1.0))
-          throw new NotSupportedException("labels must be 0 or 1 for logistic regression loss");
-        double f = Math.Max(-7, Math.Min(7, predEnum.Current)); // threshold for exponent
-        var probPos = Math.Exp(2 * f) / (1 + Math.Exp(2 * f));
-        yield return weightEnum.Current * (targetEnum.Current - probPos) / (probPos * probPos - probPos);
+        Debug.Assert(targetEnum.Current.IsAlmost(0.0) || targetEnum.Current.IsAlmost(1.0), "labels must be 0 or 1 for logistic regression loss");
+        var y = targetEnum.Current * 2 - 1; // y in {-1,1}
+
+        yield return weightEnum.Current * 2 * y / (1 + Math.Exp(2 * y * predEnum.Current));
+
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
     }
 
@@ -75 +73 @@
 
       if (targetArr.Length != predArr.Length || predArr.Length != weightArr.Length)
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
 
-      // line search for abs error
+      // "Simple Newton-Raphson step" of eqn. 23 
       LineSearchFunc lineSearch = (idx, startIdx, endIdx) => {
         double sumY = 0.0;
         double sumDiff = 0.0;
         for (int i = startIdx; i <= endIdx; i++) {
-          var yi = (targetArr[idx[i]] - predArr[idx[i]]);
-          var wi = weightArr[idx[i]];
+          var row = idx[i];
+          var y = targetArr[row] * 2 - 1; // y in {-1,1}
+          var pseudoResponse = weightArr[row] * 2 * y / (1 + Math.Exp(2 * y * predArr[row]));
 
-          sumY += wi * yi;
-          sumDiff += wi * Math.Abs(yi) * (1 - Math.Abs(yi));
-
+          sumY += pseudoResponse;
+          sumDiff += Math.Abs(pseudoResponse) * (2 - Math.Abs(pseudoResponse));
         }
         // prevent divByZero
         sumDiff = Math.Max(1E-12, sumDiff);
-        return 0.5 * sumY / sumDiff;
+        return sumY / sumDiff;
       };
       return lineSearch;

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

@@ -28 +28 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
-  // relative error loss is a special case of weighted absolute error loss
-  // absolute loss is weighted by (1/target)
+  // relative error loss is a special case of weighted absolute error loss with weights = (1/target)
   public class RelativeErrorLoss : ILossFunction {
     public double GetLoss(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight) {
@@ -42 +41 @@
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
 
       return s;
@@ -60 +59 @@
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
     }
 
@@ -70 +69 @@
 
       if (targetArr.Length != predArr.Length || predArr.Length != weightArr.Length)
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
 
       // line search for relative error
@@ -82 +81 @@
           var w0 = weightArr[idx[startIdx]] * Math.Abs(1.0 / targetArr[idx[startIdx]]);
           var w1 = weightArr[idx[endIdx]] * Math.Abs(1.0 / targetArr[idx[endIdx]]);
-          return (w0 * (targetArr[idx[startIdx]] - predArr[idx[startIdx]]) + w1 * (targetArr[idx[endIdx]] - predArr[idx[endIdx]])) / (w0 + w1);
+          if (w0 > w1) {
+            return targetArr[idx[startIdx]] - predArr[idx[startIdx]];
+          } else if (w0 < w1) {
+            return targetArr[idx[endIdx]] - predArr[idx[endIdx]];
+          } else {
+            // same weight -> return average of both residuals
+            return ((targetArr[idx[startIdx]] - predArr[idx[startIdx]]) + (targetArr[idx[endIdx]] - predArr[idx[endIdx]])) / 2;
+          }
         } else {
-          var ts = from offset in Enumerable.Range(0, nRows)
-                   let i = startIdx + offset
-                   let row = idx[i]
-                   select new { res = targetArr[row] - predArr[row], weight = weightArr[row] * Math.Abs(1.0 / targetArr[row]) };
-          ts = ts.OrderBy(t => t.res);
-          var totalWeight = ts.Sum(t => t.weight);
-          var tsEnumerator = ts.GetEnumerator();
-          tsEnumerator.MoveNext();
+          // create an array of key-value pairs to be sorted (instead of using Array.Sort(res, weights))
+          var res_w = new KeyValuePair<double, double>[nRows];
+          var totalWeight = 0.0;
+          for (int i = startIdx; i <= endIdx; i++) {
+            int row = idx[i];
+            var res = targetArr[row] - predArr[row];
+            var w = weightArr[row] * Math.Abs(1.0 / targetArr[row]);
+            res_w[i - startIdx] = new KeyValuePair<double, double>(res, w);
+            totalWeight += w;
+          }
+          res_w.StableSort((a, b) => Math.Sign(a.Key - b.Key));
 
-          double aggWeight = tsEnumerator.Current.weight; // weight of first
-
-          while (aggWeight < totalWeight / 2) {
-            tsEnumerator.MoveNext();
-            aggWeight += tsEnumerator.Current.weight;
+          int k = 0;
+          double sum = totalWeight - res_w[k].Value; // total - first weight
+          while (sum > totalWeight / 2) {
+            k++;
+            sum -= res_w[k].Value;
           }
-          return tsEnumerator.Current.res;
+          return res_w[k].Key;
         }
       };

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

@@ -35 +35 @@
       while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
         double res = targetEnum.Current - predEnum.Current;
-        s += weightEnum.Current * res * res;
+        s += weightEnum.Current * res * res; // w * (res)^2
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
 
       return s;
@@ -49 +49 @@
 
       while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
-        yield return weightEnum.Current * 2.0 * (targetEnum.Current - predEnum.Current);
+        yield return weightEnum.Current * 2.0 * (targetEnum.Current - predEnum.Current); // dL(y, f(x)) / df(x)  = w * 2 * res 
       }
       if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
     }
 
@@ -60 +60 @@
       var weightArr = weight.ToArray();
       if (targetArr.Length != predArr.Length || predArr.Length != weightArr.Length)
-        throw new ArgumentException("target, pred and weight have differing lengths");
+        throw new ArgumentException("target, pred and weight have different lengths");
 
-      // line search for squared error loss => return the average value
+      // line search for squared error loss 
+      // for a given partition of rows the optimal constant that should be added to the current prediction values is the average of the residuals
       LineSearchFunc lineSearch = (idx, startIdx, endIdx) => {
         double s = 0.0;