Data System

Location:

Gaithersburg, MD

Posted:

February 18, 2013

Contact this candidate

Resume:

Improving Variance Estimation in Biometric Systems

Ross J. Micheals

Image Group, Information Access Division, Information Technology Lab

National Institute of Standards and Technology

Gaithersburg, MD, USA *****@****.***

Terrance E. Boult

Vision and Software Technology Lab, University of Colorado at Colorado Springs

. Colorado Springs, CO, USA, tboult at uccs.edu

Abstract and computing the performance metric. A single measure-

ment alone, however, gives limited insight into the expected

Measuring system performance seems conceptually range of performance values should the experiment be run

straightforward. However, the interpretation of the results again. For this, we need to estimate the variance of the po-

and predicting future performance remain as exceptional tential results, and ideally, their corresponding likelihoods of

challenges in system evaluation. Robust experimental de- occurring. Various vision papers have looked at computing

sign is critical in evaluation, but there have been very few performance with added statistical data or con dence inter-

techniques to check designs for either overlooked associa- vals [2, 3, 5, 8, 12, 13, 15]. However, none of these methods

tions or weak assumptions. For biometric & vision system feature built-in mechanisms for testing their own sampling

evaluation, the complexity of the systems make a thorough assumptions.

exploration of the problem space impossible this lack of The concept of compatible data is more nebulous. For

veri ability in experimental design is a serious issue. In this vision systems, the mapping from real-world predicates to

paper, we present a new evaluation methodology that im- cofactors that impact the system is very complex. If the

proves the accuracy of variance estimator via the discovery mapping from these cofactors to the actual data produces

of false assumptions about the homogeneity of cofactors an unpredicted clustering, the observations within an experi-

i.e., when the data is not well mixed. The new method- ment may not be compatible. On the subject of homogeneity

ology is then applied in the context of a biometric system and the implications of clustered data, Kish [9] wrote The

evaluation with highly in uential cofactors. correspondence with the well-mixed urn, inherent in the

assumption of independence, is negated; and formulas that

depend on that assumption fail to apply. Therefore, con-

sider the following de nition. Given a pair of observations

1 Introduction (X, Y ), where X is a vector of cofactors and Y are values

of interest, we consider a cofactor Xi to be suf ciently ho-

Conceptually, measuring system performance is straightfor-

mogeneous if and only if, across trials of an experiment the

ward run the system over input data, then compare the

Xi s are independent and identically distributed (iid). This is

output and ground truth reporting some metric. With the

compatible with the desire in experimental design that in u-

data volume requirements inherent to biometric systems, the

ential factors be either (a) constrained or (b) suf ciently ran-

mechanics and logistics involved in running a system evalu-

domized. In either case, the cofactor would be suf ciently

ation are considerable often requiring resources on a gov-

homogeneous, and might be analyzed as an (a) xed or (b)

ernment scale [18, 20]. Results from an evaluation are most

random effect in a statistical model [16]. Homogeneity of all

valuable if they can be used as predictors of performance

cofactors is not a necessary condition for Y to be iid, since it

on compatible data. But what is meant precisely by perfor-

is possible that a cofactor has a nominal effect on the obser-

mance prediction and compatible data?

vations. Note that such a model requires explicitly culling

From a statistical perspective, system performance pre-

out each cofactor Xi .

diction is often viewed as a parameter estimation problem.

For biometric systems, this might be a system s identi ca- If a model departs from the observed data, then the va-

tion rate or some point on an ROC. Traditionally, the perfor- lidity of the proposed homogeneity assumptions is circum-

mance parameter is estimated by executing an experiment spect. That is, suppose for a given experiment, the statistic

of interest is, the variance of some performance metric Computational experiments and simulations that allow for

across multiple trials. Let represent the point estimator the generation of large amounts of data are a particularly

of computed from a single trial. Then, if, the average

good t to the proposed method. This methodology may be

used to not only select an appropriate variance estimator for

point estimator of the sample variance and, V [ ], the sample

an experiment, but also provide an estimator that is empiri-

variance of the parameter of interest do not converge that

