One-shot learning


One-shot learning is an object categorization problem, found mostly in computer vision. Whereas most machine learning based object categorization algorithms require training on hundreds or thousands of samples/images and very large datasets, one-shot learning aims to learn information about object categories from one, or only a few, training samples/images.
The primary focus of this article will be on the solution to this problem presented by Fei-Fei Li, R. Fergus and P. Perona in IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 28, 2006, which uses a generative object category model and variational Bayesian framework for representation and learning of visual object categories from a handful of training examples. Another paper, presented at the International Conference on Computer Vision and Pattern Recognition 2000 by Erik Miller, Nicholas Matsakis, and Paul Viola will also be discussed.

Motivation

The ability to learn object categories from few examples, and at a rapid pace, has been demonstrated in humans, and it is estimated that a child has learned almost all of the 10 ~ 30 thousand object categories in the world by the age of six. This is due not only to the human mind's computational power, but also to its ability to synthesize and learn new object classes from existing information about different, previously learned classes. Given two examples from two different object classes: one, an unknown object composed of familiar shapes, the second, an unknown, amorphous shape; it is much easier for humans to recognize the former than the latter, suggesting that humans make use of existing knowledge of previously learned classes when learning new ones.
The key motivation for the one-shot learning technique is that systems, like humans, can use prior knowledge about object categories to classify new objects.

Background

As with most classification schemes, one-shot learning involves three main challenges:
One-shot learning differs from single object recognition and standard category recognition algorithms in its emphasis on knowledge transfer, which makes use of prior knowledge of learnt categories and allows for learning on minimal training examples.
The Bayesian one-shot learning algorithm represents the foreground and background of images as parametrized by a mixture of constellation models. During the learning phase, the parameters of these models are learned using a conjugate density parameter posterior and Variational Bayesian Expectation-Maximization. In this stage the previously learned object classes inform the choice of model parameters via transfer by contextual information. For object recognition on new images, the posterior obtained during the learning phase is used in a Bayesian decision framework to estimate the ratio of p to p.

Bayesian framework

Given the task of finding a particular object in a query image, the overall objective of the Bayesian One-Shot Learning algorithm is to compare the probability that object is present in the image and the probability that only background clutter is present in the image. If the former probability is higher, the algorithm reports the object's presence in the image, and if the latter probability is higher, the algorithm reports the absence of that object in the image. In order to compute these probabilities, the object class must be modeled from a set of training images containing examples of that object.
To formalize these ideas, let be the query image, which contains either an example of the foreground category or only background clutter of a generic background category. Also let be the set of training images used as the foreground category. The decision of whether contains an object from the foreground category, or only clutter from the background category is:
where the class posteriors and have been expanded by Bayes' Theorem, yielding a ratio of likelihoods and a ratio of object category priors. We decide that the image contains an object from the foreground class if exceeds a certain threshold. We next introduce parametric models for the foreground and background classes with parameters and respectively. This foreground parametric model is learned during the learning stage from training images, as well as prior information of learnt classes. The background model we assume to be uniform across images. Omitting the constant ratio of category priors,, and parametrizing over and yields:
The posterior distribution of model parameters given the training images, is estimated in the learning phase of the algorithm. In this estimation, one-shot learning deviates sharply from more traditional Bayesian estimation models which approximate the integral as, in favor of a variational approach which makes use of prior information from previously learnt categories. For the background model, however, as well as the categories learned in advance through numerous training examples, this traditional maximum likelihood estimation of the model parameters is used.

Object category model

For each query image and training images, a constellation model is used for representation. To obtain this model for a given image, first a set of N interesting regions is detected in the image using the Kadir brady saliency detector. Each region selected is represented by a location in the image, and a description of its appearance,. Letting and and the analogous representations for training images, the expression for R becomes:
The likelihoods and are represented as mixtures of constellation models. A typical constellation model has P parts, but there are N interest regions. Thus a P-dimensional vector h assigns one region of interest to each model part. Thus h denotes a hypothesis for the model and a full constellation model is represented by summing over all possible hypotheses h in the hypothesis space. Finally the likelihood is written
The different 's represent different configurations of parts, whereas the different hypotheses h represent different assignations of regions to parts, given a part model. The assumption that the shape of the model and appearance are independent allows one to consider the likelihood expression as two separate likelihoods of appearance and shape.

Appearance

The appearance of each feature is represented by a point in appearance space. "Each part in the constellation model has a Gaussian density within this space with mean and precision parameters." From these the appearance likelihood described above is computed as a product of Gaussians over the model parts for a give hypothesis h and mixture component.

Shape

