# DART algorithm implementation. Converting mathematical notation to pseudocode

I am learning how DART algorithm (https://arxiv.org/abs/1505.01866) works and I want to implement it in C#

I have the algorithm's description in mathematical notation and I don't understand most of it. I want to convert it to pseudocode, preferably C style. Many thanks.

Image from the article:

• That image is exactly what I would call pseudocode. I suppose what you mean is to turn it into something "less pseudo"? Apr 16 at 21:52

Well, I am not familiar with the DART algorithm, but I thought it might be a good task for ChatGPT, so I took the Latex source of the article you linked, and asked it to generate C# code for it:

using System;
using System.Collections.Generic;
using System.Linq;

public class Node
{
public double X;  // Input feature value
public double Y;  // Output label value
}

public class Tree
{
public List<Node> Nodes;  // List of nodes in the tree
}

public class DARTAlgorithm
{
public const double Pdrop = 0.2;  // Probability of dropping a tree

// Trains an ensemble of decision trees on the given dataset
public List<Tree> Train(List<Node> dataset, int nTrees)
{
// Initialize the first tree with a single node at (0, 0)
var S1 = new List<Node> { new Node { X = 0, Y = 0 } };
var T1 = new Tree { Nodes = TrainTree(S1, dataset) };
var M = new List<Tree> { T1 };  // Ensemble of trees

for (int t = 2; t <= nTrees; t++)
{
// Randomly drop a subset of trees from the ensemble
var D = M.Where(t => new Random().NextDouble() < Pdrop).ToList();
var M_hat = M.Except(D).ToList();

// Construct a new dataset S_t for training the next tree
var S_t = new List<Node>();
foreach (var x in dataset)
{
// Compute the negative gradient of the loss function
// with respect to the output label for this input
var y_hat = Predict(M_hat, x);  // Predict the output for the input x
S_t.Add(new Node { X = x.X, Y = y_hat - x.Y });
}

// Train the next tree on the new dataset S_t
var T_t = new Tree { Nodes = TrainTree(S_t, dataset) };

// Scale the trees in D and replace them in M
foreach (var tree in D)
{
M[M.IndexOf(tree)] = ScaleTree(tree, D.Count + 1);
}
}

return M;
}

// Trains a decision tree on the given dataset
private List<Node> TrainTree(List<Node> dataset, List<Node> fullDataset)
{
// TODO: Implement decision tree training algorithm
throw new NotImplementedException();
}

// Predicts the output label for the given input using the given ensemble of trees
private double Predict(List<Tree> ensemble, Node x)
{
// TODO: Implement tree ensemble prediction algorithm
throw new NotImplementedException();
}

// Scales the given tree by the given scale factor
private Tree ScaleTree(Tree tree, int scaleFactor)
{
// TODO: Implement tree scaling algorithm
throw new NotImplementedException();
}
}


I don't know if it works, but it compiles.

I hesitated to publish this answer (both because I don't know if it is correct and because I myself think that people posting AI-generated answers is detrimental to the overall quality of SE sites). However, I think this is the kind of task where ChatGPT can be very useful and I wanted to illustrate this use and encourage readers to use AI tools to help themselves understand.

I will be happy to remove the answer if people think it is not appropriate here.

• This would be more illustrative if you could say whether it worked as intended, and if not then where it went wrong. Apr 16 at 21:54
• I don't know much C#, but: >Node looks like a data row, but also gets used to store tree nodes? >S1 is incorrect. >trainTree presumably doesn't need a "local" and a full dataset. >S_t has somehow interpreted the derivative of a generic loss in the specific case of squared error, and forgets to switch sign. >T_t doesn't get scaled. >scaleFactor can't be an int. Apr 17 at 2:54