In this paper, we revisit three fundamental and popular stochastic optimization algorithms (namely, Online Proximal Gradient, Regularized Dual Averaging method and ADMM with online proximal gradient) and analyze their convergence speed under conditions weaker than those in literature. In particular, previous works showed that these algorithms converge at a rate of O (\ln T/T) when the loss function is strongly convex, and O (1 /\sqrtT) in the weakly convex case. In contrast, we relax the strong convexity assumption of the loss function, and show that the algorithms converge at a rate O (\ln T/T) if the \em expectation of the loss function is \em locally strongly convex. This is a much weaker assumption and is satisfied by many practical formulations including Lasso and Logistic Regression. Our analysis thus extends the applicability of these three methods, as well as provides a general recipe for improving analysis of convergence rate for stochastic and online optimization algorithms.

This note aims to point out one typographical error and one calculation error in the above paper (ibid., vol. 23, no. 5, pp. 827-834, May 2012).

This brief deals with the estimator design problem for discrete-time switched neural networks with time-varying delay. One main problem is the asynchronous-mode switching between the neuron state and the estimator. Our goal is to design a mode-dependent estimator for the switched neural networks under average dwell time switching such that the estimation error system is exponentially stable with a prescribed l2 gain (in the H∞ sense) from the noise signal to the estimation error. A new Lyapunov functional is constructed that may increase during the mismatched switchings. New results on the stability and l2 gain analysis are then obtained. The admissible estimator gains are computed by solving a set of linear matrix inequalities. The relations among the switching law, the maximal delay upper bound, and the optimal H∞ disturbance attenuation level are established. The effectiveness of the proposed design method is finally illustrated by a numerical example.

This paper proposes a new feature selection method using a mutual information-based criterion that measures the importance of a feature in a backward selection framework. It considers the dependency among many features and uses either one of two well-known probability density function estimation methods when computing the criterion. The proposed approach is compared with existing mutual information-based methods and another sophisticated filter method on many artificial and real-world problems. The numerical results show that the proposed method can effectively identify the important features in data sets having dependency among many features and is superior, in almost all cases, to the benchmark methods.

Tuning of the regularization parameter C is a well-known process in the implementation of a support vector machine (SVM) classifier. Such a tuning process uses an appropriate validation function whose value, evaluated over a validation set, has to be optimized for the determination of the optimal C. Unfortunately, most common validation functions are not smooth functions of C. This brief presents a method for obtaining the global optimal solution of these non-smooth validation functions. The method is guaranteed to find the global optimum and relies on the regularization solution path of SVM over a range of C values. When the solution path is available, the computation needed is minimal.

This paper presents a new wrapper-based feature selection method for support vector regression (SVR) using its probabilistic predictions. The method computes the importance of a feature by aggregating the difference, over the feature space, of the conditional density functions of the SVR prediction with and without the feature. As the exact computation of this importance measure is expensive, two approximations are proposed. The effectiveness of the measure using these approximations, in comparison to several other existing feature selection methods for SVR, is evaluated on both artificial and real-world problems. The result of the experiments show that the proposed method generally performs better than, or at least as well as, the existing methods, with notable advantage when the dataset is sparse.

This paper presents an approach to optimize the zebrafish-embryo microinjection process by selecting suitable speed trajectories for the motion of the micropipette, with the objective of minimizing the risk of damaging the embryo during the microinjection process. A viscoelastic model of a zebrafish embryo is developed based on experimental data. The speed optimization problem is formulated based on this viscoelastic model. Simulation results indicate that there exists an optimal speed trajectory for the micropipette under certain conditions. The key benefit of this speed optimization approach is that the turgor pressure inside the membrane is prevented from increasing significantly during the microinjection process, thus avoiding damaging the biological components in the embryo.

This paper presents a novel wrapper-based feature selection method for Support Vector Regression (SVR) using its probabilistic predictions. The method computes the importance of a feature by aggregating the difference, over the feature space, of the conditional density functions of the SVR prediction with and without the feature. As the exact computation of this importance measure is expensive, two approximations are proposed. The effectiveness of the measure using these approximations, in comparison to several other existing feature selection methods for SVR, is evaluated on both artificial and real-world problems. The result of the experiment shows that the proposed method generally performs better, and at least as well as the existing methods, with notable advantage when the data set is sparse.

This paper describes an improved algorithm for the numerical solution to the support vector machine (SVM) classification problem for all values of the regularization parameter C . The algorithm is motivated by the work of Hastie and follows the main idea of tracking the optimality conditions of the SVM solution for ascending value of C . It differs from Hastie's approach in that the tracked path is not assumed to be 1-D. Instead, a multidimensional feasible space for the optimality condition is used to solve the tracking problem. Such a treatment allows the algorithm to properly handle data sets which Hastie's approach fails. These data sets are characterized by the presence of linearly dependent points (in the kernel space), duplicate points, or nearly duplicate points. Such data sets are quite common among many real-world data, especially those with nominal features. Other contributions of this paper include a unifying formulation of the tracking process in the form of a linear programming problem, update formula for the linear programs, considerations that guard against accumulation of errors resulting from the use of incremental updates, and routines to speed up the algorithm. The algorithm is implemented under the Matlab environment and is available for download. Experiments with several data sets including data set having up to several thousand data points are reported.

