Neural networks course

​

Recitation 4: SVMs, interpretability

​

​

​

​

​

Motivation

• For linearly separable data, the perceptron convergence to a optimal solution on the train
• Not necessarily optimal with regard to generalization (test set performance)
• Idea: In order to generalize, find a separation plane that maximizes the distance to the closest training points

Formulation

Formulation

• Scaling w doesn’t change the distance, so we can set w such that wx_iy_i = 1 for the minimal i

Dual representation

• We have a quadratic minimization problem with linear constraints
• This can be efficiently solved with lagrange multipliers

Dual problem

Dual function

Lagrangian

Dual representation for SVMs

We will not show the solution to the maximization of g. But it turns out all α_i are zero except of the ones belonging to the closest points: the support vectors.

Classification: weight all training example

Non linearly separable data

Non linear data

The dual representation

Non linearly separable data

• Prediction requires calculating the dot product between the example x and all other example x_i!

​

​

• The kernel trick computes the dot product in the feature space implicitly

The kernel trick

• We can often calculate the product without having to calculate and
• Consider the following kernel: φ((a, b)) = (a, b, a² + b²)

​

• Naive calculation:
• φ((a, b))φ((c, d)) = (a, b, a² + b²)(c, d, c² + d²) = ac + bd + (a² + b²) (c² + d²) = ac + bd + a²c² + a²d² + b²c² + b²d²
• Kernel trick: directly use ac + bd + (a² + b²) (c² + d²) = ac + bd + a²c² + a²d² + b²c² + b²d²

Polynomial Kernel

Kernels

​

​

​

​

• Theorem: if K is PSD then it represents a valid kernel (i.e. it corresponds to dot product in some feature space)

RBF kernel

Interpretability: Deep Dream