Bootstrapping populations

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Starting with a sample \{x_1,\ldots,x_m\} observed from a random variable X having a given distribution law with a set of non fixed parameters which we denote with a vector \boldsymbol\theta, a parametric inference problem consists of computing suitable values – call them estimates – of these parameters precisely on the basis of the sample. An estimate is suitable if replacing it with the unknown parameter does not cause major damage in next computations. In Algorithmic inference, suitability of an estimate reads in terms of compatibility with the observed sample.

In this framework, resampling methods are aimed at generating a set of candidate values to replace the unknown parameters that we read as compatible replicas of them. They represent a population of specifications of a random vector \boldsymbol\Theta [1] compatible with an observed sample, where the compatibility of its values has the properties of a probability distribution. By plugging parameters into the expression of the questioned distribution law, we bootstrap entire populations of random variables compatible with the observed sample.

The rationale of the algorithms computing the replicas, which we denote population bootstrap procedures, is to identify a set of statistics \{s_1,\ldots,s_k\} exhibiting specific properties, denoting a well behavior, w.r.t. the unknown parameters. The statistics are expressed as functions of the observed values \{x_1,\ldots,x_m\}, by definition. The x_i may be expressed as a function of the unknown parameters and a random seed specification z_i through the sampling mechanism (g_{\boldsymbol\theta},Z), in turn. Then, by plugging the second expression in the former, we obtain s_j expressions as functions of seeds and parameters – the master equations – that we invert to find values of the latter as a function of: i) the statistics, whose values in turn are fixed at the observed ones; and ii) the seeds, which are random according to their own distribution. Hence from a set of seed samples we obtain a set of parameter replicas.

Method[edit]

Given a \boldsymbol x=\{x_1,\ldots,x_m\} of a random variable X and a sampling mechanism (g_{\boldsymbol\theta},Z) for X, the realization x is given by \boldsymbol x=\{g_{\boldsymbol\theta}(z_1),\ldots,g_{\boldsymbol\theta}(z_m)\}, with \boldsymbol\theta=(\theta_1,\ldots,\theta_k). Focusing on well-behaved statistics,

s_1=h_1(x_1,\ldots,x_m),
  \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots
s_k=h_k(x_1,\ldots,x_m),

for their parameters, the master equations read

s_1= h_1(g_{\boldsymbol\theta} (z_1),\ldots, g_{\boldsymbol\theta} (z_m))= \rho_1(\boldsymbol\theta;z_1,\ldots,z_m)
  \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots (1)
s_k= h_k(g_{\boldsymbol\theta} (z_1),\ldots, g_{\boldsymbol\theta} (z_m))= \rho_k(\boldsymbol\theta;z_1,\ldots,z_m).

For each sample seed \{z_1,\ldots,z_m\} a vector of parameters \boldsymbol\theta is obtained from the solution of the above system with s_i fixed to the observed values. Having computed a huge set of compatible vectors, say N, the empirical marginal distribution of \Theta_j is obtaineded by:

\widehat F_{\Theta_j}(\theta)=\sum_{i=1}^N\frac{1}{N}I_{(-\infty,\theta]}(\breve\theta_{j,i}) (2)

where \breve\theta_{j,i} is the j-th component of the generic solution of (1) and where I_{(-\infty,\theta]}(\breve\theta_{j,i}) is the indicator function of \breve\theta_{j,i} in the interval (-\infty,\theta]. Some indeterminacies remain if X is discrete and this we will be considered shortly. The whole procedure may be summed up in the form of the following Algorithm, where the index \boldsymbol\Theta of \boldsymbol s_{\boldsymbol\Theta} denotes the parameter vector from which the statistics vector is derived.

Algorithm[edit]

