This is an introductory lecture designed to introduce people from outside of Computer Vision to the Image Classification problem, and the data-driven approach. The Table of Contents:

  • Paradigm Classification
    • Nearest Neighbor Classifier
    • k - Nearest Neighbor Classifier
    • Validation sets for Hyperparameter tuning
    • Summary
    • Summary: Applying kNN in practise
      • Further Reading

Image Classification

Motivation. In this section we will introduce the Prototype Classification trouble, which is the task of assigning an input image i characterization from a fixed set up of categories. This is ane of the core problems in Figurer Vision that, despite its simplicity, has a big variety of practical applications. Moreover, every bit we will run into afterwards in the form, many other seemingly distinct Calculator Vision tasks (such as object detection, segmentation) can be reduced to image classification.

Case. For example, in the image below an paradigm classification model takes a single image and assigns probabilities to 4 labels, {cat, dog, hat, mug}. Every bit shown in the epitome, proceed in mind that to a computer an paradigm is represented as one large 3-dimensional assortment of numbers. In this instance, the cat image is 248 pixels wide, 400 pixels tall, and has 3 color channels Red,Green,Blue (or RGB for short). Therefore, the prototype consists of 248 x 400 x 3 numbers, or a total of 297,600 numbers. Each number is an integer that ranges from 0 (black) to 255 (white). Our task is to turn this quarter of a million numbers into a unmarried characterization, such as "cat".

The task in Epitome Classification is to predict a unmarried characterization (or a distribution over labels as shown here to indicate our confidence) for a given image. Images are 3-dimensional arrays of integers from 0 to 255, of size Width 10 Tiptop x 3. The 3 represents the three color channels Red, Green, Blue.

Challenges. Since this task of recognizing a visual concept (e.chiliad. cat) is relatively piddling for a human being to perform, information technology is worth considering the challenges involved from the perspective of a Computer Vision algorithm. Every bit we nowadays (an inexhaustive) list of challenges beneath, keep in heed the raw representation of images as a 3-D array of brightness values:

  • Viewpoint variation. A single instance of an object can be oriented in many ways with respect to the camera.
  • Scale variation. Visual classes often exhibit variation in their size (size in the real world, non merely in terms of their extent in the image).
  • Deformation. Many objects of interest are non rigid bodies and tin exist deformed in farthermost ways.
  • Occlusion. The objects of interest tin can exist occluded. Sometimes simply a small-scale portion of an object (as little as few pixels) could be visible.
  • Illumination conditions. The effects of illumination are desperate on the pixel level.
  • Background clutter. The objects of interest may alloy into their environment, making them hard to place.
  • Intra-form variation. The classes of interest can often be relatively broad, such as chair. There are many different types of these objects, each with their ain advent.

A adept prototype classification model must be invariant to the cantankerous product of all these variations, while simultaneously retaining sensitivity to the inter-class variations.

Data-driven arroyo. How might we go about writing an algorithm that can classify images into distinct categories? Unlike writing an algorithm for, for example, sorting a list of numbers, information technology is non obvious how 1 might write an algorithm for identifying cats in images. Therefore, instead of trying to specify what every ane of the categories of interest look like directly in code, the approach that we will take is non unlike one you would have with a child: we're going to provide the computer with many examples of each class then develop learning algorithms that wait at these examples and larn near the visual appearance of each class. This approach is referred to as a data-driven approach, since it relies on offset accumulating a training dataset of labeled images. Hither is an example of what such a dataset might look like:

An example training ready for four visual categories. In practise we may have thousands of categories and hundreds of thousands of images for each category.

The image classification pipeline. We've seen that the task in Epitome Classification is to take an array of pixels that represents a single paradigm and assign a label to it. Our complete pipeline tin exist formalized as follows:

  • Input: Our input consists of a prepare of N images, each labeled with one of One thousand different classes. We refer to this data as the training ready.
  • Learning: Our chore is to utilize the training ready to learn what every one of the classes looks similar. We refer to this stride as grooming a classifier, or learning a model.
  • Evaluation: In the cease, we evaluate the quality of the classifier past request information technology to predict labels for a new fix of images that it has never seen earlier. Nosotros will then compare the true labels of these images to the ones predicted by the classifier. Intuitively, we're hoping that a lot of the predictions friction match upwardly with the true answers (which we phone call the footing truth).

