<!--
Abstract:

CS 461
Introduction to Deep Learning
Lecture 11
-->

# CS 461 - Lecture 14

## Machine Learning Principles

### Kernel Methods

Bernhard Firner

2025-10-22

---

## Suggested Reading

* Murphy (Machine Learning: A Probabilistic Perspective)
  * Intro to chapter 14, 14.4 for next class
* Flach
  * Chapter 7.2 for next class

---

## Structured Data

* ML is all about finding patterns in data
* With Markov Models we began dealing with structured data
  * Converting sentences into descriptive numbers destroys the patterns in the words
  * By working with the raw data (e.g. emails) we can extract more information

---

## More Structure

* Hidden Markov Models are great for sequential data
  * We've seen some use-cases, but there are more
  * Sequential behavior modelling, for example
* But let's forge onwards to data that has even more structure

---

## Image Data

* Images clearly have a lot of structure
  * Which is good, because the total space of all images is huge
  * A 256x256 RGB image with 256 values per color is huge
    * $2^{24}$ possible values for each pixel gives times $2^{40}$ possible 256x256 images

---

## Images Continued

* Most "possible" images won't show up, and the majority would just be noise
  * But the fact that we recognize noise as such is because of image structure
* The sparseness of the space will pose challenges as well
  * With clustering or nearest neighbor approaches, for example

---

### Early Datasets

* Making progress with images is a "recent" thing
  * Meaning that most results are within-your-lifetime new
* Impossible before computers, difficult in early days
* Real progress was only made once a large, standard dataset was created

---

## MNIST DIGITS

* Hand written numeric digits converted to 28x28 black and white images
  * Half drawn by U.S. Census Bureau employees, other half by high school students
* 60,000 training images
* 10,000 validation
* Equally distributed over classes 0-9

---

## First 100 Train and Test

</div>

---

## Digits Comments

* Simple by today's standards
  * Tiny images
  * Black and white
  * Digits are all neatly centered

---

## Applying ML to MNIST

* The dataset is so carefully assembled that anything can be used
  * Even a decision tree; the digits are very carefully centered
* This obfuscated the differences between different techniques

---

## Sensibilities

* We could apply adaboost to the dataset
  * Each of the 28*28 pixels would be a feature column
  * We would get decent results
* But we know that they wouldn't generalize to digits in different positions

---

## Sensibilities

* We could also apply hidden markov models
  * Hidden states would be the pixel locations
* This just turns into a per-pixel mean estimation with a bit of tolerance for shifting pixels
  * Almost reduces to clustering with 28x28 parameters per cluster
* Would also work okay-ish

---

## Sensibilities

* But we want a method that would actually be robust in the real world
* So where do we start?

---

## Matching Detector

* We could just drop one letter on top of another and check to see how many pixels match
  * Sounds reasonable; 8's should line up better with other 8's than with 7's
* Just perform $X_i^TX_j$ for I in the training data and J in the testing data

---

## Some Details

* Some letters are large and blocky
  * Their intersection with other letters is always high
* So normalize by the product of the norms $sqrt(\sumx_i^2)$
  * The intersection of digit pixels must be less than the union
* Biases us away from a mostly white image matching everything

---

## The Code

```python

import argparse
import gzip
import os
import numpy as np
from PIL import Image

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

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.")

args = parser.parse_args()

X_train = load_mnist_ubyte(args.train)/255
    X_test = load_mnist_ubyte(args.test)/255

for j in range(args.matches):
        max_similarity = 0
        idx = -1
        for i in range(60000):
            similarity = np.sum(X_train[i].T@X_test[j])/(np.linalg.norm(X_train[i]) * np.linalg.norm(X_test[j]))
            if similarity > max_similarity:
                max_similarity = similarity
                idx = i

print(f"{j} similarity {max_similarity}")
        Image.fromarray((255*X_train[idx]).astype(np.uint8)).save(f"mnist_match_{j}_train.png")
        Image.fromarray((255*X_test[j]).astype(np.uint8)).save(f"mnist_match_{j}_test.png")
```

---

## Intuition

* This technique works very well with typeset fonts
  * But human writing has a lot of variety
* Small rotations of a letter make it difficult to match, thick digits still match too much
* We could go down a rabbit hole of rotating, scaling, and thinning our digits
  * That way lies madness

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

</div>
</div>

---

## Next Try

* That was okay, but not great
* The matching detector is a type of `exemplar` technique
  * Remember, those are techniques where the original data sticks around
  * KNN is another example
