What Is Image Classification?

Image classification is perhaps the most fundamental of the many tasks that computer vision attempts to solve. Deep learning overcame the difficulty conventional machine learning had in continuing to improve as the amount of data grew, and its modern rise began when a network called AlexNet won an image-classification competition. Many people remember AlphaGo as the beginning of AI. AlphaGo was certainly an important event that drew enormous attention to reinforcement learning, but AlexNet made a somewhat stronger impression on me.

Returning to image classification, the task is simply to receive an image as input and match it to one of a fixed set of categories. The figure above shows examples from the CIFAR-10 dataset. It contains ten classes, and every image is indexed with a label that describes it, such as dog or cat.

To any human, this image is plainly a cat, but a computer sees it differently. Every image is quantized in a computing environment and mapped into three-dimensional memory as RGB values at individual pixel locations. When a computer first encounters the cat image, the raw sequence of numbers gives it only a 10% chance of guessing “cat” among the ten classes. We therefore want the computer to discover rules shared by the numerical arrays of as many different cat images as possible. That is the basic idea behind image classification.

What Is Challenging?

Before going deeper, it helps to introduce the concept of a tensor. A tensor generalizes the idea of a matrix and is simply an array of numbers or data. The rank of a matrix refers to the number of independent vectors it contains; in common deep-learning usage, the rank of a tensor similarly means the number of dimensions in that tensor.

If a tensor has $N$ dimensions along which its elements can be grouped, it is a rank-$N$ tensor. An image, for example, is a collection of $H \times W$ matrices with RGB channels, so it can be represented as follows.

Each pixel in the cat image denotes the color at a particular position—or, more precisely, the color rendered from a three-dimensional scene onto a two-dimensional camera. Many colors can be represented as combinations of the three additive primary colors, RGB. In a digital-camera environment, RGB values are quantized to $0 \sim 255$ as 8-bit unsigned integers, and the same representation is used in computing. We can therefore express a cat image as a tensor containing three $H \times W$ spatial matrices, one each for R, G, and B.

Throughout the posts that follow, an image's resolution means its spatial dimensions, while its channels refer to its RGB axis. The conclusion is that the image used as input to our classification task is a three-dimensional tensor.

Images represented this way present a major problem. If the angle from which an object is photographed changes—a viewpoint variation—the data can be dramatically different even though the object is the same. Once the computer receives the image representation used for classification, values vary with the viewing angle, making it hard to find a prediction algorithm that generalizes over the same object.

Differences caused by illumination conditions pose the same problem. A change from night to day, or a shift in the light source that alters the colors of the foreground and background from our viewpoint, can cause an algorithm to make different predictions for the same scene.

There are many other constraints on machine learning from images: scale variation, in which the same object changes size as the camera moves closer or farther away; deformation, because cats, for example, are liquids with dynamic poses that are difficult to model robustly; camouflage caused by similar object and background colors; occlusion, where a foreground object hides something behind it; and the many possible appearances of objects within the same class. Designing a network explicitly for every possible form of the data is nearly impossible. This is where the data-driven algorithm at the foundation of deep learning becomes the solution.

Data-Driven Algorithms

A data-driven algorithm resembles inductive reasoning. Algorithms for problems such as finding a shortest path or performing binary search begin with a reasonably bounded set of possibilities. Image classification instead needs an algorithm that can make predictions regardless of all the challenging situations described above. Even the single category “chair” contains an extraordinary variety of objects, including works of art that break our preconceptions about what a chair looks like.

To be honest, even a person might struggle to call the object on the right a chair. In any case, the aim is to build an algorithm that can handle variations in lighting, camera rotation, camera position, and every other circumstance.

We try to achieve this with anywhere from a few thousand examples to hundreds of millions. By optimizing over as much data as possible, we seek an algorithm that applies to all the object data in the world that we cannot directly observe. Most of the deep-learning algorithms discussed later use this approach.

Image-Classification Pipeline

Based on the ideas above, image classification can be divided into three components, or stages. The first is input data. We use $N$ images, each matched to one of $K$ labels—the number of classes—in a data-driven optimization process. This is the training data. In supervised learning, training data must be labeled in this way.

The second stage is learning. Here we define the objective function or algorithm used for optimization. The goal of this stage is to obtain the best possible performance from the training data supplied by the first component.

The third stage is evaluation. We need to determine how well the network actually performs while it is being optimized, which requires another collection of data. Like the training data, it must have annotations against which performance can be measured; it is called validation or test data. The reference value corresponding to an algorithm's prediction is called the ground truth.

Nearest-Neighbor Classifier

The classifier introduced here is not a neural-network architecture of the kind used in deep learning. It is a highly inefficient algorithm, but discussing it helps avoid confusing a data-driven algorithm with a gradient-descent algorithm. The relationship between the two ideas resembles the relationship between machine learning and deep learning. Gradient descent can optimize a function in a data-driven approach, but the concepts are not the same; a method need not be a neural network to be data-driven. Gradient descent, WGAN-GP (Wasserstein GAN with gradient penalty), and the other optimization algorithms now discussed in deep learning already existed in fields such as communications and mathematics before their use in AI.

A nearest-neighbor classifier needs all of its data at inference time.

