While language models (LMs) offer significant capability in zero-shot reasoning tasks across a wide range of domains, they do not perform satisfactorily in problems which requires multi-step reasoning. Previous approaches to mitigate this involves breaking a larger, multi-step task into sub-tasks and asking the language model to generate proposals (“thoughts”) for each sub-task and using exhaustive planning approaches such as DFS to compose a solution. In this work, we leverage this idea to introduce two new contributions: first, we formalize a planning-based approach to perform multi-step problem solving with LMs via Partially Observable Markov Decision Processes (POMDPs), with the LM's own reflections about the value of a state used as a search heuristic; second, leveraging the online POMDP solver POMCP, we demonstrate a superior success rate of $89.4\%$ on the Game of 24 task as compared to existing approaches while also offering better anytime performance characteristics than fixed tree-search which is used previously. Taken together, these contributions allow modern LMs to decompose and solve larger-scale reasoning tasks more effectively.

§ INTRODUCTION

Recent advances of language models (LMs) introduced the possibility of in-context, few or zero-shot reasoning (<cit.>) using LMs without much or any fine tuning.

Yet, classically, LM decoding takes place in a left-to-right fashion, auto-regressively resolving one token at a time by sampling from the output distribution of possible next words without multi-step planning.

Work in LM agents have taken steps to solve more complex problems that would typically require multi-step reasoning even while using this direct decoding approach. The simplest idea, named "chain-of-thoughts" (CoT), involves forcing the LM at decode time to begin the decoding process with natural language reasoning about its actions (<cit.>). The method has contributed to the creation of powerful language agents (<cit.>) that can reason about complex actions.

Despite the relative success of CoT, the scheme still does not support any kind of backtracking as it samples directly from the LM's posterior distribution. When a problem requires a significantly large number of steps to solve, issues relating to "de-generation" (<cit.>) becomes increasingly prevalent: whereby, naive maximizations of sequence likelihood results in a most likely sub-phrase being repeated which does not contribute to increased information or progress on a problem.

Recent theoretical work suggests these types of degeneration arises due to the distortion of output probability density caused by the last-layer softmax projection into the probability simplex (<cit.>): due the lower degrees of freedom offered by a probability syntax, both high and low tails of the latent next-word distribution becomes emphasized in the output probability distribution.

To address this, recent approaches such as Tree of Thoughts (ToT) (<cit.>) have separated the process of next-step proposal ("thinking") and choosing the actual step to take given a situation ("reasoning"). This separate allows the representation of a problem through only short decoding sequences that are less prone to degeneration, while allowing a separate LM call to score the value of being at any given partial solution through a maximum-likely single-token output that is less likely to be distorted.

In this work, we extend the ToT prompting scheme to formalize this process of "thinking" and "reasoning" via a language model as a Partially Observable Markov Decision Process (POMDP). We call this decoding scheme the Plan of Thoughts (PoT).

The key underlying assumption of the proposed PoT scheme involves the claim that LMs are able to make judgments about the value of a subsequence towards solving a problem by analyzing the likelihood of a particular sequence against a judgment of value. This assumption is supported by the existence of reinforcement learning formulations of LM-on-LM output verification—both for reasoning (<cit.>) and hallucination (<cit.>)–as well as the use of LM-inferred state value heuristics in the ToT approach.

We leverage this assumption by, similar to ToT, using the LM's evaluation of the likelihood of a sequence (similar to LM "scoring" of a "thought" in ToT) as a heuristic for the coherence and reasoning within a subsequence of LM output—forming a "self reflection" scheme similar to other LM-scoring schemes previously proposed (<cit.>). Yet, differing from ToT, we explicitly formulate this scoring by an LM as an "observation" of an unobservable underlying latent understanding of the input sequence.

By solving the PoT problem with the anytime POMCP solver (<cit.>), we further demonstrate that PoT exhibits stronger anytime characteristics on the Game of 24 task as compared to ToT while maintaining performance that is comparable to ToT and superior to CoT. We were able to obtain these results at lower costs to ToT evaluations by using a hybrid language modeling approach by using a larger language model, GPT-4 (<cit.>), for posterior sampling and evaluation while using a smaller language model, GPT-3.5-Turbo-Instruct (<cit.>), as the "thought" generator.

§ TREE OF THOUGHTS

We provide here a short summary of the Tree of Thoughts (ToT) (<cit.>) approach which we improve upon in our work. ToT offers a scheme to enable multi-step reasoning with LMs by presenting a decomposition of multi-step LM reasoning into individual steps which is then combined through classic approaches in search and planning.

Specifically, ToT represents a given problem as a finite-horizon planning problem which it then solves in four broad steps.

Thought Decomposition: by leveraging problem-specific characteristics, each problem is decomposed into distinct, incremental steps towards a solution. For the "Game of 24" task, for instance, each "thought" is considered a line of equation which contributes to the overall task of combining four numbers to reach 24.

Now, let \(p_{\theta}\) be our language model, \(s_{j}^{(i)}\) be thought candidate \(j\) of step \(i\) of a decomposed problem, \(s_{*}^{(i)}\) the optimal thought to continue from at step \(i\), \(\tau_{ *} = \qty[s^{(1)}_{ *}, ..., s^{(n)}_{ *}]\) a "solution" to a given problem.