Nearest Neighbour Classifier

As our get-go approach, we volition develop what we telephone call a Nearest Neighbor Classifier. This classifier has nothing to do with Convolutional Neural Networks and it is very rarely used in practice, merely information technology volition let united states of america to get an idea well-nigh the basic approach to an image nomenclature problem.

Example image classification dataset: CIFAR-10. I pop toy paradigm classification dataset is the CIFAR-10 dataset. This dataset consists of 60,000 tiny images that are 32 pixels loftier and wide. Each paradigm is labeled with one of ten classes (for example "airplane, motorcar, bird, etc"). These threescore,000 images are partitioned into a grooming set of fifty,000 images and a test set of 10,000 images. In the epitome below you can come across x random example images from each one of the 10 classes:

Left: Example images from the CIFAR-x dataset. Right: first column shows a few test images and next to each we bear witness the top ten nearest neighbors in the training set co-ordinate to pixel-wise deviation.

Suppose now that nosotros are given the CIFAR-ten grooming set of 50,000 images (5,000 images for every i of the labels), and nosotros wish to label the remaining 10,000. The nearest neighbor classifier will take a examination image, compare information technology to every single one of the preparation images, and predict the label of the closest grooming prototype. In the epitome above and on the right you tin run across an example issue of such a procedure for 10 example examination images. Find that in only about 3 out of 10 examples an epitome of the same class is retrieved, while in the other vii examples this is not the example. For example, in the 8th row the nearest training image to the horse head is a blood-red automobile, presumably due to the strong blackness background. Equally a effect, this image of a equus caballus would in this instance be mislabeled as a car.

You may have noticed that nosotros left unspecified the details of exactly how we compare two images, which in this case are just 2 blocks of 32 x 32 x three. One of the simplest possibilities is to compare the images pixel past pixel and add up all the differences. In other words, given two images and representing them as vectors \( I_1, I_2 \) , a reasonable option for comparing them might be the L1 distance:

\[d_1 (I_1, I_2) = \sum_{p} \left| I^p_1 - I^p_2 \correct|\]

Where the sum is taken over all pixels. Here is the process visualized:

An example of using pixel-wise differences to compare two images with L1 distance (for one color aqueduct in this instance). Ii images are subtracted elementwise and then all differences are added up to a single number. If two images are identical the result will be zip. Only if the images are very different the result will exist big.

Permit'due south also look at how we might implement the classifier in code. Outset, let's load the CIFAR-10 data into memory as 4 arrays: the training information/labels and the test data/labels. In the code below, Xtr (of size 50,000 x 32 10 32 x 3) holds all the images in the training set, and a respective 1-dimensional assortment Ytr (of length 50,000) holds the training labels (from 0 to 9):

                              Xtr                ,                Ytr                ,                Xte                ,                Yte                =                load_CIFAR10                (                'data/cifar10/'                )                # a magic function we provide # flatten out all images to be one-dimensional                                Xtr_rows                =                Xtr                .                reshape                (                Xtr                .                shape                [                0                ],                32                *                32                *                3                )                # Xtr_rows becomes 50000 x 3072                                Xte_rows                =                Xte                .                reshape                (                Xte                .                shape                [                0                ],                32                *                32                *                3                )                # Xte_rows becomes 10000 x 3072

At present that we have all images stretched out equally rows, hither is how we could train and evaluate a classifier:

                              nn                =                NearestNeighbor                ()                # create a Nearest Neighbor classifier class                                nn                .                train                (                Xtr_rows                ,                Ytr                )                # railroad train the classifier on the training images and labels                                Yte_predict                =                nn                .                predict                (                Xte_rows                )                # predict labels on the test images # and at present impress the classification accuracy, which is the average number # of examples that are correctly predicted (i.e. label matches)                                print                'accuracy: %f'                %                (                np                .                mean                (                Yte_predict                ==                Yte                )                )

