Multicategory classification via discrete support vector machines

Discrete support vector machines (DSVM), originally proposed for binary classification problems, have been shown to outperform other competing approaches on well-known benchmark datasets. Here we address their extension to multicategory classification, by developing three different methods. Two of them are based respectively on one-against-all and round-robin classification schemes, in which a number of binary discrimination problems are solved by means of a variant of DSVM. The third method directly addresses the multicategory classification task, by building a decision tree in which an optimal split to separate classes is derived at each node by a new extended formulation of DSVM. Computational tests on publicly available datasets are then conducted to compare the three multicategory classifiers based on DSVM with other methods, indicating that the proposed techniques achieve significantly higher accuracies. This research was partially supported by PRIN grant 2004132117.     

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.     

Solving multi-level multi-objective linear programming problems through fuzzy goal programming approach

In this paper, two new algorithms are presented to solve multi-level multi-objective linear programming (ML-MOLP) problems through the fuzzy goal programming (FGP) approach. The membership functions for the defined fuzzy goals of all objective functions at all levels are developed in the model formulation of the problem; so also are the membership functions for vectors of fuzzy goals of the decision variables, controlled by decision makers at the top levels. Then the fuzzy goal programming approach is used to achieve the highest degree of each of the membership goals by minimizing their deviational variables and thereby obtain the most satisfactory solution for all decision makers.     

Multi-choice goal programming formulation based on the conic scalarizing function

The multi-choice goal programming allows the decision maker to set multi-choice aspiration levels for each goal to avoid underestimation of the decision. In this paper, we propose an alternative multi-choice goal programming formulation based on the conic scalarizing function with three contributions: (1) the alternative formulation allows the decision maker to set multi-choice aspiration levels for each goal to obtain an efficient solution in the global region, (2) the proposed formulation reduces auxiliary constraints and additional variables, and (3) the proposed model guarantees to obtain a properly efficient (in the sense of Benson) point. Finally, to demonstrate the usefulness of the proposed formulation, illustrative examples and test problems are included.     

Knowledge based proximal support vector machines

We propose a proximal version of the knowledge based support vector machine formulation, termed as knowledge based proximal support vector machines (KBPSVMs) in the sequel, for binary data classification. The KBPSVM classifier incorporates prior knowledge in the form of multiple polyhedral sets, and determines two parallel planes that are kept as distant from each other as possible. The proposed algorithm is simple and fast as no quadratic programming solver needs to be employed. Effectively, only the solution of a structured system of linear equations is needed.     

基于DC规划方法的稀疏临近支持向量机

为了提高临近支持向量机（PSVM）的数值表现,在PSVM的模型中引入了$\ell_0$-范数正则项,提出了稀疏临近支持向量机模型（SPSVM）,从而提高分类器的特征选择能力。然而带有$\ell_0$-范数正则项的问题往往是NP-难问题,为了克服这一问题,采用非凸连续函数近似$\ell_0$-范数,并通过适当的DC分解将问题转化成DC规划问题进行求解,同时还讨论了算法的收敛性。数值实验结果表明不论是在仿真数据还是在实际数据中,所提出的方法是比较有效稳定的。     

A practical weight sensitivity algorithm for goal and multiple objective programming

This paper presents a weight sensitivity algorithm that can be used to investigate a portion of weight space of interest to the decision maker in a goal or multiple objective programme. The preferential information required from the decision maker is an initial estimate of their starting solution, with an equal weights solution being used as a default if this is not available, and preference information that will define the portion of weight space on which the sensitivity analysis is to be conducted. The different types of preferential information and how they are incorporated by the algorithm are discussed. The output of the algorithm is a set of distinct solutions that characterise the portion of weight space searched. The possible different output requirements of decision makers are detailed in the context of the algorithm.The methodology is demonstrated on two examples, one hypothetical and the other relating to predicting cinema-going behaviour. Conclusions and avenues for future research are given.     

Binary fuzzy goal programming

Goal programming is an important technique for solving many decision/management problems. Fuzzy goal programming involves applying the fuzzy set theory to goal programming, thus allowing the model to take into account the vague aspirations of a decision-maker. Using preference-based membership functions, we can define the fuzzy problem through natural language terms or vague phenomena. In fact, decision-making involves the achievement of fuzzy goals, some of them are met and some not because these goals are subject to the function of environment/resource constraints. Thus, binary fuzzy goal programming is employed where the problem cannot be solved by conventional goal programming approaches. This paper proposes a new idea of how to program the binary fuzzy goal programming model. The binary fuzzy goal programming model can then be solved using the integer programming method. Finally, an illustrative example is included to demonstrate the correctness and usefulness of the proposed model.     

