Prediction from statistical models

Let’s proceed to formalize prediction assuming we have full knowledge of a statistical model of the population. Our first goal is to formally develop the minimum error rule in greater generality.

We begin with binary prediction where we suppose Y has two alternative values, 0 and 1. Given some measured information X, our goal is to conjecture whether Y equals zero or one.

Throughout we assume that X and Y are random variables drawn from a joint probability distribution. It is convenient both mathematically and conceptually to specify the joint distribution as follows. We assume that Y has a priori (or prior) probabilities: p_0 = \mathop\mathbb{P}[Y=0]\,, \qquad p_1 = \mathop\mathbb{P}[Y=1] That is, we assume we know the proportion of instances with Y=1 and Y=0 in the population. We’ll always model available information as being a random vector X with support in \mathbb{R}^d. Its distribution depends on whether Y is equal to zero or one. In other words, there are two different statistical models for the data, one for each value of Y. These models are the conditional probability densities of X given a value y for Y, denoted p(x \mid Y=y). This density function is often called a generative model or likelihood function for each scenario.

Example: signal versus noise

For a simple example with more mathematical formalism, suppose that when Y=0 we observe a scalar X=\omega where \omega is unit-variance, zero mean Gaussian noise \omega\sim \mathcal{N}(0,1). Recall that the Gaussian distribution of mean \mu and variance \sigma^2 is given by the density \frac{1}{\sigma\sqrt{2\pi}}e^{-\frac12\left(\frac{x-\mu}{\sigma}\right)^2}.

Suppose when Y=1, we would observe X=s+\omega for some scalar s. That is, the conditional densities are \begin{aligned} p(x\mid Y=0) &= \mathcal{N}(0,1) \,, \\ p(x\mid Y=1) &= \mathcal{N}(s,1)\,. \end{aligned} The larger the shift s is, the easier it is to predict whether Y=0 or Y=1. For example, suppose s=10 and we observed X=11. If we had Y=0, the probability that the observation is greater than 10 is on the order of 10^{-23}, and hence we’d likely think we’re in the alternative scenario where Y=1. However, if s were very close to zero, distinguishing between the two alternatives is rather challenging. We can think of a small difference s that we’re trying to detect as a needle in a haystack.

Predictors and labels

A predictor is a function \hat Y(x) that maps an input x to a prediction \hat y=\hat Y(x). The prediction \hat y is also called a label for the point x. The target variable Y can be both real valued or discrete. When Y is a discrete random variable, each different value it can take on is called a class of the prediction problem.

To ease notation, we take the liberty to write \hat Y as a shorthand for the random variable \hat Y(X) that we get by applying the prediction function \hat Y to the random variable X.

The most common case we consider through the book is binary prediction, where we have two classes, 0 and 1. Sometimes it’s mathematically convenient to instead work with the numbers -1 and 1 for the two classes.

In most cases we consider, labels are scalars that are either discrete or real-valued. Sometimes it also makes sense to consider vector-valued predictions and target variables.

The creation and encoding of suitable labels for a prediction problem is an important step in applying machine learning to real world problems. We will return to it multiple times.

Loss functions and risk

The final ingredient in our formal setup is a loss function which generalizes the notion of an error that we defined as a mismatch between prediction and target value.

A loss function takes two inputs, \hat y and y, and returns a real number \mathit{loss}(\hat y, y) that we interpret as a quantified loss for predicting \hat y when the target is y. A loss could be negative in which case we think of it as a reward.

A prediction error corresponds to the loss function \mathit{loss}(\hat y, y)=\mathbb{1}\{\hat y \ne y\} that indicates disagreement between its two inputs. Loss functions give us modeling flexibility that will become crucial as we apply this formal setup throughout this book.

An important notion is the expected loss of a predictor taken over a population. This construct is called risk.

Now that we defined risk, our goal is to determine which decision rule minimizes risk. Let’s get a sense for how we might go about this.

In order to minimize risk, theoretically speaking, we need to solve an infinite dimensional optimization problem over binary-valued functions. That is, for every x, we need to find a binary assignment. Fortunately, the infinite dimension here turns out to not be a problem analytically once we make use of the law of iterated expectation.

This rule corresponds to the intuitive rule we derived when thinking about how to make predictions over the population. For a fixed value of the data X=x, we compare the frequency of which Y=1 occurs to which Y=0 occurs. If this frequency exceeds some threshold that is defined by our loss function, then we set \hat{Y}(x)=1. Otherwise, we set \hat{Y}(x)=0.

