<!--
Abstract:

CS 461
Introduction to Deep Learning
Lecture 11
-->

# CS 461 - Lecture 17

## Machine Learning Principles

### Large Margin Learning

Bernhard Firner

2025-11-02

---

## Reading

* Murphy
  * Chapter 14.5
    * Contain a fun statistician rant about an algorithm that works but isn't grounded in statistics
* Flach
  * Chapter 7.3

---

## Problem With Perceptrons

* Requires a Gram matrix computed with all training points
  * Since comparisons during training involved all points
* Doesn't guarantee any margins in the decision boundary

---

## Example

* This decision boundary is far closer to '+' than to '-'
* But there are no errors, so it will not update

</div>
<div class="col">

</div>
</div>

---

## Example

* This looks better
* How can we quantify that?

</div>
<div class="col">

</div>
</div>

---

## Margin

* A margin, m, is the gap between the decision boundary and the nearest training point, $x_i$
* Recall
  * $w = y\alpha X^T X$
  * $\hat{y}_i = sign(w^T x_i + w_0)$
  * where $w_0$ is a bias value
* The margin is the distance between a point, $x_i$, and the decision boundary $w^T x_i + w_0$

---

## Margin at the boundary

* Imagine that there is a sample, $x_i$, that is right at the decision boundary
* $t$ is at the boundary, so the margin is $\gt 0$
* Let's call $m$ the maximum bias to add or subtract from the decision boundary before it intersects the nearest training point
  * For $y_t=1$, $w^T x_i - m^+ \gt 0$
  * For $y_t=-1$, $-(w^T x_i - m^-) \gt 0$
  * Those nearest training points control $w$, and are called the `support vectors`

---

## Support Vectors

* The support vectors are the points nearest to the decision boundary
* If $m^+$ and $m^-$ are maximized, then there should be at least one vector from each class

</div>
<div class="col">

</div>
</div>

---

## Sparsity

* With perceptrons, $w$ is calculated from $y \alpha X^T X$
* Here, we only need a linear combination of the support vectors
  * That makes $\alpha$ sparse

</div>
<div class="col">

</div>
</div>

---

## Optimal Margin

* We want the decision boundary to be equidistant from both classes
  * Implies $m^+ = m^- = m$
* We also want to be as far from the classes as possible, so we want to maximize $m$

---

## Geometry

* Let's set up our equations with some geometry
* Two margin lines are $w^TX + w_0 + m$ and $w^TX + w_0 - m$
  * Notice that the distance between them is $\frac{2m}{\lVert w \rVert}$
    * From triangles and $a^2 + b^2 = c^2$

</div>
<div class="col">

</div>
</div>

---

## Optimization

* Let's set up our equations to minimize the margin distance, $\frac{m}{\lVert w \rVert}$
  * We will maximize w.r.t $w$ and $w_0$
* We can make $w$ a unit vector, $\frac{w}{\lVert w \rVert}$
  * Now the margin distance is $\frac{2m}{\lVert w \rVert^2}$

---

## Simplifications

* Maximizing $\frac{2m}{\lVert w \rVert^2}$ is the same as minimizing the denominator
* $m$ is an arbitrary constant, so let's just call it 1
* And for math reasons, lets maximize one side of the margin
  * So we want to minimize $\frac{1}{2}\lVert w \rVert^2$

---

## Constraints

* $\underset{w,w_0}{\mathrm{argmin}}\frac{1}{2}\lVert w \rVert^2$
* Recall that $w = y\alpha X$ and $w^TX - w_0$ is the decision boundary
* And $y_i(w^T \cdot x_i + w_0) \geq m,  \forall i \in n$
  * This ensuring predictions are positive by multiplying by $y_i$ and insists that each result is at or beyond the margin
  * And remember that we will treat $m=1$ going forward

---

## Lagrange Multipliers

* Maybe you remember this method of solving constrained optimization problems
* Write down function and constraints as a new function:
  * $\mathcal{L}(w, w_0, \alpha) = \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^n \alpha_i(y_i(w^Tx_i + w_0) - 1)$
  * $\mathcal{L}(w, w_0, \alpha) = \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^n \alpha_i y_i w^Tx_i - \sum_{i=1}^n \alpha_i y_i w_0 + \sum_{i=1}^n\alpha_i$
* Now we can take the derivatives w.r.t. $w$ and $w_0$ and set to $0$

---

## w.r.t. $w_0$

