blob: 87880a9eea104259812b5ffaa1f51e9a6a492191 [file] [log] [blame]
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements. See the NOTICE file
distributed with this work for additional information
regarding copyright ownership. The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License. You may obtain a copy of the License at
Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
KIND, either express or implied. See the License for the
specific language governing permissions and limitations
under the License.
\subsubsection{Multi-class Support Vector Machines}
\noindent{\bf Description}
Support Vector Machines are used to model the relationship between a categorical
dependent variable y and one or more explanatory variables denoted X. This
implementation supports dependent variables that have domain size greater or
equal to 2 and hence is not restricted to binary class labels.
\noindent{\bf Usage}
\texttt{-f} \textit{path}/\texttt{m-svm.dml -nvargs}
\texttt{-f} \textit{path}/\texttt{m-svm-predict.dml -nvargs}
\noindent{\bf Arguments}
\item X: Location (on HDFS) containing the explanatory variables
in a matrix. Each row constitutes an example.
\item Y: Location (on HDFS) containing a 1-column matrix specifying
the categorical dependent variable (label). Labels are assumed to be
contiguously numbered from 1 $\ldots$ \#classes. Note that, this
argument is optional for prediction.
\item icpt (default: {\tt 0}): If set to 1 then a constant bias column
is added to X.
\item tol (default: {\tt 0.001}): Procedure terminates early if the reduction
in objective function value is less than tolerance times the initial objective
function value.
\item reg (default: {\tt 1}): Regularization constant. See details to find
out where lambda appears in the objective function. If one were interested
in drawing an analogy with C-SVM, then C = 2/lambda. Usually, cross validation
is employed to determine the optimum value of lambda.
\item maxiter (default: {\tt 100}): The maximum number of iterations.
\item model: Location (on HDFS) that contains the learnt weights.
\item Log: Location (on HDFS) to collect various metrics (e.g., objective
function value etc.) that depict progress across iterations while training.
\item fmt (default: {\tt text}): Specifies the output format. Choice of
comma-separated values (csv) or as a sparse-matrix (text).
\item scores: Location (on HDFS) to store scores for a held-out test set.
Note that, this is an optional argument.
\item accuracy: Location (on HDFS) to store the accuracy computed on a
held-out test set. Note that, this is an optional argument.
\item confusion: Location (on HDFS) to store the confusion matrix
computed using a held-out test set. Note that, this is an optional
\noindent{\bf Details}
Support vector machines learn a classification function by solving the
following optimization problem ($L_2$-SVM):
&\textrm{argmin}_w& \frac{\lambda}{2} ||w||_2^2 + \sum_i \xi_i^2\\
&\textrm{subject to:}& y_i w^{\top} x_i \geq 1 - \xi_i ~ \forall i
where $x_i$ is an example from the training set with its label given by $y_i$,
$w$ is the vector of parameters and $\lambda$ is the regularization constant
specified by the user.
To extend the above formulation (binary class SVM) to the multiclass setting,
one standard approache is to learn one binary class SVM per class that
separates data belonging to that class from the rest of the training data
(one-against-the-rest SVM, see C. Scholkopf, 1995).
To account for the missing bias term, one may augment the data with a column
of constants which is achieved by setting intercept argument to 1 (C-J Hsieh
et al, 2008).
This implementation optimizes the primal directly (Chapelle, 2007). It uses
nonlinear conjugate gradient descent to minimize the objective function
coupled with choosing step-sizes by performing one-dimensional Newton
minimization in the direction of the gradient.
\noindent{\bf Returns}
The learnt weights produced by m-svm.dml are populated into a matrix that
has as many columns as there are classes in the training data, and written
to file provided on HDFS (see model in section Arguments). The number of rows
in this matrix is ncol(X) if intercept was set to 0 during invocation and ncol(X) + 1
otherwise. The bias terms, if used, are placed in the last row. Depending on what
arguments are provided during invocation, m-svm-predict.dml may compute one or more
of scores, accuracy and confusion matrix in the output format specified.
%%\noindent{\bf See Also}
%%In case of binary classification problems, please consider using a binary class classifier
%%learning algorithm, e.g., binary class $L_2$-SVM (see Section \ref{l2svm}) or logistic regression
%%(see Section \ref{logreg}). To model the relationship between a scalar dependent variable
%%y and one or more explanatory variables X, consider Linear Regression instead (see Section
%%\ref{linreg-solver} or Section \ref{linreg-iterative}).
\noindent{\bf Examples}
hadoop jar SystemML.jar -f m-svm.dml -nvargs X=/user/biadmin/X.mtx
icpt=0 tol=0.001
reg=1.0 maxiter=100 fmt=csv
hadoop jar SystemML.jar -f m-svm-predict.dml -nvargs X=/user/biadmin/X.mtx
icpt=0 fmt=csv
\noindent{\bf References}
\item W. T. Vetterling and B. P. Flannery. \newblock{\em Conjugate Gradient Methods in Multidimensions in
Numerical Recipes in C - The Art in Scientific Computing.} \newblock W. H. Press and S. A. Teukolsky
(eds.), Cambridge University Press, 1992.
\item J. Nocedal and S. J. Wright. \newblock{\em Numerical Optimization.} \newblock Springer-Verlag, 1999.
\item C-J Hsieh, K-W Chang, C-J Lin, S. S. Keerthi and S. Sundararajan. \newblock {\em A Dual Coordinate
Descent Method for Large-scale Linear SVM.} \newblock International Conference of Machine Learning
(ICML), 2008.
\item Olivier Chapelle. \newblock{\em Training a Support Vector Machine in the Primal.} \newblock Neural
Computation, 2007.
\item B. Scholkopf, C. Burges and V. Vapnik. \newblock{\em Extracting Support Data for a Given Task.} \newblock International Conference on Knowledge Discovery and Data Mining (ICDM), 1995.