Extra material: Support vector machines with conic optimization#

In this notebook we come back to the concept of training support vector machines as we did in the first SVM notebook.

Here we write the SVM models using explicit conic constraints, which MOSEK handles directly.

The first part of this notebook shall consist of data imports and other things that need no further explanation. Please move directly to the cell entitled “Conic optimization model” if you already have the data loaded from there.

Here we absorb the intercept \(b\) into the augmented weight vector \(\bar{w}=(b,w)\). The objective below regularizes this whole vector, including \(b\). This changes the training model from the first SVM notebook, which leaves the intercept unpenalized; it is more than a change of notation.

Preamble: Install Pyomo and a solver#

This notebook uses MOSEK when run locally and installs Ipopt through IDAES on Google Colab. MOSEK uses the cone structure directly; Ipopt solves the equivalent smooth continuous constraints. The dense radial-basis-function model can exhaust the memory of Ipopt’s MA27 linear solver, so the Ipopt path explicitly selects MA57 from the IDAES distribution. If your Ipopt build does not include MA57, select mumps instead; it can take longer for this dense model. Another option is to install and license MOSEK and select mosek_direct.

Each model checks solver termination before constructing a classifier. The Ipopt options guide describes the linear solver setting; the IDAES binary guide describes the available solver installation.

The IDAES build includes HSL linear solvers: HSL, a collection of Fortran codes for large-scale scientific computation. See https://www.hsl.rl.ac.uk/.

See Solvers used in this book for installation, licensing and the differences between solver interfaces.

import sys, os

if 'google.colab' in sys.modules:
    %pip install idaes-pse --pre >/dev/null 2>/dev/null
    !idaes get-extensions --to ./bin 
    os.environ["PATH"] += os.pathsep + os.path.abspath("bin")
    solver = "ipopt"
else:
    solver = "mosek_direct"

import pyomo.kernel as pmo
import pyomo.environ as pyo 
SOLVER = pmo.SolverFactory(solver)

assert SOLVER.available(), f"Solver {solver} is not available."

if solver == "ipopt":
    # Use MA57 for the dense kernel model and keep the coefficient bounds exact.
    SOLVER.options["linear_solver"] = "ma57"
    SOLVER.options["bound_relax_factor"] = 0

The data set#

The following data set contains data from a collection of known genuine and known counterfeit banknote specimens. The data includes four continuous statistical measures obtained from the wavelet transform of banknote images named “variance”, “skewness”, “curtosis”, and “entropy”, and a binary variable named “class” which is 0 if genuine and 1 if counterfeit.

https://archive.ics.uci.edu/ml/datasets/banknote+authentication

Read data#

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split

# Use the repository data locally and the same fixed snapshot on Colab.
from pathlib import Path

data_file = Path("../../datasets/data_banknote_authentication.txt")
data_url = (
    "https://raw.githubusercontent.com/mobook/MO-book/"
    "6e636bc8db144fbc17f39e4eb4543508adba85f9/"
    "datasets/data_banknote_authentication.txt"
)
df = pd.read_csv(data_file if data_file.is_file() else data_url, header=None)
df.columns = ["variance", "skewness", "curtosis", "entropy", "class"]
df.name = "Banknotes"

Select features and training sets#

Following customary practices, we divide the data set into a training set used to train the classifier, and a testing set that will be used to evaluate the performance of the classifier. In addition, we select a two-dimensional subset of the features to enable plotting of the results for exposition. Since our definition of a positive outcome corresponds to detecting a genuine banknote, we rescale the “class” feature to have values of 1 for genuine banknotes and -1 for counterfeit banknotes.

We use random_state=0 so that all formulations are trained and evaluated on the same reproducible split.

# create training and test sets
df_train, df_test = train_test_split(df, test_size=0.2, random_state=0)

# select training features
features = ["variance", "skewness"]

# separate into features and outputs
X_train = df_train[features]
y_train = 1 - 2 * df_train["class"]

# separate into features and outputs
X_test = df_test[features]
y_test = 1 - 2 * df_test["class"]

The following cell presents a simple function to create a scatter plot for a labeled 2D set of features. The function assigns default labels and colors, and passes along other keyword arguments.

def scatter_labeled_data(X, y, labels=["+1", "-1"], colors=["g", "r"], **kwargs):
    # Prepend keyword arguments for all scatter plots
    kw = {"x": 0, "y": 1, "kind": "scatter", "alpha": 0.4}
    kw.update(kwargs)

    # Ignore warnings from matplotlib scatter plot
    import warnings

    with warnings.catch_warnings():
        warnings.filterwarnings("ignore")
        kw["ax"] = X[y > 0].plot(**kw, c=colors[0], label=labels[0])
        X[y < 0].plot(**kw, c=colors[1], label=labels[1])


