SaturnTsen

Appearance

2 Image Classification

About 4317 wordsAbout 14 min

notescomputer-vision

2024-12-20

Summary: Image Classification, KNN, Hyperparameters, Curse of Dimensionality, Universal Approximation.

@Credits: EECS 498.007 | Video Lecture: UM-CV

Personal work for the assignments of the course: github repo.

Notice on Usage and Attribution

These are personal class notes based on the University of Michigan EECS 498.008 / 598.008 course. They are intended solely for personal learning and academic discussion, with no commercial use.

For detailed information, please refer to the complete notice at the end of this document

Intro

Problem: The semantic gap between low-level features and high-level concepts, and the computers do not have the intuition to understand the image.

Challenges

  • intra-class variation
  • fine-grained categories
  • background clutter
  • illumination change: lighting and shadow conditions
  • deformation: the object may have various positions
  • occlusion: the object may be partially covered

Scientific Applications

  • medical imaging
  • galaxy classification
  • object detection: classify localized objects
  • image captioning: generate a sentence to describe the image, which can be seen as a classification problem of the next-word prediction
  • Playing Go: classify the next move

An Image Classifier?

def classify(image):
    # Some magic here?
    return label

Approaches: find edges, corners, and other features based on human knowledge... but it is not scalable.

Machine Learning: Data-driven Approach

  1. Collect a dataset of images and labels
  2. Use machine learning to train a classifier
  3. Evaluate the classifier on new images
def train(images, labels):
    # Machine learning
    return model
def predict(model, test_image):
    # Use model to predict labels
    return label

Datasets

The most basic datasets: MNIST, CIFAR-10

  • MNIST: handwritten digits
  • CIFAR-10: 10 classes of objects

Larger datasets:

  • ImageNet: 1000 classes, 1.2 million images
  • COCO: 80 object categories, 300k images
  • MIT Places: 205 scene categories, 2.5 million images
  • LAION-5B: 5.85 billion images

Datasets are getting larger and larger, and the models are getting more and more complex.

Omniglot dataset: 1623 characters from 50 alphabets, 20 examples per character. It is used for few-shot learning. Few-shot learning is a type of machine learning that focuses on learning from a small number of examples. （小样本学 习）

First Model: Nearest Neighbor

Metrics: L1 distance, L2 distance, cosine similarity

L1 distance: d1(I1,I2)=∑p∣I1p−I2p∣d_1(I_1, I_2) = \sum_p |I_1^p - I_2^p|

L2 distance: d2(I1,I2)=∑p(I1p−I2p)2d_2(I_1, I_2) = \sqrt{\sum_p (I_1^p - I_2^p)^2}

import numpy as np
class NearestNeighbor:
    def __init__(self):
        pass

    def train(self, X, y):
        self.Xtr = X
        self.ytr = y

    def predict(self, X):
        num_test = X.shape[0]
        Ypred = np.zeros(num_test, dtype=self.ytr.dtype)

        for i in range(num_test):
            distances = np.sum(np.abs(self.Xtr - X[i, :]), axis=1)
            min_index = np.argmin(distances)
            Ypred[i] = self.ytr[min_index]

        return Ypred

Training time: O(1)O(1), Testing time: O(N)O(N)

  1. This is computationally expensive!
  2. Outliers can affect the result significantly.
outlier examples
Fig: outliers

Web demo: Nearest Neighbor Demo

Hyperparameters

What is the best K to use?

Hyperparameters: parameters that are not learned by the model, but are set at the start of the learning process.

Setting Hyperparameters:

  • Idea 1: Choose hyperparameters that work best on the data.
    • BAD: This works best on the training data.
  • Idea 2: Split data into train and test and choose hyperparameters that work best on the test data.
    • BAD: The algorithm is polluted by the test data!
  • Idea 3: Split data into train, validation, and test. Choose hyperparameters that work best on the validation data.
    • Better and correct ! We only touch once the test data.
    • Bad performance on the test set implies bad performance on the real world.
