Enhancing Group Fairness in Online Settings Using Oblique Decision Forests

Thank you for your detailed feedback and helpful comments.

Conditions for online learning using stale gradients

Our proposed method, Aranyani, is a tree structure specialized and related learning algorithm designed to effectively use such aggregated computations. The tree structure is parameterized using a logistic network at each node. We compute fairness gradients by taking the derivative of node outputs. Crucially, this structure allows us to prove that the error in computing the fairness gradients cannot diverge in an unbounded manner.

The theoretical results we propose rely solely on the assumptions of bounded inputs, a compact parameter set, and smooth activation functions, as well as a smooth task loss. This allows us to derive the explicit bound in Lemma 3 (Page 6), which shows that the error is a function of the $\delta$ parameter (associated with the Huber loss) and input bound $B$.

Aranyani's performance under an adversarial input stream.

Indeed understanding the performance of Aranyani under shifts in data distribution is an interesting research question. We have added results in an adversarial setting that is aligned with your proposal and report them in Appendix D (Subsection: Adversarial Stream).

Specifically, we construct an adversarial stream of data using the Adult dataset, where we present Aranyani with 90% of the majority class samples followed by the entire minority class and the remaining 10% of the majority class samples. We also experiment with the inverse scenario where the minority class samples are presented before the majority ones.

The detailed results are presented in Appendix D (Subsection: Adversarial Stream) section. From the results, we observe that even in such scenarios Aranyani can achieve good fairness-utility tradeoffs and it is possible to control the tradeoff using the $\lambda$ parameter.

We would also like to note that the convergence bounds in Theorem 1 are independent of the nature of the data stream. Therefore, the gradient bounds of Aranyani always converge to a small value, emphasizing good performance.

Thanks for taking the time to review our responses. Please let us know if you have any questions or would like any further clarifications.

Thank you for your detailed feedback and helpful comments.

Details of Aranyani’s training procedure.

We have now provided a detailed outline of Aranyani’s training procedure in Appendix C.3 (Algorithm 1).

Yes, Aranyani can be trained as an end-to-end neural network. The task loss gradients can be computed directly using standard autograd libraries. Also, for each input gradient w.r.t. node outputs can be efficiently computed. Then, these node outputs and gradients are aggregated over time to form the final gradients shown in Equation 5. We have implemented Aranyani using TensorFlow.

Impact of dataset size on Aranyani’s performance

We have performed additional experiments to evaluate the robustness of Aranyani when the dataset size is reduced. We report the performance in Appendix D (Subsection: Dataset Size Ablation). We observe that the tradeoff between fairness and utility gradually deteriorates with a decrease in the dataset size. This happens primarily because it is difficult to achieve higher accuracies with lesser data.

Impact of tree depth on Aranyani’s performance

In ablation experiments (Section 5.3), we experimented with deep trees up to a height of 8 and investigated its impact on the performance. Figure 4, shows the tradeoff between accuracy (improves with height) and DP (worsens with height) with tree height.

In practice, we have observed that a small tree depth is generally adequate for the majority of tasks. This aligns with findings from prior studies, such as TEL [1] (which employed a tree depth of 4) and DGT [2] (which utilized tree depths up to 10).

[1] Tree Ensemble Layer, Hazimeh et al. 2020. [2] Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent, Karthikeyan et al., 2022.

The practical utility of Aranyani in real-world applications.

A prominent real-world application for improving fairness in online settings is applications that involve output moderation using safety/toxicity classifiers), which may include chatbots, comments on social media platforms, etc.

This has motivated us to work on this problem entails safety or toxicity classifiers that need to adapt to new safety violation rules/examples on the fly. As such we adapted the toxicity classification task (Civil Comments [3]) to this particular setup and will release the code to reproduce the setup for future work.

We also perform experiments on the CelebA image classification dataset. The task for this dataset is to predict certain characteristics of images (in this case hair color). One can imagine that fairness in predicting image characteristics would be crucial to services that organize user photos. Such image characteristics may be used for organization; fairness ensures consistent organization experience for users.

[3] https://www.kaggle.com/c/jigsaw-unintended-bias-in-toxicity-classification/data