# plot training and test sets in two axes
fig, ax = plt.subplots(1, 2, figsize=(10, 4))
scatter_labeled_data(
    X_train,
    y_train,
    labels=["genuine", "counterfeit"],
    ax=ax[0],
    title="Training Set",
)
scatter_labeled_data(
    X_test,
    y_test,
    labels=["genuine", "counterfeit"],
    ax=ax[1],
    title="Test Set",
)
../../_images/9642e84f1347e0d5f64b78cb67559fcb8e40e8baf214c98a9ac57ee6fb8449cf.png

Performance metrics#

The accuracy score alone is not always a reliable metric for evaluating the performance of binary classifiers. For instance, when one outcome is significantly more frequent than the other, a classifier that always predicts the more common outcome without regard to the feature vector can achieve a very high accuracy score while being completely wrong on the less common outcome.

Moreover, in many applications, the consequences of a false positive can differ from those of a false negative. For these reasons, we seek a more comprehensive set of metrics to compare binary classifiers.

  • Sensitivity of a classifier measures how many of the actually positive items in the dataset have been labelled as positive.

  • Precision, on the other hand, counts how many of the items marked as positive are actually positive.

A detailed discussion on this topic recommends the Matthews correlation coefficient (MCC) as a reliable performance measure for binary classifiers.

The code below demonstrates an example of a function that evaluates the performance of a binary classifier and returns the Matthews correlation coefficient as its output.

We assign a zero decision score to the positive class, so every observation is counted. When a denominator vanishes, the corresponding sensitivity, precision or MCC is reported as zero; an empty evaluation set is rejected.

def classify(scores):
    """Assign an exact zero score to the positive class (+1)."""
    scores = np.asarray(scores, dtype=float)
    if not np.isfinite(scores).all():
        raise ValueError("Classifier scores must be finite.")
    return np.where(scores >= 0, 1, -1)


def validate(y_true, y_pred, verbose=True):
    # Align labelled observations before counting; arrays retain positional order.
    if isinstance(y_true, pd.Series) and isinstance(y_pred, pd.Series):
        if not y_true.index.is_unique or not y_pred.index.is_unique:
            raise ValueError("Observation labels must be unique.")
        if (len(y_true) != len(y_pred)
                or not y_true.index.isin(y_pred.index).all()):
            raise ValueError("True and predicted labels must identify the same observations.")
        y_pred = y_pred.reindex(y_true.index)
    # Count every observation, including an exact decision-boundary tie.
    y_true = np.asarray(y_true)
    y_pred = np.asarray(y_pred)
    if y_true.ndim != 1 or y_pred.shape != y_true.shape or y_true.size == 0:
        raise ValueError("Supply equally sized, nonempty one-dimensional arrays.")
    if not np.isin(y_true, [-1, 1]).all():
        raise ValueError("True labels must be -1 or +1.")
    y_pred = classify(y_pred)
    true_positives = int(np.count_nonzero((y_true > 0) & (y_pred > 0)))
    false_negatives = int(np.count_nonzero((y_true > 0) & (y_pred < 0)))
    false_positives = int(np.count_nonzero((y_true < 0) & (y_pred > 0)))
    true_negatives = int(np.count_nonzero((y_true < 0) & (y_pred < 0)))
    total = y_true.size

    # Calculate the Matthews correlation coefficient (MCC)
    mcc_numerator = (true_positives * true_negatives) - (
        false_positives * false_negatives
    )
    mcc_denominator = np.sqrt(
        (true_positives + false_positives)
        * (true_positives + false_negatives)
        * (true_negatives + false_positives)
        * (true_negatives + false_negatives)
    )
    mcc = mcc_numerator / mcc_denominator if mcc_denominator else 0.0

    if verbose:
        print(f"Matthews correlation coefficient (MCC) = {mcc:0.3f}")

        # report sensitivity and precision, and accuracy
        sensitivity = true_positives / (true_positives + false_negatives) if true_positives + false_negatives else 0.0
        precision = true_positives / (true_positives + false_positives) if true_positives + false_positives else 0.0
        accuracy = (true_positives + true_negatives) / total

        print(f"Sensitivity = {100 * sensitivity: 0.1f}%")
        print(f"Precision = {100 * precision: 0.1f}%")
        print(f"Accuracy = {100 * accuracy: 0.1f}%")

        # Display the binary confusion matrix
        confusion_matrix = pd.DataFrame(
            [
                [true_positives, false_negatives],
                [false_positives, true_negatives],
            ],
            index=["Actual Positive", "Actual Negative"],
            columns=["Predicted Positive", "Predicted Negative"],
        )
        display(confusion_matrix)

    return mcc

Conic optimization model#

Primal formulation#

As already explained in the first support vector machine notebook, the standard formulation of a linear support vector machine uses training sets with \(p\)-element feature vectors \(x_i\in\mathbb{R}^p\) along with classification labels for those vectors, \(y_i = \pm 1\). A classifier is defined by two parameters: a weight vector \(w\in\mathbb{R}^p\) and a bias term \(b\in\mathbb{R}\)

