. Author manuscript; available in PMC: 2015 Aug 12.

Published in final edited form as: Electron J Stat. 2015;9(1):1583–1607. doi: 10.1214/15-EJS1035

Computationally efficient confidence intervals for cross-validated area under the ROC curve estimates

Erin LeDell ^1,^✉, Maya Petersen ^1,^†, Mark van der Laan ^1,^‡

PMCID: PMC4533123 NIHMSID: NIHMS699307 PMID: 26279737

Abstract

In binary classification problems, the area under the ROC curve (AUC) is commonly used to evaluate the performance of a prediction model. Often, it is combined with cross-validation in order to assess how the results will generalize to an independent data set. In order to evaluate the quality of an estimate for cross-validated AUC, we obtain an estimate of its variance. For massive data sets, the process of generating a single performance estimate can be computationally expensive. Additionally, when using a complex prediction method, the process of cross-validating a predictive model on even a relatively small data set can still require a large amount of computation time. Thus, in many practical settings, the bootstrap is a computationally intractable approach to variance estimation. As an alternative to the bootstrap, we demonstrate a computationally efficient influence curve based approach to obtaining a variance estimate for cross-validated AUC.

Keywords and phrases: AUC, binary classification, confidence intervals, cross-validation, influence curve, influence function, machine learning, model selection, ROC, variance estimation

1. Introduction

The area under the ROC curve, or AUC, is a ranking-based measure of performance in binary classification problems. Its value can be interpreted as the probability that a randomly selected positive sample will rank higher than a randomly selected negative sample. AUC is a more discriminating performance measure than accuracy [1], and is invariant to relative class distributions [2].

In practice, we are generally concerned with how well our results will generalize to new data. Cross-validation is a means of obtaining an estimate that is generalizable to data drawn from the same distribution but not used in the training set. Common types of cross-validation procedures include V-fold [3], leave-one-out [21, 7, 3], and leave-p-out [20] cross-validation. Given the advantages of AUC as a performance measure, along with the desire to produce generalizable results, cross-validated AUC is frequently used in binary classification problems.

An important task in any estimation procedure is rigorously quantifying the uncertainty in the estimates. In many cases, specification of a parametric model known to contain the truth is not possible, and approaches to inference which are robust to model misspecification are therefore needed. Two approaches to robust inference include inference based on resampling methods, and inference based on influence curves (also known as influence functions). In practice, resampling methods such as the nonparametric bootstrap [11, 12], are commonly used due to their generic nature and simplicity. However, when data sets are large or when methods for training a prediction model are complex, bootstrapping can quickly become a computationally prohibitive procedure.

Although cross-validation lends itself well to parallelization, it can still take a very long time to generate a cross-validated performance measure, such as cross-validated AUC, depending on the complexity of the algorithm used to train the prediction model or the size of the training set. In machine learning, ensemble methods are prediction methods that make use of, or combine, several or many candidate learning algorithms to obtain better predictive performance. This boost in performance is often accompanied by an increase in the time it takes to generate cross-validated predictions. Alternatively, given massive data sets, even simple prediction methods can be computationally expensive. In cases where obtaining a single estimate of cross-validated AUC requires a significant amount of time and/or resources, the bootstrap is either not an option, or at the very least, a undesirable option for obtaining variance estimates.

As a response to the computational costs of the bootstrap, variations of the bootstrap have been developed that achieve a more desirable computational footprint, such as the “m out of n bootstrap” [9] and subsampling [19]. Another recent advancement that has been made in this area is the “Bag of Little Bootstraps” (BLB) method [4]. Unlike previous variations, BLB simultaneously addresses computational costs, statistical correctness and automation, which appears to be a promising generalized method for variance estimation on massive data sets.

Regardless of the reduction in computation that different variations of the bootstrap offer, all bootstrapping variants require repeated estimation on at least some subset of the original data. By using influence curves for variance estimation, we avoid the need to re-estimate our parameter of interest, which in the case of cross-validated AUC, requires fitting additional models. In order to estimate variance using influence curves, you must first, unsurprisingly, calculate the influence curve for your estimator. For complex estimators, it can be a difficult task to derive the influence curve. However, once the derivation is complete, variance estimation is reduced to a simple and computationally negligible calculation. This is the main motivation for our use of influence curves as a means of variance estimation.

The main goal of this paper is to establish an influence curve based approach for estimating the asymptotic variance of the cross-validated area under the ROC curve estimator. We first define true cross-validated AUC along with a corresponding estimator and then provide a brief overview of influence curve based variance estimation. We derive the influence curve for the AUC of both i.i.d. data and pooled repeated measures data (multiple observations per independent sampling unit, such as a patient), and demonstrate the construction of influence curve based confidence intervals. We conclude with a simulation that evaluates the coverage probability of the confidence intervals and provide a comparison to bootstrapped based confidence intervals. The methods are implemented in a publicly available R package called cvAUC [16].

2. Cross-validated AUC as a target parameter

In this section, we formally introduce AUC. We then define the estimator for cross-validated AUC, as well as the target that it is estimating, the true cross-validated AUC.

Consider some probability distribution, P₀, that is known to be an element of a statistical model, Inline graphic . Let O = (W, Y) ~ P₀ ∈ , where Y is a binary outcome variable, and W represents one or more covariates or predictor variables (design matrix). Without loss of generality, we will denote Y = 1 as the positive class and Y = 0 as the negative class, and ψ as a function that maps W into (0, 1). The quantity, ψ(W), is the predicted value or score of a sample. The Area Under the ROC curve can be defined as the following:

AUC (P_{0}, ψ) = \int_{0}^{1} P_{0} (ψ (W) > c ∣ Y = 1) P_{0} (ψ (W) = c ∣ Y = 0) d c .

(2.1)

Alternatively, we can define AUC as

AUC (P_{0}, ψ) = P_{0} (ψ (W_{1}) > ψ (W_{2}) ∣ Y_{1} = 1, Y_{2} = 0),

(2.2)

where (W₁, Y₁) and (W₂, Y₂) are i.i.d. samples from P₀. The quantity, AUC(P₀, ψ), the true AUC, equals the probability, conditional on sampling two independent observations where one is positive (Y₁ = 1) and the other is negative (Y₂ = 0), that the predicted value (or rank) of the positive sample, ψ(W₁), is higher than the predicted value (or rank) of the negative sample, ψ(W₂).

Consider O₁, …, O_n, i.i.d. samples from P₀, such that O_i = (W_i, Y_i) for each i, and let P_n denote the empirical distribution. Let n₀ be the number of observations with Y = 0 and let n₁ be the number of observations with Y = 1. In machine learning, the ψ function is what is learned by a binary prediction algorithm using the training data. The AUC of the empirical distribution can be written as follows:

\begin{array}{l} AUC (P_{n}, ψ) = \frac{1}{n_{0} n_{1}} \sum_{i = 1}^{n} \sum_{j = 1}^{n} I (ψ (W_{j}) > ψ (W_{i})) I (Y_{i} = 0, Y_{j} = 1) \\ = \frac{1}{n_{0} n_{1}} \sum_{i = 1}^{n_{0}} \sum_{j = 1}^{n_{1}} I (ψ (W_{j}) > ψ (W_{i})), \end{array}

where I is the indicator function.

We focus on estimating cross-validated AUC. We do not require that the cross-validation be any particular type; however, in practice, V-fold is common. We will use a generalized notation to encode the data splitting procedure, where a binary indicator vector is used to specify which observations belong to the validation set at each iteration of the cross-validation process. Let $B_{n}^{1}, \dots, B_{n}^{V}$ be the collection of random splits that define our cross-validation procedure, where $B_{n}^{v} \in {0, 1}^{n}$ . In the case of V-fold cross-validation, each of the $B_{n}^{v}$ encodes a single fold; the v^th validation fold is the set of observations indexed by {i : $B_{n}^{v} (i) = 1$ }, and the remaining observations belong to the v^th training set, {i : $B_{n}^{v} (i) = 0$ }.

Let Inline graphic denote a nonparametric model that includes the empirical distribution, P_n, and let Ψ̂ : → ℝ be an estimator of target parameter, ψ₀ true cross-validated AUC. We assume that Ψ̂(P₀) = ψ₀.