Notice that as an evaluation criterion, it is common to employ the accurateness, which measures the fraction of predictions that were correct. Notice that all classifiers we will build satisfy this ane common API: they have a train(10,y) function that takes the data and the labels to learn from. Internally, the class should build some kind of model of the labels and how they can be predicted from the data. So there is a predict(X) office, which takes new data and predicts the labels. Of course, we've left out the meat of things - the actual classifier itself. Here is an implementation of a elementary Nearest Neighbour classifier with the L1 distance that satisfies this template:

                              import                numpy                as                np                form                NearestNeighbor                (                object                ):                def                __init__                (                self                ):                laissez passer                def                train                (                cocky                ,                Ten                ,                y                ):                """ 10 is Due north 10 D where each row is an instance. Y is one-dimension of size Northward """                # the nearest neighbor classifier simply remembers all the preparation data                                self                .                Xtr                =                X                cocky                .                ytr                =                y                def                predict                (                cocky                ,                Ten                ):                """ X is N x D where each row is an case we wish to predict label for """                num_test                =                X                .                shape                [                0                ]                # lets make sure that the output type matches the input type                                Ypred                =                np                .                zeros                (                num_test                ,                dtype                =                cocky                .                ytr                .                dtype                )                # loop over all test rows                                for                i                in                range                (                num_test                ):                # discover the nearest training image to the i'th test image                                # using the L1 distance (sum of absolute value differences)                                distances                =                np                .                sum                (                np                .                abs                (                self                .                Xtr                -                X                [                i                ,:]),                axis                =                one                )                min_index                =                np                .                argmin                (                distances                )                # get the index with smallest distance                                Ypred                [                i                ]                =                self                .                ytr                [                min_index                ]                # predict the label of the nearest example                                return                Ypred

If you ran this code, you would see that this classifier only achieves 38.6% on CIFAR-10. That's more impressive than guessing at random (which would give x% accuracy since there are ten classes), but nowhere near human functioning (which is estimated at about 94%) or nigh state-of-the-art Convolutional Neural Networks that achieve well-nigh 95%, matching human being accurateness (run across the leaderboard of a recent Kaggle contest on CIFAR-ten).

The choice of distance. There are many other means of computing distances between vectors. Another common choice could be to instead use the L2 altitude, which has the geometric estimation of computing the euclidean distance betwixt two vectors. The distance takes the form:

\[d_2 (I_1, I_2) = \sqrt{\sum_{p} \left( I^p_1 - I^p_2 \right)^2}\]

In other words we would be computing the pixelwise departure as earlier, but this time nosotros square all of them, add them up and finally accept the square root. In numpy, using the code from higher up we would need to only supplant a single line of code. The line that computes the distances:

                              distances                =                np                .                sqrt                (                np                .                sum                (                np                .                foursquare                (                self                .                Xtr                -                X                [                i                ,:]),                axis                =                1                ))

Note that I included the np.sqrt telephone call above, but in a applied nearest neighbor application we could leave out the foursquare root operation considering square root is a monotonic part. That is, it scales the absolute sizes of the distances but it preserves the ordering, so the nearest neighbors with or without information technology are identical. If yous ran the Nearest Neighbor classifier on CIFAR-10 with this altitude, you would obtain 35.four% accuracy (slightly lower than our L1 distance consequence).

L1 vs. L2. It is interesting to consider differences between the two metrics. In detail, the L2 altitude is much more unforgiving than the L1 altitude when it comes to differences betwixt 2 vectors. That is, the L2 distance prefers many medium disagreements to one big 1. L1 and L2 distances (or equivalently the L1/L2 norms of the differences between a pair of images) are the virtually unremarkably used special cases of a p-norm.

one thousand - Nearest Neighbor Classifier

You may have noticed that information technology is strange to but use the characterization of the nearest image when nosotros wish to make a prediction. Indeed, information technology is almost e'er the example that i can do better by using what'southward called a g-Nearest Neighbor Classifier. The idea is very simple: instead of finding the single closest image in the training gear up, we will detect the top chiliad closest images, and have them vote on the label of the test image. In particular, when k = 1, nosotros recover the Nearest Neighbor classifier. Intuitively, higher values of chiliad have a smoothing issue that makes the classifier more resistant to outliers:

