Support Vector Machine Classifier (SVM)

Support Vector Machine (SVM) classification is among popular classification algorithms. It belongs to a family of generalized linear classification problems.

Operation

Computational methods

Programming Interface

Training

SMO

Thunder

train(…)

train_input

train_result

Inference

SMO

Thunder

infer(…)

infer_input

infer_result

Mathematical formulation

Training

Given \(n\) feature vectors \(x_1 = (x_{11}, \ldots, x_{1p}), \ldots, x_n = (x_{n1}, \ldots, x_{np})\) of size \(p\) and a vector of class labels \(y = (y_1, \ldots, y_n)\), where \(y_i \in \{-1, 1\}\) describes the class to which the feature vector \(x_i\) belongs, the problem is to build a two-class Support Vector Machine (SVM) classifier.

The SVM model is trained using the Sequential minimal optimization (SMO) method [Boser92]} for reduced to the solution of the quadratic optimization problem

\[\underset{\alpha }{\mathrm{min}}\frac{1}{2}{\alpha }^{T}Q\alpha -{e}^{T}\alpha\]

with \(0 \leq \alpha_i \leq C\), \(i = 1, \ldots, n\), \(y^T \alpha = 0\), where \(e\) is the vector of ones, \(C\) is the upper bound of the coordinates of the vector \(\alpha\), \(Q\) is a symmetric matrix of size \(n \times n\) with \(Q_{ij} = y_i y_j K(x_i, x_j)\), and \(K(x,y)\) is a kernel function.

Working subset of α updated on each iteration of the algorithm is based on the Working Set Selection (WSS) 3 scheme [Fan05]. The scheme can be optimized using one of these techniques or both:

  • Cache: the implementation can allocate a predefined amount of memory to store intermediate results of the kernel computation.

  • Shrinking: the implementation can try to decrease the amount of kernel related computations (see [Joachims99]).

The solution of the problem defines the separating hyperplane and corresponding decision function \(D(x)= \sum_{k} {y_k \alpha_k K(x_k, x)} + b\), where only those \(x_k\) that correspond to non-zero \(\alpha_k\) appear in the sum, and \(b\) is a bias. Each non-zero \(\alpha_k\) is called a classification coefficient and the corresponding \(x_k\) is called a support vector.

Training method: smo

In smo training method, all vectors from the training dataset are used for each iteration.

Training method: thunder

In thunder training method, the algorithm iteratively solves the convex optimization problem with the linear constraints by selecting the fixed set of active constrains (working set) and applying Sequential Minimal Optimization (SMO) solver to the selected subproblem. The description of this method is given in Algorithm [Wen2018].

Inference methods: smo and thunder

smo and thunder inference methods perform prediction in the same way:

Given the SVM classifier and \(r\) feature vectors \(x_1, \ldots, x_r\), the problem is to calculate the signed value of the decision function \(D(x_i)\), \(i=1, \ldots, r\). The sign of the value defines the class of the feature vector, and the absolute value of the function is a multiple of the distance between the feature vector and the separating hyperplane.

Examples

Batch Processing:

Programming Interface

All types and functions in this section are declared in the oneapi::dal::svm namespace and are available via inclusion of the oneapi/dal/algo/svm.hpp header file.

Descriptor

template<typename Task = task::by_default>
class descriptor_base

Properties

double c = 1.0

The upper bound in constraints of the quadratic optimization problem. \(C\).

Getter & Setter
double get_c() const
Invariants
c > 0
std::int64_t max_iteration_count = 100000

The maximum number of iterations \(T\).

Getter & Setter
std::int64_t get_max_iteration_count() const
Invariants
double accuracy_threshold = 0.0

The threshold \(\varepsilon\) for the stop condition.

Getter & Setter
double get_accuracy_threshold() const
Invariants
double cache_size = 200.0

The size of cache in megabytes for storing values of the kernel matrix.

Getter & Setter
double get_cache_size() const
Invariants
cache_size >= 0.0
double tau = 1e-6

The parameter of the WSS scheme \(\tau\).

Getter & Setter
double get_tau() const
Invariants
tau >= 0.0
bool shrinking = true

A flag that enables the use of a shrinking optimization technique. Used with oneapi::dal::svm::method::v1::thunder split-finding method only.

Getter & Setter
bool get_shrinking() const
template<typename Float = detail::descriptor_base<>::float_t, typename Method = detail::descriptor_base<>::method_t, typename Task = detail::descriptor_base<>::task_t, typename Kernel = detail::descriptor_base<>::kernel_t>
class descriptor
Template Parameters
  • Float – The floating-point type that the algorithm uses for intermediate computations. Can be float or double.

  • Method – Tag-type that specifies an implementation of algorithm. Can be method::v1::thunder or method::v1::smo.

  • Task – Tag-type that specifies the type of the problem to solve. Can be task::v1::classification.

Constructors

descriptor(const Kernel &kernel = kernel_t{})

Creates a new instance of the class with the given descriptor of the kernel function.

Public Methods

auto &set_c(double value)
auto &set_accuracy_threshold(double value)
auto &set_max_iteration_count(std::int64_t value)
auto &set_cache_size(double value)
auto &set_tau(double value)
auto &set_shrinking(bool value)

Properties

const Kernel &kernel

The descriptor of kernel function K(x,y). Can be linear_kernel::desc or rbf_kernel::desc.