Thought Generation: multiple, initial short decodings of a LM—sampling from \(s' \sim p_{\theta}^{thought}\qty(s^{(i+1)} | s^{(i)})\) is obtained which forms a series of next states ("thoughts") which encodes a partial step towards the solution which is reachable at any given state.

Thought Evaluation: another LM call rates each of the possible next states for their chance in reaching the solution; specifically, we ask the LM to reason about a given state by calculating the posterior probabilities of predicting a specific judgement of value (the words "sure""likely""impossible") given that state; that is: \(V(s_{j}) = \arg\max_{o} \{p^{value}_\theta(o|s_{j}), o \in \{ sure, likely, impossible\}, \forall j \in 1 ... n\).

Problem Solving: finally, given this heuristic, solving a specific problem in ToT involves using a search-and-planning scheme (specifically, DFS or BFS) to cycle between generation and evaluation of thoughts until a terminal thought is reached. Branches on the DFS tree is pruned if they are voted as "impossible".

By combining explicit planning and LM reasoning, this approach achieved state-of-the-art results on the Game of 24 and other difficult natural-language tasks such as a crossword. However, the ToT approach does not incorporate any form of heuristic-guided preferential planning between different "possible" states—in contrast to dynamic approaches which preferentially explore sequences of high probability of success.

§ METHODS

§.§ Problem Formulation

Our work formalizes and augments the stepwise decoding scheme proposed by ToT as a Partially Observable Markov Decision Process (POMDP) (<cit.>). A POMDP is a search and planning formulation which emphasizes the uncertain nature of intermediate steps by formalizing each problem into a tuple \((\mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{T}, \mathcal{R}, \gamma, s_0)\).

We specifically define our problem formulation as follows:

* \(\mathcal{S} = S \times U\), where \(s \in S\) is each sub-step of our decomposed problem and \(u \in U\) representing the unmeasurable, true underlying value being estimated by \(V(s)\) in ToT representing the usefulness of a particular thought

* \(\mathcal{A} = [a_0, a_1, a_2]\), a discrete set of possible problem-solving actions—to "continue" expanding a particular branch \(a_0\), to "rollback" to previous branch \(a_1\), or to "think" a new thought at the current branch \(a_2\).

* \(\mathcal{O} \in S \times U\), exactly the same as \(\mathcal{S}\), but instead of the unobservable underlying value of a given \(s\) we obtain \(V(s)\) instead from the language model by asking the language model for its judgement regarding a state; importantly, because the observations are simply a sample on the distribution, we can directly use \(V(s_{j}) \sim p^{value}_\theta(o|s_{j}), o \in \{ sure, likely, impossible\}, \forall j \in 1 ... n\)

* \(\mathcal{T}\) is given deterministically given the state and action—"continue" appends the current state to the solution trajectory, yielding a new subproblem, and calculates a new thought; "rollback" pops the last item in the solution trajectory back into the current state and reverts to the previous subproblem; "think" reformulates a new state given the current subproblem

* \(\mathcal{R}\) is given by a language model evaluator given a final trajectory, where: \(r_{\max}\) is given if the LM believes a trajectory successfully solves the problem, and \(r_{\min}\) is given if the LM believes a trajectory failed to solve the problem

Lastly, for this problem, we set discount \(\gamma\) to \(1\) to maximize joint reward, and \(s_0\) would be the initial, unsolved problem.

§.§ Modified POMCP

To solve the formalization given above in an actual problem, we chose the POMCP solver (<cit.>). This solver is chosen for three primary reasons.

First, by only needing actions and observation sequences as input, the solver requires no explicit distribution on observation and transitions, meaning that simply making concrete samples from the language model posterior is enough to take advantage of its distributional nature.

Second, the POMCP solver has excellent anytime performance characteristics; the search tree for possible solutions will prioritize most possible solutions as rated by intermediate value, but can expand to (at the worst case) an exhaustive search of all possible intermediate states. In particular, easier problems will have stronger heuristic signals, which typically will take less time to solve; this means that a cutoff could be specified by the user to control the speed/accuracy trade-off in solving a given problems.

Specifically, a POMCP solver collects a tree based on sequences of actions and their resulting observations \(h = \{a_1, o_1, ...\}\). When planning for a specific action, the scheme samples a series of possible next states from a generative model given your current state and action \(s' \sim T(\cdot | s,a)\) and calculates reward \(R(s,a)\) from current state.

Once this procedure grows the tree to a certain depth, a point-wise value estimate is calculated from a roll-out.

For this specific problem, we modify the typical "rollout" rollout procedure by essentially performing CoT reasoning with a weighted average of the possible rewards in obtained in the end:

obtain a value estimate at some leaf state $s_{f}$

$d > f$
$s = s_{f}$
$L \gets d-n$ Depth Remaning in Rollout
$\tau \gets \{s_0, \dots, s_{f}\}$
$L \neq 0$
$\tau \gets \tau \cup \left\{\arg\max_{s'} \qty(p^{thought}_{\theta}(s'|s))\right\}$
$s = s'$
$L \gets L-1$
$V = \frac{R_{\max} \cdot p_{\theta}^{evaluate}(\tau^{*}|\tau)+R_{\min} \cdot p_{\theta}^{evaluate}(\neg\tau^{*}|\tau)}{R_{\max}+R_{\min}}$Posterior Weighted Average of Possible Reward

where, \(p_{\theta}^{thought}\) is the "thought" generation prompt previously discussed, and \(p_{\theta}^{evaluate}\) is the evaluation prompt to check if a particular trajectory truly solves the target task which is also used in reward calculation. Recall that \(\tau^{*}\) represents a trajectory which answers the given question correctly.

As CoT is a reasonably performant reasoning procedure that is relatively lightweight to compute, we believe it would serve to raise the lower bound of possible values, and therefore aid the speed of solution in POMCP.

§.§ Task Setup

Trajectory of PoT solver interacting with a “Game of 24”

Similar to ToT, we are going to use the Game of 24 as a difficult multi-step reasoning task with which to test the scheme proposed.

The Game of 24 is a mathematical reasoning game, which uses four numbers and basic arithmetic operations to obtain a value of 24. For instance, for the problem of , a solution trajectory in terms of subproblems used in our work may look as follows:

* \(s_0\): subproblem: 4 9 10 13

* \(s_1\): \(13-9=4\), subproblem: 4 4 10

* \(s_2\): \(10-6 = 6\), subproblem: 4 6

* \(s_3\): \(4 \cdot 6\), subproblem: 24

which concludes the solution.

Data Source: in order to maintain comparability to ToT, we leverage the exact dataset curated by Yao et. al. scraped from 4nums.com as our problem set as well. Importantly, the data is sorted by rate of difficulty (as measured by weighted average time for solution)

Benchmark: the "success rate" metric reported involves the success rate across 100 games, corresponding to the metric reported by ToT. Additionally, we also report time-to-solve metrics as measured by the time between the initialization of an empty POMCP tree to obtaining a proposed solution from the scheme.

Language Modeling: distinct from ToT, to perform language model, we use two separate language models. \(p_{\theta}^{evaluate}\) and \(p_{\theta}^{value}\) (for \(\mathcal{R}\) and \(\mathcal{O}\) respectively) were computed using GPT-4-Turbo (1106), and \(p_{\theta}^{thought}\) was computed using GPT-3.5-Turbo-Instruct (0914). This hybrid approach allows for single-token only inference on the larger GPT-4 models, affording dramatic performance improvements.

Solving: we performed language model inference through the OpenAI Azure Cognitive Services API and used the POMDPs.jl, BasicPOMCP.jl Julia packages for the orchestration of the solver.

§ RESULTS

Method     Success
CoT     4.0%

ToT (b=1)     45%

ToT (b=5)     74%

PoT (ours)     89.4%

Game of 24 Results; CoT and ToT results from <cit.>.

a) ROC curve by time b) Count by time to solve

Table <ref> highlights the results we obtained by applying the PoT scheme on the Game of 24 problem. Specifically, we demonstrate a problem solving success rate which exceeds existing approaches—an in particular exceeds the results from CoT (<cit.>) by a significant margin.

Notably, because ToT used an exogenous number of search breadth, it is likely that with higher branches the approach can yield improved accuracy. Because POMCP has a dynamic branching characteristic to BFS—making a direct comparison difficult—we additionally report the relationship between time spent in problem solving and accuracy in Figure <ref>. By setting the longest time of an hour ($3600$ seconds) as a threshold of $1$ and interpolating time linearly, the accuracy results we obtain scores an AUC value of $81.4\%$.

Importantly, Figure <ref>.b highlights that a significant amount (specifically, $83.7\%$) of the cases are solved within 10 minutes—representing only $20\%$ of the total time alloted to solve; this property demonstrates the anytime characteristic from PoT's use of POMCP.

§ CONCLUSION

In this work, we present Plan of Thought (PoT), a novel language model decoding scheme that extends Tree of Thoughts (ToT) (<cit.>) which leverages a large language model's self-reflective reasoning capabilities (<cit.>) to guide multi-hop reasoning about a problem.

We formalize our approach through the POMDP framework (<cit.>), and demonstrate superior performance of our approach on the Game of 24 task compared to existing approaches using the online POMCP (<cit.>) solver. Because of the anytime behavior of POMCP, we are able to solving a large portion of the test problems in significantly less time than the maximum alloted.

We were able to demonstrate the results presented using a hybrid language modeling approach by using GPT-3.5-Turbo-Instruct as our state generator and GPT-4-Turbo for evaluation only: unlike previous approaches which only used a single, fixed language model (usually GPT-4). Taken together, these properties makes PoT a more flexible approach to solving basic multi-step reasoning tasks as compared to previous approaches—allowing for contemporary LMs to solve more complex problems.

Notably, as the previous ToT approach requires seaching on a tree of a fixed-breadth, it is likely that the approach will converge to similar performance as the PoT scheme presented here at higher choices of $b$. Importantly, however, the anytime property of the approach presents here indicates that PoT can scale its solution time dynamically to the number of “thoughts” required for each problem as shown by the AUC value of $81.4\%$ of our approach using time as a threshold, while ToT will take a fix-time approach to generate and evaluate an entire tree regardless of solution complexity.

In its current form, our work has two key limitations. First, similar to that proposed by ToT, the approach is still significantly more computationally expensive than CoT or other direct decoding approaches; therefore, these search techniques is likely unnecessary for problems which can be solved with high accuracy using simpler techniques. Second, posterior distributions—even when taking only top-k samples for extremely small k—are still meaningful only on billion-parameter models if used without additional fine tuning (<cit.>): making the heuristic-driven performance improvements of PoT limited in scope. With additional fine-tuning of surrogate value models, PoT could likely perform dramatically more efficiently while obtaining its positive characteristics in solution quality.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitlearXiv preprint arXiv:2303.08774
titleGpt-4 technical report

abstractRecent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by ﬁne-tuning on a speciﬁc task. While typically task-agnostic in architecture, this method still requires task-speciﬁc ﬁne-tuning datasets of thousands or tens of thousands of examples. By contrast, humans can generally perform a new language task from only a few examples or from simple instructions – something which current NLP systems still largely struggle to do. Here we show that scaling up language models greatly improves task-agnostic, few-shot performance, sometimes even reaching competitiveness with prior state-of-the-art ﬁnetuning approaches. Speciﬁcally, we train GPT-3, an autoregressive language model with 175 billion parameters, 10x more than any previous non-sparse language model, and test its performance in the few-shot setting. For all tasks, GPT-3 is applied without any gradient updates or ﬁne-tuning, with tasks and few-shot demonstrations speciﬁed purely via text interaction with the model. GPT-3 achieves strong performance on many NLP datasets, including translation, question-answering, and cloze tasks, as well as several tasks that require on-the-ﬂy reasoning or domain adaptation, such as unscrambling words, using a novel word in a sentence, or performing 3-digit arithmetic. At the same time, we also identify some datasets where GPT-3’s few-shot learning still struggles, as well as some datasets where GPT-3 faces methodological issues related to training on large web corpora. Finally, we ﬁnd that GPT-3 can generate samples of news articles which human evaluators have difﬁculty distinguishing from articles written by humans. We discuss broader societal impacts of this ﬁnding and of GPT-3 in general.
titleLanguage Models are Few-Shot Learners
rown et al. - 2020 - Language Models are Few-Shot Learners.pdf:application/pdf