The shape of the model for a given mixture component and hypothesis h is represented as a joint Gaussian density of the locations of features. These features are transformed into a scale and translation-invariant space before modelling the relative location of the parts by a 2-dimensional Gaussian. From this, we obtain the shape likelihood, completing our representation of . In order to reduce the number of hypotheses in the hypothesis space, only those hypotheses which satisfy the ordering constraint that the x-coordinate of each part is monotonically increasing are considered. This eliminates hypotheses from.

Conjugate densities

In order to compute, the integral must be evaluated, but is analytically intractable. The object category model above gives information about, so what remains is to examine, the posterior of, and find a sufficient approximation to render the integral tractable. Previous work approximates the posterior by a function centered at, collapsing the integral in question into. This is normally estimated using a Maximum Likelihood or Maximum A Posteriori procedure. However, because in one-shot learning, few training examples are used, the distribution will not be well-peaked, as is assumed in a function approximation. Thus instead of this traditional approximation, the Bayesian one-shot learning algorithm seeks to "find a parametric form of such that the learning of is feasible." The algorithm employs a Normal-Wishart distribution as the conjugate prior of, and in the learning phase, variational Bayesian methods with the same computational complexity as maximum likelihood methods are used to learn the hyperparameters of the distribution. Then, since is a product of Gaussians, as chosen in the object category model, the integral reduces to a multivariate Student's T distribution, which can be evaluated.

Implementation

Feature detection and representation

To detect features in an image so that it can be represented by a constellation model, the Kadir Brady feature detector is used on grey-scale images, finding salient regions of the image. These regions are then clustered, yielding a number of features and the shape parameter, composed of the cluster centers. The Kadir Brady detector was chosen because it produces fewer, more salient regions, as opposed to feature detectors like multiscale Harris, which produces numerous, less significant regions.
The regions are then taken from the image and rescaled to a small patch of 11 by 11 pixels, allowing each patch to be represented in 121-dimensional space. This dimensionality is reduced using principal component analysis, and, the appearance parameter, is then formed from the first 10 principal components of each patch.

Learning

To obtain shape and appearance priors, three categories are learned using maximum likelihood estimation. These object category model parameters are then used to estimate the hyper-parameters of the desired priors.
Given a set of training examples, the algorithm runs the feature detector on these images, and determines model parameters from the salient regions. The hypothesis index h assigning features to parts prevents a closed-form solution of the linear model, so the posterior is estimated by variational Bayesian expectation-maximization, which is run until parameter convergence after ~ 100 iterations. Learning a category in this fashion takes under a minute on a 2.8 GHz machine with a 4-part model and < 10 training images.

Experimental results

Motorbike example

To learn the motorbike category:
An alternative to the Bayesian One-Shot Learning algorithm, the algorithm presented by Erik Miller, Nicholas Matsakis, and Paul Viola at ICCV 2000 uses knowledge transfer by model parameters to learn a new object category which is similar in appearance to previously learnt categories. In their paper, an image is represented as either a texture and shape, or as a latent image which has been transformed, denoted by .

Congealing

Whereas the term vectorization denotes the process of bringing one image into correspondence with another, the authors of this paper have coined the term congealing to be "the simultaneous vectorization of each of a set of images to each other." For a set of training images of a certain category, congealing iteratively transforms each image to minimize the images' joint pixelwise entropies E, where
"where is the binary random variable defined by the values of a particular pixel p across all of the images, is the discrete entropy function of that variable, and is the set of pixel indices for the image."
The congealing algorithm begins with a set of images and a corresponding transform matrix, which at the end of the algorithm will represent the transformation of into its latent image. These latent images minimize the joint pixel-wise entropies. Thus the task of the congealing algorithm is to estimate the transformations.
Sketch of algorithm:
At the end of the algorithm,, and transforms the latent image back into the originally observed image. Congealing applied to a set of 0's and a set of 2's is shown on the right.

Classification

To use this model for classification, we must estimate the model with the maximum posterior probability given an observed image. An application of Bayes' rule to and parametrization by the transformation gives a difficult integral which the authors approximate, and then seek the best transform. That is, the transformation which maps the test image to its latent image. Once this transformation is found, the test image can be transformed into its latent image, and a nearest neighbor classifier based on Hausdorff distance between images is used to classify the latent image as belonging to a particular class.
To find this optimal, the authors propose to insert the test image I into the training ensemble for the congealing process. Since we assume that the test image is drawn from one of the classes, congealing will provide a corresponding which maps I to its latent image. The latent image can now be classified.

Single-example classification

Given a set of transformations obtained from congealing many images of a certain category, the authors extend their classifier to the case where only one training example of a new category is allowed. Applying all the transformations sequentially to, we create an artificial data training set for. This artificial data set can be made larger by borrowing transformations from not only one, but many already known categories. Once this data set is obtained,, a test instance of, can be classified as in the normal classification procedure. The key assumption here is that categories are similar enough that the transforms from one can be applied to another.

Citations