2 cally justi ed. Using an empirically justi ed variance esti-

is, if = V [ ] does not hold as the number of trials goes

mate represents a signi cant improvement from the common

to in nity, then this indicates that at least one of the assump-

practice of selecting a traditional variance estimator (along

tions required for this equality to hold must be false. One of

with its requisite assumptions) out of convenience.

the most common model departures, the one addressed here,

is the violation of the iid assumption that is, one or more

of the cofactors Xi or observations Yi are not suf ciently

2 Background

homogeneous.

Statistical literature is rich with research regarding the ef- The distribution of a random variable is hierarchical if that

fects of cofactors that do not meet the experimenter s expec- random variable is realized through sampling of a cascade

tations once they are known [10]. While many researchers of two or more component distributions, or stages. A typical

consider explicit cofactors in their experiments, it seems mixture distribution (such as a mixture of Gaussians com-

there as been little discussion within the performance eval- monly used in modeling vision systems) is a two-stage hier-

uation literature as a whole (particularly within biometrics) archical distribution since each realization requires two sep-

with respect to the discovery of in uential cofactors that re- arate samplings. In hierarchical models of two levels, the

main unmodeled. high-level stage or hyper-distribution is effectively a distri-

In this paper we present a methodology that can be used bution of distributions.

to help identify false cofactor homogeneity assumptions. Many system evaluations are concerned with random

The new methodology is not a panacea and is no substi- variables having distributions that are hierarchical in nature.

tute for thoughtful experimental design. It can, however, For example, consider the distribution of the input to a clas-

help guide an evaluator in determining the validity of various si er system. The rst stage corresponds to the selection of a

cofactor assumptions. Unlike other biometric or classi er- particular class and the second stage corresponds to a partic-

oriented methods [2, 3, 8], a distinguishing characteristic of ular instance of the selected class. Hierarchical distributions

this research is the recognition that in uential cofactors may can be problematic with respect to cofactor homogeneity

each have their own sample designs, and that this sample de- when they are sampled in non-designed ways. Speci cally,

sign may have a large in uence on the resultant variance and when data contains repeated measures, there can be groups

therefore, con dence intervals. of data that share an in uential cofactor in an unbalanced

The new methodology has some unique features worth fashion. From a distributional standpoint, repeated measures

separate consideration: can occur whenever one level of the hierarchy is constrained

Iterative The new methodology is iterative in nature. in a manner inconsistent with other observations. For exam-

This allows information gained from one analysis to be used ple, in a classi er experiment in which m instances of each

as feedback to the next iteration. In this manner experi- of n classes are observed, the classi er label (certainly an

menters can adjust assumptions until they fail to reject a important cofactor) is not well-mixed in the iid sense.

proposed sampling design. Given the often large amounts The statistics of survey sampling are particularly well-

of data/computation needed in vision this iterative feature is suited for repeated measurements [6, 10]. However, tradi-

well suited to vision system evaluation. tional survey sampling is primarily concerned with model-

Hierarchical In its current form, the methodology is best ing nite populations, or more generally, with observations

suited, but not limited to, for random variables (RVs) hav- made by a sampling process that eventually terminates. The

ing distributions that are hierarchical in nature. (Hierarchical nite population correction terms found in survey sampling

RVs will be reviewed in the following section). estimators ensure that if, in each trial, all of the population

Binary The new methodology exploits some unique re- elements are selected and selection occurs without replace-

lationships between survey sampling and binary data. These ment, then the variance of a statistic across different trials

properties are at the core of the methodology s capability will be zero.

to provide evidence against false cofactor homogeneity as- The vast majority of biometric system evaluations, how-

sumptions. ever, are concerned with modeling in nite quantities of

The methodology is primarily data-driven, i.e., the input-output pairs. The potential values that these pairs may

data of interest itself is used to explore the cofactors of in- take on may be nite, but the process by which these val-

terest. Therefore, the methodology is most convenient for ues are generated does not terminate in the same sense as

use in studies where the experiment can be easily repeated. sampling from nite population without replacement. Like-

selecting, across trials, the same n hyper-distributions. No-