\[ \begin{align*} y^{pred} & = \text{sgn}(w^\top x + b) \end{align*} \]

Throughout, we take \(\operatorname{sgn}(0)=+1\): a point exactly on the decision boundary is assigned to the positive class, as in the code below.

We train the classifier by developing and solving an optimization model for the values of \(w\) and \(b\). For the formulation used here, we introduce an augmented feature vector \(\bar{x} = (1, x) \in \mathbb{R}^{p+1}\) and an augmented weight vector \(\bar{w} = (b, w) \in \mathbb{R}^{p+1}\) so the classifier can be presented as

\[ \begin{align*} y^{pred} & = \text{sgn}(\bar{w}^\top \bar{x}) \end{align*} \]

Given a value of \(\bar{w}\), there is a family of hyperplanes in \(\mathbb{R}^{p+1}\) orthogonal to \(\bar{w}\). A separating hyperplane, if one exists, separates all data points with \(y_i = 1\) from those with \(y_i = -1\). The signed distance from \(\bar{x}_i\) to the separating hyperplane in the augmented space, measured in the direction \(\bar{w}\), is

\[\frac{\bar{w}^\top \bar{x}_i}{\|\bar{w}\|}\]

If a separating hyperplane exists, then we can choose the norm of \(\bar{w}\) so that a hard-margin classifier exists for the training set \((\bar{x}_i, y_i)\) where

\[ \begin{align*} y_i \bar{w}^\top \bar{x}_i & \geq 1 & \forall i\in\{1,2,\dots,n\} \end{align*} \]

Otherwise, if a separating hyperplane does not exist, we introduce non-negative slack variables \(z_i\) to relax the constraints and settle for a soft-margin classifier

\[ \begin{align*} y_i \bar{w}^\top \bar{x}_i & \geq 1 - z_i& \forall i\in\{1,2,\dots,n\} \end{align*} \]

For \(c>0\), at an optimum the slack is the hinge loss \(z_i=\max\{0,1-y_i\bar{w}^\top\bar{x}_i\}\). It measures a margin violation: a correctly classified point inside the margin can also have positive loss, while \(z_i>1\) implies misclassification. The objective balances the squared norm of the weights against the sum of these losses. This leads to the optimization problem

\[\begin{split} \begin{align*} \min \quad & \frac{1}{2} \|\bar{w}\|_2^2 + \frac{c}{n}\sum_{i=1}^n z_i \\ \text{s.t.} \quad & z_i \geq 1 - y_i \bar{w}^\top \bar{x}_i & \forall i\in\{1,2,\dots,n\} \\ & z_i \geq 0 & \forall i\in\{1,2,\dots,n\} \end{align*} \end{split}\]

Here \(\frac{1}{2}\|\bar{w}\|_2^2=\frac{1}{2}(b^2+\|w\|_2^2)\) penalizes both the intercept and the feature weights. Stationarity with respect to \(b\) gives \(b=\sum_i\alpha_i y_i\), rather than the dual constraint \(\sum_i\alpha_i y_i=0\) obtained with an unpenalized intercept. The dual below therefore has no such equality constraint. Choosing larger values of \(c\) puts more weight on reducing hinge loss relative to regularization. This can lead to larger weights \(\bar{w}\) and a greater risk of over-fitting the training data.

To simplify the presentation of the model, we introduce an \(n \times (p+1)\) matrix \(F\) constructed from the training data

\[\begin{split} \begin{align} F & = \begin{bmatrix} y_1\bar{x}_1^\top \\ y_2\bar{x}_2^\top \\ \vdots \\ y_n\bar{x}_n^\top \end{bmatrix} \end{align} \end{split}\]

Next we introduce a rotated quadratic cone defined as

\[\mathcal{Q}^m_r = \{u\in\mathbb{R}^m | 2u_1u_2 \geq u_3^2 + \cdots + u_m^2,\ u_1, u_2 \geq 0 \}\]

and an auxiliary decision variable \(r\) where

\[2 r \geq \|\bar{w}\|_2^2 = \bar{w}_1^2 + \bar{w}_2^2 + \cdots + \bar{w}_{p+1}^2\]

With these additional components, the primal problem is now a conic optimization problem ready for implementation with the Pyomo Kernel Library and MOSEK conic solver.

\[\begin{split} \begin{align*} \min \quad & r + \frac{c}{n} 1^\top z\\ \text{s.t.}\quad & (r, 1, \bar{w}) \in \mathcal{Q}_r^{3 + p} \\ & z + F \bar{w} \geq 1 \\ & z \geq 0 & z\in\mathbb{R}^n \\ & \bar{w}\in\mathbb{R}^{p+1},\quad r\in\mathbb{R} \\ \end{align*} \end{split}\]

Like for the previous case, the Pyomo implementation is a “factory” function that returns a linear SVM.

