Support Vector Classifier

Today

  • Cat sex
  • Soft margin
    • Overlapping classes
    • Optimization problem
    • Slack variables
  • Fitting
    • Penalty form
    • Standardization
    • Estimates
    • Slack estimates
  • Budget
    • Bias and variance
    • Cost and budget
  • Support vectors
    • Definition
    • Refits
    • Support vector count
  • Cross-validation
    • Error rate
    • Curve
  • Test error
    • Confusion matrix
  • Comparison
    • Classifiers
    • Measures
    • Results

Cat sex

Cat sex

  • Class: Sex (M: \(y = 1\), F: \(y = -1\))
  • Explanatory variables (\(p = 2\)):
    • Hwt: heart weight (g)
    • Bwt: body weight (kg)
  • Training cats: 96 (31 F, 65 M)
  • Test cats: 48

Cat sex: plot

Soft margin

Overlapping classes

  • Not separable: in 3 places a female and a male cat share both measurements
  • Maximal margin constraints cannot all hold with \(M > 0\):

\[ y_i\left(\beta_0 + \beta^\top x_i\right) \ge M \]

Optimization problem

Support vector classifier, constraints for all \(i = 1, \ldots, n\):

\[ \begin{aligned} \underset{\beta_0, \beta_1, \ldots, \beta_p, \epsilon_1, \ldots, \epsilon_n, M}{\text{maximize}} \quad & M \\ \text{subject to} \quad & \sum_{j=1}^p \beta_j^2 = 1, \\ & y_i\left(\beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip}\right) \ge M(1 - \epsilon_i), \\ & \epsilon_i \ge 0, \quad \sum_{i=1}^n \epsilon_i \le C, \end{aligned} \]

  • \(\epsilon_i\) — slack variable: violation of the margin, in units of \(M\)
  • \(C \ge 0\) — budget: bounds the total slack
  • \(\sum_j \beta_j^2 = 1\): \(f(x_i) = \beta_0 + \beta^\top x_i\) is the signed distance to the hyperplane
  • \(y_i f(x_i) \ge M(1 - \epsilon_i)\): distance on own side at least \(M(1 - \epsilon_i)\); \(\epsilon_i = 0\) is the maximal margin constraint

Slack variables

With \(f(x_i) = \beta_0 + \beta^\top x_i\):

  • \(\epsilon_i = 0\): \(y_i f(x_i) \ge M\), on the correct side and on or outside the margin
  • \(0 < \epsilon_i \le 1\): \(0 \le y_i f(x_i) < M\), inside the margin on the correct side (on the hyperplane when \(\epsilon_i = 1\))
  • \(\epsilon_i > 1\): \(y_i f(x_i) < 0\), on the wrong side of the hyperplane, misclassified
  • At most \(C\) training observations are misclassified

Fitting

Fitting

# Support vector classifier: linear kernel, standardized features.
svc_fit <- svm(Sex ~ Hwt + Bwt, data = train, kernel = "linear",
               cost = 1, tolerance = 1e-8)
svc_fit

Call:
svm(formula = Sex ~ Hwt + Bwt, data = train, kernel = "linear", cost = 1, 
    tolerance = 1e-08)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  linear 
       cost:  1 

Number of Support Vectors:  58

Penalty form

e1071::svm() solves

\[ \underset{w_0, w, \epsilon_1, \ldots, \epsilon_n}{\text{minimize}} \quad \tfrac{1}{2}\|w\|^2 + \texttt{cost}\sum_{i=1}^n \epsilon_i \quad \text{subject to} \quad y_i\left(w_0 + w^\top x_i\right) \ge 1 - \epsilon_i, \quad \epsilon_i \ge 0, \]

  • \(w_0 = \beta_0/M\), \(w = \beta/M\), so \(\|w\| = 1/M\)
  • \(\epsilon_i\) — slack variable of observation \(i\), as before
  • cost \(> 0\) — price of one unit of slack
  • Large cost: slack is expensive, a small budget
  • Small cost: slack is cheap, a large budget

Standardization

  • Margin: a distance, adding the features’ squared differences in their own units
  • Penalty: depends on the units too, so the same cost is a different budget
  • Standardize each feature, as svm() does by default (scale = TRUE):

\[ \tilde x_{ij} = \frac{x_{ij} - \bar x_j}{s_j}, \]

  • \(\bar x_j\) — mean of feature \(j\) among the training observations
  • \(s_j\) — its standard deviation
  • \(\tilde x_{ij}\) — observation \(i\)’s value of feature \(j\), in standard deviations from that mean

Standardization: fits

Estimates

# w and w0 with M on the positive side.
w_hat <- svc_w(svc_fit)

