<!--
Abstract:

CS 461
Introduction to Deep Learning
Lecture 11
-->

# CS 461 - Lecture 16

## Machine Learning Principles

### Kernel Functions

Bernhard Firner

2025-10-28

---

## Review: The Kernel Trick

* Last week we saw that the percepton weight has a dual representation
* That simplified some of the math, revealing to us that we could replace a simple matrix multiplication with a kernel function
  * The so-called kernel trick
* Depending upon the kernel, this allows use to project a linear line into different spaces

---

## The Original Perceptron

* Classifications are:
  * $\hat{y} = sign(bias + \sum weight_i x$)
* In the original representation, weights are updated when we fail on example i:
  * $weight_i \leftarrow weight_i + \lambda y x_i$

---

## The New Perceptron

* In this dual representation, classifications are:
  * $\hat{y} = sign(bias + \alpha X x)$
* To avoid confusion with the training set, X,, I may refer to the test vector as t
  * $\hat{y} = sign(bias\sum(y\alpha) + y \alpha X \cdot t)$
* Alpha is a vector of how many times each training example was wrong
  * The direction, -1 or 1, is in y (it could be folded in $\alpha$ for simplicity)

---

## Two advantages

* First, during trianing we would compute $X \cdot x_i$ for each training example
  * So we can avoid repeated calculationed by precomputing $X^TX$
  * This is called the `Gram matrix`
* Second, we can replace the dot product with a kernel, $\text{k}$

---

## There are three issues

* First, the perceptron is inefficient
  * The Gram matrix includes all points
  * If there are no errors for column $i$, then $G[:,i]$ is unused
* Second, there are no margin guarantees in perceptrons
* Third, what kernel should we use?
  * Going to focus on this one today

---

## Kernels

* Cosine similarity and dot product kernels
  * They did not give any great results on text classification or digits
  * Thick digits and wordy sentences tended to overmatch
  * Brief sentences and thin digits had the opposite problem

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

</div>
</div>

---

## First Kernel

* We went over one possible kernel last time
  * It can take this non-linearly separable data...

---

## Magically Separable

* ...and transform it into an easily separable form
* If we look at $(x^2, y^2)$, things are linearly separable
  * $\ker(x, x') = (x \cdot x')^2$

---

## Application

* This is the squaring kernel, a specific instance of a polynomial kernel
* Notice that we can use any arbitrary power
  * To include the lower-order terms, we can also add an offset
  * e.g. $(X \cdot X + 1)^2$
    * This includes terms of x, y, z, etc on their own, rather than just $x^2, y^2, xy, ...$

```python
dot_product = torch.mm(X1, X2.T)
K = (dot_product + self.offset).pow(self.degree)

```

---

## Purpose of the offset

* If we went from squaring to cubing, we would lose the lower-order terms
  * The offset tries to them, so if our important features range over dimensions this would be good
* Columns are the 19x19 pixels
  * Do those pixels have higher-order features?

---

## What is being Multiplied?

* We write x and y because we are used to talking about a graph
* But here we really mean $x_1, x_2, ..., x_n$
* Any pair denote a circle across their planes, taken together we are projecting onto a hypersphere

---

## What is actually happening?

* We are still looking at per-pixel features
  * The gram matrix is made of $k(X^T \cdot X)$
* So what we are doing is improving our ability to detect in-class vs out-of-class correlations in the pixels
  * We still end up with 28x28 lines in the classifier, one for each pixel

---

## Visualizing

* Let's try to visualize the average values that end up in the Gram matrix
* We can't look at the entire thing, because it has too many entries
* So we'll just look at the average per 3x3 pixel group over the image

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

Digit 0 in-class and average polynomial Gram matrices, with order 1, 2, and 3

</div>
</div>

---

## Digits

* So let's get results on digits
  * We'll classify each letter on their own
    * Predict if '0' or not '0', '1' or not '1', etc
  * This is called "one-vs-all" classification
* For each test example we see if a classifier "owns" it; if none do we'll just guess it's a 0

---

## Polynomial Kernel Results

* Degree 1: 79%
* Degree 2: 81%
* Degree 3: 11%

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

Notice that the shape becomes thinner with degree 3.

</div>
</div>

---

## Polynomial Discussion

* Degree 1 is our simple matching kernel.
  * We know where that one fails
* Degree 2 projects the points onto a curved surface
  * Which is better, but perhaps does not capture the nuances of this data
* Degree 3 projects onto a hypersphere, which apparently has nothing to do with digits pixels

---

## Other Kernels

* There are many functions that we *could* pick
* We we probably want is some measure of *similarity*
  * Perhaps comparing to distribution?
    * Maybe a normal distribution?

