Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs	(revision 12711)
@@ -0,0 +1,252 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Linq;
+using System.Threading;
+using HeuristicLab.Analysis;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
+using HeuristicLab.Problems.DataAnalysis;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  [Item("Gradient Boosted Trees", "Gradient boosted trees algorithm. 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; }
+    }
+
+    #region ParameterNames
+    private const string IterationsParameterName = "Iterations";
+    private const string MaxSizeParameterName = "Maximum Tree Size";
+    private const string NuParameterName = "Nu";
+    private const string RParameterName = "R";
+    private const string MParameterName = "M";
+    private const string SeedParameterName = "Seed";
+    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
+    private const string LossFunctionParameterName = "LossFunction";
+    private const string UpdateIntervalParameterName = "UpdateInterval";
+    private const string CreateSolutionParameterName = "CreateSolution";
+    #endregion
+
+    #region ParameterProperties
+    public IFixedValueParameter<IntValue> IterationsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> MaxSizeParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxSizeParameterName]; }
+    }
+    public IFixedValueParameter<DoubleValue> NuParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[NuParameterName]; }
+    }
+    public IFixedValueParameter<DoubleValue> RParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[RParameterName]; }
+    }
+    public IFixedValueParameter<DoubleValue> MParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[MParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> SeedParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
+    }
+    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
+      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
+    }
+    public IConstrainedValueParameter<StringValue> LossFunctionParameter {
+      get { return (IConstrainedValueParameter<StringValue>)Parameters[LossFunctionParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> UpdateIntervalParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
+    }
+    public IFixedValueParameter<BoolValue> CreateSolutionParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[CreateSolutionParameterName]; }
+    }
+    #endregion
+
+    #region Properties
+    public int Iterations {
+      get { return IterationsParameter.Value.Value; }
+      set { IterationsParameter.Value.Value = value; }
+    }
+    public int Seed {
+      get { return SeedParameter.Value.Value; }
+      set { SeedParameter.Value.Value = value; }
+    }
+    public bool SetSeedRandomly {
+      get { return SetSeedRandomlyParameter.Value.Value; }
+      set { SetSeedRandomlyParameter.Value.Value = value; }
+    }
+    public int MaxSize {
+      get { return MaxSizeParameter.Value.Value; }
+      set { MaxSizeParameter.Value.Value = value; }
+    }
+    public double Nu {
+      get { return NuParameter.Value.Value; }
+      set { NuParameter.Value.Value = value; }
+    }
+    public double R {
+      get { return RParameter.Value.Value; }
+      set { RParameter.Value.Value = value; }
+    }
+    public double M {
+      get { return MParameter.Value.Value; }
+      set { MParameter.Value.Value = value; }
+    }
+    public bool CreateSolution {
+      get { return CreateSolutionParameter.Value.Value; }
+      set { CreateSolutionParameter.Value.Value = value; }
+    }
+    #endregion
+
+    #region ResultsProperties
+    private double ResultsBestQuality {
+      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
+      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
+    }
+    private DataTable ResultsQualities {
+      get { return ((DataTable)Results["Qualities"].Value); }
+    }
+    #endregion
+
+    [StorableConstructor]
+    protected GradientBoostedTreesAlgorithm(bool deserializing) : base(deserializing) { }
+
+    protected GradientBoostedTreesAlgorithm(GradientBoostedTreesAlgorithm original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new GradientBoostedTreesAlgorithm(this, cloner);
+    }
+
+    public GradientBoostedTreesAlgorithm() {
+      Problem = new RegressionProblem(); // default problem
+
+      Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName, "Number of iterations (set as high as possible, adjust in combination with nu, when increasing iterations also decrease nu)", new IntValue(1000)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxSizeParameterName, "Maximal size of the tree learned in each step (prefer smaller sizes if possible)", new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(RParameterName, "Ratio of training rows selected randomly in each step (0 < R <= 1)", new DoubleValue(0.5)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(MParameterName, "Ratio of variables selected randomly in each step (0 < M <= 1)", new DoubleValue(0.5)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(NuParameterName, "Learning rate nu (step size for the gradient update, should be small 0 < nu < 0.1)", new DoubleValue(0.002)));
+      Parameters.Add(new FixedValueParameter<IntValue>(UpdateIntervalParameterName, "", new IntValue(100)));
+      Parameters[UpdateIntervalParameterName].Hidden = true;
+      Parameters.Add(new FixedValueParameter<BoolValue>(CreateSolutionParameterName, "Flag that indicates if a solution should be produced at the end of the run", new BoolValue(true)));
+      Parameters[CreateSolutionParameterName].Hidden = true;
+
+      var lossFunctionNames = ApplicationManager.Manager.GetInstances<ILossFunction>().Select(l => new StringValue(l.ToString()).AsReadOnly());
+      Parameters.Add(new ConstrainedValueParameter<StringValue>(LossFunctionParameterName, "The loss function", new ItemSet<StringValue>(lossFunctionNames)));
+      LossFunctionParameter.ActualValue = LossFunctionParameter.ValidValues.First(l => l.Value.Contains("Squared")); // squared error loss is the default
+    }
+
+
+    protected override void Run(CancellationToken cancellationToken) {
+      // Set up the algorithm
+      if (SetSeedRandomly) Seed = new System.Random().Next();
+
+      // Set up the results display
+      var iterations = new IntValue(0);
+      Results.Add(new Result("Iterations", iterations));
+
+      var table = new DataTable("Qualities");
+      table.Rows.Add(new DataRow("Loss (train)"));
+      table.Rows.Add(new DataRow("Loss (test)"));
+      Results.Add(new Result("Qualities", table));
+      var curLoss = new DoubleValue();
+      Results.Add(new Result("Loss (train)", curLoss));
+
+      // init
+      var problemData = (IRegressionProblemData)Problem.ProblemData.Clone();
+      var lossFunction = ApplicationManager.Manager.GetInstances<ILossFunction>()
+        .Single(l => l.ToString() == LossFunctionParameter.Value.Value);
+      var state = GradientBoostedTreesAlgorithmStatic.CreateGbmState(problemData, lossFunction, (uint)Seed, MaxSize, R, M, Nu);
+
+      var updateInterval = UpdateIntervalParameter.Value.Value;
+      // Loop until iteration limit reached or canceled.
+      for (int i = 0; i < Iterations; i++) {
+        cancellationToken.ThrowIfCancellationRequested();
+
+        GradientBoostedTreesAlgorithmStatic.MakeStep(state);
+
+        // iteration results
+        if (i % updateInterval == 0) {
+          curLoss.Value = state.GetTrainLoss();
+          table.Rows["Loss (train)"].Values.Add(curLoss.Value);
+          table.Rows["Loss (test)"].Values.Add(state.GetTestLoss());
+          iterations.Value = i;
+        }
+      }
+
+      // final results
+      iterations.Value = Iterations;
+      curLoss.Value = state.GetTrainLoss();
+      table.Rows["Loss (train)"].Values.Add(curLoss.Value);
+      table.Rows["Loss (test)"].Values.Add(state.GetTestLoss());
+
+      // produce variable relevance
+      var orderedImpacts = state.GetVariableRelevance().Select(t => new { name = t.Key, impact = t.Value }).ToList();
+
+      var impacts = new DoubleMatrix();
+      var matrix = impacts as IStringConvertibleMatrix;
+      matrix.Rows = orderedImpacts.Count;
+      matrix.RowNames = orderedImpacts.Select(x => x.name);
+      matrix.Columns = 1;
+      matrix.ColumnNames = new string[] { "Relative variable relevance" };
+
+      int rowIdx = 0;
+      foreach (var p in orderedImpacts) {
+        matrix.SetValue(string.Format("{0:N2}", p.impact), rowIdx++, 0);
+      }
+
+      Results.Add(new Result("Variable relevance", impacts));
+      Results.Add(new Result("Loss (test)", new DoubleValue(state.GetTestLoss())));
+
+      // produce solution 
+      if (CreateSolution) {
+        // for logistic regression we produce a classification solution
+        if (lossFunction is LogisticRegressionLoss) {
+          var model = new DiscriminantFunctionClassificationModel(state.GetModel(),
+            new AccuracyMaximizationThresholdCalculator());
+          var classificationProblemData = new ClassificationProblemData(problemData.Dataset,
+            problemData.AllowedInputVariables, problemData.TargetVariable, problemData.Transformations);
+          model.RecalculateModelParameters(classificationProblemData, classificationProblemData.TrainingIndices);
+
+          var classificationSolution = new DiscriminantFunctionClassificationSolution(model, classificationProblemData);
+          Results.Add(new Result("Solution", classificationSolution));
+        } else {
+          // otherwise we produce a regression solution
+          Results.Add(new Result("Solution", new RegressionSolution(state.GetModel(), problemData)));
+        }
+      }
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs	(revision 12711)
@@ -0,0 +1,193 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Random;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  public static class GradientBoostedTreesAlgorithmStatic {
+    #region static API
+
+    public interface IGbmState {
+      IRegressionModel GetModel();
+      double GetTrainLoss();
+      double GetTestLoss();
+      IEnumerable<KeyValuePair<string, double>> GetVariableRelevance();
+    }
+
+    // created through factory method
+    // GbmState details are private API users can only use methods from IGbmState
+    private class GbmState : IGbmState {
+      internal IRegressionProblemData problemData { get; private set; }
+      internal ILossFunction lossFunction { get; private set; }
+      internal int maxSize { get; private set; }
+      internal double nu { get; private set; }
+      internal double r { get; private set; }
+      internal double m { get; private set; }
+      internal int[] trainingRows { get; private set; }
+      internal int[] testRows { get; private set; }
+      internal RegressionTreeBuilder treeBuilder { get; private set; }
+
+      private MersenneTwister random { get; set; }
+
+      // array members (allocate only once)
+      internal double[] pred;
+      internal double[] predTest;
+      internal double[] y;
+      internal int[] activeIdx;
+      internal double[] pseudoRes;
+
+      private readonly IList<IRegressionModel> models;
+      private readonly IList<double> weights;
+
+      public GbmState(IRegressionProblemData problemData, ILossFunction lossFunction, uint randSeed, int maxSize, double r, double m, double nu) {
+        // default settings for MaxSize, Nu and R
+        this.maxSize = maxSize;
+        this.nu = nu;
+        this.r = r;
+        this.m = m;
+
+        random = new MersenneTwister(randSeed);
+        this.problemData = problemData;
+        this.trainingRows = problemData.TrainingIndices.ToArray();
+        this.testRows = problemData.TestIndices.ToArray();
+        this.lossFunction = lossFunction;
+
+        int nRows = trainingRows.Length;
+
+        y = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, trainingRows).ToArray();
+
+        treeBuilder = new RegressionTreeBuilder(problemData, random);
+
+        activeIdx = Enumerable.Range(0, nRows).ToArray();
+
+        var zeros = Enumerable.Repeat(0.0, nRows).ToArray();
+        double f0 = lossFunction.LineSearch(y, zeros, activeIdx, 0, nRows - 1); // initial constant value (mean for squared errors)
+        pred = Enumerable.Repeat(f0, nRows).ToArray();
+        predTest = Enumerable.Repeat(f0, testRows.Length).ToArray();
+        pseudoRes = new double[nRows];
+
+        models = new List<IRegressionModel>();
+        weights = new List<double>();
+        // add constant model
+        models.Add(new ConstantRegressionModel(f0));
+        weights.Add(1.0);
+      }
+
+      public IRegressionModel GetModel() {
+        return new GradientBoostedTreesModel(models, weights);
+      }
+      public IEnumerable<KeyValuePair<string, double>> GetVariableRelevance() {
+        return treeBuilder.GetVariableRelevance();
+      }
+
+      public double GetTrainLoss() {
+        int nRows = y.Length;
+        return lossFunction.GetLoss(y, pred) / nRows;
+      }
+      public double GetTestLoss() {
+        var yTest = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, testRows);
+        var nRows = testRows.Length;
+        return lossFunction.GetLoss(yTest, predTest) / nRows;
+      }
+
+      internal void AddModel(IRegressionModel m, double weight) {
+        models.Add(m);
+        weights.Add(weight);
+      }
+    }
+
+    // simple interface
+    public static IRegressionSolution TrainGbm(IRegressionProblemData problemData, ILossFunction lossFunction, int maxSize, double nu, double r, double m, int maxIterations, uint randSeed = 31415) {
+      Contract.Assert(r > 0);
+      Contract.Assert(r <= 1.0);
+      Contract.Assert(nu > 0);
+      Contract.Assert(nu <= 1.0);
+
+      var state = (GbmState)CreateGbmState(problemData, lossFunction, randSeed, maxSize, r, m, nu);
+
+      for (int iter = 0; iter < maxIterations; iter++) {
+        MakeStep(state);
+      }
+
+      var model = state.GetModel();
+      return new RegressionSolution(model, (IRegressionProblemData)problemData.Clone());
+    }
+
+    // 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) {
+      return new GbmState(problemData, lossFunction, randSeed, maxSize, r, m, nu);
+    }
+
+    // use default settings for maxSize, nu, r from state
+    public static void MakeStep(IGbmState state) {
+      var gbmState = state as GbmState;
+      if (gbmState == null) throw new ArgumentException("state");
+
+      MakeStep(gbmState, gbmState.maxSize, gbmState.nu, gbmState.r, gbmState.m);
+    }
+
+    // allow dynamic adaptation of maxSize, nu and r (even though this is not used)
+    public static void MakeStep(IGbmState state, int maxSize, double nu, double r, double m) {
+      var gbmState = state as GbmState;
+      if (gbmState == null) throw new ArgumentException("state");
+
+      var problemData = gbmState.problemData;
+      var lossFunction = gbmState.lossFunction;
+      var yPred = gbmState.pred;
+      var yPredTest = gbmState.predTest;
+      var treeBuilder = gbmState.treeBuilder;
+      var y = gbmState.y;
+      var activeIdx = gbmState.activeIdx;
+      var pseudoRes = gbmState.pseudoRes;
+      var trainingRows = gbmState.trainingRows;
+      var testRows = gbmState.testRows;
+
+      // copy output of gradient function to pre-allocated rim array (pseudo-residual per row and model)
+      int rimIdx = 0;
+      foreach (var g in lossFunction.GetLossGradient(y, yPred)) {
+        pseudoRes[rimIdx++] = g;
+      }
+
+      var tree = treeBuilder.CreateRegressionTreeForGradientBoosting(pseudoRes, yPred, maxSize, activeIdx, lossFunction, r, m);
+
+      int i = 0;
+      foreach (var pred in tree.GetEstimatedValues(problemData.Dataset, trainingRows)) {
+        yPred[i] = yPred[i] + nu * pred;
+        i++;
+      }
+      // update predictions for validation set
+      i = 0;
+      foreach (var pred in tree.GetEstimatedValues(problemData.Dataset, testRows)) {
+        yPredTest[i] = yPredTest[i] + nu * pred;
+        i++;
+      }
+
+      gbmState.AddModel(tree, nu);
+    }
+    #endregion
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs	(revision 12711)
@@ -0,0 +1,83 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#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;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  [StorableClass]
+  [Item("Gradient boosted tree model", "")]
+  // this is essentially a collection of weighted regression models
+  public sealed class GradientBoostedTreesModel : NamedItem, IRegressionModel {
+    [Storable]
+    private readonly IList<IRegressionModel> models;
+    public IEnumerable<IRegressionModel> Models { get { return models; } }
+
+    [Storable]
+    private readonly IList<double> weights;
+    public IEnumerable<double> Weights { get { return weights; } }
+
+    [StorableConstructor]
+    private GradientBoostedTreesModel(bool deserializing) : base(deserializing) { }
+    private GradientBoostedTreesModel(GradientBoostedTreesModel original, Cloner cloner)
+      : base(original, cloner) {
+      this.weights = new List<double>(original.weights);
+      this.models = new List<IRegressionModel>(original.models.Select(m => cloner.Clone(m)));
+    }
+    public GradientBoostedTreesModel(IEnumerable<IRegressionModel> models, IEnumerable<double> weights)
+      : base("Gradient boosted tree model", string.Empty) {
+      this.models = new List<IRegressionModel>(models);
+      this.weights = new List<double>(weights);
+
+      if (this.models.Count != this.weights.Count) throw new ArgumentException();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new GradientBoostedTreesModel(this, cloner);
+    }
+
+    public 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.
+                                                          // (which essentially looks up indexes in a dictionary)
+      var res = new double[rows.Count()];
+      for (int i = 0; i < models.Count; i++) {
+        var w = weights[i];
+        var m = models[i];
+        int r = 0;
+        foreach (var est in m.GetEstimatedValues(dataset, rows)) {
+          res[r++] += w * est;
+        }
+      }
+      return res;
+    }
+
+    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+      return new RegressionSolution(this, (IRegressionProblemData)problemData.Clone());
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/AbsoluteErrorLoss.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/AbsoluteErrorLoss.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/AbsoluteErrorLoss.cs	(revision 12711)
@@ -0,0 +1,83 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  // loss function for the weighted absolute error
+  public class AbsoluteErrorLoss : ILossFunction {
+    public double GetLoss(IEnumerable<double> target, IEnumerable<double> pred) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      double s = 0;
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        double res = targetEnum.Current - predEnum.Current;
+        s += Math.Abs(res);  // |res|
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have differing lengths");
+
+      return s;
+    }
+
+    public IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        // dL(y, f(x)) / df(x) = sign(res)
+        var res = targetEnum.Current - predEnum.Current;
+        if (res > 0) yield return 1.0;
+        else if (res < 0) yield return -1.0;
+        else yield return 0.0;
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have differing lengths");
+    }
+
+    // return median of residuals
+    // targetArr and predArr are not changed by LineSearch
+    public double LineSearch(double[] targetArr, double[] predArr, int[] idx, int startIdx, int endIdx) {
+      if (targetArr.Length != predArr.Length)
+        throw new ArgumentException("target and pred have differing lengths");
+
+      // Median() is allocating an array anyway
+      // It would be possible to pre-allocated an array for the residuals if Median() would allow specification of a sub-range
+      int nRows = endIdx - startIdx + 1;
+      var res = new double[nRows];
+      for (int i = startIdx; i <= endIdx; i++) {
+        var row = idx[i];
+        res[i - startIdx] = targetArr[row] - predArr[row];
+      }
+      return res.Median(); // TODO: improve efficiency
+    }
+
+    public override string ToString() {
+      return "Absolute error loss";
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs	(revision 12711)
@@ -0,0 +1,41 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System.Collections.Generic;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  // 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)
+  public interface ILossFunction {
+    // returns the loss of the current prediction vector 
+    double GetLoss(IEnumerable<double> target, IEnumerable<double> pred);
+
+    // returns an enumerable of the loss gradient for each row
+    IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred);
+
+    // returns the optimal value for the partition of rows stored in idx[startIdx] .. idx[endIdx] inclusive
+    double LineSearch(double[] targetArr, double[] predArr, int[] idx, int startIdx, int endIdx);
+  }
+}
+
+
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/LogisticRegressionLoss.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/LogisticRegressionLoss.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/LogisticRegressionLoss.cs	(revision 12711)
@@ -0,0 +1,89 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+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) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      double s = 0;
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        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 += Math.Log(1 + Math.Exp(-2 * y * predEnum.Current));
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have different lengths");
+
+      return s;
+    }
+
+    public IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        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 2 * y / (1 + Math.Exp(2 * y * predEnum.Current));
+
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have different lengths");
+    }
+
+    // targetArr and predArr are not changed by LineSearch
+    public double LineSearch(double[] targetArr, double[] predArr, int[] idx, int startIdx, int endIdx) {
+      if (targetArr.Length != predArr.Length)
+        throw new ArgumentException("target and pred have different lengths");
+
+      // "Simple Newton-Raphson step" of eqn. 23 
+      double sumY = 0.0;
+      double sumDiff = 0.0;
+      for (int i = startIdx; i <= endIdx; i++) {
+        var row = idx[i];
+        var y = targetArr[row] * 2 - 1; // y in {-1,1}
+        var pseudoResponse = 2 * y / (1 + Math.Exp(2 * y * predArr[row]));
+
+        sumY += pseudoResponse;
+        sumDiff += Math.Abs(pseudoResponse) * (2 - Math.Abs(pseudoResponse));
+      }
+      // prevent divByZero
+      sumDiff = Math.Max(1E-12, sumDiff);
+      return sumY / sumDiff;
+    }
+
+    public override string ToString() {
+      return "Logistic regression loss";
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/RelativeErrorLoss.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/RelativeErrorLoss.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/RelativeErrorLoss.cs	(revision 12711)
@@ -0,0 +1,111 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  // 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) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      double s = 0;
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        double res = targetEnum.Current - predEnum.Current;
+        s += Math.Abs(res) * Math.Abs(1.0 / targetEnum.Current);
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have different lengths");
+
+      return s;
+    }
+
+    public IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        // sign(res) * abs(1 / target)
+        var res = targetEnum.Current - predEnum.Current;
+        if (res > 0) yield return 1.0 / Math.Abs(targetEnum.Current);
+        else if (res < 0) yield return -1.0 / Math.Abs(targetEnum.Current);
+        else yield return 0.0;
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have different lengths");
+    }
+
+    // targetArr and predArr are not changed by LineSearch
+    public double LineSearch(double[] targetArr, double[] predArr, int[] idx, int startIdx, int endIdx) {
+      if (targetArr.Length != predArr.Length)
+        throw new ArgumentException("target and pred have different lengths");
+
+      // line search for relative error
+      // weighted median (weight = 1/target)
+      int nRows = endIdx - startIdx + 1; // startIdx and endIdx are inclusive
+      if (nRows == 1) return targetArr[idx[startIdx]] - predArr[idx[startIdx]]; // res 
+      else if (nRows == 2) {
+        // weighted average of two residuals
+        var w0 = Math.Abs(1.0 / targetArr[idx[startIdx]]);
+        var w1 = Math.Abs(1.0 / targetArr[idx[endIdx]]);
+        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 {
+        // 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 = Math.Abs(1.0 / targetArr[row]);
+          res_w[i - startIdx] = new KeyValuePair<double, double>(res, w);
+          totalWeight += w;
+        }
+        // TODO: improve efficiency (find median without sort)
+        res_w.StableSort((a, b) => Math.Sign(a.Key - b.Key));
+
+        int k = 0;
+        double sum = totalWeight - res_w[k].Value; // total - first weight
+        while (sum > totalWeight / 2) {
+          k++;
+          sum -= res_w[k].Value;
+        }
+        return res_w[k].Key;
+      }
+    }
+
+    public override string ToString() {
+      return "Relative error loss";
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs	(revision 12711)
@@ -0,0 +1,76 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  public class SquaredErrorLoss : ILossFunction {
+    public double GetLoss(IEnumerable<double> target, IEnumerable<double> pred) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      double s = 0;
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        double res = targetEnum.Current - predEnum.Current;
+        s += res * res; // (res)^2
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have different lengths");
+
+      return s;
+    }
+
+    public IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+
+      while (targetEnum.MoveNext() & predEnum.MoveNext()) {
+        yield return 2.0 * (targetEnum.Current - predEnum.Current); // dL(y, f(x)) / df(x)  = 2 * res 
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext())
+        throw new ArgumentException("target and pred have different lengths");
+    }
+
+    // targetArr and predArr are not changed by LineSearch
+    public double LineSearch(double[] targetArr, double[] predArr, int[] idx, int startIdx, int endIdx) {
+      if (targetArr.Length != predArr.Length)
+        throw new ArgumentException("target and pred have different lengths");
+
+      // 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
+      double s = 0.0;
+      int n = 0;
+      for (int i = startIdx; i <= endIdx; i++) {
+        int row = idx[i];
+        s += (targetArr[row] - predArr[row]);
+        n++;
+      }
+      return s / n;
+    }
+
+    public override string ToString() {
+      return "Squared error loss";
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs	(revision 12711)
@@ -0,0 +1,493 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Core;
+using HeuristicLab.Problems.DataAnalysis;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  // This class implements a greedy decision tree learner which selects splits with the maximum reduction in sum of squared errors.
+  // The tree builder also tracks variable relevance metrics based on the splits and improvement after the split.
+  // The implementation is tuned for gradient boosting where multiple trees have to be calculated for the same training data 
+  // each time with a different target vector. Vectors of idx to allow iteration of intput variables in sorted order are
+  // pre-calculated so that optimal thresholds for splits can be calculated in O(n) for each input variable.
+  // After each split the row idx are partitioned in a left an right part.
+  internal class RegressionTreeBuilder {
+    private readonly IRandom random;
+    private readonly IRegressionProblemData problemData;
+
+    private readonly int nCols;
+    private readonly double[][] x; // all training data (original order from problemData), x is constant
+    private double[] originalY; // the original target labels (from problemData), originalY is constant
+    private double[] curPred; // current predictions for originalY (in case we are using gradient boosting, otherwise = zeros), only necessary for line search
+
+    private double[] y; // training labels (original order from problemData), y can be changed
+
+    private Dictionary<string, double> sumImprovements; // for variable relevance calculation
+
+    private readonly string[] allowedVariables; // all variables in shuffled order
+    private Dictionary<string, int> varName2Index; // maps the variable names to column indexes 
+    private int effectiveVars; // number of variables that are used from allowedVariables
+
+    private int effectiveRows; // number of rows that are used from 
+    private readonly int[][] sortedIdxAll;
+    private readonly int[][] sortedIdx; // random selection from sortedIdxAll (for r < 1.0)
+
+    // helper arrays which are allocated to maximal necessary size only once in the ctor
+    private readonly int[] internalIdx, which, leftTmp, rightTmp;
+    private readonly double[] outx;
+    private readonly int[] outSortedIdx;
+
+    private RegressionTreeModel.TreeNode[] tree; // tree is represented as a flat array of nodes
+    private int curTreeNodeIdx; // the index where the next tree node is stored
+
+    // This class represents information about potential splits.
+    // For each node generated the best splitting variable and threshold as well as
+    // the improvement from the split are stored in a priority queue
+    private class PartitionSplits {
+      public int ParentNodeIdx { get; set; } // the idx of the leaf node representing this partition 
+      public int StartIdx { get; set; } // the start idx of the partition
+      public int EndIndex { get; set; } // the end idx of the partition
+      public string SplittingVariable { get; set; } // the best splitting variable
+      public double SplittingThreshold { get; set; } // the best threshold
+      public double SplittingImprovement { get; set; } // the improvement of the split (for priority queue)
+    }
+
+    // this list hold partitions with the information about the best split (organized as a sorted queue)
+    private readonly IList<PartitionSplits> queue;
+
+    // prepare and allocate buffer variables in ctor
+    public RegressionTreeBuilder(IRegressionProblemData problemData, IRandom random) {
+      this.problemData = problemData;
+      this.random = random;
+
+      var rows = problemData.TrainingIndices.Count();
+
+      this.nCols = problemData.AllowedInputVariables.Count();
+
+      allowedVariables = problemData.AllowedInputVariables.ToArray();
+      varName2Index = new Dictionary<string, int>(allowedVariables.Length);
+      for (int i = 0; i < allowedVariables.Length; i++) varName2Index.Add(allowedVariables[i], i);
+
+      sortedIdxAll = new int[nCols][];
+      sortedIdx = new int[nCols][];
+      sumImprovements = new Dictionary<string, double>();
+      internalIdx = new int[rows];
+      which = new int[rows];
+      leftTmp = new int[rows];
+      rightTmp = new int[rows];
+      outx = new double[rows];
+      outSortedIdx = new int[rows];
+      queue = new List<PartitionSplits>(100);
+
+      x = new double[nCols][];
+      originalY = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
+      y = new double[originalY.Length];
+      Array.Copy(originalY, y, y.Length); // copy values (originalY is fixed, y is changed in gradient boosting)
+      curPred = Enumerable.Repeat(0.0, y.Length).ToArray(); // zeros
+
+      int col = 0;
+      foreach (var inputVariable in problemData.AllowedInputVariables) {
+        x[col] = problemData.Dataset.GetDoubleValues(inputVariable, problemData.TrainingIndices).ToArray();
+        sortedIdxAll[col] = Enumerable.Range(0, rows).OrderBy(r => x[col][r]).ToArray();
+        sortedIdx[col] = new int[rows];
+        col++;
+      }
+    }
+
+    // simple API produces a single regression tree optimizing sum of squared errors
+    // this can be used if only a simple regression tree should be produced
+    // for a set of trees use the method CreateRegressionTreeForGradientBoosting below
+    //
+    // r and m work in the same way as for alglib random forest
+    // r is fraction of rows to use for training
+    // m is fraction of variables to use for training
+    public IRegressionModel CreateRegressionTree(int maxSize, double r = 0.5, double m = 0.5) {
+      // subtract mean of y first
+      var yAvg = y.Average();
+      for (int i = 0; i < y.Length; i++) y[i] -= yAvg;
+
+      var seLoss = new SquaredErrorLoss();
+
+      var model = CreateRegressionTreeForGradientBoosting(y, curPred, maxSize, problemData.TrainingIndices.ToArray(), seLoss, r, m);
+
+      return new GradientBoostedTreesModel(new[] { new ConstantRegressionModel(yAvg), model }, new[] { 1.0, 1.0 });
+    }
+
+    // specific interface that allows to specify the target labels and the training rows which is necessary when for gradient boosted trees
+    public IRegressionModel CreateRegressionTreeForGradientBoosting(double[] y, double[] curPred, int maxSize, int[] idx, ILossFunction lossFunction, double r = 0.5, double m = 0.5) {
+      Debug.Assert(maxSize > 0);
+      Debug.Assert(r > 0);
+      Debug.Assert(r <= 1.0);
+      Debug.Assert(y.Count() == this.y.Length);
+      Debug.Assert(m > 0);
+      Debug.Assert(m <= 1.0);
+
+      // y and curPred are changed in gradient boosting
+      this.y = y; 
+      this.curPred = curPred; 
+
+      // shuffle row idx
+      HeuristicLab.Random.ListExtensions.ShuffleInPlace(idx, random);
+
+      int nRows = idx.Count();
+
+      // shuffle variable idx
+      HeuristicLab.Random.ListExtensions.ShuffleInPlace(allowedVariables, random);
+
+      // only select a part of the rows and columns randomly
+      effectiveRows = (int)Math.Ceiling(nRows * r);
+      effectiveVars = (int)Math.Ceiling(nCols * m);
+
+      // the which array is used for partitioing row idxs  
+      Array.Clear(which, 0, which.Length);
+
+      // mark selected rows
+      for (int row = 0; row < effectiveRows; row++) {
+        which[idx[row]] = 1; // we use the which vector as a temporary variable here
+        internalIdx[row] = idx[row];
+      }
+
+      for (int col = 0; col < nCols; col++) {
+        int i = 0;
+        for (int row = 0; row < nRows; row++) {
+          if (which[sortedIdxAll[col][row]] > 0) {
+            Debug.Assert(i < effectiveRows);
+            sortedIdx[col][i] = sortedIdxAll[col][row];
+            i++;
+          }
+        }
+      }
+
+      this.tree = new RegressionTreeModel.TreeNode[maxSize];
+      this.queue.Clear();
+      this.curTreeNodeIdx = 0;
+
+      // start out with only one leaf node (constant prediction)
+      // and calculate the best split for this root node and enqueue it into a queue sorted by improvement throught the split
+      // start and end idx are inclusive
+      CreateLeafNode(0, effectiveRows - 1, lossFunction);
+
+      // process the priority queue to complete the tree
+      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
+    private void CreateRegressionTreeFromQueue(int maxNodes, ILossFunction lossFunction) {
+      while (queue.Any() && curTreeNodeIdx + 1 < maxNodes) { // two nodes are created in each loop
+        var f = queue[queue.Count - 1]; // last element has the largest improvement
+        queue.RemoveAt(queue.Count - 1);
+
+        var startIdx = f.StartIdx;
+        var endIdx = f.EndIndex;
+
+        Debug.Assert(endIdx - startIdx >= 0);
+        Debug.Assert(startIdx >= 0);
+        Debug.Assert(endIdx < internalIdx.Length);
+
+        // split partition into left and right
+        int splitIdx;
+        SplitPartition(f.StartIdx, f.EndIndex, f.SplittingVariable, f.SplittingThreshold, out splitIdx);
+        Debug.Assert(splitIdx + 1 <= endIdx);
+        Debug.Assert(startIdx <= splitIdx);
+
+        // create two leaf nodes (and enqueue best splits for both)
+        var leftTreeIdx = CreateLeafNode(startIdx, splitIdx, lossFunction);
+        var rightTreeIdx = CreateLeafNode(splitIdx + 1, endIdx, lossFunction);
+
+        // overwrite existing leaf node with an internal node
+        tree[f.ParentNodeIdx] = new RegressionTreeModel.TreeNode(f.SplittingVariable, f.SplittingThreshold, leftTreeIdx, rightTreeIdx);
+      }
+    }
+
+
+    // returns the index of the newly created tree node
+    private int CreateLeafNode(int startIdx, int endIdx, ILossFunction lossFunction) {
+      // write a leaf node
+      var val = lossFunction.LineSearch(originalY, curPred, internalIdx, startIdx, endIdx);
+      tree[curTreeNodeIdx] = new RegressionTreeModel.TreeNode(RegressionTreeModel.TreeNode.NO_VARIABLE, val);
+
+      EnqueuePartitionSplit(curTreeNodeIdx, startIdx, endIdx);
+      curTreeNodeIdx++;
+      return curTreeNodeIdx - 1;
+    }
+
+
+    // calculates the optimal split for the partition [startIdx .. endIdx] (inclusive) 
+    // which is represented by the leaf node with the specified nodeIdx
+    private void EnqueuePartitionSplit(int nodeIdx, int startIdx, int endIdx) {
+      double threshold, improvement;
+      string bestVariableName;
+      // only enqueue a new split if there are at least 2 rows left and a split is possible
+      if (startIdx < endIdx &&
+        FindBestVariableAndThreshold(startIdx, endIdx, out threshold, out bestVariableName, out improvement)) {
+        var split = new PartitionSplits() {
+          ParentNodeIdx = nodeIdx,
+          StartIdx = startIdx,
+          EndIndex = endIdx,
+          SplittingThreshold = threshold,
+          SplittingVariable = bestVariableName
+        };
+        InsertSortedQueue(split);
+      }
+    }
+
+
+    // routine for splitting a partition of rows stored in internalIdx between startIdx and endIdx into
+    // a left partition and a right partition using the given splittingVariable and threshold
+    // the splitIdx is the last index of the left partition 
+    // splitIdx + 1 is the first index of the right partition
+    // startIdx and endIdx are inclusive
+    private void SplitPartition(int startIdx, int endIdx, string splittingVar, double threshold, out int splitIdx) {
+      int bestVarIdx = varName2Index[splittingVar];
+      // split - two pass
+
+      // store which index goes into which partition 
+      for (int k = startIdx; k <= endIdx; k++) {
+        if (x[bestVarIdx][internalIdx[k]] <= threshold)
+          which[internalIdx[k]] = -1; // left partition
+        else
+          which[internalIdx[k]] = 1; // right partition
+      }
+
+      // partition sortedIdx for each variable
+      int i;
+      int j;
+      for (int col = 0; col < nCols; col++) {
+        i = 0;
+        j = 0;
+        int k;
+        for (k = startIdx; k <= endIdx; k++) {
+          Debug.Assert(Math.Abs(which[sortedIdx[col][k]]) == 1);
+
+          if (which[sortedIdx[col][k]] < 0) {
+            leftTmp[i++] = sortedIdx[col][k];
+          } else {
+            rightTmp[j++] = sortedIdx[col][k];
+          }
+        }
+        Debug.Assert(i > 0); // at least on element in the left partition
+        Debug.Assert(j > 0); // at least one element in the right partition
+        Debug.Assert(i + j == endIdx - startIdx + 1);
+        k = startIdx;
+        for (int l = 0; l < i; l++) sortedIdx[col][k++] = leftTmp[l];
+        for (int l = 0; l < j; l++) sortedIdx[col][k++] = rightTmp[l];
+      }
+
+      // partition row indices
+      i = startIdx;
+      j = endIdx;
+      while (i <= j) {
+        Debug.Assert(Math.Abs(which[internalIdx[i]]) == 1);
+        Debug.Assert(Math.Abs(which[internalIdx[j]]) == 1);
+        if (which[internalIdx[i]] < 0) i++;
+        else if (which[internalIdx[j]] > 0) j--;
+        else {
+          Debug.Assert(which[internalIdx[i]] > 0);
+          Debug.Assert(which[internalIdx[j]] < 0);
+          // swap
+          int tmp = internalIdx[i];
+          internalIdx[i] = internalIdx[j];
+          internalIdx[j] = tmp;
+          i++;
+          j--;
+        }
+      }
+      Debug.Assert(j + 1 == i);
+      Debug.Assert(i <= endIdx);
+      Debug.Assert(startIdx <= j);
+
+      splitIdx = j;
+    }
+
+    private bool FindBestVariableAndThreshold(int startIdx, int endIdx, out double threshold, out string bestVar, out double improvement) {
+      Debug.Assert(startIdx < endIdx + 1); // at least 2 elements
+
+      int rows = endIdx - startIdx + 1;
+      Debug.Assert(rows >= 2);
+
+      double sumY = 0.0;
+      for (int i = startIdx; i <= endIdx; i++) {
+        sumY += y[internalIdx[i]];
+      }
+
+      // 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;
+
+      for (int col = 0; col < effectiveVars; col++) {
+        // sort values for variable to prepare for threshold selection 
+        var curVariable = allowedVariables[col];
+        var curVariableIdx = varName2Index[curVariable];
+        for (int i = startIdx; i <= endIdx; i++) {
+          var sortedI = sortedIdx[curVariableIdx][i];
+          outSortedIdx[i - startIdx] = sortedI;
+          outx[i - startIdx] = x[curVariableIdx][sortedI];
+        }
+
+        double curImprovement;
+        double curThreshold;
+        FindBestThreshold(outx, outSortedIdx, rows, y, sumY, out curThreshold, out curImprovement);
+
+        if (curImprovement > bestImprovement) {
+          bestImprovement = curImprovement;
+          bestThreshold = curThreshold;
+          bestVar = allowedVariables[col];
+        }
+      }
+      if (bestVar == RegressionTreeModel.TreeNode.NO_VARIABLE) {
+        // not successfull
+        threshold = double.PositiveInfinity;
+        improvement = double.NegativeInfinity;
+        return false;
+      } else {
+        UpdateVariableRelevance(bestVar, sumY, bestImprovement, rows);
+        improvement = bestImprovement;
+        threshold = bestThreshold;
+        return true;
+      }
+    }
+
+    // x [0..N-1] contains rows sorted values in the range from [0..rows-1]
+    // sortedIdx [0..N-1] contains the idx of the values in x in the original dataset in the range from [0..rows-1]
+    // rows specifies the number of valid entries in x and sortedIdx
+    // y [0..N-1] contains the target values in original sorting order
+    // sumY is y.Sum()
+    // 
+    // the routine returns the best threshold (x[i] + x[i+1]) / 2 for i = [0 .. rows-2] by calculating the reduction in squared error
+    // additionally the reduction in squared error is returned in bestImprovement
+    // if all elements of x are equal the routing fails to produce a threshold
+    private static void FindBestThreshold(double[] x, int[] sortedIdx, int rows, double[] y, double sumY, out double bestThreshold, out double bestImprovement) {
+      Debug.Assert(rows >= 2);
+
+      double sl = 0.0;
+      double sr = sumY;
+      double nl = 0.0;
+      double nr = rows;
+
+      bestImprovement = 1.0 / rows * sumY * sumY; // this is the baseline for the improvement
+      bestThreshold = double.NegativeInfinity;
+      // for all thresholds
+      // if we have n rows there are n-1 possible splits
+      for (int i = 0; i < rows - 1; i++) {
+        sl += y[sortedIdx[i]];
+        sr -= y[sortedIdx[i]];
+
+        nl++;
+        nr--;
+        Debug.Assert(nl > 0);
+        Debug.Assert(nr > 0);
+
+        if (x[i] < x[i + 1]) { // don't try to split when two elements are equal
+
+          // goal is to find the split with leading to minimal total variance of left and right parts
+          // 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))²)
+          //    = 1/n * sum(y_l²) - 1/nl * 1/n * sum(y_l)² + 1/n * sum(y_r²) - 1/nr * 1/n * sum(y_r)²
+          //    = 1/n * (sum(y_l²) + sum(y_r²)) - 1/n * (sum(y_l)² / nl + sum(y_r)² / nr)
+          //    = 1/n * sum(y²) - 1/n * (sum(y_l)² / nl + sum(y_r)² / nr)
+          //      -------------
+          //       not changed by split (and the same for total variance without partitioning)
+          //
+          //   therefore we need to find the maximum value (sum(y_l)² / nl + sum(y_r)² / nr) (ignoring the factor 1/n)
+          //   and this value must be larger than 1/n * sum(y)² to be an improvement over no split 
+
+          double curQuality = sl * sl / nl + sr * sr / nr;
+
+          if (curQuality > bestImprovement) {
+            bestThreshold = (x[i] + x[i + 1]) / 2.0;
+            bestImprovement = curQuality;
+          }
+        }
+      }
+
+      // if all elements where the same then no split can be found
+    }
+
+
+    private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
+      if (string.IsNullOrEmpty(bestVar)) return;
+      // update variable relevance
+      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)) {
+        sumImprovements[bestVar] = delta;
+      }
+      sumImprovements[bestVar] = v + delta;
+    }
+
+    public IEnumerable<KeyValuePair<string, double>> GetVariableRelevance() {
+      // values are scaled: the most important variable has relevance = 100
+      double scaling = 100 / sumImprovements.Max(t => t.Value);
+      return
+        sumImprovements
+        .Select(t => new KeyValuePair<string, double>(t.Key, t.Value * scaling))
+        .OrderByDescending(t => t.Value);
+    }
+
+
+    // insert a new parition split (find insertion point and start at first element of the queue)
+    // elements are removed from the queue at the last position
+    // O(n), splits could be organized as a heap to improve runtime (see alglib tsort)
+    private void InsertSortedQueue(PartitionSplits split) {
+      // find insertion position
+      int i = 0;
+      while (i < queue.Count && queue[i].SplittingImprovement < split.SplittingImprovement) { i++; }
+
+      queue.Insert(i, split);
+    }
+  }
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs	(revision 12711)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs	(revision 12711)
@@ -0,0 +1,153 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Globalization;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.DataAnalysis;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  [StorableClass]
+  [Item("RegressionTreeModel", "Represents a decision tree for regression.")]
+  public sealed class RegressionTreeModel : NamedItem, IRegressionModel {
+
+    // trees are represented as a flat array    
+    internal struct TreeNode {
+      public readonly static string NO_VARIABLE = null;
+
+      public TreeNode(string varName, double val, int leftIdx = -1, int rightIdx = -1)
+        : this() {
+        VarName = varName;
+        Val = val;
+        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; }
+
+      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
+      public override int GetHashCode() {
+        return LeftIdx ^ RightIdx ^ Val.GetHashCode();
+      }
+      // necessary because of GetHashCode override
+      public override bool Equals(object obj) {
+        if (obj is TreeNode) {
+          var other = (TreeNode)obj;
+          return Val.Equals(other.Val) &&
+            LeftIdx.Equals(other.LeftIdx) &&
+            RightIdx.Equals(other.RightIdx) &&
+            EqualStrings(VarName, other.VarName);
+        } else {
+          return false;
+        }
+      }
+
+      private bool EqualStrings(string a, string b) {
+        return (a == null && b == null) ||
+               (a != null && b != null && a.Equals(b));
+      }
+    }
+
+    // not storable!
+    private TreeNode[] tree;
+
+    [Storable]
+    // 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]
+    private RegressionTreeModel(bool serializing) : base(serializing) { }
+    // cloning ctor
+    private RegressionTreeModel(RegressionTreeModel original, Cloner cloner)
+      : base(original, cloner) {
+      if (original.tree != null) {
+        this.tree = new TreeNode[original.tree.Length];
+        Array.Copy(original.tree, this.tree, this.tree.Length);
+      }
+    }
+
+    internal RegressionTreeModel(TreeNode[] tree)
+      : base("RegressionTreeModel", "Represents a decision tree for regression.") {
+      this.tree = tree;
+    }
+
+    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");
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new RegressionTreeModel(this, cloner);
+    }
+
+    public IEnumerable<double> GetEstimatedValues(IDataset ds, IEnumerable<int> rows) {
+      // 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));
+    }
+
+    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+      return new RegressionSolution(this, new RegressionProblemData(problemData));
+    }
+
+    // mainly for debugging
+    public override string ToString() {
+      return TreeToString(0, "");
+    }
+
+    private string TreeToString(int idx, string part) {
+      var n = tree[idx];
+      if (n.VarName == TreeNode.NO_VARIABLE) {
+        return string.Format(CultureInfo.InvariantCulture, "{0} -> {1:F}{2}", part, n.Val, Environment.NewLine);
+      } 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));
+      }
+    }
+  }
+}
Index: /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj
===================================================================
--- /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 12710)
+++ /stable/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 12711)
@@ -195,4 +195,14 @@
     <Compile Include="GaussianProcess\GaussianProcessRegressionSolution.cs" />
     <Compile Include="GaussianProcess\ICovarianceFunction.cs" />
