Non-asymptotic confidence ellipsoids for the least-squares estimate

In this paper, we consider the finite sample properties of least-squares system identification, and derive non-asymptotic confidence ellipsoids for the estimate. The shape of the confidence ellipsoids is similar to the shape of the ellipsoids derived using asymptotic theory, but unlike asymptotic theory, they are valid for a finite number of data points. The probability that the estimate belongs to a certain ellipsoid has a natural dependence on the volume of the ellipsoid, the data generating mechanism, the model order and the number of data points available.     

Asymptotic statistical theory of overtraining and cross-validation

A statistical theory for overtraining is proposed. The analysis treats general realizable stochastic neural networks, trained with Kullback-Leibler divergence in the asymptotic case of a large number of training examples. It is shown that the asymptotic gain in the generalization error is small if we perform early stopping, even if we have access to the optimal stopping time. Based on the cross-validation stopping we consider the ratio the examples should be divided into training and cross-validation sets in order to obtain the optimum performance. Although cross-validated early stopping is useless in the asymptotic region, it surely decreases the generalization error in the nonasymptotic region. Our large scale simulations done on a CM5 are in good agreement with our analytical findings.     

A theoretical comparison of batch-mode, on-line, cyclic, andalmost-cyclic learning

We study and compare different neural network learning strategies: batch-mode learning, online learning, cyclic learning, and almost-cyclic learning. Incremental learning strategies require less storage capacity than batch-mode learning. However, due to the arbitrariness in the presentation order of the training patterns, incremental learning is a stochastic process; whereas batch-mode learning is deterministic. In zeroth order, i.e., as the learning parameter eta tends to zero, all learning strategies approximate the same ordinary differential equation for convenience referred to as the "ideal behavior". Using stochastic methods valid for small learning parameters eta, we derive differential equations describing the evolution of the lowest-order deviations from this ideal behavior. We compute how the asymptotic misadjustment, measuring the average asymptotic distance from a stable fixed point of the ideal behavior, scales as a function of the learning parameter and the number of training patterns. Knowing the asymptotic misadjustment, we calculate the typical number of learning steps necessary to generate a weight within order epsilon of this fixed point, both with fixed and time-dependent learning parameters. We conclude that almost-cyclic learning (learning with random cycles) is a better alternative for batch-mode learning than cyclic learning (learning with a fixed cycle).     

Direct pole placement adaptive tracking of non-minimum phase systems

In this paper, we propose a direct pole placement adaptive tracking scheme for non-minimum-phase, open-loop stable, linear plants with time delays. This controller utilizes the internal model principle to eliminate steady-state tracking error for signals with known distinct frequencies. The controller order depends only on the number of frequencies in the reference input, but not on the order of the plant. It is shown that with sufficiently small loop gain, the controller can guarantee stable closed loop, and asymptotic tracking.     

Defining Asymptotic Parallel Time Complexity of Data-dependent Algorithms

The scientific research community has reached a stage of maturity where its strong need for high-performance computing has diffused into also everyday life of engineering and industry algorithms. In efforts to satisfy this need, parallel computers provide an efficient and economical way to solve large-scale and/or time-constrained problems. As a consequence, the end-users of these systems have a vested interest in defining the asymptotic time complexity of parallel algorithms to predict their performance on a particular parallel computer. The asymptotic parallel time complexity of data-dependent algorithms depends on the number of processors, data size, and other parameters. Discovering the main other parameters is a challenging problem and the clue in obtaining a good estimate of performance order. Great examples of these types of applications are sorting algorithms, searching algorithms and solvers of the traveling salesman problem (TSP). This article encompasses all the knowledge discovery aspects to the problem of defining the asymptotic parallel time complexity of data-dependent algorithms. The knowledge discovery methodology begins by designing a considerable number of experiments and measuring their execution times. Then, an interactive and iterative process explores data in search of patterns and/or relationships detecting some parameters that affect performance. Knowing the key parameters which characterise time complexity, it becomes possible to hypothesise to restart the process and to produce a subsequent improved time complexity model. Finally, the methodology predicts the performance order for new data sets on a particular parallel computer by replacing a numerical identification. As a case of study, a global pruning traveling salesman problem implementation (GP-TSP) has been chosen to analyze the influence of indeterminism in performance prediction of data-dependent parallel algorithms, and also to show the usefulness of the defined knowledge discovery methodology. The subsequent hypotheses generated to define the asymptotic parallel time complexity of the TSP were corroborated one by one. The experimental results confirm the expected capability of the proposed methodology; the predictions of performance time order were rather good comparing with real execution time (in the order of 85%).     

Quantification of the variance of estimated transfer functions in the presence of undermodeling

