On the sampling distribution of resubstitution and leave-one-out error estimators for linear classifiers

Error estimation is a problem of high current interest in many areas of application. This paper concerns the classical problem of determining the performance of error estimators in small-sample settings under a Gaussianity parametric assumption. We provide here for the first time the exact sampling distribution of the resubstitution and leave-one-out error estimators for linear discriminant analysis (LDA) in the univariate case, which is valid for any sample size and combination of parameters (including unequal variances and sample sizes for each class). In the multivariate case, we provide a quasi-binomial approximation to the distribution of both the resubstitution and leave-one-out error estimators for LDA, under a common but otherwise arbitrary class covariance matrix, which is assumed to be known in the design of the LDA discriminant. We provide numerical examples, using both synthetic and real data, that indicate that these approximations are accurate, provided that LDA classification error is not too large.     

Exact performance of error estimators for discrete classifiers

Discrete classification problems abound in pattern recognition and data mining applications. One of the most common discrete rules is the discrete histogram rule. This paper presents exact formulas for the computation of bias, variance, and RMS of the resubstitution and leave-one-out error estimators, for the discrete histogram rule. We also describe an algorithm to compute the exact probability distribution of resubstitution and leave-one-out, as well as their deviations from the true error rate. Using a parametric Zipf model, we compute the exact performance of resubstitution and leave-one-out, for varying expected true error, number of samples, and classifier complexity (number of bins). We compare this to approximate performance measures-computed by Monte-Carlo sampling—of 10-repeated 4-fold cross-validation and the 0.632 bootstrap error estimator. Our results show that resubstitution is low-biased but much less variable than leave-one-out, and is effectively the superior error estimator between the two, provided classifier complexity is low. In addition, our results indicate that the overall performance of resubstitution, as measured by the RMS, can be substantially better than the 10-repeated 4-fold cross-validation estimator, and even comparable to the 0.632 bootstrap estimator, provided that classifier complexity is low and the expected error rates are moderate. In addition to the results discussed in the paper, we provide an extensive set of plots that can be accessed on a companion website, at the URL http://ee.tamu.edu/∼edward/exact_discrete.     

Optimal mean-square-error calibration of classifier error estimators under Bayesian models

A recently proposed Bayesian modeling framework for classification facilitates both the analysis and optimization of error estimation performance. The Bayesian error estimator is then defined to have optimal mean-square error performance, but in many situations closed-form representations are unavailable and approximations may not be feasible. To address this, we present a method to optimally calibrate arbitrary error estimators for minimum mean-square error performance within a supposed Bayesian framework. Assuming a fixed sample size, classification rule and error estimation rule, as well as a fixed Bayesian model, the calibration is done by first computing a calibration function that maps error estimates to their optimally calibrated values off-line. Once found, this calibration function may be easily applied to error estimates on the fly whenever the assumptions apply. We demonstrate that calibrated error estimators offer significant improvement in performance relative to classical error estimators under Bayesian models with both linear and non-linear classification rules.     

A Kernel-Based Two-Class Classifier for Imbalanced Data Sets

Many kernel classifier construction algorithms adopt classification accuracy as performance metrics in model evaluation. Moreover, equal weighting is often applied to each data sample in parameter estimation. These modeling practices often become problematic if the data sets are imbalanced. We present a kernel classifier construction algorithm using orthogonal forward selection (OFS) in order to optimize the model generalization for imbalanced two-class data sets. This kernel classifier identification algorithm is based on a new regularized orthogonal weighted least squares (ROWLS) estimator and the model selection criterion of maximal leave-one-out area under curve (LOO-AUC) of the receiver operating characteristics (ROCs). It is shown that, owing to the orthogonalization procedure, the LOO-AUC can be calculated via an analytic formula based on the new regularized orthogonal weighted least squares parameter estimator, without actually splitting the estimation data set. The proposed algorithm can achieve minimal computational expense via a set of forward recursive updating formula in searching model terms with maximal incremental LOO-AUC value. Numerical examples are used to demonstrate the efficacy of the algorithm     

Local error estimator for stresses in 3D structural analysis

This paper focuses on an a posteriori error estimator for FE approximations of 3D linear elasticity problems. The objective is to present the application of the new generation of error in constitutive relation to the calculation of the local error in classical tetrahedral elements. We show on examples whose solution is known analytically that the local error estimation gives satisfactory effectivity indexes.     

