# CS 530 - Lecture 17

## Approximation

Bernhard Firner

2026-03-31

---

## Schedule

* We've covered some basics of AI
  * Agents and environments
  * Tabular reinforcement learning
    * To evaluate policies
    * To learn policies
* We have around a month to go on a whirlwind tour of techniques and make progress on projects

---

## AI Overview

* A big chunk of AI is something called "function approximation"
* This takes many forms
  * We could be estimating our current state, as in TrailNet or the Cognitive Mapping work
  * Or we could estimate the action-utility function, Q, as in AlphaGo
  * Or we could go directly to actions, as in DAVE or AlphaGoZero

---

## State Estimation

* State estimation isn't new to us
  * We looked at the discrete case with Markov model
  * Continuous case with Kalman filters and particle filters
* If you remember the TrailNet paper, you'll recall that Kalman filters combined multiple estimates
  * At the time I mentioned that fusion was a big advantage of Kalman filters

---

## For The Projects

* For the projects, I expect some kind of estimation
* You can decouple the "real world" part from the policy part
* For example, you can emulate a drone with simple 2D and simulated GPUs and IMU data
  * Do policy learning on that
  * Then show some perception result on satellite data to justify that you could, for example, segment roads, houses, forests

---

## Learning in RL

* In general, we can apply most learning techniques with reinforcement learning
* For example, Monte Carlo search could turn into:
  * $w \leftarrow w + \alpha [G_t - \hat{v}(S_t, w)]\nabla \hat{v}(S_t, w)$
* Where $w$ are the weights of a model that predicts the value of a state
  * The interpretation here is that we use the gradients of the error to update weights after seeing a gain

---

## Too Vague!

* That's a rather vague description
* What techniques should we use?
* And can you learn them quickly enough to put into your projects?

---

## What ML Techniques?

* Machine learning, and the subset of it that we call deep learning, are large
* It is difficult to pick the pieces that are most important
  * So we'll begin with the simplest

</div>

---

## The Simplest

* By simplest, I mean the simplest to apply
  * This course is meant to focus on applications
  * So we'll begin with clustering and kernel techniques
* It would appear that tabular data is simpler than continuous data
  * I will try to convince you that this isn't as true as it once was

---

## Fast Learning

