\subsection{Online Monitoring of Class Imbalance and Model Update}
\label{sec:class_monitoring}
In evolving data streams, the role of minority and majority classes can exchange and what is now considered to be minority might turn later into a majority class or vice versa~\cite{wang2013learning}. Knowing the class ratio over the stream is important for our method as it directly affects the instance weighting during training. Therefore, we keep track of the stream imbalance (whole history) using the online class imbalance monitor (OCIS) of~\cite{wang2013learning}.  
\begin{equation}\footnotesize 
    \label{eq:CCIS}
    OCIS_{t} = W_{t}^+ - W_{t}^- 
\end{equation}\normalsize
where $W_{t}^y$ is the percentage of class $y$ at timepoint $t$ maintained in an online fashion. In particular, upon the arrival of a new instance $x$ at timepoint $t$, the percentage of a class $y$ is updated as follows:
\begin{equation}\footnotesize
    \label{eq:class_monitor}
    W_{t}^y = \lambda\cdot W_{t-1}^y + (1-\lambda)\cdot\mathbb{I}[(y_{t},y)]
\end{equation}\normalsize
where $\mathbb{I}[(y_{t},y)]$ is an indicator function which equals to 1 if the true class label of $x_{t}$ is $y$, otherwise 0 and $\lambda \in [0,1)$ is a user-defined decay factor which controls the extent to which old class percentage information should be considered. The larger $\lambda$ is, the higher the contribution of historical information is, which however might hinder adaptation in case of concept drifts. A detailed analysis on the impact of $\lambda$ is shown in Sec.~\ref{sec:impact_of_L}. 

The imbalance index OCIS takes values in the $[-1,1]$ range, with 0 indicating a perfectly balanced stream and -1 or 1 indicating the total absence of one class. 

\noindent{\textbf{Model adaptation:}}
We extend OSBoost first for class imbalance; the pseudocode of the algorithm is shown in Algorithm~\ref{alg:train}. 
Upon the arrival of a new instance $x$ at timepoint $t$, the class imbalance status is updated (line 2) according to Equation~\ref{eq:CCIS}. 
Then, the weak learners are updated sequentially (lines 4-11) so that the predictions of model $H_i^t$ (line 6) affect the training of its successor model $H_{i+1}^t$ by changing the weight/contribution of instance $x$ to the model accordingly. 
The weight of instance $x$ is tuned per learner $H_i^t$ based on the error of the predecessor model $H_{i-1}^t$  on $x$, but also based on current class imbalance (lines 8-11). E.g., if at timepoint $t$ the $OCIS_{t} < 0$ and $x_t \in y^{+}$ then the $w_{i+1}$ will be increased. 
On the other hand, if at timepoint $t$ the $OCIS_{t} < 0$ and $x_t \in y^{-}$ then the $w_{i+1}$ will be decreased. Using this weighting strategy, $\mathsf{FABBOO}$~increases/decreases the instances' weights according to the class imbalance monitor.

To summarize, traditional OSBoost performs error-based instance weight tuning but does not adjust for class imbalance. On the contrary, $\mathsf{FABBOO}$~adjusts the instance weights also based on the dynamic class ratio (c.f.~Equation~\ref{eq:CCIS}) so that instances from both classes receive equal attention from the learners. Note that if the stream is balanced, i.e., $W_{t}^+ - W_{t}^-\approx 0$, the weights are only slightly affected. 

\begin{algorithm}[t!]\footnotesize 
\caption{FABBOO training procedure}
    \label{alg:train}