A posteriori error estimates of two-grid finite volume element methods for nonlinear elliptic problems

In this paper, we study the a posteriori error estimates of two-grid finite volume element method for second-order nonlinear elliptic equations. We derive the residual-based a posteriori error estimator and prove the computable upper and lower bounds on the error in $H^1$-norm. The a posteriori error estimator can be used to assess the accuracy of the two-grid finite volume element solutions in practical applications. Numerical examples are provided to illustrate the performance of the proposed estimator.     

Bounded error parameter estimation: a sequential analytic centerapproach

A sequential analytic center approach for bounded error parameter estimation is proposed. The authors show that the analytic center minimizes the logarithmic average output error among all the estimates within the membership set and is a maximum likelihood estimator for a class of noise density functions which include parabolic densities and approximations of truncated Gaussian. They also show that the analytic center is easily computable for both offline and online problems with a sequential algorithm. The convergence proof of this sequential algorithm is obtained and, moreover, it is shown that the complexity in terms of the maximum number of Newton iterations is linear in the number of observed data points     

Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap

We consider the accuracy estimation of a classifier constructed on a given training sample. The naive resubstitution estimate is known to have a downward bias problem. The traditional approach to tackling this bias problem is cross-validation. The bootstrap is another way to bring down the high variability of cross-validation. But a direct comparison of the two estimators, cross-validation and bootstrap, is not fair because the latter estimator requires much heavier computation. We performed an empirical study to compare the .632+ bootstrap estimator with the repeated 10-fold cross-validation and the repeated one-third holdout estimator. All the estimators were set to require about the same amount of computation. In the simulation study, the repeated 10-fold cross-validation estimator was found to have better performance than the .632+ bootstrap estimator when the classifier is highly adaptive to the training sample. We have also found that the .632+ bootstrap estimator suffers from a bias problem for large samples as well as for small samples.     

Determination of the optimal number of features for quadratic discriminant analysis via the normal approximation to the discriminant distribution

Given the joint feature-label distribution, increasing the number of features always results in decreased classification error; however, this is not the case when a classifier is designed via a classification rule from sample data. Typically, for fixed sample size, the error of a designed classifier decreases and then increases as the number of features grows. The problem is especially acute when sample sizes are very small and the potential number of features is very large. To obtain a general understanding of the kinds of feature-set sizes that provide good performance for a particular classification rule, performance must be evaluated based on accurate error estimation, and hence a model-based setting for optimizing the number of features is needed. This paper treats quadratic discriminant analysis (QDA) in the case of unequal covariance matrices. For two normal class-conditional distributions, the QDA classifier is determined according to a discriminant. The standard plug-in rule estimates the discriminant from a feature-label sample to obtain an estimate of the discriminant by replacing the means and covariance matrices by their respective sample means and sample covariance matrices. The unbiasedness of these estimators assures good estimation for large samples, but not for small samples.Our goal is to find an essentially analytic method to produce an error curve as a function of the number of features so that the curve can be minimized to determine an optimal number of features. We use a normal approximation to the distribution of the estimated discriminant. Since the mean and variance of the estimated discriminant will be exact, these provide insight into how the covariance matrices affect the optimal number of features. We derive the mean and variance of the estimated discriminant and compare feature-size optimization using the normal approximation to the estimated discriminant with optimization obtained by simulating the true distribution of the estimated discriminant. Optimization via the normal approximation to the estimated discriminant provides huge computational savings in comparison to optimization via simulation of the true distribution. Feature-size optimization via the normal approximation is very accurate when the covariance matrices differ modestly. The optimal number of features based on the normal approximation will exceed the actual optimal number when there is large disagreement between the covariance matrices; however, this difference is not important because the true misclassification error using the number of features obtained from the normal approximation and the number obtained from the true distribution differ only slightly, even for significantly different covariance matrices.     

Statistical properties of error estimators in performance assessment of recognition systems

The problem of estimating the error probability of a given classification system is considered. Statistical properties of the empirical error count (C) and the average conditional error (R) estimators are studied. It is shown that in the large sample case the R estimator is unbiased and its variance is less than that of the C estimator. In contrast to conventional methods of Bayes error estimation the unbiasedness of the R estimator for a given classifier can be obtained only at the price of an additional set of classified samples. On small test sets the R estimator may be subject to a pessimistic bias caused by the averaging phenomenon characterizing the functioning of conditional error estimators.     