# Linear Support Vector Machine (SVM) class
class LinearSvm:
    # Initialize the Linear SVM with weights and bias
    def __init__(self, w, b):
        self.w = pd.Series(w)
        self.b = float(b)

    # Call method to compute the decision function
    def __call__(self, X):
        return pd.Series(classify(X.dot(self.w) + self.b), index=X.index)

    # Representation method for the Linear SVM class
    def __repr__(self):
        return f"LinearSvm(w = {self.w.to_dict()}, b = {self.b})"


def conicSvmFactory(X, y, c=1):
    # create data matrix F
    n, p = X.shape
    F = np.array(
        [y.iloc[i] * np.append(1, X.iloc[i, :].to_numpy()) for i in range(n)]
    )  # Appending 1's to features

    # create model block
    m = pmo.block()

    # decision variables
    m.r = pmo.variable()
    m.w = pmo.variable_list([pmo.variable() for i in range(p + 1)])
    m.z = pmo.variable_list([pmo.variable(lb=0) for i in range(n)])

    # objective
    m.primal = pmo.objective(expr=m.r + (c / n) * sum(m.z))

    # constraints
    m.qr = pmo.conic.rotated_quadratic.as_domain(m.r, 1, m.w)
    m.d = pmo.constraint_list(
        [
            pmo.constraint(
                body=m.z[i] + sum(F[i, j] * m.w[j] for j in range(p + 1)), lb=1
            )
            for i in range(n)
        ]
    )

    # solve
    results = SOLVER.solve(m)
    pyo.assert_optimal_termination(results)

    # return svm
    b = m.w[0]()
    w = pd.Series({k: m.w[j + 1]() for j, k in enumerate(X.columns)})

    return LinearSvm(w, b)


svm_v2 = conicSvmFactory(X_train, y_train, c=10)
print(svm_v2.w)
print(svm_v2.b)
variance    0.554456
skewness    0.151651
dtype: float64
-0.2086569246539999

The following cell will reveal the performance of this standard SVM.

def scatter_comparison(X, y, y_pred):
    xmin, ymin = X.min()
    xmax, ymax = X.max()
    xlim = [xmin - 0.05 * (xmax - xmin), xmax + 0.05 * (xmax - xmin)]
    ylim = [ymin - 0.05 * (ymax - ymin), ymax + 0.05 * (ymax - ymin)]

    # Plot training and test sets
    labels = ["genuine", "counterfeit"]
    fig, ax = plt.subplots(1, 2, figsize=(10, 4))
    scatter_labeled_data(
        X, y, labels, ["g", "r"], ax=ax[0], xlim=xlim, ylim=ylim, title="Actual"
    )
    scatter_labeled_data(
        X,
        y_pred,
        labels,
        ["c", "m"],
        ax=ax[1],
        xlim=xlim,
        ylim=ylim,
        title="Prediction",
    )

    # Plot actual positives and actual negatives
    fig, ax = plt.subplots(1, 2, figsize=(10, 4))
    scatter_labeled_data(
        X[y > 0],
        y_pred[y > 0],
        ["true positive", "false negative"],
        ["c", "m"],
        xlim=xlim,
        ylim=ylim,
        ax=ax[0],
        title="Actual Positives",
    )
    scatter_labeled_data(
        X[y < 0],
        y_pred[y < 0],
        ["false positive", "true negative"],
        ["c", "m"],
        xlim=xlim,
        ylim=ylim,
        ax=ax[1],
        title="Actual Negatives",
    )


y_pred = svm_v2(X_test)
validate(y_test, y_pred)
scatter_comparison(X_test, y_test, y_pred)
Matthews correlation coefficient (MCC) = 0.762
Sensitivity =  92.4%
Precision =  87.9%
Accuracy =  88.4%
Predicted Positive Predicted Negative
Actual Positive 145 12
Actual Negative 20 98
../../_images/b9dc95ad63a5379b882966907ded352c0a4b64c3b063e248a785d26e5e95734e.png ../../_images/a2270c6260adc423315aeb8ee305177a50060f7def0a38d86aff37da34507317.png

Dual formulation#

As we already know, the dual of our problem shall be given by

\[\begin{split} \begin{align*} \min \quad & \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_i y_j ( \bar{x}_i^\top \bar{x}_j ) - \sum_{i=1}^n \alpha_i \\ \text{s.t.}\quad & \alpha_i \in \left[0, \frac{c}{n}\right] & i = 1, \dots, n. \\ \end{align*} \end{split}\]

The symmetric \(n \times n\) Gram matrix is defined as

\[\begin{split} G = \begin{bmatrix} (y_1\bar{x}_1^\top)(y_1\bar{x}_1) & \dots & (y_1\bar{x}_1^\top)(y_n\bar{x}_n) \\ \vdots & \ddots & \vdots \\ (y_n\bar{x}_n^\top)(y_1\bar{x}_1) & \dots & (y_n\bar{x}_n^\top)(y_n\bar{x}_n) \end{bmatrix} \end{split}\]