\begin{algorithmic}[1]
\Procedure{Train}{$x_{t},y_{t},\gamma, H^{t-1}_{1:N}$}      \Comment{$x_t$: newly arrived instance, $y_t$: label of $x_t$, $\gamma$: learning rate, $H^{t-1}_{1:N}$: current ensemble}
          \State $OCIS_{t} = W_{t}^+ - W_{t}^-$ \Comment{Update the class imbalance status}
        \State $w_1 = 1, q_0 = 0$ 
     \For{$i = 1$ to $N$}
        \State Train $H^{t}_i$ on $x_{t}$ with weight $w_i$  \Comment{Training of weak leaner $H_i$, where $i \in [1,N]$}
        \State $q_i = q_{i-1} + y_{t}\cdot H^{t}_i(x_{t}) - \frac{\gamma}{2+\gamma}$
        \State $w_{i+1} = min\{(1 - \gamma)^{q_{i}/2}, 1\}$  \Comment{OSBoost weight update}
       \If{$x_{t}\in y^+ $} \Comment{update $x_t$'s weight which belongs to$y^+$}
       \State $w_{i+1} = \frac{w_{i+1}}{1 + OCIS_{t}}$ 
        \EndIf
   
   
       
        \If{$x_{t}\in y^-$}  \Comment{update $x_t$'s weight which belongs to$y^-$}
      \State $w_{i+1} = \frac{w_{i+1}}{1 - OCIS_{t}}$
        \EndIf
   
   
   

      \EndFor
      \State \textbf{return} updated ensemble $H^t_{1:N}$
\EndProcedure
\end{algorithmic}
\end{algorithm}\normalsize 
 
\subsection{Online Monitoring of Cumulative Fairness and Boundary Adjustment}
\label{sec:disc_monitoring}
Methods which restore fairness only on \textit{short-term} (recent) outcomes fail to mitigate discrimination over time as discrimination scores that might be considered negligible when evaluated individually (i.e., at a single time point) might accumulate into significant discrimination in the long run~\cite{national2004measuring}. 
In this work, we aim to mitigate cumulative discrimination accumulated from the beginning of the stream in order to remove such long term discriminatory effects and adjust the decision boundary not only based on the recent behavior of the model, but also on its historical fairness-related performance.



Cumulative fairness monitoring accounts for discriminatory outcomes from the beginning of the stream until current time point $t$. 
We introduce the cumulative fairness notion for non-stationary environments. Cumulative fairness notions are updated per instance which makes them ideal for stream classification. In our work, we introduce cumulative fairness w.r.t. statistical parity~\cite{kamiran2012data}, equal opportunity~\cite{hardt2016equality} and predictive equality~\cite{verma2018fairness} as follows:


\begin{definition}{Cumulative Statistical Parity (Cum.S.P.)}
\label{eq:cumul_sp}\footnotesize 
    $$\frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in\bar{z}]}{\sum\limits_{i=1}^{t} \mathbb{I}[x_i\in\bar{z}] + l} -  \frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in z]}{\sum\limits_{i=1}^{t} \mathbb{I}[x_i\in z] + l}$$ 
\end{definition}\normalsize

\begin{definition}{Cumulative Equal Opportunity (Cum. EQ.OP.)}
\label{eq:cumul_eqop}\footnotesize
    $$\frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in\bar{z},y^+_i]}{\sum\limits_{i=1}^{t} \mathbb{I}[x_i\in\bar{z}, y^+_i] + l} -  \frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in z,y^+_i]}{\sum\limits_{i=1}^{t} \mathbb{I}[x_i\in z, y^+_i] + l}$$
\end{definition}\normalsize


\begin{definition}{Cumulative Predictive Equality (Cum. P.EQ.)}
\label{eq:cumul_pred_eq}\footnotesize
    $$\frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^-|x_i\in\bar{z},y^-_i]}{\sum\limits_{i=1}^{t} \mathbb{I}[x_i\in\bar{z}, y^-_i] + l} -  \frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^-|x_i\in z,y^-_i]}{\sum\limits_{i=1}^{t} \mathbb{I}[x_i\in z, y^-_i] + l}$$
\end{definition}\normalsize
\noindent where parameter $l$ is employed for correction in the early stages of the stream (0 division). 

Cum.S.P. Cum.EQ.OP or Cum.P.EQ. are maintained online using incremental counters updated with the arrival of new instances from the stream, and therefore, it is appropriate for stream applications where typically random access to historical stream instances is not possible. 
The cumulative fairness notions are employed by $\mathsf{FABBOO}$~for discrimination monitoring. When their values exceed a user-defined discrimination tolerance threshold $\epsilon$, the decision boundary should be adjusted.

\noindent{\textbf{Decision boundary adjustment:}}
\label{sec:boundaryAdjustment}
Post-processing adjustment of the decision boundary for discrimination mitigation has been investigated in the literature, e.g.,~\cite{fish2016confidence,hardt2016equality}. 
Closer to our approach is~\cite{fish2016confidence}, where the authors adjust the decision boundary of an AdaBoost classifier based on the (sorted) confidence scores of misclassified instances of the protected group. However, in contrast to~\cite{fish2016confidence}, we deal with stream classification, and therefore, we do not have access to historical stream instances in order to adjust the boundary accurately. Except for the access-to-the-data constraint, another reason for not considering the whole history for the adjustment of the boundary is the non-stationary nature of the stream. In such a case, adjusting the boundary based on the whole history of the stream will hinder the ability of the model to adapt to the underlying data and will eventually hurt fair outcomes.