<p><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><mi>ℒ</mi><mrow><mo stretchy="true" form="prefix">(</mo><mi>w</mi><mo>,</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><mi>α</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mo stretchy="false" form="prefix">∥</mo><mi>w</mi><msup><mo stretchy="false" form="postfix">∥</mo><mn>2</mn></msup><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msup><mi>w</mi><mi>T</mi></msup><msub><mi>x</mi><mi>i</mi></msub><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msub><mi>w</mi><mn>0</mn></msub><mo>+</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mfrac><mi>δ</mi><mrow><mi>δ</mi><msub><mi>w</mi><mn>0</mn></msub></mrow></mfrac><mi>ℒ</mi><mrow><mo stretchy="true" form="prefix">(</mo><mi>w</mi><mo>,</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><mi>α</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
\mathcal{L}(w, w_0, \alpha) &= \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^n \alpha_i y_i w^Tx_i - \sum_{i=1}^n \alpha_i y_i w_0 + \sum_{i=1}^n\alpha_i\\
\frac{\delta}{\delta w_0} \mathcal{L}(w, w_0, \alpha) &= -\sum_{i=1}^n \alpha_i y_i
\end{align*}</annotation></semantics></math></p>

---

## w.r.t. $w$

<p><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><mi>ℒ</mi><mrow><mo stretchy="true" form="prefix">(</mo><mi>w</mi><mo>,</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><mi>α</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mo stretchy="false" form="prefix">∥</mo><mi>w</mi><msup><mo stretchy="false" form="postfix">∥</mo><mn>2</mn></msup><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msup><mi>w</mi><mi>T</mi></msup><msub><mi>x</mi><mi>i</mi></msub><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msub><mi>w</mi><mn>0</mn></msub><mo>+</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mfrac><mi>δ</mi><mrow><mi>δ</mi><msub><mi>w</mi><mn>0</mn></msub></mrow></mfrac><mi>ℒ</mi><mrow><mo stretchy="true" form="prefix">(</mo><mi>w</mi><mo>,</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><mi>α</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mi>w</mi><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msub><mi>x</mi><mi>i</mi></msub></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
\mathcal{L}(w, w_0, \alpha) &= \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^n \alpha_i y_i w^Tx_i - \sum_{i=1}^n \alpha_i y_i w_0 + \sum_{i=1}^n\alpha_i\\
\frac{\delta}{\delta w_0} \mathcal{L}(w, w_0, \alpha) &= w - \sum_{i=1}^n \alpha_i y_i x_i
\end{align*}</annotation></semantics></math></p>

---

## Solving

<p><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><mn>0</mn></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mi>w</mi></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msub><mi>x</mi><mi>i</mi></msub></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
0 &= \sum_{i=1}^n \alpha_i y_i\\
w &= \sum_{i=1}^n \alpha_i y_i x_i
\end{align*}</annotation></semantics></math></p>

---

## Mid-way discussion

* Notice that $\sum_{i=1}^n \alpha_i y_i = 0$
  * That implies that we need to sample evenly from both classes
  * Makes sense
* The second equation tells us that $w$ will only depend upon a linear combination of the training inputs
  * We already know this from the perceptron, but it's good to see

---

## The Dual Form

<p><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><mi>ℒ</mi><mrow><mo stretchy="true" form="prefix">(</mo><mi>w</mi><mo>,</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><mi>α</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mo stretchy="false" form="prefix">∥</mo><mi>w</mi><msup><mo stretchy="false" form="postfix">∥</mo><mn>2</mn></msup><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msup><mi>w</mi><mi>T</mi></msup><msub><mi>x</mi><mi>i</mi></msub><mo>−</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msub><mi>w</mi><mn>0</mn></msub><mo>+</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><msup><mi>w</mi><mi>T</mi></msup><mi>w</mi><mo>−</mo><msup><mi>w</mi><mi>T</mi></msup><mi>w</mi><mo>−</mo><mn>0</mn><mo>+</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mo>−</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub><msub><mi>α</mi><mi>j</mi></msub><msub><mi>y</mi><mi>i</mi></msub><msub><mi>y</mi><mi>j</mi></msub><msubsup><mi>x</mi><mi>i</mi><mi>T</mi></msubsup><msub><mi>x</mi><mi>j</mi></msub><mo>+</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>α</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
\mathcal{L}(w, w_0, \alpha) &= \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^n \alpha_i y_i w^Tx_i - \sum_{i=1}^n \alpha_i y_i w_0 + \sum_{i=1}^n\alpha_i\\
                            &= \frac{1}{2}w^Tw - w^Tw - 0 + \sum_{i=1}^n\alpha_i\\
                            &= -\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i \alpha_j y_i y_j x^T_i x_j + \sum_{i=1}^n\alpha_i\\
\end{align*}</annotation></semantics></math></p>

* Recall the equation for $w$ if that is confusing

---

## Maximizing

* Maximize $-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i \alpha_j y_i y_j x^T_i x_j + \sum_{i=1}^n\alpha_i$
* $\sum_{i=1}^N\alpha_i y_i = 0$
* $0 \leq \alpha_i \forall i \in N$

---

## Human Interpretation

* Remember that $y \in {-1, 1}$
* $-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i \alpha_j y_i y_j x^T_i x_j$
  * To maximize, we need pairs of samples from opposite classes that maximize $x_i^Tx_j$
  * For pairs of the same class, we need to minimize $x_i^Tx_j$

---

## Support Vector

* That implies that our support vectors should be similar within class
  * Which means that we want to grab a tight cluster along the decision boundary
* In the extreme, just take one support vector from each class

---

## Not for humans

* Optimizing the equation isn't for humans
  * We'll have to use an algorithm
* `Sequential minimal optimization` takes $O(N)$ to $O(N^2)$
  * Stochastic gradient descent is also used

---

## What about $w_0$?

* SMO solves for $w$
* $w_0$ can be solved for afterwards using any support vector, i:
  * $w_0 = y_i - w^TX_i$
* But in practice we average over the used support vectors:
  $w_0 = \frac{1}{N}[\sum (y_n - w^Tx_n)]$
* Speaking of "in practice"
  * We should also scale all columns to be in the unit range

---

## Soft Margin

* That all works when there is a solution
  * Meaning that points are linearly separable
* Unfortunately, that is not always the case
* So we want to add some slack to our constraint:
  * $y_i(w^T \cdot x_i + w_0) \geq 1,  \forall i \in n$

---

## Complexity

* We create a soft margin by adding an error term, making it okay if our prediction is wrong
  * $y_i(w^T \cdot x_i + w_0) \geq 1 - \xi_i,  \forall i \in n, \xi_n \geq 0$
* Add that to the minimization:
  *  $\underset{w,w_0,\xi}{\mathrm{min}}\frac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{N}\xi_i$
* C is a hyperparameter, *complexity*, which we will describe in a moment

---

## Solution

* The solution doesn't change much, but now:
  * $0 \leq \alpha_i \leq C$
* So C limits how much we can use any particular support vector
* This is what is called a `hinge loss`
  * Any point at distance from the decision boundary, $z$ where $z > m$ incurs no penalty
  * Otherwise, $\xi = \frac{m-z}{m}$, or $1-z$ when we scale m to 1

---

## More About Complexity

* Without C, two linearly inseparable points would be sampled infinitely
  * Like a non-converging perceptron
* With large C, a single point can serve as the sole support vector for a class
  * If the data is linearly separable
* With small C, we force more points to be support vectors
  * *Every* point becomes a support vector if C is small enough

---

## C and $\alpha$

* The $\alpha_i$ value in relation to C informs us about $x_i$
  * If $\alpha_i = 0$ then the point is ignored (no error)
  * If $0 \leq \alpha_i \lt C$ then $\xi_i = 0$ and the point is on the margin
  * If $\alpha = C$ then this point is on or inside of the margin, and may be misclassified

---

## Margin Errors

---

## Margin Errors

---

## Choosing C

* C is a hyperparameter
  * If the data is linearly separable, any large enough C will have the same result
  * For other data, a search is required
* This makes things more complicated when there are other hyperparameters present

---

## The Kernel Trick

* Speaking of hyperparameters...
* The kernel trick works as before
  * Replace $w^Tx_i$ with $\mathcal{k}(w, x)$
  * And $x_i^Tx_j$ with $\mathcal{k}(x_i, x_j)$ in the optimization
* So the kernel used is another parameter
  * Along with whatever options apply to the kernel

---

## SVM - Linear Kernel

$\mathcal{k}=x^Tx$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx)^2$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx + 1)^2$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx + 10)^2$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx)^3$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx + 1)^3$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx + 10)^3$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx)^4$