The figure on the left shows several CIFAR-10 samples; the one on the right shows the ten training images judged most similar to each test image. In keeping with the algorithm's name, once we choose a metric for similarity, we can compare the distance between training and test images and predict the test image's class from its nearest neighbor. Distances are commonly calculated as follows. Distance and norm are frequently used when operating on tensors, matrices, or vectors for which ground truth exists, and they can be expressed differently according to an order $p$. A norm describes the magnitude of a vector, whereas distance is the magnitude of the difference between two vectors. A vector's norm is also called its distance from the origin, or its magnitude.

$$L_p = \left( \sum_i^n \vert x_i \vert^p \right)^{\frac{1}{p}}$$

A norm with order $p$ is written $L_p$, as above, where $x$ is assumed to be an $n$-dimensional vector. The most commonly used norms are the $L_1$ and $L_2$ norms. Substituting $p=1$ gives

$$\begin{aligned} L_1 =& \left( \sum_i^n \vert x_i \vert \right) \newline =& \vert x_1 \vert + \vert x_2 \vert + \vert x_3 \vert + \cdots + \vert x_n \vert \end{aligned}$$

The $L_1$ norm is also called the taxicab or Manhattan norm. As the equation shows, it is the sum of the absolute values of the elements. Now substitute $p=2$:

$$\begin{aligned} L_2 =& \sqrt{\sum_i^n x_i^2 } \newline =& \sqrt{x_1^2 + x_2^2 + x_3^2 + \cdots + x_n^2 } \end{aligned}$$

This is probably the familiar formula for the distance from the origin to the coordinates of a vector. Because it measures vector magnitude in Euclidean space, it is called the Euclidean norm. Vector notation also lets us rewrite it as an inner product.

$$\begin{aligned} L_2 =& \sqrt{\sum_i^n x_i^2 } \newline =& \sqrt{x \cdot x} \newline =& \sqrt{x^\top x} \newline =& \sqrt{x_1^2 + x_2^2 + x_3^2 + \cdots + x_n^2 } \end{aligned}$$

Generalizing to more than one vector, distance is the norm of the difference between two tensors.

Returning to the classifier, nearest neighbor calculates the distance between a test image and each training image using a metric such as the one above. The figure shows an $L_1$ distance, although $L_2$ distance could be used instead. After finding the minimum distance, the classifier predicts the test image's label from the label of the closest image.

$L_1$ and $L_2$ distances have different strengths and weaknesses. In general, the squared calculation makes $L_2$ less forgiving of vector differences than $L_1$. Because it is quadratic, it penalizes errors greater than one more heavily than the straight-line $L_1$ distance. “Less forgiving” simply means assigning a larger penalty to an error of the same size.

Nearest neighbor is extremely simple, but accuracy can be poor when only the single closest image determines the prediction. Comparing image vectors alone can assign the same class to two images with similar colors but completely different objects. To avoid this, we can make a prediction from a larger sample. This is KNN, or $K$-nearest neighbors: after comparing distances, it predicts using the $k$ samples that include the nearest images.

As the figure shows, when $k$ is small, the prediction depends on the closest individual samples, producing broken boundaries and a discontinuous prediction map. Predicting the majority class among the five nearest samples alleviates this problem to some extent. An arbitrarily large $K$, however, can make performance worse. This is intuitive, but we will return to it shortly.

Tuning Hyperparameters

Parameters we can adjust manually while training a network are commonly called hyperparameters. Unlike model parameters such as network weights, hyperparameters require the experimenter to perform a grid search for good values. To choose $K$ in KNN or decide whether the $L_1$ or $L_2$ norm performs better, we run experiments under each condition and use the setting with the best performance.

The validation set is important here, in addition to the training and test sets. Training data is not used to tune the hyperparameter, but tuning still requires a metric like the one measured on test data. In KNN, the training set acts as a kind of image dictionary and a test sample as the word we want to look up. If we tune hyperparameters on the test set, the resulting values are overfit to that particular test set rather than generalized to new data.

For anyone who studied deep learning first, it is worth repeating that the method under discussion is KNN, not a neural network. Unlike the usual overfitting of a DNN to its training set, overfitting in this KNN setting must be defined with respect to the test set. Both problems are addressed by monitoring a validation set, but although their contexts are similar, they are not the same kind of overfitting.

We therefore need validation data in addition to the traditional training and test data. For better generalization, the training set is divided into several folds, one of which serves as the validation set.

We can now average the measured performance across folds during training, making comparisons fairer while tuning the hyperparameter $K$.

The graph above comes from cross-validating the training and validation splits across multiple folds. With five folds, each serves as validation once, yielding five accuracy measurements. Their mean estimates performance that generalizes over the split. This is particularly useful when the available training data is very small.

The result shows that more distance comparisons—a larger $k$—provide more samples, but do not guarantee better performance because we do not know how representative the training data is of the test data. If the training set contains many samples that resemble the test point but carry different labels, adding them can be harmful. As $k$ continues to grow, this eventually becomes likely because observable data is finite. Performance therefore peaks at the intermediate value $k=7$.

Limitations

We would not regard these four images as depicting different people. Despite slight distortions and other differences, we can tell that all were generated from an image of the same person. KNN cannot. In a two-dimensional image, shifting the pixels only a few positions sideways can produce a very large distance even though it is the same picture. The error is especially severe with $L_2$ distance because the differences between every pixel value are squared and summed. KNN is therefore difficult to apply to high-dimensional data such as images, which motivates the use of neural networks. That is where the next article begins.