Getter & Setter
const Kernel & get_kernel() const
auto & set_kernel(const Kernel &kernel)

Method tags

struct smo

Tag-type that denotes SMO computational method.

struct thunder

Tag-type that denotes Thunder computational method.

using by_default = thunder

Alias tag-type for Thunder computational method.

Task tags

struct classification

Tag-type that parameterizes entities that are used for solving classification problem.

using by_default = classification

Alias tag-type for classification task.

Model

template<typename Task = task::by_default>
class model
Template Parameters

Task – Tag-type that specifies the type of the problem to solve. Can be task::v1::classification.

Constructors

model()

Creates a new instance of the class with the default property values.

Properties

std::int64_t support_vector_count = 0

The number of support vectors.

Getter & Setter
std::int64_t get_support_vector_count() const
Invariants
const table &support_vectors = table{}

A \(nsv \times p\) table containing support vectors. Where \(nsv\) - number of support vectors.

Getter & Setter
const table & get_support_vectors() const
auto & set_support_vectors(const table &value)
const table &coeffs = table{}

A \(nsv \times 1\) table containing coefficients of Lagrange multiplier.

Getter & Setter
const table & get_coeffs() const
auto & set_coeffs(const table &value)
double bias = 0.0

The bias.

Getter & Setter
double get_bias() const
auto & set_bias(double value)
std::int64_t first_class_label = 0

The first unique value in class labels.

Getter & Setter
std::int64_t get_first_class_label() const
auto & set_first_class_label(std::int64_t value)
std::int64_t second_class_label = 0

The second unique value in class labels.

Getter & Setter
std::int64_t get_second_class_label() const
auto & set_second_class_label(std::int64_t value)

Training train(...)

Input

template<typename Task = task::by_default>
class train_input
Template Parameters

Task – Tag-type that specifies the type of the problem to solve. Can be task::v1::classification.

Constructors

train_input(const table &data, const table &labels, const table &weights = table{})

Creates a new instance of the class with the given data, labels and weights.

Properties

const table &data = table{}

The training set \(X\).

Getter & Setter
const table & get_data() const
auto & set_data(const table &value)
const table &labels = table{}

The vector of labels \(y\) for the training set \(X\).

Getter & Setter
const table & get_labels() const
auto & set_labels(const table &value)
const table &weights = table{}

The vector of weights \(w\) for the training set \(X\).

Getter & Setter
const table & get_weights() const
auto & set_weights(const table &value)

Result

template<typename Task = task::by_default>
class train_result
Template Parameters

Task – Tag-type that specifies the type of the problem to solve. Can be task::v1::classification.

Constructors

train_result()

Creates a new instance of the class with the default property values.

Properties

std::int64_t support_vector_count = 0

The number of support vectors.

Getter & Setter
std::int64_t get_support_vector_count() const
const model<Task> &model = model<Task>{}

The trained SVM model.

Getter & Setter
const model< Task > & get_model() const
auto & set_model(const model< Task > &value)
const table &support_vectors = table{}

A \(nsv \times p\) table containing support vectors, where \(nsv\) is the number of support vectors.

Getter & Setter
const table & get_support_vectors() const
auto & set_support_vectors(const table &value)
const table &support_indices = table{}

A \(nsv \times 1\) table containing support indices.

Getter & Setter
const table & get_support_indices() const
auto & set_support_indices(const table &value)
const table &coeffs = table{}

A \(nsv \times 1\) table containing coefficients of Lagrange multiplier.

Getter & Setter
const table & get_coeffs() const
auto & set_coeffs(const table &value)
double bias = 0.0

The bias.

Getter & Setter
double get_bias() const
auto & set_bias(double value)

Operation

template<typename Descriptor>
svm::train_result train(const Descriptor &desc, const svm::train_input &input)
Template Parameters

Descriptor – SVM algorithm descriptor svm::desc.

Preconditions
input.data.is_empty == false
input.labels.is_empty == false
input.labels.column_count == 1
input.data.row_count == input.labels.row_count

Inference infer(...)

Input

template<typename Task = task::by_default>
class infer_input
Template Parameters

Task – Tag-type that specifies the type of the problem to solve. Can be task::v1::classification.

Constructors

infer_input(const model<Task> &trained_model, const table &data)

Creates a new instance of the class with the given model and data property values.

Properties

const model<Task> &model = model<Task>{}

The trained SVM model.

Getter & Setter
const model< Task > & get_model() const
auto & set_model(const model< Task > &value)
const table &data = table{}

The dataset for inference \(X'\).

Getter & Setter
const table & get_data() const
auto & set_data(const table &value)

Result

template<typename Task = task::by_default>
class infer_result
Template Parameters

Task – Tag-type that specifies the type of the problem to solve. Can be task::v1::classification.

Constructors

infer_result()

Creates a new instance of the class with the default property values.

Properties

const table &labels = table{}

The \(n \times 1\) table with the predicted labels.

Getter & Setter
const table & get_labels() const
auto & set_labels(const table &value)
const table &decision_function = table{}

The \(n \times 1\) table with the predicted class decistion function for each observation.

Getter & Setter
const table & get_decision_function() const
auto & set_decision_function(const table &value)

Operation

template<typename Descriptor>
svm::infer_result infer(const Descriptor &desc, const svm::infer_input &input)
Template Parameters

Descriptor – SVM algorithm descriptor svm::desc.

Preconditions
input.data.is_empty == false