Comparison of Aranyani with recent batch learning algorithms

Most representation learning methods are trained in an incremental setting where they require access to task identities. Even within a task, these algorithms need access to a batch with samples from different protected groups. Such labeled instances are not available in the online learning scenario.

Due to its stochastic batch optimization procedure, we found that only FERMI [4] can be adapted to function in the online setting. We report the results in Appendix D (Subsection: Comparison with Batch Techniques). We observe that FERMI struggles to perform with batch size=1, and is unable to improve fairness in this setting.

[4] A Stochastic Optimization Framework for Fair Risk Minimization, Lowy et al. 2022

Legends in Figure 4 (right)

We have improved the figure and added legends for each metric.

Thank you for your detailed feedback and helpful comments.

Use cases of group fairness in online settings.

Studying group fairness in the online setting has several use cases (outlined below). In our initial draft, we alluded to these in the last sentence of the first paragraph of the introduction. Based on your feedback, we have updated the introduction in the revised draft to more clearly elaborate on these use cases.

One major use case for improving fairness in online settings is applications that involve output moderation using safety/toxicity classifiers), which may include chatbots, comments on social media platforms, etc. In such applications, the definition of safety is evolving and new unsafe data points are identified on the fly, which makes them a prime candidate for online learning. Our goal is to improve demographic fairness for models learned through online learning in these applications.

To showcase the practical feasibility of our approach, we conducted experiments aimed at detecting toxicity in Wikipedia comments (refer to Section 5.2) within an online environment as a simulation testbed for this problem.

In a similar manner, we have used other datasets to simulate online learning settings, where data would arrive continuously over time, e.g., CelebA, an—image classification dataset. The task for this dataset is to predict certain characteristics of images (in this case hair color). One can imagine that fairness in predicting image characteristics would be crucial to services that organize user photos. Such image characteristics may be used for organization; fairness ensures consistent organization experience for users.

Fairness-aware online learning setting and the significance of storing past samples within this context.

As mentioned by the reviewer, to achieve group fairness in online settings, we assume that we can only store aggregate feedback from previous data points (e.g., aggregate of previous gradients). We assume that we cannot store the actual data points that contain sensitive demographic information.

Unlike typical online learning setups, it is not possible to obtain a fairness regularizer gradients update using a single instance. This is because group fairness regularizers are defined using a group of instances. This poses an interesting challenge of updating the model at each step without accessing previous instances.

This is the major challenge that we overcome in this paper. We have updated Section 3.1 to articulate the setup and our contribution better.

Objectives and metrics in group fairness aware online learning.

The online learning setup in our case is to perform multi-objective optimization for task loss and group fairness loss.

Since the fairness loss is defined over groups of samples it is not possible to define the fairness loss for a single instance and compute a instance-level loss. This makes it difficult to apply conventional online learning algorithms to this problem.

In principle, we care about the fairness-accuracy trade-off achieved by the system’s predictions over time. Therefore, in the online setup, Eq. 2 can be written as:

$\min_f \sum_{t=1}^T \mathcal{L}(f_t(\mathbf x), y), \text{ subject to DP = } \left|\mathbb{E}[f_t(\mathbf x|a=0)] - \mathbb{E}[f_t(\mathbf x|a=1)]\right| \leq \epsilon.$

Please note that the expectations in the above equation are over samples that have not appeared in the online training stream. This equation can be easily modified into Aranyani's objective by replacing the DP constraint with the node-level constraints in the tree (mimicking the transition from Eq. 2 $\rightarrow$ Eq. 3).

In online learning, we can typically get an unbiased estimate of this by computing objectives (training loss) on the new sample before updating the model. However, due to our unique problem setup, the group fairness objective cannot be computed using a single instance.

We empirically investigate the performance of our model by computing the fairness-accuracy tradeoff and observe how it evolves during the online training process. We report the results in Appendix D, Subsection: Tradeoff Convergence, Figure 12 (right). We observe that Aranyani achieves gains over the majority baseline, which implies that it can achieve non-trivial tradeoff gains.

