summaries: In this paper, the authors studied bias amplification. They showed in some situations bias is unavoidable; however, there exist some situations in which bias is a consequence of weak features (features with low influence to the classifier and high variance). Therefore, they used some feature selection methods to remove weak features; by removing weak features, they reduced the bias substantially while maintaining accuracy (In many cases they even improved accuracy).  Showing that weak features cause bias is very interesting, especially in their real-world dataset in which they improved bias and accuracy simultaneously.   In this paper the authors identify a specific source of marginal class probability bias that occurs when using logistic regression models. Using synthetic and real datasets they demonstrate this bias and explore characteristics of the data that exacerbate the issue. Finally, they propose two methods for correcting this bias in logistic regression models and neural network models with logistic output layers and evaluate these methods on several benchmark datasets.
abstractText: We study the phenomenon of bias amplification in classifiers, wherein a machine learning model learns to predict classes with a greater disparity than the underlying ground truth. We demonstrate that bias amplification can arise via an inductive bias in gradient descent methods that results in the overestimation of the importance of moderately-predictive “weak” features if insufficient training data is available. This overestimation gives rise to feature-wise bias amplification – a previously unreported form of bias that can be traced back to the features of a trained model. Through analysis and experiments, we show that while some bias cannot be mitigated without sacrificing accuracy, feature-wise bias amplification can be mitigated through targeted feature selection. We present two new feature selection algorithms for mitigating bias amplification in linear models, and show how they can be adapted to convolutional neural networks efficiently. Our experiments on synthetic and real data demonstrate that these algorithms consistently lead to reduced bias without harming accuracy, in some cases eliminating predictive bias altogether while providing modest gains in accuracy.
authors.name: Klas Leino
authors.name: Matt Fredrikson
authors.name: Emily Black
authors.name: Shayak Sen
references.authors: Muhammad Bilal Zafar Isabel Valera Manuel Gomez Rodriguez Krishna P. Gummadi
references.title: Fairness Constraints: Mechanisms for Fair Classification
references.venue: arXiv e-prints, art
references.authors: Tolga Bolukbasi Kai-Wei Chang James Y. Zou Venkatesh Saligrama Adam Kalai
references.title: Man is to computer programmer as woman is to homemaker? debiasing word embeddings
references.venue: CoRR, abs/1607.06520,
references.authors: Mateusz Buda Atsuto Maki Maciej A. Mazurowski
references.title: A systematic study of the class imbalance problem in convolutional neural networks
references.venue: CoRR, abs/1710.05381,
references.authors: Kaylee Burns Lisa Anne Hendricks Trevor Darrell Anna Rohrbach
references.title: Women also snowboard: Overcoming bias in captioning models
references.venue: CoRR, abs/1803.09797,
references.authors: Girish Chandrashekar Ferat Sahin
references.title: A survey on feature selection methods
references.venue: Computers and Electrical Engineering,
references.authors: Nitesh Chawla
references.title: Data mining for imbalanced datasets
references.venue: An overview,
references.authors: Jeffrey Dastin
references.title: Amazon scraps secret ai recruiting tool that showed bias against women, Oct 2018
references.authors: Stuart Geman Elie Bienenstock René Doursat
references.title: Neural networks and the bias/variance dilemma
references.venue: Neural Comput.,
references.authors: S. Gunasekar J. Lee D. Soudry N. Srebro
references.title: Implicit Bias of Gradient Descent on Linear Convolutional Networks
references.authors: Robert D. Hart
references.title: If youre not a white male, artificial intelligences use in healthcare could be dangerous
references.venue: https://goo.gl/Mtgf8B, July
references.authors: Mohammad Havaei Axel Davy David Warde-Farley Antoine Biard Aaron C. Courville Yoshua Bengio Chris Pal Pierre-Marc Jodoin Hugo Larochelle
references.title: Brain tumor segmentation with deep neural networks
references.venue: CoRR, abs/1505.03540,
references.authors: H. He E.A. Garcia
references.title: Learning from imbalanced data
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Been Kim Julie A Shah Finale Doshi-Velez
references.title: Mind the gap: A generative approach to interpretable feature selection and extraction
references.venue: Advances in Neural Information Processing Systems
references.authors: A. Krizhevsky G. Hinton
references.title: Learning multiple layers of features from tiny images
references.venue: Master’s thesis,
references.authors: Klas Leino Linyi Li Shayak Sen Anupam Datta Matt Fredrikson
references.title: Influence-directed explanations for deep convolutional networks. CoRR, abs/1802.03788, 2018
references.venue: URL http: //arxiv.org/abs/1802.03788
references.authors: Jundong Li Kewei Cheng Suhang Wang Fred Morstatter Robert P Trevino Jiliang Tang Huan Liu
references.title: Feature selection: A data perspective
references.venue: arXiv preprint arXiv:1601.07996,
references.authors: Ziwei Liu Ping Luo Xiaogang Wang Xiaoou Tang
references.title: Deep learning face attributes in the wild
references.venue: In Proceedings of International Conference on Computer Vision (ICCV),
references.authors: Marcus A. Maloof
references.title: Learning when data sets are imbalanced and when costs are unequeal and unknown
references.authors: Maciej A. Mazurowski Piotr A. Habas Jacek M. Zurada Joseph Y. Lo Jay A. Baker Georgia D. Tourassi
references.title: Training neural network classifiers for medical decision making: The effects of imbalanced datasets on classification performance
references.venue: Neural Networks,
references.authors: Yi Murphey Hong Guo Lee Feldkamp
references.title: Neural learning from unbalanced data: Special issue: Engineering intelligent systems (guest editor
references.venue: Lszl monostori). 21,
references.authors: Kevin P. Murphy
references.title: Machine Learning: A Probabilistic Perspective
references.authors: Thomas Oommen Laurie Baise Richard Vogel
references.title: Sampling bias and class imbalance in maximum-likelihood logistic regression
references.authors: Jason D.M. Rennie Lawrence Shih Jaime Teevan David R. Karger
references.title: Tackling the poor assumptions of naive bayes text classifiers
references.venue: In Proceedings of the Twentieth International Conference on International Conference on Machine Learning,
references.authors: Karen Simonyan Andrea Vedaldi Andrew Zisserman
references.title: Deep inside convolutional networks: Visualising image classification models and saliency
references.venue: maps. CoRR,
references.authors: D. Soudry E. Hoffer M. Shpigel Nacson S. Gunasekar N. Srebro
references.title: The Implicit Bias of Gradient Descent on Separable Data
references.authors: Pierre Stock Moustapha Cissé
references.title: Convnets and imagenet beyond accuracy: Explanations, bias detection, adversarial examples and model criticism
references.authors: Mukund Sundararajan Ankur Taly Qiqi Yan
references.title: Axiomatic attribution for deep networks
references.venue: CoRR, abs/1703.01365,
references.authors: B.C. Wallace K. Small C.E. Brodley T.A. Trikalinos
references.title: Class imbalance, redux
references.venue: IEEE 11th International Conference on Data Mining,
references.authors: B.C. Wallace K. Small C.E. Brodley T.A. Trikalinos
references.title: Class imbalance, redux
references.venue: IEEE 11th International Conference on Data Mining,
references.authors: Harry Zhang
references.title: The optimality of naive bayes
references.venue: AA, 1(2):3,
references.authors: Jieyu Zhao Tianlu Wang Mark Yatskar Vicente Ordonez Kai-Wei Chang
references.title: Men also like shopping: Reducing gender bias amplification using corpus-level constraints
references.venue: CoRR, abs/1707.09457,
references.authors: Indre Zliobaite
references.title: On the relation between accuracy and fairness in binary classification
references.venue: CoRR, abs/1505.05723,
sections.heading: 1 INTRODUCTION
sections.text: Bias amplification occurs when the distribution over prediction outputs is skewed in comparison to the prior distribution of the prediction target. Aside from being problematic for accuracy, this phenomenon is also potentially concerning as it relates to the fairness of a model’s predictions (Zhao et al., 2017; Burns et al., 2018; Bolukbasi et al., 2016; Stock & Cissé, 2017) as models that learn to overpredict negative outcomes for certain groups may exacerbate stereotypes, prejudices, and disadvantages already reflected in the data (Hart, 2017).
  Several factors can cause bias amplification in practice. The class imbalance problem is a wellstudied scenario where some classes in the data are significantly less likely than others (Wallace et al., 2011a). Classifiers trained to minimize empricial risk are not penalized for ignoring minority classes. However, as we show through analysis and experiments, bias amplification can arise in cases where the class prior is not severely skewed, or even when it is unbiased. Thus, techniques for dealing with class imbalance alone cannot explain or address all cases of bias amplification.
  We examine bias amplification in the context of binary classifiers, and show that it can be decomposed into a component that is intrinsic to the model, and one that arises from the inductive bias of gradient descent on certain feature configurations. The intrinsic case manifests when the class prior distribution is more informative for prediction than the features, causing the the model to predict the class mode. This type of bias is unavoidable, as we show that any mitigation of it will lead to less accurate predictions (Section 3.1).
  Interestingly, linear classifiers trained with gradient descent tend to overestimate the importance of moderately-predictive, or “weak,” features if insufficient training data is available (Section 3.2). This overestimation gives rise to feature-wise bias amplification – a previously unreported form of bias (see Section 2 for comparison to related work) that can be traced back to the features of a trained model. It occurs when there are more features that positively correlate with one class than the other. If these features are given undue importance in the model, then their combined influence will lead to bias amplification in favor of the corresponding class.
  A concrete example of this would be predicting gender from face images. Suppose that there are several features that occur slightly more often with women (i.e. are weakly correlated with women) – long hair, eyeliner, purses, smiling, necklaces – but only a few that are more correlated with
  men – necktie, mustache. Then, our analysis suggests a model would exhibit feature-wise bias amplification towards female prediction, because there are more weak features oriented towards that class. In fact, we experimentally demonstrate that feature-wise bias amplification can happen even when the class prior is unbiased; e.g., even if the aforementioned hypothetical classification problem contained an equal number of male and female training instances.
  Our analysis sheds new light on real instances of the problem, and paves the way for practical mitigations of it. The existence of such moderately-predictive weak features is not uncommon in models trained on real data. Viewing deep networks as the composition of a feature extractor and a linear classifier, we explain some instances of bias amplification in deep networks (Table 1, Section 5).
  Finally, this understanding of feature-wise bias amplification motivates a solution based on feature selection. We develop two new feature-selection algorithms that are designed to mitigate bias amplification (Section 4). We demonstrate their effectiveness on both linear classifiers and deep neural networks (Section 5). For example, for a VGG16 network trained on CelebA (Liu et al., 2015) to predict the “attractive” label, our approach removed 95% of the bias in predictions. We observe that in addition to mitigating bias amplification, these feature selection methods reduce generalization error relative to an `1 regularization baseline for both linear models and deep networks (Table 1).
sections.heading: 2 RELATED WORK
sections.text: While the term bias is used in a number of different contexts in machine learning, we use bias amplification in the sense of Zhao et al. (2017), where the distribution over prediction outputs is skewed in comparison to the prior distribution of the prediction target. For example, Zhao et al. (2017) and Burns et al. (2018) use the imSitu vSRL dataset for the MS-COCO task, i.e. to classify agents and actions in pictures. In the dataset, women are twice as likely to be the agent when the action is cooking, but the model was five times as likely to predict women to be the agent cooking.
  In a related example, Stock & Cissé (2017) identify bias in models trained on the ImageNet dataset. Despite there being near-parity of white and black people in pictures in the basketball class, 78% of the images that the model classified as basketball had black people in them and only 44% had white people in them. Additionally, 90% of the misclassified basketball pictures had white people in them, whereas only 20% had black people in them. Note that this type of bias over classes is distinct from the learning bias in machine learning (Geman et al., 1992) which has received renewed interest in the context of SGD and under-determined models (Gunasekar et al., 2018; Soudry et al., 2017).
  Naturally, bias has been studied in the context of fairness, and in particular in cases where preexisting societal biases are propagated by a model’s predictions. One recent example of this is Amazons gender-biased recruiting tool, which learned not to prefer candidates from all-female colleges based on past hiring data(Dastin, 2018). Removing such biases from models’ behavior altogether using fairness criteria (Bilal Zafar et al., 2015; Binns, 2018; Zliobaite, 2015) requires deviating from patterns in the data, and may conflict with accuracy. However, bias can also come as a product of the model itself: a model could ostensibly take a relatively unbiased dataset and erroneously make more biased predictions due to some limitations of learning. Feature-wise bias falls into this class, as it is created by the mechanics of the learning rule itself rather than stemming from the data. This means that removing feature-wise bias would make the model more faithful to the data it was given, generally increasing accuracy. Consequently, this paper does not weigh in on which fairness guidelines to use in navigating the bias-accuracy tradeoff, since it does not apply to the type of bias we present.
  Bias amplification is often thought to be result of class imbalance in the training data, which is wellstudied in the learning community (see He & Garcia (2009) and Buda et al. (2017) for comprehensive surveys). There are a myriad of empirical investigations of the effects of class imbalance in machine learning and different ways of mitigating these effects (Maloof, 2003; Chawla, 2005; Mazurowski et al., 2008; Oommen et al., 2011; Wallace et al., 2011b).
  It has been shown that neural networks are affected by class imbalance as well (Murphey et al., 2004). Buda et al. (2017) point out that the detrimental effect of class imbalance on neural networks increases with scale. They advocate for an oversampling technique mixed with thresholding to improve accuracy based on empirical tests. An interesting and less common technique from Havaei et al. (2015) relies on a drastic change to neural network training procedure in order to better detect
  brain tumors: they first train the net on an even distribution, and then on a representative sample, but only on the output layer in the second half of training.
  In contrast to prior work, we demonstrate that bias amplification can occur without existing imbalances in the training set. Therefore, we identify a new source of bias that can be traced to particular features in the model. Since we remove bias feature-wise, our approach can also be viewed as method for feature selection. While feature selection is a well-studied problem, to the authors’ knowledge, no one has looked at removing features to mitigate bias. Generally, feature selection has been applied for improving model accuracy, or gaining insight into the data (Chandrashekar & Sahin, 2014). For example, Kim et al. (2015) use feature selection for interpretability during data exploration. They select features that have high variance across clusters created based on humaninterpretable, logical rules. Differing from prior work, we focus on bias by identifying features that are likely to increase bias, but can be removed while maintaining accuracy.
  Naive Bayes classification models comprise a similarly well-studied topic. Rennie et al. (2003) point out common downfalls of Naive Bayes classifiers on datasets that do not meet Naive Bayes criteria: bias from class imbalance, and the problem of over-predicting classes with correlated features. Our work shows that similar effects can occur even on data that does match Naive Bayes assumptions. Zhang (2004) shows that the naive Bayes classifier is optimal so long as the dependencies between features over the whole network cancel each other out. Our work can mitigate bias in scenarios where these conditions do not hold.
sections.heading: 3 BIAS AMPLIFICATION IN BINARY CLASSIFIERS
sections.text: In this section, we define bias amplification for binary classifiers, and show that in some cases it may be unavoidable. Namely, a Bayes-optimal classifier trained on poorly-separated data can end up predicting one label nearly always, even if the prior label bias is minimal. While our analysis makes strong generative assumptions, we show that its results hold qualitatively on real data that resemble these assumptions. We begin by formalizing the setting.
  We consider the standard binary classification problem of predicting a label y ∈ {0, 1} given features x = (x1, . . . , xd) ∈ X . We assume that data are generated from some unknown distribution D, and that the prior probability of y = 1 is p∗. Without loss of generality, we assume that p∗ ≥ 1/2. The learning algorithm recieves a training set S drawn i.i.d. from Dn and outputs a predictor hS : X → {0, 1} with the goal of minimizing 0-1 loss on unknown future i.i.d. samples from D.
  Definition 1 (Bias amplification, systematic bias) Let hS be a binary classifier trained on S ∼ Dn. The bias amplification of hS on D, written BD(hS), is given by Equation 1.
  BD(hS) = E (x,y)∼D [hS(x)− y] (1)
  We say that a learning rule exhibits systematic bias whenever it exhibits non-zero bias amplification on average over training samples, i.e. it satisfies Equation 2.
  E S∼Dn [BD(hS)] 6= 0 (2)
  Definition 1 formalizes bias amplification and systematic bias in this setting. Intuitively, bias amplification corresponds to be the probability that hS predicts class 1 on instances from class 0 in excess of the prior p∗. Systematic bias lifts the definition to learners, characterizing rules that are expected to amplify bias on training sets drawn from D.
sections.heading: 3.1 SYSTEMATIC BIAS IN BAYES-OPTIMAL PREDICTORS
sections.text: Definition 1 makes it clear that systematic bias is a property of the learning rule producing hS and the distribution, so any technique that aims to address it will need to change one or both. However, if the learner always produces Bayes-optimal predictors for D, then any such change will result in suboptimal classifiers, making bias amplification unavoidable. In this section we characterize the systematic bias of a family of linear Bayes-optimal predictors.
  Consider a special case of binary classification in which x are drawn from a multivariate Gaussian distribution with class means µ∗0,µ ∗ 1 ∈ Rd and diagonal covariance matrix Σ∗, and y is a Bernoulli
  random variable with parameter p∗. Then D is given by Equation 3.
  D , Pr[x|y] = N (x|µ∗y,Σ∗), y ∼ Bernoulli(p∗) (3)
  Because the features in x are independent given the class label, the Bayes-optimal learning rule for this data is Gaussian Naive Bayes, which is expressible as a linear classifier (Murphy, 2012).
  Making the ideal assumption that we are always able to learn the Bayes-optimal classifier h∗ for parameters µ∗y,Σ
  ∗, p∗, we proceed with the question: does h∗ have systematic bias? Our assumption of hS = h∗ reduces this question to whether BD(h∗) is zero. Proposition 1 shows that BD(h∗) is strictly a function of the class prior p∗ and the Mahalanobis distance D of the class means µ∗y . Corollary 1 shows that when the prior is unbiased, the model’s predictions remain unbiased.
  Proposition 1 Let x be distributed according to Equation 3, y be Bernoulli with parameter p∗, D be the Mahalanobis distance between the class means µ∗0,µ ∗ 1, and β = −D−1 log(p∗/(1 − p∗)). Then the bias amplification of the Bayes-optimal classifier h∗ is:
  BD(h ∗) = 1− p∗ − (1− p∗)Φ ( β + D2 ) − p∗Φ ( β − D2 ) Corollary 1 When x is distributed according to Equation 3 and p∗ = 1/2, BD(h∗) = 0.
  The proofs of both claims are given in the appendix. Corollary 1 is due to the fact that when p∗ = 1/2, β = 0. Because of the symmetry Φ(−x) = 1 − Φ(x), the Φ terms cancel out giving Pr[h∗(x) = 1] = 1/2, and thus the bias amplification BD(h∗) = 0.
  Figure 1a shows the effect on real data available on the UCI repository classified using Gaussian Naive Bayes (GNB). These datasets were chosen because their distributions roughly correspond to the naive Bayes assumption of conditional feature independence, and GNB outperformed logistic regression. In each case, bias amplification occurs in approximate correspondence with Proposition 1, tracking the empirical class prior and class distance to Figure 1b.
  Figure 1b shows BD(h∗) as a function of p∗ for several values of D. As the means grow closer together, there is less information available to make reliable predictions, and the label prior is used as the more informative signal. Note that BD(h∗) is bounded by 1/2, and the critical point corresponds to bias “saturation” where the model always predicts class 1. From this it becomes clear that the extent to which overprediction occurs grows rather quickly when the means are moderately close. For example when p∗ = 3/4 and the class means are separated by distance 1/2, the classifier will predict Y = 1 with probability close to 1.
  Summary: Bias amplification may be unavoidable when the learning rule is a good fit for the data, but the features are less effective at distinguishing between classes than the prior. Our results show that in the particular case of conditionally-independent Gaussian data, the Bayes-optimal predictor suffers from bias as the Mahalanobis distance between class means decreases, leading to a noticeable increase even when the prior is only somewhat biased. The effect is strong enough to manifest in real settings where generative assumptions do not hold, but GNB outperforms other linear classifiers.
sections.heading: 3.2 FEATURE ASYMMETRY AND GRADIENT DESCENT
sections.text: When the learning rule does not produce a Bayes-optimal predictor, it may be the case that excess bias can safely be removed without harming accuracy. To support this claim, we turn our attention to logistic regression classifiers trained using stochastic gradient descent. Logistic regression predictors for data generated according to Equation 3 converge in the limit to the same Bayes-optimal predictors studied in Proposition 1 and Corollary 1 (Murphy, 2012).
  Logistic regression models make fewer assumptions about the data and are therefore more widelyapplicable, but as we demonstrate in this section, this flexibility comes at the expense of an inductive bias that can lead to systematic bias in predictions. To show this, we continue under our assumption that x and y are generated according to Equation 3, and consider the case where p∗ = 1/2. According to Corollary 1, any systematic bias that emerges must come from differences between the trained classifier hS and the Bayes-optimal h∗.
sections.heading: 3.2.1 FEATURE ASYMMETRY
sections.text: To define what is meant by “feature asymmetry”, consider the orientation of each feature xj as given by the sign of µ1j−µ0j . The sign of each coefficient in h∗ will correspond to its feature orientation, so we can think of each feature as being “towards” either class 0 or class 1. Likewise, we can view the combined features as being asymmetric towards y when there are more features oriented towards y than towards 1− y. As shown in Table 1 (Section 5), high-dimensional data with biased class priors often exhibit feature asymmetry towards the majority class. This does not necessarily lead to excessive bias, and the analysis from the previous section indicates that if p∗ = 1/2 then it may be possible to learn a predictor with no bias. However, if the learning rule overestimates the importance of some of the features oriented towards the majority class, then variance in those features present in minority instances will cause mispredictions that lead to excess bias beyond what is characterized in Proposition 1.
  This problem is pronounced when many of the majority-oriented features are weak predictors, which in this setting means that the magnitude of their corresponding coefficients in h∗ are small relative to the other features (for example, features with high variance or similar means between classes). The weak features have small coefficients in h∗, but if the learner systematically overestimates the corresponding coefficients in hS , the resulting classifier will be “out of balance” with the distribution generating the data.
  Figure 2 explores this phenomenon through synthetic Gaussian data exemplifying this feature asymmetry, in which the strongly-predictive features have low variance σs = 1, and the weakly-predictive features have relatively higher variance σw > 1. Specifically, the data used here follows Equation 3 with the parameters shown in Equation 4.
  p∗ = 1/2,µ∗0 = (0, 1, 0, . . . , 0),µ ∗ 1 = (1, 0, 1, . . . , 1),Σ ∗ = diag(σs, σs, σw, . . . , σw) (4)
  Figure 2c suggests that overestimation of weak features is precisely the form of inductive bias exhibited by gradient descent when learning logistic classifiers. As hS converges to the Bayes-optimal configuration, the magnitude of weak-feature coefficients gradually decreases to the appropriate quantity. As the variance increases, the extent of the overapproximation grows accordingly.
  While this effect may arise when methods other than SGD are used to estimate the coefficients, Figure 3 shows that it occurs consistently in models trained using SGD. In particular, we discovered the same bias amplification effect in the asymmetric feature setting when using SGD on multiple different loss functions. This suggests that this effect is brought about by SGD, and not the logistic loss in particular. Furthermore, our results in Table 1 (Section 5) reveal that feature-wise bias amplification can occur in deep models, i.e., the phenomenon is not limited to linear models.
sections.heading: 3.2.2 PREDICTION BIAS FROM INDUCTIVE BIAS
sections.text: While the classifier remains far from convergence, the cumulative effect of feature overapproximation with high-dimensional data leads to systematic bias. Figure 2a demonstrates that as the disparity in weak features towards class y = 1 increases, so does the expected bias towards that class. This bias cannot be explained by Proposition 1, because this data is distributed with p∗ = 1/2. Rather, it is clear that the effect diminishes as the training size increases and hS converges towards h∗. This suggests gradient descent tends to “overuse” the weak features prior to convergence, leading to systematic bias that over-predicts the majority class in asymmetric regimes.
  Figure 2b demonstrates that for a fixed disparity in weak features, the features must be sufficiently weak in order to cause bias. This suggests that a feature imbalance alone is not sufficient for causing systematic bias. Moreover, the weak features, rather than the strong features, are responsible for the bias. As the training size increases, the amount of variance required to cause bias increases. However, when the features have sufficiently high variance, the model will eventually decrease their contribution, relieving their impact on the bias and accuracy of the model.
  Summary: When the data is distributed asymmetrically with respect to features’ orientation towards a class, gradient descent may lead to systematic bias especially when many of the asymmetric features are weak predictors. This bias is a result of the learning rule, as it manifests in cases where a Bayes-optimal predictor would exhibit no bias, and therefore it may be possible to mitigate it without harming accuracy.
sections.heading: 4 MITIGATING FEATURE-WISE BIAS AMPLIFICATION
sections.text: While Theorem 1 suggests that some bias is unavoidable, the empirical analysis in the previous section shows that some systematic bias may not be. Our analysis also suggests an approach for removing such bias, namely by identifying and removing the weak features that are systematically overestimated by gradient descent. In this section, we describe two approaches for accomplishing this that are based on measuring the influence (Leino et al., 2018) of features on trained models. In Section 5, we show that these methods are effective at mitigating bias without harming accuracy on both logistic predictors and deep networks.
sections.heading: 4.1 INFLUENCE-DIRECTED FEATURE REMOVAL
sections.text: Given a model h : X0 → R and feature, xj , the influence χj of xj on h is a quantitative measure of feature j’s contribution to the output of h. To extend this notion to internal layers of a deep network h, we consider the slice abstraction (Leino et al., 2018) comprised of a pair of functions f : X0 → X , and g : X → R, such that h = g ◦ f . We define f to be the network up to the penultimate layer, and g be the final layer. Intuitively, We can then think of the features as being precomputed by f , i.e., x = f(x0) for x0 ∈ X0, allowing us to treat the final layer as a linear model acting on features computed via a deep network. Note that the slice abstraction encompasses linear models as well, by defining f to be the identity function.
  A growing body of work on influence measures (Simonyan et al., 2013; Sundararajan et al., 2017; Leino et al., 2018) provides numerous choices for χj , each with different tradeoffs. We use the internal distributional influence (Leino et al., 2018), as it incorporates the slice abstraction naturally. This measure is given by Equation 5 for a distribution of interest P , which characterizes the distribution of test instances.
  χj(g ◦ f, P ) = ∫
  x∈X0
  ∂g
  ∂f(x)j ∣∣∣∣∣ f(x) P (x)dx (5)
  We now describe two techniques that use this measure to remove features causing bias.
  Feature parity. Motivated by the fact that bias amplification may be caused by feature asymmetry, we can attempt to mitigate it by enforcing parity in features across the classes. To avoid removing features that are useful for correct predictions, we order the features by their influence on the model’s output, and remove features from the majority class until parity is reached. If the model has a bias term, we adjust it by subtracting the product of each removed coefficient and the mean of its corresponding feature.
  Experts Section 3.2 identifies “weak” features as a likely source of systematic bias. This is a somewhat artificial construct, as real data often does not exhibit a clear separation between strong and weak features. Qualitatively, the weak features are less predictive than the strong features, and the learner accounts for this by giving less influence to the weak features. Thus, we can think of imposing a strong/weak feature dichotomy by defining the weak features to be those such that |χj | < χ∗ for some threshold χ∗. This reduces the feature selection problem to a search for an appropriate χ∗ that mitigates bias to the greatest extent without harming accuracy.
  We parameterize this search problem in terms of α, β, where the α features with the most positive influence and β features with the most negative influence are “strong”, and the rest are considered weak. This amounts to selecting the class-wise expert (Leino et al., 2018) for the dominant class. Formally, let Fα be the set of α features with the α highest positive influences, and Fβ the set of β features with the β most negative influences. For slice h = g ◦ f , let gαβ be defined as model g with its weights replaced by wαβ as defined by Equation 6. Then we define expert, g α∗
  β∗ , to be the classifier given by setting α∗ and β∗ according to Equation 7. In other words, the α and β that minimize bias while maintaining at least the original model’s accuracy. Here LS represents the 0-1 loss on the training set, S.
  wαβ j = { wj j ∈ Fα ∪ Fβ 0 j /∈ Fα ∪ Fβ
  (6)
  α∗, β∗ = argmin α,β
  ∣∣BD(gαβ )∣∣ subject to LS(gαβ ) ≤ LS(g) (7)
  We note that this is always feasible by selecting all the features. Furthermore, this is a discrete optimization problem, which can be solved efficiently with a grid search over the possible α and β. In practice, even when there are many features, we can exhaustively search this space. When there are ties we can break them by preferring the model with the greatest accuracy.
sections.heading: 5 EXPERIMENTS
sections.text: In this section we present empirical evidence to support our claim that feature-wise bias amplification can safely be removed without harming the accuracy of the classifier. We show this on both logistic predictors and deep networks by measuring the bias on several benchmark datasets, and running the parity and expert mitigation approaches described in Section 4. As a baseline, we compare against `1 regularization in the logistic classifier experiments.
  The results are shown in Table 1. To summarize, on every dataset we consider, at least one of the methods in Section 4 proves effective at reducing the classifier’s bias amplification. `1 regularization removes bias less reliably, and never to the extent that our methods do. In all but two cases, the influence-directed experts show the best performance in terms of bias removal, and this method is able to reduce bias in all but one case. In terms of accuracy, our methods consistently improve classifier performance, and in some cases significantly. For example, on the prostate dataset, influence-directed experts removed 80% of the prediction bias while improving accuracy from 57.7% to 90.2%.
  Data. We performed experiments over eight binary classification datasets from various domains (rows 3-11 in Table 1) and two image classification datasets (CIFAR10-binary, CelebA). Table 2 in the Appendix details the number of features and instances for each dataset. Our criteria for selecting logistic regression datasets were: high feature dimensionality, binary labels, and row-structured instances (i.e., not time series data). Among the logistic regression datasets, arcene, colon, glioma, pc/mac, prostate, smokers were obtained from the scikit-feature repository (Li et al., 2016), and micromass was obtained from the UCI repository (Dheeru & Karra Taniskidou, 2017). The synthetic dataset was generated in the manner described in Section 3.2, containing one strongly-predictive feature (σ2 = 1) for each class, 1,000 weak features (σ2 = 3), and p∗ = 1/2.
  For the deep network experiments, we created a binary classification problem from CIFAR10 (Krizhevsky & Hinton, 2009) from the “bird” and “frog” classes. We selected these classes as they showed the greatest posterior disparity on VGG16 network trained on the original dataset. For CelebA, we trained a VGG16 network with one fully-connected layer of 4096 units to predict the attractiveness label given in the training data.
  Methodology. For the logistic regression experiments, we used scikit-learn’s SGDClassifier estimator to train each model using the logistic loss function. Logistic regression measurements were obtained by averaging over 20 pseudorandom training runs on a randomly-selected stratified train/test split. Experiments involving experts selected α, β using grid search over the possible values that minimize bias subject to not harming accuracy as described in Section 4. Similarly, experiments involving `1 regularization use a grid search to select the regularization paramter, optimizing for the same criteria used to select α, β. Experiments on deep networks use the training/test split provided by the respective dataset authors. Models were trained until convergence using Keras 2 with the Theano backend.
  Logistic regression. Table 1 shows that on linear models, feature parity always improves or maintains the model in terms of both bias amplification and accuracy. Notably, in each case where feature parity removes bias, the accuracy is likewise improved, supporting our claim that bias resulting from asymmetric feature regimes is avoidable. In most cases, the benefit from applying feature parity is, however, rather small. arcene is the exception, which is likely due to the fact that it has large feature asymmetry in the original model, leaving ample opportunity for improvement by this approach.
  The results suggest that influence-directed experts are the most effective mitigation technique, both in terms of bias removal and accuracy improvement. In most datasets, this approach reduced bias while improving accuracy, often substantially. Most notably on the prostate dataset, where the original model failed to achieve accuracy appreciably greater than chance and extreme bias. The mitigation achieves 90% accuracy while removing 80% of the bias, improving the model significantly. Similarly, for arcene and smokers, this approach removed over 50% of the prediction bias while improving accuracy 5-11%.
  `1 regularization proved least reliable at removing bias subject to not harming accuracy. In many cases, it was unable to remove much bias (glioma, micromass, PC/Mac). On synthetic data `1 gave the best bias reduction. Though it did perform admirably on several real datasets (arcene, prostate, smokers), even removing up to 40% of the bias on the prostate dataset, it was consistently outperformed by either the parity or expert method. Additionally, on the colon dataset, it made bias significantly worse (150%) for gains in accuracy.
  Deep networks. The results show that deep networks tend to have a less significant feature asymmetry than data used for logistic models, which we would expect to render the feature parity approach less effective. The results confirm this, although on CIFAR10 parity had some effect on bias and a proportional positive effect on accuracy. Influence-directed experts, on the other hand, continued to perform well for the deep models. While this approach generally had a greater effect on accuracy than bias for the linear models, this trend reversed for deep networks, where the decrease in bias was consistently greater than the increase in accuracy. For example, the 7.7% bias in the original CelebA model was reduced by approximately 98% to 0.2%, effectively eliminating it from the model’s predictions. The overall effect on accuracy remained modest (0.3% improvement).
  These results on deep networks are somewhat surprising, considering that the techniques described in Section 4 were motivated by observations concerning simple linear classifiers. While the improvements in accuracy are not as significant as those seen on linear classifiers, they align with our expectations regarding bias reduction. This suggests that future work might improve on these results by adapting the approach described in this paper to better suit deep networks.
  Acknowledgments This work was developed with the support of the National Science Foundation under Grant No. CNS-1704845, and the Air Force Research Laboratory under agreement number FA8750-15-2-0277. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright notation thereon. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Air Force Research Laboratory, the National Science Foundation, or the U.S. Government.
