Changeset 16692 for branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees

Timestamp:

03/18/19 17:24:30 (6 years ago)

Author:

abeham

Message:

#2521: merged trunk changes up to r15681 into branch (removal of trunk/sources)

Location:

branches/2521_ProblemRefactoring

Files:

• . (modified) (2 props)
• HeuristicLab.Algorithms.DataAnalysis (modified) (1 prop)
• HeuristicLab.Algorithms.DataAnalysis/3.4 (modified) (1 prop)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs (modified) (6 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs (modified) (6 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModelSurrogate.cs (modified) (9 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesSolution.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/IGradientBoostedTreesModel.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/AbsoluteErrorLoss.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/LogisticRegressionLoss.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/QuantileRegressionLoss.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/RelativeErrorLoss.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs (modified) (6 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs (modified) (13 diffs)

branches/2521_ProblemRefactoring

@@ -24 +24 @@
 protoc.exe
 obj
+.vs

@@ -24 +24 @@
 protoc.exe
 obj
+.vs

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -21 +21 @@
 #endregion
 
-using System;
 using System.Linq;
 using System.Threading;
@@ -35 +34 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
-  [Item("Gradient Boosted Trees (GBT)", "Gradient boosted trees algorithm. Friedman, J. \"Greedy Function Approximation: A Gradient Boosting Machine\", IMS 1999 Reitz Lecture.")]
+  [Item("Gradient Boosted Trees (GBT)", "Gradient boosted trees algorithm. Specific implementation of gradient boosting for regression trees. Friedman, J. \"Greedy Function Approximation: A Gradient Boosting Machine\", IMS 1999 Reitz Lecture.")]
   [StorableClass]
   [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 125)]
-  public class GradientBoostedTreesAlgorithm : BasicAlgorithm {
-    public override Type ProblemType {
-      get { return typeof(IRegressionProblem); }
-    }
-    public new IRegressionProblem Problem {
-      get { return (IRegressionProblem)base.Problem; }
-      set { base.Problem = value; }
-    }
-
+  public class GradientBoostedTreesAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
     #region ParameterNames
     private const string IterationsParameterName = "Iterations";
@@ -204 +195 @@
       table.Rows.Add(new DataRow("Loss (train)"));
       table.Rows.Add(new DataRow("Loss (test)"));
+      table.Rows["Loss (train)"].VisualProperties.StartIndexZero = true;
+      table.Rows["Loss (test)"].VisualProperties.StartIndexZero = true;
+
       Results.Add(new Result("Qualities", table));
       var curLoss = new DoubleValue();
@@ -263 +257 @@
           var classificationProblemData = new ClassificationProblemData(problemData.Dataset,
             problemData.AllowedInputVariables, problemData.TargetVariable, problemData.Transformations);
-          classificationModel.RecalculateModelParameters(classificationProblemData, classificationProblemData.TrainingIndices);
+          classificationProblemData.TrainingPartition.Start = Problem.ProblemData.TrainingPartition.Start;
+          classificationProblemData.TrainingPartition.End = Problem.ProblemData.TrainingPartition.End;
+          classificationProblemData.TestPartition.Start = Problem.ProblemData.TestPartition.Start;
+          classificationProblemData.TestPartition.End = Problem.ProblemData.TestPartition.End;
+
+          classificationModel.SetThresholdsAndClassValues(new double[] { double.NegativeInfinity, 0.0 }, new[] { 0.0, 1.0 });
+
 
           var classificationSolution = new DiscriminantFunctionClassificationSolution(classificationModel, classificationProblemData);
@@ -269 +269 @@
         } else {
           // otherwise we produce a regression solution
-          Results.Add(new Result("Solution", new RegressionSolution(model, problemData)));
+          Results.Add(new Result("Solution", new GradientBoostedTreesSolution(model, problemData)));
         }
       }

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -96 +96 @@
         weights = new List<double>();
         // add constant model
-        models.Add(new ConstantModel(f0));
+        models.Add(new ConstantModel(f0, problemData.TargetVariable));
         weights.Add(1.0);
       }
@@ -148 +148 @@
     // for custom stepping & termination
     public static IGbmState CreateGbmState(IRegressionProblemData problemData, ILossFunction lossFunction, uint randSeed, int maxSize = 3, double r = 0.66, double m = 0.5, double nu = 0.01) {
+      // check input variables. Only double variables are allowed.
+      var invalidInputs =
+        problemData.AllowedInputVariables.Where(name => !problemData.Dataset.VariableHasType<double>(name));
+      if (invalidInputs.Any())
+        throw new NotSupportedException("Gradient tree boosting only supports real-valued variables. Unsupported inputs: " + string.Join(", ", invalidInputs));
+
       return new GbmState(problemData, lossFunction, randSeed, maxSize, r, m, nu);
     }

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -31 +31 @@
 namespace HeuristicLab.Algorithms.DataAnalysis {
   [StorableClass]
-  [Item("Gradient boosted tree model", "")]
+  [Item("Gradient boosted trees model", "")]
   // this is essentially a collection of weighted regression models
-  public sealed class GradientBoostedTreesModel : NamedItem, IGradientBoostedTreesModel {
+  public sealed class GradientBoostedTreesModel : RegressionModel, IGradientBoostedTreesModel {
     // BackwardsCompatibility3.4 for allowing deserialization & serialization of old models
     #region Backwards compatible code, remove with 3.5
@@ -58 +58 @@
     #endregion
 
+    public override IEnumerable<string> VariablesUsedForPrediction {
+      get { return models.SelectMany(x => x.VariablesUsedForPrediction).Distinct().OrderBy(x => x); }
+    }
+
     private readonly IList<IRegressionModel> models;
     public IEnumerable<IRegressionModel> Models { get { return models; } }
@@ -77 +81 @@
     }
     [Obsolete("The constructor of GBTModel should not be used directly anymore (use GBTModelSurrogate instead)")]
-    public GradientBoostedTreesModel(IEnumerable<IRegressionModel> models, IEnumerable<double> weights)
-      : base("Gradient boosted tree model", string.Empty) {
+    internal GradientBoostedTreesModel(IEnumerable<IRegressionModel> models, IEnumerable<double> weights)
+      : base(string.Empty, "Gradient boosted tree model", string.Empty) {
       this.models = new List<IRegressionModel>(models);
       this.weights = new List<double>(weights);
@@ -89 +93 @@
     }
 
-    public IEnumerable<double> GetEstimatedValues(IDataset dataset, IEnumerable<int> rows) {
+    public override IEnumerable<double> GetEstimatedValues(IDataset dataset, IEnumerable<int> rows) {
       // allocate target array go over all models and add up weighted estimation for each row
       if (!rows.Any()) return Enumerable.Empty<double>(); // return immediately if rows is empty. This prevents multiple iteration over lazy rows enumerable.
@@ -105 +109 @@
     }
 
-    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+    public override IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
       return new RegressionSolution(this, (IRegressionProblemData)problemData.Clone());
     }
+
   }
 }

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModelSurrogate.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -21 +21 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -33 +35 @@
   // recalculate the actual GBT model on demand
   [Item("Gradient boosted tree model", "")]
-  public sealed class GradientBoostedTreesModelSurrogate : NamedItem, IGradientBoostedTreesModel {
+  public sealed class GradientBoostedTreesModelSurrogate : RegressionModel, IGradientBoostedTreesModel {
     // don't store the actual model!
-    private IGradientBoostedTreesModel actualModel; // the actual model is only recalculated when necessary
+    // the actual model is only recalculated when necessary
+    private readonly Lazy<IGradientBoostedTreesModel> actualModel;
+    private IGradientBoostedTreesModel ActualModel {
+      get { return actualModel.Value; }
+    }
 
     [Storable]
@@ -55 +61 @@
 
 
+    public override IEnumerable<string> VariablesUsedForPrediction {
+      get {
+        return ActualModel.Models.SelectMany(x => x.VariablesUsedForPrediction).Distinct().OrderBy(x => x);
+      }
+    }
+
     [StorableConstructor]
-    private GradientBoostedTreesModelSurrogate(bool deserializing) : base(deserializing) { }
+    private GradientBoostedTreesModelSurrogate(bool deserializing)
+      : base(deserializing) {
+      actualModel = new Lazy<IGradientBoostedTreesModel>(() => RecalculateModel());
+    }
 
     private GradientBoostedTreesModelSurrogate(GradientBoostedTreesModelSurrogate original, Cloner cloner)
       : base(original, cloner) {
-      if (original.actualModel != null) this.actualModel = cloner.Clone(original.actualModel);
+      IGradientBoostedTreesModel clonedModel = null;
+      if (original.ActualModel != null) clonedModel = cloner.Clone(original.ActualModel);
+      actualModel = new Lazy<IGradientBoostedTreesModel>(CreateLazyInitFunc(clonedModel)); // only capture clonedModel in the closure
 
       this.trainingProblemData = cloner.Clone(original.trainingProblemData);
@@ -72 +89 @@
     }
 
+    private Func<IGradientBoostedTreesModel> CreateLazyInitFunc(IGradientBoostedTreesModel clonedModel) {
+      return () => {
+        return clonedModel == null ? RecalculateModel() : clonedModel;
+      };
+    }
+
     // create only the surrogate model without an actual model
-    public GradientBoostedTreesModelSurrogate(IRegressionProblemData trainingProblemData, uint seed, ILossFunction lossFunction, int iterations, int maxSize, double r, double m, double nu)
-      : base("Gradient boosted tree model", string.Empty) {
+    public GradientBoostedTreesModelSurrogate(IRegressionProblemData trainingProblemData, uint seed,
+      ILossFunction lossFunction, int iterations, int maxSize, double r, double m, double nu)
+      : base(trainingProblemData.TargetVariable, "Gradient boosted tree model", string.Empty) {
       this.trainingProblemData = trainingProblemData;
       this.seed = seed;
@@ -86 +110 @@
 
     // wrap an actual model in a surrograte
-    public GradientBoostedTreesModelSurrogate(IRegressionProblemData trainingProblemData, uint seed, ILossFunction lossFunction, int iterations, int maxSize, double r, double m, double nu, IGradientBoostedTreesModel model)
+    public GradientBoostedTreesModelSurrogate(IRegressionProblemData trainingProblemData, uint seed,
+      ILossFunction lossFunction, int iterations, int maxSize, double r, double m, double nu,
+      IGradientBoostedTreesModel model)
       : this(trainingProblemData, seed, lossFunction, iterations, maxSize, r, m, nu) {
-      this.actualModel = model;
+      actualModel = new Lazy<IGradientBoostedTreesModel>(() => model);
     }
 
@@ -96 +122 @@
 
     // forward message to actual model (recalculate model first if necessary)
-    public IEnumerable<double> GetEstimatedValues(IDataset dataset, IEnumerable<int> rows) {
-      if (actualModel == null) actualModel = RecalculateModel();
-      return actualModel.GetEstimatedValues(dataset, rows);
+    public override IEnumerable<double> GetEstimatedValues(IDataset dataset, IEnumerable<int> rows) {
+      return ActualModel.GetEstimatedValues(dataset, rows);
     }
 
-    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+    public override IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
       return new RegressionSolution(this, (IRegressionProblemData)problemData.Clone());
     }
-
 
     private IGradientBoostedTreesModel RecalculateModel() {
@@ -112 +136 @@
     public IEnumerable<IRegressionModel> Models {
       get {
-        if (actualModel == null) actualModel = RecalculateModel();
-        return actualModel.Models;
+        return ActualModel.Models;
       }
     }
@@ -119 +142 @@
     public IEnumerable<double> Weights {
       get {
-        if (actualModel == null) actualModel = RecalculateModel();
-        return actualModel.Weights;
+        return ActualModel.Weights;
       }
     }

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesSolution.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
-using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/IGradientBoostedTreesModel.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -21 +21 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
-using System.Linq;
-using HeuristicLab.Common;
-using HeuristicLab.Core;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
 

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/AbsoluteErrorLoss.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/LogisticRegressionLoss.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -24 +24 @@
 using System.Collections.Generic;
 using System.Diagnostics;
-using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/QuantileRegressionLoss.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/RelativeErrorLoss.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -23 +23 @@
 using System;
 using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -22 +22 @@
 
 using System;
-using System.Collections;
 using System.Collections.Generic;
 using System.Diagnostics;
@@ -129 +128 @@
 
       // y and curPred are changed in gradient boosting
-      this.y = y; 
-      this.curPred = curPred; 
+      this.y = y;
+      this.curPred = curPred;
 
       // shuffle row idx
@@ -137 +136 @@
       int nRows = idx.Count();
 
-      // shuffle variable idx
+      // shuffle variable names
       HeuristicLab.Random.ListExtensions.ShuffleInPlace(allowedVariables, random);
 
@@ -176 +175 @@
       CreateRegressionTreeFromQueue(maxSize, lossFunction);
 
-      return new RegressionTreeModel(tree.ToArray());
-    }
-
-
-    // processes potential splits from the queue as long as splits are left and the maximum size of the tree is not reached
+      return new RegressionTreeModel(tree.ToArray(), problemData.TargetVariable);
+    }
+
+
+    // 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 +203 @@
 
         // 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));
       }
     }

branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  * and the BEACON Center for the Study of Evolution in Action.
  * 
@@ -28 +28 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
   [StorableClass]
   [Item("RegressionTreeModel", "Represents a decision tree for regression.")]
-  public sealed class RegressionTreeModel : NamedItem, IRegressionModel {
+  public sealed class RegressionTreeModel : RegressionModel {
+    public override IEnumerable<string> VariablesUsedForPrediction {
+      get { return tree.Select(t => t.VarName).Where(v => v != TreeNode.NO_VARIABLE); }
+    }
 
     // trees are represented as a flat array    
@@ -40 +46 @@
       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 +52 @@
         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 +73 @@
             LeftIdx.Equals(other.LeftIdx) &&
             RightIdx.Equals(other.RightIdx) &&
+            WeightLeft.Equals(other.WeightLeft) &&
             EqualStrings(VarName, other.VarName);
         } else {
@@ -79 +89 @@
     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]
@@ -98 +163 @@
     }
 
-    internal RegressionTreeModel(TreeNode[] tree)
-      : base("RegressionTreeModel", "Represents a decision tree for regression.") {
+    internal RegressionTreeModel(TreeNode[] tree, string targetVariable)
+      : base(targetVariable, "RegressionTreeModel", "Represents a decision tree for regression.") {
       this.tree = tree;
     }
@@ -108 +173 @@
         if (node.VarName == TreeNode.NO_VARIABLE)
           return node.Val;
-
-        if (columnCache[nodeIdx][row] <= node.Val)
+        if (columnCache[nodeIdx] == null || double.IsNaN(columnCache[nodeIdx][row])) {
+          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
@@ -121 +190 @@
     }
 
-    public IEnumerable<double> GetEstimatedValues(IDataset ds, IEnumerable<int> rows) {
+    public override IEnumerable<double> GetEstimatedValues(IDataset ds, IEnumerable<int> rows) {
       // lookup columns for variableNames in one pass over the tree to speed up evaluation later on
       ReadOnlyCollection<double>[] columnCache = new ReadOnlyCollection<double>[tree.Length];
@@ -127 +196 @@
       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);
         }
       }
@@ -133 +204 @@
     }
 
-    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+    public override IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
       return new RegressionSolution(this, new RegressionProblemData(problemData));
     }
@@ -141 +212 @@
       return TreeToString(0, "");
     }