This paper presents a new wrapper-based feature selection method for multilayer perceptron (MLP) neural networks. It uses a feature ranking criterion to measure the importance of a feature by computing the aggregate difference, over the feature space, of the probabilistic outputs of the MLP with and without the feature. Thus, a score of importance with respect to every feature can be provided using this criterion. Based on the numerical experiments on several artificial and real-world data sets, the proposed method performs, in general, better than several selected feature selection methods for MLP, particularly when the data set is sparse or has many redundant features. In addition, as a wrapper-based approach, the computational cost for the proposed method is modest.

Stability and performance degradation in feedback control systems under saturation can be overcome by anti-windup techniques. In this paper, a new anti-windup approach called “Auxiliary Input Anti-windup” is proposed, which incorporates an auxiliary input into the controller of the system. Finding the maximal output admissible set of the augmented closed-loop system, the control effort is then obtained from a quadratic optimization problem subjected to linear inequality constraints. Performance and effectiveness of the proposed anti-windup approach, as compared with other methods, is illustrated with simulation examples. Experimental results show that the introduced Auxiliary Input (AI) anti-windup scheme improves the performance of the system.

A novel electroencephalogram (EEG) artifact removal method is presented in this paper. The proposed method combines a probabilistic multi-class Support Vector Machine (SVM) and an error correction algorithm for component classification, where i) the probabilistic multi-class SVM is modified to properly handle the unbalanced nature of component classification and ii) the error correction algorithm is used to accommodate the structural information of the learning problem. The proposed component classifier was tested on real-life EEG data and it significantly outperformed the standard SVM used in the literature. A qualitative evaluation on the reconstructed EEG shows that the proposed artifact removal method greatly reduced the amount of artifacts while well preserving brain activities in almost all EEG epochs.

Novel feature-selection methods are proposed for multi-class support-vector-machine (SVM) learning. They are based on two new feature-ranking criteria. Both criteria, collectively termed multi-class feature-based sensitivity of posterior probabilities (MFSPP), evaluate the importance of a feature by computing the aggregate value, over the feature space, of the absolute difference of the probabilistic outputs of the multi-class SVM with and without the feature. In their original form, the criteria are computationally expensive and three approximations, MFSPP1-MFSPP3, are then proposed. In a carefully controlled experimental study, all these three approximations are tested on various artificial and benchmark datasets. Results show that they outperform the multi-class versions of support-vector-machine recursive feature-elimination method (SVM-RFE) and other standard filtering methods, with one of the three proposed approximations having a slight edge over the other two. Based on the experiments, the advantage of the proposed methods is particularly significant when training dataset is sparse.

This paper presents a new wrapper-based feature selection method for multi-layer perceptrons (MLP) neural networks. It uses a feature ranking criterion to measure the importance of a feature by computing the aggregate difference, over the feature space, of the probabilistic outputs of the MLP with and without the feature. Thus, a score of importance with respect to every feature can be provided using this criterion. The proposed criterion has inexpensive evaluation. Based on the numerical experiment on several artificial and real-world data sets, the proposed method performs at least as well, if not better, than several existing feature selection methods for MLP.

A straight line needle trajectory is typically used in medical needle insertion for percutaneous intervention. Flexible needle steering may be able to avoid obstacles, and reach regions that are currently inaccessible using straight line trajectory. The success of flexible needle insertion in clinical application, for example, biopsy to obtain a tissue sample from human liver organ is dependent on how accurate the motion path can be planned and simulated. We developed a motion planning algorithm for flexible needle insertion with an integrative model of human liver organ, and finite element models of needle and needle-tissue interaction. The aim of image based integrative modeling is to have a unified organ model of patient comprising finite element and implicit surface models of blood vessels, normal and pathological tissues. The trajectory path can be determined in an interactive manner. The generated trajectory for flexible needles avoids obstacles (vessels) to reach target (tumor) inaccessible to rigid needles. The algorithm can also be used to simulate needle bending due to dynamic contact with tumor

The paper considers piecewise linear system with bounded disturbances (PWLBD system). Some properties of the minimal disturbance invariant set Finfinof PWLBD systems are discussed and an algorithm for the computation of its outer bounds is presented. In general, the set Finfinof PWLBD system is non-convex and a union of many polytopes. The resulting outer bounds are convex and remain disturbance invariant property

