ST443 Machine Learning and data mining

Week 10

Question 1

1. SVC and SVM.

1. In the class, we have shown that the SVC corresponds to the following optimisation problem: \[ \underset{(\beta_0, \beta, \xi) \in \Re \times \Re^p \times \Re^n_{\geq 0}}{\min} \, \frac{1}{2} \| \beta \|_2^2 + \rho \sum_{i = 1}^n \xi_i, \quad \text{s.t. } y_i (\beta_0 + \beta^\top x_i) \geq 1 - \xi_i, \, \forall i = 1, \ldots, n \,, \] where \(\rho \geq 0\) is a tuning cost hyperparameter. Explain how \(\rho\) controls the bias-variance trade-off of the SVC.

Question 1.a

Soft-margin SVC

\[ \underset{(\beta_0, \beta, \xi) \in \Re \times \Re^p \times \Re^n_{\geq 0}}{\min} \, \frac{1}{2} \| \beta \|_2^2 + \rho \sum_{i = 1}^n \xi_i, \quad \text{s.t. } y_i (\beta_0 + \beta^\top x_i) \geq 1 - \xi_i, \, \forall i = 1, \ldots, n \,, \]

• \(\rho\) controls how much we penalise the objective for violations of the margin
• Large \(\rho\), heavy penalisation, we strongly prefer no violations of margin, so margin will get smaller
• Small margin means we make less mistakes (low bias), but we have fewer support vectors (higher variance)
• Large margins means we allow for more mistakes (high bias), but have more support vectors (lower variance)

Question 1.a

library(e1071)
library(plotly)

set.seed(443)

n_per <- 100
X_pos <- cbind(rnorm(n_per,  1.5, 1), rnorm(n_per,  1.5, 1))
X_neg <- cbind(rnorm(n_per, -1.5, 1), rnorm(n_per, -1.5, 1))

df <- rbind(
  data.frame(x1 = X_pos[, 1], x2 = X_pos[, 2], y = "1"),
  data.frame(x1 = X_neg[, 1], x2 = X_neg[, 2], y = "-1")
)
df$y <- factor(df$y, levels = c("-1", "1"))

pad <- 1
xlim <- range(df$x1) + c(-pad, pad)
ylim <- range(df$x2) + c(-pad, pad)

rho_grid <- c(0.01, 0.05, 0.1, 0.2, 0.5, 1, 2, 5, 10, 20)

line_segment <- function(w, b, level, xlim, ylim, tol = 1e-9) {
  w1 <- w[1]; w2 <- w[2]
  pts <- matrix(numeric(0), ncol = 2)
  
  if (abs(w2) > tol) {
    y <- (level - b - w1 * xlim[1]) / w2
    pts <- rbind(pts, c(xlim[1], y))
    y <- (level - b - w1 * xlim[2]) / w2
    pts <- rbind(pts, c(xlim[2], y))
  }
  if (abs(w1) > tol) {
    x <- (level - b - w2 * ylim[1]) / w1
    pts <- rbind(pts, c(x, ylim[1]))
    x <- (level - b - w2 * ylim[2]) / w1
    pts <- rbind(pts, c(x, ylim[2]))
  }
  
  inside <- pts[,1] >= xlim[1] - 1e-7 & pts[,1] <= xlim[2] + 1e-7 &
    pts[,2] >= ylim[1] - 1e-7 & pts[,2] <= ylim[2] + 1e-7
  pts <- pts[inside, , drop = FALSE]
  
  if (nrow(pts) == 0) return(data.frame(x = numeric(0), y = numeric(0)))
  
  pts <- unique(round(pts, 8))
  
  if (nrow(pts) == 1) return(data.frame(x = pts[1,1], y = pts[1,2]))
  
  if (nrow(pts) > 2) {
    d <- as.matrix(dist(pts))
    ij <- which(d == max(d), arr.ind = TRUE)[1, ]
    pts <- pts[c(ij[1], ij[2]), , drop = FALSE]
  } else {
    pts <- pts[1:2, , drop = FALSE]
  }
  
  data.frame(x = pts[,1], y = pts[,2])
}

