Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs	(revision 12332)
@@ -0,0 +1,232 @@
+﻿#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.ComponentModel;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using System.Threading;
+using GradientBoostedTrees;
+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;
+using HeuristicLab.Random;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  [Item("Gradient Boosted Trees", "")]
+  [StorableClass]
+  [Creatable("Algorithms")]
+  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 MaxDepthParameterName = "Maximum Tree Depth";
+    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";
+    #endregion
+
+    #region ParameterProperties
+    public IFixedValueParameter<IntValue> IterationsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> MaxDepthParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxDepthParameterName]; }
+    }
+    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]; }
+    }
+    #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 MaxDepth {
+      get { return MaxDepthParameter.Value.Value; }
+      set { MaxDepthParameter.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; }
+    }
+    #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>(MaxDepthParameterName, "Maximal depth of the tree learned in each step (prefer smaller depths if possible)", new IntValue(5)));
+      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>("UpdateInterval", "", new IntValue(100)));
+      Parameters["UpdateInterval"].Hidden = true;
+
+      var lossFunctionNames = ApplicationManager.Manager.GetInstances<ILossFunction>().Select(l => new StringValue(l.ToString()).AsReadOnly());
+      var defaultLossFunction = lossFunctionNames.First(l => l.Value.Contains("Squared")); // squared error loss is the default
+      Parameters.Add(new ConstrainedValueParameter<StringValue>(LossFunctionParameterName, "The loss function", new ItemSet<StringValue>(lossFunctionNames), defaultLossFunction));
+    }
+
+
+    protected override void Run(CancellationToken cancellationToken) {
+      // Set up the algorithm
+      if (SetSeedRandomly) Seed = new System.Random().Next();
+      // random.Reset(Seed);
+
+      // 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("Current loss", curLoss));
+
+      // init
+      var problemData = Problem.ProblemData;
+      var lossFunction = ApplicationManager.Manager.GetInstances<ILossFunction>().Single(l => l.ToString() == LossFunctionParameter.Value.Value);
+      var state = GradientBoostedTreesAlgorithmStatic.CreateGbmState(problemData, lossFunction, (uint)Seed, MaxDepth, 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
+      // update variable impacts matrix
+      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));
+
+      // produce solution 
+      Results.Add(new Result("Solution", new RegressionSolution(state.GetModel(), (IRegressionProblemData)problemData.Clone())));
+    }
+  }
+}
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithmStatic.cs	(revision 12332)
@@ -0,0 +1,198 @@
+﻿#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 GradientBoostedTrees;
+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
+    private class GbmState : IGbmState {
+      internal IRegressionProblemData problemData { get; set; }
+      internal MersenneTwister random { get; set; }
+      internal ILossFunction lossFunction { get; set; }
+      internal int maxDepth { get; set; }
+      internal double nu { get; set; }
+      internal double r { get; set; }
+      internal double m { get; set; }
+      internal RegressionTreeBuilder treeBuilder;
+
+
+      // array members (allocate only once)
+      internal double[] pred;
+      internal double[] predTest;
+      internal double[] w;
+      internal double[] y;
+      internal int[] activeIdx;
+      internal double[] rim;
+
+      internal IList<IRegressionModel> models;
+      internal IList<double> weights;
+
+      public GbmState(IRegressionProblemData problemData, ILossFunction lossFunction, uint randSeed, int maxDepth, double r, double m, double nu) {
+        // default settings for MaxDepth, Nu and R
+        this.maxDepth = maxDepth;
+        this.nu = nu;
+        this.r = r;
+        this.m = m;
+
+        random = new MersenneTwister(randSeed);
+        this.problemData = problemData;
+        this.lossFunction = lossFunction;
+
+        int nRows = problemData.TrainingIndices.Count();
+
+        y = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
+        // weights are all 1 for now (HL doesn't support weights yet)
+        w = Enumerable.Repeat(1.0, nRows).ToArray();
+
+        treeBuilder = new RegressionTreeBuilder(problemData, random);
+
+        activeIdx = problemData.TrainingIndices.ToArray();
+
+        // prepare arrays (allocate only once)
+        double f0 = y.Average(); // default prediction (constant)
+        pred = Enumerable.Repeat(f0, nRows).ToArray();
+        predTest = Enumerable.Repeat(f0, problemData.TestIndices.Count()).ToArray();
+        rim = 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, w) / nRows;
+      }
+      public double GetTestLoss() {
+        var yTest = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TestIndices);
+        var wTest = yTest.Select(_ => 1.0); // ones
+        var nRows = yTest.Count();
+        return lossFunction.GetLoss(yTest, predTest, wTest) / nRows;
+      }
+    }
+
+    // simple interface
+    public static IRegressionSolution TrainGbm(IRegressionProblemData problemData, int maxDepth, double nu, double r, int maxIterations) {
+      return TrainGbm(problemData, new SquaredErrorLoss(), maxDepth, nu, r, maxIterations);
+    }
+
+    // simple interface
+    public static IRegressionSolution TrainGbm(IRegressionProblemData problemData, ILossFunction lossFunction,
+      int maxDepth, double nu, double r, 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);
+      state.maxDepth = maxDepth;
+      state.r = r;
+      state.nu = nu;
+
+      for (int iter = 0; iter < maxIterations; iter++) {
+        MakeStep(state);
+      }
+
+      var model = new GradientBoostedTreesModel(state.models, state.weights);
+      return new RegressionSolution(model, (IRegressionProblemData)problemData.Clone());
+    }
+
+    // for custom stepping & termination
+    public static IGbmState CreateGbmState(IRegressionProblemData problemData, ILossFunction lossFunction, uint randSeed, int maxDepth = 3, double r = 0.66, double m = 0.5, double nu = 0.01) {
+      return new GbmState(problemData, lossFunction, randSeed, maxDepth, r, m, nu);
+    }
+
+    // use default settings for maxDepth, 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.maxDepth, gbmState.nu, gbmState.r, gbmState.m);
+    }
+
+    // allow dynamic adaptation of maxDepth, nu and r
+    public static void MakeStep(IGbmState state, int maxDepth, 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 w = gbmState.w;
+      var treeBuilder = gbmState.treeBuilder;
+      var y = gbmState.y;
+      var activeIdx = gbmState.activeIdx;
+      var rim = gbmState.rim;
+
+      // copy output of gradient function to pre-allocated rim array (pseudo-residuals)
+      int rimIdx = 0;
+      foreach (var g in lossFunction.GetLossGradient(y, yPred, w)) {
+        rim[rimIdx++] = g;
+      }
+
+      var tree = treeBuilder.CreateRegressionTreeForGradientBoosting(rim, maxDepth, activeIdx, lossFunction.GetLineSearchFunc(y, yPred, w), r, m);
+
+      int i = 0;
+      foreach (var pred in tree.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices)) {
+        yPred[i] = yPred[i] + nu * pred;
+        i++;
+      }
+      // update predictions for validation set
+      i = 0;
+      foreach (var pred in tree.GetEstimatedValues(problemData.Dataset, problemData.TestIndices)) {
+        yPredTest[i] = yPredTest[i] + nu * pred;
+        i++;
+      }
+
+      gbmState.weights.Add(nu);
+      gbmState.models.Add(tree);
+    }
+    #endregion
+  }
+}
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesModel.cs	(revision 12332)
@@ -0,0 +1,54 @@
+﻿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 GradientBoostedTrees {
+  [Item("GradientBoostedTreesSolution", "")]
+  [StorableClass]
+  public sealed class GradientBoostedTreesModel : NamedItem, IRegressionModel {
+
+    [Storable]
+    private readonly IList<IRegressionModel> models;
+    [Storable]
+    private readonly IList<double> 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() {
+      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(Dataset dataset, IEnumerable<int> rows) {
+      var tuples = (from idx in Enumerable.Range(0, models.Count)
+                    let model = models[idx]
+                    let weight = weights[idx]
+                    select new { weight, enumerator = model.GetEstimatedValues(dataset, rows).GetEnumerator() }).ToArray();
+
+
+      while (tuples.All(t => t.enumerator.MoveNext())) {
+        yield return tuples.Sum(t => t.weight * t.enumerator.Current);
+      }
+    }
+
+    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+      return new RegressionSolution(this, (IRegressionProblemData)problemData.Clone());
+    }
+  }
+}
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/ILossFunction.cs	(revision 12332)
@@ -0,0 +1,16 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Core;
+
+namespace GradientBoostedTrees {
+  public delegate double LineSearchFunc(int[] idx, int startIdx, int endIdx);
+
+  public interface ILossFunction {
+    double GetLoss(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight);
+    IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight);
+    LineSearchFunc GetLineSearchFunc(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight);
+  }
+}
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/LossFunctions/SquaredErrorLoss.cs	(revision 12332)
@@ -0,0 +1,65 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+
+namespace GradientBoostedTrees {
+  public class SquaredErrorLoss : ILossFunction {
+    public double GetLoss(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+      var weightEnum = weight.GetEnumerator();
+
+      double s = 0;
+      while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
+        double res = targetEnum.Current - predEnum.Current;
+        s += weightEnum.Current * res * res;
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
+        throw new ArgumentException("target, pred and weight have differing lengths");
+
+      return s;
+    }
+
+    public IEnumerable<double> GetLossGradient(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight) {
+      var targetEnum = target.GetEnumerator();
+      var predEnum = pred.GetEnumerator();
+      var weightEnum = weight.GetEnumerator();
+
+      while (targetEnum.MoveNext() & predEnum.MoveNext() & weightEnum.MoveNext()) {
+        yield return weightEnum.Current * 2.0 * (targetEnum.Current - predEnum.Current);
+      }
+      if (targetEnum.MoveNext() | predEnum.MoveNext() | weightEnum.MoveNext())
+        throw new ArgumentException("target, pred and weight have differing lengths");
+    }
+
+    public LineSearchFunc GetLineSearchFunc(IEnumerable<double> target, IEnumerable<double> pred, IEnumerable<double> weight) {
+      var targetArr = target.ToArray();
+      var predArr = pred.ToArray();
+      var weightArr = weight.ToArray();
+      if (targetArr.Length != predArr.Length || predArr.Length != weightArr.Length)
+        throw new ArgumentException("target, pred and weight have differing lengths");
+
+      // line search for 
+      LineSearchFunc lineSearch = (idx, startIdx, endIdx) => {
+        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;
+      };
+      return lineSearch;
+
+    }
+
+    public override string ToString() {
+      return "Squared error loss";
+    }
+  }
+}
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs	(revision 12332)
@@ -0,0 +1,358 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Problems.DataAnalysis;
+
+namespace GradientBoostedTrees {
+  public 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)
+    private double[] y; // training labels (original order from problemData)
+
+    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 readonly IList<RegressionTreeModel.TreeNode> nodeQueue;
+
+    // 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];
+      nodeQueue = new List<RegressionTreeModel.TreeNode>();
+
+      x = new double[nCols][];
+      y = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
+
+
+      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++;
+      }
+    }
+
+    // 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 maxDepth, 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 zeros = Enumerable.Repeat(0.0, y.Length);
+      var ones = Enumerable.Repeat(1.0, y.Length);
+
+      var model = CreateRegressionTreeForGradientBoosting(y, maxDepth, problemData.TrainingIndices.ToArray(), seLoss.GetLineSearchFunc(y, zeros, ones), 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 this functionality is called by the gradient boosting routine
+    public IRegressionModel CreateRegressionTreeForGradientBoosting(double[] y, int maxDepth, int[] idx, LineSearchFunc lineSearch, double r = 0.5, double m = 0.5) {
+      Contract.Assert(maxDepth > 0);
+      Contract.Assert(r > 0);
+      Contract.Assert(r <= 1.0);
+      Contract.Assert(y.Count() == this.y.Length);
+      Contract.Assert(m > 0);
+      Contract.Assert(m <= 1.0);
+
+      this.y = y; // y is changed in gradient boosting
+
+      // shuffle row idx
+      HeuristicLab.Random.ListExtensions.ShuffleInPlace(idx, random);
+
+      int nRows = idx.Count();
+
+      // shuffle variable idx
+      HeuristicLab.Random.ListExtensions.ShuffleInPlace(allowedVariables, random);
+
+      effectiveRows = (int)Math.Ceiling(nRows * r);
+      effectiveVars = (int)Math.Ceiling(nCols * m);
+
+      Array.Clear(which, 0, which.Length);
+
+      // mark selected rows
+      for (int row = 0; row < effectiveRows; row++) {
+        which[idx[row]] = 1;
+        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) {
+            Trace.Assert(i < effectiveRows);
+            sortedIdx[col][i] = sortedIdxAll[col][row];
+            i++;
+          }
+        }
+      }
+      // start and end idx are inclusive
+      var tree = CreateRegressionTreeForIdx(maxDepth, 0, effectiveRows - 1, lineSearch);
+      return new RegressionTreeModel(tree);
+    }
+
+    // startIdx and endIdx are inclusive
+    private RegressionTreeModel.TreeNode CreateRegressionTreeForIdx(int maxDepth, int startIdx, int endIdx, LineSearchFunc lineSearch) {
+      Contract.Assert(endIdx - startIdx >= 0);
+      Contract.Assert(startIdx >= 0);
+      Contract.Assert(endIdx < internalIdx.Length);
+
+      RegressionTreeModel.TreeNode t;
+      // TODO: stop when y is constant
+      // TODO: use priority queue of nodes to be expanded (sorted by improvement) instead of the recursion to maximum depth
+      if (maxDepth <= 1 || endIdx - startIdx == 0) {
+        // max depth reached or only one element         
+        t = new RegressionTreeModel.TreeNode(RegressionTreeModel.TreeNode.NO_VARIABLE, lineSearch(internalIdx, startIdx, endIdx));
+        return t;
+      } else {
+        int i, j;
+        double threshold;
+        string bestVariableName;
+        FindBestVariableAndThreshold(startIdx, endIdx, out threshold, out bestVariableName);
+
+        // if bestVariableName is NO_VARIABLE then no split was possible anymore
+        if (bestVariableName == RegressionTreeModel.TreeNode.NO_VARIABLE) {
+          return new RegressionTreeModel.TreeNode(RegressionTreeModel.TreeNode.NO_VARIABLE, lineSearch(internalIdx, startIdx, endIdx));
+        } else {
+
+
+          int bestVarIdx = varName2Index[bestVariableName];
+          // split - two pass
+
+          // store which index goes where
+          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
+          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 {
+              Trace.Assert(which[internalIdx[i]] > 0);
+              Trace.Assert(which[internalIdx[j]] < 0);
+              // swap
+              int tmp = internalIdx[i];
+              internalIdx[i] = internalIdx[j];
+              internalIdx[j] = tmp;
+              i++;
+              j--;
+            }
+          }
+          Debug.Assert(j < i);
+          Debug.Assert(i >= startIdx);
+          Debug.Assert(j <= endIdx);
+
+          t = new RegressionTreeModel.TreeNode(bestVariableName,
+            threshold,
+            CreateRegressionTreeForIdx(maxDepth - 1, startIdx, j, lineSearch),
+            CreateRegressionTreeForIdx(maxDepth - 1, i, endIdx, lineSearch));
+
+          return t;
+        }
+      }
+    }
+
+    private void FindBestVariableAndThreshold(int startIdx, int endIdx, out double threshold, out string bestVar) {
+      Contract.Assert(startIdx < endIdx + 1); // at least 2 elements
+
+      int rows = endIdx - startIdx + 1;
+      Contract.Assert(rows >= 2);
+
+      double sumY = 0.0;
+      for (int i = startIdx; i <= endIdx; i++) {
+        sumY += y[internalIdx[i]];
+      }
+
+      double bestImprovement = 0.0;
+      double bestThreshold = double.PositiveInfinity;
+      bestVar = string.Empty;
+
+      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];
+        }
+      }
+
+      UpdateVariableRelevance(bestVar, sumY, bestImprovement, rows);
+
+      threshold = bestThreshold;
+
+      // Contract.Assert(bestImprovement > 0);
+      // Contract.Assert(bestImprovement < double.PositiveInfinity);
+      // Contract.Assert(bestVar != string.Empty);
+      // Contract.Assert(allowedVariables.Contains(bestVar));
+    }
+
+    // assumption is that the Average(y) = 0
+    private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
+      // update variable relevance
+      double err = sumY * sumY / rows;
+      double errAfterSplit = bestImprovement;
+
+      double delta = (errAfterSplit - err); // relative reduction in squared error
+      double v;
+      if (!sumImprovements.TryGetValue(bestVar, out v)) {
+        sumImprovements[bestVar] = delta;
+      }
+      sumImprovements[bestVar] = v + delta;
+    }
+
+    // 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) {
+      Contract.Assert(rows >= 2);
+
+      double sl = 0.0;
+      double sr = sumY;
+      double nl = 0.0;
+      double nr = rows;
+
+      bestImprovement = 0.0;
+      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
+          double curQuality = sl * sl / nl + sr * sr / nr;
+          // curQuality = nl*nr / (nl+nr) * Sqr(sl / nl - sr / nr) // greedy function approximation page 12 eqn (35)
+
+          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
+    }
+
+
+    public IEnumerable<KeyValuePair<string, double>> GetVariableRelevance() {
+      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);
+    }
+  }
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs	(revision 12332)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs	(revision 12332)
@@ -0,0 +1,75 @@
+﻿using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.DataAnalysis;
+
+namespace GradientBoostedTrees {
+  [StorableClass]
+  [Item("RegressionTreeModel", "Represents a decision tree for regression.")]
+  // TODO: Implement a view for this
+  public class RegressionTreeModel : NamedItem, IRegressionModel {
+
+    [StorableClass]
+    public class TreeNode {
+      public readonly static string NO_VARIABLE = string.Empty;
+      [Storable]
+      public readonly string varName; // name of the variable for splitting or -1 if terminal node
+      [Storable]
+      public readonly double val; // threshold
+      [Storable]
+      public readonly TreeNode left;
+      [Storable]
+      public readonly TreeNode right;
+
+      public TreeNode(string varName, double value, TreeNode left = null, TreeNode right = null) {
+        this.varName = varName;
+        this.val = value;
+        this.left = left;
+        this.right = right;
+      }
+    }
+
+    [Storable]
+    public readonly TreeNode tree;
+
+    [StorableConstructor]
+    private RegressionTreeModel(bool serializing) : base(serializing) { }
+    // cloning ctor
+    public RegressionTreeModel(RegressionTreeModel original, Cloner cloner)
+      : base(original, cloner) {
+      this.tree = original.tree;
+    }
+
+    public RegressionTreeModel(TreeNode tree)
+      : base() {
+      this.name = ItemName;
+      this.description = ItemDescription;
+
+      this.tree = tree;
+    }
+
+    private static double GetPredictionForRow(TreeNode t, Dataset ds, int row) {
+      if (t.varName == TreeNode.NO_VARIABLE)
+        return t.val;
+      else if (ds.GetDoubleValue(t.varName, row) <= t.val)
+        return GetPredictionForRow(t.left, ds, row);
+      else
+        return GetPredictionForRow(t.right, ds, row);
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new RegressionTreeModel(this, cloner);
+    }
+
+    public IEnumerable<double> GetEstimatedValues(Dataset ds, IEnumerable<int> rows) {
+      return rows.Select(r => GetPredictionForRow(tree, ds, r));
+    }
+
+    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
+      return new RegressionSolution(this, new RegressionProblemData(problemData));
+    }
+  }
+
+}
Index: /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj
===================================================================
--- /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 12331)
+++ /branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 12332)
@@ -195,4 +195,11 @@
     <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\ILossFunction.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: /branches/GBT/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Regression/RegressionSolution.cs
===================================================================
--- /branches/GBT/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Regression/RegressionSolution.cs	(revision 12331)
+++ /branches/GBT/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Regression/RegressionSolution.cs	(revision 12332)
@@ -30,5 +30,5 @@
   /// </summary>
   [StorableClass]
-  public abstract class RegressionSolution : RegressionSolutionBase {
+  public class RegressionSolution : RegressionSolutionBase {
     protected readonly Dictionary<int, double> evaluationCache;
 
@@ -42,5 +42,5 @@
       evaluationCache = new Dictionary<int, double>(original.evaluationCache);
     }
-    protected RegressionSolution(IRegressionModel model, IRegressionProblemData problemData)
+    public RegressionSolution(IRegressionModel model, IRegressionProblemData problemData)
       : base(model, problemData) {
       evaluationCache = new Dictionary<int, double>(problemData.Dataset.Rows);