For each $B_{n}^{v}$ , we define $ψ_{B_{n}^{v}} = \hat{Ψ} (P_{n, B_{n}^{v}}^{0})$ , where $P_{n, B_{n}^{v}}^{0}$ is the empirical distribution of the observations contained in the v^th training set. The function $ψ_{B_{n}^{v}}$ , which is learned from the vt^h training set, will be used to generate predicted values for the observations in the v^th validation fold. We define $n_{1}^{v}$ and $n_{0}^{v}$ to be the number of positive and negative samples in the v^th validation fold, respectively. Formally, $n_{1}^{v} = \sum_{i = 1}^{n} I (Y_{i} = 1) I (B_{n}^{v} (i) = 1)$ and $n_{0}^{v} = \sum_{i = 1}^{n} I (Y_{i} = 0) I (B_{n}^{v} (i) = 1)$ , We note that $n_{1}^{v}$ and $n_{0}^{v}$ are random variables that depend on the value of both $B_{n}^{v}$ and {Yi : $B_{n}^{v} (i) = 1$ }. The AUC for a single validation fold, {i : $B_{n}^{v} (i) = 1$ }, is:

AUC (P_{n, B_{n}^{v}}^{1}, ψ_{B_{n}^{v}}) = \frac{1}{n_{0}^{v} n_{1}^{v}} \sum_{i = 1}^{n} \sum_{j = 1}^{n} I (ψ_{B_{n}^{v}} (W_{j}) > ψ_{B_{n}^{v}} (W_{i})) I (Y_{i} = 0, Y_{j} = 1) I (B_{n}^{v} (i) = B_{n}^{v} (j) = 1) .

Then the V-fold cross-validated AUC estimator is defined as:

\begin{array}{l} E_{B_{n}} AUC (P_{n, B_{n}}^{1}, ψ_{B_{n}}) = \frac{1}{V} \sum_{v = 1}^{V} AUC (P_{n, B_{n}}^{1}, ψ_{B_{n}^{v}}) \\ = \frac{1}{V} \sum_{v = 1}^{V} \frac{1}{n_{0}^{v} n_{1}^{v}} \sum_{i = 1}^{n} \sum_{j = 1}^{n} I (ψ_{B_{n}^{v}} (W_{j}) > ψ_{B_{n}^{v}} (W_{i})) \times I (Y_{i} = 0, Y_{j} = 1) I (B_{n}^{v} (i) = B_{n}^{v} (j) = 1) . \end{array}

(2.3)

The target, ψ₀, of the V-fold cross-validated AUC estimator is defined as:

\begin{array}{l} E_{B_{n}} AUC (P_{0}, ψ_{B_{n}}) = \frac{1}{V} \sum_{v = 1}^{V} AUC (P_{0}, ψ_{B_{n}^{v}}) \\ = \frac{1}{V} \sum_{v = 1}^{V} P_{0} (ψ_{B_{n}^{v}} (W_{1}) > ψ_{B_{n}^{v}} (W_{2}) ∣ Y_{1} = 1, Y_{2} = 0), \end{array}

(2.4)

where (W₁, Y₁) and (W₂, Y₂) are i.i.d. samples from P₀. In other words, our target parameter, the true cross-validated AUC, corresponds to fitting the prediction function on each training set, evaluating its true performance (or true probability of correctly ranking two randomly selected observations, where one is a positive sample and the other a negative sample) in the corresponding validation set, and finally, taking the average over the validation sets. The true value of this target parameter is random, in that it depends on the split of the sampled data into training sets and corresponding fits of the prediction function. We now wish to construct confidence intervals for our estimator of cross-validated AUC, $E_{B_{n}} AUC (P_{n, B_{n}}^{1}, ψ_{B_{n}})$ .

3. Influence curves for variance estimation

We provide a brief overview of influence curves and their relation to variance estimation. We outline the general procedure for obtaining confidence intervals using the influence curve of an estimator. This section serves as a gentle introduction to concepts and notation used throughout the paper.

Suppose that O ≡ O₁, …, O_n are i.i.d. samples from a probability distribution, P₀, that is known to be an element of a statistical model, Inline graphic . Let be some class of functions of O. Throughout this paper, we will use the notation Pf, where P is a probability distribution, to denote ∫ f(x)dP (x). We consider the empirical process, (P₀f : f ∈ ), which is a “vector” of true means. Let Ψ : → ℝ^d be a parameter of interest, and let ψ₀ = Ψ(P₀) ≡ Ψ(P₀f : f ∈ Inline graphic ) be the true parameter value; ψ₀ is a function of true means. Now let denote a nonparametric model that includes the empirical distribution, P_n, of O₁, …, O_n. We consider the empirical process, (P_nf : f ∈ ), which is a “vector” of empirical means. Let Ψ̂ : Inline graphic → ℝ^d be an estimator of ψ₀ that maps the empirical distribution, P_n, or rather, a “vector” of empirical means, into an estimate Ψ̂(P_n) ≡ Ψ̂(P_nf : f ∈ ). We assume that Ψ̂(P₀) = ψ₀, so that the estimator targets the desired target parameter, ψ₀. This estimate is asymptotically linear at P₀ if

\hat{Ψ} (P_{n}) - \hat{Ψ} (P_{0}) = \frac{1}{n} \sum_{i = 1}^{n} I C (P_{0}) (O_{i}) + o_{P} (1 / \sqrt{n})

(3.1)

for some zero-mean function, IC(P₀), of O (i.e. P₀IC(P₀) = 0). The function, IC(P₀), is called the influence curve (or influence function) of the estimator, Ψ. The main task in the process of constructing influence curve based confidence intervals is demonstrating the asymptotic linearity of your estimator.

By the Central Limit Theorem, we find that $\sqrt{n} (\hat{Ψ} (P_{n}) - \hat{Ψ} (P_{0})) \overset{d}{\to} N (0, \sum_{0})$ , where Σ₀ = P₀IC(P₀)IC(P₀)^T. This covariance matrix can be estimated with the empirical covariance matrix $\hat{I C} (O_{i})$ , i = 1, …, n where $\hat{I C}$ is an estimate of IC(P₀). When our target parameter is one-dimensional, as in cross-validated AUC, we can write the following:

\sqrt{n} (\hat{Ψ} (P_{n}) - \hat{Ψ} (P_{0})) \overset{d}{\to} N (0, Φ^{2} (P_{0})),

(3.2)

where Φ²(P₀) = ∫ IC(P₀)(x)²dP₀(x). We can estimate Φ²(P₀) as

Φ_{n}^{2} \equiv Φ^{2} (P_{n}) = \frac{1}{n} \sum_{i = 1}^{n} I C (P_{n}) {(O_{i})}^{2},

(3.3)

however, other estimators of the variance of the influence curve can be considered. Letting z_r denote the r^th quantile of the standard normal distribution, it follows that for any estimate $Φ_{n}^{2} \equiv Φ^{2} (P_{n})$ of ϕ²(P₀), we have that

(\hat{Ψ} (P_{n}) - z_{1 - α / 2} \frac{Φ_{n}}{\sqrt{n}}, \hat{Ψ} (P_{n}) + z_{1 - α / 2} \frac{Φ_{n}}{\sqrt{n}})

(3.4)

forms an approximate 100 × (1 − α)% confidence interval for ψ₀ ≡ Ψ̂(P₀).

In order to assume that asymptotically linear estimators of ψ₀ exist, we must assume that the parameter Ψ is pathwise differentiable [10]. This method for establishing the asymptotic linearity and normality of the estimator is called the functional delta method [22, 14], which is a generalization of the classical delta method for finite dimensional functions of a finite set of estimators.

4. Confidence intervals for cross-validated AUC

In this section, we establish the influence curve for AUC and show that the empirical AUC is an asymptotically linear estimator of the true AUC. Using these results, we follow the methodology from Section 3 to derive confidence intervals for cross-validated AUC. Then we provide a description of the practical construction of the confidence intervals from an i.i.d. data sample.

Theorem 4.1

Let O = (W, Y) ~ P₀, where W represents one or more variables and Y is binary. Without loss of generality, assume Y ∈ {0, 1} and that ψ is a function that maps W into (0, 1). Define AUC(P₀, ψ) as

\int_{0}^{1} P_{0} (ψ (W) > c ∣ Y = 1) P_{0} (ψ (W) = c ∣ Y = 0) d c .

The efficient influence curve of AUC(P₀, ψ), evaluated at a single observation, O_i = (W_i, Y_i), for a nonparametric model for P₀ is given by

\begin{array}{l} {I C}_{AUC} (P_{0}, ψ) (O_{i}) = \frac{I (Y_{i} = 1)}{P_{0} (Y = 1)} {P_{0} (ψ (W) < x ∣ Y = 0) |}_{x = ψ (W_{i})} \\ + \frac{I (Y_{i} = 0)}{P_{0} (Y = 0)} {P_{0} (ψ (W) > x ∣ Y = 1) |}_{x = ψ (W_{i})} \\ - {\frac{I (Y_{i} = 0)}{P_{0} (Y = 0)} + \frac{I (Y_{i} = 1)}{P_{0} (Y = 1)}} AUC (P_{0}, ψ) . \end{array}

