Changeset 13895

Timestamp:

06/15/16 10:02:15 (8 years ago)

Author:

gkronber

Message:

#2612: extended GBT to support calculation of partial dependence (as described in the greedy function approximation paper), changed persistence of regression tree models and added two unit tests.

Location:

trunk/sources

Files:

• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs (modified) (7 diffs)
• HeuristicLab.Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/GradientBoostingTest.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs

@@ -180 +180 @@
 
 
-    // processes potential splits from the queue as long as splits are left and the maximum size of the tree is not reached
+    // processes potential splits from the queue as long as splits are remaining and the maximum size of the tree is not reached
     private void CreateRegressionTreeFromQueue(int maxNodes, ILossFunction lossFunction) {
       while (queue.Any() && curTreeNodeIdx + 1 < maxNodes) { // two nodes are created in each loop
@@ -204 +204 @@
 
         // overwrite existing leaf node with an internal node
-        tree[f.ParentNodeIdx] = new RegressionTreeModel.TreeNode(f.SplittingVariable, f.SplittingThreshold, leftTreeIdx, rightTreeIdx);
+        tree[f.ParentNodeIdx] = new RegressionTreeModel.TreeNode(f.SplittingVariable, f.SplittingThreshold, leftTreeIdx, rightTreeIdx, weightLeft: (splitIdx - startIdx + 1) / (double)(endIdx - startIdx + 1));
       }
     }

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs

@@ -40 +40 @@
       public readonly static string NO_VARIABLE = null;
 
-      public TreeNode(string varName, double val, int leftIdx = -1, int rightIdx = -1)
+      public TreeNode(string varName, double val, int leftIdx = -1, int rightIdx = -1, double weightLeft = -1.0)
         : this() {
         VarName = varName;
@@ -46 +46 @@
         LeftIdx = leftIdx;
         RightIdx = rightIdx;
-      }
-
-      public string VarName { get; private set; } // name of the variable for splitting or NO_VARIABLE if terminal node
-      public double Val { get; private set; } // threshold
-      public int LeftIdx { get; private set; }
-      public int RightIdx { get; private set; }
+        WeightLeft = weightLeft;
+      }
+
+      public string VarName { get; internal set; } // name of the variable for splitting or NO_VARIABLE if terminal node
+      public double Val { get; internal set; } // threshold
+      public int LeftIdx { get; internal set; }
+      public int RightIdx { get; internal set; }
+      public double WeightLeft { get; internal set; } // for partial dependence plots (value in range [0..1] describes the fraction of training samples for the left sub-tree
+
 
       // necessary because the default implementation of GetHashCode for structs in .NET would only return the hashcode of val here
@@ -64 +67 @@
             LeftIdx.Equals(other.LeftIdx) &&
             RightIdx.Equals(other.RightIdx) &&
+            WeightLeft.Equals(other.WeightLeft) &&
             EqualStrings(VarName, other.VarName);
         } else {
@@ -79 +83 @@
     private TreeNode[] tree;
 
-    [Storable]
+    #region old storable format 
+    // remove with HL 3.4
+    [Storable(AllowOneWay = true)]
     // to prevent storing the references to data caches in nodes
-    // TODO seemingly it is bad (performance-wise) to persist tuples (tuples are used as keys in a dictionary)
+    // seemingly, it is bad (performance-wise) to persist tuples (tuples are used as keys in a dictionary)
     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(); }
-    }
+      // 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, -1.0)).ToArray(); } // use a weight of -1.0 to indicate that partial dependence cannot be calculated for old models 
+    }
+    #endregion
+    #region new storable format
+    [Storable]
+    private string[] SerializedTreeVarNames {
+      get { return tree.Select(t => t.VarName).ToArray(); }
+      set {
+        if (tree == null) tree = new TreeNode[value.Length];
+        for (int i = 0; i < value.Length; i++) {
+          tree[i].VarName = value[i];
+        }
+      }
+    }
+    [Storable]
+    private double[] SerializedTreeValues {
+      get { return tree.Select(t => t.Val).ToArray(); }
+      set {
+        if (tree == null) tree = new TreeNode[value.Length];
+        for (int i = 0; i < value.Length; i++) {
+          tree[i].Val = value[i];
+        }
+      }
+    }
+    [Storable]
+    private int[] SerializedTreeLeftIdx {
+      get { return tree.Select(t => t.LeftIdx).ToArray(); }
+      set {
+        if (tree == null) tree = new TreeNode[value.Length];
+        for (int i = 0; i < value.Length; i++) {
+          tree[i].LeftIdx = value[i];
+        }
+      }
+    }
+    [Storable]
+    private int[] SerializedTreeRightIdx {
+      get { return tree.Select(t => t.RightIdx).ToArray(); }
+      set {
+        if (tree == null) tree = new TreeNode[value.Length];
+        for (int i = 0; i < value.Length; i++) {
+          tree[i].RightIdx = value[i];
+        }
+      }
+    }
+    [Storable]
+    private double[] SerializedTreeWeightLeft {
+      get { return tree.Select(t => t.WeightLeft).ToArray(); }
+      set {
+        if (tree == null) tree = new TreeNode[value.Length];
+        for (int i = 0; i < value.Length; i++) {
+          tree[i].WeightLeft = value[i];
+        }
+      }
+    }
+    #endregion
+
+
+
 
     [StorableConstructor]
@@ -108 +170 @@
         if (node.VarName == TreeNode.NO_VARIABLE)
           return node.Val;