where each entry is the dot product of two vectors \((y_i\bar{x}_i), (y_j\bar{x}_j) \in \mathbb{R}^{p+1}\).

Compared to the primal, the dual formulation appears to have reduced the number of decision variables from \(n + p + 1\) to \(n\). But this has come with the penalty of introducing a dense matrix with \(n^2\) coefficients and potential processing time of order \(n^3\). For large training sets where \(n\sim 10^4-10^6\) or even larger, this becomes a prohibitively expensive calculation. In addition, the Gram matrix will be rank deficient for cases \(p+1 < n\).

Reformulating the dual problem as a conic optimization problem eliminates the need to compute and store the full Gram matrix \(G\). The reformulation begins by using the \(n \times (p+1)\) matrix \(F\) previously introduced in the primal problem:

\[\begin{split} F = \begin{bmatrix} y_1 \bar{x}_1^\top \\ y_2 \bar{x}_2^\top \\ \vdots \\ y_n \bar{x}_n^\top \end{bmatrix} \end{split}\]

Then \(G = FF^\top\) and the optimization problem becomes

\[\begin{split} \begin{align*} \min\quad & \frac{1}{2} \alpha^\top F F^\top \alpha - 1^\top \alpha \\ \text{s.t.}\quad & 0 \leq \alpha \leq \frac{c}{n} & \alpha\in\mathbb{R}^n \\ \end{align*} \end{split}\]

We introduce an additional decision variable \(r \geq 0\) to specify rotated quadratic cones. Let \(z = F^\top\alpha\), then

\[\alpha^\top F F^\top \alpha \leq 2 r \iff z^\top z \leq 2 r \iff (r, 1, z) \in \mathcal{Q}_r^{3 + p}\]

The result is a conic optimization problem for the dual coefficients \(\alpha\) and auxiliary variables \(r\) and \(z\).

\[\begin{split} \begin{align*} \min \quad & r - 1^\top \alpha\\ \text{s.t.} \quad & (r, 1, z) \in \mathcal{Q}_r^{3 + p} & r\in\mathbb{R} \\ & z = F^\top \alpha & z\in\mathbb{R}^{p+1} \\ & 0 \leq \alpha \leq \frac{c}{n} & \alpha\in\mathbb{R}^n \\ \end{align*} \end{split}\]

The solution to the dual formulation provides an alternative expression for the resulting support vector machine. Let \(\mathcal{SV}\) represent the set of support vectors, which can be implemented as the set of indices for which \(\alpha_i > 0\). The SVM can be expressed as either

\[ \begin{align} y^{pred} & = \text{sgn}\left( \bar{w}^\top \bar{x} \right)\quad \text{where}\quad \bar{w} = \sum_{i\in\mathcal{SV}} \alpha_i y_i \bar{x}_i \end{align} \]

or, more directly, as

\[ \begin{align} y^{pred} & = \text{sgn}\left( \sum_{i\in\mathcal{SV}} \alpha_i y_i \bar{x}_i^\top \bar{x} \right) \end{align} \]

The first formulation is a computationally efficient implementation of a linear SVM, and is used in the following Pyomo implementation. The second formulation, however, provides additional insight into how an SVM works, and is the basis for important generalizations of SVM including the kernelized SVM discussed below. The intercept has not disappeared: it is the first coordinate of \(\bar{w}\) and is recovered from the dual coefficients as \(b=\sum_i\alpha_i y_i\).

The following code implements the above SVM dual formulation.

Pyomo implementation#

def conicDualSVMFactory(X, y, c=1):
    n, p = X.shape
    F = np.array(
        [y.iloc[i] * np.append(1, X.iloc[i, :].to_numpy()) for i in range(n)]
    )  # Appending 1's to features

    m = pmo.block()

    # decision variables
    m.r = pmo.variable()
    m.a = pmo.variable_list([pmo.variable(lb=0, ub=c / n) for i in range(n)])
    m.z = pmo.variable_list([pmo.variable() for i in range(p + 1)])

    # objective
    m.o = pmo.objective(expr=m.r - sum(m.a))

    # constraints
    m.d = pmo.constraint_list(
        [
            pmo.constraint(body=sum(F[i, j] * m.a[i] for i in range(n)) - m.z[j], rhs=0)
            for j in range(p + 1)
        ]
    )
    m.q = pmo.conic.rotated_quadratic.as_domain(m.r, 1, m.z)

    # solve
    results = SOLVER.solve(m)
    pyo.assert_optimal_termination(results)

    # Use a relative tolerance only to color the support-vector plot.
    support_tol = 1e-3 * c / n
    S = [i for i in range(n) if m.a[i]() > support_tol]

    # create and return linear SVM
    w_bar = sum(m.a[i]() * F[i, :] for i in range(n))
    w = pd.Series({k: w_bar[j + 1] for j, k in enumerate(X.columns)})
    b = w_bar[0]

    y_support = pd.Series([1 if i in S else -1 for i in range(n)], index=X.index)
    scatter_labeled_data(
        X,
        y_support,
        colors=["b", "y"],
        labels=["Support Vector", ""],
        title="Support Vectors",
    )

    return LinearSvm(w, b)