wise, sampling a nite population with replacement is not a

process that must terminate. tice that having a hyper-distribution that is effectively dis-

As noted in [4, 11, 22], traditionally, random variable- crete is a necessary condition for strati ed sampling. A

oriented research lacks robustness when it comes to de- hyper-distribution might cover an in nite population, but if

scribing data with complex sample designs (i.e., non-iid the sampling process results in a deterministic and repeat-

data). Speci cally, it is not a general rule that survey able selection of particular mixture components, then strati-

sampling estimators can be applied to in nite populations ed sampling results, since the same distributions (or strata)

without breaking down. For example, consider the nite from the hyper-distribution are selected each trial.

For an unbiased estimator of V [E [ i ]], the variance of the

population strati ed sampling estimator from [6](p. 92),

[M (M m n2 m) i Si, where M is the total elements expected value of the stratum means is Si /nm. Let Xij be

per stratum, m is the number of sampled elements per stra- the j th element of stratum i. Thus

tum, N is the number of strata and Si is the element vari- n m

ance of stratum i. Clearly, this estimator breaks down as V [Xst ] = V [Xij ]. (1)

n 2 m2

M approaches in nity. Therefore, what is needed is a col- i j

lection of unbiased estimators for various sample designs as

Since Xij and Xij share the same distribution Fi so

they correspond to in nite population models. This requires

adapting the sample design concepts from survey sampling n m

to random variables. Speci cally, we adapt the variance esti- V [Xst ] = V [Xi ] (2)

n 2 m2

mators for simple random sampling, strati ed sampling, and i j

cluster sampling.

However, by de nition of the strati ed sampling process,

samples are iid within a stratum, so

2.1 Variance Estimators

Let a repeatable experiment be an experiment that can be n n

1 1

V [Xst ] = mV [Xi ] = i (3)

modeled statistically and veri ed empirically. While most 2 m2 2m

n n

experiments have a potentially in nite number of parame- i i

ters that can be modeled, our focus will be on the minimal 2

where i is the variance of the statistic of interest over

modeling needed for prediction i.e. on estimating vari-

stratum i. Therefore, an unbiased estimator of V [Xst ] is

ance. In survey sampling, the sample design dictates the 2 /nm, since E [S 2 ] = 2 /n. This form is similar, but not

Si i

variance estimators. The method proposed here inverts that

quite the same as the survey sampling estimator for nite

tradition seek a sample design in which the variance es-

populations.

timate computed from a single trial agrees with the average

sample variance from repeating experiments. When this is 2.1.3 Cluster Sampling

not true, the assumed sample design is rejected. In survey sampling, cluster sampling involves two stages

of srs. From a random variable standpoint, this is tanta-

2.1.1 Simple Random Sampling

mount to rst, realizing a distribution e.g. xing a hyper-

We begin with the relationship between simple random sam-

distribution parameter and second, sampling iid data from

pling (srs) and iid data. In survey sampling, srs implies that

that constrained distribution. Note the subtle, but impor-

every population element has the same (uniform) probability

tant difference from strati ed sampling, where the very same

of being selected. We can make an analogous construction

subpopulations are selected every trial.

for random variables. Consider a discrete population of n

We derive the variance of the cluster sample mean for

elements, where each element xi has a relative frequency fi .

doubly in nite populations by rst considering the case in

Then, it is trivial to construct an index set over the interval

which the mean is computed from m samples of one hyper-

[0, 1) and a mapping F 1 from indexes to outcomes such

distribution sample. This case is easily generalized to n

that F 1 is the quantile function of F, the CDF of all fi s. n

hyper-distributions since, for iid X s, V [ X ] = nV [X ].

Then, a uniform selection over the index set generates iid

We make use of the conditional variance formula,V [X ] =

samples of F [17]. A similar construction can be used for

E [V (X )] + V [E (X )] where xing corresponds to se-

the continuous case.

lection from the hyper-distribution. From this, V [E (X )]+

m E [V (X )]. Therefore, for n repetitions of the sample

2.1.2 Strati ed Sampling

process

In survey sampling, strati ed sampling involves partitioning

the population into n non-overlapping groups, or strata, and 1 1

V [E (X )] + E [V (X )]

V [Xcl ] = (4)

then systematically selecting m elements via srs within each n nm

stratum. Given the duality of srs and iid data, it follows that 1 1 2

= V [ i ] + E [ i ] (5)

for in nite populations, strati ed sampling is tantamount to

n nm

3 Methodology Outline

An unbiased estimator of V [X ] is still needed. We might use

2 = 2 2 2

a linear combination of Si Si /n for E [ i ] and S = With the terminology de ned, we proceed with an overview

( i )2 /(n 1) for V [ i ]. Although E [Si ] = E [ i ],

of the new methodology. The overall process consists of

note that E [S ] = V [Xi ]. Another application of the con- three steps that are repeated ias long as a violation of as-

2 sumptions is detected. First (dichotomization step), reduce

ditional variance formula yields E [S ] = V [ i ] + m E [ i ]

]. Com- the statistic of interest to a binary value. Second (assump-

which gives S /n as an unbiased estimator of V [Xcl

tions step), propose a data partition and sample design. Third

paring this with Equation (3), we can see that the difference

(analysis step), compare the sample (empirical) statistic to

between strati ed and cluster sampling leads to signi cantly

the point estimate average. If the statistics are not considered

different variance estimators.

compatible, reject the proposed assumptions and iterate.

2.2 Binary Data

3.1 Dichotomization Step

It was mentioned previously that a key enabler of the new

The rst step of the methodology is to reduce the system

methodology stems from reduction to binary data. In perfor-

output to a binary value. In evaluations where the metric of

mance evaluation this is common we produce experiment

interest is a rate of success or failure, this usually involves a

data that is classi ed as either a success or a failure. We

simple thresholding of a result.

may group this into higher level constructs, such as an ROC

Dichotomizing the performance measures allows for the

curve, but the inherent binary nature has important implica-

exploitation of some unique interactions between sample de-

tions on the statistical models we can use.

sign and binary data. However, it is not without disadvan-

For a two-stage hierarchical distribution in which the -

tages. For scalar data, the binary requirement is nominal,

nal observations are binary, the hyper-distribution consists

since it can be thresholded and the analysis performed over

of the space of all single-dimensional distribution functions

a wide variety of thresholds. Multidimensional data or scalar

over [0, 1]. It follows that the second stage is a Bernoulli dis-

data depending on multiple cofactors may require a complex

tribution with mean (probability of success) and variance

2 transformation or an analysis in a high-dimensional space.

(1 ). Let and represent the true mean and vari-

This view could make the application of the new methodol-

ance of, as determined by the hyper-distribution parame-

ogy dif cult. While it might be tempting to view this as a

ter . Then, for cluster sampling, we combine the identity

E [ 2 ] = (1 ) with Equation (4), to get

2 preprocessing step and try to have a methodology that sim-

ply uses the dichotomized data, including this in the itera-

2 2

(1 )

tive process is important because a poor projection into the

V [Xcl ] = + (6)

n nm binary space may itself cause unmodeled clustering of the

(m 1) (1 ) data that impacts predictability. It has been shown that the

= + (7)

thresholding of performance measures can be problematic

nm nm

when it forces the results into the tails of the distribution.

Observe, that for srs, m = 1, so V [Xsrs ] = (1 )/n.

Therefore, V [Xsrs ] from n = nm samples is always less 3.2 Assumptions Step

than or equal to V [Xcl ].

The second step of the methodology is to assume a set of in-

For strati ed sampling, each stratum has its own prob-

uential cofactors along with a sample design. The grouping

ability of success, i . From Equation (3), V [Xst ] =

involves selecting a partition P based on cofactors X that the

i i (1 i ). This is equivalent to

n2 m experimenter believes divides the observations Y into one of

n the equivalence classes such that (1) for each set, all obser-

i i

(1 )

V [Xst ] =, (8) vations within an equivalence class are mutually iid and (2)

n2 m

that the observations Y are partially exchangeable [7] ac-

which is always less than or equal to V [Xsrs ] for nm sam- cording to P . Standard survey sampling theory (e.g. [6]) can

ples. be used to show that the estimators derived in Section 2.1

In conclusion, for two-stage hierarchical distribution of hold for (1). Sugden [21] shows that the estimators hold for

binary outcomes, the following inequality always holds true the more relaxed constraints in (2).

In addition to proposing a partition, an experimenter must

V [Xst ] V [Xsrs ] V [Xcl ]. (9)

consider a sample design at each level of the hierarchy in

The next step is to demonstrate the great utility of this this methodology we restrict ourselves to comparing three

inequality. The effect of different kinds of groupings cou- designs, strati ed sampling (st), simple random sampling

pled with the reconciliation of the observed versus expected (srs), and cluster sampling (cl). If an in uential cofactor is

variances provide insight into the effect of the cofactors that selected in a deterministic, repeatable fashion, this suggests

de ne those groupings. that strati ed sampling is in use. Cofactors that are randomly

selected, but constrained for sets of observations, suggest basic function of the Photohead system is to isolate the ef-

that a cluster sampling process is present. Cluster sampling fects of sensors/weather by displaying a sequence of facial

collapses to simple random sampling when the number of imagery, and recapturing the image via another sensor lo-

elements is one. That is, observations are made via the same cated at some distance away from the display. Such a re-

process, and the level of the cofactor is not dependent on the imaging would effectively isolate the degradation of image

trial number. quality due to environmental and sensor effects. Because the

Photohead system uses a displayed image and not a live sub-

ject, the recognition results are potentially confounded with

3.3 Analysis Step

cofactors due to the imaging display. However, the effect

Finally, in the analysis step, the sample variance of the statis-

of that confounding is much simpler than subject variations

tic of interest is compared with the average point estimate of

over time or pose variation. Therefore, although the Pho-

the sample variance. Only the means of Vcl and are of in-

tohead system is not a replacement for using actual human

] can be made arbitrar-