How to split your data
Fig: How to split your data
  • Idea 4: Cross-validation: split data into k folds, train on k-1 folds, and test on the remaining fold. Repeat k times and average the results.
    • Better than Idea 3, but computationally expensive. Useful for small datasets, but not used too much in deep learning.
cross-validation
Fig: cross-validation

Empirical studies:

Empirical studies
Fig: Empirical studies

Correctness: Universal Approximation

KNN has universal approximation power on compact sets.

Universal Approximation
Fig: Universal Approximation

Curse of Dimensionality

As the number of (input) dimensions increases, the volume of the space increases exponentially, and the number of data points required to fill the space increases exponentially.

Summary

  • KNN very is slow at runtime.
  • Distance metrics on pixels are not informative, e.g. predicting a human's face based on the surrounding pixels.
  • Surprisingly, KNN works well with extracted convolutional features!

Assignment 1

Some notes:

PyTorch Tensor Operations

Recall: some useful functions in PyTorch

## Creating tensors ##
torch.full # to create a tensor filled with a single value
torch.rand # to create a tensor of random values
torch.arange # to create a tensor with values that increase by 1
torch.linspace # to create a tensor with values that increase by a fixed amount
torch.eye # to create an identity matrix

## Reshaping tensors ##
torch.view # to reshape a tensor in-place
torch.reshape # to reshape a tensor
torch.flatten # to flatten a tensor

torch.permute # to permute the dimensions of a tensor
torch.transpose # to transpose a tensor

torch.squeeze # to remove dimensions of size 1
torch.unsqueeze # to add dimensions of size 1

## Aggregating tensors ##

torch.argmax # to find the index of the maximum value
torch.topk # to find the k largest values
torch.sort # to sort a tensor
torch.argsort # to find the indices that would sort a tensor

torch.sum # to sum a tensor
torch.mean # to compute the mean of a tensor
torch.std # to compute the standard deviation of a tensor

## Multiplying tensors ##
torch.mm # to perform matrix-matrix multiplication
torch.mv # to perform matrix-vector multiplication
torch.einsum # to perform Einstein summation
torch.kron # to compute the Kronecker product

## Concat and split tensors ##
torch.cat # to concatenate tensors
torch.chunk # to split a tensor into chunks

Slicing, Indexing, and Boolean Masking

Access a single row or columns of a tensor

There are two common ways to access a single row or column of a tensor: using an integer will reduce the rank by one, and using a length-one slice will keep the same rank. Note that this is different behavior from MATLAB.

Slicing a tensor

Slicing a tensor returns a view into the same data, so modifying it will also modify the original tensor. To avoid this, you can use the clone() method to make a copy of a tensor.

When you index into torch tensor using slicing, the resulting tensor view will always be a subarray of the original tensor. This is powerful, but can be restrictive.

Indexing with an integer array or a tensor

We can also use index arrays to index tensors; this lets us construct new tensors with a lot more flexibility than using slices.

As an example, we can use index arrays to reorder the rows or columns of a tensor:

# Credit: UMich EECS 498.007

