Self-adaptive support vector machines: modelling and experiments

Method  In this paper, we introduce a bi-level optimization formulation for the model and feature selection problems of support vector machines (SVMs). A bi-level optimization model is proposed to select the best model, where the standard convex quadratic optimization problem of the SVM training is cast as a subproblem. Feasibility  The optimal objective value of the quadratic problem of SVMs is minimized over a feasible range of the kernel parameters at the master level of the bi-level model. Since the optimal objective value of the subproblem is a continuous function of the kernel parameters, through implicity defined over a certain region, the solution of this bi-level problem always exists. The problem of feature selection can be handled in a similar manner. Experiments and results  Two approaches for solving the bi-level problem of model and feature selection are considered as well. Experimental results show that the bi-level formulation provides a plausible tool for model selection.     

On qualitative robustness of support vector machines

Support vector machines (SVMs) have attracted much attention in theoretical and in applied statistics. The main topics of recent interest are consistency, learning rates and robustness. We address the open problem whether SVMs are qualitatively robust. Our results show that SVMs are qualitatively robust for any fixed regularization parameter λ. However, under extremely mild conditions on the SVM, it turns out that SVMs are not qualitatively robust any more for any null sequence λ_n, which are the classical sequences needed to obtain universal consistency. This lack of qualitative robustness is of a rather theoretical nature because we show that, in any case, SVMs fulfill a finite sample qualitative robustness property.For a fixed regularization parameter, SVMs can be represented by a functional on the set of all probability measures. Qualitative robustness is proven by showing that this functional is continuous with respect to the topology generated by weak convergence of probability measures. Combined with the existence and uniqueness of SVMs, our results show that SVMs are the solutions of a well-posed mathematical problem in Hadamard’s sense.     

A review on consistency and robustness properties of support vector machines for heavy-tailed distributions

Support vector machines (SVMs) belong to the class of modern statistical machine learning techniques and can be described as M-estimators with a Hilbert norm regularization term for functions. SVMs are consistent and robust for classification and regression purposes if based on a Lipschitz continuous loss and a bounded continuous kernel with a dense reproducing kernel Hilbert space. For regression, one of the conditions used is that the output variable Y has a finite first absolute moment. This assumption, however, excludes heavy-tailed distributions. Recently, the applicability of SVMs was enlarged to these distributions by considering shifted loss functions. In this review paper, we briefly describe the approach of SVMs based on shifted loss functions and list some properties of such SVMs. Then, we prove that SVMs based on a bounded continuous kernel and on a convex and Lipschitz continuous, but not necessarily differentiable, shifted loss function have a bounded Bouligand influence function for all distributions, even for heavy-tailed distributions including extreme value distributions and Cauchy distributions. SVMs are thus robust in this sense. Our result covers the important loss functions ${\epsilon}$ -insensitive for regression and pinball for quantile regression, which were not covered by earlier results on the influence function. We demonstrate the usefulness of SVMs even for heavy-tailed distributions by applying SVMs to a simulated data set with Cauchy errors and to a data set of large fire insurance claims of Copenhagen Re.     

Simultaneous classification and feature selection via convex quadratic programming with application to HIV-associated neurocognitive disorder assessment

Support vector machines (SVMs), that utilize a mixture of the _L1$L_1$-norm and the _L2$L_2$-norm penalties, are capable of performing simultaneous classification and selection of highly correlated features. These SVMs, typically set up as convex programming problems, are re-formulated here as simple convex quadratic minimization problems over non-negativity constraints, giving rise to a new formulation – the pq-SVM method. Solutions to our re-formulation are obtained efficiently by an extremely simple algorithm. Computational results on a range of publicly available datasets indicate that these methods allow greater classification accuracy in addition to selecting groups of highly correlated features. These methods were also compared on a new dataset assessing HIV-associated neurocognitive disorder in a group of 97 HIV-infected individuals.     

Genetic programming for feature construction and selection in classification on high-dimensional data

Classification on high-dimensional data with thousands to tens of thousands of dimensions is a challenging task due to the high dimensionality and the quality of the feature set. The problem can be addressed by using feature selection to choose only informative features or feature construction to create new high-level features. Genetic programming (GP) using a tree-based representation can be used for both feature construction and implicit feature selection. This work presents a comprehensive study to investigate the use of GP for feature construction and selection on high-dimensional classification problems. Different combinations of the constructed and/or selected features are tested and compared on seven high-dimensional gene expression problems, and different classification algorithms are used to evaluate their performance. The results show that the constructed and/or selected feature sets can significantly reduce the dimensionality and maintain or even increase the classification accuracy in most cases. The cases with overfitting occurred are analysed via the distribution of features. Further analysis is also performed to show why the constructed feature can achieve promising classification performance.     

