Lagrangian support vector regression via unconstrained convex minimization

Abstract

In this paper, a simple reformulation of the Lagrangian dual of the 2-norm support vector regression (SVR) is proposed as an unconstrained minimization problem. This formulation has the advantage that its objective function is strongly convex and further having only $m$ variables, where $m$ is the number of input data points. The proposed unconstrained Lagrangian SVR (ULSVR) is solvable by computing the zeros of its gradient. However, since its objective function contains the non-smooth ‘plus’ function, two approaches are followed to solve the proposed optimization problem: (i) by introducing a smooth approximation, generate a slightly modified unconstrained minimization problem and solve it; (ii) solve the problem directly by applying generalized derivative. Computational results obtained on a number of synthetic and real-world benchmark datasets showing similar generalization performance with much faster learning speed in accordance with the conventional SVR and training time very close to least squares SVR clearly indicate the superiority of ULSVR solved by smooth and generalized derivative approaches.

Introduction

Support Vector Machines (SVMs) are state-of-the-art machine learning techniques based on Vapnik and Chervonenkis structural risk minimization principle (Vapnik, 2000). They are computationally powerful tools showing better generalization ability compared to other machine learning methods on a wide variety of real-world problems like face detection (Osuna, Freund, & Girosi, 1997), gene prediction (Guyon, Weston, Barnhill, & Vapnik, 2002), text categorization (Joachims, Ndellec, & Rouveriol, 1998) and image segmentation (Chen & Wang, 2005). It is well known that SVM formulation (Cristianini and Shawe-Taylor, 2000, Vapnik, 2000) can be posed as a quadratic programming problem (QPP) with linear inequality constraints which is a convex programming problem having a unique optimal solution. Although SVM has been initially proposed for classification, later it has been extended to regression (Vapnik, 2000).

The function approximation by regression is of great importance in many fields of research such as bioinformatics, control theory, economics, information science and signal processing. The main challenge in developing a useful regression model is to capture accurately the underlying functional relationship between the given inputs and their output values. Once the resulting model is obtained it can be used as a tool for analysis, simulation and prediction.

For a given set of data points, support vector regression (SVR) aims at determining a linear regressor where the input data are either considered in the original pattern space itself or taken into a higher dimensional feature space. With the introduction of $\epsilon$-insensitive error loss function proposed by Vapnik (2000), SVR has emerged as a powerful paradigm of choice for regression because of its improved generalization performance in comparison to other popular machine learning methods like artificial neural networks.

Considering the minimization of the square of 2-norm of the slack variables instead of the usual 1-norm and maximizing the margin with respect to both the orientation and the relative location to the origin of the bounding parallel planes, Mangasarian and Musicant, 2001a, Mangasarian and Musicant, 2001b studied “equivalent” SVM formulations for classification problems resulting in positive-definite dual problems having only non-negative constraints. For the formulation of SVM as an unconstrained optimization problem whose objective function becomes not twice differentiable, a smoothing technique is adopted to derive a new SVM formulation called Smooth SVM (SSVM) in Lee and Mangasarian (2001). As its extension to $\epsilon$-insensitive error loss based SVR, termed Smooth SVR (SSVR), we refer the reader to Lee, Hsieh, and Huang (2005). Also, on a finite Newton method of solution for SVM for classification with generalized Hessian approach, see Fung and Mangasarian (2003) and further on its extension to SVR, the interested reader is referred to Balasundaram and Kapil (2011). In addition, for the extension of the Active set SVM (ASVM) proposed for the classification (Mangasarian & Musicant, 2001b) to SVR, we refer Musicant and Feinberg (2004). For a review on optimization techniques used for training SVMs, see Shawe-Taylor and Sun (2011). Finally on the interesting work on multitask learning and multiview learning methods as extension of kernel based methods, we refer Ji and Sun (2013), Sun (2011) and Xie and Sun (2012).

It is well-known that the conventional $\epsilon$-insensitive SVR is formulated as a convex quadratic minimization problem having $2m$ nonnegative variables and $2m$ linear inequality constraints whereas 2-norm SVR introduces only $2m$ linear inequality constraints, where $m$ is the number of training points. In either case, more variables and constraints enlarge the problem size and therefore increase in the computational cost for solving the regression problem. Recently, a new nonparallel plane regressor termed as twin SVR (TSVR) is proposed in Peng (2010a) wherein a pair of QPPs, each having $m$ number of constraints, is solved instead of solving a single QPP having $2m$ constraints as in the conventional SVR which makes TSVR works faster than SVR.

In our approach, the 2-norm SVR in dual is reformulated as a single, unconstrained minimization problem having only $m$ variables. We term such reformulation as unconstrained Lagrangian SVR (ULSVR). The proposed ULSVR model can be solved using gradient based methods. However, since the objective function contains a term having non-smooth ‘plus’ function, two approaches are taken to solve the minimization problem: (i) two smooth approximation functions, studied in Lee and Mangasarian (2001) and Peng (2010b), are introduced and their slightly modified unconstrained minimization problems are solved; (ii) directly solve the minimization problem by applying generalized derivative. In both the approaches, by applying simple iterative methods, the zeros of the gradient are computed.

Finally, for the study of Lagrangian and implicit Lagrangian SVR solved using block matrices with the advantage of reduced training cost, see the work of Balasundaram and Kapil, 2010, Balasundaram and Kapil, 2011.

The effectiveness of the proposed approach in formulating ULSVR problem and solving it using various iterative methods is demonstrated by performing numerical experiments on a number of synthetic and real-world benchmark datasets and comparing their results with conventional SVR and least squares SVR. Comparable generalization performance in solving ULSVR with less computational training time clearly indicates its suitability on problems of interest.

The paper is organized as follows. In Section  2, formulations of the conventional and 2-norm SVR are introduced. Section  3 briefly dwells on least squares SVR. The proposed ULSVR formulation having only $m$ variables and various algorithms used for solving it are described in Section  4. On a number of synthetic and real-world datasets numerical experiments are performed and the results obtained by ULSVR are compared with SVR and least squares SVR in Section  5. Finally we conclude our work in Section  6.

In this work, all vectors are considered as column vectors. For any two vectors $x,y$ in ${\Re }^n$, their inner product will be denoted by $x^{t}y$ where $x^t$ is the transpose of $x$. When $x$ is orthogonal to $y$ we write $x\perp y$. The 2-norm of a vector $x$ will be denoted by, $\left|\right|x\left|\right|$. For $x={(x_1,\dots ,x_n)}^t\in {\Re }^n$, the plus function $x_{+}$ is defined as: ${\left(x_{+}\right)}_i=max\{0,x_i\}$, where $i=1,\dots ,n$. Further we define the step function $x_{\ast }$ as: ${\left(x_{\ast }\right)}_i=1$ for $x_i>0$, ${\left(x_{\ast }\right)}_i=0$ if $x_i<0$ and ${\left(x_{\ast }\right)}_i=0.5$ when $x_i=0$. The identity matrix of appropriate size is denoted by $I$ and the diagonal matrix of order $n$ whose diagonal elements become the components of the vector $x\in {\Re }^n$ by diag(x). The column vector of ones of dimension $m$ is denoted by $e$. If $f$ is a real valued function of the variable $x={(x_1,\dots ,x_n)}^t\in {\Re }^n$ then its gradient vector and Hessian matrix are defined by, $\nabla f={(\frac{\partial f}{\partial x_1},\dots ,\frac{\partial f}{\partial x_n})}^t$ and ${\nabla }^{2}f={({\partial }^{2}f/\partial x_i\partial x_j)}_{i,j=1,\dots ,n}$ respectively.