# What is the loss/cost function of decision trees?

In Decision Tree, splitting criterion methods are applied say information gain to split the current tree node to built a decision tree, but in many machine learning problems, normally there is a cost/loss function to be minimised to get the best parameters.

My question is how to define such a cost function of Decision Tree?

• For some outcome $y$, decision trees will give you predictions $\hat{y}$. You may then choose the tree that has the minimum squared error, which means you're working with the typical loss function $L=(y-\hat{y})^2$. – suckrates Feb 27 '18 at 14:06

I think it helps to distinguish between training metrics and evaluation metrics, and between global training metrics and local training metrics. When we talk about evaluation metrics, as @AlvaroFuentes said, a loss function can always be defined for decision trees, in the same way as for any other model. In training, it is true that often a global metric is chosen and training attempts to optimize over that metric *. But training does not have to be this way, and in the case of decision trees, training proceeds through a greedy search, each step based on a local metric (eg, information gain or Gini index). In fact, even when a global training metric is defined (say, likelihood), each step in training is still is evaluated based on some local metric (say, gradient of likelihood) and hence in a sense "greedy"; it is just that in this case the local metric is inspired by the global one. And in both cases there is no guarantee that a greedy search based on some local metric actually optimizes the global metric (eg, local optima).

* Side note: This training metric is often different from the evaluation metrics, chosen for its nicer mathematical properties to help the training; eg, likelihood, L2 or cross entropy vs accuracy or AUC.

• I look forward to hearing other people's thoughts on this. – Lei Huang Mar 27 '19 at 22:03

Chapter 8 of Introduction to Statistical Learning by Gareth James et al. talks about how Decision Tree follows a greedy top-down approach also known as recursive binary splitting to stratify the predictor space. What this algorithm tries to do is, starting at the top (a single region containing all observations) it tries to analyze all predictors and all cutpoint values for each predictor to choose the optimal set of predictors and cutpoint values that will have the least sum of squared error.

The sum of squared error here is the sum of squares of the difference between each observation in the split region and the mean response value of that region. This is the loss function that is being optimized.

• Thanks for answering this old question. – GoingMyWay Mar 5 at 6:11

Its just simply the count of leaves. Trees exchange their series for parallel, at an equalization of the leaf count. You can figure out the exact relationship yourself.