+
+    /// <summary>
+    /// Transforms the tree model to a symbolic regression solution
+    /// </summary>
+    /// <param name="problemData"></param>
+    /// <returns>A new symbolic regression solution which matches the tree model</returns>
+    public ISymbolicRegressionSolution CreateSymbolicRegressionSolution(IRegressionProblemData problemData) {
+      return CreateSymbolicRegressionModel().CreateRegressionSolution(problemData);
+    }
+
+    /// <summary>
+    /// Transforms the tree model to a symbolic regression model
+    /// </summary>
+    /// <returns>A new symbolic regression model which matches the tree model</returns>
+    public SymbolicRegressionModel CreateSymbolicRegressionModel() {
+      var rootSy = new ProgramRootSymbol();
+      var startSy = new StartSymbol();
+      var varCondSy = new VariableCondition() { IgnoreSlope = true };
+      var constSy = new Constant();
+
+      var startNode = startSy.CreateTreeNode();
+      startNode.AddSubtree(CreateSymbolicRegressionTreeRecursive(tree, 0, varCondSy, constSy));
+      var rootNode = rootSy.CreateTreeNode();
+      rootNode.AddSubtree(startNode);
+      return new SymbolicRegressionModel(TargetVariable, new SymbolicExpressionTree(rootNode), new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+    }
+
+    private ISymbolicExpressionTreeNode CreateSymbolicRegressionTreeRecursive(TreeNode[] treeNodes, int nodeIdx, VariableCondition varCondSy, Constant constSy) {
+      var curNode = treeNodes[nodeIdx];
+      if (curNode.VarName == TreeNode.NO_VARIABLE) {
+        var node = (ConstantTreeNode)constSy.CreateTreeNode();
+        node.Value = curNode.Val;
+        return node;
+      } else {
+        var node = (VariableConditionTreeNode)varCondSy.CreateTreeNode();
+        node.VariableName = curNode.VarName;
+        node.Threshold = curNode.Val;
+
+        var left = CreateSymbolicRegressionTreeRecursive(treeNodes, curNode.LeftIdx, varCondSy, constSy);
+        var right = CreateSymbolicRegressionTreeRecursive(treeNodes, curNode.RightIdx, varCondSy, constSy);
+        node.AddSubtree(left);
+        node.AddSubtree(right);
+        return node;
+      }
+    }
+
 
     private string TreeToString(int idx, string part) {
@@ -148 +265 @@
       } 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));
+      }
+    }
+
   }
 }

@@ -24 +24 @@
 protoc.exe
 obj
+.vs