Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors studied the optimal and fair decision trees. They proposed a dynamic programming method considering the fairness constraint. Due to the global fairness constraint, the decision tree is not separable. Using upper and lower bounds on the fairness values, the authors decrease the search space and improve the solution time. 
strengths_and_weaknesses: With the use of upper and lower bounds on fairness, the authors set forth a new dominance relation. The same bounds also lead to a new pruning mechanism. Consequently, the authors obtain a method that finds the Pareto front, and it is faster than the other methods proposed in the literature.

The paper is mainly based on two papers [14, 15] that authors have also cited. Adding only group fairness constraint and pruning the trees through trivial bounds are straightforward extensions. In its current form, the work does not introduce enough novelty to the literature.

questions: Is there a theoretical guarantee that obtaining the "global" optimal solution to the posed problem would lead to higher accuracy and/or fairness for the out-of-sample instances?

What is the impact of highly imbalanced datasets on the performance of the proposed algorithm?

The authors have reported only the runtimes for DPF and FairOCT. How about the accuracies and fairness scores? In case of multiple optimal solutions, one would think that the out-of-sample performances may differ. Do these methods obtain exactly same solutions? 

How do the computation times of the proposed method compare against the method of Kamiran? Are the results for Kamiran in Table 3 obtained after tuning the hyperparameters of the method?

The following recent paper discusses fairness in optimal trees by formulating MIP. Their results seem promising. It would be great if the authors also review this paper and highlight their differences:

Jo, N., Aghaei, S., Benson, J., Gómez, A., & Vayanos, P. (2022). Learning Optimal Fair Classification Trees. arXiv preprint arXiv:2201.09932.


limitations: Limitations are discussed in the conclusion section.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors designed a specialized algorithm, DPF(Dynamic Programming Fair?) that can find fair optimal decision trees, i.e., the decision trees with the best performance metrics under a given fairness gap constraint. The algorithm can also return a Pareto front of performance and fairness and use the front to filter out dominated splits at each level. Dynamic programming is used in DPF to find possible splits. The authors show numerical results that DPF is much more efficient to train compared to related works like FairOCT. 
strengths_and_weaknesses: Strengths:
1. Strong numerical results showing that DPF is much more efficient to train compared to related works like FairOCT
2. Clear Problem statement

Weaknesses:
1. No theorem or propositions to show the advantage of DPF theoretically
2. Pseudo code would be nice to have in the main article than in the appendix to help the readers understand the algorithm
questions: 1. In some of the other decision tree models, putting samples into different bins help significantly with the split finding and training speed. In this work, when keeping all the non-dominated submodels, is it possible to use this technique? 
2. If the technique in question 1 is possible, what are some of the conditions that guarantee when splitting at the bin boundaries results in two non-dominated submodels, all other splits within this bin are also non-dominated? Is this somehow related to the monotonic condition? 
3. Is it possible to come up with theoretical reasonanings on the efficiency of DPF? Can you specify when, or on what type of dataset DPF can perform much better than the related works and when not?
4. DPF is compared to other in-process fairness oriented algorithms in the article, so a natural question to ask is can DPF be compared to or combined with pre-process fairness oriented methods or post-process fairness oriented methods?
limitations: As discussed in the weaknesses already.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a dynamic programming (DP) model to construct optimal decision trees subject to fairness constraints, i.e., where the positive classification observes demographic parity. The methodology extends an existing bi-objective recursive reformulation for decision trees and returns the full Pareto frontier in terms of the optimal and fairness criteria. In particular, the authors develop upper and lower bounds on the fairness constraint to ensure all generated solutions are feasible, in addition to pruning techniques to speed up the frontier enumeration. The numerical study evaluates the approach against current (mostly MIP-based) state-of-the-art methods.
strengths_and_weaknesses: Strengths
- Very strong numerical results, significantly outperforming the state of the art
- Idea is intuitive and easy to implement
- Paper very well written

Weaknesses
- I have concerns about the contribution; except for the lower or upper bounds, the methodology itself seems to be derived in a somewhat straightforward way from existing works
- Scalability and usage could be detailed more thoroughly

Major comments

Overall, I greatly enjoyed reading the work because the methodology is intuitive, involves interesting bounding procedures associated with the structure of the fairness constraint, and the numerical results are quite strong, outperforming MIP-based models very prominently. However, I have two major concerns after reading the work.

(i) [Novelty.] My (possibly wrong) impression is that the authors essentially implemented the ideas from two existing works (references [14] and [15] of the paper) for this paper. More precisely, they specialized the bi-objective approach to accommodate fairness constraints by considering interval-based labelling to ensure the full Pareto frontier was enumerated correctly. While the effectiveness is apparent and there is some novelty in the upper/lower bounds, this brought me some concerns about whether the results are somewhat incremental to existing literature. I believe this could be addressed in multiple ways. For instance, authors could expand on other constraint classes that could leverage the methodology, or whether there are other fairness definitions that could also be accommodated by the technique.

(ii) [Scalability and Usage.] It is impressive that the authors are enumerating the full Pareto frontier. This shines light into two usual questions that also follow any type of multiobjective work. First, it is unclear how scalable that is; while it worked well for the datasets in the numerical experiments, how large are the problems that actually can be solved by DP in this context? Second, even if the Pareto frontier can be fully enumerated, what would be the guidelines/insights to pick the appropriate tree among such a possibly large set? It would be great if authors could expand further on those concepts.