sections.heading: A PROOFS
sections.text: Proposition 1 Let x be distributed according to Equation 3, y be Bernoulli with parameter p∗, D be the Mahalanobis distance between the class means µ∗0,µ ∗ 1, and β = −D−1 log(p∗/(1 − p∗)). Then the bias amplification of the Bayes-optimal classifier h∗ is:
  BD(h ∗) = 1− p∗ − (1− p∗)Φ ( β + D
  2
  ) − p∗Φ ( β − D
  2 ) Proof. Note that the Bayes-optimal classifier can be expressed as a linear weighted sum (Murphy, 2012) in terms of parameters ŵ, b̂ as shown in Equation 8.
  Pr[Y = 1|X = x] = (1 + exp−(ŵTx + b̂))−1 (8) ŵ = Σ̂−1(µ̂1 − µ̂0)
  b̂ = −1 2 (µ̂1 − µ̂0)T Σ̂−1(µ̂1 + µ̂0) + log p̂∗ 1− p̂∗
  The random variable wTX is a univariate Gaussian with variance wTΣw and mean wTµy when Y = y. Then the quantity we are interested in is shown in Equation 9, where Φ is the CDF of the standard normal distribution.
  Pr [ wTX > −b ∣∣Y = y] = 1− Φ(−b−wTµy√ wTΣw ) (9)
  Notice that the quantity
  wT (µ1 − µ0) = (µ1 − µ0)TΣ−1(µ1 − µ0)
  is the square of the Mahalanobis distance between the class means.
  −b−wTµ0 = 1
  2 wT (µ1 − µ0)− log
  p∗
  1− p∗
  = D2 2 − log p
  ∗
  1− p∗
  −b−wTµ1 = − 1
  2 wT (µ1 − µ0)− log
  p∗
  1− p∗
  = −D 2 2 − log p
  ∗
  1− p∗
  Similarly, we can rewrite the standard deviation of wTX exactly as D. Rewriting the numerator in the Φ term of (9),
  (wTΣw) 1 2 = ( (µ1 − µ0)TΣ−1ΣΣ−1(µ1 − µ0) ) 1 2
  = ( (µ1 − µ0)TΣ−1(µ1 − µ0) ) 1 2
  = D Then we can write Pr [ wTX > −b ] as:
  (1− p∗) ( 1− Φ ( β + D
  2
  )) + p∗ ( 1− Φ ( β − D
  2 )) =1− (1− p∗)Φ ( β + D
  2
  ) − p∗Φ ( β − D
  2
  )
  Corollary 1 When x is distributed according to Equation 3 and p∗ = 1/2, BD(h∗) = 0.
  Proof. Note that because p∗ = 1/2, the term β = 0 in Theorem 1. Using the main result of the theorem, we have:
  Pr [ wTX > −b ] =1− 1
  2
  [ Φ ( D
  2
  ) + Φ ( −D
  2 )] =1− 1
  2
  [ Φ ( D
  2
  ) + ( 1− Φ ( D
  2 ))] = 1
  2
  The third equality holds because Φ has rotational symmetry about (0, 1/2), giving the identity Φ(−x) = 1− Φ(x).
title: FEATURE-WISE BIAS AMPLIFICATION