A primal method for multiple kernel learning

The canonical support vector machines (SVMs) are based on a single kernel, recent publications have shown that using multiple kernels instead of a single one can enhance interpretability of the decision function and promote classification accuracy. However, most of existing approaches mainly reformulate the multiple kernel learning as a saddle point optimization problem which concentrates on solving the dual. In this paper, we show that the multiple kernel learning (MKL) problem can be reformulated as a BiConvex optimization and can also be solved in the primal. While the saddle point method still lacks convergence results, our proposed method exhibits strong optimization convergence properties. To solve the MKL problem, a two-stage algorithm that optimizes canonical SVMs and kernel weights alternately is proposed. Since standard Newton and gradient methods are too time-consuming, we employ the truncated-Newton method to optimize the canonical SVMs. The Hessian matrix need not be stored explicitly, and the Newton direction can be computed using several Preconditioned Conjugate Gradient steps on the Hessian operator equation, the algorithm is shown more efficient than the current primal approaches in this MKL setting. Furthermore, we use the Nesterov’s optimal gradient method to optimize the kernel weights. One remarkable advantage of solving in the primal is that it achieves much faster convergence rate than solving in the dual and does not require a two-stage algorithm even for the single kernel LapSVM. Introducing the Laplacian regularizer, we also extend our primal method to semi-supervised scenario. Extensive experiments on some UCI benchmarks have shown that the proposed algorithm converges rapidly and achieves competitive accuracy.     

Primal explicit max margin feature selection for nonlinear support vector machines

Embedding feature selection in nonlinear support vector machines (SVMs) leads to a challenging non-convex minimization problem, which can be prone to suboptimal solutions. This paper develops an effective algorithm to directly solve the embedded feature selection primal problem. We use a trust-region method, which is better suited for non-convex optimization compared to line-search methods, and guarantees convergence to a minimizer. We devise an alternating optimization approach to tackle the problem efficiently, breaking it down into a convex subproblem, corresponding to standard SVM optimization, and a non-convex subproblem for feature selection. Importantly, we show that a straightforward alternating optimization approach can be susceptible to saddle point solutions. We propose a novel technique, which shares an explicit margin variable to overcome saddle point convergence and improve solution quality. Experiment results show our method outperforms the state-of-the-art embedded SVM feature selection method, as well as other leading filter and wrapper approaches.     

Prox-regularization of the dual method of centers for generalized fractional programs

We present in this paper a prox-dual regularization algorithm for solving generalized fractional programming problems. The algorithm combines the dual method of centres for generalized fractional programs and the proximal point algorithm and can handle nondifferentiable convex problems with possibly unbounded feasible constraints set. The proposed procedure generates two sequences of dual and primal values that approximate the optimal value of the considered problem respectively from below and from above at each step. It also generates a sequence of dual solutions that converges to a solution of the dual problem, and a sequence of primal solutions whose every accumulation point is a solution of the primal problem. For a class of problems, including linear fractional programs, the algorithm converges linearly.     

An efficient multiple-kernel learning for pattern classification

Support vector machines (SVMs) have been broadly applied to classification problems. However, a successful application of SVMs depends heavily on the determination of the right type and suitable hyperparameter settings of kernel functions. Recently, multiple-kernel learning (MKL) algorithms have been developed to deal with these issues by combining different kernels together. The weight with each kernel in the combination is obtained through learning. Lanckriet et al. proposed a way of deriving the weights by transforming the learning into a semidefinite programming (SDP) problem with a transduction setting. However, the amount of time and space required by this method is demanding. In this paper, we reformulate the SDP problem with an induction setting and incorporate two strategies to reduce the search complexity of the learning process, based on the comments discussed in the Lanckriet et al. paper. The primal and dual forms of SDP are derived. A discussion on computation complexity is given. Experimental results obtained from synthetic and benchmark datasets show that the proposed method runs efficiently in multiple-kernel learning.     

Hessian distances and their applications in the complexity analysis of interior-point methods

For interior points in convex cones, we introduce the Hessian distance function, and show that it is convenient for complexity analysis of polynomial-time interior-point methods (IPMs). As an example of its application, we develop new infeasible-start IPM for the linear conic optimization problem. In our setting, the primal and dual cones need not to be self-dual. We can start from any primal–dual point in the interior of the cones. Then, the damped Newton's method can be used for obtaining an approximate solution for the strictly feasible case, or for detecting primal/dual infeasibility. The complexity of these cases depends on the Hessian distance between the starting point and the feasibility/infeasibility certificates. We also present some numerical results.     

Interior point methods meet simplex in L∞, fitting problems