abstractDespite their ubiquity in language generation, it remains unknown why truncation sampling heuristics like nucleus sampling are so effective. We provide a theoretical explanation for the effectiveness of the truncation sampling by proving that truncation methods that discard tokens below some probability threshold (the most common type of truncation) can guarantee that all sampled tokens have nonzero true probability. However, thresholds are a coarse heuristic, and necessarily discard some tokens with nonzero true probability as well. In pursuit of a more precise sampling strategy, we show that we can leverage a known source of model errors, the softmax bottleneck, to prove that certain tokens have nonzero true probability, without relying on a threshold. Based on our findings, we develop an experimental truncation strategy and the present pilot studies demonstrating the promise of this type of algorithm. Our evaluations show that our method outperforms its threshold-based counterparts under automatic and human evaluation metrics for low-entropy (i.e., close to greedy) open-ended text generation. Our theoretical findings and pilot experiments provide both insight into why truncation sampling works, and make progress toward more expressive sampling algorithms that better surface the generative capabilities of large language models.
titleClosing the Curious Case of Neural Text Degeneration
99USIE/Finlayson et al. - 2023 - Closing the Curious Case of Neural Text Degenerati.pdf:application/pdf

abstractDespite considerable advances in neural language modeling, it remains an open question what the best decoding strategy is for text generation from a language model (e.g. to generate a story). The counter-intuitive empirical observation is that even though the use of likelihood as training objective leads to high quality models for a broad range of language understanding tasks, maximization-based decoding methods such as beam search lead to degeneration — output text that is bland, incoherent, or gets stuck in repetitive loops.
titleThe Curious Case of Neural Text Degeneration
oltzman et al. - 2020 - The Curious Case of Neural Text Degeneration.pdf:application/pdf

journaltitleThe 2023 Conference on Empirical Methods in Natural Language Processing
titlePrompting is not a substitute for probability measurements in large language models

abstractIn this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (MDPs) and partially observable MDPs (POMDPs). We then outline a novel algorithm for solving POMDPs off line and show how, in some cases, a ﬁnite-memory controller can be extracted from the solution to a POMDP. We conclude with a discussion of how our approach relates to previous work, the complexity of ﬁnding exact solutions to POMDPs, and of some possibilities for ﬁnding approximate solutions. © 1998 Elsevier Science B.V. All rights reserved.
journaltitleArtificial Intelligence
shortjournalArtificial Intelligence
titlePlanning and acting in partially observable stochastic domains
4/Kaelbling et al. - 1998 - Planning and acting in partially observable stocha.pdf:application/pdf

Dublin, Ireland

Association for Computational Linguistics

abstractLarge pretrained generative models like GPT3 often suffer from hallucinating non-existent or incorrect content, which undermines their potential merits in real applications. Existing work usually attempts to detect these hallucinations based on a corresponding oracle reference at a sentence or document level. However ground-truth references may not be readily available for many free-form text generation applications, and sentence- or documentlevel detection may fail to provide the finegrained signals that would prevent fallacious content in real time. As a first step to addressing these issues, we propose a novel token-level, reference-free hallucination detection task and an associated annotated dataset named HADES (HAllucination DEtection dataSet) 1. To create this dataset, we first perturb a large number of text segments extracted from English language Wikipedia, and then verify these with crowd-sourced annotations. To mitigate label imbalance during annotation, we utilize an iterative model-in-loop strategy. We conduct comprehensive data analyses and create multiple baseline models.
eventtitleProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
journaltitleProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
titleA Token-level Reference-free Hallucination Detection Benchmark for Free-form Text Generation
iu et al. - 2022 - A Token-level Reference-free Hallucination Detecti.pdf:application/pdf

journaltitlearXiv preprint arXiv:2304.01904
titleRefiner: Reasoning feedback on intermediate representations

journaltitlearXiv preprint arXiv:2303.11366
titleReflexion: an autonomous agent with dynamic memory and self-reflection

journaltitleAdvances in neural information processing systems
titleMonte-Carlo planning in large POMDPs

abstractConventionally, generation of natural language for dialogue agents may be viewed as a statistical learning problem: determine the patterns in human-provided data and generate appropriate responses with similar statistical properties. However, dialogue can also be regarded as a goal directed process, where speakers attempt to accomplish a speciﬁc task. Reinforcement learning (RL) algorithms are designed speciﬁcally for solving such goaldirected problems, but the most direct way to apply RL – through trial-and-error learning in human conversations, – is costly. In this paper, we study how ofﬂine reinforcement learning can instead be used to train dialogue agents entirely using static datasets collected from human speakers. Our experiments show that recently developed ofﬂine RL methods can be combined with language models to yield realistic dialogue agents that better accomplish task goals.
titleCHAI: A CHatbot AI for Task-Oriented Dialogue with Offline Reinforcement Learning
erma et al. - 2022 - CHAI A CHatbot AI for Task-Oriented Dialogue with.pdf:application/pdf
ine Learning

abstractWe explore how generating a chain of thought—a series of intermediate reasoning steps—signiﬁcantly improves the ability of large language models to perform complex reasoning. In particular, we show how such reasoning abilities emerge naturally in sufﬁciently large language models via a simple method called chain-ofthought prompting, where a few chain of thought demonstrations are provided as exemplars in prompting. Experiments on three large language models show that chain-of-thought prompting improves performance on a range of arithmetic, commonsense, and symbolic reasoning tasks. The empirical gains can be striking. For instance, prompting a PaLM 540B with just eight chain-of-thought exemplars achieves state-of-the-art accuracy on the GSM8K benchmark of math word problems, surpassing even ﬁnetuned GPT-3 with a veriﬁer.
titleChain-of-Thought Prompting Elicits Reasoning in Large Language Models

abstractLanguage models are increasingly being deployed for general problem solving across a wide range of tasks, but are still confined to token-level, left-to-right decision-making processes during inference. This means they can fall short in tasks that require exploration, strategic lookahead, or where initial decisions play a pivotal role. To surmount these challenges, we introduce a new framework for language model inference, “Tree of Thoughts” (ToT), which generalizes over the popular “Chain of Thought” approach to prompting language models, and enables exploration over coherent units of text (“thoughts”) that serve as intermediate steps toward problem solving. ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices to decide the next course of action, as well as looking ahead or backtracking when necessary to make global choices. Our experiments show that ToT significantly enhances language models’ problem-solving abilities on three novel tasks requiring non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords. For instance, in Game of 24, while GPT-4 with chain-of-thought prompting only solved 4% of tasks, our method achieved a success rate of 74%. Code repo with all prompts: https://github.com/princeton-nlp/tree-of-thought-llm.
shorttitleTree of Thoughts
titleTree of Thoughts: Deliberate Problem Solving with Large Language Models
WAD2F/Yao et al. - 2023 - Tree of Thoughts Deliberate Problem Solving with .pdf:application/pdf
ine Learning

abstractWhile large language models (LLMs) have demonstrated impressive performance across tasks in language understanding and interactive decision making, their abilities for reasoning (e.g. chain-of-thought prompting) and acting (e.g. action plan generation) have primarily been studied as separate topics. In this paper, we explore the use of LLMs to generate both reasoning traces and task-speciﬁc actions in an interleaved manner, allowing for greater synergy between the two: reasoning traces help the model induce, track, and update action plans as well as handle exceptions, while actions allow it to interface with and gather additional information from external sources such as knowledge bases or environments. We apply our approach, named ReAct, to a diverse set of language and decision making tasks and demonstrate its effectiveness over state-of-the-art baselines in addition to improved human interpretability and trustworthiness. Concretely, on question answering (HotpotQA) and fact veriﬁcation (Fever), ReAct overcomes prevalent issues of hallucination and error propagation in chain-of-thought reasoning by interacting with a simple Wikipedia API, and generating human-like task-solving trajectories that are more interpretable than baselines without reasoning traces. Furthermore, on two interactive decision making benchmarks (ALFWorld and WebShop), ReAct outperforms imitation and reinforcement learning methods by an absolute success rate of 34% and 10% respectively, while being prompted with only one or two in-context examples.
titleReAct: Synergizing Reasoning and Acting in Language Models
3YP9S33/Yao et al. - 2023 - ReAct Synergizing Reasoning and Acting in Languag.pdf:application/pdf
ine Learning