A reference model for customer-centric data mining with support vector machines

Supervised classification is an important part of corporate data mining to support decision making in customer-centric planning tasks. The paper proposes a hierarchical reference model for support vector machine based classification within this discipline. The approach balances the conflicting goals of transparent yet accurate models and compares favourably to alternative classifiers in a large-scale empirical evaluation in real-world customer relationship management applications. Recent advances in support vector machine oriented research are incorporated to approach feature, instance and model selection in a unified framework.     

A chance constraints goal programming model for the advertising planning problem

This paper presents a model which has been designed to decide the number of advertisement in different advertising media and the optimal allocation of the budget assigned to the different media. The main objective of this problem is to maximize the reach to the desired section of people for different media within their maximum allowable budget without violating the max and min number of advertisement goals. The media have been considered as different newspapers and different channels in Televisions. Here in this article the model has been formulated in such a way that the advertisement should reach to those who are suitable for the product instead of going to those section who are not considered suitable for the product as well. A chance constrained goal programming model has been designed after considering the parameter corresponding to reach for different media as random variables. The random variables in this case has been considered as values which have known mean and standard deviations. A case for an upcoming institution who are interested to advertise for its two years Post Graduate Diploma in Management (PGDM) programme to the different newspapers and television channels has been designed to illustrate the solution methodology.     

A memetic approach to construct transductive discrete support vector machines

Transductive learning involves the construction and application of prediction models to classify a fixed set of decision objects into discrete groups. It is a special case of classification analysis with important applications in web-mining, corporate planning and other areas. This paper proposes a novel transductive classifier that is based on the philosophy of discrete support vector machines. We formalize the task to estimate the class labels of decision objects as a mixed integer program. A memetic algorithm is developed to solve the mathematical program and to construct a transductive support vector machine classifier, respectively. Empirical experiments on synthetic and real-world data evidence the effectiveness of the new approach and demonstrate that it identifies high quality solutions in short time. Furthermore, the results suggest that the class predictions following from the memetic algorithm are significantly more accurate than the predictions of a CPLEX-based reference classifier. Comparisons to other transductive and inductive classifiers provide further support for our approach and suggest that it performs competitive with respect to several benchmarks.     

Learning errors of linear programming support vector regression

In this paper, we give several results of learning errors for linear programming support vector regression. The corresponding theorems are proved in the reproducing kernel Hilbert space. With the covering number, the approximation property and the capacity of the reproducing kernel Hilbert space are measured. The obtained result (Theorem 2.1) shows that the learning error can be controlled by the sample error and regularization error. The mentioned sample error is summarized by the errors of learning regression function and regularizing function in the reproducing kernel Hilbert space. After estimating the generalization error of learning regression function (Theorem 2.2), the upper bound (Theorem 2.3) of the regularized learning algorithm associated with linear programming support vector regression is estimated.     

A fuzzy goal programming approach to multi-objective optimization problem with priorities

In goal programming problem, the general equilibrium and optimization are often two conflicting factors. This paper proposes a generalized varying-domain optimization method for fuzzy goal programming (FGP) incorporating multiple priorities. According to the three possible styles of the objective function, the varying-domain optimization method and its generalization are proposed. This method can generate the results consistent with the decision-maker (DM)’s expectation, that the goal with higher priority may have higher level of satisfaction. Using this new method, it is a simple process to balance between the equilibrium and optimization, and the result is the consequence of a synthetic decision between them. In contrast to the previous method, the proposed method can make that the higher priority achieving the higher satisfactory degree. To get the global solution of the nonlinear nonconvex programming problem resulting from the original problem and the varying-domain optimization method, the co-evolutionary genetic algorithms (GAs), called GENOCOPIII, is used instead of the SQP method. In this way the DM can get the optimum of the optimization problem. We demonstrate the power of this proposed method by illustrative examples.     

Revised multi-choice goal programming