Evaluation: To evaluate this in practice, we store all predictions made by our system and report the group fairness (demographic parity) using these decisions at each time step.

First, we would like to express our gratitude to the reviewer for taking the time to read our response, engaging with it, increasing the score, and allowing us to engage in an interactive discussion to address the remaining comments. Below, we respond to the two specific remaining comments.

Why do we just consider achieving DP for t? Or do you mean we need to achieve this constraint for all t?

Yes, you are correct. We mean that the DP condition needs to be satisfied for all t. Here is the updated objective for the same:

$\min_f \sum_{t=1}^T \mathcal{L}(f_t(\mathbf x), y), \text{ subject to DP = } \left|\mathbb{E}[f_t(\mathbf x|a=0)] - \mathbb{E}[f_t(\mathbf x|a=1)]\right| \leq \epsilon. \forall t \in [1, T]$

...... [As in] Eq. (5) in the paper “A Reductions Approach to Fair Classification”, the regularizer can be just represented as some linear combination of losses → therefore, we can still compute the gradient just like typical online learning setting, and then use the FTL, right? [...] [Similar approach in] “FairBatch: batch selection for model fairness”*

Thanks for pointing this out.

Equation 5 (below) in (Agarwal et al. 2018 [1]) is the definition of cost sensitive classification. describes the task loss and not the fairness regularizer.

$\arg \min_{h \in \mathcal H} \sum^n_{i=1} h(X_i) C^1_i + (1 - h(X_i)) C^0_i. \quad \text{(5)}$

In Agarwal et al’s Eq (5), each class has an associated cost ($C_i^0$ for class 0, $C_i^0$ for 1). This task loss (Eq 5) is additive across input samples. Similarly in our paper the task loss (our Eq 2), is additive across input samples. The fairness regularizers in Agarwal et al are reformulated as cost-sensitive classification. However, their cost-sensitive optimization procedure requires estimation of certain probability distributions for it to work well as we will discuss below:

The challenge for online methods comes in the fairness regularizer in the objectives. Agarwal et al. (2018) applies the fairness regularizer in the first (unlabeled) equation of Section 3.2 in their paper shown below.

$L(Q, \mathbf{\lambda}) = \widehat{\mathrm{err}} (Q) + \mathbf{\lambda}^T (\mathbf M \mathbf{\hat{\mu}}(Q) - \mathbf{\hat{c}}).$

In this equation, $\widehat{\mathrm{err}} (Q)$ refers to classification error, and the fairness objective is $\mathbf{\hat{\mu}}(Q)$ term is a vector of conditional moments across protected groups ($a$) or target label ($y$) or both (described in Example 1&2 in their paper). This is shown below:

$\widehat{\mathbf{\mu}}(Q) = [\widehat{\mu}_{a_i, y_i}(Q)], \quad \forall (a_i, y_i)$

Recall that the setting in our paper considers a single sample at a time. This sample will belong to one of the two protected groups (the attribute $a$). Let’s consider DP fairness in such a setting, $\hat{\mu}(Q) = [\hat{\mu_{a=0}}(Q), \hat{\mu_{a=1}}(Q)]$ (since there is no conditioning on the true label). Suppose the observed sample has $a=0$. We would then not be able to estimate the fairness term, $\hat{\mu_{a=1}}$. We can estimate $\hat{\mu}_{a=0}$, but note that the overall estimate of the cost-sensitive objective function could be severely biased if we simply plug in $\hat{\mu}$ (and hence the overall optimization procedure may not even converge) but the estimate could be severely biased (and hence not converge).

Similarly, in the (Roh et al., 2021 [2]) paper the additive equations are presented in Section 2 using $L_{y, z}$ terms shown below:

$\mathbf{w_\lambda} = \arg\min\limits_{\mathbf{w}} \lambda_1 L_{0,0}(\mathbf{w}) + \left(\frac{m_{*,0}}{m} - \lambda_1\right)L_{1,0}(\mathbf{w}) + \lambda_2 L_{0,1}(\mathbf{w}) + \left( \frac{m_{\*, 1}}{m} - \lambda_2\right) L_{1,1}(\mathbf{w}).$