# Investigating Trade-offs in Utility, Fairness and Differential Privacy in
Neural Networks

Marlotte Pannekoek  Giacomo Spigler

###### Abstract

To enable an ethical and legal use of machine learning algorithms, they must
both be fair and protect the privacy of those whose data are being used.
However, implementing privacy and fairness constraints might come at the cost
of utility (Jayaraman & Evans, 2019; Gong et al., 2020). This paper
investigates the privacy-utility-fairness trade-off in neural networks by
comparing a Simple (S-NN), a Fair (F-NN), a Differentially Private (DP-NN),
and a Differentially Private and Fair Neural Network (DPF-NN) to evaluate
differences in performance on metrics for privacy ($\epsilon$, $\delta$),
fairness (risk difference), and utility (accuracy). In the scenario with the
highest considered privacy guarantees ($\epsilon$ = 0.1, $\delta$ = 0.00001),
the DPF-NN was found to achieve better risk difference than all the other
neural networks with only a marginally lower accuracy than the S-NN and DP-NN.
This model is considered fair as it achieved a risk difference below the
strict (0.05) and lenient (0.1) thresholds. However, while the accuracy of the
proposed model improved on previous work from Xu, Yuan and Wu (2019), the risk
difference was found to be worse.

Machine Learning, fairness, differential privacy, utility-fairness-privacy
tradeoff, neural networks

##  1 Introduction

Machine learning algorithms are employed with great goals in mind, such as
improved decision-making or increased efficiency. These benefits explain the
ubiquitous use of such algorithms. However, potential harms should not be
overlooked. Firstly, using personal data for training can cause leakage of
private information. In addition, individuals can be unfairly affected when
outcomes are dependent on race, sex, religious beliefs, sexual orientation, or
economic status. For machine learning algorithms trained on personal data to
be viable in today’s society, they must ensure fairness and privacy for their
users. This is required for both ethical and legal reasons (Xu et al., 2019;
Wood et al., 2018). In this paper, we build on existing research to
investigate how algorithms can ensure privacy while remaining fair and useful.
To this extent, we tested how applying the fairness method Reject Option
Classification influences the performance of a neural network (Briggs &
Hollmén, 2020). Furthermore, the effects of adding a privacy-preserving
optimizer to a simple and to a fair neural network were investigated.

Prior research has shown that when personal data are used for training machine
learning models, these data can be retrieved by observing the behavior or
structure of the learning algorithms (Yeom et al., 2020). This can negatively
affect social status, employment chances, and insurance costs for end users of
the systems (Wood et al., 2018). Therefore, it appears critical to develop and
apply privacy-preserving methods. Along this direction, here we focus on the
differential privacy framework, which is currently considered state-of-the-art
(Gong et al., 2020). Its goal is to produce an approximately equal output,
whether an individual is included in the analysis or not (Wood et al., 2018).
An essential element of differential privacy is the privacy budget $\epsilon$,
which controls how well privacy is protected. In general, lower values of
$\epsilon$ imply more privacy protection. Nonetheless, choosing the best value
for the parameter is still difficult (Jayaraman & Evans, 2019).

Finally, fairness entails that the behavior of a machine learning system does
not dependent on protected attributes such as race and gender (Zhu et al.,
2020). It is often assumed that algorithms are fair and impartial since
decisions are based on data instead of human judgment (Corbett-Davies & Goel,
2018). However, several studies provide evidence that algorithms can be
negatively biased towards protected groups, which could, for example, cause
men to be preferred over women with similar skills by hiring algorithms (Xu et
al., 2019). Several methods have been developed to achieve fairness via
manipulation of the data or of the algorithms during pre-processing, in-
processing, or post-processing phases. In this research, the post-processing
method of “Reject Option Classification” was applied to a simple and a
differentially private neural network to explore its effect on the performance
of the network.

The existing empirical research on differentially private and fair algorithms
has mainly focused on logistic regression (Xu et al., 2019; Jagielski et al.,
2019; Ding et al., 2020). Research by Friedler et al. (2019), however, shows
that the trade-off between accuracy and fairness can differ greatly depending
on the specific algorithm being used. This suggests that it would be useful to
research the combination of fairness and privacy on a wider range of machine
learning systems.

In recent years both differential privacy and fairness have received much
attention (Caton & Haas, 2020; Yeom et al., 2020). However, several authors
have argued more research on algorithms that can achieve both goals (Ekstrand
et al., 2018; Zhu et al., 2020; Xu et al., 2019; Datta et al., 2018). Earlier
work on differential privacy has shown that there can be trade-offs between
utility and privacy-preservation (Jayaraman & Evans, 2019; Gong et al., 2020).
Similar work has been done on the trade-off between utility and fairness
(Feldman et al., 2015). _Here we investigate the trade-off between utility,
privacy, and fairness when the goal of an algorithm is to perform well on all
three metrics._

Specifically, we explore how the privacy-utility-fairness trade-off in neural
networks is affected by:
\- the Reject Option Classification method for fairness;
\- a differentially private optimizer, under varying privacy budgets;
\- the joint use of a differentially private optimizer and the Reject Option
Classification method for fairness.

We finally compare the different cases with corresponding state-of-the-art
results by Xu, Yuan, and Wu (2019).

##  2 Related Work

The combination of fairness and differential privacy has been the subject of
recent empirical research (Xu et al., 2019). The work by Xu, Yuan and Wu
(2019) in particular compared two algorithms with respect to utility and
fairness, under different choices of the privacy budget ($\epsilon$). The
algorithms were tested on two benchmarks; the Adult and the Dutch dataset. The
metrics used for utility and fairness were accuracy and risk difference,
respectively. For their first algorithm, logistic regression was used, and a
penalty was added to the objective function to ensure fairness. A technique
known as the functional mechanism was then applied to the objective function
to ensure differential privacy. In the second algorithm, the objective
function was corrupted by noise sampled from a Laplace distribution of which
the mean was shifted according to a fairness constraint, therefore satisfying
both fairness and differential privacy. Both algorithms achieved differential
privacy and fairness with reasonable utility. Their results show that as
$\epsilon$ was decreased, thus increasing the degree of privacy protection,
the accuracy decreased, with a dynamics consistent across both datasets and
methods.

Further, Jagielski et al. (2019) compared the use of a post-processing method
for achieving fairness with an in-processing method. Only the algorithm using
post-processing achieved a reasonable fairness-accuracy-privacy trade-off.
However, only privacy with regard to the sensitive attribute was taken into
account.

Ding et al. (2020) also combined privacy and fairness and explored varying the
amount of noise added to different attributes. They also used a less strict
definition of differential privacy. Using these techniques, they improved on
the results achieved by Xu, Yuan and Wu (2019). Their results suggest that
increasing $\epsilon$ from 0.1 to 1 results in a higher increase in accuracy
than increasing $\epsilon$ from 10 to 100. However, this difference was not
tested for significance. For most values of $\epsilon$, their algorithms
achieved reasonable values of risk difference.

Cummings, Gupta, Kimpara and Morgenstern (2019) found that exact fairness and
differential privacy in their set-up could not be achieved, although a trade-
off could be achieved by relaxing the notion of exact fairness to ‘approximate
fairness’.

Hajian, Domingo-Ferrer, Monreale, Pedreschi and Giannotti (2015) investigated
the application of privacy-preserving and fairness techniques on patterns
derived by a classifier using multiple association rules. Their approach can
be classified as a post-processing approach as they altered the classifier’s
results instead of the classifier itself or the data it was trained on (Hajian
et al., 2015). They investigate both _k_ -anonymity and differential privacy
to achieve privacy. Their empirical analyses demonstrate that _k_ -anonymity
distorted the patterns less than the differential privacy approach.
Additionally, their results show that applying the privacy technique after the
fairness technique can deteriorate the achieved fairness.

##  3 Experiments

###  3.1 Dataset Description

The experiments presented here were performed using the Adult dataset (Dua &
Graff, 2017), due to its importance in research on privacy and fairness, and
to allow for a direct comparison with state-of-the-art results (Xu et al.,
2019).

The importance of the Adult dataset in the field is due to the presence of
sensitive attributes that could be used for personal identification or
potentially threaten the fairness of models trained on it. The dataset is
openly available and consists of 45,222 cases and 14 variables. In this
research, only ’sex’ was regarded as a sensitive attribute, and ’income’ was
regarded as the dependent variable. Income is treated as a binary variable,
separating incomes of less than 50,000 (income = 0) and more than 50,000
(income = 1). The sex variable refers to biological sex with male and female
as the possible values.

