Changeset 12699

Timestamp:

07/09/15 18:46:20 (9 years ago)

Author:

gkronber

Message:

#2261: improved performance of evaluation for regression tree models

Location:

branches/GBT-trunkintegration

Files:

• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs (modified) (8 diffs)
• Tests/Test.cs (modified) (3 diffs)

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

@@ -170 +170 @@
 
       int i = 0;
-      // TODO: slow because of multiple calls to GetDoubleValue for each row index 
       foreach (var pred in tree.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices)) {
         yPred[i] = yPred[i] + nu * pred;

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

@@ -25 +25 @@
 using System.Globalization;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -36 +35 @@
   public sealed class RegressionTreeModel : NamedItem, IRegressionModel {
 
-    // trees are represented as a flat array
+    // trees are represented as a flat array    
     internal struct TreeNode {
-      public readonly static string NO_VARIABLE = string.Empty;
+      public readonly static string NO_VARIABLE = null;
 
       public TreeNode(string varName, double val, int leftIdx = -1, int rightIdx = -1)
@@ -52 +51 @@
       public int LeftIdx { get; private set; }
       public int RightIdx { get; private set; }
+
+      internal IList<double> Data { get; set; } // only necessary to improve efficiency of evaluation
 
       // necessary because the default implementation of GetHashCode for structs in .NET would only return the hashcode of val here
@@ -76 +77 @@
     }
 
+    // not storable!
+    private TreeNode[] tree;
+
     [Storable]
-    private readonly TreeNode[] tree;
+    // to prevent storing the references to data caches in nodes
+    private Tuple<string, double, int, int>[] SerializedTree {
+      get { return tree.Select(t => Tuple.Create(t.VarName, t.Val, t.LeftIdx, t.RightIdx)).ToArray(); }
+      set { this.tree = value.Select(t => new TreeNode(t.Item1, t.Item2, t.Item3, t.Item4)).ToArray(); }
+    }
 
     [StorableConstructor]
@@ -84 +92 @@
     private RegressionTreeModel(RegressionTreeModel original, Cloner cloner)
       : base(original, cloner) {
-      this.tree = original.tree; // shallow clone, tree must be readonly
+      if (original.tree != null) {
+        this.tree = new TreeNode[original.tree.Length];
+        Array.Copy(original.tree, this.tree, this.tree.Length);
+      }
     }
 
@@ -92 +103 @@
     }
 
-    private static double GetPredictionForRow(TreeNode[] t, int nodeIdx, IDataset ds, int row) {
-      var node = t[nodeIdx];
-      if (node.VarName == TreeNode.NO_VARIABLE)
-        return node.Val;
-      // TODO: many calls to GetDoubleValue are slow because of the dictionary lookup in Dataset (see ticket #2417)
-      else if (ds.GetDoubleValue(node.VarName, row) <= node.Val)
-        return GetPredictionForRow(t, node.LeftIdx, ds, row);
-      else
-        return GetPredictionForRow(t, node.RightIdx, ds, row);
+    private static double GetPredictionForRow(TreeNode[] t, int nodeIdx, int row) {
+      while (nodeIdx != -1) {
+        var node = t[nodeIdx];
+        if (node.VarName == TreeNode.NO_VARIABLE)
+          return node.Val;
+
+        if (node.Data[row] <= node.Val)
+          nodeIdx = node.LeftIdx;
+        else
+          nodeIdx = node.RightIdx;
+      }
+      throw new InvalidOperationException("Invalid tree in RegressionTreeModel");
     }
 
@@ -108 +122 @@
 
     public IEnumerable<double> GetEstimatedValues(IDataset ds, IEnumerable<int> rows) {
-      return rows.Select(r => GetPredictionForRow(tree, 0, ds, r));
+      // lookup columns for variableNames in one pass over the tree to speed up evaluation later on
+      for (int i = 0; i < tree.Length; i++) {
+        if (tree[i].VarName != TreeNode.NO_VARIABLE) {
+          tree[i].Data = ds.GetReadOnlyDoubleValues(tree[i].VarName);
+        }
+      }
+      return rows.Select(r => GetPredictionForRow(tree, 0, r));
     }
 
@@ -130 +150 @@
       }
     }
-
   }
-
 }

branches/GBT-trunkintegration/Tests/Test.cs

@@ -183 +183 @@
       gbt.Iterations = 5000;
       gbt.MaxSize = 20;
+      gbt.CreateSolution = false;
       #endregion
 
       RunAlgorithm(gbt);
 
+      Console.WriteLine(gbt.ExecutionTime);
       Assert.AreEqual(267.68704241153921, ((DoubleValue)gbt.Results["Loss (train)"].Value).Value, 1E-6);
       Assert.AreEqual(393.84704062205469, ((DoubleValue)gbt.Results["Loss (test)"].Value).Value, 1E-6);
@@ -209 +211 @@
       gbt.Nu = 0.02;
       gbt.LossFunctionParameter.Value = gbt.LossFunctionParameter.ValidValues.First(l => l.ToString().Contains("Absolute"));
+      gbt.CreateSolution = false;
       #endregion
 
       RunAlgorithm(gbt);
 
+      Console.WriteLine(gbt.ExecutionTime);
       Assert.AreEqual(10.551385044666661, ((DoubleValue)gbt.Results["Loss (train)"].Value).Value, 1E-6);
       Assert.AreEqual(12.918001745581172, ((DoubleValue)gbt.Results["Loss (test)"].Value).Value, 1E-6);
@@ -235 +239 @@
       gbt.Nu = 0.005;
       gbt.LossFunctionParameter.Value = gbt.LossFunctionParameter.ValidValues.First(l => l.ToString().Contains("Relative"));
+      gbt.CreateSolution = false;
       #endregion
 
       RunAlgorithm(gbt);
 
+      Console.WriteLine(gbt.ExecutionTime);
       Assert.AreEqual(0.061954221604374943, ((DoubleValue)gbt.Results["Loss (train)"].Value).Value, 1E-6);
       Assert.AreEqual(0.06316303473499961, ((DoubleValue)gbt.Results["Loss (test)"].Value).Value, 1E-6);