For each ψ, the empirical AUC(P_n, ψ) is asymptotically linear with influence curve IC_AUC (P₀, ψ). Let B_n ∈ {0, 1}ⁿ be a random split of the observations into a training and validation set. Let $P_{n, B_{n}}^{1}$ and $P_{n, B_{n}}^{0}$ be the empirical distributions of the validation set, {i : B_n(i) = 1}, and training set, {i : B_n(i) = 0}, respectively. We assume that B_n has only a finite number of values uniformly in n, as in V-fold cross-validation. We assume that p =Σ_i B_n(i)/n is bounded away from a δ > 0, with probability 1. Define the cross-validated area under the ROC curve as

\hat{R} (\hat{Ψ}, P_{n}) = E_{B_{n}} AUC (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0})) .

(4.1)

We also define the target of this cross-validated area under the ROC curve as

\tilde{R} (\hat{Ψ}, P_{n}) = E_{B_{n}} AUC (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) .

(4.2)

We assume that there exists a ψ₁ ∈ Ψ so that P₀{IC_AUC (P₀, Ψ̂(P_n)) − IC_AUC (P₀, ψ₁)}² converges to zero in probability as n → ∞. We also assume that sup_ψ_∈_Ψ sup_O |IC_AUC (P₀, ψ)(O)| < ∞, where the supremum over O is over a support of P₀. Then,

\hat{R} (Ψ, P_{n}) - \tilde{R} (\hat{Ψ}, P_{n}) = \frac{1}{n} \sum_{i = 1}^{n} {I C}_{AUC} (O_{i}) + o_{P} (1 / \sqrt{n}) .

(4.3)

In particular, $\sqrt{n} (\hat{R} (\hat{Ψ}, P_{n}) - \tilde{R} (\hat{Ψ}, P_{n}))$ converges to a normal distribution with mean zero and variance, σ² = P₀ {IC_AUC (P₀, ψ₁)}². Thus, one can construct an asymptotically 0.95-confidence interval for R̃(Ψ̂, P_n) given by $\hat{R} (\hat{Ψ}, P_{n}) \pm 1.96 \frac{σ_{n}}{\sqrt{n}}$ , where $σ_{n}^{2}$ is a consistent estimator of σ². A consistent estimator of σ² is obtained as

σ_{n}^{2} = E_{B_{n}} P_{n, B_{n}}^{1} {{I C}_{AUC} (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0}))}^{2} .

(4.4)

Proof

In order to derive influence curve based confidence intervals for cross-validated AUC, we must first derive the influence curve for AUC and show that AUC(P_n, ψ) is an asymptotically linear estimator of AUC (P₀, ψ) with influence curve as specified in the theorem. For that purpose we use the functional delta method [22, 14]. The asymptotic linearity of AUC(P_n, ψ) is an immediate consequence of the compact differentiability of functionals (F₁, F₂) → ∫ F₁(x)dF₂(x) for cumulative distribution functions (F₁, F₂) in Gill (1989) so that the functional delta-method can be applied here as well. Therefore it only remains to determine the actual influence curve which is defined in terms of the Gateaux derivative of P → AUC(P, ψ) in the direction of the empirical distribution for a single observation O. We will do that now.

We define F_a(c) = P₀(ψ(W) < c | Y = a) for a ∈ {0, 1}. Therefore, we can alternatively express true AUC as

AUC (P_{0}, ψ) = Φ (F_{0}, F_{1}) = \int (1 - F_{1} (c)) {d F}_{0} (c) .

(4.5)

The Gateaux derivative of Φ(F₀, F₁) in direction (h₀, h₁) is given by:

{\frac{d}{d ε} Φ (F_{0} + ε h_{0}, F_{1} + ε h_{1}) |}_{ε = 0} = \int - h_{1} (c) {d F}_{0} (c) + \int (1 - F_{1} (c)) d h_{0} (c)

Therefore, we have the following linear approximation:

Φ (F_{0 n}, F_{1 n}) - Φ (F_{0}, F_{1}) = \int - (F_{1 n} - F_{1}) {d F}_{0} + \int (1 - F_{1}) d (F_{0 n} - F_{0})

Let F₀_n, F₁_n be the empirical distributions of F₀, F₁. Next we derive the linear approximations of F₁_n − F₁ and F₀_n − F₀. Note that for a ∈ {0, 1},

F_{a n} (c) = P_{n} (ψ (W) < c ∣ Y = a) = \frac{P_{n} (ψ (W) < c, Y = a)}{P_{n} (Y = a)}

(4.6)

It follows that F_an(c) − F_a(c) ~

\begin{array}{l} \frac{(P_{n} - P_{0}) (ψ (W) < c, Y = a)}{P_{0} (Y = a)} - \frac{P_{0} (ψ (W) < c, Y = a)}{{[P_{0} (Y = a)]}^{2}} (P_{n} (Y = a) - P_{0} (Y = a)) \\ = \frac{1}{n} \sum_{i = 1}^{n} {\frac{I (ψ (W_{i}) < c, Y_{i} = a)}{P_{0} (Y = a)} - \frac{F_{a} (c) I (Y_{i} = a)}{P_{0} (Y = a)}} \end{array}

So the influence curve of F_an(c) for a single observation, O_i = (W_i, Y_i), is:

\frac{I (ψ (W_{i}) < c, Y_{i} = a)}{P_{0} (Y = a)} - \frac{F_{a} (c) I (Y_{i} = a)}{P_{0} (Y = a)}

(4.7)

We can substitute this for h_a in the linear approximation above resulting in the desired influence curve IC_AUC (P₀, ψ) as presented in the theorem. For that, it is helpful to observe that:

\int I (ψ (W_{i}) < c, Y_{i} = 1) {d F}_{0} (c) = I (Y_{i} = 1) \int_{ψ (W_{i}) < c} {d F}_{0} (c)

(4.8)

= I (Y_{i} = 1) (1 - F_{0} (ψ (W_{i}))

(4.9)

This is the influence curve for AUC(P_n, ψ), and, since the model Inline graphic for P₀ is nonparametric, this is also the efficient influence curve of parameter AUC(P₀, ψ) on a nonparametric model.

Using the notation that was defined in Section 2, it follows that

\begin{array}{l} E_{B_{n}} AUC (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0})) - E_{B_{n}} AUC (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) = E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {I C}_{AUC} (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) + E_{B_{n}} R (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0})) \\ \approx E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {I C}_{AUC} (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) + o_{P} (1 / \sqrt{n}) \\ = E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {I C}_{AUC} (P_{0}, ψ_{1}) + E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {{I C}_{AUC} (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) - {I C}_{AUC} (P_{0}, ψ_{1})} + o_{P} (1 / \sqrt{n}) \\ = E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {I C}_{AUC} (P_{0}, ψ_{1}) + o_{P} (1 / \sqrt{n}) \\ = (P_{n} - P_{0}) {I C}_{AUC} (P_{0}, ψ_{1}) + o_{P} (1 / \sqrt{n}) . \end{array}

At the first equality we apply the previously established asymptotic linearity of $AUC (P_{n, B_{n}^{1}}, ψ)$ , conditional on the training sample, which proves that each B_n-specific remainder $R (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0}))$ is $o_{P} (1 / \sqrt{n})$ . Since there are only a finite number of possible B_n, this also proves the next equivalence stating that the average across the different B_n-splits of the remainder is also $o_{P} (1 / \sqrt{n})$ . In the third equality, we just carry out a simple split of the empirical process in two terms. In the statement of the theorem, we assume that P₀{IC_AUC (P₀, Ψ̂(P_n)) − IC_AUC (P₀, ψ₁)}² converges to zero in probability as n → ∞ for some ψ₁. Using a result from [23] involving the application of empirical process theory (specifically Lemma 2.14.1 in [22]), the term, $E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {{I C}_{AUC} (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) - {I C}_{AUC} (P_{0}, ψ_{1})}$ , is shown to be $o_{P} (1 / \sqrt{n})$ , which results in the fourth equality.

Finally, $E_{B_{n}} (P_{n, B_{n}}^{1} - P_{0}) {I C}_{AUC} (P_{0}, ψ_{1}) = (P_{n} - P_{0}) {I C}_{AUC} (P_{0}, ψ_{1})$ , proving the asymptotic linearity of the cross-validated AUC estimator as stated in the final equality. In particular,

\sqrt{n} (E_{B_{n}} AUC (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0})) - E_{B_{n}} AUC (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})))

