Understanding Image Classification through Linear Classification and Nearest Neighbor Algorithms in Computer Vision

Get ready to dive into image classification!

This blog breaks down the basics of linear classifiers and nearest neighbor algorithms, showing you how they work together to make sense of visual data. We’ll also tackle challenges like dealing with complex data and tuning hyperparameters, all while connecting these ideas to more advanced models like CNNs.

Perfect for anyone curious about the world of computer vision!

Image classification is like a big deal in comp vision. It’s when the system gets an image, like a cat or something, and the computer’s job is to figure out what category it goes in.

How Computers See: The Semantic Gap Thing But the way computers see images is different — it sees them as numbers, like pixels and stuff for colors like red, blue, green.

This makes a “semantic gap” between how we see stuff and how computers see it.

Challenges: Viewport Changes and Lighting Issues There’s some tricky stuff too, like when you move the camera to a different angle, suddenly pixels change, So the numbers also chnges like vlue of RGB

And if the lighting changes, like it’s too bright or too dark, it affects how the image looks.

illumination

Building a Tough Algorithm: Deformation and Occlusion The algorithm has to be tough, so it can handle things like when the cat is in a different position(DEFORMTAION)

or when only part of the cat shows up, like just the tail.(OCCULSION)

Inter-Class Variations: Not All Cats Look the Same Backgrounds, different sizes, colors, and ages can make things complicated too. If we want a computer program to deal with all these cats right, we gotta check out what advancements are happening in this area.

Image Classifier: How It Works

Image classification is when you take an image and try to figure out what it is — like if it’s a cat or not. The computer does some crazy stuff to analyze the image and then spits out a class label.

From Edge Detection to Machine Learning Recognizing cats is something people have tried for a while — like looking for edges or features like a cat’s nose.

But just finding edges isn’t really a scalable way to recognize things because, well, what about dogs, or anything else? Instead, we gather large datasets with images of cats, airplanes, or whatever, and then train a machine learning classifier with that data.

With lots of images, the computer can learn what makes a cat a cat or what makes an airplane an airplane.

This training phase gives you a model, and that’s where the API comes in. There are two main functions in this setup:

Train: You give it a bunch of images, and it outputs a model.

Predict: You feed this trained model new images, and it gives you the category or class label for each image.

This method is way more flexible and can handle the variety in images better.

Convolutional Neural Networks:

The Early Days, The first classifiers were based on a simple idea called the nearest neighbor algorithm. It’s kind of a dumb approach — it memorizes all the training data. When you give it a new image to predict, it just finds the most similar image in the training set.

Example: CIFAR-10

Let’s say we use the CIFAR-10 dataset,

which has 10 classes (like cats, cars, etc.)

and 50,000 training images.

On the right, you have sorted training images, and on the left, you have a test image. If you apply the nearest neighbor algorithm, it looks through the dataset to find the closest match.

How It Works: Comparing Images

To compare the test image with training images, you use a comparison function,

like L1 distance (Manhattan distance). This means you take the difference between each pixel in the test image and each pixel in a training image.

For example, if the difference is 456, it gives a rough measure of how similar the images are.

This approach can work, but it’s not super smart — it’s slow and can struggle when images are different from what it’s seen before. That’s where more advanced methods like Convolutional Neural Networks (CNNs) come in.

PYTHON CODE:

This code is for a super simple Nearest Neighbor classifier.

First, we train it by just storing the training data (images and their labels). When it’s time to predict the label for a new image, it compares this new image to all the training images using L1 distance (basically, it checks how different they are by adding up pixel differences).

Then, it finds the training image that’s closest to the new image and assigns its label as the prediction. It’s straightforward but not very smart — just picks the closest match!

import numpy as np

class NearestNeighbor:
    def __init__(self):
        pass

    def train(self, x, y):
        # X is n x d where each row is an example, Y is 1-dimensional of size n
        self.x_train = x
        self.y_train = y

    def predict(self, x):
        # X is n x d where each row is an example we wish to predict the label for
        num_test = x.shape[0]
        y_pred = np.zeros(num_test, dtype=self.y_train.dtype)

        for i in range(num_test):
            # Compute L1 distance between the test example and all training examples
            distances = np.sum(np.abs(self.x_train - x[i, :]), axis=1)
            # Find the index with the minimum distance
            min_index = np.argmin(distances)
            # Predict the label of the nearest example
            y_pred[i] = self.y_train[min_index]

        return y_pred

Speed of Training and Prediction

In a Nearest Neighbor classifier, training is quite slow because it just memorizes all the training examples, which can take a lot of time with many examples.

However, predicting is fast because it only involves finding the closest example in that memorized data.

Ideally, we want classifiers to be slow during training and fast during testing, so Nearest Neighbor is a bit backward since training can take a while.

How It Works in Practice

When you apply this classifier, you might see different colors representing various classes or categories for each pixel.

For example, the essential regions might be marked in green, with yellow in the middle, and sort of fingers pushing into a blue region.

Using K Nearest Neighbors

In a K Nearest Neighbor (KNN) setup, you consider the closest k neighbors to make a prediction. If you set k=3, the algorithm will take a vote from the three nearest neighbors. If you increase k to 5, the decision boundary between the green and blue areas becomes smoother, meaning the classifier is less sensitive to noise and can make more reliable predictions.

Dealing with the White Region

In a Nearest Neighbor classifier, the majority winner in a white region (where there are no nearest neighbors) can be problematic because it means the algorithm lacks sufficient data to make a good prediction. However, with K Nearest Neighbor, we can compare different points effectively.