+    <Compile Include="GradientBoostedTrees\GradientBoostedTreesAlgorithm.cs" />
+    <Compile Include="GradientBoostedTrees\GradientBoostedTreesAlgorithmStatic.cs" />
+    <Compile Include="GradientBoostedTrees\GradientBoostedTreesModel.cs" />
+    <Compile Include="GradientBoostedTrees\LossFunctions\AbsoluteErrorLoss.cs" />
+    <Compile Include="GradientBoostedTrees\LossFunctions\ILossFunction.cs" />
+    <Compile Include="GradientBoostedTrees\LossFunctions\LogisticRegressionLoss.cs" />
+    <Compile Include="GradientBoostedTrees\LossFunctions\RelativeErrorLoss.cs" />
+    <Compile Include="GradientBoostedTrees\LossFunctions\SquaredErrorLoss.cs" />
+    <Compile Include="GradientBoostedTrees\RegressionTreeBuilder.cs" />
+    <Compile Include="GradientBoostedTrees\RegressionTreeModel.cs" />
     <Compile Include="Interfaces\IGaussianProcessClassificationModelCreator.cs" />
     <Compile Include="Interfaces\IGaussianProcessRegressionModelCreator.cs" />
Index: /stable/HeuristicLab.Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/GradientBoostingTest.cs
===================================================================
--- /stable/HeuristicLab.Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/GradientBoostingTest.cs	(revision 12711)
+++ /stable/HeuristicLab.Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/GradientBoostingTest.cs	(revision 12711)
@@ -0,0 +1,279 @@
+﻿using System;
+using System.Linq;
+using System.Threading;
+using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using HeuristicLab.Problems.DataAnalysis;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  [TestClass()]
+  public class GradientBoostingTest {
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void DecisionTreeTest() {
+      {
+        var xy = new double[,]
+        {
+          {-1, 20, 0},
+          {-1, 20, 0},
+          { 1, 10, 0},
+          { 1, 10, 0},
+        };
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // x1 <= 15 -> 1 
+        // x1 >  15 -> -1
+        BuildTree(xy, allVariables, 10);
+      }
+
+
+      {
+        var xy = new double[,]
+        {
+          {-1, 20,  1},
+          {-1, 20, -1},
+          { 1, 10, -1},
+          { 1, 10, 1},
+        };
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // ignore irrelevant variables
+        // x1 <= 15 -> 1 
+        // x1 >  15 -> -1
+        BuildTree(xy, allVariables, 10);
+      }
+
+      {
+        // split must be by x1 first 
+        var xy = new double[,]
+        {
+          {-2, 20,  1},
+          {-1, 20, -1},
+          { 1, 10, -1},
+          { 2, 10, 1},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // x1 <= 15 AND x2 <= 0 -> 1 
+        // x1 <= 15 AND x2 >  0 -> 2 
+        // x1 >  15 AND x2 <= 0 -> -1
+        // x1 >  15 AND x2 >  0 -> -2
+        BuildTree(xy, allVariables, 10);
+      }
+
+      {
+        // averaging ys
+        var xy = new double[,]
+        {
+          {-2.5, 20,  1},
+          {-1.5, 20,  1},
+          {-1.5, 20, -1},
+          {-0.5, 20, -1},
+          {0.5, 10, -1},
+          {1.5, 10, -1},
+          {1.5, 10, 1},
+          {2.5, 10, 1},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // x1 <= 15 AND x2 <= 0 -> 1 
+        // x1 <= 15 AND x2 >  0 -> 2 
+        // x1 >  15 AND x2 <= 0 -> -1
+        // x1 >  15 AND x2 >  0 -> -2
+        BuildTree(xy, allVariables, 10);
+      }
+
+
+      {
+        // diagonal split (no split possible)
+        var xy = new double[,]
+        {
+          { 1, 1, 1},
+          {-1, 1, 2},
+          {-1, 2, 1},
+          { 1, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // split cannot be found
+        // -> 0.0
+        BuildTree(xy, allVariables, 3);
+      }
+      {
+        // almost diagonal split 
+        var xy = new double[,]
+        {
+          { 1, 1, 1},
+          {-1, 1, 2},
+          {-1, 2, 1},
+          { 1.0001, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+        // (two possible solutions)
+        // x2 <= 1.5 -> 0
+        // x2 >  1.5 -> 0 (not quite)
+        BuildTree(xy, allVariables, 3);
+
+        // x1 <= 1.5 AND x2 <= 1.5 -> 1 
+        // x1 <= 1.5 AND x2 >  1.5 -> -1 
+        // x1 >  1.5 AND x2 <= 1.5 -> -1
+        // x1 >  1.5 AND x2 >  1.5 -> 1 (not quite)
+        BuildTree(xy, allVariables, 7);
+      }
+      {
+        // unbalanced split
+        var xy = new double[,]
+        {
+          {-1, 1, 1},
+          {-1, 1, 2},
+          {0.9, 2, 1},
+          {1.1, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+        // x1 <= 1.5 -> -1.0 
+        // x1 >  1.5 AND x2 <= 1.5 -> 0.9
+        // x1 >  1.5 AND x2 >  1.5 -> 1.1
+        BuildTree(xy, allVariables, 10);
+      }
+
+      {
+        // unbalanced split
+        var xy = new double[,]
+        {
+          {-1, 1, 1},
+          {-1, 1, 2},
+          {-1, 2, 1},
+          { 3, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+        // (two possible solutions)
+        // x2 <= 1.5 -> -1.0 
+        // x2 >  1.5 AND x1 <= 1.5 -> -1.0
+        // x2 >  1.5 AND x1 >  1.5 ->  3.0
+        BuildTree(xy, allVariables, 10);
+      }
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "long")]
+    public void GradientBoostingTestTowerSquaredError() {
+      var gbt = new GradientBoostedTreesAlgorithm();
+      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));
+
+      #region Algorithm Configuration
+      gbt.Problem = regProblem;
+      gbt.Seed = 0;
+      gbt.SetSeedRandomly = false;
+      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);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "long")]
+    public void GradientBoostingTestTowerAbsoluteError() {
+      var gbt = new GradientBoostedTreesAlgorithm();
+      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));
+
+      #region Algorithm Configuration
+      gbt.Problem = regProblem;
+      gbt.Seed = 0;
+      gbt.SetSeedRandomly = false;
+      gbt.Iterations = 1000;
+      gbt.MaxSize = 20;
+      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);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "long")]
+    public void GradientBoostingTestTowerRelativeError() {
+      var gbt = new GradientBoostedTreesAlgorithm();
+      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));
+
+      #region Algorithm Configuration
+      gbt.Problem = regProblem;
+      gbt.Seed = 0;
+      gbt.SetSeedRandomly = false;
+      gbt.Iterations = 3000;
+      gbt.MaxSize = 20;
+      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);
+    }
+
+    // same as in SamplesUtil
+    private void RunAlgorithm(IAlgorithm a) {
+      var trigger = new EventWaitHandle(false, EventResetMode.ManualReset);
+      Exception ex = null;
+      a.Stopped += (src, e) => { trigger.Set(); };
+      a.ExceptionOccurred += (src, e) => { ex = e.Value; trigger.Set(); };
+      a.Prepare();
+      a.Start();
+      trigger.WaitOne();
+
+      Assert.AreEqual(ex, null);
+    }
+
+    #region helper
+    private void BuildTree(double[,] xy, string[] allVariables, int maxSize) {
+      int nRows = xy.GetLength(0);
+      var allowedInputs = allVariables.Skip(1);
+      var dataset = new Dataset(allVariables, xy);
+      var problemData = new RegressionProblemData(dataset, allowedInputs, allVariables.First());
+      problemData.TrainingPartition.Start = 0;
+      problemData.TrainingPartition.End = nRows;
+      problemData.TestPartition.Start = nRows;
+      problemData.TestPartition.End = nRows;
+      var solution = GradientBoostedTreesAlgorithmStatic.TrainGbm(problemData, new SquaredErrorLoss(), maxSize, nu: 1, r: 1, m: 1, maxIterations: 1, randSeed: 31415);
+      var model = (GradientBoostedTreesModel)solution.Model;
+      var treeM = model.Models.Skip(1).First() as RegressionTreeModel;
+
+      Console.WriteLine(treeM.ToString());
+      Console.WriteLine();
+    }
+    #endregion
+  }
+}
Index: /stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj
===================================================================
--- /stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj	(revision 12710)
+++ /stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj	(revision 12711)
@@ -442,4 +442,5 @@
     <Compile Include="HeuristicLab-3.3\ThreadSafeLogTest.cs" />
     <Compile Include="HeuristicLab-3.3\ToStringTest.cs" />
+    <Compile Include="HeuristicLab.Algorithms.DataAnalysis-3.4\GradientBoostingTest.cs" />
     <Compile Include="HeuristicLab.Algorithms.DataAnalysis-3.4\SupportVectorMachineTest.cs" />
     <Compile Include="HeuristicLab.Algorithms.DataAnalysis-3.4\GaussianProcessModelTest.cs" />