To overcome this issue, we use a sliding window model of a pre-defined size $M$ to approximate the optimal boundary tweak. In particular, we maintain a sliding window of size $M$ (see Figure~\ref{fig:architecture}) for each segment to allow for boundary adjustment for different parity-based notions based on each discriminated segment. 
In the case of statistical parity or equal opportunity, the only relevant sliding window is the one for the protected positive segment (denoted by $SW_z^+$). On the other hand, in the case of predictive equality, the relevant segment to be maintained is the negative segment (denoted by $SW_z^-$). 

For the boundary adjustment, there are two main steps: i) we approximate the optimal boundary adjustment by calculating how many instances need to be accepted/rejected in order to restore parity at timepoint $t$. ii) We proceed by shifting the boundary based on the confidence scores of the classified instances which reside in the sliding window. 
To estimate the number of examples $(n_t)$ which are needed in order to mitigate discrimination at timepoint $t$ for each fairness notion, we solve the cumulative fairness notions with respect to $(n_t)$. To calculate $n_t$ for cumulative statistical parity, we obtain:
\begin{equation}\footnotesize
\label{eq:position_sp} 
n_t = \Bigg\lfloor \sum_{i=1}^{t} \mathbb{I}[x_i\in z] \cdot \frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in\bar{z}]}{ \sum\limits_{i=1}^{t} \mathbb{I}[x_i\in\bar{z}]} - \sum_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in z]\Bigg\rfloor
\end{equation}\normalsize

To estimate $n_t$ for equal opportunity, we follow the same rationale as previously: 
\begin{equation}\footnotesize
\label{eq:position_eqop} 
n_t = \Bigg\lfloor \sum\limits_{i=1}^{t} \mathbb{I}[x_i\in z,y_i^+] \cdot \frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in\bar{z},y^+]}{ \sum\limits_{i=1}^{t} \mathbb{I}[x_i\in\bar{z}, y^+_i]} - \sum_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^+|x_i\in z,y^+]\Bigg\rfloor
\end{equation}\normalsize

Predictive equality is identical to equal opportunity but for the negative class:
\begin{equation}\footnotesize
\label{eq:position_peq} 
n_t = \Bigg\lfloor \sum\limits_{i=1}^{t} \mathbb{I}[x_i\in z,y_i^-] \cdot \frac{\sum\limits_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^-|x_i\in\bar{z},y^-]}{ \sum\limits_{i=1}^{t} \mathbb{I}[x_i\in\bar{z}, y^-_i]} - \sum_{i=1}^{t} \mathbb{I}[f_i(x_i)=y^-|x_i\in z,y^-]\Bigg\rfloor
\end{equation}\normalsize


In the offline case~\cite{fish2016confidence}, they tweak the boundary continuously until parity is achieved. In our work, we approximate the optimally fair decision boundary by considering as threshold the $n^{th}$'s instance confidence score. For this, the misclassified instances in $SW_z^+$ (or $SW_z^-$) are sorted based on the confidence scores in a descending order. The decision boundary is adjusted according to the $n_{t}$-th instance of the sorted window ($SW_z^+$ or $SW_z^-$). In particular, if $\theta^{t-1}$ is the decision boundary value (original value $\theta^{0}$ is 0.5) of the $n_{t-1}$-th, the fair-boundary is adjusted to $\theta^{t}$. Note that in the early stage of the stream, where the sliding window does not contain a sufficient number of instances, the boundary is tweaked based on the misclassified instance with the highest confidence within the window.

\subsection{$\mathsf{FABBOO}$~Classification}
\label{sec:classification}
$\mathsf{FABBOO}$~is an online ensemble of sequential weak learners that tackles class imbalance and cumulative discriminatory outcomes in the stream. Moreover, $\mathsf{FABBOO}$~deals with concept drifts, through \textit{blind adaptation}, by employing a base learner that is able to react to concept drifts. In particular, we employ Adaptive Hoeffding Trees (\textbf{AHT})~\cite{bifet2009adaptive}  as weak learners; AHT is a decision-tree induction algorithm for streams that ensures DT model adaptation to the underlying data distribution by not only updating the tree with new instances from the stream, but also by replacing sub-trees when their performance decreases.  
 


