Robust multicategory support vector machines using difference convex algorithm

The support vector machine (SVM) is one of the most popular classification methods in the machine learning literature. Binary SVM methods have been extensively studied, and have achieved many successes in various disciplines. However, generalization to multicategory SVM (MSVM) methods can be very challenging. Many existing methods estimate k functions for k classes with an explicit sum-to-zero constraint. It was shown recently that such a formulation can be suboptimal. Moreover, many existing MSVMs are not Fisher consistent, or do not take into account the effect of outliers. In this paper, we focus on classification in the angle-based framework, which is free of the explicit sum-to-zero constraint, hence more efficient, and propose two robust MSVM methods using truncated hinge loss functions. We show that our new classifiers can enjoy Fisher consistency, and simultaneously alleviate the impact of outliers to achieve more stable classification performance. To implement our proposed classifiers, we employ the difference convex algorithm for efficient computation. Theoretical and numerical results obtained indicate that for problems with potential outliers, our robust angle-based MSVMs can be very competitive among existing methods.     

The consistency of multicategory support vector machines

The goal of classification (or pattern recognition) is to construct a classifier with small misclassification error. The notions of consistency and universal consistency are important to the construction of classification rules. A consistent rule guarantees us that taking more samples essentially suffices to roughly reconstruct the unknown distribution. Support vector machine (SVM) algorithm is one of the most important rules in two category classification. How to effectively extend the SVM for multicategory classification is still an on-going research issue. Different versions of multicategory support vector machines (MSVMs) have been proposed and used in practice. We study the one designed by Lee, Lin and Wahba with hinge loss functional. The consistency of MSVMs is established under a mild condition. As a corollary, the universal consistency holds true if the reproducing kernel Hilbert space is dense in C norm. In addition, an example is given to demonstrate the main results. Dedicated to Charlie Micchelli on the occasion of his 60th birthday Supported in part by NSF of China under Grants 10571010 and 10171007.     

Sparse Penalized Forward Selection for Support Vector Classification

We propose a new binary classification and variable selection technique especially designed for high-dimensional predictors. Among many predictors, typically, only a small fraction of them have significant impact on prediction. In such a situation, more interpretable models with better prediction accuracy can be obtained by variable selection along with classification. By adding an ?₁-type penalty to the loss function, common classification methods such as logistic regression or support vector machines (SVM) can perform variable selection. Existing penalized SVM methods all attempt to jointly solve all the parameters involved in the penalization problem altogether. When data dimension is very high, the joint optimization problem is very complex and involves a lot of memory allocation. In this article, we propose a new penalized forward search technique that can reduce high-dimensional optimization problems to one-dimensional optimization by iterating the selection steps. The new algorithm can be regarded as a forward selection version of the penalized SVM and its variants. The advantage of optimizing in one dimension is that the location of the optimum solution can be obtained with intelligent search by exploiting convexity and a piecewise linear or quadratic structure of the criterion function. In each step, the predictor that is most able to predict the outcome is chosen in the model. The search is then repeatedly used in an iterative fashion until convergence occurs. Comparison of our new classification rule with ?₁-SVM and other common methods show very promising performance, in that the proposed method leads to much leaner models without compromising misclassification rates, particularly for high-dimensional predictors.     

The RH boundary value problem of the k-monogenic functions

In this paper we study the Riemann and Hilbert problems of k-monogenic functions. By using Euler operator, we transform the boundary value problem of k-monogenic functions into the boundary value problems of monogenic functions. Then by the Almansi-type theorem of k-monogenic functions, we get the solutions of these problems.     

Multiclass Probability Estimation With Support Vector Machines

Multiclass classification and probability estimation have important applications in data analytics. Support vector machines (SVMs) have shown great success in various real-world problems due to their high classification accuracy. However, one main limitation of standard SVMs is that they do not provide class probability estimates, and thus fail to offer uncertainty measure about class prediction. In this article, we propose a simple yet effective framework to endow kernel SVMs with the feature of multiclass probability estimation. The new probability estimator does not rely on any parametric assumption on the data distribution, therefore, it is flexible and robust. Theoretically, we show that the proposed estimator is asymptotically consistent. Computationally, the new procedure can be conveniently implemented using standard SVM softwares. Our extensive numerical studies demonstrate competitive performance of the new estimator when compared with existing methods such as multiple logistic regression, linear discrimination analysis, tree-based methods, and random forest, under various classification settings. Supplementary materials for this article are available online.     

基于支持向量机委员会机器的个人信用评估模型

为了充分利用SVM在个人信用评估方面的优点、克服其不足,提出了基于支持向量机委员会机器的个人信用评估模型.将模型与基于属性效用函数估计构造新学习样本方法结合起来进行个人信用评估;经实证分析及与SVM方法对比发现,模型具有更好、更快、更多适应性的预测分类能力.     