###  3.2 Data Pre-Processing

To ensure comparability, the same pre-processing steps were applied as in the
study by Xu, Yuan and Wu (2019). Specifically, list-wise deletions were
performed, dummy codes were used for the categorical variables, and continuous
variables were normalized. The Adult dataset already contained a separate
train and test set. The train dataset was further split up into train and
validation sets. The train, validation, and test dataset constitute 53.4%,
13.3%, and 33.3% of the total amount of data, respectively.

Initial data exploration showed a class imbalance in the labels, with
approximately 75$\%$ of the reported incomes being less than 50,000.
Furthermore, data exploration showed that females were underrepresented,
making up around 32$\%$ of the cases. Approximately 88$\%$ of females earned
less than 50,000, against 69$\%$ of males, which motivated applying fairness
constraints.

###  3.3 Models

Four models were compared to explore the effect of differential privacy and
fairness methods on the privacy-utility-fairness trade-off: a baseline
‘Simple’ neural network (S-NN), and a Fair (F-NN), a Differentially Private
(DP-NN), and a Differentially Private and Fair neural network (DPF-NN). All
models were implemented using Keras (Chollet, 2015). When no specific
parameter settings are mentioned, the default settings were used.

Simple Neural Network (S-NN). The S-NN consisted of three fully connected
layers with six neurons in the first and second layer and one neuron in the
final layer. The first and the second layer used a ReLu activation, while the
last layer used a sigmoid activation. Binary cross-entropy was used as the
loss function and Adam as the optimizer (Kingma & Ba, 2017). Training was
performed for a fixed duration of 20 epochs of Stochastic Gradient Descent
with minibatches of size $mb=20$.

Fair Neural Network (F-NN). The network used for the F-NN was equal to the
S-NN. However, the ‘Reject Option Classification’ method was added to alter
the output labels after prediction in an effort to improve fairness. The
method was chosen as the best performing of six fairness methods that were
previously evaluated. Results from the comparison are reported in the
Supplementary Materials. The pre-processing and post-processing techniques to
ensure fairness were implemented using the Artificial Intelligence Fairness
360 library (AIF 360) (Bellamy et al., 2018).

Differentially Private Neural Network (DP-NN). The network used for the DP-NN
was equal to the S-NN. However, training was performed using a differentially
private variant of the Adam optimizer (DPAdamGaussianOptimizer) (McMahan et
al., 2019). This optimizer adds Gaussian noise to the gradient to ensure
differential privacy. The noise$\\_$multiplier parameter was used to specify
the amount of noise added to the model. This parameter’s value depends on the
target value for $\epsilon$ and $\delta$ (quantifying the probability of not
achieving privacy within the privacy budget.), and was calculated using the
compute$\\_$dp$\\_$sgd$\\_$privacy function. Another notable aspect of the
differentially private optimizer is that norm clipping is applied after the
data are split up into minibatches, but before adding the noise. Training was
repeated for values of $\epsilon\in\\{0.1,1,10,100\\}$ and
$\delta\in\\{0.01,0.001,0.0001,0.00001\\}$, as they are commonly used values
in differential privacy applications (Xu et al., 2019; Ding et al., 2020).

Differentially Private and Fair Neural Network (DPF-NN).

The DPF-NN finally integrated the F-NN and the DP-NN, combining the use of the
Reject Option Classification method from F-NN with the differentially private
optimizer from DP-NN. The same values of $\epsilon$ and $\delta$ as the DP-NN
were used.

###  3.4 Evaluation Criteria

The different models were tested for accuracy and risk difference to assess
the utility and fairness of the models, respectively. All experiments were
repeated ten times with different random seeds. This procedure is compatible
with the previous work by Xu, Yuan and Wu (2019).

A mean accuracy above 75.4$\%$ on test data was considered an improvement over
an algorithm that chooses the majority label. Risk difference was used as the
metric to evaluate model fairness. A risk difference of 0 was considered
optimal for fairness. Standard thresholds below which models are considered
fair include 0.05 and 0.1 (Briggs & Hollmén, 2020; Xu et al., 2019). Both were
considered and will be referred to as the strict and the lenient threshold,
respectively, throughout this paper.

The risk difference and accuracy scores (for given values of $\epsilon$ and
$\delta$) were compared to the thresholds and the scores achieved by the
baseline models by Xu, Yuan and Wu (2019). Independent t-tests were applied to
assess significant differences between algorithms, using a significance level
of 0.05. Lastly, linear regression was performed to test for an effect of
$\epsilon$ and $\delta$ on mean accuracy in the DP-NN and DPF-NN models.

##  4 Results

The accuracy and risk difference for all the neural networks ($\epsilon=0.1$,
$\delta=0.00001$) are shown in Table 1, together with the results achieved by
the equivalent models from Xu, Yuan and Wu (2019). Further comparisons between
the models are available in the Supplementary Materials.

Table 1: Comparison between the performance of the neural networks from this
work (top half) and the logistic regression models by Xu, Yuan and Wu (2019)
(bottom half). The order of the models indicate correspondence between the
models proposed in this work and those of Xu, Yuan and Wu (simple baseline -
LR; fair network - FairLR; differentially private network - PrivLR;
differentially private and fair network - PFLR*). The privacy parameters
$\epsilon=0.1$, $\delta=0.00001$ were used in the models that applied
differential privacy constraints. Performance is shown as mean accuracy (in
percentage) and risk difference (with standard deviations). Higher values are
preferred for accuracy, whereas lower values are preferred for risk
difference.
| Accuracy | Risk difference
---|---|---
S-NN | 84.14 ± 0.34 | 0.1310 ± 0.0147
DP-NN | 84.03 ± 0.05 | 0.1355 ± 0.0024
F-NN | 79.25 ± 3.50 | 0.0566 ± 0.0065
DPF-NN | 82.98 ± 0.19 | 0.0475 ± 0.0020
LR | 83.80 ± 0.23 | 0.1577 ± 0.0064
PrivLR | 62.63 ± 14.80 | 0.0883 ± 0.0805
FairLR | 77.39 ± 5.21 | 0.0095 ± 0.0071
PFLR* | 74.91 ± 0.40 | 0.0028 ± 0.0039

T-tests were applied to assess whether the differences between the different
neural networks and the models by Xu, Yuan and Wu (2019) are significant at a
significance level of 0.05. The results from these t-tests regarding the mean
accuracy and risk difference scores can be found in Table 2 and Table 3,
respectively.

Table 2: Difference in mean accuracy between all models. A positive score
means that the model defined in the row performed better than the model
defined in the column. Eq. Model refers to the equivalent model from Xu, Yuan
and Wu (2019). For example, FairLR is the equivalent model for the F-NN. An
independent t-test was performed to test if the difference in means was
significant at significance level $\alpha=.05$ (indicated by *). $DF=18$ for
all t-tests. The t-statistic is reported in brackets. The privacy parameters
$\epsilon=0.1$, $\delta=0.00001$ were used in the models that applied
differential privacy constraints.
| S-NN | DP-NN | F-NN | DPF-NN | Eq. Model
---|---|---|---|---|---
S-NN | 0 (0.0) | 0.11 (1.0) | 4.89* (4.4) | 1.16* (9.4) | 0.34* (2.6)
DP-NN |  | 0 (0.0) | 4.78* (4.3) | 1.05* (16.9) | 21.40* (4.6)
F-NN |  |  | 0 (0.0) | -3.73* (-3.4) | 1.86 (0.9)
DPF-NN |  |  |  | 0 (0.0) | 8.07* (57.6)

Table 3: Difference in mean risk difference between all models. A negative
score means that the model defined in the row performed better than the model
defined in the column. Eq. Model refers to the equivalent model from Xu, Yuan
and Wu (2019). For example, FairLR is the equivalent model for the F-NN.*
means that the difference is significant at a 0.05 significance level. $DF=18$
for all t-tests. The t-statistic is reported in brackets. The privacy
parameters $\epsilon=0.1$, $\delta=0.00001$ were used in the models that
applied differential privacy constraints.
| S-NN | DP-NN | F-NN | DPF-NN | Eq. Model
---|---|---|---|---|---
S-NN | 0 (0.0) | -0.0045 (-1.0) | 0.0744* (14.6) | 0.0835* (17.8) | -0.0267* (-5.3)
DP-NN |  | 0 (0.0) | 0.0789* (36.0) | 0.0880* (89.1) | 0.0472 (1.9)
F-NN |  |  | 0 (0.0) | 0.0091* (4.2) | 0.0471* (15.5)
DPF-NN |  |  |  | 0 (0.0) | 0.0447* (32.3)