-
-        if (columnCache[nodeIdx][row] <= node.Val)
+        if (columnCache[nodeIdx] == null) {
+          if (node.WeightLeft.IsAlmost(-1.0)) throw new InvalidOperationException("Cannot calculate partial dependence for trees loaded from older versions of HeuristicLab.");
+          // weighted average for partial dependence plot (recursive here because we need to calculate both sub-trees)
+          return node.WeightLeft * GetPredictionForRow(t, columnCache, node.LeftIdx, row) +
+                 (1.0 - node.WeightLeft) * GetPredictionForRow(t, columnCache, node.RightIdx, row);
+        } else if (columnCache[nodeIdx][row] <= node.Val)
           nodeIdx = node.LeftIdx;
         else
@@ -127 +193 @@
       for (int i = 0; i < tree.Length; i++) {
         if (tree[i].VarName != TreeNode.NO_VARIABLE) {
-          columnCache[i] = ds.GetReadOnlyDoubleValues(tree[i].VarName);
+          // tree models also support calculating estimations if not all variables used for training are available in the dataset
+          if (ds.ColumnNames.Contains(tree[i].VarName))
+            columnCache[i] = ds.GetReadOnlyDoubleValues(tree[i].VarName);
         }
       }
@@ -148 +216 @@
       } else {
         return
-          TreeToString(n.LeftIdx, string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} <= {3:F}", part, string.IsNullOrEmpty(part) ? "" : " and ", n.VarName, n.Val))
-        + TreeToString(n.RightIdx, string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} >  {3:F}", part, string.IsNullOrEmpty(part) ? "" : " and ", n.VarName, n.Val));
+          TreeToString(n.LeftIdx, string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} <= {3:F} ({4:N3})", part, string.IsNullOrEmpty(part) ? "" : " and ", n.VarName, n.Val, n.WeightLeft))
+        + TreeToString(n.RightIdx, string.Format(CultureInfo.InvariantCulture, "{0}{1}{2}  >  {3:F} ({4:N3}))", part, string.IsNullOrEmpty(part) ? "" : " and ", n.VarName, n.Val, 1.0 - n.WeightLeft));
       }
     }

trunk/sources/HeuristicLab.Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/GradientBoostingTest.cs

@@ -1 +1 @@
 using System;
+using System.Collections;
+using System.IO;
 using System.Linq;
 using System.Threading;
@@ -160 +162 @@
         // x2 >  1.5 AND x1 >  1.5 ->  3.0
         BuildTree(xy, allVariables, 10);
+      }
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void TestDecisionTreePartialDependence() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.RegressionRealWorldInstanceProvider();
+      var instance = provider.GetDataDescriptors().Single(x => x.Name.Contains("Tower"));
+      var regProblem = new RegressionProblem();
+      regProblem.Load(provider.LoadData(instance));
+      var problemData = regProblem.ProblemData;
+      var state = GradientBoostedTreesAlgorithmStatic.CreateGbmState(problemData, new SquaredErrorLoss(), randSeed: 31415, maxSize: 10, r: 0.5, m: 1, nu: 0.02);
+      for (int i = 0; i < 1000; i++)
+        GradientBoostedTreesAlgorithmStatic.MakeStep(state);
+
+
+      var mostImportantVar = state.GetVariableRelevance().OrderByDescending(kvp => kvp.Value).First();
+      Console.WriteLine("var: {0} relevance: {1}", mostImportantVar.Key, mostImportantVar.Value);
+      var model = ((IGradientBoostedTreesModel)state.GetModel());
+      var treeM = model.Models.Skip(1).First();
+      Console.WriteLine(treeM.ToString());
+      Console.WriteLine();
+
+      var mostImportantVarValues = problemData.Dataset.GetDoubleValues(mostImportantVar.Key).OrderBy(x => x).ToArray();
+      var ds = new ModifiableDataset(new string[] { mostImportantVar.Key },
+        new IList[] { mostImportantVarValues.ToList<double>() });
+
+      var estValues = model.GetEstimatedValues(ds, Enumerable.Range(0, mostImportantVarValues.Length)).ToArray();
+
+      for (int i = 0; i < mostImportantVarValues.Length; i += 10) {
+        Console.WriteLine("{0,-5:N3} {1,-5:N3}", mostImportantVarValues[i], estValues[i]);
+      }
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void TestDecisionTreePersistence() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.RegressionRealWorldInstanceProvider();
+      var instance = provider.GetDataDescriptors().Single(x => x.Name.Contains("Tower"));
+      var regProblem = new RegressionProblem();
+      regProblem.Load(provider.LoadData(instance));
+      var problemData = regProblem.ProblemData;
+      var state = GradientBoostedTreesAlgorithmStatic.CreateGbmState(problemData, new SquaredErrorLoss(), randSeed: 31415, maxSize: 100, r: 0.5, m: 1, nu: 1);
+      GradientBoostedTreesAlgorithmStatic.MakeStep(state);
+
+      var model = ((IGradientBoostedTreesModel)state.GetModel());
+      var treeM = model.Models.Skip(1).First();
+      var origStr = treeM.ToString();
+      using (var memStream = new MemoryStream()) {
+        Persistence.Default.Xml.XmlGenerator.Serialize(treeM, memStream);
+        var buf = memStream.GetBuffer();
+        using (var restoreStream = new MemoryStream(buf)) {
+          var restoredTree = Persistence.Default.Xml.XmlParser.Deserialize(restoreStream);
+          var restoredStr = restoredTree.ToString();
+          Assert.AreEqual(origStr, restoredStr);
+        }
       }
     }