# Create the following rank 2 tensor with shape (3, 4)
# [[ 1  2  3  4]
#  [ 5  6  7  8]
#  [ 9 10 11 12]]
a = torch.tensor([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
print('Original tensor:')
print(a)

# Create a new tensor of shape (5, 4) by reordering rows from a:
# - First two rows same as the first row of a
# - Third row is the same as the last row of a
# - Fourth and fifth rows are the same as the second row from a
idx = [0, 0, 2, 1, 1]  # index arrays can be Python lists of integers
print('\nReordered rows:')
print(a[idx])

# Create a new tensor of shape (3, 4) by reversing the columns from a
idx = torch.tensor([3, 2, 1, 0])  # Index arrays can be int64 torch tensors
print('\nReordered columns:')
print(a[:, idx])

More generally, given index arrays idx0 and idx1 with N elements each, a[idx0, idx1] is equivalent to:

# Credit: UMich EECS 498.007

torch.tensor([
  a[idx0[0], idx1[0]],
  a[idx0[1], idx1[1]],
  ...,
  a[idx0[N - 1], idx1[N - 1]]
])

(A similar pattern extends to tensors with more than two dimensions)

# Credit: UMich EECS 498.007

We can for example use this to get or set the diagonal of a tensor:

a = torch.tensor([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print('Original tensor:')
print(a)

idx = [0, 1, 2]
print('\nGet the diagonal:')
print(a[idx, idx])

# Modify the diagonal
a[idx, idx] = torch.tensor([11, 22, 33])
print('\nAfter setting the diagonal:')
print(a)

Select one element from each row or column of a tensor:

Boolean masking of tensors

The shape of the boolean mask should be the same as the original tensor, or should be broadcastable to the same shape. This is commonly used so I will not detail it here.

Reshape, Permute, and Contiguous

Reshape

Reshaping is calculated with the notion of stride. The stride of a tensor is the number of elements in the memory that need to be skipped over to obtain the next element along each dimension. See this blog post by Edward Yang for a clear explanation of the problem.

Permute

Permute is used to change the order of dimensions in a tensor. This can be understood mathematically.

Consider the symmetric group SnS_n of all permutations of nn elements. In other words, σ∈Sn\sigma \in S_n is a bijection from the set {1,2,…,n}\{1, 2, \ldots, n\} to itself. The permutation σ\sigma can be represented as a list of integers σ=[σ(1),σ(2),…,σ(n)]\sigma = [\sigma(1), \sigma(2), \ldots, \sigma(n)].

Let AA be a tensor of shape (d1,d2,…,dn)(d_1, d_2, \ldots, d_n). The tensor A′A' permuted by σ\sigma is a tensor of shape (dσ(1),dσ(2),…,dσ(n))(d_{\sigma(1)}, d_{\sigma(2)}, \ldots, d_{\sigma(n)}). And for any index (i1′,i2′,…,in′)(i_1', i_2', \ldots, i_n') in A′A', we have

Ai1′,i2′,…,in′′=Aiσ−1(1)′,iσ−1(2)′,…,iσ−1(n)′ A'_{i_1', i_2', \ldots, i_n'} = A_{i_{\sigma^{-1}(1)}', i_{\sigma^{-1}(2)}', \ldots, i_{\sigma^{-1}(n)}'} 

import torch

A = torch.tensor([[[1, 2], [3, 4]], [[5, 6], [7, 8]]])
# A has shape (2, 2, 2)
σ = [2, 0, 1]
A_prime = A.permute(*σ)
print("\nA' (permute [2, 0, 1]):\n", A_prime)
i_prime = (0, 1, 1)
i_original = (i_prime[σ.index(0)], i_prime[σ.index(1)], i_prime[σ.index(2)])
assert A_prime[i_prime] == A[i_original], "Permute operation is incorrect!"
print("\nVerified")

Contiguous ?

Some combinations of reshaping operations will fail with cryptic errors. The exact reasons for this have to do with the way that tensors and views of tensors are implemented, and are beyond the scope of this assignment. However if you're curious, this blog post by Edward Yang gives a clear explanation of the problem.

pytorch-internals is a good blog to understand the operation contiguous(), view() and reshape().

KNN

KNN Implementation

Notice on Usage and Attribution

This note is based on the University of Michigan's publicly available course EECS 498.008 / 598.008 and is intended solely for personal learning and academic discussion, with no commercial use.

  • Nature of the Notes: These notes include extensive references and citations from course materials to ensure clarity and completeness. However, they are presented as personal interpretations and summaries, not as substitutes for the original course content.
  • Original Course Resources: Please refer to the official University of Michigan website for complete and accurate course materials.
  • Third-Party Open Access Content: This note may reference Open Access (OA) papers or resources cited within the course materials. These materials are used under their original Open Access licenses (e.g., CC BY, CC BY-SA).
  • Proper Attribution: Every referenced OA resource is appropriately cited, including the author, publication title, source link, and license type.
  • Copyright Notice: All rights to third-party content remain with their respective authors or publishers.
  • Content Removal: If you believe any content infringes on your copyright, please contact me, and I will promptly remove the content in question.