Simple Neural Network (S-NN). As shown in Table 1 the S-NN achieved an average
accuracy of 84.14% (_SD_ = 0.34). This is slightly but significantly higher
than the simple logistic regression (LR) by Xu, Yuan and Wu (2019), _t_(18) =
2.6, _p_ = .017, which achieved an average accuracy of 83.80% (_SD_ = 0.23).
The average risk difference for the S-NN was 0.1310 (_SD_ = 0.0147), which is
slightly but significantly lower than the 0.1577 (_SD_ = 0.00064) risk
difference from the model by Xu, Yuan and Wu (2019), _t_(18) = -5.3, _p_ $<$
.001. The achieved accuracy of the S-NN is above the threshold of an algorithm
that chooses the majority label.

Fair Neural Network (F-NN).

The F-NN achieved an average accuracy of 79.25% (_SD_ = 3.50), which is above
the majority label threshold and a significant decrease of 4.89 compared to
the S-NN (_M_ = 84.14%, _SD_ = 0.34), _t_(18) = 4.4, _p_ $<$ .001. Compared to
the average accuracy from the fair model by Xu, Yuan and Wu (2019) (_M_ =
77.39%, _SD_ = 5.21), this is an increase of 0.0186 in average accuracy.
However, this difference is not significant, _t_(18) = 0.9, _p_ = .361. The
mean risk difference achieved by the F-NN is 0.0566 (_SD_ = 0.0065), which is
slightly above the 0.05 threshold. Compared to the risk difference of the S-NN
(_M_ = 0.1310, _SD_ = 0.0147), this is a 0.0744 decrease, which was found to
be significant, _t_(18) = -14.6, _p_ $<$ .001. Compared to the fair logistic
regression model by Xu, Yuan and Wu (2019), which achieved an average risk
difference of 0.0095 (_SD_ = 0.0071), this is a significant increase of
0.0471, _t_(18) = 15.5, _p_ $<$ .001.

In conclusion, the application of Reject Option Classification in the F-NN did
lead to a decreased risk difference compared to the S-NN. The mean risk of the
F-NN was below the lenient 0.1 threshold. However, it is still slightly above
the 0.05 threshold and higher than the average risk difference achieved by the
fair logistic regression model by Xu, Yuan and Wu (2019). The fair model’s
accuracy is lower compared to the S-NN but still acceptable and higher than
that of the fair logistic model.

Differentially Private Neural Network (DP-NN).

A table can be found in the appendix that displays the mean accuracy and risk
difference for the DP-NN with differing values for $\epsilon$ and $\delta$. A
linear regression was run to determine whether there was a significant effect
of $\epsilon$ and $\delta$ on average accuracy and risk difference for the DP-
NN. No significant effect on risk difference
($F(6,9)=3.15,p=.0597,R^{2}=0.68$) or accuracy
($F(6,9)=2.88,p=.0748,R^{2}=0.66$) could be observed for varying values of
$\epsilon$ and $\delta$. Across all $\delta$ and $\epsilon$ values, the
overall average of the average accuracy is 84.05% (_SD_ = 0.05). The overall
average of the average risk difference is 0.1345 (_SD_ = 0.0016).

The average accuracy of the DP-NN model with $\epsilon$ = 0.1 and $\delta$ =
0.00001, so with the highest privacy guarantee, is 84.03% (_SD_ = 0.05). With
the highest privacy guarantee, the DP-NN achieved a mean accuracy that was
0.11 lower than that of the S-NN (_M_ = 84.14%, _SD_ = 0.34). This difference
was, however, not significant (_t_(18) = -1.0, _p_ = .325). The average risk
difference of the model with the highest privacy guarantee is 0.1355 (_SD_ =
0.0024), a difference of 0.0045 compared to the S-NN (_M_ = 0.1310, _SD_ =
0.0147). However, this difference is not significant, _t_(18) = 1.0, _p_ =
.352.

In the appendix a summary table is given of the accuracy and risk difference
for differing values of $\epsilon$ and $\delta$ = 0.00001 for the DP-NN and
the differentially private logistic regression model by Xu, Yuan and Wu
(2019). When comparing the models with the lowest $\epsilon$, the DP-NN
model’s average risk difference (_M_ = 0.1355, _SD_ = 0.0024) is 0.0472 higher
than that of the differentially private logistic regression (_M_ = 0.0883,
_SD_ = 0.0805). However, this is not a significant difference, _t_(18) = 1.9,
_p_ = .080. The DP-NN model (_M_ = 84.03%, _SD_ = 0.05) does significantly
improve the average accuracy by 21.40, _t_(18) = 4.6, _p_ $<$ .001, in
comparison with the differentially private logistic regression (_M_ = 62.63%,
_SD_ = 14.80). When comparing the models with the highest $\epsilon$, DP-NN
also achieved a higher average accuracy (_M_ = 84.03%, _SD_ = 0.05) in
comparison with the logistic regression model (_M_ = 82.95%, _SD_ = 0.32). The
difference is smaller (10.08) but still significant, _t_(18) = 10.5, _p_ $<$
.001.

In conclusion, no trend in average accuracy or risk difference was found for
varying values of $\epsilon$ and $\delta$. Furthermore, there were no
significant differences in average accuracy or risk difference between the DP-
NN and the S-NN ($\epsilon$ = 0.1, $\delta$ = 0.00001). The DP-NN does,
however, improve the average accuracy compared to the differentially private
logistic regression.

Differentially Private and Fair Neural Network (DPF-NN). In the appendix a
table is provided that shows the average accuracy and risk difference for
varying values of $\epsilon$ and $\delta$ for the DPF-NN. As with the DP-NN,
the mean risk difference and the accuracy barely differ for different values
of $\delta$ and $\epsilon$. This is supported by the results from a simple
linear regression that was performed to determine whether there was a
significant effect of $\epsilon$ and $\delta$ on mean accuracy and risk
difference. These results show no significant effect on mean accuracy
($F(6,9)=0.66,p=.687,R^{2}=0.30$) or risk difference
($F(6,9)=0.57,p=.748,R^{2}=0.27$). Across all values of $\delta$ and
$\epsilon$ the average of the mean accuracy scores is 82.96 % (_SD_ = 0.25).
The overall average for the average risk difference is 0.0475 (_SD_ = 0.0017).
All averages for risk difference, including the overall average, are below the
0.05 threshold.

The DPF-NN with the highest privacy guarantee ($\epsilon$ = 0.1 and $\delta$ =
0.00001) has a mean accuracy of 82.98% (_SD_ = 0.19). Compared to the S-NN
(_M_ = 84.14%, _SD_ = 0.34), that is a 1.16 lower average accuracy. This is a
significant difference (_t_(18) = -9.4, _p_ $<$ .001). The DPF-NN with the
highest privacy guarantee achieved a mean risk difference of 0.0475 (_SD_ =
0.0020), which is a 0.0835 lower average risk difference compared to the S-NN
(_M_ = 0.1310, _SD_ = 0.0147). This is also a significant difference, _t_(18)
= -17.8, _p_ $<$ .001.

Compared to the F-NN (_M_ = 79.25%, _SD_ = 3.50), the most private DPF-NN (_M_
= 82.98%, _SD_ = 0.19) has a significantly higher average accuracy (_t_(18) =
3.4, _p_ = .003). The difference between the models is 3.73. The average risk
difference of the DPF-NN (_M_ = 0.0475, _SD_ = 0.0020) is 0.0091 lower
compared to the most private F-NN (_M_ = 0.0566, _SD_ = 0.0065), which is a
significant difference (_t_(18) = -4.2, _p_ = .001).

When $\epsilon$ equals 0.1 and $\delta$ equals 0.00001, the average accuracy
of the DPF-NN (_M_ = 82.98%, _SD_ = 0.19) is significantly lower by 1.05
(_t_(18) = -16.9, _p_ $<$ .001) compared to the DP-NN (_M_ = 84.03%, _SD_ =
0.05). With respect to average risk difference, the DPF-NN (_M_ = 0.0475, _SD_
= 0.0020) has a significantly lower average compared to the DP-NN (_M_ =
0.1355, _SD_ = 0.0024). This difference of 0.0880 is significant (_t_(18) =
-89.1, _p_ $<$ .001).