# Unit-norm estimates on the standardized scale, and the margin.
norm_w <- sqrt(sum(w_hat$w^2))
beta_hat <- c(beta0 = w_hat$w0, w_hat$w) / norm_w
M_hat <- 1 / norm_w
round(c(beta_hat, M = M_hat), 4)
  beta0     Hwt     Bwt       M 
 0.5519 -0.1502  0.9887  0.6426 

Slack estimates

\[ \widehat\epsilon_i = \max\left(0,\ 1 - \frac{y_i \widehat f(x_i)}{\widehat M}\right), \]

  • \(\widehat f(x)\) — fitted value
  • \(\widehat M\) — margin

Budget

Budget

Bias and variance

  • \(C = 0\): the maximal margin classifier, which exists only for separable classes
  • Small \(C\): narrow margin, few support vectors, low bias, high variance
  • Large \(C\): wide margin, many support vectors, low variance, more bias

Cost and budget

  • Larger cost: budget \(C\) no larger, margin \(\widehat M\) no wider
  • cost \(\ne C\): the \(C\) a cost gives depends on the data
  • cost \(\to \infty\) on separable data: the maximal margin classifier
cost \(\sum_i\widehat\epsilon_i\) \(\widehat M\) Support vectors Inside the margin Wrong side Training error rate
0.01 61.68 17.68 62 31 31 0.323
0.10 58.80 1.77 62 34 28 0.292
1.00 54.55 0.64 58 33 22 0.229
10.00 54.41 0.57 56 32 21 0.219

Support vectors

Support vectors

Definition

  • Support vectors: \(y_i\widehat f(x_i) \le \widehat M\), on the margin, inside it, or on the wrong side of the hyperplane
  • Wider than the previous lecture’s: the observations on the margin only, the case with no slack
  • Circled cats: 58 of the 96
  • The fitted hyperplane depends only on them

Refits

  • Delete an observation outside the margin, or move it anywhere outside: the fit is unchanged
  • Refit to the 58 support vectors alone: the same estimates, to six decimal places
  • Maximal margin: a handful of support vectors; here, every observation inside the margin or on the wrong side

Support vector count

Cross-validation

Error rate

# 10-fold cross-validation over the grid of cost values.
cv_fit <- tune(svm, Sex ~ Hwt + Bwt, data = train, kernel = "linear",
               ranges = list(cost = cost_grid))
head(cv_fit$performances, 3)
cv_fit$best.parameters
        cost     error dispersion
1 0.01000000 0.3255556  0.1478747
2 0.01778279 0.3255556  0.1478747
3 0.03162278 0.3255556  0.1478747
       cost
10 1.778279

Curve

Test error

Test error

Confusion matrix

     Predicted
Truth  F  M
    F 11  5
    M  4 28
  • Positive class: M
  • Test error rate: \((FP + FN)/n = (5 + 4)/48 = 0.188\)
  • Classifying every test cat M: 33.3%

Comparison

Classifiers

  • Support vector classifier (chosen cost)
  • Logistic regression: main effects; with interaction; with squares and interaction
  • LDA, QDA
  • Random forest
# Fits to the training cats; each gives a probability that a cat is M.
set.seed(20261114)
logit_fit <- glm(Sex ~ Hwt + Bwt, data = train, family = binomial)
lda_fit <- MASS::lda(Sex ~ Hwt + Bwt, data = train)
qda_fit <- MASS::qda(Sex ~ Hwt + Bwt, data = train)
rf_fit <- randomForest::randomForest(Sex ~ Hwt + Bwt, data = train)

# Probabilities of F and M that LDA gives the first three test cats.
head(predict(lda_fit, test)$posterior, 3)
           F         M
1  0.7219232 0.2780768
6  0.6667787 0.3332213
10 0.6774822 0.3225178

Measures

  • Error rate: proportion misclassified

\[ \text{log loss} = -\frac{1}{n}\sum_{i=1}^n \log \widehat p_i, \]

  • \(\widehat p_i\) — probability given cat \(i\)’s observed sex
  • \(n\) — number of cats

Results

Classifier CV error rate (%) CV log loss Test error rate (%) Test log loss
Logistic, main effects 22.9 0.510 16.7 0.418
Logistic, interaction 26.0 0.513 16.7 0.417
Logistic, quadratic 25.0 0.550 16.7 0.402
LDA 24.0 0.509 16.7 0.429
QDA 27.1 0.543 14.6 0.377
Random forest 22.9 0.567 20.8 0.406
Support vector classifier 24.0 — 18.8 —

Conclusion

  • Overlapping classes need slack, bounded by a budget \(C\)
  • At most \(C\) training observations are misclassified
  • The fit depends only on the support vectors
  • Small budget: low bias, high variance; large budget: the reverse
  • Larger cost: budget no larger, margin no wider; features standardized
  • cost by cross-validation; judged by the test error rate