一种新颖混合贝叶斯分类模型研究

朴素贝叶斯分类器（Naive Bayesian classifier,NB）是一种简单而有效的分类模型,但这种分类器缺乏对训练集信息的充分利用,影响了它的分类性能。通过分析NB的分类原理,并结合线性判别分析（Linear Discriminant Analysis,LDA）与核判别分析（Kernel Discriminant Analysis,KDA）的优点,提出了一种混合贝叶斯分类模型DANB（Discriminant Analysis Naive Bayesian classifier,DANB）。将该分类方法与NB和TAN（Tree Augmented Naive Bayesian classifier,TAN）进行实验比较,结果表明,在大多数数据集上,DANB分类器具有较高的分类正确率。     

Optimum control of an unknown linear plant using Bayesian estimation of the error

In this paper, the theory of the optimum control of an unknown linear plant is discussed. Rather than try to estimate the coeffcients of the plant, the future error as defined by a quadratic measure is estimated using a Bayesian estimator. In this manner, better system performance can be expected since the effect of estimation errors on the estimator is obtained. The optimum control signal is then obtained which minimizes the estimated future error. It is shown that it is a linear function of the present output of the system. In the final section, a necessary and sufficient condition is obtained for the convergence of this procedure to the optimum system obtained with known coefficients.     

On the performance of bias-reduction techniques for variance estimation in approximate Bayesian bootstrap imputation

Multiply imputed data sets can be created with the approximate Bayesian bootstrap (ABB) approach under the assumption of ignorable nonresponse. The theoretical development and inferential validity are predicated upon asymptotic properties; and biases are known to occur in small-to-moderate samples. There have been attempts to reduce the finite-sample bias for the multiple imputation variance estimator. In this note, we present an empirical study for evaluating the comparative performance of the two proposed bias-correction techniques and their impact on precision. The results suggest that to varying degrees, bias improvements are outweighed by efficiency losses for the variance estimator. We argue that the original ABB has better small-sample properties than the modified versions in terms of the integrated behavior of accuracy and precision, as measured by the root mean-square error.     

A flux-free a posteriori error estimator for the incompressible Stokes problem using a mixed FE formulation

In this contribution, we present an a posteriori error estimator for the incompressible Stokes problem valid for a conventional mixed FE formulation. Due to the saddle-point property of the problem, conventional error estimators developed for pure minimization problems cannot be utilized straight-forwardly. The new estimator is built up by two key ingredients. At first, a computed error approximation, exactly fulfilling the continuity equation for the error, is obtained via local Dirichlet problems. Secondly, we adopt the approach of solving local equilibrated flux-free problems in order to bound the remaining, incompressible, error. In this manner, guaranteed upper and lower bounds, of the velocity “energy norm” of the error as well as goal-oriented (linear) output functionals, with respect to a reference (overkill) mesh are obtained. In particular, it should be noted that this approach requires no computation of hybrid fluxes. Furthermore, the estimator is applicable to mixed FE formulations using continuous pressure approximations, such as the Mini and Taylor–Hood class of elements. In conclusion, a few simple numerical examples are presented, illustrating the accuracy of the error bounds.     

Evaluation of numerical error estimation based on grid refinement studies with the method of the manufactured solutions

This article presents a study on the estimation of the numerical uncertainty based on grid refinement studies with the method of manufactured solutions. The availability of an exact solution and the convergence of the numerical solution to machine accuracy allow the determination of the exact error and of the distinct contributions of the iterative and discretization errors. The study focuses on three different problems of error/uncertainty evaluation (the uncertainty is in this case the error multiplied by a safety factor): the estimation of the iterative error/uncertainty; the influence of the iterative error on the estimation of the discretization error/uncertainty, and the overall numerical error/uncertainty as a combination of the iterative and discretization errors. The results obtained in this study show that it is possible to obtain a reliable iterative error estimator based on a geometric-progression extrapolation of the L_∞ norm of the differences between iterations. In order to obtain a negligible influence of the iterative error on the estimation of the discretization error, the iterative error must be two to three orders of magnitude smaller than the discretization error. If the iterative error is non-negligible it should be added, simply arithmetically, to the discretization error to obtain a reliable estimate of the numerical error; combining by RMS is not conservative.     