questions: 1. Given the nice performance, is it possible to extend the approach to non-binary trees? It would not be surprising to find cases where the DP would perform well (if the state space is still relatively "compact").

2. Could authors discuss the scalability of the approach for datasets beyond the ones presented?

3. Labelling approaches in multiobjective DP optimization can be significantly improved when using bidirectional search, such as the one presented in [1]. That is, the state-space graph of the DP is constructed from top-down and bottom-up separately, and the Pareto frontier is "merged" when the two layers meet. This is the key performance in state-of-the-art multiobjective models, such as the ones appearing in shortest-path subproblems for vehicle routing. I wonder how this relates to Algorithm 1, or whether that could help improve the methodology?

[1] Galand L, Ismaili A, Perny P, Spanjaard O (2013) Bidirectional preference-based search for state space graph problems. Proceedings of the Sixth International Symposium on Combinatorial Search
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper address the problem of finding fair and accurate decision trees. Using demographic parity as the fairness definition, they try to minimize misclassification while at the same time satisfying a fairness constraint. The problem is hence formulated as a multiobjective problem in which both misclassification error and group imbalance are minimized. Having defined a dominating solution as one which is similar or better in both objectives, they search for Pareto fronts of nondominated solutions.

Previous work have proposed dynamic programming approaches for biobjective optimization in decision trees, and finding the Pareto front  of nondominated solutions in the case where the objectives are additive and monotonic. Since the imbalance part of their objective is not monotonic (contains absolute value), the dynamic programming approach cannot be directly used. As a result, the authors propose a way to calculate the upper and lower bound of the imbalance value, and later on, redefine the dominance relation based on these values. They then propose a dp approach that finds the Pareto frontiers and improve the time complexity of the search by pruning the search space based on the upper and lower bound values of the imbalance.
strengths_and_weaknesses: Strengths
- very well written except for some typos mentioned below
- they consider a well-motivated problem

Weaknesses

- From section 4 on, the paper does not flow very well. In the end of section 3, it gets clear that due to non-monotonicity of the imbalance function, the dp approach cannot be directly used and the reader is waiting for that problem to be addresses. In the beginning of section 4 you directly mention that you present DPF, without saying what it stands for, and without saying how it tries to overcome the monotonicity problem. Section 4 is hard to follow. Not everything is clearly defined such as the meaning of (R), being the rest of the tree, and how exactly you calculate the upper/lower bounds. I believe the quality of the upper/lower bounds directly affect the quality of the solutions found so I do not find the sentence "These bounds can be trivial, ..." in line 202 really convincing. 

There are further presentation issues mentioned below:
- punctuations before/after equations are completely missing
- typo in the first line of Eq.8
- Eq 8 needs some explanation. You copy it from another paper without introducing what it is searching for. For example, it is not clear what (|D|,0) is showing. I had to refer to the cited papers to understand but I think it is better if the paper is self-contained and the reader does not need to search for the meaning of notation elsewhere.
- lines 176-178 are not well written
- line 191, "is" is missing
- you never mention what is "DPF". You use the abbreviation from the first occurrence.
questions: I would like to thank the authors for taking the time to write the paper in a well-organized way. It was my pleasure to review the paper. I have a few questions from the authors: 

- How good are the set of Pareto frontiers? Can it be that a solution that is not dominated by any other solution is not really a good one? Assume the accuracy is very high but it is at the cost of very low fairness (in the tuple (M,I), M is very high and I is very low. Then it could happen that no other solution can dominate this one because no solution can beat M, but the solution is very imbalanced. 

- In equation 11 and 12, is it not the case that the lower bound is always equal to the lowerbound of the rest + I_n and the upper bound is equal to the upperbound of the rest + I_n? I do not understand why you wrote it with min/max?

- it is not very easy to understand equations 14-17. What is the function U exactly? How exactly does the merge function work? if it works the same as defined in Eq.9, then how is it using the upper/lower bound information? If it is not using that information, why is it input to the function?

limitations: they have provided the run time of their approach so it gets clear that it gets higher as the dataset or the number of features grows. Maybe they could also talk about space complexity and how much storage they used to store the intermediate solutions, since they use a dp approach. They could also show the performance considering more fairness criteria rather than just demographic parity. Their approach is applicable to binary classification with binary features. It would be nice to mention what happens if the features are not binary and whether the algorithm could scale.
review_title: null

Meta-review: metareview: I recommend acceptance due to the strengths identified by the positive reviews, despite some doubts expressed by more negative reviews. This paper modifies existing dynamic programming approaches for learning decision trees to accommodate non-monotonic constraints, motivated in particular by group fairness. Experiment show that this approach is orders of magnitude faster than existing alternatives. 

The main unresolved reviewer concern is novelty---how much of a contribution is the ability to hand non-monotonic constraints? If this paper were exclusively targetted to the decision tree community, this would be an important concern. However, I view the significance of this contribution in terms of making decision trees a computationally tractable option for designing fair decisions. Interpretability is an important concern in many domains where fairness is an issue, and thus this is an important contribution.
confidence: Certain
Decision: Accept