svm_v3 = conicDualSVMFactory(X_train, y_train, c=10)
print(svm_v3.w, svm_v3.b)
variance    0.554456
skewness    0.151651
dtype: float64 -0.20865692461693444
../../_images/cdb78ec44b718b7721ceede308ccd419088c05c4efae4b9c687e82b9a01ffcb0.png

The following cell implements the above conic dual formulation and should obtain exactly the same accuracy results.

y_pred = svm_v3(X_test)
validate(y_test, y_pred)
scatter_comparison(X_test, y_test, y_pred)
Matthews correlation coefficient (MCC) = 0.762
Sensitivity =  92.4%
Precision =  87.9%
Accuracy =  88.4%
Predicted Positive Predicted Negative
Actual Positive 145 12
Actual Negative 20 98
../../_images/b9dc95ad63a5379b882966907ded352c0a4b64c3b063e248a785d26e5e95734e.png ../../_images/a2270c6260adc423315aeb8ee305177a50060f7def0a38d86aff37da34507317.png

Kernelized SVM#

Nonlinear feature spaces#

A linear SVM uses a linear decision boundary. A soft-margin model can accommodate data that are not perfectly linearly separable. Nonlinear decision boundaries can be obtained by mapping the feature vector to nonlinear features:

\[ \bar{x} \rightarrow \phi(\bar{x}) \]

where \(\phi(\bar{x})\) is a function mapping \(\bar{x}\) into a higher dimensional “feature space”. That is, \(\phi : \mathbb{R}^{p + 1} \rightarrow \mathbb{R}^d\) where \(d \geq p +1 \). The additional dimensions may include features such as powers of the terms in \(x\), or products of those terms, or other types of nonlinear transformations. In this way, the SVM has more ‘room to play’ in order to try to separate one point from another.

Corresponding to such a transformed vector, we have a binary classification tool given by

\[ y^{pred} = \text{sgn} \left( w^\top \phi(\bar{x}) \right). \]

The dual follows the penalized-intercept linear formulation above in this notebook, with \(\bar{x}\) replaced by \(\phi(\bar{x})\). The regularizer includes every feature coefficient, so there is no separate unpenalized intercept and no equality \(\sum_i\alpha_i y_i=0\). We obtain:

\[\begin{split} \begin{align*} \min \ & \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_i y_j \phi(\bar{x}_i)^\top \phi(\bar{x}_j) - \sum_{i=1}^n \alpha_i \\ \text{s. t.}\quad & \alpha_i \in \left[0, \frac{c}{n}\right] & i = 1, \dots, n \\ \end{align*} \end{split}\]

The kernel trick#

If you look at the optimization problem above and the corresponding classifier tool, this is an interesting situation where the separating hyperplane is embedded in a high dimensional space of nonlinear features determined by the mapping \(\phi(\bar{x})\), but all we need to train the classifier and to use the classifier are the inner products \(\phi(\bar{x}_i)^\top\phi(\bar{x}_j)\) and \(\phi(\bar{x}_i)^\top\phi(\bar{x})\), rather than the ‘raw’ \(\phi(\bar{x}_i)\) and \(\phi(\bar{x})\) values. If we had a function \(K(\bar{x}, \bar{z})\) that returned the value \(\phi(\bar{x})^\top\phi(\bar{z})\) then we would never need to actually compute \(\phi(\bar{x})\), \(\phi(\bar{z})\) or their inner product.

Mercer’s theorem turns the analysis on its head by specifying conditions under which a function \(K(\bar{x}, \bar{z})\) can be expressed as an inner product for some \(\phi(\bar{x})\). If \(K(\bar{x}, \bar{z})\) is symmetric (i.e., \(K(\bar{x}, \bar{z}) = K(\bar{z}, \bar{x})\)), and if the Gram matrix constructed for any collection of points \(\bar{x}_1, \bar{x}_2, \ldots, \bar{x}_n\)

\[\begin{split} \begin{bmatrix} K(\bar{x}_1, \bar{x}_1) & \dots & K(\bar{x}_1, \bar{x}_n) \\ \vdots & \ddots & \vdots \\ K(\bar{x}_n, \bar{x}_1) & \dots & K(\bar{x}_n, \bar{x}_n) \end{bmatrix} \end{split}\]

is positive semidefinite, then there is some \(\phi(\bar{x})\) for which \(K(\bar{x}, \bar{z})\) is an inner product. We call such functions kernels. The practical consequence is that we can train and implement nonlinear classifiers using kernels without ever needing to compute the higher dimensional features. This remarkable result is called the “kernel trick”.