Probabilities of the form \mathop\mathbb{P}[Y=y\mid X=x], as they appeared in the lemma, are called posterior probability.

We can relate them to the likelihood function via Bayes rule: \mathop\mathbb{P}[Y=y\mid X=x] = \frac{p(x\mid Y=y) p_y }{p(x)}\,, where p(x) is a density function for the marginal distribution of X.

When we use posterior probabilities, we can rewrite the optimal predictor as \hat {Y}(x) = \mathbb{1}\left\{ \frac{p(x\mid Y=1)}{p(x\mid Y=0)} \geq \frac{p_0(\mathit{loss}(1,0)-\mathit{loss}(0,0))}{p_1(\mathit{loss}(0,1)-\mathit{loss}(1,1))}\right\}\,. This rule is an example of a likelihood ratio test.

If we denote the optimal threshold value \eta = \frac{p_0(\mathit{loss}(1,0)-\mathit{loss}(0,0))}{p_1(\mathit{loss}(0,1)-\mathit{loss}(1,1))}\,,\qquad(1) then the predictor that minimizes the risk is the likelihood ratio test \hat{Y}(x) = \mathbb{1}\{ \mathcal{L}(x)\geq \eta \}\,.

A LRT naturally partitions the sample space in two regions: \begin{aligned} \mathcal{X}_0 & = \left\{ x \in \mathcal{X} \colon \mathcal{L}(x) \leq \eta \right\}\\ \mathcal{X}_1 &= \left\{ x \in \mathcal{X} \colon \mathcal{L}(x) > \eta \right\}\,. \end{aligned} The sample space \mathcal{X} then becomes the disjoint union of \mathcal{X}_0 and \mathcal{X}_1. Since we only need to identify which set x belongs to, we can use any function h:\mathcal{X} \rightarrow \mathbb{R} which gives rise to the same threshold rule. As long as h(x) \leq t whenever \mathcal{L}(x) \leq \eta and vice versa, these functions give rise to the same partition into \mathcal{X}_0 and \mathcal{X}_1. So, for example, if g is any monotonically increasing function, then the predictor \hat{Y}_g(x) = \mathbb{1} \{ g(\mathcal{L}(x))\geq g(\eta) \} is equivalent to using \hat{Y}(x). In particular, it’s popular to use the logarithmic predictor \hat{Y}_{\mathrm{log}}(x) = \mathbb{1} \{\log p(x\mid Y=1)- \log p(x\mid Y=0) \geq \log(\eta)\}\,, as it is often more convenient or numerically stable to work with logarithms of likelihoods.

This discussion shows that there are an infinite number of functions which give rise to the same binary predictor. Hence, we don’t need to know the conditional densities exactly and can still compute the optimal predictor. For example, suppose the true partitioning of the real line under an LRT is \mathcal{X}_0 = \{x\colon x\geq 0\}\quad\text{and}\quad\mathcal{X}_1 = \{x\colon x< 0\}\,. Setting the threshold to t=0, the functions h(x) = x or h(x)=x^3 give the same predictor, as does any odd function which is positive on the right half line.

Example: needle in a haystack revisited

Let’s return to our needle in a haystack example with \begin{align*} p(X\mid Y=0) &= \mathcal{N}(0,1)\,,\\ p(X\mid Y=1) &= \mathcal{N}(s,1)\,, \end{align*} and assume that the prior probability of Y=1 is very small, say, p_1 = 10^{-6}. Suppose that if we declare \hat{Y}=0, we do not pay a cost. If we declare \hat{Y}=1 but are wrong, we incur a cost of 100. But if we guess \hat{Y}=1 and it is actually true that Y=1, we actually gain a reward of 1,000,000. That is \mathit{loss}(0,0) = 0, \mathit{loss}(0,1)=0, \mathit{loss}(1,0) = 100, and \mathit{loss}(1,1)=-1,000,000\,.