The classification of a new unseen instance at time point $t$, i.e., $x_t$, is based on weighted majority voting and depends on its membership to $z$. If the instance does not belong to $z$ (i.e., it is a non-protected instance), then the standard boundary of the ensemble is used. Otherwise, the adjusted boundary is used. More formally (for Cum.S.P. and Cum.EQ.OP.):
\begin{equation}\footnotesize 
\label{eq:ensemble_disc}
f_t(x_{t}) =
 \begin{cases}
 y^+ & \quad  if~x_{t} \in z~and~H^t_{1:N}(x_{t}) \geq \theta^{t}\\
 H^t_{1:N}(x_{t}) & \quad \text{otherwise.}
 \end{cases}
\end{equation}\normalsize
where $N$ is the number of weak learners of the ensemble, and $\theta^t$ is the fair adjusted boundary at timepoint $t$.
Similarly, for Cum.P.EQ. the decision of $f_t(x_{t})$ is $y^-$ is the confidence score is greater than the boundary at the time point $t$. Note that the adjustment of the boundary based on $\theta^t$ is applied at the ensemble level.




\subsection{Competitors, Datasets and Metrics}
\label{sec:baselines}

\noindent{\textbf{Competitors}:} We evaluate FABBOO against two recent state-of-the-art fairness-aware stream classifiers~\cite{iosifidis2019fairness,wenbin2019fairness}, the fairness-agnostic non-stationary OSBoost~\cite{chen2012online} and imbalance-aware non-stationary and fairness agnostic CSMOTE~\cite{bernardo2020csmote}. We also employ two variations of FABBOO to show the impact of its different components, namely class imbalance and cumulative fairness. All methods employ AHTs~\cite{bifet2009adaptive} as weak learners and therefore are able to handle concept drifts. The only exception are FAHT~\cite{wenbin2019fairness} which is an incremental Hoeffding Tree that does not tackle concept drifts and CSMOTE~\cite{bernardo2020csmote} which is build on top of adaptive random forest equipped with ADWIN to handle concept drifts. An overview follows:

\begin{enumerate}

\item \textbf{Fairness Aware Hoeffding Tree (FAHT)~\cite{wenbin2019fairness}:} FAHT is an extension of the Hoeffding tree for fairness-aware learning that extends the typically employed information gain split attribute selection criterion to also include fairness gain (based on the statistical parity fairness measure). FAHT grows the tree by jointly considering information- and fairness-gain, however, it does not handle concept drifts nor class imbalance.


\item \textbf{Massaging (MS)~\cite{iosifidis2019fairness}:} a chunk-based model-agnostic stream fairness-aware learning approach which minimizes statistical parity on recent discriminatory outcomes. In particular, it detects and mitigates discrimination within the current chunk by performing label swaps, also known as ``massaging''~\cite{kamiran2009classifying} and retrains the model based on the ``corrected" chunk. MS is dealing with concept drifts by blind adaptation (using any adaptive learner), but considers only short-term discrimination outcomes, i.e., within the chunk, and does not account for class imbalance. We use default chunk size of 1,000 instances. 



\item \textbf{Online Smooth Boosting (OSBoost)~\cite{chen2012online}:} OSBoost does not consider fairness nor class imbalance.  


\item \textbf{Continuous SMOTE (CSMOTE)~\cite{bernardo2020csmote}:} CSMOTE does not consider fairness but it tackles class imbalance by re-sampling the minority class from a sliding window. We initialize CSMOTE with its default hyper-parameters. 

\item \textbf{Online Fair Imbalanced Boosting (OFIB):} A variation of FABBOO that does not account for class imbalance i.e., it does not use OCIS during training. This variation helps to show the importance of tackling class imbalance. 

\item \textbf{Chunk Fair Balanced Boosting (CFBB):} A variation of FABBOO that tackles short-term, instead of cumulative, discrimination. This variation helps to show the importance of long term fairness assessment. Instead of accounting for discrimination from the beginning of the stream, it monitors a chunk of 1,000 instances.
\end{enumerate}

 