Implementation#

To take advantage of the kernel trick, we assume an appropriate kernel \(K(\bar{x}, \bar{z})\) has been identified, then replace all instances of \(\phi(\bar{x}_i)^\top \phi(\bar{x})\) with the kernel. The “kernelized” SVM is then given by the solution to

\[\begin{split} \begin{align*} \min \ & \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(\bar{x}_i, \bar{x}_j) - \sum_{i=1}^n \alpha_i \\ \text{s. t.}\quad & \alpha_i \in \left[0, \frac{c}{n}\right] & i = 1, \dots, n \\ \end{align*} \end{split}\]

where the resulting classifier is given by

\[y^{pred} = \text{sgn} \left( \sum_{i=1}^n \alpha_i y_i K(\bar{x}_i, \bar{x}) \right)\]

We define the \(n\times n\) symmetric positive semidefinite Gram matrix

\[\begin{split} G = \begin{bmatrix} y_1 y_1 K(\bar{x}_1, \bar{x}_1) & \dots & y_1 y_n K(\bar{x}_1, \bar{x}_n) \\ \vdots & \ddots & \vdots \\ y_n y_1 K(\bar{x}_n, \bar{x}_1) & \dots & y_n y_n K(\bar{x}_n, \bar{x}_n) \end{bmatrix} \end{split}\]

We factor \(G = FF^\top\) where \(F\) has dimensions \(n \times q\) and where \(q\) is the rank of \(G\). This factorization is not unique. As demonstrated in the Python code below, one suitable factorization is the spectral factorization \(G = U\Lambda U^T\) where \(\Lambda\) is a \(q\times q\) diagonal matrix of non-zero eigenvalues, and \(U\) is an \(n\times q\) matrix with orthonormal columns such that \(U^\top U = I_q\). Then

\[F = U\Lambda^{1/2}\]

Once this factorization is complete, the optimization problem for the kernelized SVM is the same as for the linear SVM in the dual formulation

\[\begin{split} \begin{align*} \min\quad & \frac{1}{2} \alpha^\top F F^\top \alpha - 1^\top \alpha \\ \text{s.t.}\quad & 0 \leq \alpha \leq \frac{c}{n} & \alpha\in\mathbb{R}^n \\ \end{align*} \end{split}\]

The result is a conic program for the dual coefficients \(\alpha\) and auxiliary variables \(r\) and \(z\).

\[\begin{split} \begin{align*} \min \quad & r - 1^\top \alpha\\ \text{s.t.} \quad & (r, 1, z) \in \mathcal{Q}_r^{2 + q} & r\in\mathbb{R} \\ & z = F^\top \alpha & z\in\mathbb{R}^{q} \\ & 0 \leq \alpha \leq \frac{c}{n} & \alpha\in\mathbb{R}^n \\ \end{align*} \end{split}\]

Summarizing, the essential difference between training the linear and kernelized SVM is the need to compute and factor the Gram matrix. The result will be a set of non-zero coefficients \(\alpha_i > 0\) that define a set of support vectors \(\mathcal{SV}\). The classifier is then given by

\[y^{pred} = \text{sgn} \left( \sum_{i\in\mathcal{SV}} \alpha_i y_i K(\bar{x}_i, \bar{x}) \right)\]

The following cell implements this model, leaving it to the user to specify the kernel function via a lambda-function argument.

The plots highlight coefficients exceeding 1e-3 * c / n. Both classifier implementations retain every fitted coefficient when evaluating predictions: a small coefficient can have a substantial contribution when features or kernel values are large.

The factory below passes augmented vectors \(\bar{x}=(1,x)\) and \(\bar{z}=(1,z)\) to every kernel function.

def kernelSVMFactory(X, y, c, tol=1e-8, kernel=lambda x, z: (x @ z)):
    n, p = X.shape

    # convert to numpy arrays for speed
    X_ = np.hstack([np.ones((n, 1)), X.to_numpy()])
    y_ = y.to_numpy()

    # kernel matrix
    G = [
        [y_[i] * y_[j] * kernel(X_[i, :], X_[j, :]) for j in range(n)] for i in range(n)
    ]

    # spectral factors for a positive semi-definite matrix
    eigvals, V = np.linalg.eigh(G)
    idx = eigvals >= tol * max(eigvals)
    F = V[:, idx] @ np.diag(np.sqrt(eigvals[idx]))
    q = sum(idx)

    # build model
    m = pmo.block()

    # decision variables
    m.r = pmo.variable()
    m.a = pmo.variable_list([pmo.variable(lb=0, ub=c / n) for i in range(n)])
    m.z = pmo.variable_list([pmo.variable() for i in range(q)])

    # objective
    m.o = pmo.objective(expr=m.r - sum(m.a))

    # constraints
    m.d = pmo.constraint_list(
        [
            pmo.constraint(body=sum(F[i, j] * m.a[i] for i in range(n)) - m.z[j], rhs=0)
            for j in range(q)
        ]
    )
    m.q = pmo.conic.rotated_quadratic.as_domain(m.r, 1, m.z)

    # solve
    results = SOLVER.solve(m)
    pyo.assert_optimal_termination(results)

    # Use a relative tolerance only to color the support-vector plot.
    support_tol = 1e-3 * c / n
    SV = [i for i in range(n) if m.a[i]() > support_tol]
    y_support = pd.Series(
        [1 if i in SV else -1 for i in range(n)], index=X.index
    )
    scatter_labeled_data(
        X,
        y_support,
        colors=["b", "y"],
        labels=["Support Vector", ""],
        title="Support Vectors",
    )

    def kernelSVM(Z):
        nz, pz = Z.shape
        Z_ = np.hstack([np.ones((nz, 1)), Z.to_numpy()])
        y_pred = pd.Series(
            [
                int(classify(sum(m.a[i]() * y_[i] * kernel(X_[i, :], Z_[j, :]) for i in range(n))))
                for j in range(nz)
            ],
            index=Z.index,
        )
        return y_pred

    return kernelSVM