What is the LRT for this problem? Here, it’s considerably easier to work with logarithms: \log(\eta) = \log\left( \frac{(1-10^{-6}) \cdot 100}{10^{-6} \cdot 10^{6}}\right) \approx 4.61 Now, \log p(x\mid Y=1)- \log p(x\mid Y=0) = -\frac{1}{2} (x-s)^2 + \frac{1}{2} x^2 = sx-\frac{1}{2}s^2 Hence, the optimal predictor is to declare \hat{Y}= \mathbb{1}\left\{ sx > \tfrac{1}{2}s^2+\log(\eta) \right\}\,. The optimal rule here is linear. Moreover, the rule divides the space into two open intervals. While the entire real line lies in the union of these two intervals, it is exceptionally unlikely to ever see an x larger than |s|+5. Hence, even if our predictor were incorrect in these regions, the risk would still be nearly optimal as these terms have almost no bearing on our expected risk!

Maximum a posteriori and maximum likelihood

A folk theorem of statistical decision theory states that essentially all optimal rules are equivalent to likelihood ratio tests. While this isn’t always true, many important prediction rules end up being equivalent to LRTs. Shortly, we’ll see an optimization problem that speaks to the power of LRTs. But before that, we can already show that the well known maximum likelihood and maximum a posteriori predictors are both LRTs.

The expected error of a predictor is the expected number of times we declare \hat{Y}=0 (resp. \hat{Y}=1) when \hat{Y}=1 (resp. \hat{Y}=0) is true. Minimizing the error is equivalent to minimizing the risk with cost \mathit{loss}(0,0)=\mathit{loss}(1,1)=0, \mathit{loss}(1,0)=\mathit{loss}(0,1)=1. The optimum predictor is hence a likelihood ratio test. In particular, \hat{Y}(x) =\mathbb{1}\left\{ \mathcal{L}(x) \geq \tfrac{p_0}{p_1}\right\}\,. Using Bayes rule, one can see that this rule is equivalent to \hat{Y}(x) = \arg \max_{y\in\{0,1\}}\mathop\mathbb{P}[Y=y\mid X=x]\,. Recall that the expression \mathop\mathbb{P}[Y=y\mid X=x] is called the posterior probability of Y=y given X=x. And this rule is hence referred to as the maximum a posteriori (MAP) rule.

As we discussed above, the expression p(x\mid Y=y) is called the likelihood of the point x given the class Y=y. A maximum likelihood rule would set \hat{Y}(x) = \arg \max_y p(x\mid Y=y)\,. This is completely equivalent to the LRT when p_0=p_1 and the costs are \mathit{loss}(0,0)=\mathit{loss}(1,1)=0, \mathit{loss}(1,0)=\mathit{loss}(0,1)=1. Hence, the maximum likelihood rule is equivalent to the MAP rule with a uniform prior on the labels.

That both of these popular rules ended up reducing to LRTs is no accident. In what follows, we will show that LRTs are almost always the optimal solution of optimization-driven decision theory.

ROC curves

True and false positive rate lead to another fundamental notion, called the receiver operating characteristic (ROC) curve.

The ROC curve is a property of the joint distribution (X, Y) and shows for every possible value \alpha=[0, 1] the best possible true positive rate that we can hope to achieve with any predictor that has false positive rate \alpha. As a result the ROC curve is a curve in the FPR-TPR plane. It traces out the maximal TPR for any given FPR. Clearly the ROC curve contains values (0,0) and (1,1), which are achieved by constant predictors that either reject or accept all inputs.

We will now show, in a celebrated result by Neyman and Pearson, that the ROC curve is given by varying the threshold in the likelihood ratio test from negative to positive infinity.

Properties of ROC curves

A specific randomized predictor that is useful for analysis combines two other rules. Suppose predictor one yields (\mathrm{FPR}^{(1)},\mathrm{TPR}^{(1)}) and the second rule achieves (\mathrm{FPR}^{(2)},\mathrm{TPR}^{(2)}). If we flip a biased coin and use rule one with probability p and rule 2 with probability 1-p, then this yields a randomized predictor with (\mathrm{FPR},\mathrm{TPR}) = (p\mathrm{FPR}^{(1)}+(1-p)\mathrm{FPR}^{(2)} ,p \mathrm{TPR}^{(1)}+(1-p)\mathrm{TPR}^{(2)}). Using this rule lets us prove several properties of ROC curves.

The Neyman-Pearson Lemma gives us a few more useful properties.

Example: the needle one more time