Testing satisfiability

Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1,d]. We say that Φ is ε-far from satisfiable, if one must remove at least εn^k functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ε-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/ε², are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT.Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ε-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ε-far from satisfiable instances, in randomized constant time.From the above result we obtain as a special case, previous results of Alon and Krivelevich, and of Czumaj and Sohler, concerning testing of graphs and hypergraphs colorability. We also discuss the difference between testing with one-sided and two-sided error.     

Block Coordinate Relaxation Methods for Nonparametric Wavelet Denoising

Abstract

An important class of nonparametric signal processing methods entails forming a set of predictors from an overcomplete set of basis functions associated with a fast transform (e.g., wavelet packets). In these methods, the number of basis functions can far exceed the number of sample values in the signal, leading to an ill-posed prediction problem. The “basis pursuit” denoising method of Chen, Donoho, and Saunders regularizes the prediction problem by adding an l ₁ penalty term on the coefficients for the basis functions. Use of an l ₁ penalty instead of l ₂ has significant benefits, including higher resolution of signals close in time/frequency and a more parsimonious representation. The l ₁ penalty, however, poses a challenging optimization problem that was solved by Chen, Donoho and Saunders using a novel application of interior-point algorithms (IP). This article investigates an alternative optimization approach based on block coordinate relaxation (BCR) for sets of basis functions that are the finite union of sets of orthonormal basis functions (e.g., wavelet packets). We show that the BCR algorithm is globally convergent, and empirically, the BCR algorithm is faster than the IP algorithm for a variety of signal denoising problems.     

On Nearest Neighbor Classification Using Adaptive Choice of k

Nearest neighbor classification is one of the simplest and popular methods for statistical pattern recognition. It classifies an observation x to the class, which is the most frequent in the neighborhood of x. The size of this neighborhood is usually determined by a predefined parameter k. Normally, one uses cross-validation techniques to estimate the optimum value of this parameter, and that estimated value is used for classifying all observations. However, in classification problems, in addition to depending on the training sample, a good choice of k depends on the specific observation to be classified. Therefore, instead of using a fixed value of k over the entire measurement space, a spatially adaptive choice of k may be more useful in practice. This article presents one such adaptive nearest neighbor classification technique, where the value of k is selected depending on the distribution of competing classes in the vicinity of the observation to be classified. The utility of the proposed method has been illustrated using some simulated examples and well-known benchmark datasets. Asymptotic optimality of its misclassification rate has been derived under appropriate regularity conditions.     

Un résultat de consistance pour des SVM fonctionnels par interpolation spline

This Note proposes a new methodology for function classification with Support Vector Machine (SVM). Rather than relying on projection on a truncated Hilbert basis as in our previous work, we use an implicit spline interpolation that allows us to compute SVM on the derivatives of the studied functions. To that end, we propose a kernel defined directly on the discretizations of the observed functions. We show that this method is universally consistent. To cite this article: N. Villa, F. Rossi, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Estimation of the misclassification error for multicategory support vector machine classification

The purpose of this paper is to provide an error analysis for the multicategory support vector machine （MSVM） classificaton problems. We establish the uniform convergency approach for MSVMs and estimate the misclassification error. The main difficulty we overcome here is to bound the offset vector. As a result, we confirm that the MSVM classification algorithm with polynomial kernels is always efficient when the degree of the kernel polynomial is large enough. Finally the rate of convergence and examples are given to demonstrate the main results.     

The k-Client Problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients.We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions.     

Dominators for Multiple-objective Quasiconvex Maximization Problems

In this paper we address the problem of finding a dominator for a multiple-objective maximization problem with quasiconvex functions. The one-dimensional case is discussed in some detail, showing how a Branch-and-Bound procedure leads to a dominator with certain minimality properties. Then, the well-known result stating that the set of vertices of a polytope S contains an optimal solution for single-objective quasiconvex maximization problems is extended to multiple-objective problems, showing that, under upper-semicontinuity assumptions, the set of (k 21)-dimensional faces is a dominator for k-objective problems. In particular, for biobjective quasiconvex problems on a polytope S, the edges of S constitute a dominator, from which a dominator with minimality properties can be extracted by Branch-and Bound methods.     

Fortran codes for computing the discrete Helmholtz integral operators

In this paper Fortran subroutines for the evaluation of the discrete form of the Helmholtz integral operators L _k, M _k, M _k ^t and N _k for two-dimensional, three-dimensional and three-dimensional axisymmetric problems are described. The subroutines are useful in the solution of Helmholtz problems via boundary element and related methods. The subroutines have been designed to be easy to use, reliable and efficient. The subroutines are also flexible in that the quadrature rule is defined as a parameter and the library functions (such as the Hankel, exponential and square root functions) are called from external routines. The subroutines are demonstrated on test problems arising from the solution of the Neumann problem exterior to a closed boundary via the Burton and Miller equation. This revised version was published online in August 2006 with corrections to the Cover Date.     