Sequential minimal optimization (SMO) is one popular algorithm for training support vector machine (SVM), but it still requires a large amount of computation time for solving large size problems. This paper proposes one parallel implementation of SMO for training SVM. The parallel SMO is developed using message passing interface (MPI). Specifically, the parallel SMO first partitions the entire training data set into smaller subsets and then simultaneously runs multiple CPU processors to deal with each of the partitioned data sets. Experiments show that there is great speedup on the adult data set and the Mixing National Institute of Standard and Technology (MNIST) data set when many processors are used. There are also satisfactory results on the Web data set.

The least square support vector machines (LS-SVM) formulation corresponds to the solution of a linear system of equations. Several approaches to its numerical solutions have been proposed in the literature. In this letter, we propose an improved method to the numerical solution of LS-SVM and show that the problem can be solved using one reduced system of linear equations. Compared with the existing algorithm for LS-SVM, the approach used in this letter is about twice as efficient. Numerical results using the proposed method are provided for comparisons with other existing algorithms.

One of the main challenges in support vector machine (SVM) for data mining applications is to obtain explicit knowledge from the solutions of SVM for explaining classification decisions. This paper exploits the fact that the decisions from a non-linear SVM could be decoded into linguistic rules based on the information provided by support vectors and its decision function. Given a support vector of a certain class, cross points between each line, which is extended from the support vector along each axis, and SVM decision hyper-curve are searched first. A hyper-rectangular rule is derived from these cross points. The hyper-rectangle is tuned by a tuning phase in order to exclude those out-class data points. Finally, redundant rules are merged to produce a compact rule set. Simultaneously, important attributes could be highlighted in the extracted rules. Rule extraction results from our proposed method could follow decisions of SVM classifiers very well. Comparisons between our method and other rule extraction methods are also carried out on several benchmark data sets. Higher rule accuracy is obtained in our method with fewer number of premises in each rule.

In this paper, we use a unified loss function, called the soft insensitive loss function, for Bayesian support vector regression. We follow standard Gaussian processes for regression to set up the Bayesian framework, in which the unified loss function is used in the likelihood evaluation. Under this framework, the maximum a posteriori estimate of the function values corresponds to the solution of an extended support vector regression problem. The overall approach has the merits of support vector regression such as convex quadratic programming and sparsity in solution representation. It also has the advantages of Bayesian methods for model adaptation and error bars of its predictions. Experimental results on simulated and real-world data sets indicate that the approach works well even on large data sets.

In this paper, we give an efficient method for computing the leave-one-out (LOO) error for support vector machines (SVMs) with Gaussian kernels quite accurately. It is particularly suitable for iterative decomposition methods of solving SVMs. The importance of various steps of the method is illustrated in detail by showing the performance on six benchmark datasets. The new method often leads to speedups of 10-50 times compared to standard LOO error computation. It has good promise for use in hyperparameter tuning and model comparison

This letter describes Bayesian techniques for support vector classification. In particular, we propose a novel differentiable loss function, called the trigonometric loss function, which has the desirable characteristic of natural normalization in the likelihood function, and then follow standard gaussian processes techniques to set up a Bayesian framework. In this framework, Bayesian inference is used to implement model adaptation, while keeping the merits of support vector classifier, such as sparseness and convex programming. This differs from standard gaussian processes for classification. Moreover, we put forward class probability in making predictions. Experimental results on benchmark data sets indicate the usefulness of this approach.

Considers fast algorithms for computing the Euclidean distance between objects that are modeled by convex polytopes in three-dimensional space. The algorithms, designated by RGJK, are modifications of the Gilbert-Johnson-Keerthi algorithm that follow the scheme originated by Cameron (1997). Each polytope is represented by its vertices and a list of adjacent vertices for each vertex. When the algorithms are appropriately applied to a pair of objects that have small incremental motions, they share the advantage of the closest-feature algorithm introduced by Lin and Canny (1991): computational time is very small and does not depend significantly on the total number of object vertices. However, when the objects contain complex vertices or faces, the time can increase drastically. Reasons for this problem are analyzed and algorithmic fixes for them are given. Other contributions to algorithmic performance include a procedure for reducing computational time in the presence of collisions. Comprehensive numerical experiments illuminate the dependence of computational time on algorithmic details, object complexity, and the size of incremental motions. The experiments include direct comparisons of RGJK with the closest-feature algorithms of Lin and Canny and of Mirtich (1998).

A fast algorithm is presented for computing the growth distance between a pair of convex objects in three-dimensional space. The growth distance is a measure of both separation and penetration between objects. When the objects are polytopes represented by their faces, the growth distance is determined by the solution of a linear program (LP). The article presents an approach to the solution of the LP. Under appropriate conditions, the computational time is very small and does not depend on the total number of faces of the objects. Compared to the existing algorithm for growth distance, there is a time reduction of several orders of magnitude. This increase in speed is achieved by exploiting two resources: adjacency of the object faces and the computational coherence induced by incremental motions of the objects, Computational experiments show that the performance of the algorithm is in the same range as the fastest codes for the computation of the Euclidean separation distance.

