Fast robust estimation of prediction error based on resampling

Robust estimators of the prediction error of a linear model are proposed. The estimators are based on the resampling techniques cross-validation and bootstrap. The robustness of the prediction error estimators is obtained by robustly estimating the regression parameters of the linear model and by trimming the largest prediction errors. To avoid the recalculation of time-consuming robust regression estimates, fast approximations for the robust estimates of the resampled data are used. This leads to time-efficient and robust estimators of prediction error.     

Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression

Given n training examples, the training of a least squares support vector machine (LS-SVM) or kernel ridge regression (KRR) corresponds to solving a linear system of dimension n. In cross-validating LS-SVM or KRR, the training examples are split into two distinct subsets for a number of times (l) wherein a subset of m examples are used for validation and the other subset of (n-m) examples are used for training the classifier. In this case l linear systems of dimension (n-m) need to be solved. We propose a novel method for cross-validation (CV) of LS-SVM or KRR in which instead of solving l linear systems of dimension (n-m), we compute the inverse of an n dimensional square matrix and solve l linear systems of dimension m, thereby reducing the complexity when l is large and/or m is small. Typical multi-fold, leave-one-out cross-validation (LOO-CV) and leave-many-out cross-validations are considered. For five-fold CV used in practice with five repetitions over randomly drawn slices, the proposed algorithm is approximately four times as efficient as the naive implementation. For large data sets, we propose to evaluate the CV approximately by applying the well-known incomplete Cholesky decomposition technique and the complexity of these approximate algorithms will scale linearly on the data size if the rank of the associated kernel matrix is much smaller than n. Simulations are provided to demonstrate the performance of LS-SVM and the efficiency of the proposed algorithm with comparisons to the naive and some existent implementations of multi-fold and LOO-CV.     

Feature selection for manufacturing process monitoring using cross-validation

A novel algorithm is developed for feature selection and parameter tuning in quality monitoring of manufacturing processes using cross-validation. Due to the recent development in sensing technology, many on-line signals are collected for manufacturing process monitoring and feature extraction is then performed to extract critical features related to product/process quality. However, lack of precise process knowledge may result in many irrelevant or redundant features. Therefore, a systematic procedure is needed to select a parsimonious set of features which provide sufficient information for process monitoring. In this study, a new method for selecting features and tuning SPC limits is proposed by applying k-fold cross-validation to simultaneously select important features and set the monitoring limits using Type I and Type II errors obtained from cross-validation. The monitoring performance for production data collected from ultrasonic metal welding of batteries demonstrates that the proposed algorithm is able to select the most efficient features and control limits and thus leading to satisfactory monitoring performance.     

Fast and numerically stable methods for the computation of Zernike moments

Zernike moments (ZMs) are used in many image processing applications due to their superior performance over other moments. However, they suffer from high computation cost and numerical instability at high order of moments. In the past many recursive methods have been developed to improve their speed performance and considerable success has been achieved. The analysis of numerical stability has also gained momentum as it affects the accuracy of moments and their invariance property. There are three recursive methods which are normally used in ZMs calculation—Prata’s, Kintner’s and q-recursive methods. The earlier studies have found the q-recursive method outperforming the two other methods. In this paper, we modify Prata’s method and present a recursive relation which is proved to be faster than the q-recursive method. Numerical instability is observed at high orders of moments with the q-recursive method suffering from the underflow problem while the modified Prata’s method suffering from finite precision error. The modified Kintner’s method is the least susceptible to these errors. Keeping in view the better numerical stability, we further make the modified Kintner’s method marginally faster than the q-recursive method. We recommend the modified Prata’s method for low orders (≤90) and Kintner’s fast method for high orders (>90) of ZMs.     

Measuring the prediction error. A comparison of cross-validation, bootstrap and covariance penalty methods

The estimators most widely used to evaluate the prediction error of a non-linear regression model are examined. An extensive simulation approach allowed the comparison of the performance of these estimators for different non-parametric methods, and with varying signal-to-noise ratio and sample size. Estimators based on resampling methods such as Leave-one-out, parametric and non-parametric Bootstrap, as well as repeated Cross Validation methods and Hold-out, were considered. The methods used are Regression Trees, Projection Pursuit Regression and Neural Networks. The repeated-corrected 10-fold Cross-Validation estimator and the Parametric Bootstrap estimator obtained the best performance in the simulations.     

An experimental comparison of cross-validation techniques for estimating the area under the ROC curve