---

## SVM - Poly Kernel

$\mathcal{k}=(x^Tx)^5$

---

## SVM - RBF Kernel

$\mathcal{k}=exp(-\gamma \lVert x_1 - x_2 \rVert^2)$

---

## SVM - Harder margin

$\mathcal{k}=exp(-\gamma \lVert x_1 - x_2 \rVert^2)$

---

## Digits

```python
import argparse
import gzip
import os
import numpy as np
from PIL import Image
import sklearn

def load_mnist_ubyte(image_path):
    """
    Loads MNIST images from the raw ubyte files.

Args:
        image_path (str): Path to the image file (e.g., 'train-images-idx3-ubyte.gz').

Returns:
        images (numpy.ndarray)
    """
    with gzip.open(image_path, 'rb') as f:
        # Read the header: magic number (4 bytes) + num images (4 bytes) +
        # num rows (4 bytes) + num cols (4 bytes) = 16 bytes.

# Read the entire file content into a buffer
        image_data = f.read()

# The image data starts at byte 16.
        images = np.frombuffer(image_data, dtype=np.uint8, offset=16)

# We need the dimensions to reshape. We can extract them from the header bytes,
        # which are big-endian ('>'). We use struct.unpack if we were being strict,
        # but here we'll assume the standard MNIST format and calculate the dimensions
        # for a clean numpy approach.

# The number of images is in the 5th to 8th byte (4 bytes)
        num_images = np.frombuffer(image_data, dtype='>i4', offset=4, count=1)[0]
        # Rows and columns are 28x28 for MNIST, stored in bytes 9-12 and 13-16.
        # num_rows = np.frombuffer(image_data, dtype='>i4', offset=8, count=1)[0]
        # num_cols = np.frombuffer(image_data, dtype='>i4', offset=12, count=1)[0]
        num_rows = 28
        num_cols = 28

# Reshape the 1D array into a 3D array (num_images, rows, columns)
        images = images.reshape(num_images, num_rows, num_cols)
    return images

def load_mnist_labels(label_path):
    """
    Loads MNIST labels from the raw ubyte files.

Args:
        label_path (str): Path to the label file (e.g., 'train-labels-idx1-ubyte.gz').

Returns:
        labels (numpy.ndarray)
    """
    with gzip.open(label_path, 'rb') as f:
        # Read the header: magic number (4 bytes) + num items (4 bytes) = 8 bytes.
        # Skip these 8 bytes.

# Read the entire file content into a buffer
        label_data = f.read()

# The label data starts at byte 8. The data type is unsigned byte ('B' or np.uint8).
        # Labels are a 1D vector.
        labels = np.frombuffer(label_data, dtype=np.uint8, offset=8)

return labels

def evalLabelVsAll(X_train, X_test, Y_train_orig, Y_test_orig, target_label, num_mismatches=0, extra_args={}):
    """
    First sets labels for anything matching the target_label to 1 and other entries to 0.
    Then fits a perceptron to the given training data before evaluating on the given test data.
    """
    # Change all labels to 0 or 1
    print("Setting labels to 1 and 0")
    match_mask = Y_train_orig == target_label
    print(f"{match_mask.sum()} training samples match {target_label}")
    Y_train = np.where(match_mask, 1, 0)
    match_mask = Y_test_orig == target_label
    print(f"{match_mask.sum()} testing samples match {target_label}")
    Y_test = np.where(match_mask, 1, 0)

print("Creating an svm.")
    svm = sklearn.svm.SVC(**extra_args)
    print("Training the SVM.")
    svm.fit(X_train, Y_train)

print("Inference with the SVM.")
    results = svm.predict(X_test)
    matches = (results == Y_test)
    accuracy = np.sum(matches) / len(Y_test)
    print(f"Accuracy {accuracy} predicting class {target_label}")
    print(f"{Y_test.shape[0] - np.sum(matches)} failures")

if num_mismatches > 0:
        mismatches = (results != Y_test)
        mismatch_orig = X_test[mismatches]
        mismatch_truth = Y_test_orig[mismatches]
        mislabels = results[mismatches]

for i in range(min(20, mismatches.sum())):
            if mismatch_truth[i] == target_label:
                Image.fromarray((255*mismatch_orig[i].reshape((28, 28))).astype(np.uint8)).save(f"mnist_item_{i}_false_negative_{target_label}.png")
            else:
                Image.fromarray((255*mismatch_orig[i].reshape((28, 28))).astype(np.uint8)).save(f"mnist_item_{i}_false_positive_{target_label}_actually_{mismatch_truth[i]}.png")
    return accuracy, results

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "--train",
        required=True,
        help="gzip file with mnist data.")
    parser.add_argument(
        "--test",
        required=True,
        help="gzip file with mnist data.")
    parser.add_argument(
        "--train_labels",
        required=True,
        help="gzip file with mnist labels.")
    parser.add_argument(
        "--test_labels",
        required=True,
        help="gzip file with mnist labels.")
    parser.add_argument(
        "--number",
        required=False,
        type=int,
        default=0,
        help="Number to classify. This number will be class 1, others will be -1. If > 9, then this evaluations each digit separately.")
    parser.add_argument(
        "--epochs",
        required=False,
        type=int,
        default=5,
        help="Number of epochs to train.")
    parser.add_argument(
        "--train_samples",
        required=False,
        type=int,
        default=30000,
        help="Number of samples to use for training (to reduce memory consumption).")
    parser.add_argument(
        "--save_mismatch",
        required=False,
        type=int,
        default=0,
        help="The number of mismatches to save.")
    parser.add_argument(
        "--kernel",
        required=False,
        type=str,
        default='linear',
        help="linear or rbf")
    parser.add_argument(
        "--C",
        required=False,
        type=int,
        default=None,
        help="C value for svm soft margin. Defaults to 1 within scikit's implmementation")
    parser.add_argument(
        "--gamma",
        required=False,
        type=float,
        default=0.1,
        help="Gamma for the rbf kernel")
    parser.add_argument(
        "--degree",
        required=False,
        type=int,
        default=None,
        help="Degree for the polynomial kernel (try 2)")
    parser.add_argument(
        "--offset",
        required=False,
        type=float,
        default=None,
        help="Offset for the polynomial kernel (try 1)")

args = parser.parse_args()

extra_args = {}
    for arg in ['kernel', 'gamma', 'degree', 'offset', 'C']:
        if None != getattr(args, arg):
            extra_args[arg] = getattr(args, arg)

print("Loading data")
    X_train = load_mnist_ubyte(args.train)/255
    X_test = load_mnist_ubyte(args.test)/255
    Y_train_digits = load_mnist_labels(args.train_labels)
    Y_test_digits = load_mnist_labels(args.test_labels)

# Flatten everything
    print("Flattening the data")
    X_train = X_train.reshape((X_train.shape[0], -1))
    X_test = X_test.reshape((X_test.shape[0], -1))

if args.number in list(range(10)):
        evalLabelVsAll(X_train, X_test, Y_train_digits, Y_test_digits, args.number, args.save_mismatch, extra_args)
    else:
        sum_acc = 0
        y_hats = []
        for number in range(10):
            acc, y_hat = evalLabelVsAll(X_train, X_test, Y_train_digits, Y_test_digits, number, args.save_mismatch, extra_args)
            sum_acc += acc
            y_hats.append(y_hat)
        # We can't just count the overall accuracy, or each model can say that nothing belongs to its class and we get a 90%
        # Loop through all of the examples, see which is the first to claim it
        y_hats = np.array(y_hats)
        # just use the first 1 as the class prediction
        # If none of the classes were predicted, we'll end up guessing 0
        class_predictions = np.argmax(y_hats, axis=0)
        matches = (class_predictions == Y_test_digits)
        accuracy = np.sum(matches) / len(Y_test_digits)
        print(f"Overall accuracy {accuracy}")
```