converges to a normal distribution with mean zero and variance, σ² = P₀ {IC_AUC (P₀, ψ₁)}². A consistent estimator of σ² is obtained as

σ_{n}^{2} = E_{B_{n}} P_{n, B_{n}}^{1} {{I C}_{AUC} (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0}))}^{2} .

For $σ_{n}^{2}$ , we estimate the unknown conditional probabilities of the influence curve IC_AUC with the empirical distribution of the validation set, so that $P_{n, B_{n}}^{1} (ψ (W) > x ∣ Y = 0)$ will be consistent at $ψ = \hat{Ψ} (P_{n, B_{n}}^{0})$ under no conditions on the estimator Ψ̂. This is why we replaced P₀ in IC_AUC (P₀, ψ) by the empirical distribution of the validation set. However, the probabilities P₀(Y = 1) and P₀(Y = 0) can be estimated using the whole sample.

Thus, one can construct an asymptotically 0.95-confidence interval for $E_{B_{n}} AUC (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0}))$ given by $E_{B_{n}} AUC (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0})) \pm 1.96 \frac{σ_{n}}{\sqrt{n}}$ .

4.1. A practical implementation for i.i.d. data

For further clarity, we provide a description of the practical construction of the confidence intervals from an i.i.d. data set, as implemented in our software package. Consider an i.i.d. sample of size n with a binary outcome Y. For each observation, O_i = (W_i, Y_i), we have a d-dimensional numeric vector W_i (design matrix) and a binary outcome, Y_i. Without loss of generality, let Y_i ∈ {0, 1}, for all i = 1, …, n, however, Y can be any ordered two-class variable. In this example, we will use V-fold cross-validation and define the the splits as $B_{n}^{1}, \dots, B_{n}^{V}$ , as defined previously. Calculating the V-fold cross validated AUC estimate corresponds to:

Building or fitting the prediction function on each of V validation sets.
Generating a predicted outcome for each observation in the v^th validation set. The predictions are generated using a fit that was trained on the {1, …, V} \ v folds.
For each validation fold, using these predicted values, together with the observed outcomes for each observation, to generate an estimate of the AUC for that validation fold.
Average these estimates across the V validation folds to calculate the cross-validated AUC.

Recall that $P_{n, B_{n}^{v}}^{1}$ and $P_{n, B_{n}^{v}}^{0}$ are the empirical distributions of the v^th validation and training set, respectively and P_n is the empirical distribution of the whole data sample. The V-fold cross-validated AUC estimate, denoted R̂(Ψ̂, P_n), is given by $\frac{1}{V} \sum_{v = 1}^{V} AUC (P_{n, B_{n}}^{1}, ψ_{B_{n}^{v}})$ . In order to construct influence curve based confidence intervals for R̂(Ψ̂, P_n), we estimate the asymptotic variance as:

σ_{n}^{2} = E_{B_{n}} P_{n, B_{n}}^{1} {{I C}_{AUC} (P_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0}))}^{2}

(4.10)

= \frac{1}{V} \sum_{v = 1}^{V} {\frac{1}{n} \sum_{i = 1}^{n} {{I C}_{AUC} (P_{n, B_{n}^{v}}^{1}, \hat{Ψ} (P_{n, B_{n}^{v}}^{0})) (O_{i})}^{2} I (B_{n}^{v} (i) = 1)},

(4.11)

where $ψ_{B_{n}^{v}} = \hat{Ψ} (P_{n, B_{n}^{v}}^{0})$ , and for each v ∈ {1, …, V} and i ∈ {1, …, n}, we have

\begin{array}{l} {I C}_{AUC} (P_{n, B_{n}^{v}}^{1}, \hat{Ψ} (P_{n, B_{n}^{v}}^{0})) (O_{i}) \\ = \frac{I (Y_{i} = 1)}{P_{n} (Y = 1)} {P_{n, B_{n}^{v}}^{1} (ψ_{B_{n}^{v}} (W) < x ∣ Y = 0) |}_{x = ψ_{B_{n}^{v}} (W_{i})} \\ + \frac{I (Y_{i} = 0)}{P_{n} (Y = 0)} {P_{n, B_{n}^{v}}^{1} (ψ_{B_{n}^{v}} (W) > x ∣ Y = 1) |}_{x = ψ_{B_{n}^{v}} (W_{i})} \\ - {\frac{I (Y_{i} = 0)}{P_{n} (Y = 0)} + \frac{I (Y_{i} = 1)}{P_{n} (Y = 1)}} AUC (P_{n, B_{n}}^{1}, ψ_{B_{n}^{v}}) . \end{array}

Despite the density of the notation above, each of the components in the influence curve can be calculated very easily from the data. The terms, $P_{n} (Y = 1) \equiv \frac{1}{n} \sum_{j = 1}^{n} I (Y_{j} = 1)$ and $P_{n} (Y = 0) \equiv \frac{1}{n} \sum_{j = 1}^{n} I (Y_{j} = 0)$ , are the proportions of positive and negative samples, respectively, in the empirical distribution. Let $n_{1}^{v} = \sum_{j = 1}^{n} I (Y_{j} = 1) I (B_{n}^{v} (j) = 1)$ be the number of positive samples in the v^th validation set and let $n_{0}^{v} = \sum_{j = 1}^{n} I (Y_{j} = 0) I (B_{n}^{v} (j) = 1)$ be the number of negative samples in the v^th validation set. Also, recall that $ψ_{B_{n}^{v}}$ is the function learned by the v^th training set, which maps a vector, W, of covariates, to a predicted value, $ψ_{B_{n}^{v}} (W) \in (0, 1)$ . For a given sample, O_i = (W_i, Y_i), we calculate the predicted value, $ψ_{B_{n}^{v}} (W_{i})$ , and note that whether Y_i is labeled as positive (Y_i = 1) or negative (Y_i = 0). Above, each of the terms in the expression for the influence curve contains an indicator function, conditional on the value of Y_i. Therefore, given the value of Y_i, we need only to evaluate the non-zero part of the expression.

When Y_i = 1, we need to evaluate:

{P_{n, B_{n}^{v}}^{1} (ψ_{B_{n}^{v}} (W) < x ∣ Y = 0) |}_{x = ψ_{B_{n}^{v}} (W_{i})} = \frac{1}{n_{0}^{v}} \sum_{j = 1}^{n} I (W_{j} < ψ_{B_{n}^{v}} (W_{i})) I (Y_{j} = 0) I (B_{n}^{v} (j) = 1)

This sum counts the number of negative samples in the validation set that have a predicted value less than $ψ_{B_{n}^{v}} (W_{i})$ , the predicted value for sample i. Then, we divide by the total number of negative samples in the validation set. Similarly, when Y_i = 0, we need to evaluate:

{P_{n, B_{n}^{v}}^{1} (ψ_{B_{n}^{v}} (W) > x ∣ Y = 1) |}_{x = ψ_{B_{n}^{v}} (W_{i})} = \frac{1}{n_{0}^{v}} \sum_{j = 1}^{n} I (W_{j} > ψ_{B_{n}^{v}} (W_{i})) I (Y_{j} = 1) I (B_{n}^{v} (j) = 1)

This sum counts the number of positive samples in the validation set that have a predicted value greater than $ψ_{B_{n}^{v}} (W_{i})$ , the predicted value for sample i. Then, we divide by the total number of positive samples in the validation set. The remaining term in the expression for the influence curve is simply $AUC (P_{n, B_{n}}^{1}, ψ_{B_{n}^{v}})$ , given in Section 3, multiplied by inverse probability of P_n(Y = 1) or P_n(Y = 0), depending on the value of the indicator function at Y_i. Thus, for fixed v ∈ {1, …, V} and i ∈ {1, …, n}, we have demonstrated how to calculate the quantity, ${I C}_{AUC} (P_{n, B_{n}^{v}}^{1}, \hat{Ψ} (P_{n, B_{n}^{v}}^{0})) (O_{i})$ , from an i.i.d. data set. Then we square this term and sum over i.i.d. samples, i, and cross-validation folds, v, to get

σ_{n}^{2} = \frac{1}{V} \sum_{v = 1}^{V} {\frac{1}{n} \sum_{i = 1}^{n} {{I C}_{AUC} (P_{n, B_{n}^{v}}^{1}, \hat{Ψ} (P_{n, B_{n}^{v}}^{0})) (O_{i})}^{2} I (B_{n}^{v} (i) = 1)},

an estimate for the asymptotic variance of R̂(Ψ̂, P_n), our V-fold cross-validated AUC estimator. The target of this estimator is

