Support Vector Machines

Contents

• Regression Learning Function
• Classification Learning Function
• Novelty Detection Functions
• Prediction Functions
• Notes
• Examples
• Literature
• Related Topics

Warning

This MADlib method is still in early stage development. There may be some issues that will be addressed in a future version. Interface and implementation is subject to change.

Support vector machines (SVMs) and related kernel methods have been among the most popular and well-studied machine learning techniques of the past 15 years, with an amazing number of innovations and applications.

In a nutshell, an SVM model \(f(x)\) takes the form of

\[ f(x) = \sum_i \alpha_i k(x_i,x), \]

where each \( \alpha_i \) is a real number, each \( \boldsymbol x_i \) is a data point from the training set (called a support vector), and \( k(\cdot, \cdot) \) is a kernel function that measures how "similar" two objects are. In regression, \( f(\boldsymbol x) \) is the regression function we seek. In classification, \( f(\boldsymbol x) \) serves as the decision boundary; so for example in binary classification, the predictor can output class 1 for object \(x\) if \( f(\boldsymbol x) \geq 0 \), and class 2 otherwise.

In the case when the kernel function \( k(\cdot, \cdot) \) is the standard inner product on vectors, \( f(\boldsymbol x) \) is just an alternative way of writing a linear function

\[ f'(\boldsymbol x) = \langle \boldsymbol w, \boldsymbol x \rangle, \]

where \( \boldsymbol w \) is a weight vector having the same dimension as \( \boldsymbol x \). One of the key points of SVMs is that we can use more fancy kernel functions to efficiently learn linear models in high-dimensional feature spaces, since \( k(\boldsymbol x_i, \boldsymbol x_j) \) can be understood as an efficient way of computing an inner product in the feature space:

\[ k(\boldsymbol x_i, \boldsymbol x_j) = \langle \phi(\boldsymbol x_i), \phi(\boldsymbol x_j) \rangle, \]

where \( \phi(\boldsymbol x) \) projects \( \boldsymbol x \) into a (possibly infinite-dimensional) feature space.

There are many algorithms for learning kernel machines. This module implements the class of online learning with kernels algorithms described in Kivinen et al. [1]. It also includes the incremental gradient descent (IGD) method Feng et al. [3] for learning linear SVMs with the Hinge loss \(l(z) = \max(0, 1-z)\). See also the book Scholkopf and Smola [2] for more details of SVMs in general.

The IGD implementation is based on Bismarck project in University of Wisconsin (http://hazy.cs.wisc.edu/hazy/victor/bismarck/). The methods introduced in [1] are implemented according to their original descriptions, except that we only update the support vector model when we make a significant error. The original algorithms in [1] update the support vector model at every step, even when no error was made, in the name of regularization. For practical purposes, and this is verified empirically to a certain degree, updating only when necessary is both faster and better from a learning-theoretic point of view, at least in the i.i.d. setting.

Methods for classification, regression and novelty detection are available. Multiple instances of the algorithms can be executed in parallel on different subsets of the training data. The resultant support vector models can then be combined using standard techniques like averaging or majority voting.

Training data points are accessed via a table or a view. The support vector models can also be stored in tables for fast execution.

Regression Learning Function

Regression learning is achieved through the following function:

svm_regression( input_table,
                model_table,
                parallel,
                kernel_func,
                verbose DEFAULT false,
                eta DEFAULT 0.1,
                nu DEFAULT 0.005,
                slambda DEFAULT 0.05,
                kernel_param DEFAULT 1.0
              )

For classification and regression, the training table/view is expected to be of the following form (the array size of ind must not be greater than 102,400.):

{TABLE|VIEW} input_table (
    ...
    id INT,
    ind FLOAT8[],
    label FLOAT8,
    ...
)

For novelty detection, the label field is not required. Also note that the column names of input_table requires to be exactly the same as described above. This limitation will be removed when this module graduates from early development stage.

Classification Learning Function

Classification learning is achieved through the following two functions:

• Learn linear SVM(s) using IGD [3].

  lsvm_classification( input_table,
                       model_table,
                       parallel DEFAULT false,
                       verbose DEFAULT false,
                       eta DEFAULT 0.1,
                       reg DEFAULT 0.001,
                       max_iter DEFAULT 100
                     )
  

  Note that, as any gradient descent methods, IGD will converge with a greater eta (stepsize), thus faster, if the input training data is well-conditioned. We highly recommend user to perform data preparation, such that the mean value of each feature column is 0 and standard error is 1, and append an extra feature with constant value 1 for intercept term. We plan to provide a function for this when this module graduates from early stage development.
• Learn linear or non-linear SVM(s) using the method described in [1].

  svm_classification( input_table,
                      model_table,
                      parallel,
                      kernel_func,
                      verbose DEFAULT false,
                      eta DEFAULT 0.1,
                      nu DEFAULT 0.005,
                      kernel_param DEFAULT 1.0
                    )
  

Novelty Detection Function

Novelty detection is achieved through the following function:

svm_novelty_detection( input_table,
                       model_table,
                       parallel,
                       kernel_func,
                       verbose DEFAULT false,
                       eta DEFAULT 0.1,
                       nu DEFAULT 0.005,
                       kernel_param DEFAULT 1.0
                     )

Assuming the model_table parameter takes on value 'model', each learning function will produce two tables as output: 'model' and 'model_param'. The first contains the support vectors of the model(s) learned. The second contains the parameters of the model(s) learned, which include information like the kernel function used and the value of the intercept, if there is one.

Prediction Functions

• To make predictions on a single data point x using a single model learned previously, we use the function

  svm_predict_batch( input_table,
                     data_col,
                     id_col,
                     model_table,
                     output_table,
                     parallel
                   )
  

  If the parallel parameter is true, then each data point in the input table will have multiple predicted values corresponding to the number of models learned in
• If the model is produced by the lsvm_classification() function, use the following prediction function instead.

  lsvm_predict_batch( input_table,
                      data_col,
                      id_col,
                      model_table,
                      output_table,
                    )
  

• Note that, to make predictions on a subset of data points stored in a table, a separated view or table needs to be created ahead of time:

  -- create subset as a view
  CREATE VIEW subset AS SELECT * FROM input_table WHERE id <= 100;
  -- prediction on the subset
  SELECT svm_predict_batch('subset', 'ind', 'id',
      'svm_model', 'subset_svm_predict', false);
  -- prediction using linear SVMs
  SELECT lsvm_predict_batch('subset', 'ind', 'id',
      'lsvm_model', 'subset_lsvm_predict');
  

Notes

The kernel_func argument of svm_classification, svm_regression, and svm_novelty_detection can only accept a kernel function in the following form:

FLOAT8 kernel_function(FLOAT8[], FLOAT8[], FLOAT8)

The first two parameters are feature vectors, and the third one is a control parameter for the kernel function. The value of the control parameter must be set throught the kernel_param argument of svm_classification, svm_regression, and svm_novelty_detection.

Currently, three kernel functions have been implemented: linear or dot product (svm_dot), polynomial (svm_polynomial) and Gaussian (svm_gaussian) kernels. Note that for the dot product kernel, it actually only requires two FLOAT8[] parameters. To be compliant with the requirements for the kernel function, we have an overloaded version of svm_dot which accepts two FLOAT8[] and one FLOAT8 and returns a FLOAT8, but the FLOAT8 parameter is simply a placeholder and will be ignored.

With the HAWQ database, only the above pre-built kernel functions can be used. With the Greenplum database and PostgreSQL database, one can use any user-defined function as long as it conforms to the requirements for the kernel function.

Examples

As a general first step, prepare and populate an input table/view with the following structure:

CREATE TABLE/VIEW my_schema.my_input_table(
    id    INT,       -- point ID
    ind   FLOAT8[],  -- data point
    label FLOAT8     -- label of data point
);

The label field is not required for novelty detection.

Example usage for regression:

1. Randomly generate 1000 5-dimensional data labelled using the simple target function.

   t(x) = if x[5] = 10 then 50 else if x[5] = -10 then 50 else 0;
   

   and store that in the my_schema.my_train_data table as follows:

   SELECT madlib.svm_generate_reg_data(
       'my_schema.my_train_data', 1000, 5);
   

2. Learn a regression model and store the resultant model under the name 'myexp'.

   SELECT madlib.svm_regression('my_schema.my_train_data',
       'myexp1', false, 'madlib.svm_dot');
   

3. To learn multiple support vector models, we replace the learning step above by

   SELECT madlib.svm_regression('my_schema.my_train_data',
       'myexp2', true, 'madlib.svm_dot');
   

4. We can also predict the labels of data points stored in a table. For example, we can execute the following:

   -- prepare test data
   CREATE TABLE madlib.svm_reg_test AS
       SELECT id, ind
       FROM my_schema.my_train_data
       LIMIT 20;
   -- prediction using a single model
   SELECT madlib.svm_predict_batch('madlib.svm_reg_test', 'ind', 'id',
       'myexp1', 'madlib.svm_reg_output1', false);
   SELECT * FROM madlib.svm_reg_output1;
   -- prediction using multiple models
   SELECT madlib.svm_predict_batch('madlib.svm_reg_test', 'ind', 'id',
       'myexp2', 'madlib.svm_reg_output2', true);
   SELECT * FROM madlib.svm_reg_output2;
   

Example usage for classification:

1. Randomly generate training and testing data labelled by the simple target function.

   t(x) = if x[1] > 0 and  x[2] < 0 then 1 else -1;
   

   and store that in tables as follows:

   SELECT madlib.svm_generate_cls_data(
       'my_schema.my_train_data', 2000, 5);
   SELECT madlib.svm_generate_cls_data(
       'my_schema.my_test_data', 3000, 5);
   

2. Learn a classification model and store the resultant model the table 'myexpc'.

   SELECT madlib.svm_classification('my_schema.my_train_data',
       'myexpc', false, 'madlib.svm_dot');
   

3. Start using the model to predict the labels of testing data points.

   SELECT madlib.svm_predict_batch('my_schema.my_test_data', 'ind', 'id',
       'myexpc', 'my_schema.svm_cls_output1', false);
   

4. To learn multiple support vector models, replace the model-building and prediction steps above.

   -- training
   SELECT madlib.svm_classification('my_schema.my_train_data',
       'myexpc', true, 'madlib.svm_dot');
   -- predicting
   SELECT madlib.svm_predict_batch('my_schema.my_test_data', 'ind', 'id',
       'myexpc', 'my_schema.svm_cls_output1', true);
   

5. To learn a linear support vector model using IGD [3], replace the model-building and prediction steps.

   -- training
   SELECT madlib.lsvm_classification(
       'my_schema.my_train_data', 'my_lsvm');
   -- predicting
   SELECT madlib.lsvm_predict_batch('my_schema.my_test_data',
       'ind', 'id', 'my_lsvm', 'my_lsvm_predict');
   

Example usage for novelty detection:

1. Randomly generate 100 2-dimensional data (the normal cases) and store that in the my_schema.my_train_data table.

   SELECT madlib.svm_generate_nd_data(
       'my_schema.my_train_data', 100, 2);
   

2. Learning and predicting using a single novelty detection model:

   SELECT madlib.svm_novelty_detection( 'my_schema.my_train_data',
                                       'myexpnd',
                                       false,
                                       'madlib.svm_dot'
                                     );
   SELECT * FROM myexpnd;
   

3. Learning and predicting using multiple models can be done as follows:

   SELECT madlib.svm_novelty_detection( 'my_schema.my_train_data',
                                       'myexpnd',
                                       true,
                                       'madlib.svm_dot'
                                     );
   SELECT * FROM myexpnd;
   

Model cleanup: To drop all tables pertaining to the model, use:

SELECT svm_drop_model('model_table');

Literature

[1] Jyrki Kivinen, Alexander J. Smola, and Robert C. Williamson: Online Learning with Kernels, IEEE Transactions on Signal Processing, 52(8), 2165-2176, 2004.

[2] Bernhard Scholkopf and Alexander J. Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, 2002.

[3] X. Feng, A. Kumar, B. Recht, and C. Ré: Towards a unified architecture for in-RDBMS analytics, In SIGMOD Conference, 2012.

Related Topics

File online_sv.sql_in and lsvm.sql_in documenting the SQL functions.