terest in the analysis phase, since V [

subjects, it does provide a much more practical, and repeat-

ily small by increasing the number of trials per experiment.

able, mechanism for obtaining the vast amount of outdoor

If and only if the statistic of interest is known to be of a

data required for such an analysis and also helps isolate par-

particular distribution, then the analysis step could be made

ticular variables of interest.

more formal by using a hypothesis test to decide whether

Functionally, the Photohead system takes a set of origi-

or not to reject the proposed grouping and sample design.

nal images as input, and produces a set of degraded images,

We recommend that should a hypothesis test be used, it be

or reimaged data. A data collection refers to the generation

used only in the very last iteration of the methodology so

of a particular set of degraded images. The server side of

that an experimenter does not reach conclusions about any

the software controlled the image display, while the clients

particular assumptions prematurely.

were in charge of capture, where each client corresponded

The desired output of the analysis stage is not only a par-

to a different sensor. At xed intervals throughout the day, a

tition that is not rejected, but also insight into the effect of

data collection would begin by logging the time of day, and

the cofactor of interest and how it is sampled. For exam-

downloading, from the National Weather Service website,

ple, consider the case where for a particular cofactor, cluster

the weather conditions at the nearest airport.After shuf ing

sampling is assumed but the sample variance is more similar

the order in which the set of original images would be dis-

to simple random sampling. Then, an evaluator may wish to

played the server would display an image, and indicate that

perform another experiment in which a cofactor previously

an image was ready for capture. Upon receiving the signal,

suspected as in uential is demoted to a nuisance parameter.

each client would capture an image from their assigned sen-

The analysis phase might also suggest that additional ran-

sor and signal back to the server that they had captured an

domization is needed. Suppose that no estimator i.e., nei-

image. The server, after receiving a signal from each client,

ther Vst, Vsrs, nor Vcl is compatible with a particular par-

would repeat the process, until every image in the original

tition. The divergence of the sample variance and the point

set had been recaptured. The Photohead data was collected

estimators could be due to a basic lack of stationarity re-

over several months and across all times of day. The im-

quired for obtaining a repeatable experiment. We investigate

ages were degraded from a large variety of weather effects

this phenomenon with a real experiment in the next section.

including snow, rain, fog, and wind.

The Photohead data includes multiple images of each

4 Experimentation subject so a standard FERET-style [19] probe/gallery test is

In this section, we apply the new methodology to the bio- possible each probe differs from the gallery by a change

metric system evaluation installation which we will refer to in some variable of interest. In a test like FERET, the same

as the Photohead experiments. The main goal of this section image would never be used in both the gallery and the probe

is to show a systematic application of the new methodology set because not only does this not makes sense operationally,

for a biometric system evaluation with strong in uential co- but it also changes the face recognition problem into a triv-

factors (such as time and subject). ial image matching problem. An important idea in the Pho-

The Photohead system is a testbed designed to evaluate tohead project, a form of self-matching, is somewhat con-

the in uence of environmental and sensor effects on the per- trary to what one would do in a more traditional evaluation.

formance of face recognition systems. Collecting suf cient Suppose, instead of a probe-gallery pair consisting of two

data for many different subjects, over all times of day and different images of the same person, we used the same im-

weather conditions, is simply not feasible. Furthermore, the age, except that the probe version of the image undergoes

inherent variance in pose and subject would be confounded some form of digital or analog processing such as imaging

with the sensor and environmental effects, but separating the through the weather. For this experiment, a face that is in

cofactors would require a very large amount of data. The exactly the same pose and lighting helps to isolate effects of

weather and sensor cofactors from other cofactors. Thus the

self-matching experiments, any deviation from ideal perfor-

mance can therefore be attributed solely to the analog degra-

dation or image processing.

The facial imagery used for the Photohead experiments

also came from the well-known FERET database. The

source data consists of 1,024 images, four each of 256 sub-

jects. Let S represent the set of all 1,024 images, S1 consist

of the all of the rst images of the 256 subjects, S2 the sec-

ond, and so on. During a single data collection, all 1,024 im-

ages are displayed, and recaptured. Let S t represent the set

of recaptured images from the data collection started at time

t. Then, all 1,024 recaptured images S t are compared via

Figure 1. Baseline sample variance and average point estimator of

a commercial face recognition algorithm to all of the origi- that variance. For this case, all estimators are severely overdis-

nal 1,024 images S, producing a similarity matrix. Since we persed (underestimate the true variance). The solid (red) line corre-

are interested in isolating the sensor and atmospheric effects, sponds to the sample variance, the dotted (green) line corresponds

we will primarily be interested in the experiments in which to the mean cluster sampling point estimator, the dashed (gray) line

Si is a gallery and Si a probe set. If re-imaging effects are corresponds to the mean simple random sampling point estimator,

and the dot-dash (blue) line corresponds to the strati ed sampling

nominal, then our identi cation rate should be 100 percent.

estimator.

4.1 Analysis

nored (i.e., considered nuisance parameters), xed, or ran-

Our analysis involves computing collections of point estima-

domized.

tors and comparing their mean to a set of sample statistics.

The evaluations consist of nested loops that group, sample, In our rst experiment, we consider strati ed sampling

and calculate the various statistics of interest. The nested over the (rank one) identi cation rate for clear days, where

loops correspond to different trials, runs, and experiments. the data is partitioned by subject. The corpus of data has

An experiment may consist of several trials. The experi- 1,440 such collections (as de ned in the previous section),

so the total experimental data is a 256 1, 440 array. For

ment may itself be repeated in another run. Point estimators

are generated at the trial level sample (empirical) vari- each experimental run, 180 columns were selected, without

ances are determined per run. Each experimental run has replacement, from the full data array. Then, each experiment

is broken into a multitude of trials, or 180/m matrices of

an associated block of data; the particular block depending

size 256 m where m is the number of elements per trial.

on the conditions under consideration. It is easiest to visu-

(m = 4 is chosen out of convenience, but other values work

alize the data as a large table, where each row of the table

is a group (i.e., a cluster or stratum), the columns as differ- as well [14]).

ent data collections, and within each cell is a set of scores The results of this initial partition are shown in Figure 1.

generated by a particular probe. This set of scores can trans- In these experiments, all trials for a given experiment have

formed to a summary statistic. To simplify the analysis, we the same set of xed subject, each group within a trial has

choose recognition rank (as de ned by the FRVT 2002 pro- the same xed subject, and all other potential cofactors are

tocol [18]) because it is unidimensional. ignored. As evident in the graph, the empirical variance (red,

Within a run, each experiment uses a random subset of the solid line) is grossly underestimated, regardless of the class

total data, which is at most, one-half of the data. Therefore, of estimators, which are orders of magnitude away (the y -

across experiments, data is sometimes reused. This is not as axis is logarithmic). This indicates that the data, used as

desirable as having new data for each experiment, however, is, fails to capture a large amount of variance. Therefore,

we save the availability of new data for intra-experiment use. the data is not yet well-mixed. One way of resolving this

That is, the statistics across experiments are primarily qual- would be to model an additional level in the hierarchical dis-

itative where the statistics are used quantitatively, within tribution i.e., try cluster strati ed sampling or three-stage

an experiment, different trials do not share data. cluster sampling. While this might incorporate the discrep-

As discussed in section 3.2, in these experiments we re- ancy numerically, it would neither give us insight into why

strict ourselves to comparing three designs, strati ed sam- such a difference in variance is present, nor would it allow

pling (st), simple random sampling (srs), or cluster sampling us to compare sample variances and point estimators, since

(cl). Each design has an associated variance estimator which we would be reducing our entire dataset into a single point

will be compared to the point estimator described above. For estimator. It also suggests if we had just blindly applied a

each iteration, we identify if the cofactors of interest are ig- statistical analysis of the sample of convenience e.g. us-

Figure 2. Sample variance (solid red line) and average point esti- Figure 3. Sample variance (solid red line) and average point estima-

mators of that variance when randomizing over time. (Cluster in tor of that variance when randomizing over time and grouping by

dotted green, simple random in dashed grey, and strati ed in dot- (original) image. (Cluster in dotted green, simple random in dashed

dash blue.) This is a clear improvement over the previous case. grey, and strati ed in dot-dash blue.) Finally we have agreement

between the sample variance and a class of estimator, with strati-

ed sampling being most appropriate for this experiment.

ing Bernoulli as a basis for hypothesis testing we would

not obtain meaningful results.

future research.

To nd the source of this variance, a series of lattice plots

These three graphs demonstrate importance of sampling

were generated (not shown). On visual inspection, it was

design for estimation, and the methodology in action. While

apparent that the most in uential cofactor was time. There-

for this data, strati ed sampling variance estimator was the

fore, to better accommodate any time-dependent variance,

best match, that is not always the case different designs

we introduce a randomization step at the beginning of the

yield different results. Consider the case where we use dif-

experiment phase. If we shuf e all of the data within a row,

ferent subjects per trial. Figure 4 shows the results when

then we simulate the condition where, within a stratum, im-

partitioning on original image with temporal randomization.

ages are taken at a random time. By shuf ing each row inde-

In this case, the set of images per trial is randomized, each

pendently, and uniformly, we reduce the dependence caused

group within a trial has a xed original image, and time is

by all of the nth images within a group sharing the same

randomized within each group. This graph demonstrates

timestamp. This effectively, helps homogenize the cofactor

the critical nature of considering the proper sample design.

of time.

Given the same underlying data, we have vastly different

The results after temporal randomization are shown in

variances given different selection mechanisms i.e, if we

Figure 2. Here, we have a xed set of subjects across tri-

use strati ed or cluster sampling.

als, a xed subject per group, but unlike the previous graph,

In summary, this section showed how the new method-

we now randomize over time within each group. This is cer-

ology can be applied to a real biometric experiment. By

tainly an improvement of the previous graph the point

rejecting homogeneity assumptions that were clearly incor-

estimates are no longer orders of magnitudes away from

rect, an estimator compatible with the empirical variance

the sample variance. However, we have now overestimated

was achieved. Understanding the variance and the nature

the sample variance, for strati ed sampling, simple random

of the sampling establishes the foundation for the applica-

sampling, and cluster sampling. This suggests we still have

tion of techniques such as BRR or Fay s Method [15, 23],

not selected the best criterion for our data partition.

which allow for variance estimation of more general, non-

Recalling our experimental setup, consider a partition linear statistics, such as the degrees of freedom estimate re-

based on degraded images corresponding to the same orig- quired for con dence intervals.

inal image. That is, we have 1,024 instead of 256 groups

since there are four original images per subject. These re-

5 Conclusions

sults are shown in Figure 3. Here, we have a xed set of

subjects across trials, a xed original image per group, but In this paper we showed a new methodology for rejecting

we still randomize over time per group. This graph gives incorrect homogeneity assumptions in evaluation. We illus-

strong evidence that for this Photohead installation, strati- trated the methodology in the context of a real biometric sys-

ed sampling given temporal randomization is the most ap- tem evaluation. Given randomization over time, and parti-

propriate variance estimator. A more formal hypothesis test tioning by original image, the Photohead data was compati-

might be devised to test this assumption; this is a subject of ble with strati ed or cluster sampling, depending on whether

[3] R. M. Bolle, N. K. Ratha, and S. Pankanti. Con dence inter-

val measurement in performance analysis of biometrics sys-

tems using the bootstrap. In Proc. Third IEEE Workshop

on Empirical Evaluation Methods in Computer Vision, 2001.

CVPR 2001 Workshop.

[4] C.-M. Cassel, C.-E. Sarndal, and J. H. Wretman. Foundations

of Inference in Survey Sampling. John Wiley & Sons, 1977.

[5] K. Cho, P. Meer, and J. Cabrera. Performance assessment

through bootstrap. IEEE PAMI, 19(11):1185 1198, Novem-

ber 1997.

[6] W. G. Cochran. Sampling Techniques. John Wiley & Sons,

third edition, 1977.

[7] B. de Finetti. Theory of Probability: A Critical Introductory

Treatment. John Wiley & Sons, 1970.

Figure 4. Sample variance (solid red line) and average point estima-

[8] D. D. Jensen. Induction with Randomization Testing:

tor of that variance when randomizing over time and grouping by

Decision-Oriented Analysis of Large Data Sets. PhD thesis,

(original) image. (Cluster in dotted green, simple random in dashed

Washigton Univ., May 1992.

grey, and strati ed in dot-dash blue.) Between trials, different sub-

[9] L. Kish. Con dence intervals for clustered samples. Ameri-

jects are used. This time the results are compatible with cluster

can Sociological Review, 22(2):154 165, April 1957.

sampling. The sample variance point estimator shows a high vari-

ation due to the reduced number of trials per experiment chang- [10] L. Kish. Survey Sampling. John Wiley & Sons, 1965.

ing subjects each trial without overlap severely limits the number [11] L. Kish and M. R. Frankel. Inference from complex samples.

of independent repetitions (per experiment) that can be performed. Journal of the Royal Statistical Society B, 36(1):1 37, 1974.

[12] B. Matei, P. Meer, and D. Tyler. Empirical Evaluation Tech-

niques in Computer Vision, chapter Performance Assessment

or not the same (strati ed sampling) or different (cluster by Resampling: Rigid Motion Estimators. IEEE Computer

sampling) original images were selected between trials. Us- Society, 1998.

ing the proposed methodology, the accuracy of these vari- [13] P. Meer and B. Georgescu. Edge detection with embedded

ance estimators was examined. con dence. IEEE Trans. PAMI, 23(12):1351 1365, 2001.

Having a valid variance estimator is the most critical [14] R. J. Micheals. Biometric System Evaluation. PhD thesis,

component in obtaining con dence intervals. The variance Lehigh Univ., 2003.

estimates developed using this methodology may be trans- [15] R. J. Micheals and T. E. Boult. Ef cient evaluation of clas-

si cation and recognition systems. In Proc. IEEE Conf. on

formed into con dence intervals by combining a resampling

Contact this candidate