Chang [C.-T. Chang, Multi-choice goal programming, Omega, The Inter. J. Manage. Sci. 35 (2007) 389–396] has recently proposed a new method namely multi-choice goal programming (MCGP) for multi-objective decision problems. The multi-choice goal programming allows the decision maker to set multi-choice aspiration levels for each goal to avoid underestimation of the decision. However, to express the multi-choice aspiration levels, multiplicative terms of binary variables are involved in their model. This leads to difficult implementation and it is not easily understood by industrial participants. In this paper, we propose an alternative method to formulate the multi-choice aspiration levels with two contributions: (1) the alternative approach does not involve multiplicative terms of binary variables, this leads to more efficient use of MCGP and is easily understood by industrial participants, and (2) the alternative approach represents a linear form of MCGP which can easily be solved by common linear programming packages, not requiring the use of integer programming packages. In addition, a new concept of constrained MCGP is introduced for constructing the relationships between goals in this paper. Finally, to demonstrate the usefulness of the proposed method, an illustrate example is included.     

Using support vector machines to learn the efficient set in multiple objective discrete optimization

We propose using support vector machines (SVMs) to learn the efficient set in multiple objective discrete optimization (MODO). We conjecture that a surface generated by SVM could provide a good approximation of the efficient set. As one way of testing this idea, we embed the SVM-approximated efficient set information into a Genetic Algorithm (GA). This is accomplished by using a SVM-based fitness function that guides the GA search. We implement our SVM-guided GA on the multiple objective knapsack and assignment problems. We observe that using SVM improves the performance of the GA compared to a benchmark distance based fitness function and may provide competitive results.     

An efficient method for solving linear goal programming problems

This note proposes a solution algorithm for linear goal programming problems. The proposed method simplifies the traditional solution methods. Also, the proposed method is computationally efficient.     

Support vector machines regression with unbounded sampling

Uniform boundedness of output variables is a standard assumption in most theoretical analysis of regression algorithms. This standard assumption has recently been weaken to a moment hypothesis in least square regression (LSR) setting. Although there has been a large literature on error analysis for LSR under the moment hypothesis, very little is known about the statistical properties of support vector machines regression with unbounded sampling. In this paper, we fill the gap in the literature. Without any restriction on the boundedness of the output sampling, we establish an ad hoc convergence analysis for support vector machines regression under very mild conditions.     

Support vector machines as Bayes' classifiers

We reformulate the problem of determining support vectors directly as an application of Bayes' classifiers rather than as the dual program to a binary geometric separation problem. The primary purpose of the reformulation is to create a simpler exposition of the support vector machines technique. A secondary advantage is that it immediately and naturally applies to multi-class classification problems where the kernel function can be normalized as a density.     

Optimal kernel selection in twin support vector machines

In twin support vector machines (TWSVMs), we determine pair of non-parallel planes by solving two related SVM-type problems, each of which is smaller than the one in a conventional SVM. However, similar to other classification methods, the performance of the TWSVM classifier depends on the choice of the kernel. In this paper we treat the kernel selection problem for TWSVM as an optimization problem over the convex set of finitely many basic kernels, and formulate the same as an iterative alternating optimization problem. The efficacy of the proposed classification algorithm is demonstrated with some UCI machine learning benchmark datasets.     

Interval goal programming for S-shaped penalty function

The approach of Jones and Tamiz (1995) [Jones, D.F., Tamiz, M., 1995. Expanding the flexibility of goal programming via preference modeling techniques. Omega 23, 41–48] has been accepted as the most efficient approach in the field of interval goal programming (IGP). Although several modifications to the original approach have been proposed recently [Vitoriano, B., Romero, C., 1999. Extended interval goal programming. Journal of the Operational Research Society 50, 1280–1283; Chang, C.-T., 2006. Mixed binary interval goal programming. Journal of the Operational Research Society 35, 389–396], all of them cannot formulate IGP with an S-shaped penalty function. In order to improve the utility of IGP, we extend the model of Chang (2006) [Chang, C.-T., 2006. Mixed binary interval goal programming. Journal of the Operational Research Society 35, 389–396] to be able to model an S-shaped penalty function. The newly formulated model is more concise and compact than the method of Li and Yu (2000) and it can easily be applied to a decision problem with the S-shaped penalty function. Finally, an illustrative example (i.e. how to build an appropriate E-learning system) is included for demonstrating the usefulness of the proposed model.