\tilde{R} (\hat{Ψ}, P_{n}) = E_{B_{n}} AUC (P_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) = \frac{1}{V} \sum_{v = 1}^{V} AUC (P_{0}, \hat{Ψ} (P_{n, B_{n}^{v}}^{0})),

the true V-fold cross-validated AUC. Then, as in Theorem 4.1, one can construct an asymptotically 0.95-confidence interval for R̃(Ψ̂, P_n) as $\hat{R} (\hat{Ψ}, P_{n}) \pm 1.96 \frac{σ_{n}}{\sqrt{n}}$ .

5. Generalization to pooled repeated measures data

Above, we derived a consistent influence curve based estimator of the asymptotic variance of cross-validated AUC for the simple setting in which there are n i.i.d. observations. Each of these observations, O_i has a predictor variable, W_i, coupled with a binary outcome variable, Y_i, that we wish to predict. Now we consider the common setting in which there are repeated measures for each observation. This data structure arises frequently in medical studies, where each patient is measured at multiple time points. We focus on the case where the order of these measures is not meaningful, and one simply wishes to obtain a single summary of classifier performance pooled over all measures. We begin by providing a formal definition of the target parameter, the pooled cross-validated AUC, for such cases. We then extend the results presented in the previous sections to derive an influence curve based variance estimator for the cross-validated AUC of a pooled repeated measures data set.

As before, we let P₀ ∈ Inline graphic and Ψ: → Ψ. We denote the target parameter Ψ(P₀) as ψ₀. Let O = (W (t), Y (t): t ∈ τ) ~ P₀ for a possibly random index set τ ⊂ {1, …, T}, where t corresponds to a single time-point observation. Here Y (t) is binary for each t. We observe n i.i.d. copies O_i = (W_i(t), Y_i(t): t ∈ τ_i), i = 1, …, n of O. Let Inline graphic denote a nonparametric model that includes the empirical distribution, P_n, of O₁, …, O_n and let Ψ̂: → ℝ be an estimator of ψ₀. We assume that Ψ̂(P₀) = ψ₀. We consider the case where t is not a meaningful index, and that either ψ₀(t, w) = E₀ (Y (t) | W (t) = w) does not depend on t, or that the investigator has no interest in understanding the dependence on t. Consider the distribution,

{\bar{P}}_{0} (w, y) = \frac{1}{E_{0} ∣ τ ∣} \sum_{t = 1}^{T} P_{0} (t \in τ) P_{0} (W (t) = w, Y (t) = y ∣ t \in τ) .

This represents the limit distribution of the empirical distribution P̄_n of the pooled sample:

{\bar{P}}_{n} (w, y) = \frac{1}{\sum_{i = 1}^{n} ∣ τ_{i} ∣} \sum_{i = 1}^{n} \sum_{t \in τ_{i}} I (W_{i} (t) = w, Y_{i} (t) = y) .

One could define as a measure of interest for evaluation a predictor ψ, the area under the ROC curve one would obtain if one treats the pooled sample as N i.i.d. observations. That is, we define

\bar{AUC} ({\bar{P}}_{0}, ψ) = \int_{0}^{1} {\bar{P}}_{0} (ψ (W) > c ∣ Y = 1) {\bar{P}}_{0} (ψ (W) = c ∣ Y = 0) d c,

(5.1)

where, without loss of generality, we let the positive class be represented by Y = 1 and the negative class be represented by Y = 0. The pooled repeated measures AUC can be interpreted as the probability that, after pooling over all independent sampling units and all time points, a randomly sampled positive outcome will be ranked more highly than a randomly sampled negative outcome.

The AUC for the empirical distribution of the pooled sample can be expressed explicitly as follows. Let $n_{0} = \sum_{i = 1}^{n} \sum_{t \in τ_{i}} I (Y_{i} (t) = 0)$ and let $n_{1} = \sum_{j = 1}^{n} \sum_{s \in τ_{j}} I (Y_{j} (s) = 1)$ . Then we have

\bar{AUC} ({\bar{P}}_{n}, ψ) = \frac{1}{n_{0} n_{1}} \sum_{i = 1}^{n} \sum_{t \in τ_{i}} \sum_{j = 1}^{n} \sum_{s \in τ_{j}} I (ψ (W_{j} (s)) > ψ (W_{i} (t))) I (Y_{i} (t) = 0, Y_{j} (s) = 1) .

Now we consider the cross-validated AUC of a pooled repeated measures data set. Let B_n ∈ {0, 1}ⁿ be a random split of the n independent observations into a training and validation set. Let ${\bar{P}}_{n, B_{n}}^{1}$ and ${\bar{P}}_{n, B_{n}}^{0}$ be the empirical distributions of the pooled data within the validation set, {i: B_n(i) = 1}, and training set, {i: B_n(i) = 0}, respectively. We assume that B_n has only a finite number of values uniformly in n, as in V -fold cross-validation. Given a random split, B_n, we define $ψ_{B_{n}} \equiv \hat{Ψ} ({\bar{P}}_{n, B_{n}}^{0})$ .

As in the i.i.d. example in the previous section, we will walk through the case of V -fold cross-validation. Let $B_{n}^{1}, \dots, B_{n}^{V}$ be the collection of random splits that define our cross-validation procedure. In the case of V-fold cross-validation, each of the $B_{n}^{v}$ encodes a single fold; the v^th validation fold is {i : $B_{n}^{v} (i) = 1$ }, and the remaining samples belong to the v^th training set, {i : $B_{n}^{v} (i) = 0$ }. Note that since our independent units are collections of pooled time points, O_i = (W_i(t), Y_i(t): t ∈ τ_i), that all pooled samples from each i.i.d. sample, O_i will be contained within the same validation fold.

For each $B_{n}^{v}$ , we define $ψ_{B_{n}^{v}} \equiv \hat{Ψ} ({\bar{P}}_{n, B_{n}^{v}}^{0})$ , where ${\bar{P}}_{n, B_{n}^{v}}^{0}$ is the empirical distribution of the pooled data contained in the v^th training set. The function $ψ_{B_{n}^{v}}$ , which is learned from the v^th training set, will be used to generate predicted values for the observations in the v^th validation fold. We define $n_{1}^{v}$ and $n_{0}^{v}$ to be the number of positive and negative samples in the v^th validation fold, respectively. Formally, $n_{1}^{v} = \sum_{i = 1}^{n} \sum_{t \in τ_{i}} I (Y_{i} (t) = 1) I (B_{n}^{v} (i) = 1)$ and $n_{0}^{v} = \sum_{i = 1}^{n} \sum_{t \in τ_{i}} I (Y_{i} (t) = 0) I (B_{n}^{v} (i) = 1)$ . We note that $n_{1}^{v}$ and $n_{0}^{v}$ are random variables that depend on the value of both $B_{n}^{v}$ and {Y_i : $B_{n}^{v} (i) = 1$ }.

The AUC for a single validation fold, {i : $B_{n}^{v} (i) = 1$ }, for pooled repeated measures data, is

\bar{AUC} ({\bar{P}}_{n, B_{n}^{v}}^{1}, ψ_{B_{n}^{v}}) = \frac{1}{n_{0}^{v} n_{1}^{v}} \sum_{i = 1}^{n} \sum_{t \in τ_{i}} \sum_{j = 1}^{n} \sum_{s \in τ_{j}} h (n, v, i, t, j, s)

(5.2)

where h(n, v, i, t, j, s) =

I (ψ_{B_{n}^{v}} (W_{j} (s)) > ψ_{B_{n}^{v}} (W_{i} (t))) I (Y_{i} (t) = 0, Y_{j} (s) = 1) I (B_{n}^{v} (i) = B_{n}^{v} (j) = 1) .

In other words, it is the probability that, after pooling over units and time, a randomly drawn positive sample will be assigned a higher predicted value than a randomly drawn negative sample in the same validation fold by the prediction model fit using the corresponding training set.

Then the V -fold cross-validated AUC estimator, for pooled repeated measures data, is defined as

E_{B_{n}} \bar{AUC} ({\bar{P}}_{n, B_{n}}^{1}, ψ_{B_{n}}) = \frac{1}{V} \sum_{v = 1}^{V} \bar{AUC} ({\bar{P}}_{n, B_{n}^{v}}^{1}, ψ_{B_{n}^{v}})

(5.3)

= \frac{1}{V} \sum_{v = 1}^{V} {\frac{1}{n_{0}^{v} n_{1}^{v}} \sum_{i = 1}^{n} \sum_{t \in τ_{i}} \sum_{j = 1}^{n} \sum_{s \in τ_{j}} h (n, v, i, t, j, s)} .

