1
$\begingroup$

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.

I am refering to this article: https://arxiv.org/pdf/1505.01866.pdf

Image from the article:

DART mathematical notation

$\endgroup$
1
  • $\begingroup$ That image is exactly what I would call pseudocode. I suppose what you mean is to turn it into something "less pseudo"? $\endgroup$
    – Ben Reiniger
    Apr 16 at 21:52

1 Answer 1

1
$\begingroup$

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();
            if (!D.Any()) D.Add(M[new Random().Next(M.Count)]);
            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) };
            M.Add(T_t);  // Add the new tree to the ensemble
            
            // 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.

$\endgroup$
2
  • $\begingroup$ This would be more illustrative if you could say whether it worked as intended, and if not then where it went wrong. $\endgroup$
    – Ben Reiniger
    Apr 16 at 21:54
  • $\begingroup$ 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. $\endgroup$
    – Ben Reiniger
    Apr 17 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.