We study the effect of undermodeling on the parameter variance for prediction error time-domain identification in open loop. We consider linear time-invariant discrete time single-input-single-output systems with known noise model. We examine asymptotic expressions for the variance for large number of data. This quantity depends in general on the fourth order statistical properties of the applied input. However, we establish a sufficient condition under which the asymptotic variance depends on the input power spectrum only. For this case, we deliver exact expressions. For a stochastic input the undermodeling contributes to the parameter variance due to the correlation between the prediction errors and its gradients, while for a deterministic input it has no influence. As an additional contribution, we investigate the parameter variance under the assumptions of the stochastic embedding procedure.     

Asymptotic analysis of an optimized quicksort algorithm

Jon Bentley and Douglas McIlroy have implemented a fast quicksort for the C standard library in 1993. We consider here the average-case complexity in terms of number of comparisons of this algorithm, and give its asymptotic expansion up to the constant order.     

Local likelihood regression in generalized linear single-index models with applications to microarray data

Searching for an effective dimension reduction space is an important problem in regression, especially for high-dimensional data such as microarray data. A major characteristic of microarray data consists in the small number of observations n and a very large number of genes p. This “large p, small n” paradigm makes the discriminant analysis for classification difficult. In order to offset this dimensionality problem a solution consists in reducing the dimension. Supervised classification is understood as a regression problem with a small number of observations and a large number of covariates. A new approach for dimension reduction is proposed. This is based on a semi-parametric approach which uses local likelihood estimates for single-index generalized linear models. The asymptotic properties of this procedure are considered and its asymptotic performances are illustrated by simulations. Applications of this method when applied to binary and multiclass classification of the three real data sets Colon, Leukemia and SRBCT are presented.     

An analysis of two related loop-free algorithms for generating integer partitions

Summary Two loop-free algorithms, LEX and NEXPAR2, for generating the partitions of a positive integer n, in lexicographic and antilexicographic order, respectively, are investigated, and their structures are shown to be closely related. By utilising a number of combinatorial identities which relate the cardinalities of various classes of partitions, we derive formulae from which operation counts for the two algorithms may be obtained. For large n, corresponding asymptotic formulae are also obtained. A number of modifications and refinements of the two algorithms are discussed, and the relative performance of the algorithms resulting, and also the original algorithms, is analysed for both the non-asymptotic and the asymptotic cases.     

Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem

One of the possible realizations of the branch-and-bound method on multiprocessor systems with distributed memory, the front-end algorithm is addressed. The complexity of the front-end algorithm is studied for a family of Boolean knapsack problems with one constraint under the assumption that the number of processors is not limited. Formulas for the order of complexity growth with an increase in dimension of the problems from the addressed family are obtained for the front-end algorithm. The asymptotic acceleration behavior and efficiency of resource use with an increase in the number of variables are studied.     

融合渐近性的灰狼优化支持向量机模型

大数据的发展对数据分类领域的分类准确性有了更高的要求;支持向量机(Support Vector Machine,SVM)的广泛应用需要一种高效的方法来构造一个分类能力强的SVM分类器;SVM的核函数参数与惩罚因子以及特征子集对预测模型的复杂度和预测精度有着重要影响。为提高SVM的分类性能,文中将SVM的渐近性融合到灰狼优化(Grey Wolf Optimization,GWO)算法中,提出了新的SVM分类器模型,该模型对SVM的参数与数据的特征子集同时进行优化,融合SVM渐近性的新灰狼个体将灰狼优化算法的搜索空间导向超参数空间中的最佳区域,能够更快地获得最优解;此外,将获得的分类准确率、所选特征个数和支持向量个数相结合,提出了一种新的适应度函数,新的适应度函数与融合渐近性的灰狼优化算法将搜索引向最优解。采用UCI中的多个经典数据集对所提模型进行验证,将其与网格搜素算法、未融合渐近性的灰狼优化算法以及其他文献中的方法进行对比,其分类准确率在不同数据集上均有不同程度的提升。实验结果表明,所提算法能找到SVM的最优参数与最小特征子集,具有更高的分类准确率和更短的平均处理时间。     

Method of asymptotic semiinvariants for studying a mathematical model of a random access network

To study a mathematical model of a random access network with a finite number of sources, retrials, and a conflict warning stage, we propose a method of asymptotic semiinvariants under a growing number of sources, which allows us to find the asymptotic probability distribution of the number of requests in a retrial pool. We present results of numerical implementation of a prelimit distribution of the number of requests in the retrial pool. We compare the prelimit and asymptotic semiinvariants.     

On the design of a position feedback control law for a simple mechanical system subject to impacts

