Decision trees: leaf-wise (best-first) and level-wise tree traverse

Question

Issue 1:

I am confused by the description of LightGBM regarding the way the tree is expanded.

They state:

Most decision tree learning algorithms grow tree by level (depth)-wise, like the following image:

Questions 1: Which "most" algorithms are implemented this way? As far as I know C4.5 and CART use DFS. XGBoost uses BFS. Which other algorithms or packages use BFS for decision trees?

Issue 2:

LightGBM states:

LightGBM grows tree by leaf-wise (best-first).It will choose the leaf with max delta loss to grow. When growing same leaf, leaf-wise algorithm can reduce more loss than level-wise algorithm.

Question 2: Is it correct to say that level-wise growth trees will have equal depth for all leaves?

Questions 3: If Question 2 is not correct, then the trees from level-wise and leaf-wise growth will look the same at the end of the traversal (without pruning etc). Is it a correct statement?

Questions 4: If question 3 is correct, how can "leaf-wise algorithm can reduce more loss than level-wise algorithm"? Does it have to do with the post-pruning algorithm?

Answer 1

If you grow the full tree, best-first (leaf-wise) and depth-first (level-wise) will result in the same tree. The difference is in the order in which the tree is expanded. Since we don't normally grow trees to their full depth, order matters: application of early stopping criteria and pruning methods can result in very different trees. Because leaf-wise chooses splits based on their contribution to the global loss and not just the loss along a particular branch, it often (not always) will learn lower-error trees "faster" than level-wise. I.e. for a given number of leaves, leaf-wise will probably out-perform level-wise. As you add more nodes, without stopping or pruning they will converge to the same performance because they will literally build the same tree eventually.

Reference:

Shi, H. (2007). Best-first Decision Tree Learning (Thesis, Master of Science (MSc)). The University of Waikato, Hamilton, New Zealand. Retrieved from https://hdl.handle.net/10289/2317

---

EDIT: Regarding your first question, both C4.5 and CART are depth-first examples, not best-first. Here's some relevant content from the reference above:

1.2.1 Standard decision trees

Standard algorithms such as C4.5 (Quinlan, 1993) and CART (Breiman et al., 1984) for the top-down induction of decision trees expand nodes in depth-first order in each step using the divide-and-conquer strategy. Normally, at each node of a decision tree, testing only involves a single attribute and the attribute value is compared to a constant. The basic idea of standard decision trees is that, first, select an attribute to place at the root node and make some branches for this attribute based on some criteria (e.g. information or Gini index). Then, split training instances into subsets, one for each branch extending from the root node. The number of subsets is the same as the number of branches. Then, this step is repeated for a chosen branch, using only those instances that actually reach it. A fixed order is used to expand nodes (normally, left to right). If at any time all instances at a node have the same class label, which is known as a pure node, splitting stops and the node is made into a terminal node. This construction process continues until all nodes are pure. It is then followed by a pruning process to reduce overfittings (see Section 1.3).

1.2.2 Best-first decision trees

Another possibility, which so far appears to only have been evaluated in the context of boosting algorithms (Friedman et al., 2000), is to expand nodes in best-first order instead of a fixed order. This method adds the ”best” split node to the tree in each step. The ”best” node is the node that maximally reduces impurity among all nodes available for splitting (i.e. not labelled as terminal nodes). Although this results in the same fully-grown tree as standard depth-first expansion, it enables us to investigate new tree pruning methods that use cross-validation to select the number of expansions. Both pre-pruning and post-pruning can be performed in this way, which enables a fair comparison between them (see Section 1.3).

Best-first decision trees are constructed in a divide-and-conquer fashion similar to standard depth-first decision trees. The basic idea of how a best-first tree is built is as follows. First, select an attribute to place at the root node and make some branches for this attribute based on some criteria. Then, split training instances into subsets, one for each branch extending from the root node. In this thesis only binary decision trees are considered and thus the number of branches is exactly two. Then, this step is repeated for a chosen branch, using only those instances that actually reach it. In each step we choose the ”best” subset among all subsets that are available for expansions. This constructing process continues until all nodes are pure or a specific number of expansions is reached. Figure 1.1 shows the difference in split order between a hypothetical binary best-first tree and a hypothetical binary depth-first tree. Note that other orderings may be chosen for the best-first tree while the order is always the same in the depth-first case.