---

## Digits - Linear Kernel

Accuracy 87.22% with C=1

---

## Digits - RBF Kernel

Accuracy 83.88% with C=1, $\gamma=0.1$ (so we need to tune hyperparameters)

---

## Takeaways

* SVMs do three things:
  * Sparsity in $\alpha$ makes it possible to work with large training sets
  * The large margin improves generalization to unseen points
  * Kernel trick allows the SVM to operate on non-linear space

---

## Bias and Variance

* Sparsity and the large margin can both be seen as techniques to prevent overfitting
  * Heuristics that improve performance on unseen points
* The kernel trick increases modelling power
  * So that we can fit the variance of a dataset
* Very low C simplifies a model, high C demands a tighter fit

---

## Quiz Next Class

* Mainly on HMMs
* A little bit of kernels

<!--

## Converting Outputs to Probabilities

* As with perceptrons, SVMs are just an algorithm
* But sometimes we want to classify with a probability

Next time: Do some comparisons
           Or maybe that is a good recitation topic

Compare on Digits:
  * perceptron with linear kernel and rbf
  * AdaBoost with linear regression and decision stumps
  * SVM with linear kernel and rbf

Something about shattering and vc dimensionality; how many dividing lines is this? How does this compare to perceptron? To adaboost?
Then how would we get more dimensionality?
-->