Column continuous transition functions

A column continuous transition function is by definition a standard transition function P(t) whose every column is continuous for t?0 in the norm topology of bounded sequence space l_∞. We will prove that it has a stable q-matrix and that there exists a one-to-one relationship between column continuous transition functions and increasing integrated semigroups on l_∞. Using the theory of integrated semigroups, we give some necessary and sufficient conditions under which the minimal q-function is column continuous, in terms of its generator (of the Markov semigroup) as well as its q-matrix. Furthermore, we will construct all column continuous Q-functions for a conservative, single-exit and column bounded q-matrix Q. As applications, we find that many interesting continuous-time Markov chains (CTMCs), say Feller-Reuter-Riley processes, monotone processes, birth-death processes and branching processes, etc., have column continuity.     

New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains

We consider a multi-period problem of fair transfer prices and inventory holding policies in two enterprise supply chains. This problem was formulated as a mixed integer non-linear program by Gjerdrum et al. (Eur J Oper Res 143:582–599, 2002). Existing global optimization methods to solve this problem are computationally expensive. We propose a continuous approach based on difference of convex functions (DC) programming and DC Algorithms (DCA) for solving this combinatorial optimization problem. The problem is first reformulated as a DC program via an exact penalty technique. Afterward, DCA, an efficient local approach in non-convex programming framework, is investigated to solve the resulting problem. For globally solving this problem, we investigate a combined DCA-Branch and Bound algorithm. DCA is applied to get lower bounds while upper bounds are computed from a relaxation problem. The numerical results on several test problems show that the proposed algorithms are efficient: DCA provides a good integer solution in a short CPU time although it works on a continuous domain, and the combined DCA-Branch and Bound finds an \(\epsilon \) -optimal solution for large-scale problems in a reasonable time.     

On conditions for optimality of the nonlinearl 1 problem

The purpose of this paper is to present necessary and sufficient conditions for optimality in the nonlinearl ₁ problem. Furthermore, the relationship of thel ₁ problem and the Pietrzykowski's approach to solve the nonlinear programming problem is discussed in detail.     

On the chromatic number for a set of metric spaces

We study the problem of finding the chromatic number of a metric space with a forbidden distance. Using the linear-algebraic technique in combinatorics and convex optimization methods, we obtain a set of new estimates and observe the change of the asymptotic lower bound for the chromatic number of Euclidean space under the continuous change of the metric from l ₁ to l ₂.     

Perturbing the Dual Feasible Region for Solving Convex Quadratic Programs

A dual l _p-norm perturbation approach is introduced for solving convex quadratic programming problems. The feasible region of the Lagrangian dual program is approximated by a proper subset that is defined by a single smooth convex constraint involving the l _p-norm of a vector measure of constraint violation. It is shown that the perturbed dual program becomes the dual program as p and, under some standard conditions, the optimal solution of the perturbed dual program converges to a dual optimal solution. A closed-form formula that converts an optimal solution of the perturbed dual program into a feasible solution of the primal convex quadratic program is also provided. Such primal feasible solutions converge to an optimal primal solution as p. The proposed approach generalizes the previously proposed primal perturbation approach with an entropic barrier function. Its theory specializes easily for linear programming.     

Finite Families of lp-Spaces and Multirectangular Characteristics

Under consideration are finite families of Banach spaces with unconditional basis. The problem of isomorphic classification of families is studied together with the related problem of uniqueness of an unconditional basis for a family. Complete solution of both problems for l ₁- and c ₀-families is given by using some geometric invariants combined with the corresponding results for l ₁ and c ₀.     

A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.     

The mean uncertainty and distance dimension of multidimensional cantorian spaces

Several ways of describing the internal structure of infinite point sets and determining a corresponding average dimension are outlined. Possible relevance to discretisation of quantum space-time are discussed. Finally, a method for determining the average internal distance between different Cantor points is proposed.The main conclusion is that a micro-scale Cantorian space-time may be based on an average Cantorian distance d_l⁽⁰⁾ ⋍ 0.629, while the smooth space-time is retrieved when d_l⁽⁰⁾ → 0.5, which means d_l⁽⁰⁾ tends towards the average distance of a continuous smooth line at a vanishing resolution. This correspond to the case when space is viewed from very far, at the macro-scale of classical physics.     