Estimation of the mean squared error of predictors of small area linear parameters under a logistic mixed model

An accuracy measure (mean squared error, MSE) is necessary when small area estimators of linear parameters are provided. Even in the case when such estimators arise from the assumption of relatively simple models for the variable of interest, as linear mixed models, the analytic form of the MSE is not suitable to be calculated explicitly. Some good and widely used approximations are available for those models. For generalized linear mixed models, a rough approximation can be obtained by a linearization of the model and application of Prasad-Rao approximation for linear mixed models. Resampling methods, although computationally demanding, represent a conceptually simple alternative. Under a logistic mixed linear model for the characteristic of interest, the Prasad-Rao-type formula is compared with a bootstrap estimator obtained by a wild bootstrap designed for estimating under finite populations. A simulation study is developed in order to study the performance of both methods for estimating a small area proportion.     

A new algorithm for fitting tracks with energy losses due to Bremsstrahlung

This paper introduces a Fast Bayesian Track Fit (FBTF) — a new algorithm for fitting tracks with Bremsstrahlung-induced energy losses. The FBTF algorithm combines a standard Kalman filter and a Bayesian estimator for fractional energy losses. The estimator uses computationally efficient approximations of the Bethe–Heitler distribution and measurement likelihood which allows analytical calculation of Bayesian integrals. The algorithm performance has been evaluated with simulated data using a simplified tracking scenario. The results regarding track parameter estimation quality and computing time are presented and compared with those obtained with a Gaussian-sum filter.     

Online estimation of discrete,continuous, and conditional joint densities using classifier chains

We address the problem of estimating discrete, continuous, and conditional joint densities online, i.e., the algorithm is only provided the current example and its current estimate for its update. The family of proposed online density estimators, estimation of densities online (EDO), uses classifier chains to model dependencies among features, where each classifier in the chain estimates the probability of one particular feature. Because a single chain may not provide a reliable estimate, we also consider ensembles of classifier chains and ensembles of weighted classifier chains. For all density estimators, we provide consistency proofs and propose algorithms to perform certain inference tasks. The empirical evaluation of the estimators is conducted in several experiments and on datasets of up to several millions of instances. In the discrete case, we compare our estimators to density estimates computed by Bayesian structure learners. In the continuous case, we compare them to a state-of-the-art online density estimator. Our experiments demonstrate that, even though designed to work online, EDO delivers estimators of competitive accuracy compared to other density estimators (batch Bayesian structure learners on discrete datasets and the state-of-the-art online density estimator on continuous datasets). Besides achieving similar performance in these cases, EDO is also able to estimate densities with mixed types of variables, i.e., discrete and continuous random variables.     

Compression and aggregation of Bayesian estimates for data intensive computing

Bayesian estimation is a major and robust estimator for many advanced statistical models. Being able to incorporate prior knowledge in statistical inference, Bayesian methods have been successfully applied in many different fields such as business, computer science, economics, epidemiology, genetics, imaging, and political science. However, due to its high computational complexity, Bayesian estimation has been deemed difficult, if not impractical, for large-scale databases, stream data, data warehouses, and data in the cloud. In this paper, we propose a novel compression and aggregation schemes (C&A) that enables distributed, parallel, or incremental computation of Bayesian estimates. Assuming partitioning of a large dataset, the C&A scheme compresses each partition into a synopsis and aggregates the synopsis into an overall Bayesian estimate without accessing the raw data. Such a C&A scheme can find applications in OLAP for data cubes, stream data mining, and cloud computing. It saves tremendous computing time since it processes each partition only once, enabling fast incremental update, and allows parallel processing. We prove that the compression is asymptotically lossless in the sense that the aggregated estimator deviates from the true model by an error that is bounded and approaches to zero when the data size increases. The results show that the proposed C&A scheme can make feasible OLAP of Bayesian estimates in a data cube. Further, it supports real-time Bayesian analysis of stream data, which can only be scanned once and cannot be permanently retained. Experimental results validate our theoretical analysis and demonstrate that our method can dramatically save time and space costs with almost no degradation of the modeling accuracy.