An example of the deviation betwixt Nearest Neighbor and a 5-Nearest Neighbor classifier, using ii-dimensional points and 3 classes (red, blueish, greenish). The colored regions evidence the decision boundaries induced past the classifier with an L2 distance. The white regions bear witness points that are ambiguously classified (i.e. class votes are tied for at least two classes). Notice that in the instance of a NN classifier, outlier datapoints (east.g. dark-green point in the middle of a cloud of blue points) create pocket-size islands of probable incorrect predictions, while the 5-NN classifier smooths over these irregularities, probable leading to improve generalization on the test data (not shown). Also note that the gray regions in the 5-NN image are caused by ties in the votes amongst the nearest neighbors (due east.thou. two neighbors are red, adjacent 2 neighbors are bluish, concluding neighbour is green).

In exercise, y'all will almost always want to employ k-Nearest Neighbor. Only what value of 1000 should you apply? We turn to this problem next.

Validation sets for Hyperparameter tuning

The k-nearest neighbour classifier requires a setting for k. But what number works best? Additionally, we saw that in that location are many different distance functions nosotros could have used: L1 norm, L2 norm, in that location are many other choices we didn't even consider (e.g. dot products). These choices are chosen hyperparameters and they come up very often in the design of many Machine Learning algorithms that learn from data. It'southward often not obvious what values/settings one should choose.

Y'all might be tempted to suggest that we should try out many unlike values and see what works best. That is a fine idea and that's indeed what nosotros volition do, but this must be done very advisedly. In particular, we cannot apply the exam fix for the purpose of tweaking hyperparameters. Whenever you're designing Machine Learning algorithms, you should remember of the examination gear up as a very precious resources that should ideally never be touched until one fourth dimension at the very stop. Otherwise, the very existent danger is that you may tune your hyperparameters to work well on the test ready, but if you were to deploy your model you could see a significantly reduced functioning. In practise, nosotros would say that yous overfit to the test set. Another mode of looking at information technology is that if you tune your hyperparameters on the test set, you are effectively using the test set as the training set, and therefore the performance yous achieve on it will be as well optimistic with respect to what you might actually observe when you deploy your model. Only if you but use the examination fix once at cease, information technology remains a good proxy for measuring the generalization of your classifier (we will see much more discussion surrounding generalization afterwards in the class).

Evaluate on the test gear up just a single time, at the very stop.

Luckily, in that location is a right mode of tuning the hyperparameters and information technology does not bear upon the test set at all. The idea is to dissever our training set up in two: a slightly smaller training ready, and what we call a validation set. Using CIFAR-x every bit an example, we could for example use 49,000 of the training images for grooming, and leave ane,000 aside for validation. This validation set is substantially used as a false test fix to tune the hyper-parameters.

Here is what this might look like in the example of CIFAR-10:

                              # assume we take Xtr_rows, Ytr, Xte_rows, Yte as earlier # call up Xtr_rows is l,000 x 3072 matrix                                Xval_rows                =                Xtr_rows                [:                grand                ,                :]                # take kickoff 1000 for validation                                Yval                =                Ytr                [:                m                ]                Xtr_rows                =                Xtr_rows                [                1000                :,                :]                # go on last 49,000 for train                                Ytr                =                Ytr                [                1000                :]                # find hyperparameters that work best on the validation set                                validation_accuracies                =                []                for                k                in                [                1                ,                3                ,                five                ,                10                ,                xx                ,                50                ,                100                ]:                # use a particular value of g and evaluation on validation data                                nn                =                NearestNeighbor                ()                nn                .                railroad train                (                Xtr_rows                ,                Ytr                )                # here nosotros assume a modified NearestNeighbor form that can take a k as input                                Yval_predict                =                nn                .                predict                (                Xval_rows                ,                chiliad                =                k                )                acc                =                np                .                mean                (                Yval_predict                ==                Yval                )                impress                'accuracy: %f'                %                (                acc                ,)                # keep runway of what works on the validation set                                validation_accuracies                .                suspend                ((                thou                ,                acc                ))

By the terminate of this process, we could plot a graph that shows which values of thousand work all-time. We would then stick with this value and evaluate one time on the actual test set.

Divide your grooming set up into training set and a validation set up. Use validation gear up to tune all hyperparameters. At the cease run a unmarried time on the test set and report performance.