The control of mechanical systems subject to smooth impacts is considered in this paper. As the dynamic model of the mechanical system varies in dependence on the condition of contact or non-contact, a family of dynamic compensators from position measurements is first derived, thus guaranteeing the asymptotic stability in the two different conditions. As the system can switch between the two conditions an arbitrary number of times, the stability of the overall system is not guaranteed by the stability in the two separate phases; hence, a Lyapunov approach is proposed in order to guarantee the asymptotic stability of the overall system independently of the number of transitions between the two phases. Second, it is shown how to select among the considered family of compensators the one that reduces as much as possible the effects of the impacts on the trajectory of the system, while considering a regulation problem, with zero steady-state regulation error. Both simulation and experimental results have been carried out showing the effectiveness of the proposed technique.     

Finite-Sample Convergence Properties of the LVQ1 Algorithm and the Batch LVQ1 Algorithm

This letter addresses the asymptotic convergence of Kohonen's LVQ1 algorithm when the number of training samples are finite with an analysis that uses the dynamical systems and optimisation theories. It establishes the sufficient conditions to ensure the convergence of LVQ1 near a minimum of its cost function for constant step sizes and cyclic sampling. It also proposes a batch version of LVQ1 based on the very fast Newton optimisation method that cancels the dependence of the on-line version on the order of supplied training samples.     

Novel development of Lyapunov stability of motion

The paper presents a refined analysis of the influence of initial data on dynamic behaviour and stability properties of non-stationary systems. As a result, new stability properties are discovered and defined as well as the corresponding stability domains. Furthermore, general necessary conditions are established for asymptotic stability of the unperturbed motion of these systems, the instantaneous asymptotic stability domain of which can be either time-invariant or time-varying and then possibly asymptotically contractive. It is shown that the classical Lyapunov stability conditions cannot be applied to the stability test as soon as the system instantaneous domain of asymptotic stability is asymptotically contractive. In order to investigate asymptotic stability of the motion in such cases novel criteria are established. Under the criteria the Eulerian derivative of a system Lyapunov function may be non-positive only and still guarantee asymptotic stability of the unperturbed motion

The results are illustrated by examples.     

Asymptotic synchronization of the Colpitts oscillator

In this paper we deal with the observer-based asymptotic synchronization problem for a class of chaotic oscillators. Some results based on a differential algebraic approach are used in order to determine the algebraic observability of unknown variables. The strategy consists of proposing a slave system (observer) which tends to follow asymptotically the master system. The methodology is tested in the real-time asymptotic synchronization of the Colpitts oscillator by means of a proportional reduced order observer (PROO) of free-model type.     

Constrained Swarm Stabilization of Fractional Order Linear Time Invariant Swarm Systems

This paper deals with asymptotic swarm stabilization of fractional order linear time invariant swarm systems in the presence of two constraints: the input saturation constraint and the restriction on distance of the agents from final destination which should be less than a desired value. A feedback control law is proposed for asymptotic swarm stabilization of fractional order swarm systems which guarantees satisfying the above-mentioned constraints. Numerical simulation results are given to confirm the efficiency of the proposed control method.      

Variance-error quantification for identified poles and zeros

This paper deals with quantification of noise induced errors in identified discrete-time models of causal linear time-invariant systems, where the model error is described by the asymptotic (in data length) variance of the estimated poles and zeros. The main conclusion is that there is a fundamental difference in the accuracy of the estimates depending on whether the zeros and poles lie inside or outside the unit circle. As the model order goes to infinity, the asymptotic variance approaches a finite limit for estimates of zeros and poles having magnitude larger than one, but for zeros and poles strictly inside the unit circle the asymptotic variance grows exponentially with the model order. We analyze how the variance of poles and zeros is affected by model order, model structure and input excitation. We treat general black-box model structures including ARMAX and Box–Jenkins models.     

The effect of regularization on variance error

This note addresses the problem of quantifying the effect of noise induced error(so called "variance error") in system estimates found via a regularised cost criterion. It builds on recent work by the authors in which expressions for nonregularised criterions are derived which are exact for finite model order. Those new expressions were established to be very different to previous quantifications that are widely used but based on asymptotic in model order arguments. A key purpose of this note is to expose a rapprochement between these new finite model order, and the pre-existing asymptotic model order quantifications. In so doing, a further new result is established. Namely, that variance error in the frequency domain is dependent on the choice of the point about which regularization is affected.     

Solution of the Schrödinger equation by a high order perturbation method based on a linear reference potential

The paper is devoted to the enhancement of the accuracy of the line-based perturbation method via the introduction of the perturbation corrections. We effectively construct the first and the second order corrections. We also perform the error analysis to predict that the introduction of successive corrections substantially enhances the order of the method from four, for the zeroth order version, to six and ten when the first and the second-order corrections are included. In order to remove the effect of the accuracy loss due to near-cancellation of like-terms when evaluating the perturbation corrections we construct alternative asymptotic formulae using a Maple code. We also propose a procedure for choosing the step size in terms of the preset accuracy and give a number of numerical illustrations.