When the results for $\delta$ = 0.00001 for the DPF-NN are compared to the
results from the PFLR* model by Xu, Yuan and Wu (2019), some conclusions can
be drawn. Firstly, for all values of $\epsilon$, the PFLR* model achieves
lower average risk difference than the DPF-NN model. However, the average
accuracy scores are also lower for the PFLR*. The difference in risk
difference between the two models is at most 0.0447, with the lowest
$\epsilon$. In this case the difference between the DPF-NN (_M_ = 0.0475, _SD_
= 0.0020) and the PFLR* (_M_ = 0.0028, _SD_ = 0.0039) is significant (_t_(18)
= 32.3, _p_ $<$ .001). The minimal difference in risk difference between the
DPF-NN (_M_ = 0.0437, _SD_ = 0.0154) and the PFLR* (_M_ = 0.0204, _SD_ =
0.0140) is 0.0233 when $\epsilon$ equals 10. This difference is still
significant (_t_(18) = 3.5, _p_ = .002).

For average accuracy, the largest difference between the DPF-NN (_M_ = 82.98%,
_SD_ = 0.19) and the PFLR* (_M_ = 74.91%, _SD_ = 0.40) was 8.07, for the
lowest privacy budget. This is a significant difference (_t_(18) = 57.6, _p_
$<$ .001). The smallest difference in average accuracy between the DPF-NN (_M_
= 83.04%, _SD_ = 0.23) and the PFLR* (_M_ = 79.13%, _SD_ = 2.00) was for the
highest $\epsilon$ and came down to a difference of 3.91. This smallest
difference is also significant (_t_(18) = 6.1, _p_ $<$ .001).

In conclusion, adding differential privacy and fairness to a simple neural
network decreased the average risk difference below the 0.05 threshold. The
average accuracy also decreased but was still well above the 75.4% threshold.
Adding both differential privacy and fairness compared to only adding fairness
increased the accuracy and decreased the risk difference. Adding both
differential privacy and fairness compared to only adding differential privacy
decreased the risk difference and slightly decreased the accuracy. When the
DPF-NN ($\delta$ = 0.00001) is compared to the DPFLR* by Xu, Yuan and Wu
(2019), the DPF-NN achieves a higher average risk difference, though still
under the strict 0.05 threshold, but higher average accuracy for all values of
$\epsilon$.

##  5 Discussion

Four models were compared, a Simple (S-NN), a Fair (F-NN), a Differentially
Private (DP-NN), and a Differentially Private and Fair Neural Network (DPF-
NN). These models were evaluated for different values of $\epsilon$ and
$\delta$ on fairness and utility metrics. The models were compared relative to
each other, to the models by Xu, Yuand and Wu (2019), and to several threshold
values.

Effects of Fairness Constraints on the Fairness-Utility Trade-off.

Adding fairness constraints to the S-NN significantly reduced the mean
accuracy but also significantly decreased the mean risk difference. The F-NN
model achieved a mean risk difference of 0.0566 (_SD_ = 0.0065). This is below
the lenient 0.1 threshold. However, it is close to but not below the strict
0.05 threshold. The achieved accuracy was above the threshold of choosing the
majority label. Reductions in statistical parity also decreased utility when
Reject Option Classification was applied in the research by Hufthammer, et al.
(2020). However, in the research by Briggs and Hollmén (2020), the utility was
improved.

Effects of Privacy Constraints on the Privacy-Utility Trade-off. The
performance of the DP-NN was evaluated for different values of $\epsilon$ and
$\delta$. A linear regression showed that no significant effect on risk
differences or accuracy could be observed as a function of $\epsilon$ and
$\delta$. Furthermore, changing the standard Adam optimizer of the S-NN to the
differentially private optimizer in the DP-NN did not significantly change the
accuracy nor the risk difference when the highest privacy constraints were
applied ($\epsilon$ = 0.1, $\delta$ = 0.00001). This model achieved an
accuracy well above the majority label baseline. The risk difference was above
both the strict and the lenient thresholds, which is expected since no
fairness constraints were added to this model. _Most notably and contrary to
previous results(Zhao et al., 2020; Jayaraman & Evans, 2019; Gong et al.,
2020), no disruption in accuracy was observed when using lower values of
$\epsilon$ and $\delta$._

Effects of Fairness and Privacy Constraints on the Privacy-Utility-Fairness
Trade-off. Like the case of DP-NN, no trend in risk differences or accuracy
was observed for varying values of $\epsilon$ and $\delta$ in the DPF-NN
model. The results on the DPF-NN showed that adding both fairness and a strong
privacy guarantee ($\epsilon$ = 0.1, $\delta$ = 0.00001) to the S-NN model
significantly increased its accuracy. However, this also significantly
decreased risk difference. While the accuracy of the DPF-NN with $\epsilon$ =
0.1 and $\delta$ = 0.00001 was lower, it was still well above the majority
label baseline. The achieved mean risk difference by this model was below both
the strict and lenient thresholds. The model is, therefore, considered fair.
Adding both fairness and differential privacy ($\epsilon$ = 0.1, $\delta$ =
0.00001) significantly increased accuracy compared to only adding fairness,
but it decreased accuracy compared to only adding differential privacy
($\epsilon$ = 0.1, $\delta$ = 0.00001). Adding both differential privacy and
fairness improved fairness compared to adding only differential privacy or
fairness.

Comparison with Equivalent Models. The results from Xu, yuan and Wu (2019)
were used as baselines to compare the performance of the proposed models.

The S-NN achieved a significantly higher mean accuracy and a lower mean risk
difference than the baseline simple model. The F-NN achieved higher accuracy
than the baseline fair model though this difference is not significant. The
F-NN also produced a significantly higher mean risk difference and is,
therefore, deemed less fair. There were no significant changes in risk
difference between the DP-NN with the highest privacy guarantees ($\epsilon$ =
0.1, $\delta$ = 0.00001) and the PFLR* with the highest privacy guarantees
($\epsilon$ = 0.1) by Xu, Yuan and Wu (2019). The DP-NN did, however, achieve
a significantly higher mean accuracy. The DPF-NN with the highest privacy
guarantees ($\epsilon$ = 0.1, $\delta$ = 0.00001) significantly outperformed
the baseline differentially private and fair model with the highest privacy
guarantees ($\epsilon$ = 0.1) on mean accuracy but produced a significantly
higher mean risk difference. It is, thus, less fair but has more utility.

Limitations and Future Research.

In the present work, only the variable ‘sex’ was considered as a sensitive
attribute. However, in many practical applications, multiple sensitive
variables may need to be considered. For example, the models may be considered
fair with respect to gender but still make discriminatory decisions with
respect to race. Likewise, Caton and Haas (2020) also warned of the effects of
variables that are themselves not considered sensitive, but are still related
to sensitive variables. Furthermore, only one fairness metric was considered
in this research, risk difference, which is a measure of
demographic/statistical parity that captures group fairness. As previously
discussed, reduced unfairness according to one metric may not reduce and it
may even increase unfairness according to another metric (Lee & Kizilcec,
2020; Hufthammer et al., 2020; Caton & Haas, 2020). If the models used in this
research would be employed in real-life settings it would, therefore, be
crucial to consider if demographic/statistical parity would be suitable for
the specific application. Related to this are the chosen threshold: for
example, in this research, the limit of risk difference beneath which a model
was deemed fair was 0.05 for the strict threshold and 0.1 for the lenient
threshold. However, whether these thresholds are suitable in a real-life
application may depend on the use case and legislative requirements (Datta et
al., 2018). If the goal of fairness is preferred over utility, the fair and
differentially private and fair logistic regression models by Xu, Yuan and Wu
(2019) should be preferred over the equivalent models presented here.
Likewise, utility may be measured differently in different applications, which
may require using balanced accuracy, F1-score, or other metrics, which might
lead to different model rankings. Additionally, it would be interesting to
assess whether combining pre- and post- processing fairness techniques would
improve results. Lastly, a relaxed notion of differential privacy was
considered in this research, while in some applications, strict or traditional
differential privacy may be preferred.

Lastly, the results achieved by the differentially private and fair model in
this research are encouraging and should be validated on a larger selection of
datasets and using other metrics to assess the privacy-utility-fairness trade-
off.

##  6 Conclusion