Consider again the needle in a haystack example, where p(x\mid Y=0) = \mathcal{N}(0,\sigma^2) and p(x\mid Y=1) = \mathcal{N}(s,\sigma^2) with s a positive scalar. The optimal predictor is to declare \hat{Y}=1 when X is greater than \gamma:= \frac{s}{2} + \frac{\sigma^2 \log \eta}{s}. Hence we have \begin{aligned} \mathrm{TPR} &= \int_{\gamma}^{\infty} p(x\mid Y=1) \,\mathrm{d}x = \tfrac{1}{2} \operatorname{erfc} \left(\frac{\gamma-s}{\sqrt{2}\sigma}\right)\\ \mathrm{FPR} &= \int_{\gamma}^{\infty} p(x\mid Y=0) \,\mathrm{d}x = \tfrac{1}{2} \operatorname{erfc} \left(\frac{\gamma}{\sqrt{2}\sigma}\right)\,. \end{aligned}

For fixed s and \sigma, the ROC curve (\mathrm{FPR}(\gamma),\mathrm{TPR}(\gamma)) only depends on the signal to noise ratio (SNR), s/\sigma. For small SNR, the ROC curve is close to the \mathrm{FPR}=\mathrm{TPR} line. For large SNR, \mathrm{TPR} approaches 1 for all values of \mathrm{FPR}.

Area under the ROC curve

Oftentimes in information retrieval and machine learning, the term ROC curve is overloaded to describe the achievable FPR-TPR pairs that we get by varying the threshold t in any predictor \hat Y(x) = \mathbb{1}\{ R(x) > t\}. Note such curves must lie below the ROC curves that are traced out by the optimal likelihood ratio test, but may approximate the true ROC curves in many cases.

A popular summary statistic for evaluating the quality of a decision function is the area under its associated ROC curve. This is commonly abbreviated as AUC. In the ROC curve plotted in the previous section, as the SNR increases, the AUC increases. However, AUC does not tell the entire story. Here we plot two ROC curves with the same AUC.

If we constrain \mathrm{FPR} to be less than 10%, for the blue curve, \mathrm{TPR} can be as high as 80% whereas it can only reach 50% for the red. AUC should be always viewed skeptically: the shape of an ROC curve is always more informative than any individual number.

Legal background in the United States

The legal frameworks governing decision making differ from country to country, and from one domain to another. We take a glimpse at the situation in the United States, bearing in mind that our description is incomplete and does not transfer to other countries.

Discrimination is not a general concept. It is concerned with socially salient categories that have served as the basis for unjustified and systematically adverse treatment in the past. United States law recognizes certain protected categories including race, sex (which extends to sexual orientation), religion, disability status, and place of birth.

Further, discrimination is a domain specific concept concerned with important opportunities that affect people’s lives. Regulated domains include credit (Equal Credit Opportunity Act), education (Civil Rights Act of 1964; Education Amendments of 1972), employment (Civil Rights Act of 1964), housing (Fair Housing Act), and public accommodation (Civil Rights Act of 1964). Particularly relevant to machine learning practitioners is the fact that the scope of these regulations extends to marketing and advertising within these domains. An ad for a credit card, for example, allocates access to credit and would therefore fall into the credit domain.

There are different legal frameworks available to a plaintiff that brings forward a case of discrimination. One is called disparate treatment, the other is disparate impact. Both capture different forms of discrimination. Disparate treatment is about purposeful consideration of group membership with the intention of discrimination. Disparate impact is about unjustified harm, possibly through indirect mechanisms. Whereas disparate treatment is about procedural fairness, disparate impact is more about distributive justice.

It’s worth noting that anti-discrimination law does not reflect one overarching moral theory. Pieces of legislation often came in response to civil rights movements, each hard fought through decades of activism.

Unfortunately, these legal frameworks don’t give us a formal definition that we could directly apply. In fact, there is some well-recognized tension between the two doctrines.

Formal non-discrimination criteria

The idea of formal non-discrimination (or fairness) criteria goes back to pioneering work of Anne Cleary and other researchers in the educational testing community of the 1960s.Hutchinson and Mitchell, “50 Years of Test (Un) Fairness: Lessons for Machine Learning,” in Conference on Fairness, Accountability, and Transparency, 2019, 49–58.

The main idea is to introduce a discrete random variable A that encodes membership status in one or multiple protected classes. Formally, this random variable lives in the same probability space as the other covariates X, the decision \hat Y=\mathbb{1}\{ R > t\} in terms of a score R, and the outcome Y. The random variable A might coincide with one of the features in X or correlate strongly with some combination of them.