Quoting from the notation section of their paper: `` $L_{y,z}(\mathbf w)$ be the empirical risk aggregated over samples subject to $y = y$ and $z = z$”. Since a given input sample is associated with only a single $y’$ and $z’$, all terms except the $L_{y’, z’}(\mathbf w)$ cannot be estimated using a single sample.

In summary, the difficulty of group fairness in the online setting is about estimating deriving an unbiased estimator for the fairness term regularizer from a single observed sample. This is evident in both of the approaches mentioned, Agarwal et al (2018) and Roh et al (2021). Concretely, if we have a binary classifier with a binary sensitive attribute $a$. With a single sample, with say $a=0$, it is not clear how to estimate the fairness violation rate from this single sample since the other attribute $a=1$ is unobserved.

[1] A Reductions Approach to Fair Classification, Agarwal et al. 2018 (link)

[2] FairBatch: Batch Selection For Model Fairness, Roh et al. 2021 (link)

We hope that this helps clarify your question. Please don’t hesitate to let us know if we can help answer any other questions/comments in the remainder of the discussion period.

We apologize for the miscommunication on our end; Eq. (5) is indeed the definition of vanilla cost sensitive optimization (and neither the task loss or the overall loss). We have corrected this in our above reply through an edit for clarity as well.

Apart from this, we should say that the main point of our response is not dependent on Eq. (5). The main point that we are making is that the reduction approach of Agarwal et al (2018) relies on the computation of the estimator $\hat{\mu}$, where $\mu$ is an expectation over an indicator function as defined in the unnumbered Eq. after (1). This is the term that cannot be directly estimated from a single (or even no) sample in our online learning setting. Thus, enforcing the constraints on these quantities is not directly possible and is not expected to work.

Suppose the observed sample has $a=0$. We would then not be able to estimate the fairness term, $\hat{\mu_{a=1}}$ as we have no samples on it. Estimating $\hat{\mu}$ is needed in the learning algorithm for the cost-sensitive reduction.

Thank you for your detailed feedback and helpful comments.

Functioning of Aranyani at each node and its scalability with multiple protected groups

In our work, we use soft decisions at each node of the tree (soft-routed oblique trees defined in Section 2). In this way, every sample has some probability of reaching all leaves. The probability of reaching a node is a function of the outputs in the path from the root to that node. Since we want nodes to assign outputs equally to different groups, we apply fairness constraints on the node outputs.

Scaling: The storage cost of the aggregate statistics scales linearly with the number of protected groups. For binary settings, the storage cost is $O(2^hd)$, where $d$ is the data dimension and $h$ is the tree height. When we have $K$ groups, the storage cost becomes $O(2^hKd)$. The time complexity increases by a constant amount when $K$ groups are available, as the Huber loss must be computed for each group (refer to Equation 24 in Appendix B).

Choice of fairness constraint parameters $\lambda$ and $\delta$

A large number of in-processing fairness regularization techniques apply a divergence with a regularization strength parameter to improve fairness at the cost of model performance (cf. [1, 2]). It is expected that as $\lambda$ grows, the fairness violation will decrease. However, note that in practice, we are interested in test performance vs test fairness violation tradeoffs, and hence tuning the value of $\lambda$ could only be achieved using a validation set as is common in prior work (like FERMI [2]). We follow the same procedure and report results for a range of $\lambda$s.

[1] Fairness-Aware Learning for Continuous Attributes and Treatments, Mary et al. 2019 [2] A Stochastic Optimization Framework for Fair Risk Minimization, Lowy et al. 2022

Pseudocode for Aranyani’s training algorithm

We have added a detailed outline of Aranyani’s online algorithm in Appendix C.3 (Algorithm 1).

Scalability (computational time) of Aranyani

We would like to clarify that we do not generate a new oblique tree at each step. We use a fixed set of complete binary trees (forest) throughout the training process and only the node parameters are updated during training. As is the case for training online models the only updates we use are task loss gradients and fairness loss gradients (Equation 5), which need to be computed at each time step.

In practice, our approach is quite scalable across large data streams. We conducted additional experiments to evaluate the runtime of our algorithm and report them in Table 2 (Appendix D, Subsection: Runtime Analysis).