---

## Gaussian kernel

* What should this kernel do?
  * Probably measure a pdf
* For a non-vector value, $g(x)=\frac{1}{\sigma\sqrt 2 \pi} exp(-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2})$

---

## More Gauss

* We can drop the outer term and change to vectors: $exp(-\frac{1}{2}(x - x')^T \Sigma^{-1}(x - x'))$
* This simplifies because $\Sigma$ will be diagonal
  * $exp(-\frac{1}{2}\sum_{j=1}^D \frac{D}{\Sigma^2_j}(x_j - x_j')^2)$

---

## Is Variance Necessary?

* Do we need the variance?
  * We're just going to do some curve fitting
  * From that perspective, the variance is a constant that we can learn
* $exp(-\sum_{j=1}^D\frac{(x_j - x_j')^2}{l})$
* $l$ is a length scaling factor

---

## Matrix Simplification

* $exp(-\sum_{j=1}^D(x_j - x_j')^2)$
* Becomes 
  * $K(x,x') = exp(-\frac{\lVert x - x' \rVert^2}{l})$

---

## Other Names

* This is the gaussian kernel if you derive it from the normal pdf
* But it is a squared exponential kernel if you look at what it does
* Or the exponentiated quadratic kernel because of the form
* Or a radial basis function
  * Because $x-x'$ is translation invariant
  * And $x-x'$ can be thought of as the radius

---

## Uses

* The rbf/gaussian/EQ/SE kernel has wide uses
  * And is how it also ended up with multiple names
* The $l$ value can be thought of as the `bandwidth` of the function
  * Basically indicates a weighting for similarity over distance

---

## On Digits

* Again, we'll look at the average kernel value over 3x3 pixel groups
* Rather than dividing, computers like to multiply
  * So we replace $l$ with its inverse, $\gamma$

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

Digit 0 in-class and average rbf Gram matrices, with order gamma = 0.1,0.2,0.3,0.4

</div>
</div>

---

## Results

---

## RBF Advantages

* Classifying using RBF with a learned weight is a bit like hard clustering in K-Means
  * The "centroid" comes from the statistics of the training classes
* But, as with clustering, what if we should be modeling multiple classes?
  * With RBF, choosing a constant value for the distance creates a clustering algorithm
  * But what about using multiple kernels to make new features?

---

## Combining Kernels

* Perhaps the rbf kernel and the polynomial kernel are finding different features
* Predictions are currently
  * $\hat{y} = sign(bias + \sum_{i=1}^n \alpha_i y_i k(X_i, t))$
* Why not:
  * $\hat{y} = sign(bias + \sum_{i=1}^n \alpha_i y_i \sum_{j=1}^Jk_j(X_i, t))$

---

## Combining Features

* And if we can make new features, why not get fancy?
  * What about temporally shifted kernels?
    * If we know that our features are correlated (like pixels) why not compare adjacent ones?
* $k(X_i, X_j) = X_i[0:n-1] \cdot X_j[1:n]$

---

## Limitations?

* In fact, why not go crazy?
  * Because these computations come with a cost
* The gram matrix requires kernel computation!

---

## Gram Matrix Cost

* A is $m \times k$, i.e. m rows of k features
* If we compute $G=A^TA$
  * with m data points and k features, this is a $kxk$ matrix
  * takes $O(k^2m)$ to compute (there are optimizations, but this hurts)
  * A is $m\times k$, $A^T$ is $k \times m$

---

## Memory for Speed

* Alternatively, computer $G=AA^T$
  * Steps are $O(m^2k)$
  * But now $G$ will be $m \times m$ in size, which is huge
  * Prediction is slightly slower
    * Multiply over all data points rather than over features

---

## So let's talk sparsity

* Remember how we mentioned that the perception was inefficient?
* $\alpha$ is probably going to be sparse
  * So we can find a way to do fewer matrix operations
  * This is the idea behind *support vector machines*

---

## Review

* We'll finish with kernels after talking about SVMs
* Quiz next Thursday will cover through today
  * Leave SVMs for the quiz after that
  * This includes the hidden markov model content from 13 and 14
* So let's do some review questions

---

## Practice Questions

A fair and unfair coin are being flipped. The fair coin has equal probability of heads and tails of 0.5.
The unfair coin is heads with probability 0.9. The transition from fair to unfair is with probability 0.2.
The probability of transitioning from unfair to fair is also 0.2.
What is ABO?

</div>

---

## Practice Questions

Which of these statements about about a hidden Markov model with 3 hidden states and a vocabulary of 5 observable tokens is **true**?

a. The transition matrix, A, is size 3x5.  
b. The emission matrix, B, is size 5x5.  
c. The parameters of the HMM can be trained with the EM algorithm.  
d b and c are both true.

</div>

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Draw the emission matrix, B.

</div>

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Draw the transimission matrix, B.

</div>

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><mo>=</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>a</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>b</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>c</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>d</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mspace width="1.0em"></mspace></mtd></mtr></mtable><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">
B=
\begin{matrix}
\\
\\
a \\
b \\
c \\
d \\
\quad
\end{matrix}
\begin{pmatrix}
 0.5  & 0.5 \\
 0.5  & 0.5 \\
 0.5  & 0.5 \\
 0.5  & 0.5
\end{pmatrix}</annotation></semantics></math></p>

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Draw the transimission matrix, A.

</div>

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Draw the transimission matrix, A.

</div>

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>A</mi><mo>=</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>a</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>b</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>c</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mi>d</mi></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mspace width="1.0em"></mspace></mtd></mtr></mtable><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>1.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.0</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">
A=
\begin{matrix}
\\
\\
a \\
b \\
c \\
d \\
\quad
\end{matrix}
\begin{pmatrix}
  0.5  & 0.5 &  0.0  & 0.0 \\
  0.5  & 0.0 &  0.5  & 0.0 \\
  0.5  & 0.0 &  0.0  & 0.5 \\
  1.0  & 0.0 &  0.0  & 0.0
\end{pmatrix}</annotation></semantics></math></p>

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Using your transmission matrix, A, solve for the stationary state, $\pi$.

</div>

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Using your transmission matrix, A, solve for the stationary state, $\pi$.

</div>

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mi>π</mi><mo>=</mo><mi>a</mi><mo>+</mo><mi>b</mi><mo>+</mo><mi>c</mi><mo>+</mo><mi>d</mi><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.5</mn><mi>a</mi><mo>+</mo><mn>0.5</mn><mi>b</mi><mo>+</mo><mn>0.5</mn><mi>c</mi><mo>+</mo><mi>d</mi><mo>=</mo><mi>a</mi></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.5</mn><mi>a</mi><mo>=</mo><mi>b</mi></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.5</mn><mi>b</mi><mo>=</mo><mi>c</mi></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.5</mn><mi>c</mi><mo>=</mo><mi>d</mi></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
&\pi=a+b+c+d=1 \\
&0.5a + 0.5b + 0.5c + d = a \\
&0.5a = b \\
&0.5b = c \\
&0.5c = d
\end{align*}</annotation></semantics></math></p>

</div>

* Notice that each new state is half as likely as the previous

---

## Practice Questions

A fair coin is being flipped, and you will stop flipping it when you successfully flip 3 heads in a row.
Using your transmission matrix, A, solve for the stationary state, $\pi$.

</div>

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.125</mn><mi>a</mi><mo>=</mo><mi>d</mi></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.25</mn><mi>b</mi><mo>=</mo><mi>d</mi></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mn>0.5</mn><mi>c</mi><mo>=</mo><mi>d</mi></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mo>→</mo><mn>8</mn><mi>d</mi><mo>+</mo><mn>4</mn><mi>d</mi><mo>+</mo><mn>2</mn><mi>d</mi><mo>+</mo><mi>d</mi><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mo>→</mo><mi>d</mi><mo>=</mo><mfrac><mn>1</mn><mn>15</mn></mfrac></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
&0.125a = d\\
&0.25b = d\\
&0.5c = d\\
&\rightarrow 8d + 4d + 2d + d = 1\\
&\rightarrow d = \frac{1}{15}\\
\end{align*}</annotation></semantics></math></p>

</div>

---

## Practice Questions

Use  the stationary state, $\pi$, to find the average game length.

</div>

* $\pi = (8/15, 4/15, 2/15, 1/15)$
* To find the expected game length, we first remove the transition into the $a$ from $d$.
  * We added that transition to satisfy the markov property
* So the expected number of flips until 3 heads is 14

---

## Practice Questions

Use  the stationary state, $\pi$, to find the average game length.

</div>

* Feel free to verify:

```python
import numpy
import random

results = []

for _ in range(10000):
    count = 0
    sum = 0
    while sum < 3:
        val = round(random.random())
        sum = val*sum + val
        count += 1
    results.append(count)

print(numpy.mean(results))

```

---

## Practice Questions

When is a HMM **least effective** at predicting hidden states from observed states?

a. When hidden states have distinct entries in the rows of the emission matrix.
b. When the transition probabilities make it very likely to remain in the current state.
c. When transition probabilities are all near 0.5.
d. When the transition matrix is square.

</div>