PaperlayerView exact revision on arXiv

Source-linked AI summary

Using Pareto Simulated Annealing to Address Algorithmic Bias in Machine Learning

William Blanzeisky, Pádraig Cunningham

arXiv:2105.15064v1cs.LGcs.CY

TL;DR

Algorithmic bias can stem from training data or from the algorithm, including underestimation associated with underfitting. This paper uses Pareto Simulated Annealing to optimize balanced accuracy and underestimation, reporting near-perfect underestimation with high balanced accuracy on one synthetic and two real datasets.

  • Problem

    Algorithmic underestimation can arise when models underfit because of training-data and model-capacity limitations, while fairness is not explicitly considered in ordinary optimization.

    Source: §2 · p. 2, §4 · p. 3

  • Method

    The framework adapts Pareto Simulated Annealing to optimize balanced accuracy and underestimation as competing objectives.

    Source: §1 · p. 1, §4 · p. 3

  • Results

    The framework achieved near-perfect underestimation while maintaining high balanced accuracy on one synthetic and two real datasets.

    Source: §6 · p. 4

  • Takeaways & Limitations

    On all three datasets, PSA(BA+US) outperformed SA(BA) and SGD(log-loss) in underestimation.

    Source: §5 · p. 4

    PSA is problem-dependent, and selecting appropriate parameters is challenging enough that preliminary experiments are often required.

    Source: §4 · p. 3

Abstract

from arXiv · show

Algorithmic Bias can be due to bias in the training data or issues with the algorithm itself. These algorithmic issues typically relate to problems with model capacity and regularisation. This underestimation bias may arise because the model has been optimised for good generalisation accuracy without any explicit consideration of bias or fairness. In a sense, we should not be surprised that a model might be biased when it hasn't been "asked" not to be. In this paper, we consider including bias (underestimation) as an additional criterion in model training. We present a multi-objective optimisation strategy using Pareto Simulated Annealing that optimise for both balanced accuracy and underestimation. We demonstrate the effectiveness of this strategy on one synthetic and two real-world datasets.

1 INTRODUCTION

Algorithmic bias can originate in training data or in the learning algorithm, while common mitigation approaches formulate fairness and predictive performance as competing objectives. The paper proposes Pareto Simulated Annealing to optimize balanced accuracy and underestimation together.

1 INTRODUCTION

  • Algorithmic bias can arise from biased training data or from the algorithm itself, which may introduce or amplify bias.Data-originating bias is sometimes called negative legacy; algorithm-originating bias is called underestimation.Source: §1 · p. 1
  • Fairness-aware objective-function approaches often create non-convex optimization problems, motivating methods that address non-convexity.Prior approaches include convex proxies, disciplined convex-concave programming, and majorization-minimization.Source: §1 · p. 1
  • The proposed Pareto Simulated Annealing strategy jointly maximizes balanced accuracy and minimizes underestimation of desirable outcomes for the minority group.It seeks a set of Pareto-optimal solutions because accuracy and underestimation can conflict.Source: §1 · p. 1
  • The strategy is assessed on one synthetic and two real-world datasets.The paper places the method after background sections on bias and multi-objective optimization.Source: §1 · p. 1

2 BIAS IN MACHINE LEARNING

The section distinguishes data-originating negative legacy from algorithm-originating underestimation and introduces measures for disparate impact and underestimation. These measures capture different aspects of minority outcomes, and a perfect underestimation score does not guarantee fairness under disparate impact.

2 BIAS IN MACHINE LEARNING

  • Disparate Impact (DI_S) compares the predicted desirable-outcome rate for the sensitive minority with that for the majority, with 0.8 marking the 80% rule.The measure captures subgroup outcome disparity but does not identify the source of bias.Source: §2 · p. 1
  • Negative legacy refers to data-related bias, whereas underestimation is algorithmic bias associated with missing subtle phenomena and underfitting.Underestimation can also involve model-capacity limitations, irreducible error, regularization, and feature or class imbalance.Source: §2 · p. 2
  • The underestimation score (US_S) compares minority desirable outcomes predicted by the classifier with those actually present in the data.US_S below 1 indicates underprediction, while US_S equal to 1 does not rule out disparate impact.Source: §2 · p. 2

3 MULTI-CRITERIA OPTIMIZATION

Multi-criteria optimization addresses competing objectives by seeking non-dominated solutions. Simulated Annealing explores a large search space, and Pareto Simulated Annealing extends it to approximate a set of solutions across multiple objectives.