(5.4)

We also define the target, ψ₀, of the V -fold cross-validated AUC estimate as

E_{B_{n}} \bar{AUC} ({\bar{P}}_{0}, ψ_{B_{n}}) = \frac{1}{V} \sum_{v = 1}^{V} \bar{AUC} ({\bar{P}}_{0}, ψ_{B_{n}^{v}})

(5.5)

= \frac{1}{V} \sum_{v = 1}^{V} {\bar{P}}_{0} (ψ_{B_{n}^{v}} (W_{1}) > ψ_{B_{n}^{v}} (W_{2}) ∣ Y_{1} = 1, Y_{2} = 0),

(5.6)

where (W₁, Y₁) ≡ (W₁(t), Y₁(t)) and (W₂, Y₂) ≡ (W₂(t), Y₂(t)) are single time-point observations. The following theorem is the pooled repeated measures analogue to Theorem 4.1.

Analogous to i.i.d. data version, this target represents the average across validation folds of the true probability (under P₀) that a randomly sampled positive observation would be ranked higher than a randomly sampled negative observation in the same validation fold by the prediction function fit in the corresponding training set. Again, the true value of this target parameter is random – it depends on the random split of the sample into V folds and corresponding fits of the prediction function. However, it nonetheless provides a meaningful measure of the performance of the prediction function on independent data.

Theorem 5.1

The efficient influence curve of $\bar{AUC} ({\bar{P}}_{0}, ψ)$ , evaluated at O_i = (W_i(t), Y_i(t)): t ∈ τ_i), for a nonparametric model for P₀ is given by:

{I C}_{\bar{AUC}} ({\bar{P}}_{0}, ψ) (O_{i}) = \frac{1}{E_{0} ∣ τ ∣} \sum_{t \in τ} {I C}_{AUC} ({\bar{P}}_{0}, ψ) (W_{i} (t), Y_{i} (t)),

where

\begin{array}{l} {I C}_{AUC} ({\bar{P}}_{0}, ψ) (W_{i} (t), Y_{i} (t)) \\ = \frac{I (Y_{i} (t) = 1)}{{\bar{P}}_{0} (Y = 1)} {{\bar{P}}_{0} (ψ (W) < x ∣ Y (t) = 0) |}_{x = ψ (W_{i} (t))} \\ + \frac{I (Y_{i} (t) = 0)}{{\bar{P}}_{0} (Y = 0)} {{\bar{P}}_{0} (ψ (W) > x ∣ Y (t) = 1) |}_{x = ψ (W_{i} (t))} \\ - {\frac{I (Y_{i} (t) = 0)}{{\bar{P}}_{0} (Y = 0)} + \frac{I (Y_{i} (t) = 1)}{{\bar{P}}_{0} (Y = 1)}} AUC ({\bar{P}}_{0}, ψ), \end{array}

Directly above, (W, Y) ≡ (W(s), Y (s)) represents a single time-point observation. For each ψ, the estimator $\bar{AUC} ({\bar{P}}_{n}, ψ)$ obtained by plugging in the pooled empirical distribution P̄₀, is asymptotically linear with influence curve ${I C}_{\bar{AUC}} ({\bar{P}}_{0}, ψ)$ .

Let B_n ∈ {0, 1}ⁿ be a random split and let $P_{n, B_{n}}^{1}$ and $P_{n, B_{n}}^{0}$ be the empirical distributions of the validation {i: B_n(i) = 1} and training set {i: B_n(i) = 0}, respectively. Let ${\bar{P}}_{n, B_{n}}^{1}$ be the empirical distribution of the pooled data within the validation set. We assume that B_n has only a finite number of values uniformly in n, as in V-fold cross-validation. We assume that p = Σ_i B_n(i)/n is bounded away from a δ > 0, with probability 1. Define the cross-validated area under the ROC curve as

\hat{R} (\hat{Ψ}, P_{n}) = E_{B_{n}} \bar{AUC} ({\bar{P}}_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0})) .

(5.7)

We also define the target of this cross-validated area under the ROC curve as

\tilde{R} (\hat{Ψ}, P_{n}) = E_{B_{n}} \bar{AUC} ({\bar{P}}_{0}, \hat{Ψ} (P_{n, B_{n}}^{0})) .

(5.8)

We assume that there exists a ψ₁ ∈ Ψ so that $P_{0} {{I C}_{\bar{AUC}} ({\bar{P}}_{0}, \hat{Ψ} (P_{n})) - {I C}_{\bar{AUC}} ({\bar{P}}_{0}, ψ_{1})}^{2}$ converges to zero in probability as n → ∞. We also assume that ${sup}_{ψ \in Ψ} {sup}_{O} ∣ {I C}_{\bar{AUC}} ({\bar{P}}_{0}, ψ) (O) ∣ < \infty$ , where the supremum over O is over a support of P₀. Then,

\hat{R} (\hat{Ψ}, P_{n}) - \tilde{R} (\hat{Ψ}, P_{n}) = \frac{1}{n} \sum_{i = 1}^{n} {I C}_{\bar{AUC}} ({\bar{P}}_{0}, ψ_{1}) (O_{i}) + o_{P} (1 / \sqrt{n}) .

(5.9)

In particular, $\sqrt{n} (\hat{R} (\hat{Ψ}, P_{n}) - \tilde{R} (\hat{Ψ}, P_{n}))$ converges to a normal distribution with mean zero and variance, $σ^{2} = P_{0} {{I C}_{\bar{AUC}} ({\bar{P}}_{0}, ψ_{1})}^{2}$ . Thus, one can construct an asymptotically 0.95-confidence interval for R̃(Ψ̂, P_n) given by $\hat{R} (\hat{Ψ}, P_{n}) \pm 1.96 \frac{σ_{n}}{\sqrt{n}}$ where $σ_{n}^{2}$ is a consistent estimator of σ². A consistent estimator of σ² is obtained as

σ_{n}^{2} = E_{B_{n}} P_{n, B_{n}}^{1} {{I C}_{\bar{AUC}} ({\bar{P}}_{n, B_{n}}^{1}, \hat{Ψ} (P_{n, B_{n}}^{0}))}^{2} .

(5.10)

Proof

This is the pooled repeated measures analogue of Theorem 4.1, so the proof follows the exact same format and arguments as the proof of Theorem 4.1.

6. Software

We implemented the influence curve based confidence intervals for cross-validated AUC for i.i.d. data as well as for pooled repeated measures data, as an R package. The package, called cvAUC [16], has the same function interface as the popular ROCR package [6].

For each observation, the user provides a cross-validated predicted value, as generated by a binary prediction algorithm, and a corresponding binary class label. If the user has pooled repeated measures data instead of i.i.d. data, then the user must also provide an id for each observation. The user must also indicate which observations belong to each cross-validation fold. To be clear, the user must provide for each observation, i:

The value of the outcome, Y_i.
The validation fold, v ∈ {1, …, V }, that observation, i, is associated with.
The predicted probability of the outcome, ψ(W_i), based on plugging in that observation’s covariates, W_i, into a fit trained on the observations associated with folds: {1, …, V }\v.

The main functions of the package calculate the confidence intervals (confidence level supplied by the user; defaults to 95%) for cross-validated AUC and AUC estimates calculated using i.i.d. and pooled repeated measures training data. The package also includes utility functions to compute AUC and cross-validated AUC from a set of predicted values and associated true labels.

To provide some context to the computational efficiency of our methods, the influence curve based CV AUC variance calculation for i.i.d. data takes less than half a second to execute for a sample of 100,000 observations on a 2.3 GHz Intel Core i7 processor (package version 1.0.3). For 1 million observations, it currently takes 13 seconds. More information and code examples can be found in the user manual for the package, and we provide a simple code example in Appendix A. The cvAUC R package is available on CRAN at http://cran.r-project.org/web/packages/cvAUC/index.html.

7. Coverage probability of the confidence intervals

In this section, we describe and present results from a simulation which demonstrates the coverage probability of our influence curve based confidence intervals as implemented in our R package, cvAUC [16]. The coverage probability of a confidence interval is the proportion of the time, over repetitions of the identical experiment, that the interval contains the true value of interest. Our true value of interest is true cross-validated AUC, defined in equation 2.4. In the simulation below, we consider a variety of training set sizes. We show that when n is small, the coverage probability of the influence curve based confidence interval may drop below the specified rate. Therefore, if you have a small sample size, bootstrapping may serve as a computationally-reasonable alternative variance estimation technique. To quantify the computational advantage of the influence curve approach, we evaluate the required number of bootstrap replicates that are required in order to achieve 95% coverage.