Thank you for such detailed feedback and so many insightful suggestions.

Efficacy of Aranyani using other notions of fairness

We have added the results for the equality of opportunity fairness measure in Appendix D (Subsection: Equality of Opportunity). Even in this setup, we find that Aranyani achieves a strong accuracy-EO tradeoff and outperforms the majority baseline significantly.

Error bars in Aranyani’s results

We have incorporated the variance for each result and revised the figures in both Figures 2 and 3 within the main paper.

Variance in accuracy and DP scores during the online training process.

We have performed additional experiments to examine this scenario in Appendix D (Subsection: Performance Variance). We report the results from 5 different runs on the Adult dataset. We observe that the variation in the metrics: accuracy and DP, exist only during the initial phase of the online learning process (please note that the $x$-axis is in log-scale for better visibility). After as few as 1000 samples, both the accuracy and DP scores stabilize with minimal variation.

Variance in results with an increase in the number of trees in the forest.

Thank you for pointing this out. In the initial draft, we reported the minimum and maximum scores out of 3 runs by the error bars. We have fixed that now and report the standard deviation across 5 different runs for each tree count configuration. We have also expanded our evaluation to investigate up to 15 trees in the forest. In the updated figure, we observe a decreasing trend in the standard deviation of the reported metrics with an increase in tree count, as hypothesized in the main paper (Section 2).

The influence of tree depth on the expressivity of Aranyani.

The empirical results for accuracy and fairness follow that of our theoretical results. Apart from the tree depth, there are several ways to increase the expressivity of the model: (a) using more trees, and (b) using stronger classifiers at the node level, among others. In practice, we have observed that a small tree depth is generally adequate for the majority of tasks. This aligns with findings from prior studies, such as TEL [1] (which employed a tree depth of 4) and DGT [2] (which utilized tree depths up to 10).

[1] Tree Ensemble Layer, Hazimeh et al. 2020. [2] Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent, Karthikeyan et al., 2022.

Ablation with different regularization loss functions.

In this work, we focus on the Huber loss as the regularization measure. We choose Huber as it provides us with better theoretical guarantees while using stale gradients. In general, it is possible to explore other divergence measures like L2 loss. If we use L2 loss instead the fairness gradient in Equation 5 will have the $F_{ij} \Delta F_{ij}$ term only. The approximation error of $F_{ij}$ may increase over time leading to a worse convergence bound of the gradients. For Huber loss, it is possible to theoretically bound the error using the $\delta$ parameter. Hinge loss on the other hand is used to measure the classification performance and we could not think of how to apply it directly to regularize $F_{ij}$.

We have also added the results and discussion for this experiment in Appendix D (Subsection: Regularizer Ablation).

Empirical runtime analysis of Aranyani

We have provided an empirical estimate for the runtime in Appendix D (Runtime analysis). Please refer to that section for a detailed description.

Legends in Figure 4 (right)

We have updated the figure and included legends to improve its clarity.

Typo in Aranyani’s symbol

We have fixed the symbol in the current draft.

Scaling Aranyani to an M-ary tree and its applications

Yes, it is possible to have a non-binary, $M$-ary oblique tree structure. For an $M$-ary oblique tree, the DP bound is $hM^h\epsilon$ and the empirical Rademacher complexity bound is $M^h/\sqrt{n}$. Again, this goes on to show the tradeoff between fairness and accuracy as the DP bound worsens and the Rademacher bound improves.

We do not foresee any specific scenario that necessitates the use of $M$-ary splits. Although $M$-ary splits lead to better expressivity of the model, it can be achieved through various means like increasing the tree depth, number of trees in the forest, complexity of the node networks, etc.

Ablations with different feedback mechanisms during online learning

We have performed this experiment on the COMPAS dataset, where the model receives gradient updates only when its prediction $\hat{y}=1$. We report the results in Appendix D (Limited Feedback) section. We observe that Aranyani achieves a similar tradeoff curve in this setup. However, it is unable to achieve higher accuracies as it receives a significantly smaller number of gradient updates.