\noindent{\textbf{Datasets}:
\begin{table*}[t!]
\caption{An overview of the datasets.}
\centering
\begin{adjustbox}{width=1\textwidth,center}
\begin{tabular}{lccccccccc}
\hline
 & \#Instances & \#Attributes & Sen.Attr. & $z$ & $\bar{z}$ & Class ratio (+:-) & Stream & Positive class & Source
 \\ \hline
Adult Cen. & 45,175 & 14 & Gender & Female & Male & 1:3.03 & - & \textless{}50K & \cite{dua2017}\\
Bank & 40,004 & 16 & Marit. Status & Married & Single & 1:7.57 & - & subscription & \cite{dua2017}\\
Compas & 5,278 & 9 & Race & Black & White & 1:1.12 & - & recidivism & \cite{larson2016we} \\
Default & 30,000 & 24 & Gender & Female & Male & 1:3.52 & - & default payment & \cite{dua2017}\\
Kdd Cen. & 299,285 & 41 & Gender & Female & Male & 1:15.11 & - & \textless{}50K & \cite{dua2017}\\
Law Sc. & 18,692 & 12 & Gender & Female & Male & 1:9.18 & - & bar exam & \cite{wightman1998lsac}\\
Loan & 21,443 & 38 & Gender & Female & Male & 1:1.26 & \checkmark & paid &\cite{cortez2019}\\
NYPD & 311,367 & 16 & Gender & Female & Male & 1:3.68 & \checkmark & felony &\cite{birchall2015data}\\
synthetic & 150,236 & 6 & synth. & synth. & synth. & 1:3.13 & \checkmark & synth. &\cite{iosifidis2019fairness}\\
\hline
\end{tabular}
\end{adjustbox}
\label{tbl:datasets}
\end{table*}
To evaluate FABBOO, we employ a variety of real-world as well as synthetic datasets which are summarized in Table~\ref{tbl:datasets}. The datasets vary in terms of class imbalance, dimensionality and volume. 
Same as in~\cite{iosifidis2019fairness,wenbin2019fairness}, we use \textit{Adult census} dataset (Adult) and \textit{Kdd Census} dataset (Kdd Cen.) as well as \textit{Bank} dataset, \textit{Compas} dataset,
\textit{Default} dataset and \textit{Law School (Law Sc.)} dataset by randomly shuffling them, since they are not stream datasets. 
We also employ \textit{Loan}, \textit{NYPD} and a \textit{synthetic} dataset, all of which have temporal characteristics. 
For the synthetic dataset, we follow the authors' initialization process~\cite{iosifidis2019fairness}, where each attribute corresponds to a different Gaussian distribution, and moreover, we inject class imbalance and concept drifts to the stream. Concept drifts in this scenario are implemented by shifting the mean average of each Gaussian distribution (5 non-reoccurring concept drifts have been inserted at random points, see Figure~\ref{fig:overtime_sp} or~\ref{fig:overtime_eqop}). In addition, we have used further synthetic datasets to show the impact of $\mathsf{FABBOO}$'s hyper-parameters (Sec.~\ref{sec:impact_of_L} and~\ref{sec:impact_of_M}). We introduce each of them in the corresponding sections.

\noindent{\textbf{Metrics}:}
To evaluate the performance of FABBOO and competitors, we employ a set of measures which are able to show the performance in the presence of class imbalance. Same as in~\cite{ditzler2012incremental}, we employ \textit{balanced accuracy} (Bal.Acc.), \textit{Gmean}, \textit{Kappa}, and \textit{Recall}. For measuring discrimination, we report on \textit{cumulative statistical parity (Cum.S.P.)} in Sec.~\ref{sec:sp_results} and \textit{cumulative equal opportunity (Cum.EQ.OP.)} in Sec.~\ref{sec:eqop_results}

\subsection{Results on cumulative statistical parity}
\label{sec:sp_results}
\input{statistical_results}

\subsection{Results on cumulative equal opportunity}
\label{sec:eqop_results}
\input{eqop_results}

\vspace{-.8mm}
\subsection{Performance vs execution time: Impact of $N$}
\label{sec:impact_of_t}
\input{impact_of_t}


\subsection{Varying class imbalance: Impact of $\lambda$}
\label{sec:impact_of_L}
\input{impact_of_L}


\subsection{Concept drifts and fair boundary adjustments: Impact of $M$}
\label{sec:impact_of_M}
\input{impact_of_M}





\section{Introduction}
\label{sec:intro}
\input{introduction}

\section{Basic Concepts and Problem Definition}
\label{sec:prelim}
\input{preliminaries}

\section{Related Work}
\label{sec:related}
\input{related}

\section{Online Fairness- and Class Imbalance-aware Boosting}
\label{sec:approach}
\input{approach}

\section{Evaluation}
\label{sec:exp}
\input{experiments}

\section{Conclusion}
\label{sec:conclusion}
\input{conclusions}

 \bibliographystyle{spmpsci}     