* Let's say that you want a robot to navigate an unseen environment
* In [TrailNet](https://arxiv.org/abs/1705.02550), they used a large amount of training data
  * This allowed their drone to estimate its position on the trail
* What if we want to navigate an unstructured environment, using reinforcement learning?
  * We could assign rewards and penalties based upon the time it takes to make progress to a goal, for example

---

## Fast Learning

* That was (roughly) the problem statement in [Fast Incremental Learning for Off-Road Robot Navigation](https://arxiv.org/abs/1606.08057)
* Instead of RL, they used a human to provide rapid labels, but the idea is similar
  * You just need a robot durable enough to bump into things
  * Or use your current rate of motion as part of the reward

---

## Cost Maps

* If we think about our maze and racetracks, a camera is a method of spying on future states
* If we can recognize walls and a goal, then we can begin estimating Q before we reach locations
* It seems natural to use lidar or a stereo camera if we want to recognize obstacles

---

## Stereo Cost Map

</div>

---

## Insufficient

* It turns out that any sensor on its own is insufficient for this task
  * Consider a snowy field
  * It is certainly *flat*, but it may not be *traversible*
* So a good agent must perceive the semantics of its surroundings
  * This sounds like we need to collect a bunch of training data, right?

---

## Lessons from AlexNet

* The [AlexNet paper](https://proceedings.neurips.cc/paper/2012/hash/c399862d3b9d6b76c8436e924a68c45b-Abstract.html) was published in 2012, but it holds some enduring lessons
* An important one is that features learned by neural networks generalize very well
  * What does that mean?

---

## Distances

* Column 1 shows five ILSVRC2010 test images
* The rest of the rows are the six images whose feature vectors have the smallest Euclidean distance

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

<img style="width: 80%" class="r-stretch" src="./figures/AlexNetFigure4Right.png" />
<br/>
<small>See Figure 4 of the original paper.</small>

</div>
</div>

---

## Universal Feature Vectors

* Instead of training from scratch, we can take advantage of this serendipitous facet of deep learning
* What are features?
  * Just a vector of numbers
  * Suddenly our methods that require tabular or unstructured inputs are fine again
* But let's use an example to demonstrate that these features vector are useful

---

## Fast Incremental Learning

* The paper takes advantage of this by training a new classifier using the features of something trained on ImageNet
* The new labels come from a human, but they didn't have to

</div>

---

## **FAST**

* The authors said *fast*
* No time for bounding boxes, just scribbles
* The features should be roughly the same for different patches, so do we need to mark large areas?

---

</div>

---

## Magic

* This is a form of transfer learning, where something learned in one task carries over to a second one
* This transferability works in multiple domains
  * Image features used in visual tasks
  * Word embeddings us in language translation
* Let's spend a moment to find an intuition of what is happening

---

## Memory Networks

* One way to think of neural networks is that they are lossy memory systems
* Which prompts the question: what is a memory system?
* We want to retrieve an original value using something that references it, a key

---

## Simple example

* Let's say we have a 4 pixel image
* Can we make a system where the entire image can be reconstructed from just a single pixel?
  * Here, the image is the value and the pixel is the key

---

## Weight Matrix

* An artificial neural network would have multiple layers of neurons
  * Each would perform some math, such as the linear layer: $y = \beta + \omega X$
  * $\beta$ is a single value and $\omega$ is a vector
  * If we want multiple outputs, then $\beta$ becomes a vector and $\omega$ becomes a matrix
* But let's begin with a system that only uses that $\omega$
  * Our goal is to retrieve images given a key

---

## Weight Matrix

* We'll use $xx^T$ to create a weight matrix
* $xx^T$ has a row to predict each pixel's value given an input key
  * And note, this is $xx^T$ if x is 4x1, $x^Tx$ is 1x4, so how you store the image matters

---

## Removing the diagonal

* We don't want to use each pixel to represent itself
  * Set the diagonal to 0

---

## Prediction

* Let's say we only get the top row of pixels in $X_{t}$
  * Can we retrieve the bottom row with $w^TX_{t}$?

---

## Prediction

* This doesn't *quite* work
  * What if we simplify all weights to 1 or -1?
  * This basically changes this to a classification problem

---

## 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 flattenAndPolarize(X):
    """Convert the image into value -1 and 1"""
    flattened = X.reshape(-1, 1)
    positive_mask = np.sign(flattened - 0.5) == 1
    polarized = np.where(positive_mask, 1, -1)
    return polarized

def createWeightMatrix(X):
    # This is the outer product
    weight_matrix = np.dot(X, X.T)
    # We remove the identity because predictions for pixel i shouldn't use pixel i
    np.fill_diagonal(weight_matrix, 0)
    return weight_matrix

def retrieve(weights, X, max_steps=100):
    """Retrieve a sample from the Hopfield weights and the partial image."""
    cur_state = X.copy()
    num_features = X.size

for _ in range(max_steps):
        # Remember the previous state so we can check for convergence
        next_state = np.sign(weights.T @ cur_state)

# Check for convergence (no change in state)
        if np.array_equal(cur_state, next_state):
            # print(f"Converged after {_ + 1} iterations.")
            break
        cur_state = next_state

return cur_state

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "--train",
        required=True,
        help="gzip file with mnist data.")
    parser.add_argument(
        "--index",
        required=False,
        type=int,
        default=0,
        help="Index to convert and retrieve")

args = parser.parse_args()

print("Loading data")
    X_train = load_mnist_ubyte(args.train)/255

# Polarize the first sample
    polarized = flattenAndPolarize(X_train[args.index])
    W = createWeightMatrix(polarized)
    print(f"Image shape is {X_train[args.index].shape}")
    print(f"Weight matrix size is {W.shape}")
    masked = polarized.copy()
    print(f"masked size is {masked.size}")
    masked[int(masked.size/2):].fill(0)
    retrieved = retrieve(W, masked)

Image.fromarray((255*((polarized+1)/2).reshape((28, 28))).astype(np.uint8)).save(f"hopfield_test_image_{args.index}.png")
    Image.fromarray((255*((masked+1)/2).reshape((28, 28))).astype(np.uint8)).save(f"hopfield_masked_image_{args.index}.png")
    Image.fromarray((255*((retrieved+1)/2).reshape((28, 28))).astype(np.uint8)).save(f"hopfield_retrieved_image_{args.index}.png")
```

---

## Examples

---

## Combined Weights

* We want to mix weights for multiple images
  * And then query with unseen inputs
  * So we will simply sum the weights
* The reconstruction will be wrong after a single multiply, so we'll just repeat it and hopefully it will converge
  * $sign(w^Tsign(w^Tsign(w^Tsign(w^Tsign(w^TX_{t})))))$

---

## Test with 2 Images

Works great!

---

## Test with 10

* Some garbage
  * It turns out that this doesn't work if the images aren't linearly separable

---

## Internals

* Starts off looking like a 3
  * But some of those pixels are correlated with a 5
  * After several rounds of multiplications, it is a combination of the two

---

## Hopfield Network

* That was an older idea, called a Hopfield network
* But it gives us an intuition for what is happening in a modern neural network
* Let's say we have a classifier
  * The weights being learned must be some representation of the original inputs

---

## Compressed Data

* Neural network have parameters far fewer than features in their training data
* But if feature vectors contain something unique to an image class, the information must still be there
* So we can assume that feature vectors are a compressed representation of input images
  * That's what makes the technique in the fast incremental learning paper work

---

## Clustering

* The AlexNet results, and the results of the paper, are basically using clustering
  * Either similarity to a single feature vector
  * Or similarity to a set of feature vectors that correspond to obstacle or path

---

## Kernel Methods

* Clustering is a linear operation
* So what if we need to learn a nonlinear response?
  * Perceptrons and Support Vector Machines can work with small amounts of data
* Perceptrons can learn online (and are used in CPU branch prediction, for example)
* SVMs have optimal decision boundaries, so usually generalize well

---

## Goals

* We'll go through some concrete examples to quickly bootstrap learning
* Final homework will be to use learning to solve a maze-like problem
  * This should be applicable to most of your projects
* The final week we'll do project presentations

---

## Pretrained Features with SVM

* This is example code to quickly train a detector using pretrained DNN features

```python
#!/usr/bin/python3

# This is an example demonstrating the reuse of a model as a feature extractor.
# This demo covers dataset collection, SVM training, and object detection.

import argparse

import numpy
import random
import torch
import torchvision
# Open CV for the GUI
import cv2

from PIL import Image

from sklearn import svm
import os

def run_demo():
    """Demo data collection and object detection."""
    parser = argparse.ArgumentParser(
        description="SVM Classifier demo")
    parser.add_argument(
        '--class_model',
        type=str,
        #default='efficientnet_v2_s',
        default='mobilenet_v3_small',
        help='Name of the model to use.')
    parser.add_argument(
        '--bbox_size',
        type=int,
        default=200,
        help='Default bounding box size')
    args = parser.parse_args()

# See if we've already gotten the model
    model_path = args.class_model + ".checkpoint"
    if os.path.exists(model_path):
        classifier = torchvision.models.get_model(args.class_model, weights=None)
        checkpoint = torch.load(model_path, map_location=torch.device('cpu'))
        classifier.load_state_dict(checkpoint['classifier_params'], strict=True)
    else:
        classifier = torchvision.models.get_model(args.class_model, weights="DEFAULT")

torch.save(
            { "classifier_params": classifier.state_dict() },
            model_path)

classifier.eval()
 
    # This will print out the entire model
    print(classifier)

# We will need to preprocess images with preprocessor.transforms
    #preprocessor = torchvision.models.EfficientNet_V2_S_Weights.IMAGENET1K_V1.transforms()
    preprocessor = torchvision.models.MobileNet_V3_Small_Weights.IMAGENET1K_V1.transforms()
    #compiled_classifier = torch.compile(classifier.features)

# Make a vectorize function by ignoring the end of the network
    def vectorize(image):
        with torch.no_grad():
            pre = preprocessor(image).unsqueeze(0)
            return classifier.features(pre).numpy()
            #return compiled_classifier(pre).numpy()

# Some display constants
    text_yellow=(0, 255, 255)
    text_blue=(255, 0, 0)
    text_green=(0, 255, 0)
    text_red=(0, 0, 255)

# Open the webcam
    video = cv2.VideoCapture(0)

# Check and set some properties
    # See the OpenCV docs for a list of properties:
    # https://docs.opencv.org/4.11.0/d4/d15/group__videoio__flags__base.html#gaeb8dd9c89c10a5c63c139bf7c4f5704d
    # or samples in OpenCV repository: python/samples/video.py and python/samples/video_v4l2.py
    vid_width = video.get(cv2.CAP_PROP_FRAME_WIDTH)
    vid_height = video.get(cv2.CAP_PROP_FRAME_HEIGHT)
    # Sample bboxes will be 224 pixels wide. We want to always be able to fit two 224x224 boxes in an image,
    # so set a minimum frame size of 960x720 pixels
    if vid_height < 720:
        video.set(cv2.CAP_PROP_FRAME_WIDTH, 960)
        video.set(cv2.CAP_PROP_FRAME_HEIGHT, 720)
    vid_width = int(video.get(cv2.CAP_PROP_FRAME_WIDTH))
    vid_height = int(video.get(cv2.CAP_PROP_FRAME_HEIGHT))

# Helper to get a bounding box
    def centerToBox(x, y, width):
        safe_x = int(min(vid_width - width//2 - 1, max(x, width//2)))
        safe_y = int(min(vid_height - width//2 - 1, max(y, width//2)))
        return safe_x - width//2, safe_y - width//2, safe_x + width//2, safe_y + width//2

# Remember the current UI state.
    # waiting: the user needs to draw a bounding box and start training
    # tracking: vit is being used to track and label new data
    # classifying_fixed: classifying with the SVM, using a single box
    # quitting: the user wants to exit
    mode = "waiting"

# OpenCV's waitKey function returns not just the key, but also any keyboard modifiers. This
    # means that the returned value cannot be compared to just the key.
    def isKey(cvkey, key):
        return key == (cvkey & 0xFF)

# Keep going until capture fails or the user quits
    has_frame, frame = video.read()
    if has_frame:
        # Flip the frame so it looks like mirror
        frame = cv2.flip(frame, 1)

positive_examples = []
    negative_examples = []

if not has_frame:
        print("Capture failures, exiting!")
        exit(1)

while mode != "quitting" and has_frame:
        display_frame = frame.copy()
        #frame_h, frame_w, _ = display_frame.shape
        if mode == "waiting":
            cv2.putText(display_frame, "Press 't' to collect training data in a bbox.", (0, 25), cv2.FONT_HERSHEY_SIMPLEX, 1, text_yellow)
            left, top, right, bottom = centerToBox(vid_width//2, vid_height//2, args.bbox_size)
            cv2.rectangle(display_frame, (left, top), (right, bottom), text_yellow, 2)
        elif mode == "training":
            left, top, right, bottom = centerToBox(vid_width//2, vid_height//2, args.bbox_size)
            cv2.rectangle(display_frame, (left, top), (right, bottom), text_yellow, 2)

cv2.putText(display_frame, "Press any key to stop training.", (0, 45), cv2.FONT_HERSHEY_SIMPLEX, 1, text_yellow)

# Add the found area to the positive examples and select something else for a negative example
            # We don't need to store the images, only the feature vectors
            #positive_image = numpy.moveaxis(frame[top:bottom, left:right, :], source=-1, destination=0)
            positive_image = frame[top:bottom, left:right, :]
            positive_image = cv2.cvtColor(positive_image, cv2.COLOR_BGR2RGB)
            positive_image = Image.fromarray(positive_image)
            # Remember this positive example
            positive_examples.append(vectorize(positive_image)[0].flatten())
            # Won't need the image anymore
            del positive_image

# Make a negative example from a different part of the image
            rand_x = random.uniform(0, vid_width - args.bbox_size/2)
            rand_y = random.uniform(0, vid_height - args.bbox_size/2)
            neg_left, neg_top, neg_right, neg_bottom = centerToBox(rand_x, rand_y, args.bbox_size)
            # Keep regenerating until we find a box that doesn't overlap
            while (not (neg_left > right or neg_right < left or neg_top > bottom or neg_bottom < top)):
                rand_x = random.uniform(0, vid_width - args.bbox_size/2)
                rand_y = random.uniform(0, vid_height - args.bbox_size/2)
                neg_left, neg_top, neg_right, neg_bottom = centerToBox(rand_x, rand_y, args.bbox_size)

cv2.rectangle(display_frame, (neg_left, neg_top), (neg_right, neg_bottom), text_red, 1)
            negative_image = frame[neg_top:neg_bottom, neg_left:neg_right, :]
            negative_image = cv2.cvtColor(negative_image, cv2.COLOR_BGR2RGB)
            negative_image = Image.fromarray(negative_image)
            negative_examples.append(vectorize(negative_image)[0].flatten())
            # Won't need the image anymore
            del negative_image
        elif mode.startswith("classifying"):

left, top, right, bottom = centerToBox(vid_width//2, vid_height//2, args.bbox_size)

input_image = frame[top:bottom, left:right]
            input_image = cv2.cvtColor(input_image, cv2.COLOR_BGR2RGB)
            input_image = Image.fromarray(input_image)
            features = vectorize(input_image)[0].flatten()
            if features.ndim < 2:
                features = features.reshape(1, -1)
            predictions = clf.predict(features)

# Track which boxes had the target if we are tracking
            if predictions[0] == 0:
                rect_color = text_yellow
            if predictions[0] == 1:
                rect_color = text_green

cv2.rectangle(display_frame, (left, top), (right, bottom), rect_color, 2)

cv2.putText(display_frame, f"Predictions: {predictions}", (0, 25), cv2.FONT_HERSHEY_SIMPLEX, 1, text_yellow)
            cv2.putText(display_frame, "Press 't' to train.", (0, 45), cv2.FONT_HERSHEY_SIMPLEX, 1, text_yellow)

cv2.imshow('Label Demo', display_frame)

key = cv2.waitKey(1)
        if key > 0:
            if isKey(key, ord('q')):
                print("Quitting")
                mode = "quitting"
            elif isKey(key, ord('t')):
                if mode != "training":
                    display_frame = frame.copy()
                    cv2.putText(display_frame, "Training with data in bbox", (0, 25), cv2.FONT_HERSHEY_SIMPLEX, 1, text_yellow)
                    cv2.imshow('Label Demo', display_frame)
                    mode = "training"
            elif mode == "training":
                # Stop collecting training data and train the svm, then switch to classifying mode.
                labels = [1] * len(positive_examples) + [0] * len(negative_examples)
                kernel = "poly"
                clf = svm.SVC(kernel=kernel, coef0=1.0, gamma=1.0, degree=2, C=10)
                clf.fit(positive_examples + negative_examples, labels)
                mode = "classifying"

# Grab the next frame
        has_frame, frame = video.read()
        if has_frame:
            # Flip the frame so it looks like mirror
            frame = cv2.flip(frame, 1)

# Cleanup
    video.release()
    cv2.destroyAllWindows()

if __name__ == '__main__':
    run_demo()
```