Broadly speaking, different statistical fairness criteria all equalize some group-dependent statistical quantity across groups defined by the different settings of A. For example, we could ask to equalize acceptance rates across all groups. This corresponds to imposing the constraint for all groups a and b:

\mathop\mathbb{P}[\hat Y = 1 \mid A=a] = \mathop\mathbb{P}[\hat Y = 1 \mid A=b]

Researchers have proposed dozens of different criteria, each trying to capture different intuitions about what is fair. Simplifying the landscape of fairness criteria, we can say that there are essentially three fundamentally different ones of particular significance:

• Acceptance rate \mathop\mathbb{P}[\hat Y = 1]
• Error rates \mathop\mathbb{P}[\hat Y = 0 \mid Y = 1] and \mathop\mathbb{P}[\hat Y = 1 \mid Y =0]
• Outcome frequency given score value \mathop\mathbb{P}[Y = 1 \mid R = r ]

The meaning of the first two as a formal matter is clear given what we already covered. The third criterion needs a bit more motivation. A useful property of score functions is calibration which asserts that \mathop\mathbb{P}[Y = 1\mid R=r]=r for all score values r. In words, we can interpret a score value r as the propensity of positive outcomes among instances assigned the score value r. What the third criterion says is closely related. We ask that the score values have the same meaning in each group. That is, instances labeled r in one group are equally likely to be positive instances as those scored r in any other group.

The three criteria can be generalized and simplified using three different conditional independence statements.

Each of these applies not only to binary prediction, but any set of random variables where the independence statement holds. It’s not hard to see that independence implies equality of acceptance rates across groups. Separation implies equality of error rates across groups. And sufficiency implies that all groups have the same rate of positive outcomes given a score value.Barocas, Hardt, and Narayanan, Fairness and Machine Learning (fairmlbook.org, 2019).

Researchers have shown that any two of the three criteria are mutually exclusive except in special cases. That means, generally speaking, imposing one criterion forgoes the other two.Kleinberg, Mullainathan, and Raghavan, “Inherent Trade-Offs in the Fair Determination of Risk Scores,” in Innovations in Theoretical Computer Science, 2017; Chouldechova, “Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments,” Big Data 5, no. 2 (2017): 153–63.

Although these formal criteria are easy to state and arguably natural in the language of decision theory, their merit as measures of discrimination has been subject of an ongoing debate.

Merits and limitations of a narrow statistical perspective

The tension between these criteria played out in a public debate around the use of risk scores to predict recidivism in pre-trial detention decisions.

There’s a risk score, called COMPAS, used by many jurisdictions in the United States to assess risk of recidivism in pre-trial bail decisions. Recidivism refers to a person’s relapse into criminal behavior. In the United States, a defendant may either be detained or released on bail prior to the trial in court depending on various factors. Judges may detain defendants in part based on this score.

Investigative journalists at ProPublica found that Black defendants face a higher false positive rate, i.e., more Black defendants labeled high risk end up not committing a crime upon release than among White defendants labeled high risk.Angwin et al., “Machine Bias,” ProPublica, May 2016, https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing. In other words, the COMPAS score fails the separation criterion.

A company called Northpointe, which sells the proprietary COMPAS risk model, pointed out in return that Black and White defendants have equal recidivism rates given a particular score value. That is defendants labeled, say, an ‘8’ for high risk would go on to recidivate at a roughly equal rate in either group. Northpointe claimed that this property is desirable so that a judge can interpret scores equally in both groups.Dieterich, Mendoza, and Brennan, “COMPAS Risk Scales: Demonstrating Accuracy Equity and Predictive Parity” (Northpointe Inc. Research Department, 2016), https://www.documentcloud.org/documents/2998391-ProPublica-Commentary-Final-070616.html.

The COMPAS debate illustrates both the merits and limitations of the narrow framing of discrimination as a classification criterion.

On the hand, the error rate disparity gave ProPublica a tangible and concrete way to put pressure on Northpointe. The narrow framing of decision making identifies the decision maker as responsible for their decisions. As such, it can be used to interrogate and possibly intervene in the practices of an entity.

On the other hand, decisions are always part of a broader system that embeds structural patterns of discrimination. For example, a measure of recidivism hinges crucially on existing policing patterns. Crime is only found where policing activity happens. However, the allocation and severity of police force itself has racial bias. Some scholars therefore find an emphasis on statistical criteria rather than structural determinants of discrimination to be limited.