all_points <- list()
all_sv <- list()
all_lines <- list()

for (k in seq_along(rho_grid)) {
  rho <- rho_grid[k]
  
  fit <- svm(y ~ x1 + x2, data = df, type = "C-classification",
             kernel = "linear", cost = rho, scale = FALSE)
  
  w <- drop(t(fit$coefs) %*% fit$SV)
  b <- -fit$rho
  
  tmp_points <- df
  tmp_points$rho <- rho
  all_points[[k]] <- tmp_points
  
  sv_idx <- fit$index
  sv_df <- df[sv_idx, ]
  sv_df$rho <- rho
  all_sv[[k]] <- sv_df
  
  bound <- line_segment(w, b,  0, xlim, ylim)
  mpos  <- line_segment(w, b,  1, xlim, ylim)
  mneg  <- line_segment(w, b, -1, xlim, ylim)
  
  if (nrow(bound) > 0) bound$kind <- "boundary"
  if (nrow(mpos)  > 0) mpos$kind  <- "margin+"
  if (nrow(mneg)  > 0) mneg$kind  <- "margin-"
  
  lines_k <- rbind(bound, mpos, mneg)
  if (nrow(lines_k) > 0) {
    lines_k$rho <- rho
    all_lines[[k]] <- lines_k
  }
}

points_all <- do.call(rbind, all_points)
sv_all <- do.call(rbind, all_sv)
lines_all <- do.call(rbind, all_lines)

points_all$rho_f <- factor(points_all$rho, levels = rho_grid)
sv_all$rho_f <- factor(sv_all$rho, levels = rho_grid)
lines_all$rho_f <- factor(lines_all$rho, levels = rho_grid)
lines_all$group <- paste(lines_all$kind, lines_all$rho_f)

pts_pos <- subset(points_all, y == "1")
pts_neg <- subset(points_all, y == "-1")

p <- plot_ly()

p <- add_markers(
  p,
  data = pts_pos,
  x = ~x1,
  y = ~x2,
  frame = ~rho_f,
  marker = list(size = 7, color = "#1f77b4"),
  name = "y = 1",
  showlegend = TRUE
)

p <- add_markers(
  p,
  data = pts_neg,
  x = ~x1,
  y = ~x2,
  frame = ~rho_f,
  marker = list(size = 7, color = "#ff7f0e"),
  name = "y = -1",
  showlegend = TRUE
)

p <- add_markers(
  p,
  data = sv_all,
  x = ~x1,
  y = ~x2,
  frame = ~rho_f,
  marker = list(symbol = "circle-open", size = 16,
                color = "black", line = list(width = 2, color = "black")),
  inherit = FALSE,
  name = "support vectors",
  showlegend = TRUE
)

p <- add_lines(
  p,
  data = subset(lines_all, kind == "boundary"),
  x = ~x,
  y = ~y,
  frame = ~rho_f,
  split = ~group,
  line = list(color = "black", width = 4),
  inherit = FALSE,
  showlegend = FALSE
)

p <- add_lines(
  p,
  data = subset(lines_all, kind == "margin+"),
  x = ~x,
  y = ~y,
  frame = ~rho_f,
  split = ~group,
  line = list(color = "lightgray", width = 2, dash = "dash"),
  inherit = FALSE,
  showlegend = FALSE
)

p <- add_lines(
  p,
  data = subset(lines_all, kind == "margin-"),
  x = ~x,
  y = ~y,
  frame = ~rho_f,
  split = ~group,
  line = list(color = "lightgray", width = 2, dash = "dash"),
  inherit = FALSE,
  showlegend = FALSE
)

p <- layout(
  p,
  xaxis = list(title = "x1", range = xlim),
  yaxis = list(title = "x2", range = ylim, scaleanchor = "x", scaleratio = 1),
  title = "Soft-margin SVC"
)