Cantankerous-validation. In cases where the size of your training information (and therefore as well the validation information) might be pocket-sized, people sometimes use a more than sophisticated technique for hyperparameter tuning chosen cantankerous-validation. Working with our previous case, the thought is that instead of arbitrarily picking the kickoff 1000 datapoints to be the validation set and rest training set, you tin can go a improve and less noisy estimate of how well a certain value of m works by iterating over unlike validation sets and averaging the operation across these. For case, in v-fold cross-validation, we would split the training information into 5 equal folds, use 4 of them for preparation, and 1 for validation. We would so iterate over which fold is the validation fold, evaluate the functioning, and finally average the functioning across the unlike folds.

Example of a v-fold cantankerous-validation run for the parameter k. For each value of k we railroad train on 4 folds and evaluate on the 5th. Hence, for each grand we receive v accuracies on the validation fold (accuracy is the y-axis, each result is a indicate). The trend line is drawn through the average of the results for each 1000 and the error bars indicate the standard difference. Annotation that in this particular case, the cross-validation suggests that a value of about thousand = 7 works best on this particular dataset (respective to the peak in the plot). If we used more than than 5 folds, we might wait to come across a smoother (i.e. less noisy) bend.

In practise. In practice, people prefer to avoid cantankerous-validation in favor of having a single validation split, since cross-validation can be computationally expensive. The splits people tend to utilize is betwixt l%-ninety% of the training information for training and residue for validation. All the same, this depends on multiple factors: For example if the number of hyperparameters is large yous may prefer to apply bigger validation splits. If the number of examples in the validation ready is small (perhaps just a few hundred or and so), information technology is safer to utilise cantankerous-validation. Typical number of folds you can see in practice would be 3-fold, 5-fold or 10-fold cantankerous-validation.

Common data splits. A grooming and test set is given. The training set is split into folds (for example five folds hither). The folds 1-iv become the preparation set. 1 fold (e.g. fold 5 here in yellow) is denoted as the Validation fold and is used to melody the hyperparameters. Cross-validation goes a stride farther and iterates over the choice of which fold is the validation fold, separately from 1-5. This would exist referred to equally v-fold cross-validation. In the very end once the model is trained and all the all-time hyperparameters were adamant, the model is evaluated a single time on the test data (cherry-red).

Pros and Cons of Nearest Neighbor classifier.

It is worth considering some advantages and drawbacks of the Nearest Neighbor classifier. Clearly, one advantage is that information technology is very simple to implement and understand. Additionally, the classifier takes no time to railroad train, since all that is required is to store and possibly index the training data. However, nosotros pay that computational cost at test time, since classifying a test example requires a comparison to every single training example. This is backwards, since in do we often care about the test time efficiency much more than the efficiency at training time. In fact, the deep neural networks we will develop later in this class shift this tradeoff to the other farthermost: They are very expensive to train, simply once the training is finished it is very cheap to allocate a new test example. This manner of operation is much more desirable in practice.

Every bit an aside, the computational complexity of the Nearest Neighbor classifier is an active area of research, and several Approximate Nearest Neighbor (ANN) algorithms and libraries exist that tin accelerate the nearest neighbor lookup in a dataset (e.g. FLANN). These algorithms allow one to trade off the definiteness of the nearest neighbor retrieval with its infinite/time complexity during retrieval, and commonly rely on a pre-processing/indexing stage that involves building a kdtree, or running the k-means algorithm.

The Nearest Neighbor Classifier may sometimes be a skilful choice in some settings (peculiarly if the information is low-dimensional), but it is rarely appropriate for use in practical image classification settings. I problem is that images are high-dimensional objects (i.east. they often contain many pixels), and distances over high-dimensional spaces can be very counter-intuitive. The prototype beneath illustrates the signal that the pixel-based L2 similarities we developed above are very different from perceptual similarities:

Pixel-based distances on high-dimensional data (and images especially) can exist very unintuitive. An original prototype (left) and three other images next to it that are all equally far away from it based on L2 pixel altitude. Clearly, the pixel-wise distance does not correspond at all to perceptual or semantic similarity.

Here is one more visualization to convince you that using pixel differences to compare images is inadequate. We tin can employ a visualization technique chosen t-SNE to take the CIFAR-x images and embed them in ii dimensions so that their (local) pairwise distances are best preserved. In this visualization, images that are shown nearby are considered to be very virtually according to the L2 pixelwise distance we developed above:

CIFAR-10 images embedded in two dimensions with t-SNE. Images that are nearby on this image are considered to exist close based on the L2 pixel altitude. Discover the strong effect of background rather than semantic form differences. Click here for a bigger version of this visualization.

