Algorithmic inference

Algorithmic inference gathers new developments in the statistical inference methods made feasible by the powerful computing devices widely available to any data analyst. Cornerstones in this field are computational learning theory, granular computing, bioinformatics, and, long ago, structural probability . The main focus is on the algorithms which compute statistics rooting the study of a random phenomenon, along with the amount of data they must feed on to produce reliable results. This shifts the interest of mathematicians from the study of the distribution laws to the functional properties of the statistics, and the interest of computer scientists from the algorithms for processing data to the information they process.

Algorithmic inference gathers new developments in the statistical inference methods made feasible by the powerful computing devices widely available to any data analyst. Cornerstones in this field are computational learning theory, granular computing, bioinformatics, and, long ago, structural probability . The main focus is on the algorithms which compute statistics rooting the study of a random phenomenon, along with the amount of data they must feed on to produce reliable results. This shifts the interest of mathematicians from the study of the distribution laws to the functional properties of the statistics, and the interest of computer scientists from the algorithms for processing data to the information they process. S_\mu =\sum_{i=1}^m X_i and S_{\sigma^2} = \sum_{i=1}^m (X_i-\overline X)^2,\text{ where }\overline X = \frac{S_{\mu}}{m} is the sample mean, we recognize that T=\frac{S_{\mu}-m\mu}{\sqrt{S_{\sigma^2}}}\sqrt\frac{m-1}{m} = \frac{\overline X-\mu}{\sqrt{S_{\sigma^2}/(m(m-1))}} follows a Student's t distribution with parameter (degrees of freedom) m − 1, so that f_T(t) = \frac{\Gamma(m/2)}{\Gamma((m-1)/2)} \frac{1}{\sqrt{\pi(m-1)}} \left(1 + \frac{t^2}{m-1}\right)^{m/2}. Gauging T between two quantiles and inverting its expression as a function of \mu you obtain confidence intervals for \mu . With the sample specification: \mathbf x=\{7.14, 6.3, 3.9, 6.46, 0.2, 2.94, 4.14, 4.69, 6.02, 1.58\} having size m = 10, you compute the statistics s_\mu = 43.37 and s_{\sigma^2}=46.07 , and obtain a 0.90 confidence interval for \mu with extremes (3.03, 5.65). | 1 = . It consists of a pair (Z, g_{\boldsymbol\theta}) , where the seed Z is a random variable without unknown parameters, while the explaining function g_{\boldsymbol\theta} is a function mapping from samples of Z to samples of the random variable X we are interested in. The parameter vector \boldsymbol\theta is a specification of the random parameter \mathbf\Theta . Its components are the parameters of the X distribution law. The Integral Transform Theorem ensures the existence of such a mechanism for each (scalar or vector) X when the seed coincides with the random variable U uniformly distributed in [0,1] . Example. : For X following a Pareto distribution with parameters a and k, i.e. F_X(x)=\left(1-\frac{k}{x}^a\right) I_{[k,\infty)}(x), a sampling mechanism (U, g_{(a,k)}) for X with seed U reads: g_{(a,k)}(u)=k (1-u)^{-\frac{1}{a}}, or, equivalently, g_{(a,k)}(u)=k u^{-1/a}. | 2 = . The actual connection between the model and the observed data is tossed in terms of a set of relations between statistics on the data and unknown parameters that come as a corollary of the sampling mechanisms. We call these relations master equations. Pivoting around the statistic s=h(x_1,\ldots,x_m)= h(g_{\boldsymbol\theta}(z_1),\ldots, g_{\boldsymbol\theta}(z_m)) , the general form of a master equation is: s = \rho(\boldsymbol\theta;z_1,\ldots,z_m). With these relations we may inspect the values of the parameters that could have generated a sample with the observed statistic from a particular setting of the seeds representing the seed of the sample. Hence, to the population of sample seeds corresponds a population of parameters. In order to ensure this population clean properties, it is enough to draw randomly the seed values and involve either sufficient statistics or, simply, well-behaved statistics w.r.t. the parameters, in the master equations. For example, the statistics s_1 = \sum_{i=1}^m \log x_i and s_2 = \min_{i=1,\ldots,m} \{x_i\} prove to be sufficient for parameters a and k of a Pareto random variable X. Thanks to the (equivalent form of the) sampling mechanism g_{(a,k)} we may read them as s_1 = m\log k + \frac{1}{a} \sum_{i=1}^m \log u_i s_2 = \min_{i=1,\ldots,m} \{k u_i^{-\frac{1}{a}}\}, respectively. | 3 = Parameter population. Having fixed a set of master equations, you may map sample seeds into parameters either numerically through a population bootstrap, or analytically through a twisting argument. Hence from a population of seeds you obtain a population of parameters. Example. From the above master equation we can draw a pair of parameters, ( a, k) , compatible with the observed sample by solving the following system of equations: a=\frac{\sum\log u_i - m \log \min \{u_i\}}{s_1-m\log s_2}. k = \exp\left(\frac{ a s_1 - \sum\log u_i}{m a}\right) where s_1 and s_2 are the observed statistics and u_1,\ldots,u_m a set of uniform seeds. Transferring to the parameters the probability (density) affecting the seeds, you obtain the distribution law of the random parameters A and K compatible with the statistics you have observed. Compatibility denotes parameters of compatible populations, i.e. of populations that could have generated a sample giving rise to the observed statistics. You may formalize this notion as follows: }} ===Definition=== For a random variable and a sample drawn from it a compatible distribution is a distribution having the same sampling mechanism \mathcal M_X=(Z,g_{\boldsymbol\theta}) of X with a value \boldsymbol\theta of the random parameter \mathbf\Theta derived from a master equation rooted on a well-behaved statistic s. Implementing the twisting argument method, you get the distribution law F_M(\mu)  of the mean M of a Gaussian variable X on the basis of the statistic s_M = \sum_{i=1}^m x_i  when \Sigma^2  is known to be equal to \sigma^2   . Its expression is: F_M(\mu) = \Phi{\left(\frac{m\mu-s_M}{\sigma\sqrt{m}}\right)}, shown in the figure on the right, where \Phi is the cumulative distribution function of a standard normal distribution. Computing a confidence interval for M given its distribution function is straightforward: we need only find two quantiles (for instance \delta/2  and 1-\delta/2  quantiles in case we are interested in a confidence interval of level δ symmetric in the tail's probabilities) as indicated on the left in the diagram showing the behavior of the two bounds for different values of the statistic s m . The Achilles heel of Fisher's approach lies in the joint distribution of more than one parameter, say mean and variance of a Gaussian distribution. On the contrary, with the last approach (and above-mentioned methods: population bootstrap and twisting argument) we may learn the joint distribution of many parameters. For instance, focusing on the distribution of two or many more parameters, in the figures below we report two confidence regions where the function to be learnt falls with a confidence of 90%. The former concerns the probability with which an extended support vector machine attributes a binary label 1 to the points of the (x,y) plane. The two surfaces are drawn on the basis of a set of sample points in turn labelled according to a specific distribution law . The latter concerns the confidence region of the hazard rate of breast cancer recurrence computed from a censored sample .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1349080432 under CC BY-SA 4.0; modifications have been made.