p <- animation_opts(p, frame = 0, transition = 0, redraw = TRUE)
p <- suppressWarnings(animation_slider(p, currentvalue = list(prefix = "ρ = ")))
p$x$layout$updatemenus <- NULL
p

Question 1.b

2. Let \(x = (x_1, x_2)^\top \in \Re^2\) and \(\Phi(x) = (x_1, x_2, x_1 x_2)^\top \in \Re^3\). Give the expression for the kernel \(\mathcal{k}(x, x')\) of \(\Phi\).

Question 1.b.

\[ \begin{aligned} k(x,x') &= \Phi(x)^\top \Phi(x') \\ &= (x_1, x_2, x_1 x_2)^\top(x_1', x_2', x_1' x_2') \\ &= x_1x_1' + x_2x_2' + x_1x_1'x_2x_2' \,. \end{aligned} \]

Question 1.c

3. Show that the function \(\mathcal{k}(x, x') = \cos(x - x')\) for \(x, x' \in \Re\) is a kernel for some \(\Phi\), and that \(\mathcal{k}\) is a symmetric and positive definite kernel.

Question 1.c

Symmetry, PSD

For any \(r \in \mathbb{N}\), \(x_1, \ldots, x_r \in \Re\),

\[ \mathcal K = \begin{bmatrix} \mathcal{k}(x_1, x_1) & \mathcal{k}(x_1, x_2) & \ldots & \mathcal{k}(x_1, x_r) \\ \mathcal{k}(x_2, x_1) & \mathcal{k}(x_2, x_2) & \ldots & \mathcal{k}(x_2, x_r) \\ \vdots & \ddots & \ddots & \vdots \\ \mathcal{k}(x_r, x_1) & \mathcal{k}(x_r, x_2) & \ldots & \mathcal{k}(x_r, x_r) \end{bmatrix} \]

is symmetric, and positive semidefinite

Question 1.c

Symmetry

• Need \(\mathcal{k}(x_1, x_2) = \mathcal{k}(x_2, x_1) \iff \cos(x_1 - x_2) = \cos(x_2 - x_1)\)

xs <- seq(from = -5, to = 5, length.out = 1000)

plot(xs, cos(xs), type = "l", col = "blue", lwd = 2) 
abline(v = 0, col = "grey", linetype = "dash", lty = 2)

• \(\cos(x) = \cos(-x) = \cos(|x|)\)

• Consequently \(\cos(x_1 - x_2) = \cos(-(x_1 - x_2)) = \cos(x_2 - x_1)\)

Question 1.c

Feature map

A Fundamental trigonometric identity [NE]:

Video: Cosine of the Difference of Two Angles

Video: Law of cosines

\[ \cos(x - x') = \cos(x) \cos(x') + \sin(x) \sin(x') \]

\[ \begin{aligned} \cos(x - x') &= \cos(x) \cos(x') + \sin(x) \sin(x') \\ &= \begin{bmatrix} \cos(x) & \sin(x) \end{bmatrix} \begin{bmatrix} \cos(x') \\ \sin(x') \end{bmatrix} \\ &= \Phi(x)^\top \Phi(x') \,, \end{aligned} \]

for

\[ \Phi(x) = \begin{bmatrix} \cos(x) \\ \sin(x) \end{bmatrix} \,. \]

Question 1.c

PSD

• Need: For any \(r, \in \mathbb{N}\), \(x_1, \ldots, x_r \in \Re\), \(v \in \Re^r, v \neq 0\), \(v^\top \mathcal K v \geq 0\)

\[ \begin{aligned} \mathcal K &= \begin{bmatrix} \Phi(x_1)^\top \Phi(x_1) & \Phi(x_1)^\top \Phi(x_2) & \ldots & \Phi(x_1)^\top \Phi(x_r) \\ \Phi(x_2)^\top \Phi(x_1) & \Phi(x_2)^\top \Phi(x_2) & \ldots & \Phi(x_2)^\top \Phi(x_r) \\ \vdots & \ddots & \ddots & \vdots \\ \Phi(x_r)^\top \Phi(x_1) & \Phi(x_r)^\top \Phi(x_2) & \ldots &\Phi(x_r)^\top \Phi(x_r) \end{bmatrix} \\ &= \begin{bmatrix} \Phi(x_1)^\top \\ \Phi(x_2)^\top \\ \vdots \\ \Phi(x_r)^\top \end{bmatrix} \begin{bmatrix} \Phi(x_1) & \Phi(x_2) & \ldots & \Phi(x_r) \end{bmatrix} \end{aligned} \]

Question 1.c

PSD

• Need: For any \(r, \in \mathbb{N}\), \(x_1, \ldots, x_r \in \Re\), \(v \in \Re^r\), \(v^\top K v \geq 0\)

\[ v^\top \mathcal K v= v^\top [\Phi(x_1), \ldots, \Phi(x_r)]^\top [\Phi(x_1), \ldots, \Phi(x_r)] v = \tilde v^\top \tilde v \geq 0 \,, \]

for \[ \tilde v = [\Phi(x_1), \ldots, \Phi(x_r)] v \,. \]

Question 1.d

4. Consider the polynomial kernel \[ \mathcal{k}(x, x') = (c + \gamma x^\top x')^d \] for \(d = 2\), \(\gamma > 0\) and \(c \ge 0\), where \(x, x' \in \Re^p\). Show the feature map \(\Phi\) of this kernel.

Question 1.d

\[ \begin{aligned} \mathcal{k}(x, y) &= (c + \gamma x^\top y)^2 \\ &= c^2 + 2 c \gamma \sum_{i = 1}^p x_i y_i + \gamma^2 \left(\sum_{i = 1}^p x_i y_i \right)^2 \\ &= c^2 + 2 c \gamma \sum_{i = 1}^p x_i y_i + \gamma^2 \sum_{i = 1}^p\sum_{j = 1}^p x_ix_j y_i y_j \\ &= c^2 + 2 c \gamma \sum_{i = 1}^p x_i y_i + \gamma^2 \sum_{i = 1}^p x_i^2 y_i^2 + 2\gamma^2 \sum_{i = 1}^p\sum_{j > 1}^r x_ix_j y_i y_j \end{aligned} \]

Idea: match to second order polynomial with interactions \[ \begin{multline} \Psi(x) = \begin{bmatrix} x_1, x_2, \ldots, x_p, x_1^2, \ldots, x_p^2, x_1 x_2, \ldots, x_1 x_p, x_2 x_3, \ldots, x_{p-1} x_p \end{bmatrix} \end{multline} \]

Question 1.d

\[ \Phi(x)^\top \Phi(y) = c^2 + 2 c \gamma \sum_{i = 1}^p x_i y_i + \gamma^2 \sum_{i = 1}^p x_i^2 y_i^2 + 2\gamma^2 \sum_{i = 1}^p\sum_{j > 1}^p x_ix_j y_i y_j \]

vs

\[ \Psi(x)^\top \Psi(y) = \sum_{i = 1}^p x_i y_i + \sum_{i = 1}^p x_i^2 y_i^2 + 2\sum_{i=1}^p\sum_{j > 1}^p x_ix_j y_i y_j \]

Therefore

\[ \Phi(x) = \begin{bmatrix} c, \sqrt{2c \gamma} x_1, \ldots, \sqrt{2c \gamma} x_p, \gamma x_1^2 , \ldots,\gamma x_p^2, \gamma x_1 x_2, \ldots, \gamma x_{p-1} x_p \end{bmatrix} \]

Question 1.e

5. Consider the SVM with a radial basis kernel, which takes the form \[ \mathcal{k}(x, x') = \exp\left(-\gamma \|x - x'\|_2^2\right), \] where \(\gamma > 0\). Explain how the parameter \(\gamma\) influences the bias and variance of the SVM classifier.

Question 1.e

SVC

\[ x^\top \beta^* = \sum_{i = 1}^p \lambda_i^* y_i x_i^\top x \]

SVM

\[ s(x) = \sum_{i = 1}^p \lambda_i^* y_i k(x_i, x) = \sum_{i = 1}^n \lambda_i^* y_i \exp \left(-\gamma \| x_i - x \|^2 \right) \]

• If \(\gamma \to \infty\): \(k(x,x_i) \approx 0\) whenever \(x_i \neq x\)
  • Like \(1\)-NN, low bias
  • Can produce highly nonlinear decision boundaries
  • If data change, the decsion boundary will change drastically (high variance)
• If \(\gamma \to 0\): \(k(x,x_i) \to 1\), so prediction function becomes constant
  • Low variance, high bias
  • Generally, for large gamma, more points around \(x\) will contribute to score, lower variance but bias increases

Learnings

• How kernels relate to inner product
• How differnt kernels and hyperparameters give different decision boundaries
• Soft-margin SVC/SVM cost parameter

Question 2

SVM and XOR data. Let \(f ∶ \{0, 1\}^2 \to \{0, 1\}\) be the exclusive OR function, where $f (a,b) = 1 if (a,b) = (0, 1) or (a,b) = (1, 0), and \(f (a, b) = 0\) otherwise. Consider the XOR dataset \((x_1, y_1), \ldots , (x_4, x_4)\), defined such that

• \(x_1 = (0, 0)^\top\),
• \(x_2 = (0, 1)^\top\),
• \(x_3 = (1, 0)^\top\), and
• \(x_4 = (1, 1)^\top\),

and \(y_i = f (x_i)\) for \(i = 1,\ldots , 4\).

Question 2

library(ggplot2)

df <- data.frame(
  x = c(0, 0, 1, 1),
  y = c(0, 1, 0, 1),
  col = c("black", "white", "white", "black")
)

ggplot(df, aes(x, y)) +
  geom_point(aes(fill = col), shape = 21, size = 5, colour = "black") +
  scale_fill_identity() +
  coord_fixed() +
  theme_minimal()

The XOR dataset is a classical example of a non-linearly separable dataset.

Question 2.a

1. Show that \((x_1, y_1), \ldots , (x_4, y_4)\) is not a linearly separable dataset.

Question 2

Affine \(1\)-dimensional hyperplane

For \(\beta_0 \in \Re\), \(\beta \in \Re^2, \, \beta \neq 0_2\),

\[ H(\beta_0, \beta) = \{x \in \Re^2: \beta_0 + x^\top \beta = 0 \} \]

Separating hyperplane

\(H(\beta_0, \beta)\) is a separating hyperplane, if for all \(y_i \in \{-1,1\}\),

\[ y_i(\beta_0 + x_i^\top \beta) \geq 0 \]

Question 2

WLOG:

\[ f(x_i) = \begin{cases} 1 & \text{if } \| x \|_1 = 1 \\ -1 & \text{otherwise} \end{cases} \]

• \(f(x_1) = f([0,0]) = -1\)
• \(f(x_2) = f([1,0]) = 1\)
• \(f(x_3) = f([0,1]) = 1\)
  
• \(f(x_4) = f([1,1]) = -1\)

Then have \[ \begin{aligned} -(\beta_0 + [0,0] \beta) &\geq 0 \\ \beta_0 + [1, 0] \beta & \geq 0 \\ \beta_0 + [0,1]\beta& \geq 0 \\ -(\beta_0 + [1,1]\beta) & \geq 0 \end{aligned} \]

Question 2

\[ \begin{aligned} -(\beta_0 + [0,0] \beta) &\geq 0 \\ \beta_0 + [1, 0] \beta & \geq 0 \\ \beta_0 + [0,1]\beta& \geq 0 \\ -(\beta_0 + [1,1]\beta) & \geq 0 \end{aligned} \]

Yields

\[ \begin{aligned} \beta_0 &\leq 0 \\ \beta_1 & \geq -\beta_0 \\ \beta_2 & \geq -\beta_0 \\ \beta_0 + \beta_1 + \beta_2 &\leq 0 \end{aligned} \]

But then

\[ \begin{aligned} \beta_0 + \beta_1 + \beta_2 \geq \beta_0 - 2 \beta_0 = - \beta_0 \geq 0 \,, \end{aligned} \]

and would need \(\beta_0 = \beta_1 = \beta_2 = 0\), and \(H(0, [0,0]^\top)\) is not a \(1\)D hyperplane.

Question 2

2. Consider the SVM using the quadratic polynomial kernel \[ \mathcal{k}(x,x') = (c + \gamma x^\top x')^2 \] for \(\gamma > 0\), \(c \geq 0\). Show that in the transformed feature domain using this kernel, the observation points are linearly separable.

Question 2.b

\[ \Phi(x_1,x_2) = \begin{bmatrix} c, & \sqrt{2c\gamma} x_1, & \sqrt{2c\gamma} x_2, & \gamma^2 x_1^2, & \gamma^2 x_1^2, & \sqrt{2}\gamma x_1x_2 \end{bmatrix} \]

Quick and dirty

• \(c = 0\)
• \(\gamma = 1\)

\[ \Phi(x_1,x_2) = \begin{bmatrix} x_1^2, & x_1^2, & \sqrt{2}\gamma x_1x_2 \end{bmatrix} \]

• \(\Phi(0,0) = [0,0,0]^\top\)
• \(\Phi(1,0) = [1,0,0]^\top\)
• \(\Phi(0,1) = [0,1,0]^\top\)
• \(\Phi(1,1) = [1,1,\sqrt{2}]^\top\)

Question 2.a

\[ y_i ( \beta_0 + \beta^\top \Phi(x_i)) \geq 0 \]

\[ \begin{aligned} -(\beta_0 + [0,0,0]\beta) &\geq 0 \\ \beta_0 + [1,0,0]\beta &\geq 0 \\ \beta_0 + [0,1,0]\beta &\geq 0 \\ \beta_0 + [1,1,\sqrt{2}] \beta & \geq 0 \end{aligned} \]

\[ \begin{aligned} \beta_0 &\leq 0 \\ \beta_1 & \geq - \beta_0 \\ \beta_2 & \geq - \beta_0 \\ -(\beta_0 + \beta_1 + \beta_2 + \sqrt{2}\beta_3) &\geq 0 \\ \end{aligned} \]

Take

• \(\beta_0 = -1/4\)
• \(\beta_1 = \beta_2 = 1\)
• \(\beta_3 = - (1 + \sqrt{2})\)

Question 2.a

A separating feature map

library(ggplot2)

df <- data.frame(
  x1 = c(0, 1, 0, 1),
  x2 = c(0, 0, 1, 1),
  y  = factor(c(0, 1, 1, 0))
)

grid <- expand.grid(
  x1 = seq(0, 1, length.out = 200),
  x2 = seq(0, 1, length.out = 200)
)
grid$g <-  -.1/4 + grid$x1^2 + grid$x2^2 - (1 + sqrt(2)) * ( grid$x1 *  grid$x2)

ggplot() +
  geom_raster(data = grid, aes(x1, x2, fill = g > 0), alpha = 0.3) +
  geom_contour(data = grid, aes(x1, x2, z = g), breaks = 0, colour = "black") +
  geom_point(data = df, aes(x1, x2, colour = y), size = 3) +
  scale_fill_manual(values = c("grey", "white"), guide = "none") +
  scale_colour_manual(values = c("black", "lightgrey")) +
  coord_fixed() +
  theme_minimal()

Question 2.a

A separating feature map

Learnings

• Separating hyperplanes & relation to SVMs
• Get comfortable with different kernels