The closure operator in a multivalued logic based on functional equations

An operator of FE-closure is introduced on the set of functions of a multivalued logic based on the systems of functional equations. It is proved that, for every k ≥ 2, the FE-closure operator generates a finite classification on the set P _k of functions of k-valued logic. The least class in this classification is shown to be the class H _k of all homogeneous functions. Also a series of corollaries are obtained concerning the finite FE-generating sets in the FE-closed classes.     

Complete reducibility of subgroups of reductive algebraic groups over nonperfect fields III

Let G be a reductive group over a nonperfect field k. We study rationality problems for Serre’s notion of complete reducibility of subgroups of G. In our previous work, we constructed examples of subgroups H of G that are G-completely reducible but not G-completely reducible over k (and vice versa). In this article, we give a theoretical underpinning of those constructions. Then using Geometric Invariant Theory, we obtain a new result on the structure of G(k)-(and G-) orbits in an arbitrary affine G-variety. We discuss several related problems to complement the main results.     

Support vector machine classifiers with uncertain knowledge sets via robust optimization

In this article we study support vector machine (SVM) classifiers in the face of uncertain knowledge sets and show how data uncertainty in knowledge sets can be treated in SVM classification by employing robust optimization. We present knowledge-based SVM classifiers with uncertain knowledge sets using convex quadratic optimization duality. We show that the knowledge-based SVM, where prior knowledge is in the form of uncertain linear constraints, results in an uncertain convex optimization problem with a set containment constraint. Using a new extension of Farkas' lemma, we reformulate the robust counterpart of the uncertain convex optimization problem in the case of interval uncertainty as a convex quadratic optimization problem. We then reformulate the resulting convex optimization problems as a simple quadratic optimization problem with non-negativity constraints using the Lagrange duality. We obtain the solution of the converted problem by a fixed point iterative algorithm and establish the convergence of the algorithm. We finally present some preliminary results of our computational experiments of the method.     

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary (preemptive schedule). We consider both the sum-of-completion times measure, or the sum of the last color assigned to each vertex, as well as the more common makespan measure, or the number of colors used. In this paper, we study two fundamental classes of graphs: planar graphs and partial k-trees. For both classes, we give a polynomial time approximation scheme (PTAS) for the multicoloring sum, for both the preemptive and nonpreemptive cases. On the other hand, we show the problem to be strongly NP-hard on planar graphs, even in the unweighted case, known as the sum coloring problem. For a nonpreemptive multicoloring sum of partial k-trees, we obtain a fully polynomial time approximation scheme. This is based on a pseudo-polynomial time algorithm that holds for a general class of cost functions. Finally, we give a PTAS for the makespan of a preemptive multicoloring of partial k-trees that uses only O(log n) preemptions. These results are based on several properties of multicolorings and tools for manipulating them, which may be of more general applicability.     

Some Riemann boundary value problems in Clifford analysis

In this paper, we mainly study the R_m (m>0) Riemann boundary value problems for functions with values in a Clifford algebra C?(V_{3, 3}). We prove a generalized Liouville‐type theorem for harmonic functions and biharmonic functions by combining the growth behaviour estimates with the series expansions for k‐monogenic functions. We obtain the result under only one growth condition at infinity by using the integral representation formulas for harmonic functions and biharmonic functions. By using the Plemelj formula and the integral representation formulas, a more generalized Liouville theorem for harmonic functions and biharmonic functions are presented. Combining the Plemelj formula and the integral representation formulas with the above generalized Liouville theorem, we prove that the R_m (m>0) Riemann boundary value problems for monogenic functions, harmonic functions and biharmonic functions are solvable. Explicit representation formulas of the solutions are given. Copyright © 2009 John Wiley & Sons, Ltd.     

Smooth and Semismooth Newton Methods for Constrained Approximation and Estimation

In the article, we show that the constrained L ₂ approximation problem, the positive polynomial interpolation, and the density estimation problems can all be reformulated as a system of smooth or semismooth equations by using Lagrange duality theory. The obtained equations contain integral functions of the same form. The differentiability or (strong) semismoothness of the integral functions and the Hölder continuity of the Jacobian of the integral function were investigated. Then a globalized Newton-type method for solving these problems was introduced. Global convergence and numerical tests for estimating probability density functions with wavelet basis were also given. The research in this article not only strengthened the theoretical results in literatures but also provided a possibility for solving the probability density function estimation problem by Newton-type method.