Interior point methods specialized to the L_∞ fitting problem are surveyed, improved, and compared with the traditional simplex approach. A primal affine‐scaling interior point method is presented, completing the affine‐scaling interior point family approach to the L_∞ fitting problem. Computational complexity and data storage are reduced for interior point approaches when dealing with polynomial fitting problems. Numerical experiments indicate that interior point approaches rarely perform better than the simplex method for the tested problems. The primal affine‐scaling method presented in this paper achieved the best results among the interior point family.     

Scheduling parallel-machine batch operations to maximize on-time delivery performance

In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing on-time delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NP-hard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadth-first tree search algorithm that gives evidence of the quality of the solutions.     

On decentralized negotiation of optimal consensus

A consensus problem consists of finding a distributed control strategy that brings the state or output of a group of agents to a common value, a consensus point. In this paper, we propose a negotiation algorithm that computes an optimal consensus point for agents modeled as linear control systems subject to convex input constraints and linear state constraints. By primal decomposition and incremental subgradient methods, it is shown that the algorithm can be implemented such that each agent exchanges only a small amount of information per iteration with its neighbors.     

Ginisupport vector machines for segmental minimum Bayes risk decoding of continuous speech

We describe the use of support vector machines (SVMs) for continuous speech recognition by incorporating them in segmental minimum Bayes risk decoding. Lattice cutting is used to convert the Automatic Speech Recognition search space into sequences of smaller recognition problems. SVMs are then trained as discriminative models over each of these problems and used in a rescoring framework. We pose the estimation of a posterior distribution over hypotheses in these regions of acoustic confusion as a logistic regression problem. We also show that GiniSVMs can be used as an approximation technique to estimate the parameters of the logistic regression problem. On a small vocabulary recognition task we show that the use of GiniSVMs can improve the performance of a well trained hidden Markov model system trained under the Maximum Mutual Information criterion. We also find that it is possible to derive reliable confidence scores over the GiniSVM hypotheses and that these can be used to good effect in hypothesis combination. We discuss the problems that we expect to encounter in extending this approach to large vocabulary continuous speech recognition and describe initial investigation of constrained estimation techniques to derive feature spaces for SVMs.     

Fuzzy support vector machines

A support vector machine (SVM) learns the decision surface from two distinct classes of the input points. In many applications, each input point may not be fully assigned to one of these two classes. In this paper, we apply a fuzzy membership to each input point and reformulate the SVMs such that different input points can make different contributions to the learning of decision surface. We call the proposed method fuzzy SVMs (FSVMs).     

A new maximal-margin spherical-structured multi-class support vector machine

Support vector machines (SVMs), initially proposed for two-class classification problems, have been very successful in pattern recognition problems. For multi-class classification problems, the standard hyperplane-based SVMs are made by constructing and combining several maximal-margin hyperplanes, and each class of data is confined into a certain area constructed by those hyperplanes. Instead of using hyperplanes, hyperspheres that tightly enclosed the data of each class can be used. Since the class-specific hyperspheres are constructed for each class separately, the spherical-structured SVMs can be used to deal with the multi-class classification problem easily. In addition, the center and radius of the class-specific hypersphere characterize the distribution of examples from that class, and may be useful for dealing with imbalance problems. In this paper, we incorporate the concept of maximal margin into the spherical-structured SVMs. Besides, the proposed approach has the advantage of using a new parameter on controlling the number of support vectors. Experimental results show that the proposed method performs well on both artificial and benchmark datasets.     

Convergence Analysis of Primal–Dual Based Methods for Total Variation Minimization with Finite Element Approximation

We consider a minimization model with total variational regularization, which can be reformulated as a saddle-point problem and then be efficiently solved by the primal–dual method. We utilize the consistent finite element method to discretize the saddle-point reformulation; thus possible jumps of the solution can be captured over some adaptive meshes and a generic domain can be easily treated. Our emphasis is analyzing the convergence of a more general primal–dual scheme with a combination factor for the discretized model. We establish the global convergence and derive the worst-case convergence rate measured by the iteration complexity for this general primal–dual scheme. This analysis is new in the finite element context for the minimization model with total variational regularization under discussion. Furthermore, we propose a prediction–correction scheme based on the general primal–dual scheme, which can significantly relax the step size for the discretization in the time direction. Its global convergence and the worst-case convergence rate are also established. Some preliminary numerical results are reported to verify the rationale of considering the general primal–dual scheme and the primal–dual-based prediction–correction scheme.     

Implementation and analysis of alternative algorithms for generalized shortest path problems

This paper addresses a special class of deterministic dynamic programming problems which can be formulated as a generalized network problem. Because of the similarities between this class of dynamic programming problems and shortest path problems, we are naming it the Generalized Shortest Path problem. A new primal extreme point algorithm and a new special dual algorithm are proposed here. While researchers have presented a variety of algorithms to solve this class of problems, there has been no comuptational analysis of these algorithms. An in-depth computational analysis is performed to determine the most efficient set of rules for implementing the algorithms of this paper.     

