Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an algorithm to build decision graphs. The idea of this algorithm is to recursively replace internal nodes as well as leaf nodes in a decision tree by a small decision tree. In the case of internal nodes, this decision tree is grown to optimally direct the examples falling into that node to the left or right successor of the replaced node. In the case of leaf nodes, the small tree is grown to predict the target. Experiments compare the approach with standard CART tree and ensembles.

main_review: The idea of building decision graphs is not new but it is interesting. The way the authors motivate them in the paper is however not very convincing. They draw a parallel between TnT and oblique trees, which suggest that TnT are more expressive that standard trees and that's the reason they are expected to be more accurate. This is actually not the case, since any decision graph can indeed be represented by a (more complex) decision tree. In my opinion, the main interest of graphs instead of trees is the reduced size of the model and the potential reduction of variance (because using a graph allows to avoid the sample size reduction effect inherent to tree partitioning).

The proposed algorithm to grow graphs is original to the best of my knowledge. The related work section is however incomplete. There are a number of other decision graph training algorithms, such as the following two (and several other references therein):
* Zighed D.A. (2007) Induction Graphs for Data Mining. In: Brito P., Cucumel G., Bertrand P., de Carvalho F. (eds) Selected Contributions in Data Analysis and Classification. Studies in Classification, Data Analysis, and Knowledge Organization. Springer, Berlin, Heidelberg.
* Jamie Shotton, Sebastian Nowozin, Toby Sharp, John Winn, Pushmeet Kohli, and Antonio Criminisi. 2013. Decision jungles: compact and rich models for classification. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1 (NIPS'13).

I think the proposed method should be discussed and compared more thoroughly with this literature.

In the end, I think I managed to understand the main idea of the algorithm but the description could have been clearer. What confused me the most was how internal splits are expanded into micro-trees, i.e., the way labels are constructed to train these micro-trees (as explained in 3.1). Part of the confusion comes from the fact that some notations are not clearly explained (e.g., in (5) what is $G_{n_i\rightarrow left}$  and why does it take as its first argument a subset $X$, and not a single $x$ as $G$).

In Section 3.3, a discussion and motivation for the introduction of the parameters $N_1$ and $N_2$ in Algorithm 2 is missing and this added to my confusion (there is more discussion of these parameters in the supplementary material however). Why wait for $N_2$ steps of node expansion before merging? Actually, why not merging after each micro tree construction inside the "for each node ($n_i$)" loop? In line 17, there is a reference to $t_i$ while we are outside the loop over $n_i$. What does it mean to merge $t_i$ there? Is the indentation correct?

Also, if I understand correctly, the order in which the nodes are considered in the loop in Line 5 matters (since changing an internal node into a replacement micro-tree will change the prediction for the samples falling into that node and thus will have an impact on its ancestors). If this is correct, it's not clear from the paper which order is used in practice.

Overall, the algorithm to construct these graphs makes sense and I like the idea of trees in trees. One drawback of the approach however is the introduction of the three hyper-parameters $N_1$, $N_2$, and $C$, whose interplay is not very clear. The authors seem also to put more emphasis on setting $C$ than on setting $N_1$ and $N_2$, which are mainly fixed to arbitrary default values. I have the feeling that it would be possible to have a single hyper-parameter. For example, why setting $N_2$ to 1 is not enough?

The experiments show that there is a benefit in using graphs in terms of accuracy. Methods are compared however at fixed number of splits and I don't think it's appropriate (or at least enough). First, there is no mechanism in TnT to set precisely the number of nodes and thus, this is not a very natural comparison (in practice, this is not how the method will be used). Second, one of the main benefits of CART is that it's a non-parametric method that can adapt model complexity to the problem at hand (using pruning). I would thus compare both methods at their optimum complexity (determined by CV), in terms of accuracy, number of splits and inference time.

The same comment applies for the comparison within ensembles. The number of ensemble terms and the number of nodes is arbitrarily set to small numbers in the experiment, while in practice, RF are used with unpruned trees and ensembles of hundreds of trees are averaged. Showing that TnT ensembles are better than suboptimal forests is not a very convincing result in my opinion. 

Minor remarks:
* Equation (4) is said to be an optimisation problem, which closed-form solution is (5). I don't understand notations in (5). What is optimized? Why is the sum over all examples? What is the value of $G_{n_i\rightarrow left/right}(x)$ for samples that do not reach $n_i$? 
* The synthetic examples show indeed the potential benefit of using a DAG instead of a tree, if one wants to reduce the number of splits. It's not clear however whether the proposed algorithm is able to produce the graph in 2(c) for such problem given the heuristic nature of the algorithm. If not, then I think presenting this example after having presented the algorithm is a bit misleading.
* In Figure 4, are CART trees fully grown when the maximum number of splits is reached or would it be possible to grow them further? I was expecting the accur I'm not sure that the maximum number of splits.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Inspired from Network in Network the paper proposes an extension of decision trees that replaces internal and leaf nodes with micro decision trees, thus extending decision trees to decision graphs.

main_review: In particular the authors propose a learning algorithm for decision graphs adopting a simple and effective iterative algorithm.

It should be interesting to explain why a decision graph has an accuracy greater than that of decision tree. Since there are shared decision paths, it seems that the decision power of a graph is lower than that of a tree. Probably it is due to deeper models involving more splits on the path to the leaf. A discussion should be interesting.

The learning approach presented in section 3 is clear and well presented.

Finally, the experimental evaluation proves that the TnT decision graph outperforms the axis-aligned decision trees on a number of benchmark datasets.
limitations_and_societal_impact: The main limitation regards the time complexity of the proposed approach.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an algorithm to build decision acyclic graphs with properties similar to those of decision trees: each node has a split condition to route instances and terminal nodes of the graph (i.e. those without children) provide the classification labels.  This model is trained by creating embedded decision trees inside decision the graph nodes iteratively. The algorithm starts with a single leave node in which, a small decision tree is build to route the examples to left/right. Then the decision tree internal decision tree of the node is flattened to create a graph. The acyclic graph structure appears since all left/right decisions of the embedded tree are routed to the same left/right graph node. Then, for each node the same process is applied iteratively.

The method is used as the base classifier of bagging and Adaboost ensembles and compared on 8 datasets against standard decision trees with RF and Adaboost using the same over all complexity (complexity measured as number of splits).
main_review: The paper is well written and quite clear, although some aspects could be further clarified (see below).

I have some issues/doubts bout the paper:
* The description of algorithm 1 is partial and a bit unclear. For instance, N1 and N2 are not described when the algorithm is introduced. I believe that N1 is the number of times the DT in the nodes of the graph are flattened. N2 remain unclear, why does the algorithm goes N2 times over all nodes of the graph to build a DT at each node? Also in line 2, t subscript appears but it is not defined before, Should be 0 instead of t? In addition, infer function is only explained with a comment in the algorithm. I suppose it is related to eq (6). 
* One unclear aspect to me is how he complexity of the models are gauged for the experiments. I understand that there is a C hyper-param that could be used to limit the complexity of the mini decision trees but it is unclear to me how to limit the over all complexity of the decision graph. For intance, are the curves in Fig3(c,d) obtained modifying C or do they use a fixed C? If so, which one? if not, how the C is modified? Idem for Fig4. Also in Fig4, how are the complexity of CART controlled? Using C? max_depth? other? A curious aspect is that for most plots, there is o over-fitting with the increment of the complexity of trees and graphs.
* The article says "With 1000 splits, the average decision depth of the best-first CART is 12.3,whereas the TnT decision graph has a mean depth of 27.3." Is it a good thing that the paths are longer? How about the performance of DT and DG at equal path lengths?
* The comparison of TnT +bagging/adaboost with standard RF and adaboost is done in the context of equal complexity in terms of number of base models and overall number of splits. Again, the process to achieve this equal complexity is unclear. Is the C set for TnT ensembles and then using the obtained complexity, the standard ensembles are created with different max_depth (?) until they reach the same complexity? Any way I believe the comparison has to be done also without constrains for both methods. Using a maximum number of base DT of 20 (#E) is clearly suboptimal for RF and adaboost. Also using a limiting number of split for RF is suboptimal. The results of a fully trained RF (#E=100-200, and no splits limit) and adaboost should also be reported.

Minor aspects:
* Sometimes the paper is a bit repetitive (e.g. lines 164-171). 
* Figure 2 plots (N 1 = 2, N 2 = 5) in c) and d) with different colour. it would be clearer to use the same colour.
* Fig 5: It could be interesting to mark the root node in the plots. Also plot b) could be unentanled a bit to better visualize.

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors present a new algorithm for large decision graphs. Tree in a tree is a scalable method that fits new decision trees in place of the internal/leaf nodes and constructs a directed acyclic graph. The authors show that their method outperforms other learning models in different datasets with different configurations.
main_review: * Positive points:
- The paper is well written and well structured. The authors are clear and objective in their communication.
- The experimental procedure sounds robust, with various datasets and classification methods (decision trees/graphs).
- The time complexity sounds good, even though the authors state very clearly that CART and TAO would be more efficient.

* Negative Points:
- Since the authors are using accuracy to quantify the power of their method, I believe more classification methods should be used in their study.  If the authors were accessing the readability of the final graph, it would be understandable to only use other decision trees and graphs as the benchmark. However,  accuracy-wise, other classification methods (e.g., neural networks and kernel machines) should be used as well.
- Considering that decision trees are sometimes used for their explainability, I would have liked to see each dataset's result. Figure 5 is not readable or understandable.
- I do not believe that the limitations written by the authors are limitations at all. A trade-off is clear for me in terms of accuracy versus training time. I would have like to see more limitations on this work or a more robust argumentation on why this limitation is essential for TnT.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper presents a way to to grow decision graphs by using decision trees as the splitting criterion of another tree. Reviewers praised the simplicity of the idea and its effectiveness on classification tasks.

During the reviewing and rebuttal phase, some criticisms regarding missing references and more crucially missing experiments with suitable comparisons were raised.
Authors provided additional convincing results in the rebuttal and managed to convince one reviewer to upgrade its weak rejection score into a weak acceptance.

The paper is accepted, subject to including the missing comparisons to the literature, and the additional baselines and experiments discussed in the rebuttal.
Decision: Accept (Poster)