7.1. Simulation to evaluate coverage probability

Let n × k represent the dimensions of our training set design matrix, X. We considered training sets where n = {500, 1000, 5000, 10000, 20000} and k = {10, 50, 100, 200}. The the number of covariates that are correlated with the outcome is fixed at 10. The remaining k – 10 covariates are random noise. For the 10 informative covariates, we generate 100,000 points from Inline graphic (μ, Σ), and for each these observations, we let Y = 0. Similarly, we generate 100,000 observations from (ν, Σ) and let Y = 1 for all these observations. For this simulation, we let μ_i = 0 and ν_i = 0.3, for i ∈ {1, …, 10} and we let Σ represent the identity covariance matrix. These combined 200,000 observations represent our true data distribution, P₀. We note that our target parameter, true cross-validated AUC, is itself random, but that it represents a true target. We are interested in the confidence interval that contains this random target 95% of the time. The samples were generated using the mvrnorm function of the R package, MASS [5].

To calculate the coverage probability of our influence curve based confidence intervals, we generate the CV AUC and corresponding confidence intervals 5,000 times and report the proportion of times that the confidence interval contains the true CV AUC. For each iteration, we sample n points from the same distribution as our population data and use that as a training set.

We perform 10-fold cross-validation by splitting these n observations into 10 validation folds, stratifying by outcome, Y. For each validation fold, we train a Lasso-regularized logistic regression fit using the glmnet R package [13] using the observations from the remaining 9 folds. Using the fit model, we then generate predictions for each of the samples in the validation fold and calculate the empirical AUC. We will call this the fold AUC. We also calculate the true AUC by generating predicted values for all of the 200,000 data points in our population data and calculating the empirical AUC among this population.

This process is repeated for each of the 10 validation folds, at which point we average the fold AUCs to get the estimate for cross-validated AUC. We also average the 10 true AUCs to get the true cross-validated AUC. We then calculate a 95% confidence interval for our CV AUC estimate and note whether or not the true CV AUC falls within the confidence interval.

For each value of k ∈ {10, 50, 100, 200}, this process is repeated 5,000 times to obtain an estimate of the coverage probability of our confidence intervals. The coverage probability is the proportion times that the true CV AUC fell within our confidence interval. For 95% confidence intervals, we expect the coverage probability to be close to 0.95. The coverage probabilities for each training set is shown in Table 1.

Table 1.

Coverage probability for influence curve based confidence intervals for CV AUC using training sets of various dimension.

	n = 500	n = 1, 000	n = 5, 000	n = 10, 000	n = 20, 000
k = 10	0.909	0.928	0.946	0.943	0.943
k = 50	0.891	0.931	0.946	0.950	0.941
k = 100	0.885	0.925	0.946	0.946	0.949
k = 200	0.878	0.923	0.947	0.937	0.940

Open in a new tab

The results of the simulation indicate that for a relatively small sample size (e.g. n = 1, 000), the coverage probability of the confidence intervals are slightly lower (92–93%) than specified (95%). However, when n ≥ 5, 000, we have coverage between 94–95%. These simulations use just one particular data generating distribution, but the results can serve as a rough benchmark of coverage probability rates over various n.

In Table 2, we summarize the standard errors estimated using the influence curve based variance estimation technique, as implemented in the cvAUC package. For comparison, in Table 3 we report the standard deviation of the CV AUC estimates across the 5,000 iterations of the simulation. We see that for n ≥ 5, 000, the standard errors and standard deviations are identical, however, for smaller n, the influence curve based standard errors are slightly conservative compared to the standard deviation across the 5,000 iterations. This is expected, based on the coverage probabilities reported in Table 4.

Table 2.

Influence curve based standard errors for CV AUC for training sets of various dimensions.

	n = 500	n = 1, 000	n = 5, 000	n = 10, 000	n = 20, 000
k = 10	0.023	0.015	0.007	0.005	0.003
k = 50	0.023	0.016	0.007	0.005	0.003
k = 100	0.024	0.016	0.007	0.005	0.003
k = 200	0.024	0.016	0.007	0.005	0.003

Open in a new tab

Table 3.

Standard deviation of 5,000 CV AUC estimates for training sets of various dimensions.

	n = 500	n = 1, 000	n = 5, 000	n = 10, 000	n = 20, 000
k = 10	0.028	0.017	0.007	0.005	0.003
k = 50	0.033	0.018	0.007	0.005	0.003
k = 100	0.034	0.019	0.007	0.005	0.003
k = 200	0.038	0.019	0.007	0.005	0.003

Open in a new tab

Table 4.

Average CV AUC across 5,000 iterations for training sets of various dimensions.

	n = 500	n = 1, 000	n = 5, 000	n = 10, 000	n = 20, 000
k = 10	0.720	0.737	0.747	0.748	0.748
k = 50	0.706	0.733	0.747	0.748	0.748
k = 100	0.699	0.731	0.747	0.748	0.748
k = 200	0.689	0.728	0.747	0.748	0.748

Open in a new tab

For reference, we provide the average CV AUC estimate across 5,000 iterations for training sets of various dimensions in Table 4. A total of 20 × 5, 000 = 500, 000 cross validated AUC estimates were generated for the entire simulation. The number of individual models that were trained across all 10 folds was 500, 000 × 10 = 5 million.

7.2. Comparison to bootstrapped confidence intervals

We implemented quantile (or percent) bootstrapped confidence intervals in Julia [8] (version 0.0.3) to compare the coverage probability of bootstrap derived confidence intervals to influence curve derived confidence intervals. The same data generating distributions [18] as the influence curve based simulations were used, and again we used Lasso-regularized logistic regression [15]. For each iteration of the experiment, we generate an original training set and B bootstrapped replicates of the this training set. Using the B training sets, we generate B cross-validated AUC estimates [17]. We use the 0.025 and 0.975 quantiles of the B cross-validated AUCs to estimate the 95% confidence intervals. In this simulation, the computation time for bootstrapped confidence intervals is o(B) times greater than the runtime of the influence curve based confidence intervals since each bootstrap replicate requires a complete re-calculation of CV AUC. Some methods of bootstrapping (e.g. m of out n bootstrap [9] and “Bag of Little Bootstraps” [4]) make computational improvements on o(B), however all bootstrapping methods require you to make repeated estimations of CV AUC.

On a training set of n = 1,000 observations, we evaluated how many bootstrapped replicates, B, are required to obtain 95% coverage. In this simulation, we found that at least 400 bootstrap replicates were required to obtain a coverage probability of 0.95. The coverage probabilities for increasing values of B are shown in Table 5.

Table 5.

Bootstrap confidence interval coverage probability using B bootstrapped replicates of a training set of n = 1,000 observations.

	B = 100	B = 200	B = 300	B = 400
k = 10	0.906	0.930	0.929	0.958

Open in a new tab

Since the bootstrap confidence interval coverage probability estimate converged after approximately 1,000 iterations of the experiment, the coverage probability estimates in Table 5 are averaged over 1,000 iterations instead of 5,000.

8. Conclusion

Cross-validated AUC represents an attractive and commonly used measure of performance in binary classification problems. However, resampling based approaches to constructing confidence intervals for this quantity can be computationally expensive. In this paper, we established the asymptotical linearity of the cross-validated AUC estimator and derived its influence curve for both the i.i.d. and pooled repeated measures cases. We then presented a computationally efficient approach to constructing confidence intervals based on estimating this influence curve, which is implemented as a publicly available R package called cvAUC. A simulation demonstrated that we were able to achieve the expected coverage probability for our confidence intervals, however, for small sample sizes, the coverage probability can dip below the desired rate. We have demonstrated a computationally efficient alternative to bootstrapping for estimating the variance of cross-validated AUC estimates.

Fig 1 — Plots of the coverage probabilities for 95% confidence intervals generated by our simulation for training sets of 1,000 (left) and 5,000 (right) observations. In the case of a 95% confidence interval, the coverage probability should be close to 0.95. For the smaller dataset of n = 1, 000 observations, we see that the coverage is slightly lower (92–93%) than specified, whereas for n = 5, 000, the coverage is closer to 95%.

Acknowledgments

We would like to thank the developers of the ROCR R package [6].

Appendix A: Appendix

A.1. Code example

Below is a simple example of how to use the cvAUC R package. This i.i.d. data example does the following:

Load a data set with a binary outcome. For the i.i.d. case we use a simulated data set of 500 observations, included with the package, of graduate admissions data.
Divide the indices randomly into 10 folds, stratifying by outcome. Stratification is not necessary, but is commonly performed in order to create validation folds with similar distributions. Store this information in a list called folds.
Define a function to fit a model on the training data and to generate predicted values for the observations in the validation fold, for a single iteration of the cross-validation procedure. We use a logistic regression fit.
Apply this function across all folds to generate predicted values for each validation fold. The concatenated version of these predicted values is stored in vector called predictions. The outcome vector, Y, is the labels argument.