* Parametrizing the data could be better, but also more difficult
  * For digits, that could be representing each one as a series of strokes, as in a vector drawing

---

## Similarity Scoring

* `exemplar` techniques use similarity scoring for classification
* How can we formalize similarity?
  * $k(x, x') \geq 0$ and $k(x, x')$ is real valued
  * That function is a `kernel function`
    * It would be nice if $k(x, x') = k(x', x)$ for reasons we'll see later

---

## Linear Kernel

* The matching detector, $X_i^TX_j$, is a linear kernel
  * When we normalized, we turned it into the `cosine similarity`
  * $cos\theta = \frac{x\cdot y}{||x||_2\cdot ||y||_2}$
  * Different from Euclidean distance because it doesn't depend upon the length of x and y
* Generally speaking, linear kernels are good when $X$ is highly separable
  * In the case of digits, this is not the case

---

## Kernel Methods

* Kernel methods are all similarity techniques
  * But there are many ways to write a kernel function
* And some of these kernels are particularly suited to structured data

---

## String Kernels

* As an example, let's compare two strings

<pre>
Almost simultaneously, with a mighty volition of ungraduated, instantaneous
swiftness, the White Whale darted through the weltering sea.
</pre>

<pre>
In this attitude the White Whale now shook the slight cedar as a mildly cruel
cat her mouse.
</pre>

---

## Challenge

* They both have "White Whale", so a human would notice a similarity
  * But they are different lengths, with plenty of different words
  * How can we compare them?
* We could build a probabilistic model
  * Influenced by the training corpus
  * We want something that can be done pair-wise

---

## Defining a Metric

* So let's define the string similarity as the number of substrings in common
  * Substring being a single word or word pairs, etc
* This works for any pair of strings
  * And these don't have to be English sentences, they could be DNA, RNA, etc

---

## String Distance

* The matched words are:
  * 'a', 2*'the', 'White', 'Whale'
* So $K(x_1,x_2)$, the similarity of the first sentence to the second, is 5
* The similarity is also symmetric, since $K(x_1,x_2) = K(x_1,x_2)$

---

## Types of Kernels

* That was a `bag of words` kernel
  * If we restricted comparisons to be words of length $k$, that is a $k$-spectrum kernel
* By controlling the similarity metric, we can influence what features are used for similarity

---

## Back to Images

* So how will any of that help with image comparison?
  * First, notice that we can create a new distance metric
  * $Distance = 1 - similarity = 1 - k(x_1,x_2)$
* If we use a naive distance, such as pixel differences, techniques won't work
  * e.g. KNN on the digits dataset will be terrible

---

## "Better" distances

* What algorithms used distances?
  * Clustering, obviously
  * Also the perceptron, which simply adjusted a line closer to any misclassified points

---

## Perceptron

* Recall that the perception was a line that estimates a class using the sign function
  * $\hat{y} = sign(bias + \sum weight_i x_i$)
* Every time the perceptron is wrong, we adjust the bias and weights in the "correct" direction by a learning rate, $\lambda$
  * $weight_i \leftarrow weight_i - \lambda y x_i$

---

## Steady State

* The perceptron's line should eventually divide any linearly separable data
* What's the relevance here?
  * The parameters adjust via a step independent of anything in the observations, X
  * But if we gave it a single X value to learn, it would eventually converge on a line that matched X

---

## Exemplar-Based

* That means that the final weights are actually made out of a blend of the parameters of the training data
* The numbers in $x_i$ won't matter, only their similarity and difference with members of the same and different classes
  * The perceptron's decision boundary ends up between the two classes of data
* From this, we can make a classifier based upon similarity, even if the items in X aren't numbers

---

## Details

* Let's wait on the details unti next class
  * No math before quiz
* But let's look at some possible training sentences

---

## Moby Dick

<pre>
Almost simultaneously, with a mighty volition of ungraduated, instantaneous
swiftness, the White Whale darted through the weltering sea.

In this attitude the White Whale now shook the slight cedar as a mildly cruel
cat her mouse.
</pre>

---

## Pride and Prejudice

<pre>
The evening altogether passed off pleasantly to the whole family.

Elizabeth blushed and blushed again with shame and vexation.
</pre>

<!--

Motivate structured data

Talk about mnist

mnist from https://huggingface.co/datasets/ylecun/mnist/tree/main

Show sliding window match

This brings up similarity searches
  Nonparametric models don't learn the parameters of a function, but rather try to learn the function by doing a similarity match from new points to known points