In this paper, we explored the impact of differential privacy and fairness
constraints on the privacy-utility-fairness, both when they are applied
independently and when they are combined together. Contrary to the previous
research on this topic, this research focused on neural networks instead of
logistic regression. Applying only fairness constraints led to a model with
high accuracy and fairness but no privacy. Applying only privacy constraints
led to a private but unfair model with high accuracy. The model that combined
privacy and fairness constraints achieved better fairness than the model that
only applied fairness constraints, while maintaining high accuracy. While the
accuracy of the fair and private model significantly improved on previous work
from Xu, Yuan and Wu (2019), the risk difference was found to be worse.
Contrary to previous research both the DP-NN and DPF-NN model did not show a
trend of a decrease in accuracy with an increase in the offered privacy. In
conclusion, creating models that achieve fairness and preserve privacy while
maintaining satisfactory utility is both possible and necessary. Hopefully,
this and other contributions to the existing research on private and fair
models can encourage and improve their use in real-world applications.

## References

  * Bellamy et al. (2018) Bellamy, R. K. E., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martina, J., Mehta, S., Mojsilovic, A., Nagar, S., Ramamurthy, K. N., Richards, J., Saha, D., Sattigeri, P., Singh, M., Varshney, K. R., and Zhang, Y.  AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias.  _https://arxiv.org/abs/1810.01943_ , October 2018.
  * Briggs & Hollmén (2020) Briggs, E. and Hollmén, J.  Mitigating discrimination in clinical machine learning decision support using algorithmic processing techniques.  In _International Conference on Discovery Science_ , pp. 19–33. Springer, 2020.
  * Caton & Haas (2020) Caton, S. and Haas, C.  Fairness in Machine Learning: A Survey.  _arXiv:2010.04053 [cs, stat]_ , October 2020.  arXiv: 2010.04053.
  * Chollet (2015) Chollet, F.  Keras, 2015.  URL https://github.com/fchollet/keras.
  * Corbett-Davies & Goel (2018) Corbett-Davies, S. and Goel, S.  The Measure and Mismeasure of Fairness: A Critical Review of Fair Machine Learning.  _arXiv:1808.00023 [cs]_ , August 2018.  URL http://arxiv.org/abs/1808.00023.  arXiv: 1808.00023.
  * Cummings et al. (2019) Cummings, R., Gupta, V., Kimpara, D., and Morgenstern, J.  On the Compatibility of Privacy and Fairness.  In _Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization - UMAP’19 Adjunct_ , pp. 309–315, Larnaca, Cyprus, 2019. ACM Press.  ISBN 978-1-4503-6711-0.  doi: 10.1145/3314183.3323847.  URL http://dl.acm.org/citation.cfm?doid=3314183.3323847.
  * Datta et al. (2018) Datta, A., Sen, S., and Tschantz, M. C.  Correspondences between Privacy and Nondiscrimination: Why They Should Be Studied Together.  _arXiv:1808.01735 [cs]_ , August 2018.  arXiv: 1808.01735.
  * Ding et al. (2020) Ding, J., Zhang, X., Li, X., Wang, J., Yu, R., and Pan, M.  Differentially private and fair classification via calibrated functional mechanism.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 622–629, 2020.  Issue: 01.
  * Dua & Graff (2017) Dua, D. and Graff, C.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Ekstrand et al. (2018) Ekstrand, M. D., Joshaghani, R., and Mehrpouyan, H.  Privacy for All: Ensuring Fair and Equitable Privacy Protections.  In _Proceedings of Machine learning Research: Conference on Fairness, Accountability, and Transparency_ , pp. 1–13, 2018.
  * Feldman et al. (2015) Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubramanian, S.  Certifying and Removing Disparate Impact.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’15_ , pp. 259–268, Sydney, NSW, Australia, 2015. ACM Press.  ISBN 978-1-4503-3664-2.  doi: 10.1145/2783258.2783311.  URL http://dl.acm.org/citation.cfm?doid=2783258.2783311.
  * Friedler et al. (2019) Friedler, S. A., Scheidegger, C., Venkatasubramanian, S., Choudhary, S., Hamilton, E. P., and Roth, D.  A comparative study of fairness-enhancing interventions in machine learning.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , FAT* ’19, pp. 329–338, New York, NY, USA, January 2019. Association for Computing Machinery.  ISBN 978-1-4503-6125-5.  doi: 10.1145/3287560.3287589.  URL https://doi.org/10.1145/3287560.3287589.
  * Gong et al. (2020) Gong, M., Pan, K., Xie, Y., Qin, A., and Tang, Z.  Preserving differential privacy in deep neural networks with relevance-based adaptive noise imposition.  _Neural Networks_ , 125:131–141, May 2020.  ISSN 08936080.  doi: 10.1016/j.neunet.2020.02.001.  URL https://linkinghub.elsevier.com/retrieve/pii/S0893608020300460.
  * Hajian et al. (2015) Hajian, S., Domingo-Ferrer, J., Monreale, A., Pedreschi, D., and Giannotti, F.  Discrimination- and privacy-aware patterns.  _Data Mining and Knowledge Discovery_ , 29(6):1733–1782, November 2015.  ISSN 1573-756X.  doi: 10.1007/s10618-014-0393-7.  URL https://doi.org/10.1007/s10618-014-0393-7.
  * Hufthammer et al. (2020) Hufthammer, K. T., Aasheim, T. H., Ånneland, S., Brynjulfsen, H., and Slavkovik, M.  Bias mitigation with aif360: A comparative study.  In _Norsk IKT-konferanse for forskning og utdanning_ , number 1, 2020\.
  * Jagielski et al. (2019) Jagielski, M., Kearns, M., Mao, J., Oprea, A., Roth, A., Sharifi-Malvajerdi, S., and Ullman, J.  Differentially Private Fair Learning.  In _International Conference on Machine Learning_ , pp. 3000–3008, 2019.
  * Jayaraman & Evans (2019) Jayaraman, B. and Evans, D.  Evaluating differentially private machine learning in practice.  In _28th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 19)_, pp. 1895–1912, 2019.
  * Kingma & Ba (2017) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization, 2017.
  * Langley (2000) Langley, P.  Crafting papers on machine learning.  In Langley, P. (ed.), _Proceedings of the 17th International Conference on Machine Learning (ICML 2000)_ , pp. 1207–1216, Stanford, CA, 2000\. Morgan Kaufmann.
  * Lee & Kizilcec (2020) Lee, H. and Kizilcec, R. F.  Evaluation of Fairness Trade-offs in Predicting Student Success.  _arXiv:2007.00088 [cs]_ , June 2020.  arXiv: 2007.00088.
  * McMahan et al. (2019) McMahan, H. B., Andrew, G., Erlingsson, U., Chien, S., Mironov, I., Papernot, N., and Kairouz, P.  A General Approach to Adding Differential Privacy to Iterative Training Procedures.  _arXiv:1812.06210 [cs, stat]_ , March 2019.  URL http://arxiv.org/abs/1812.06210.  arXiv: 1812.06210.
  * Wood et al. (2018) Wood, A., Altman, M., Bembenek, A., Bun, M., Gaboardi, M., Honaker, J., Nissim, K., O’Brien, D., Steinke, T., and Vadhan, S.  Differential Privacy: A Primer for a Non-Technical Audience.  _SSRN Electronic Journal_ , 2018.  ISSN 1556-5068.  doi: 10.2139/ssrn.3338027.  URL https://www.ssrn.com/abstract=3338027.
  * Xu et al. (2019) Xu, D., Yuan, S., and Wu, X.  Achieving differential privacy and fairness in logistic regression.  In _Companion Proceedings of The 2019 World Wide Web Conference_ , pp. 594–599, 2019.
  * Yeom et al. (2020) Yeom, S., Giacomelli, I., Menaged, A., Fredrikson, M., and Jha, S.  Overfitting, robustness, and malicious algorithms: A study of potential causes of privacy risk in machine learning.  _Journal of Computer Security_ , 28(1):35–70, February 2020.  ISSN 18758924, 0926227X.  doi: 10.3233/JCS-191362.  URL https://www.medra.org/servlet/aliasResolver?alias=iospress&doi=10.3233/JCS-191362.
  * Zhao et al. (2020) Zhao, B. Z. H., Kaafar, M. A., and Kourtellis, N.  Not one but many Tradeoffs: Privacy Vs. Utility in Differentially Private Machine Learning.  In _Proceedings of the 2020 ACM SIGSAC Conference on Cloud Computing Security Workshop_ , pp. 15–26, Virtual Event USA, November 2020. ACM.  ISBN 978-1-4503-8084-3.  doi: 10.1145/3411495.3421352.  URL https://dl.acm.org/doi/10.1145/3411495.3421352.
  * Zhu et al. (2020) Zhu, T., Ye, D., Wang, W., Zhou, W., and Yu, P. S.  More than privacy: applying differential privacy in key areas of artificial intelligence.  _arXiv preprint arXiv:2008.01916_ , 2020.