Dual gauge programs,with applications to quadratic programming and the minimum-norm problem

A gauge functionf(·) is a nonnegative convex function that is positively homogeneous and satisfiesf(0)=0. Norms and pseudonorms are specific instances of a gauge function. This paper presents a gauge duality theory for a gauge program, which is the problem of minimizing the value of a gauge functionf(·) over a convex set. The gauge dual program is also a gauge program, unlike the standard Lagrange dual. We present sufficient conditions onf(·) that ensure the existence of optimal solutions to the gauge program and its dual, with no duality gap. These sufficient conditions are relatively weak and are easy to verify, and are independent of any qualifications on the constraints. The theory is applied to a class of convex quadratic programs, and to the minimuml _p norm problem. The gauge dual program is shown to provide a smaller duality than the standard dual, in a certain sense discussed in the text.     

Portfolio selection under downside risk measures and cardinality constraints based on DC programming and DCA

In this paper, we consider the case of downside risk measures with cardinality and bounding constraints in portfolio selection. These constraints limit the amount of capital to be invested in each asset as well as the number of assets composing the portfolio. While the standard Markowitz’s model is a convex quadratic program, this new model is a NP-hard mixed integer quadratic program. Realizing the computational intractability for this class of problems, especially large-scale problems, we first reformulate it as a DC program with the help of exact penalty techniques in Difference of Convex functions (DC) programming and then solve it by DC Algorithms (DCA). To check globality of computed solutions, a global method combining the local algorithm DCA with a Branch-and-Bound algorithm is investigated. Numerical simulations show that DCA is an efficient and promising approach for the considered problem.      

SVM classification for imbalanced data sets using a multiobjective optimization framework

Classification of imbalanced data sets in which negative instances outnumber the positive instances is a significant challenge. These data sets are commonly encountered in real-life problems. However, performance of well-known classifiers is limited in such cases. Various solution approaches have been proposed for the class imbalance problem using either data-level or algorithm-level modifications. Support Vector Machines (SVMs) that have a solid theoretical background also encounter a dramatic decrease in performance when the data distribution is imbalanced. In this study, we propose an L ₁-norm SVM approach that is based on a three objective optimization problem so as to incorporate into the formulation the error sums for the two classes independently. Motivated by the inherent multi objective nature of the SVMs, the solution approach utilizes a reduction into two criteria formulations and investigates the efficient frontier systematically. The results indicate that a comprehensive treatment of distinct positive and negative error levels may lead to performance improvements that have varying degrees of increased computational effort.     

A discrete particle swarm optimization method for feature selection in binary classification problems

This paper investigates the feature subset selection problem for the binary classification problem using logistic regression model. We developed a modified discrete particle swarm optimization (PSO) algorithm for the feature subset selection problem. This approach embodies an adaptive feature selection procedure which dynamically accounts for the relevance and dependence of the features included the feature subset. We compare the proposed methodology with the tabu search and scatter search algorithms using publicly available datasets. The results show that the proposed discrete PSO algorithm is competitive in terms of both classification accuracy and computational performance.     

The critical Fujita exponent for a diffusion equation with a potential term

We study the initial-boundary-value problem of the diffusion equation u _t = Δu ^m ? V (x)u ^m + u ^p in a conelike domain D = [1,∞) × Ω, where V (x) ~ ω ₂ |x| ^?2 with ω ₂ > 0. Let ω ₁ denote the smallest Dirichlet eigenvalue for the Laplace–Beltrami operator on Ω, and let l denote the positive root of l ² + (n ? 2)l = ω ₁ + ω ₂. We prove that if m < p ≤ m + 2/(n + l), then the problem has no global nonnegative solutions for any nonnegative u ₀ unless u ₀ = 0; if p > m + 2/(n + l), then the problem has global solutions for some \( {u_0}\gneq 0 \) .     

A continuous DC programming approach to the strategic supply chain design problem from qualified partner set

We present a new continuous approach based on the DC (difference of convex functions) programming and DC algorithms (DCA) to the problem of supply chain design at the strategic level when production of a new market opportunity has to be launched among a set of qualified partners. A well known formulation of this problem is the mixed integer linear program. In this paper, we reformulate this problem as a DC program by using an exact penalty technique. The proposed algorithm is a combination of DCA and Branch and Bound scheme. It works in a continuous domain but provides mixed integer solutions. Numerical simulations on many empirical data sets show the efficiency of our approach with respect to the standard Branch and Bound algorithm.