Reliable estimation of the classification performance of inferred predictive models is difficult when working with small data sets. Cross-validation is in this case a typical strategy for estimating the performance. However, many standard approaches to cross-validation suffer from extensive bias or variance when the area under the ROC curve (AUC) is used as the performance measure. This issue is explored through an extensive simulation study. Leave-pair-out cross-validation is proposed for conditional AUC-estimation, as it is almost unbiased, and its deviation variance is as low as that of the best alternative approaches. When using regularized least-squares based learners, efficient algorithms exist for calculating the leave-pair-out cross-validation estimate.     

Fast projection methods for minimal design problems in linear system theory

The so-called minimal design problem (or MDP) of linear system theory is to find a proper minimal degree rational matrix solution of the equation H(z)D(z)=N(z), where {N(z),D(z)} are given p×r and m×r polynomial matrices with D(z) of full rank r≦m.We describe some solution algorithms that appear to be more efficient (in terms of number of computations and of potential numerical stability) than those presently known. The algorithms are based on the structure of a polynomial echelon form of the left minimal basis of the so-called generalized Sylvester resultant matrix of {N(z), D(z)}. Orthogonal projection algorithms that exploit the Toeplitz structure of this resultant matrix are used to reduce the number of computations needed for the solution.     

Fast adaptive algorithms for minor component analysis using Householder transformation

In this paper, we propose new adaptive algorithms for the extraction and tracking of the least (minor) or eventually, principal eigenvectors of a positive Hermitian covariance matrix. The main advantage of our proposed algorithms is their low computational complexity and numerical stability even in the minor component analysis case. The proposed algorithms are considered fast in the sense that their computational cost is O(np) flops per iteration where n is the size of the observation vector and p<n is the number of eigenvectors to estimate.We consider OJA-type minor component algorithms based on the constraint and non-constraint stochastic gradient technique. Using appropriate fast orthogonalization procedures, we introduce new fast algorithms that extract the minor (or principal) eigenvectors and guarantee good numerical stability as well as the orthogonality of their weight matrix at each iteration. In order to have a faster convergence rate, we propose a normalized version of these algorithms by seeking the optimal step-size. Our algorithms behave similarly or even better than other existing algorithms of higher complexity as illustrated by our simulation results.     

Seismic assessment of school buildings in Taiwan using the evolutionary support vector machine inference system

Elementary and junior high school buildings in Taiwan are designed to serve not only as places of education but also as temporary shelters in the aftermath of major earthquakes. Effective evaluation of the seismic resistance of school buildings is a critical issue that deserves further investigation. The National Center for Research on Earthquake Engineering (in Taiwan) currently employs performance-target ground acceleration (A_P) as the index to evaluate school structure compliance with seismic resistance requirements. However, computational processes are complicated, time consuming, and require the input of many experts. To address this problem, this paper developed an evolutionary support vector machine inference system (ESIS) that integrated two AI techniques, namely, the support vector machine (SVM) and fast messy genetic algorithm (fmGA). Based on training results, the developed system can predict the A_P of a school building in a significantly shorter time base, thus increasing evaluation efficiency significantly. The validity of ESIS was tested using the 10-Fold Cross-Validation method. Another aim of this paper is to retain and apply expert knowledge and relevant experience to the solution of similar problems in the future.     

Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis

In this paper we study aprobabilistic approach which is an alternative to the classical worst-case algorithms for robustness analysis and design of uncertain control systems. That is, we aim to estimate the probability that a control system with uncertain parametersq restricted to a boxQ attains a given level of performance γ. Since this probability depends on the underlying distribution, we address the following question: What is a “reasonable” distribution so that the estimated probability makes sense? To answer this question, we define two worstcase criteria and prove that the uniform distribution is optimal in both cases. In the second part of the paper we turn our attention to a subsequent problem. That is, we estimate the sizes of both the so-called “good” and “bad” sets via sampling. Roughly speaking, the good set contains the parametersq∈Q with a performance level better than or equal to γ while the bad set is the set of parametersq∈Q with a performance level worse than γ. We give bounds on the minimum sample size to attain a good estimate of these sets in a certain probabilistic sense.     

Stochastic algorithms for robustness of control performances

In recent years, there has been a growing interest in developing statistical learning methods to provide approximate solutions to “difficult” control problems. In particular, randomized algorithms have become a very popular tool used for stability and performance analysis as well as for design of control systems. However, as randomized algorithms provide an efficient solution procedure to the “intractable” problems, stochastic methods bring closer to understanding the properties of the real systems. The topic of this paper is the use of stochastic methods in order to solve the problem of control robustness: the case of parametric stochastic uncertainty is considered. Necessary concepts regarding stochastic control theory and stochastic differential equations are introduced. Then a convergence analysis is provided by means of the Chernoff bounds, which guarantees robustness in mean and in probability. As an illustration, the robustness of control performances of example control systems is computed.     