Distance Metrics: L1 and L2

We use different distance metrics, such as L1 (Manhattan distance) and L2 (Euclidean distance), to measure the differences between points.

The circle shape represents L2 distance, while L1 depends on the coordinates, creating a diamond-like shape in 2D.

Changing coordinates doesn’t matter in L2 since it is more generic and treats all features equally.

On the other hand, L1 distance is more sensitive to individual entries and their contributions to the task. When classifying images or objects, K Nearest Neighbor can be applied to various data types, and geometrically, you can see how the shapes of decision boundaries change based on the chosen distance metric.

Impact of K and Distance Metric on Decision Boundaries

As you change the value of k, the decision boundary alters. For example, a smaller k (like k=1) makes the boundary very sensitive to noise, while a larger k results in smoother boundaries.

here is video demo example

[embed]

Choosing Hyperparameters

When using the algorithm in practice, choosing hyperparameters (like the best value of k) is crucial.

A common approach is to try different values and see which one gives the best performance.

L1 distance has coordinate dependency, so it’s important to consider this when selecting hyperparameters.

In machine learning, we don’t just want to fit the data; we care about how well our model works on unseen data. Therefore, it’s a bad idea to use multiple hyperparameters without proper validation.

Splitting Data for Validation

To effectively choose hyperparameters, it’s best to split your data into three sets: training, validation, and test. You can train on the training set, validate different hyperparameters on the validation set, and finally evaluate your model’s performance on the test set to see how it performs on unseen data. This approach helps ensure that the chosen model generalizes well and isn’t just overfitting the training data.

Hyperparameter Setting with Cross-Validation

When dealing with small datasets, setting hyperparameters can be challenging

Instead of using a separate test set, we can split the training data into multiple folds for cross-validation.

This technique allows us to train the model on different subsets and validate it on the remaining portions. By cycling through each fold, we can determine which hyperparameters lead to more robust performance.

Training and Validation

The training set consists of images with labels that the model memorizes. During validation, the model classifies images by comparing them to the nearest training examples and transferring the labels accordingly. The algorithm effectively memorizes the training data and uses the validation set to evaluate how well it can predict labels.

Representativeness of the Test Set:

Is it possible for the test set to be unrepresentative of real-world data? This can happen if the data distribution shifts over time.

Using independent and identically distributed (i.i.d.) techniques helps give predictive power to test data.

Distribution Shift and Concept Drift: Real-world data often changes over time, leading to distribution shifts or concept drift. For example, the conditions under which data is collected might differ, such as variations between rainy and sunny days. In such cases, it’s important to apply cross-validation carefully, possibly using time series splits or data augmentation to ensure that the model generalizes well.

Importance of Random Partitioning

When partitioning data in a dataset, it’s crucial to ensure that the splits are random. This randomness helps maintain a representative sample of the entire dataset in both training and validation sets, leading to more reliable model evaluation.

K Nearest Neighbor and Cross-Validation

In the context of K Nearest Neighbor (KNN), we can plot the x-axis with different values of k and the y-axis with cross-validation accuracy for each value.

By using 5-fold cross-validation, we can determine which hyperparameter values work best for our KNN model on image datasets.

KNN can be slow at test time, especially when calculating distances.

L1 and L2 Distances

One issue with KNN is that both L1 and L2 distances may yield similar results for images, particularly when comparing images that are slightly altered (like tinted or shifted). This can happen because L2 distance measures the Euclidean distance between pixel values, which might not accurately reflect the visual similarity of the images.

Why Similar L2 Distances Can Be Misleading

The reason images can have the same L2 distance is that this metric does not account for the perceptual similarity of images

For instance, two images might be pixel-wise close in terms of L2 distance but look quite different to the human eye.

Thus, relying solely on L2 distance may not capture the true visual differences between images.

Linear Classification

In machine learning that helps us categorize data into different classes based on a linear relationship.

It’s like drawing a straight line (or a hyperplane in higher dimensions) to separate different groups in a dataset.

Input Features:

In the case of images, each pixel can be considered a feature.

For example, a grayscale image has one feature per pixel, while a color image has three features (red, green, and blue channels).

Weights and Bias:

Each feature is associated with a weight, which indicates how important that feature is for making a classification.

The bias is an additional parameter that helps shift the decision boundary. The linear model computes a score by combining the weighted inputs and the bias:

f(x,w)=w1⋅x1+w2⋅x2+…+wn⋅xn+bf(x, w) = w_1 \cdot x_1 + w_2 \cdot x_2 + \ldots + w_n \cdot x_n + bf(x,w)=w1​⋅x1​+w2​⋅x2​+…+wn​⋅xn​+b

Here, xxx represents the input features, www represents the weights, and bbb is the bias.

Decision Boundary:

The model makes a prediction by checking if the score is above or below a certain threshold.

If the score is above the threshold, the input is classified as one class (e.g., cat); otherwise, it’s classified as another class (e.g., dog).

In a two-dimensional space, this would correspond to a line separating the two classes.

Limitations

Linearity Assumption:

They assume that the relationship between features and classes is linear. This means they can struggle with complex datasets where classes are not easily separable by a straight line (or hyperplane).

• For instance, if the data points form a circle, a linear classifier won’t be able to separate them effectively.

Multimodal Data:

When a class appears in different regions of the feature space, a linear classifier might not find a suitable decision boundary.

For example, if you have two categories that overlap significantly, a linear classifier may misclassify many points.