Generating parameter populations through a bootstrap
Given a sample \{x_1,\ldots,x_m\} from a random variable with parameter vector \boldsymbol\theta unknown,
  1. Identify a vector of well-behaved statistics \boldsymbol S for \boldsymbol\Theta;
  2. compute a specification \boldsymbol s_{\boldsymbol\Theta} of \boldsymbol S from the sample;
  3. repeat for a satisfactory number N of iterations:
    • draw a sample seed \breve{\boldsymbol z}_i of size m from the seed random variable;
    • get \breve{\boldsymbol\theta}_i=\mathrm{Inv}(\boldsymbol s,\boldsymbol z_i) as a solution of (1) in θ with \boldsymbol s=\boldsymbol s_{\boldsymbol\Theta} and \boldsymbol z_i = \{\breve z_1,\ldots,\breve z_m\};
    • add \breve{\boldsymbol\theta}_i to \boldsymbol\Theta; population.
Cumulative distribution function of the parameter Λ of an Exponential random variable when statistic s_\Lambda=6.36
Cumulative distribution function of the parameter A of a uniform continuous random variable when statistic s_A=9.91

You may easily see from a table of sufficient statistics that we obtain the curve in the picture on the left by computing the empirical distribution (2) on the population obtained through the above algorithm when: i) X is an Exponential random variable, ii)  s_\Lambda= \sum_{j=1}^m x_j , and

\text{ iii) Inv}(s_\Lambda,\boldsymbol u_i) =\sum_{j=1}^m(-\log u_{ij})/s_\Lambda,

and the curve in the picture on the right when: i) X is a Uniform random variable in [0,a] , ii)  s_A= \max_{j=1, \ldots, m} x_j , and

\text{iii) Inv}(s_A,\boldsymbol u_i) =s_A/\max_{j=1,\ldots,m}\{u_{ij}\}.

Remark[edit]

Note that the accuracy with which a parameter distribution law of populations compatible with a sample is obtained is not a function of the sample size. Instead, it is a function of the number of seeds we draw. In turn, this number is purely a matter of computational time but does not require any extension of the observed data. With other bootstrapping methods focusing on a generation of sample replicas (like those proposed by (Efron and Tibshirani 1993)) the accuracy of the estimate distributions depends on the sample size.

Example[edit]

For \boldsymbol x expected to represent a Pareto distribution, whose specification requires values for the parameters a and k,[2] we have that the cumulative distribution function reads:

Joint empirical cumulative distribution function of parameters (A,K) of a Pareto random variable when m=30, s_1=83.24 and s_{2}=8.37 based on 5,000 replicas.
F_X(x)=1-\left(\frac{k}{x}\right)^a.

A sampling mechanism (g_{(a,k)}, U) has [0,1] uniform seed U and explaining function g_{(a,k)} described by:

x= g_{(a,k)}=(1 - u)^{-\frac{1}{a}} k

A relevant statistic \boldsymbol s_\boldsymbol\Theta is constituted by the pair of joint sufficient statistics for A and K, respectively s_1=\sum_{i=1}^m \log x_i, s_{2}=\min\{x_i\}. The master equations read

s_1=\sum_{i=1}^m -\frac{1}{a}\log(1 - u_i)+m \log k
s_{2}=(1 - u_{\min})^{-\frac{1}{a}} k

with u_{\min}=\min\{u_i\}.

Figure on the right reports the three-dimensional plot of the empirical cumulative distribution function (2) of (A,K).

Notes[edit]

  1. ^ By default, capital letters (such as U, X) will denote random variables and small letters (u, x) their corresponding realizations.
  2. ^ We denote here with symbols a and k the Pareto parameters elsewhere indicated through k and x_{\mathrm{min}}.

References[edit]

  • Efron, B. and Tibshirani, R. (1993). An introduction to the Boostrap. Freeman, New York: Chapman and Hall. 
  • Apolloni, B; Malchiodi, D.; Gaito, S. (2006). Algorithmic Inference in Machine Learning. International Series on Advanced Intelligence 5 (2nd ed.). Adelaide: Magill. "Advanced Knowledge International" 
  • Apolloni, B., Bassis, S., Gaito. S. and Malchiodi, D. (2007). "Appreciation of medical treatments by learning underlying functions with good confidence". Current Pharmaceutical Design 13 (15): 1545–1570. doi:10.2174/138161207780765891. PMID 17504150.