A probabilistic framework for problems with real structured uncertainty in systems and control

The objective of this paper is twofold. First, the problem of generation of real random matrix samples with uniform distribution in structured (spectral) norm bounded sets is studied. This includes an analysis of the distribution of the singular values of uniformly distributed real matrices, and an efficient (i.e. polynomial-time) algorithm for their generation. Second, it is shown how the developed techniques may be used to solve in a probabilistic setting several hard problems involving systems subject to real structured uncertainty.     

Fast kernel conditional density estimation: A dual-tree Monte Carlo approach

We describe a fast, data-driven bandwidth selection procedure for kernel conditional density estimation (KCDE). Specifically, we give a Monte Carlo dual-tree algorithm for efficient, error-controlled approximation of a cross-validated likelihood objective. While exact evaluation of this objective has an unscalable O(n²) computational cost, our method is practical and shows speedup factors as high as 286,000 when applied to real multivariate datasets containing up to one million points. In absolute terms, computation times are reduced from months to minutes. This enables applications at much greater scale than previously possible. The core idea in our method is to first derive a standard deterministic dual-tree approximation, whose loose deterministic bounds we then replace with tight, probabilistic Monte Carlo bounds. The resulting Monte Carlo dual-tree algorithm exhibits strong error control and high speedup across a broad range of datasets several orders of magnitude greater in size than those reported in previous work. The cost of this high acceleration is the loss of the formal error guarantee of the deterministic dual-tree framework; however, our experiments show that error is still amply controlled by our Monte Carlo algorithm, and the many-order-of-magnitude speedups are worth this sacrifice in the large-data case, where cross-validated bandwidth selection for KCDE would otherwise be impractical.     

关于快速多极算法FMM的几点注解

详细分析快速多极算法FMM,对引力场的势函数进行了详细的多极展开和泰勒局部展开的推导过程,并在此基础上分析和推导了引力势的两种展开式的截断误差,讨论了FMM的误差收敛情况,说明了FMM的误差可由截断次数p进行控制.     

A Fast Direct Solver for a Class of Elliptic Partial Differential Equations

We describe a fast and robust method for solving the large sparse linear systems that arise upon the discretization of elliptic partial differential equations such as Laplace’s equation and the Helmholtz equation at low frequencies. While most existing fast schemes for this task rely on so called “iterative” solvers, the method described here solves the linear system directly (to within an arbitrary predefined accuracy). The method is described for the particular case of an operator defined on a square uniform grid, but can be generalized other geometries. For a grid containing N points, a single solve requires O(Nlog ² N) arithmetic operations and storage. Storing the information required to perform additional solves rapidly requires O(Nlog N) storage. The scheme is particularly efficient in situations involving domains that are loaded on the boundary only and where the solution is sought only on the boundary. In this environment, subsequent solves (after the first) can be performed in operations. The efficiency of the scheme is illustrated with numerical examples. For instance, a system of size 10⁶×10⁶ is directly solved to seven digits accuracy in four minutes on a 2.8 GHz P4 desktop PC.     

基于图像处理的快速位置检测算法研究

论文在分析典型图像获取的硬件环境和常用图像检测算法的基础上,提出了一种基于图像处理的快速物体位置检测算法,阐述了算法的原理。该算法可以不通过传统的数字滤波、二值化、边缘提取处理,快速得到被检测物体的平面位置。     

A Fast Parallel Clustering Algorithm for Large Spatial Databases

The clustering algorithm DBSCAN relies on a density-based notion of clusters and is designed to discover clusters of arbitrary shape as well as to distinguish noise. In this paper, we present PDBSCAN, a parallel version of this algorithm. We use the ‘shared-nothing’ architecture with multiple computers interconnected through a network. A fundamental component of a shared-nothing system is its distributed data structure. We introduce the dR*-tree, a distributed spatial index structure in which the data is spread among multiple computers and the indexes of the data are replicated on every computer. We implemented our method using a number of workstations connected via Ethernet (10 Mbit). A performance evaluation shows that PDBSCAN offers nearly linear speedup and has excellent scaleup and sizeup behavior.     

入侵检测中一种新的快速字符串匹配算法

基于字符串匹配的检测方法是入侵检测系统中一类很重要的分析方法。文章首先分析了现有的几种准确字符串匹配算法,然后提出了一种新的多模式字符串匹配算法,并且分析了这些算法的复杂性。最后,文章用具体的实验数据来验证这些算法的性能。通过实验可以看出,新算法使得检测速度大大提高,签名容量大大增加。