Evaluating E-Discovery

Point- and lower-bound confidence estimates on the completeness (or recall) of an e-discovery production are calculated by sampling documents, from both the production and the remainder of the collection (the null set). The most straightforward way to draw this sample is as a simple random sample (SRS) across the whole collection, produced and unproduced. However, the same level of accuracy can be achieved for a fraction of the review cost by using stratified sampling instead. In this post, I introduce the use of stratified sampling in the evaluation of e-discovery productions. In a later post, I will provide worked examples, illustrating the saving in review cost that can be achieved.

Sampling aims to estimate characteristics of a population by looking at a sample of that population. In simple random sampling, we sample from the population indifferently; each element of the population (and each combination of elements) has the same probability of being included. By contrast, in stratified sampling, we divide the population up into disjoint sets or strata; sample from each stratum separately; and combine the evidence from each stratum into an overall estimate.

Stratified sampling improves estimate accuracy in two ways. First, if the characteristic of interest (in e-discovery, the proportion of responsive documents) differs systematically between sub-populations, then accuracy is gained by estimating the characteristic for each sub-population separately, and then aggregating it for the population as a whole. The increase in accuracy comes because we substitute lower within-sub-population for higher between-sub-population sampling error.

Say, for example, we're estimating the average weight of a mixed herd of great danes and chihuahuas. In stratified sampling, we sample from the great danes and from the chihuahuas separately, and only have to worry about whether the sampled great danes are representative of all great danes, and the sampled chihuahuas of all chihuahuas. In simple random sampling, we sample dogs indifferently, and then have to worry about whether the sampled dogs are representative of dogs in general. Happening unawares to sample more great danes than chihuahuas will hurt our estimate a lot; happening by chance to sample more heavy chihuahuas than light chihuahuas will hurt our estimate only a little.

Stratified sampling offers an additional advantage if sub-populations have differing homogeneities. The more heterogeneous a sub-population, the less accurate a sample-based estimate. We can achieve greater accuracy for the same sample budget by sampling the more heterogeneous sub-population at a higher rate than the more homogeneous sub-population. If our chihuahuas all have similar weights, while the great danes are more variable, then we're better off devoting more samples to the great danes, and fewer to the chihuahuas.

How does all of this apply to production evaluation in e-discovery? Here, we have two clearly defined sub-populations: the (candidate) production and the null set. These sub-populations differ significantly in the characteristic of interest, namely the proportion of responsive documents: the production is likely to be dense with them, the null set vary sparse. The null set is also far more homogeneous, being overwhelmingly non-responsive, and so we can sample it more lightly and assign the saved annotations to the more heterogeneous production. (*)

We can go further and divide the collection into more strata than just the produced and null sets. Most contemporary predictive coding systems are able to rank documents by probability of responsiveness, with the production being determined by truncating the ranking at some cutoff. The documents in the null set just below this cutoff are more likely to be responsive than the documents further down. Therefore, it makes sense to divide the null set into two (or more) strata based on this ranking, and sample the upper null set more densely than the lower null set---to look, in essence, for responsive documents missed by the production where we are more likely to find them.

Finally, we require a method of estimation, not just of point estimates, but of confidence intervals. For simple random sampling, the simple binomial confidence interval is used, on the proportion of sampled responsive documents that happen to fall in the production. Interval estimation for stratified sampling is more complex, which has perhaps deterred practitioners to date. However, a method of estimating confidence intervals on recall from stratified sampling is described and validated in my recently published ACMTOIS article, Approximate Recall Confidence Intervals (January 2013, Volume 31, Issue 1, pages 2:1--33) (free version in arXiv). In a later posting, I will provided worked examples with the two sampling and interval methods, and illustrate the significant cost savings that stratified sampling offers.

(*) In practice, predicting the optimal sample allocation between null set and production set is more complicated than just observing which has the higher prevalence, since the production set yield occurs twice in the recall formula (one as numerator, one as denominator), and the null set yield is a divisor, not an added term, in the formula. We will examine this issue in more detail in a later post.

This entry was posted on Thursday, April 18th, 2013 at 4:46 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.