In particular, note that images that are nearby each other are much more a part of the general color distribution of the images, or the type of background rather than their semantic identity. For example, a dog tin can be seen very near a frog since both happen to exist on white groundwork. Ideally we would like images of all of the 10 classes to form their own clusters, so that images of the same class are nearby to each other regardless of irrelevant characteristics and variations (such every bit the background). Even so, to go this property we will have to go across raw pixels.

Summary

In summary:

  • We introduced the problem of Image Classification, in which we are given a set of images that are all labeled with a single category. We are then asked to predict these categories for a novel set of test images and measure the accuracy of the predictions.
  • Nosotros introduced a simple classifier chosen the Nearest Neighbor classifier. We saw that there are multiple hyper-parameters (such as value of grand, or the type of distance used to compare examples) that are associated with this classifier and that there was no obvious way of choosing them.
  • We saw that the right way to set these hyperparameters is to carve up your preparation data into two: a training set and a fake test set, which we call validation set. We try different hyperparameter values and go on the values that atomic number 82 to the all-time functioning on the validation set.
  • If the lack of training data is a concern, nosotros discussed a procedure called cantankerous-validation, which tin can aid reduce racket in estimating which hyperparameters piece of work best.
  • Once the best hyperparameters are found, we fix them and perform a single evaluation on the actual exam set.
  • Nosotros saw that Nearest Neighbor can get united states nigh forty% accuracy on CIFAR-10. Information technology is uncomplicated to implement merely requires us to store the unabridged training set and information technology is expensive to evaluate on a test prototype.
  • Finally, we saw that the use of L1 or L2 distances on raw pixel values is non adequate since the distances correlate more strongly with backgrounds and color distributions of images than with their semantic content.

In next lectures we will commence on addressing these challenges and eventually arrive at solutions that give xc% accuracies, let the states to completely discard the training set one time learning is complete, and they volition allow us to evaluate a test image in less than a millisecond.

Summary: Applying kNN in do

If y'all wish to apply kNN in practice (hopefully not on images, or peradventure as only a baseline) proceed as follows:

  1. Preprocess your data: Normalize the features in your information (east.g. one pixel in images) to have zero mean and unit of measurement variance. We will cover this in more item in subsequently sections, and chose not to cover data normalization in this section considering pixels in images are usually homogeneous and do non exhibit widely different distributions, alleviating the need for data normalization.
  2. If your information is very loftier-dimensional, consider using a dimensionality reduction technique such as PCA (wiki ref, CS229ref, blog ref), NCA (wiki ref, blog ref), or even Random Projections.
  3. Split up your training data randomly into railroad train/val splits. As a rule of thumb, between seventy-90% of your information usually goes to the train divide. This setting depends on how many hyperparameters you take and how much of an influence you await them to take. If there are many hyperparameters to judge, you should err on the side of having larger validation set to gauge them finer. If you are concerned about the size of your validation data, information technology is best to split the grooming data into folds and perform cross-validation. If you can afford the computational budget information technology is always safer to go with cross-validation (the more folds the improve, but more expensive).
  4. Railroad train and evaluate the kNN classifier on the validation data (for all folds, if doing cross-validation) for many choices of k (e.1000. the more the amend) and across different distance types (L1 and L2 are good candidates)
  5. If your kNN classifier is running too long, consider using an Approximate Nearest Neighbour library (e.thousand. FLANN) to accelerate the retrieval (at price of some accuracy).
  6. Take note of the hyperparameters that gave the best results. There is a question of whether you should utilize the full training set up with the best hyperparameters, since the optimal hyperparameters might change if you were to fold the validation data into your grooming gear up (since the size of the data would be larger). In practice it is cleaner to not utilise the validation data in the final classifier and consider it to exist burned on estimating the hyperparameters. Evaluate the best model on the test set. Report the test set accuracy and declare the outcome to exist the performance of the kNN classifier on your data.

Farther Reading

Here are some (optional) links you may find interesting for further reading:

  • A Few Useful Things to Know most Car Learning, where specially section 6 is related but the whole paper is a warmly recommended reading.

  • Recognizing and Learning Object Categories, a short course of object categorization at ICCV 2005.