核对齐多核模糊支持向量机

支持向量机（SVMs）是当前被广泛使用的机器学习技术,其通过最优分割超平面来提高分类器的泛化能力,在实际应用中表现优异。然而SVM也存在易受噪声影响,以及核函数选择等难题。针对以上问题,本文将基于核对齐的多核学习方法引入到模糊支持向量机（fuzzy support vector machine, FSVM）中,提出了模糊多核支持向量机模型（multiple kernel fuzzy support vector machine,MFSVM）。MFSVM通过模糊粗糙集方法计算每一样例隶属度;其次,利用核对齐的多核方法计算每一单核权重,并将组合核引入到模糊支持向量机中。该方法不仅提高了支持向量机的抗噪声能力,也有效避免了核选择难题。在UCI数据库上进行实验,结果表明本文所提方法具有较高的分类精度,验证了该方法的可行性与有效性。     

Geometrical properties of nu support vector machines with different norms

By employing the L1 or Linfinity norms in maximizing margins, support vector machines (SVMs) result in a linear programming problem that requires a lower computational load compared to SVMs with the L2 norm. However, how the change of norm affects the generalization ability of SVMs has not been clarified so far except for numerical experiments. In this letter, the geometrical meaning of SVMs with the Lp norm is investigated, and the SVM solutions are shown to have rather little dependency on p.     

The background primal sketch: An approach for tracking moving objects

In this paper we present an algorithm that integrates spatial and temporal information for the tracking of moving nonrigid objects. In addition, we obtain outlines of the moving objects.Three basic ingredients are employed in the proposed algorithm, namely, the background primal sketch, the threshold, and outlier maps. The background primal sketch is an edge map of the background without moving objects. If the background primal sketch is known, then edges of moving objects can be determined by comparing the edge map of the input image with the background primal sketch. A moving edge point is modeled as an outlier, that is, a pixel with an edge value differing from the background edge value in the background primal sketch by an amount larger than the threshold in the threshold map at the same physical location. The map that contains all the outliers is called the outlier map. In this paper we present techniques based on robust statistics for determining the background primal sketch, the threshold, and outlier maps.In an ideal situation the outlier map would contain the complete outlines of the moving objects. In practice, the outliers do not form closed contours. The final step of the algorithm employs an edge-guided morphological approach to generate closed outlines of the moving objects. The proposed approach has been tested on sequences of moving human blood cells (neutrophil) as well as of human body motion with encouraging results.     

核方法在人脸识别中的应用

1 引言人脸识别技术广泛应用于身份验证、门检系统以及人员监视等方面,在过去的几年里,人脸识别技术有了很大的发展。人脸识别技术与普通的模式识别不同,主要是因为在一般的模式识别中,有几个分类,每个分类中有很多样本,这样可以安排大量样本进行训练;相反,人脸识别中通常会有很多不同的人脸,每个人脸代表一个分类,而每个分类中的样本数都比较少,在很多情况下,甚至每个人只有一张图片(如身份证照片),在文[4]中提出了处理只有一个样本情况下的人脸识别。     

Wavelet kernel support vector machines forecasting techniques: Case study on water-level predictions during typhoons

This paper presents a novel algorithm, wavelet support vector machines (wavelet SVMs), for forecasting the hourly water levels at gauging stations. These stations are under strong precipitations and affected by tidal effects during typhoons. An admissible wavelet kernel SVMs implements the combination of wavelet technique with SVMs. The wavelet is a multi-dimension wavelet function that can approximate arbitrary nonlinear functions. Using both classical Gaussian and wavelet SVMs, this study constructed the channel level models for forecasting downstream water levels. The developed models were then applied to the Tanshui River Basin in Taiwan and the water levels at various lag times predicted by both Gaussian and wavelet SVMs were compared. Analysis results showed that the optimal situation occurred at the lag time of 3 h with relative mean square errors (RMSEs) of 0.205 and 0.160 m obtained by the Gaussian and wavelet SVMs, respectively at Taipei Bridge station and RMSEs of 0.154 and 0.092 m at Tudigong station, respectively. As seen in the comparison, wavelet SVMs yielded more accurate predictions than Gaussian SVMs and offered a practical solution to the problem of water-level predictions during typhoon attacks.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.     

Texture classification using the support vector machines

In recent years, support vector machines (SVMs) have demonstrated excellent performance in a variety of pattern recognition problems. In this paper, we apply SVMs for texture classification, using translation-invariant features generated from the discrete wavelet frame transform. To alleviate the problem of selecting the right kernel parameter in the SVM, we use a fusion scheme based on multiple SVMs, each with a different setting of the kernel parameter. Compared to the traditional Bayes classifier and the learning vector quantization algorithm, SVMs, and, in particular, the fused output from multiple SVMs, produce more accurate classification results on the Brodatz texture album.