Linear kernel#

A linear kernel reduces the kernelized SVM to the previous case.

\[K(\bar{x},\bar{z})=\bar{x}^\top\bar{z}=1+x^\top z.\]

This is useful for verifying the calculation because we can check if we obtain indeed the same results.

svm = kernelSVMFactory(X_train, y_train, c=10, kernel=lambda x, z: x @ z)

y_pred = svm(X_test)
validate(y_test, y_pred)
scatter_comparison(X_test, y_test, y_pred)
Matthews correlation coefficient (MCC) = 0.762
Sensitivity =  92.4%
Precision =  87.9%
Accuracy =  88.4%
Predicted Positive Predicted Negative
Actual Positive 145 12
Actual Negative 20 98
../../_images/cdb78ec44b718b7721ceede308ccd419088c05c4efae4b9c687e82b9a01ffcb0.png ../../_images/b9dc95ad63a5379b882966907ded352c0a4b64c3b063e248a785d26e5e95734e.png ../../_images/a2270c6260adc423315aeb8ee305177a50060f7def0a38d86aff37da34507317.png

Radial basis function kernel#

A radial basis function kernel is given by

\[K(\bar{x},\bar{z})=\exp\left(-\gamma\|\bar{x}-\bar{z}\|^2\right)=\exp\left(-\gamma\|x-z\|^2\right).\]

The radial basis function is commonly used as the default kernel in SVM applications and as we shall see, it can give a significant boost to the predictive performance of our tool.

rbf = lambda x, z: np.exp(-10 * np.linalg.norm(x - z) ** 2)
svm = kernelSVMFactory(X_train, y_train, c=10, kernel=rbf)

y_pred = svm(X_test)
validate(y_test, y_pred)
scatter_comparison(X_test, y_test, y_pred)
Matthews correlation coefficient (MCC) = 0.891
Sensitivity =  93.0%
Precision =  97.3%
Accuracy =  94.5%
Predicted Positive Predicted Negative
Actual Positive 146 11
Actual Negative 4 114
../../_images/a7a2d2a0673b4256549b4134fcaf2f403e70d808208f1692f42bfc219849703a.png ../../_images/56eb6cdccc25e131bc4e92444901676c4a68ce75be989e54bc934e17a9ddf955.png ../../_images/2d73d6087d1b931ce48049390883e8d1e80556f2def0a81ea4ee930daa9205d1.png

Polynomial kernel#

Another important kernel function type is the polynomial kernel (which corresponds to including in the feature vector the powers of all features up to a certain degree \(d\)).

\[K(\bar{x}, \bar{z}) = (1 + \bar{x}^\top \bar{z})^d.\]

The quadratic example below therefore uses \((2+x^\top z)^2\) on the original feature vectors.

Increasing \(d\) makes the feature space more flexible, but does not guarantee better predictions on the test set. Try varying \(d\) and compare the resulting performance metrics.

poly = lambda x, z: (1 + (x @ z)) ** 2

svm = kernelSVMFactory(X_train, y_train, c=10, kernel=poly)

y_pred = svm(X_test)
validate(y_test, y_pred)
scatter_comparison(X_test, y_test, y_pred)
Matthews correlation coefficient (MCC) = 0.829
Sensitivity =  94.9%
Precision =  90.9%
Accuracy =  91.6%
Predicted Positive Predicted Negative
Actual Positive 149 8
Actual Negative 15 103
../../_images/a295a7dfe448df0dc2afc136399ffa84e1668360344931a644626ea0ae76c1a3.png ../../_images/11aa77399581f4e4d2a21c8671ebdddf5010b7e9e923f25710a3b5659a9f4bab.png ../../_images/8bc3f903f1453a2a1d8bafa16345bd0f5e52468aeea14226c9811766d3bb778a.png