# Create CV folds (stratify by outcome)
.cvFolds <- function(Y, V){
  Y0 <- split(sample(which(Y==0)),
          rep(1:V, length=length(which(Y==0))))
  Y1 <- split(sample(which(Y==1)),
         rep(1:V, length=length(which(Y==1))))
  folds <- vector(“list”, length=V)
  for (v in seq(V)) {folds[[v]] <- c(Y0[[v]], Y1[[v]])}
  return(folds)
}

# Train/test glm for each fold
.doFit <- function(v, folds, data){
  fit <- glm(Y~., data=data[-folds[[v]],], family=binomial)
  pred <- predict(fit, newdata=data[folds[[v]],], type=“response”)
  return(pred)
}

iid_example <- function(data, V=10){
  # Create folds
  folds <- .cvFolds(Y=data$Y, V=V)
  # CV train/predict
  predictions <- unlist(sapply(seq(V), .doFit,
                      folds=folds, data=data))
  # Re-order pred values
  predictions[unlist(folds)] <- predictions
  # Get CV AUC and confidence interval
  out <- ci.cvAUC(predictions=predictions, labels=data$Y,
           folds=folds, confidence=0.95)
  return(out)
}

# Run example
library(cvAUC)
data(admissions)
set.seed(1)
out <- iid_example(data=admissions, V=10)
# The output is given as follows:
# > out
# $cvAUC
# [1] 0.9046473
#
# $se
# [1] 0.01620238
#
# $ci
# [1] 0.8728913 0.9364034
#
# $confidence
# [1] 0.95

Contributor Information

Erin LeDell, Email: ledell@berkeley.edu.

Maya Petersen, Email: mayaliv@berkeley.edu.

Mark van der Laan, Email: laan@berkeley.edu.

References

1.Ling C, Huang J, Zhang H. AUC: a statistically consistent and more discriminating measure than accuracy. Proceedings of IJCAI; 2003.2003. [Google Scholar]
2.Bradley AP. The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognition. 1997;30:1145–1159. [Google Scholar]
3.Geisser S. The predictive sample reuse method with applications. Amer Statist Assoc. 1975;70:320–328. [Google Scholar]
4.Kleiner A, Talwalkar A, Sarkar P, Jordan M. A scalable bootstrap for massive data. Journal of the Royal Statistical Society, Series B 2013 [Google Scholar]
5.Venables WN, Ripley BD. Modern Applied Statistics with S. 4. Springer; New York: 2002. [Google Scholar]
6.Sing T, Sander O, Beerenwinkel N, Lengauer T. ROCR: Visualizing classifier performance in R. Bioinformatics. 2005;21(20):3940–3941. doi: 10.1093/bioinformatics/bti623. [DOI] [PubMed] [Google Scholar]
7.Allen DM. The relationship between variable selection and data augmentation and a method for prediction. Technometrics. 1974;16:125–127. [Google Scholar]
8.Bezanson J, Karpinski S, Shah VB, Edelman A. Julia: A fast dynamic language for technical computing. CoRR abs/1209.5145. 2012 http://arxiv.org/abs/1209.5145.
9.Bickel PJ, Götze F, van Zwet WR. Resampling fewer than n observations: gains, losses, and remedies for losses. Statist Sinica. 1997;7(1):1–31. Empirical Bayes, sequential analysis and related topics in statistics and probability (New Brunswick, NJ, 1995) [Google Scholar]
10.Bickel PJ, Klaassen CAJ, Ritov Y, Wellner JA. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press; Baltimore, MD: 1993. Efficient and adaptive estimation for semiparametric models. [Google Scholar]
11.Efron B. Bootstrap methods: another look at the jackknife. Ann Statist. 1979;7(1):1–26. [Google Scholar]
12.Efron B, Tibshirani RJ. Monographs on Statistics and Applied Probability. Vol. 57. Chapman and Hall; New York: 1993. An introduction to the bootstrap. [Google Scholar]
13.Friedman J, Hastie T, Tibshirani R. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software. 2010;33(1):1–22. http://www.jstatsoft.org/v33/i01/ [PMC free article] [PubMed] [Google Scholar]
14.Gill RD. Non- and semi-parametric maximum likelihood estimators and the von Mises method. I Scand. J Statist. 1989;16(2):97–128. With a discussion by J. A. Wellner and J. Præstgaard and a reply by the author. [Google Scholar]
15.Kornblith S. GLMNet.jl: Julia wrapper for fitting Lasso/ElasticNet GLM models using glmnet. 2014 Commit version 0526df8455, https://github.com/simonster/GLMNet.jl.
16.LeDell E, Petersen M, van der Laan M. cvAUC: Cross-Validated Area Under the ROC Curve Confidence Intervals. R package version 1.0-0. 2013 doi: 10.1214/15-EJS1035. http://CRAN.R-project.org/package=cvAUC. [DOI] [PMC free article] [PubMed]
17.Lin D. A set of functions to support the development of machine learning algorithms. 2014 v0.4.2, https://github.com/JuliaStats/MLBase.jl.
18.Lin D, White JM. A Julia package for probability distributions and associated functions. 2014 v0.5.4, https://github.com/JuliaStats/Distributions.jl.
19.Politis DN, Romano JP, Wolf M. Springer Series in Statistics. Springer-Verlag; New York: 1999. Sub-sampling. http://dx.doi.org/10.1007/978-1-4612-1554-7. [Google Scholar]
20.Shao J. Linear model selection by cross-validation. J Amer Statist Assoc. 1993;88:422, 486–494. [Google Scholar]
21.Stone M. Cross-validatory choice and assessment of statistical predictions. J Roy Statist Soc Ser B. 1974;36:111–147. With discussion by G. A. Barnard, A. C. Atkinson, L. K. Chan, A. P. Dawid, F. Downton, J. Dickey, A. G. Baker, O. Barndorff-Nielsen, D. R. Cox, S. Giesser, D. Hinkley, R. R. Hocking, and A. S. Young, and with a reply by the authors. [Google Scholar]
22.van der Vaart AW, Wellner JA. Springer Series in Statistics. Springer-Verlag; New York: 1996. Weak convergence and empirical processes. With applications to statistics. [Google Scholar]
23.Zheng W, van der Laan MJ. Targeted maximum likelihood estimation of natural direct effect. Tech Rep. 2011;288 doi: 10.2202/1557-4679.1361. U.C. Berkeley Division of Biostatistics Working Paper Series. [DOI] [PMC free article] [PubMed] [Google Scholar]

PERMALINK

Computationally efficient confidence intervals for cross-validated area under the ROC curve estimates

Erin LeDell

Maya Petersen

Mark van der Laan

Abstract

1. Introduction

2. Cross-validated AUC as a target parameter

3. Influence curves for variance estimation

4. Confidence intervals for cross-validated AUC

Theorem 4.1

Proof

4.1. A practical implementation for i.i.d. data

5. Generalization to pooled repeated measures data

Theorem 5.1

Proof

6. Software

7. Coverage probability of the confidence intervals

7.1. Simulation to evaluate coverage probability

Table 1.

Table 2.

Table 3.

Table 4.

7.2. Comparison to bootstrapped confidence intervals

Table 5.

8. Conclusion

Fig 1.

Acknowledgments

Appendix A: Appendix

A.1. Code example

Contributor Information

References

ACTIONS

PERMALINK

RESOURCES

Cite

Add to Collections

PERMALINK

Computationally efficient confidence intervals for cross-validated area under the ROC curve estimates

Erin LeDell

Maya Petersen

Mark van der Laan

Abstract

1. Introduction

2. Cross-validated AUC as a target parameter

3. Influence curves for variance estimation

4. Confidence intervals for cross-validated AUC

Theorem 4.1

Proof

4.1. A practical implementation for i.i.d. data

5. Generalization to pooled repeated measures data

Theorem 5.1

Proof

6. Software

7. Coverage probability of the confidence intervals

7.1. Simulation to evaluate coverage probability

Table 1.

Table 2.

Table 3.

Table 4.

7.2. Comparison to bootstrapped confidence intervals

Table 5.

8. Conclusion

Fig 1.

Acknowledgments

Appendix A: Appendix

A.1. Code example

Contributor Information

References

ACTIONS

PERMALINK

RESOURCES

Similar articles

Cited by other articles

Links to NCBI Databases