This paper introduces a novel heuristic roadmap method for path planning, one that is inspired by the Voronoi diagram concept, but easily applicable to general configuration spaces. The roadmap is formed by connecting the local maxima of a clearance function which is defined using distance functions. Reaching the roadmap from any free configuration is achieved by applying the continuous active-set optimization algorithm to the maximization of the clearance function. Preliminary experiments with the new roadmap algorithm point to its potential utility in solving practical path planning problems.

A fast algorithm is presented for computing the growth distance between a pair of convex objects in three dimensional space. The growth distance has been introduced by Ong et al. (1996) as a measure of both separation and penetration between objects. This article presents an approach to the growth distance computation using geometrical consideration. Under appropriate conditions, the computational time is very small and does not depend on the total number of faces of the objects. This increase in speed comes from the use of information on the adjacency of faces of the objects. Such adjacency information is particularly useful for object undergoing incremental motion. Computational experiments provided shows that the performance of the algorithm is in the same range as the known fastest Euclidean distance code.

An algorithm is presented for computing the Euclidean distance between a pair of objects represented by convex polytopes in three dimensional space. It is a fast version of the well known algorithm by Gilbert, Johnson and Keerthi (1988) in which the polytopes are characterized by their vertices. The improvement in speed comes from the inclusion of additional structural information on the objects; for each vertex there is a list of adjacent vertices. No other information or preprocessing of data is needed. Following Cameron, the adjacency structures are used to greatly reduce the number of inner product evaluations needed to compute the polytope support functions used in the original Gilbert-Johnson-Keerthi algorithm. When the algorithm is applied to a pair of objects that move incrementally along smooth paths, it shares the advantage of the incremental distance algorithm introduced by Lin and Canny (1991). Algorithmic details and performance issues are developed fully. Computational experiments provide quantitative data on the effects of object complexity and the size of incremental object motions.

There are many applications in robotics where collision detection, separation distance and penetration distance between geometrical models of objects are required. Efficient numerical procedures for the computation of these proximal relations are important as they are frequently invoked. A new measure of penetration and separation called the growth distance has been introduced in the literature. It has been shown that the growth distance can be efficiently computed for convex polytopes. This paper extends the computation of growth distance to smooth convex objects. Specifically, the authors introduce a formulation of the growth distance for smooth convex objects which is well suited for numerical computation. By modeling convex objects as the union of convex subobjects, the growth distance of a wide family of objects can be computed. However, computation of growth distance for such object models may be expensive. A fast algorithm is introduced which reduces the computational time significantly. In the case where the objects undergo continuous relative motion and the growth distances must be evaluated for a large number of closely spaced points along the motion, further reduction in computational effort is achieved. Numerical experiments with objects that are found in typical robot applications are also provided.

Quantitative measures for the separation and penetration of two convex objects are formulated, These measures, called separation and penetration growth distances, are closely related to traditional translational distance measures and share many of their desirable properties. The solution of a single optimization problem yields both the separation and penetration distances. For 3D polytopes the optimization problem is a linear program in four variables whose asymptotic computational time is O(m), where m is the number of linear inequalities required to specify the two polytopes. This equals or far betters the known times required to compute translational distances: O(m) for separation and 0(m/sup 2/ log m) for penetration. When the positioning of the two objects depends on configuration variables, the partial derivatives of the growth distances with respect to the configuration variables exist almost everywhere. Derivatives of the penetration growth distance can be used to construct motions which separate the objects. An application to path finding is described.

New quantitative measures for the separation and penetration of two convex objects are formulated. These measures, called separation and penetration growth distances, are closely related to traditional distance measures and share many of their desirable properties. The solution of a single optimization problem yields both the separation and penetration distances. For polytopal objects the optimization problem is a simple linear program whose computational time is O(m), where m is the number of linear inequalities required to specify the two polytopes. Numerical experiments with three dimensional polytopes demonstrate that the growth distances can be computed more rapidly than the traditional distances with a large advantage in the case of penetration distances.>

An algorithmic approach to path finding is considered for a general class of robotic systems. The basic idea is to formulate an optimization problem over a family of continuous paths which satisfy the specified end conditions and possess robot-obstacle collisions. The cost to be minimized depends on the penetration growth distance, a new measure for the depth of intersection between a pair of object models. The growth distance and its derivatives with respect to configuration variables describing the orientation and position of the objects can be computed quickly. This is a key factor in attaining acceptable computational times. Variations of the initial strategy, which improve computational efficiency and reliability, are discussed. Significant reductions in computational time are easily obtained by parallel processing.>