3 MULTI-CRITERIA OPTIMIZATION

  • A multi-objective optimization problem simultaneously optimizes two or more objective functions, often with no single solution dominating across all criteria.Pareto optimality identifies the set of non-dominated solutions when improving one objective may worsen another.Source: §3 · p. 2

3.1 Simulated Annealing

  • Simulated Annealing searches a large space by sometimes accepting inferior candidate solutions, with that acceptance becoming less likely as temperature falls.The process perturbs a current solution, evaluates candidates over iterations, and cools according to a rate until changes stop being accepted.Source: §3.1 · p. 2

3.2 Pareto Simulated Annealing

  • Pareto Simulated Annealing extends Simulated Annealing to multi-objective problems by initializing a solution set and generating candidates to form an estimated Pareto front [1].It aggregates acceptance probabilities across objectives; normalization may express objective changes as percentage improvements, with a weighted sum.Source: §3.2 · p. 2
  • Prior PSA applications include water-network design, control-cabinet layout, and accuracy-sparsity optimization in non-negative matrix factorization.The passage also notes that multiple PSA variants exist.Source: §3.2 · p. 2

4 MITIGATING UNDERESTIMATION

The section formulates underestimation mitigation as a multi-objective optimization problem for logistic regression, optimizing balanced accuracy and underestimation together. It adapts Pareto Simulated Annealing (PSA) to search for solutions that balance these objectives.

4 MITIGATING UNDERESTIMATION

  • Logistic regression parameters are fitted by minimizing log loss, while the proposed remediation seeks high balanced accuracy and USS = 1.The setup defines the prediction output from dataset features and the sensitive attribute.Source: §4 · pp. 2–3
  • Fairness-unaware optimization can yield biased predictions, while directly adding fairness constraints can produce non-convex loss functions that challenge gradient-based optimizers.The proposed response is a PSA strategy optimizing balanced accuracy and underestimation together.Source: §4 · p. 3
  • Balanced accuracy is the classification-prediction measure used as one of the optimization criteria.The section defines it for predictions against the target labels.Source: §4 · p. 3
  • The implementation uses two initial temperatures because balanced accuracy is bounded in [0, 1], whereas underestimation is unbounded above.The acceptance probability is modified to account for both temperatures.Source: §4 · p. 3
  • PSA initializes a solution set, perturbs one parameter dimension with Gaussian noise, and probabilistically accepts dominated candidates during its search.It cools the temperatures until changes stop, then selects non-dominated solutions as the Pareto set.Source: §4 · p. 3
  • The method directly optimizes fairness objectives and can escape local optima, but it is problem-dependent and parameter selection often requires preliminary experiments.The section also presents the framework in Algorithm 1.Source: §4 · p. 3

5 EXPERIMENTS

Across the three evaluated datasets, PSA achieved better underestimation outcomes than the two comparison methods, while retaining good balanced accuracy. Training-set Pareto fronts also show that perfect underestimation was achievable without much balanced-accuracy loss.

5 EXPERIMENTS

  • The framework was experimentally evaluated on a synthetic dataset, Census Income, and a reduced ProPublica Recidivism dataset, predicting income above or below $50,000 and the recidivism target.Comparisons included PSA (BA+US), logistic regression optimized using SA on balance accuracy, SA(BA), and scikit-learn logistic regression optimized on log-loss, SGD(log-loss).Source: §5 · pp. 3–4
  • The training-set Pareto fronts show competing criteria, yet USS = 1 was achievable without much loss in balance accuracy.Figure 1 presents the Pareto fronts for the three datasets.Source: Figure 1 · p. 4, §5 · p. 4
  • PSA(BA+US) outperformed SA(BA) and SGD(log-loss) in underestimation on all three datasets; the authors report near-perfect underestimation with good balanced accuracy.The models tested had USS = 1 on training data; Figure 2 presents test-set results.Source: Figure 2 · p. 4, §5 · p. 4
  • Table 1 provides summary details for the three datasets used in the experiments.The passage identifies the table's scope but does not provide its dataset values.Source: Table 1 · p. 4

6 CONCLUSION AND FUTURE WORK

The paper concludes that Pareto Simulated Annealing can optimize balanced accuracy and underestimation together, achieving near-perfect underestimation with high balanced accuracy on one synthetic and two real datasets. Future work will evaluate other algorithms and datasets.

6 CONCLUSION AND FUTURE WORK

  • PSA achieved near-perfect underestimation while maintaining high balance accuracy on one synthetic and two real datasets.The authors plan to evaluate the strategy with neural networks, decision trees, and additional datasets.Source: §6 · p. 4

Related papers

Loading 2105.15064v1…