i Remerciements Je tiens à remercier en tout premier lieu mon directeur de thèse Liming Chen pour m'avoir accueilli au sein du Laboratoire, pour m'avoir fait conance, pour son soutien. Dans les périodes diciles, il a su prendre du temps pour m'aider à avancer. Je lui exprime ma profonde reconnaissance.

Je tiens tout particulièrement à remercier mon co-directeur de thèse Florent Perronnin pour avoir su me guider avec gentillesse pendant ces trois années. Ses capacités scientiques, son honnêteté humaine, son encouragement et ses remarques ont largement contribué à l'aboutissement de cette thèse.

J'adresse évidemment un grand merci à Chris Dance et Marco Bressan pour m'avoir donné l'opportunité de réaliser cette thèse dans le Centre de Recherche Européen de Xerox (XRCE).

Je tiens à remercier les rapporteurs Frédéric Jurie et Stéphane Canu qui ont pris le temps de lire et évaluer mes travaux ainsi que pour leurs remarques constructives qu'ils ont faites. J'adresse également des remerciements aux membres du jury pour l'intérêt qu'ils ont porté à mes travaux.

Cette thèse s'est déroulée successivement au sein du XRCE et du Laboratoire d'InfoRmatique en Image et Systèmes d'information. Je tiens à remercier tous mes collègues et mes amis du XRCE et du LIRIS pour l'ambiance chaleureuse, amicale et passionnée.

Enn, je souhaite exprimer toute ma reconnaissance à ma chérie Xiaodong, mes parents et beaux-parents pour leur soutien constant et leur patience.

Outline of thesis 5

• In chapter 3, we introduce the datasets used in this thesis.

• In chapter 4, we describe the estimation of universal and adapted image models. We present two similarity measures between distributions and explain how they can be approximated in our case.

• In chapter 5, we show that the vector of mixture weights can be computed through the optimization of a convex objective function. We compare our novel image representation with that standard kernel-based classier i.e. the KLK or the PPK proposed in chapter 4 and demonstrate its eciency.

• In chapter 6, we propose an alternative measure of contextual similarity between distributions.

• In chapter 7, we explain explicit data embedding for large-scale learning.

• In chapter 8, we summarize our conclusions and propose future directions.

With the rapid development of digital cameras and camera phones, the world is currently experiencing a digital imaging revolution. Many online photo sharing websites such as Flickr [Flickr ] or Facebook [Facebook ] have enabled millions of users to upload and share their photo albums over the Internet. For instance, as of October 2009, Flickr claimed to host more than 4 billion images [Flickr 2009]. In April 2009, Facebook announced that it hosted 15 billion photos with a growth rate of 220 million photos per week [Facebook 2009]. However, accessing these huge repositories remains an open problem. Search engines like Google Images [Google ], Yahoo! Image Search [Yahoo! ] or Picsearch [Picsearch ] still rely only on the textual metadata associated with images (e.g. le name, title and tags if any) and disregard the most important information: the image content. There has been a great interest in the last decade in automatic image annotation, i.e. assigning to an image one or multiple labels based on its semantic content. Although it is an easy problem for humans, it has proved to be very dicult for computers to cope with variations in view, lighting and occlusion and with typical object and scene variations as illustrated by the cat images in Figure 1. 1. In the eld of image annotation, representations based on the bag-of-patches (BOP) -which describe an image as an unordered set of low-level local feature vectors -combined with kernel-based learning have become the state-of-the-art. Kernel-based algorithms require the denition of a proper measure of similarity between BOP representations. The focus of this thesis has been on the denition of probabilistic representations of images based on the BOP assumption and the computation of similarities between such representations with application to kernel learning of image classiers.

Problems and Contributions

We now list the four problems that we addressed in this thesis with the proposed solutions.

Modeling Image as Adapted Gaussian Mixture Model

As already mentioned, the most successful image representation to date in computer vision is certainly the BOP. BOP representations are very simple, yet eective and demonstrated state-of-the-art performance in several evaluations [START_REF] Everingham | [END_REF], Everingham et al. 2006, Everingham et al. 2007, Everingham et al. 2008, Everingham et al. 2009] although they disregard all information about the spatial layout of the feature descriptors. In this thesis, we will work only with BOP models.

As measuring directly the similarity between BOPs (model-free approaches) is costly, model-based approaches have been proposed. They consist in (i) modeling each set of feature vectors as a distribution and (ii) dening a measure of similarity between the vector sets as the similarity between their respective distributions.

There are two leading model-based approaches in the case of the BOP representation:

• The rst one, the bag-of-visual-words (BOV), models an image as a discrete distribution [START_REF] Sivic | [END_REF], Csurka et al. 2004]. The BOV is based on an intermediate representation, the visual vocabulary, which is estimated oine on a large set of low-level feature vectors. Each image is characterized 1.2. Problems and Contributions 3 by a histogram of visual words frequencies. One of the main limitations of this approach is the assumption that the distribution of feature vectors in any image can be known a priori.

• The second one models an image as a continuous distribution, generally a Gaussian Mixture Model (GMM) [START_REF] Jebara | [END_REF], Jebara et al. 2004, Goldberger et al. 2003, Moreno et al. 2003, Vasconcelos 2004, Vasconcelos et al. 2004] and measures the similarity as the Kullback-Leibler divergence (KLD) or the probability product kernel (PPK) between GMMs. However, these methods have two main shortcomings. First, the robust estimation of the GMM parameters may be dicult as the cardinality of the vector set is small. Second, computing the similarity between two GMMs is expensive.

In chapter 4, we propose a novel GMM-based representation of images which is based on the maximum a posteriori (MAP) adaptation of a "universal" GMM. The advantages of this approach are twofold. MAP provides a more accurate estimate of the GMM parameters compared to standard maximum likelihood estimation (MLE). Moreover, there is a correspondence between the Gaussians of two GMMs adapted from a common distribution and one can take advantage of this fact to compute eciently the probabilistic similarity. This work presented in chapter 4 was published in CVPR'08 [Liu & Perronnin 2008].

Modeling Images as Mixtures of Reference Images

We then address what we believe is an inherent limitation of traditional measures of similarity between distributions, such as the KLD or PPK. They give a high similarity when two distributions match globally but a low similarity when they match partially. This implies that two GMMs will typically have a high similarity if all their Gaussians match (at least approximately) but may have a low similarity because few Gaussians in one of the GMMs match poorly the Gaussians of the other GMM. If we translate this assertion into the image domain, this means that two images will have a high similarity if they match completely, e.g. same object in the same background, but may have a low similarity because they match partially.

In chapter 5 we thus propose to approximate an image, modeled as a GMM, as a convex combination of K reference image GMMs (later referred to as MOM for mixture of mixtures) and to characterize this image as a K-dimensional vector of mixture weights. These mixture weights measure a soft count of matching Gaussian components between the image to be described and each reference image. Hence, they encode a similarity which favors local matches (i.e. strong matches of individual Gaussians) and is therefore fundamentally dierent from traditional KLD or PPK.

The vector of mixture weights may be used as input to a discriminative classier for categorization.

Although the computation of the mixture weights is a convex optimization problem, its direct optimization is dicult. We propose two approximate optimization algorithms: the rst one based on traditional sampling methods, the second one based on a variational bound approximation of the true objective function. This work presented in chapter 5 was published in CVPR'09 [Perronnin & Liu 2009].

Contextual Similarity based on MOM

We say that a similarity between two distributions p and q is absolute if it only depends on p and q. We say that the similarity is contextual in the other case. We can see that the similarity dened between two images in the previous subsection is contextual as it depends on a set of reference images: the context. However, dening the similarity between two images using an explicit set of context images is both costly and cumbersome.

In chapter 6, we propose an alternative measure of contextual similarity between distributions: the similarity between two distributions p and q is measured in the context of a third distribution u. The similarity is computed following similar approximate optimization techniques proposed for the MOM approach. Although we do not observe a signicant increase of accuracy, an advantage of the proposed similarity is that the context does not depend explicitly on a set of reference images. An extension, applying ideas proposed in chapter 6 to discrete distribution with application to image retrieval, was published in CVPR'09 [Perronnin et al. 2009].

Explicit Data Embedding for Large-Scale Learning

We focus on the problem of large-scale kernel learning on BOV representations. Linear classiers are fast to learn and to evaluate but their accuracy is generally limited. Non-linear classiers outperform signicantly linear classiers on BOV representations but are dicult to scale to large training sets.

However, non-linear kernel classiers rely on an implicit mapping of the data such that non-linear classication in the original space corresponds to linear classication in the new space. It has been proposed to perform an explicit (possibly approximate) mapping of the data and to learn directly linear classiers in the new space.

In chapter 7, we experiment with three approaches to BOV embedding: 1) kernel PCA (kPCA) [START_REF] Schölkopf | [END_REF]], 2) a modied kPCA we propose for additive kernels and 3) random projections for shift-invariant kernels [START_REF] Rahimi | [END_REF]]. An important conclusion is that simply square-rooting BOV vectors -which corresponds to an exact mapping for the Bhattacharyya kernel -already leads to large improvements, often quite close to the best results obtained with additive kernels. Another conclusion is that, although it is possible to go beyond additive kernels, the embedding for non-additive kernels comes at a much higher cost. The work presented in chapter 7 was published in CVPR '10 [Perronnin et al. 2010].

Outline of thesis

The structure of this thesis is as follows.

• In chapter 2, we give more detailed reviews of related work, especially on BOP approaches and the similarity between BOPs. In this chapter, we review BOP approaches to image categorization. The literature review will be split into three parts. In the rst part, we review very briey the local feature detection and extraction. In the second part, we review the measures of similarity between BOP representations. In the third part, we review briey kernel based classication.

Patch Detection and Extraction

There are mainly three strategies for patch detection:

• Interest Points: We just provide a few examples of interest points based methods. [Lindeberg 1998] developed a scale invariant blob detector, where a blob is dened by a maximum of the normalized Laplacian in scale-space. The original Harris corner detector [START_REF] Harris | [END_REF]] is invariant to rotation but is not scale-invariant. Multi-scale Harris by [Mikolajczyk & Schmid 2004] was adapted to solve this problem by selecting the points in the multi-scale representation. The Harris-Laplace detector [Mikolajczyk & Schmid 2001] is invariant to rotation and scale changes. The points are detected by the scaleadapted Harris function and selected in scale-space by the Laplacian of Gaussian operator. (see [Mikolajczyk et al. 2005] for a detailed overview)

• Random Sampling: [START_REF] Marée | [END_REF]] and [START_REF] Nowak | [END_REF] showed experimentally that random sampling could outperform interest points detectors.

• Dense Sampling: similarly, [START_REF][END_REF][START_REF] Perona | [END_REF] showed experimentally that using regular grids to select patches could outperform interest points detectors as well.

It is possible to combine dierent strategies. The winning system of the PAS-CAL VOC 2007 Challenge which used the combination of interest points detectors and dense sampling was shown to outperform each method taken separately [START_REF] Everingham | [END_REF].

One or multiple feature descriptors are computed for each extracted patch. We provide a few examples among the most well-known descriptors:

• The SIFT [Lowe 2004] descriptor subdivides the patch into a set of regions and computes a histogram of local oriented gradients in each subregion. Typically, there are 4 × 4 = 16 subregions and each histogram contains 8 bins which results in a 128 dimensional descriptor.

• The PCA-SIFT [START_REF] Ke | [END_REF] consists in computing the gradient in horizontal and vertical directions at each pixel of the patch and then reducing the dimensionality of the resulting representation using Principal Component Analysis (PCA). This typically results in a 36 dimensional feature.

• The SURF [Bay et al. 2006] descriptor is similar to the SIFT in the sense that the patch is subdivided regularly into a set of subregions. In each subregion, four-dimensional features are computed based on Haar wavelets. This results in a 64 dimensional descriptor.

• Some of the previous descriptors can be extended to color features. In this thesis, we extract low-level features on regular grids at multiple scales and make use of two types of low-level features: the rst features are SIFT descriptors and the second ones are based on simple RGB statistics.

Measuring the Similarity between Bags-of-Patches

We rst review model-free approaches, i.e. the methods that directly compare sets of patches. We then review model-based approaches which consist in estimating a model (typically probabilistic) from each BOP representation and then computing the similarity between BOPs as a similarity between the models. These approaches can be divided into two sub-classes as a BOP can be modeled with a discrete or continuous distribution.

Model-Free Approaches

In this section we review those approaches which measure directly the similarity between two unordered feature sets. We assume that we have two feature sets X = {x i , i = 1...T X } and Z = {z j , j = 1...T Z }. The simplest approach to dening a measure of similarity between such sets is the sum of the similarities between all possible pairs of feature vector. Let k(., .) be a positive semi-denite kernel (psd). The summation kernel [Haussler 1999] is dened as

K S (X, Z) = 1 T X 1 T Z T X i=1 T Z j=1 k(x i , z j ). (2.1)
However, its discriminative ability is compromised as all possible matchings between features are combined with equal weights. The good matchings could be easily swamped by the bad ones. [START_REF] Wallraven | [END_REF]] and [START_REF] Boughhorbed | [END_REF] both proposed a matching kernel that only considered the similarities of the best matched local features:

K M (X, Z) = 1 2   1 T X T X i=1 max j=1...T Z k(x i , z j ) + 1 T Z T Z j=1 max i=1...T X k(z j , x i )   . (2.2)
Unfortunately, the "max" operator makes this kernel non-Mercer (not psd).

Lyu [Lyu 2005] proposed a Mercer kernel to quantify the similarities between feature sets. The kernel is a linear combination of the p-exponentiated kernels between local features:

K(X, Z) = 1 T X 1 T Z T X i=1 T Z j=1 [k(x i , z j )] p . (2.3)
p is the kernel parameter and p > 1 gives more inuence to good matchings. The Earth Mover's Distance (EMD) [Rubner et al. 1998] is a measure of similarity between sets of features and aims at nding an optimal matching that would be required to transform one set into the other. It is dened as (2.4) subject to the following constraints:

EM D = max f ij i=1...T X j=1...T Z T X i=1 T Z j=1 k(x i , z j )f ij ,
f ij ≥ 0, (2.5
)

T Z j=1 f ij ≤ 1, (2.6) T X i=1 f ij ≤ 1, (2.7) T X i=1 T Z j=1 f ij = min(T X , T Z ). (2.8)
f ij is the ow between x i and z j . The computation of the EMD requires the computation of a similarity between all pairs of components of the two sets and the optimization of a transportation problem whose complexity is cubic in the number of features.

To address the computational issue, [Grauman & Darrell 2005a] makes use of an embedding of the EMD based on the work of [START_REF] Indyk | [END_REF]. However, the approximation suers from a high error when the feature dimension increases.

All the previous approaches have high computational complexity: typically O(T X T Z ) with T X and T Z varying from a few hundreds to a few thousands.

[ Grauman & Darrell 2005b] proposed the Pyramid Match Kernel (PMK) to address the computational cost issue. It partitions the feature space in a hierarchical manner, from ne to coarse and counts the number of correspondences between two feature sets at each level of the hierarchy. While the PMK is ecient for a small number of dimensions (e.g. 2), its cost grows exponentially with the number of dimensions.

Model-Based Approaches: Discrete Distributions

In this section, we review the approaches which model an image as a discrete distribution, i.e. bag-of-visual-words representation (BOV). There are three main steps in a BOV based system: oine visual vocabulary generation, histogram computation and histogram similarity computation.

Visual Vocabulary Generation

The visual vocabulary can be obtained oine on a set of BOPs by unsupervised or supervised learning methods.

The k-means [Sivic & Zisserman 2003, Csurka et al. 2004] is an unsupervised clustering algorithm which proceeds by iterated assignments of points to their closest cluster centers and re-computation of the cluster centers. The advantage of k-means is its simple and ecient implementation. One drawback of k-means is that most of the centroids will end-up in dense regions which do not necessarily correspond to discriminative patches. [START_REF] Jurie | [END_REF] proposed a radius-based clustering, which avoids setting all cluster centers into high density areas and assigns all features within a xed radius of similarity r to one cluster, where r is a parameter of the algorithm. [START_REF] Wu | [END_REF] proposed to use the Histogram Intersection Kernel (HIK) instead of the popular Euclidean distance to cluster features into visual words. They also proposed to use the one-class SVM for the clustering and demonstrated higher accuracy.

In [START_REF] Farquhar | [END_REF], Zhang et al. 2005], category specic vocabularies are trained and agglomerated into a single vocabulary. Although substantial improvements were obtained, this approach is impractical for a large number of categories as the size of the agglomerated vocabulary and the histogram representation grow linearly with the number of categories. Especially when the number of categories is large, this makes the histogram computation costly and the classier learning challenging. Therefore, a compact visual vocabulary can provide a lower-dimensional representation and eectively avoid these diculties. [Winn et al. 2005, Fulkerson et al. 2008, Lazebnik & Raginsky 2009] make use of the mutual information between the features and category information to reduce the number of visual words without sacricing the discriminative power of the vocabulary. [Moosmann et al. 2006] proposed an ecient alternative, in which training examples are recursively divided using a randomized decision forest and where the splits in the decision trees are comparisons of a descriptor dimension to a threshold. [START_REF] Perronnin | [END_REF]] characterize images using a set of category specic histograms, where each histogram describes whether the content can be best modeled by the universal vocabulary or by its corresponding category vocabulary. [START_REF][END_REF] proposed to unify the vocabulary construction with classier training, and then to encode an image by a sequence of visual bits that constitute the semantic vocabulary.

The visual vocabulary generated by the unsupervised approaches is universal i.e. it is independent of the category set, but its discriminative ability is generally poor as it ignores label information. While supervised approaches explicitly incorporate the category information and can be more discriminative, we believe that they are not scalable. Indeed, every time a category is added to the system all image histograms have to be recomputed and all classiers to be retrained.

Histogram Computation

The BOV approach characterizes an image by a histogram of visual word frequencies. There are two strategies to assign features to visual words: hard assignment and soft assignment. We assume that we have a set of features extracted from an image X = {x t , t = 1...T } where T is the number of features.

In hard assignment a feature vector is assigned to the single best representative visual word. The advantages of hard assignment are the simplicity and the fact that it leads to sparser histograms compared to soft assignment. The main problem is that two close patches might be assigned to two dierent centroids and therefore lead to two dierent representations.

There are two approaches to soft assignment. The rst one consists in making the assignment a decreasing function of the Euclidean distance of the descriptor to the centroid. [van Gemert et al. 2008] uses for this purpose the Gaussian kernel. However, this is somewhat heuristic and requires the hand tuning of the bandwidth parameter. A more principled alternative consists in performing probabilistic clustering using typically a Gaussian Mixture Model (GMM) [Farquhar et al. 2005, Winn et al. 2005, Perronnin et al. 2006]. The soft assignment is then computed as the posterior probability of the Gaussian knowing the observations.

Let us call γ t (i) the hard/soft assignment of x t to centroid/Gaussian i, then the BOV is computed as:

1 T T t=1 γ t (i).
(2.9)

Chapter 2. Literature Review

Similarity Computation

We assume that we have two BOV histograms a = {a i , i = 1...N } and b = {b i , i = 1...N }. Among the most popular kernels are the Bhattacharyya kernel (BHA), the χ 2 kernel (CHI2) and the Intersection kernel (INT), all of which are positive semi-denite kernels (psd):

K bha (a, b) = N i=1 a i b i , (2.10) K chi2 (a, b) = 2 N i=1 a i b i a i + b i , (2.11) K int (a, b) = N i=1 min(a i , b i ).
(2.12)

If K is a psd kernel, exp(γK) with γ > 0 is also guaranteed to be a psd kernel. Hence, all the previous kernels can be exponentiated as K exp = exp(γ(K -1)). The -1 in the kernel is to ensure that the exponentiated kernel values are upper-bounded by 1. Also it makes these kernels easier to relate to well-known kernels: K exp bha is the rbf kernel on the square-rooted vectors, K exp chi2 is a popular kernel used for instance in [START_REF] Zhang | [END_REF], Vedaldi et al. 2009], and K exp int is the Laplacian kernel:

K exp bha (a, b) = exp - γ 2 N i=1 ( √ a i -b i ) 2 , (2.13) K exp chi2 (a, b) = exp - γ 2 N i=1 (a i -b i ) 2 a i + b i , (2.14) K exp int (a, b) = exp -γ N i=1 |a i -b i | . (2.15)
The parameter γ controls the neighborhood size around the training samples and therefore the non-linearity of the classier.

Model-Based Approaches: Continuous Distributions

In this section we review the approaches which model an image as a continuous distribution. [Moreno et al. 2003, Farquhar et al. 2005] proposed to model an image with a single Gaussian with full covariance.

However, the monomodal assumption is generally too restrictive. [Goldberger et al. 2003, Vasconcelos 2004, Vasconcelos et al. 2004] proposed to model an image as a mixture of Gaussians, generally with diagonal covariance.

Similarity Computation

A probabilistic kernel is dened between the distributions, such as the Probability Product Kernel (PPK) and the Kullback-Leibler Kernel (KLK). There is a closed 2.3. Kernel-Based Learning 13 form solution for the PPK or the KLK between two Gaussians. However there is generally no closed form solution for them in the case of GMMs. We only provide denitions of the kernels and will discuss in chapter 4 how these measures can be approximated in the case of mixture models.

We assume that we have two continuous distributions p and q dened on the space R D (D is the dimensionality of the low-level features). Jebara et al. proposed the PPK [START_REF] Jebara | [END_REF], Jebara et al. 2004] as a kernel between distributions:

K ρ ppk (p, q) = x∈R D p(x) ρ q(x) ρ dx (2.16)
where ρ is a parameter. The PPK is trivially psd and has two special cases. When ρ = 1, the PPK takes the form of the expectation of one distribution under the other. This is referred to as the Expected Likelihood Kernel (ELK):

K elk (p, q) = x∈R D p(x)q(x)dx = E p [q(x)] = E q [p(x)]
(2.17)

When ρ = 1/2, it is known as the Bhattacharyya Kernel (BHA):

K bha (p, q) = x∈R D p(x) q(x)dx. (2.18)
This is an upper bound on the Bayesian error. The Kullback-Leibler Divergence (KLD) [Kullback 1968] is dened as follows:

KL(p||q) = x∈R D p(x) log p(x) q(x) dx. (2.19)
The symmetric KL is given by: SKL(p, q) = KL(p||q) + KL(q||p).

(2.20)

The KLK [START_REF] Moreno | [END_REF]] can then be dened by exponentiating the symmetric KLD (not necessarily psd): (-γSKL(p, q)). (2.21) where γ > 0 is a kernel parameter.

K klk = exp

Kernel-Based Learning

We assume that we have a set of N labeled training samples {(x i , y i ), i = 1...N } where each x i is an image representation (not to be mistaken for the x i of BOP in section 2.2.1) and each y i ∈ {-1, +1} is a binary label.

In kernel based classication, the decision function has the form: .22) with α = [α 1 , ..., α N ] an N -dimensional vector of parameters, β an oset parameter and K(x, x i ) the similarity between x and training sample x i . The most popular kernel classier is certainly the Support Vector Machine (SVM) [Vapnik 1995]. The parameters α and β are learned by minimizing the following loss function:

f (x) = N i=1 α i K(x, x i ) + β. ( 2
1 N N i=1 hinge (f (x i ), y i ) + λ||f || 2 2 (2.23)
where hinge (f (x i ), y i ) = max(0, 1 -f (x i )y i ) is the hinge loss and λ is the regularization parameter for penalization. The major advantage of the SVM is that it leads to a sparse solution in α, thus reducing the cost of classication.

An alternative classier is Sparse Logistic Regression (SLR) [Krishnapruam et al. 2005] which minimizes the following loss function:

1 N N i=1 log (f (x i ), y i ) + λ||α|| 1 (2.24)
where log (f

(x i ), y i ) = log(1 + exp(-f (x i )y i )).
The L 1 regularization leads to a sparse solution, as is the case of the SVM. Both SVM and SLR lead to similar results as observed experimentally in [START_REF] Krishnapruam | [END_REF]. We used SLR in most of our experiments.

Caltech-256

The Caltech-256 [START_REF] Grin | Caltech-256 Object Category Dataset[END_REF]] database has a total of 29,780 images containing 256 categories. Each category contains at least 80 images. We show the taxonomic tree of all the 256 categories proposed by Greg Grin [Grin 2007] on Figure 3.3.

ImageNet

ImageNet is an image database organized according to the WordNet hierarchy and collects approximately 9.4M images corresponding to almost 15K concepts. Images of each concept are quality-controlled and human-annotated using the Amazon In this chapter, we focus on those methods which model images as continuous distributions (GMMs) [START_REF] Jebara | [END_REF], Jebara et al. 2004, Goldberger et al. 2003, Moreno et al. 2003, Vasconcelos 2004, Vasconcelos et al. 2004]. We note that these approaches have two main shortcomings:

• First, the robust estimation of the GMM parameters may be dicult if the cardinality of the feature set is small. For instance, the number of features extracted from an image typically varies from a few hundreds up to a few thousands. One could increase this number, e.g. by using a denser grid in the case of regular extraction or by lowering the detection threshold in the case of interest points detectors, but this would also signicantly increase the cost of the feature extraction and the GMM estimation.

• Second, as there is no closed form solution for the KLK or the PPK between two GMMs, the cost of traditional approximations is typically quadratic in the number of Gaussian components.

In this chapter, we present a novel approach to compute the similarity between two unordered variable-sized vector sets with application to image categorization.

It consists in representing one image by a GMM obtained through maximum a posteriori (MAP) adaptation of a common "universal" GMM. This oers two main advantages:

• First, MAP estimation is more accurate than MLE in the challenging case where the training data is scarce as the universal model provides a priori information on the location of the parameters in the whole parameter space.

We will show experimentally that this a priori information needs not to be exact: even if the universal model is learned on a set of images which is not directly related to the task at hand, excellent performance is obtained.

• Second, if two GMMs are adapted from a common distribution, there is a one-to-one correspondence between their Gaussians. We make use of this correspondence to derive approximations of the PPK and KLK with a cost linear in the number of Gaussians.

Note that the idea of learning visual vocabularies -modeled as GMMsthrough the adaptation of a common universal vocabulary has already been used in [START_REF] Perronnin | [END_REF]]. However, in [START_REF] Perronnin | [END_REF]] the adapted vocabularies are class-GMMs and images are modeled with histograms of visual-word occurrences while in this chapter the adapted vocabularies are image-GMMs.

The remainder of this chapter is organized as follows. In section 4.1 we describe the estimation of universal and adapted GMMs. In section 4.2 we rst present two similarity measures between distributions, the PPK and the KLD, review how they were approximated in the state-of-the-art and then propose our approximations. In section 4.3 we provide experimental results on three databases: PASCAL VOC2007, Scene-15 and Caltech-256 and compare to the state-of-the-art. Finally we draw a brief conclude in section 4.4.

Image Representation

Let us rst introduce our notations. The parameters of a GMM are denoted λ = {w i , µ i , Σ i , i = 1...N } where w i , µ i and Σ i are respectively the weight, mean vector and covariance matrix of Gaussian i and N denotes the number of Gaussians. Let x t be an observation vector and q t its associated hidden variable, i.e. the variable indicating which Gaussian emitted x t .

The likelihood that observation x t was generated by the GMM is:

p(x t |λ) = N i=1 w i p i (x t |λ) . (4.1)
where p i (x t |λ) = p(x t |q t = i, λ). Finally, γ i (x t ) = p(q t = i|x t , λ) is the occupancy probability, i.e. the probability that observation x t was generated by Gaussian i. It is computed using Bayes formula:

γ i (x t ) = w i p i (x t |λ) N j=1 w j p j (x t |λ) . ( 4

.2)

We now describe the training of the universal model and the adapted image models.

Training the Universal Model

The universal GMM is supposed to describe the content of any image and, therefore, it should be trained oine on a varied set of images. Let λ u denote the parameters of the universal GMM. Let X = {x t , t = 1...T } be the set of training vectors. The estimation of λ u may be performed by maximizing the log-likelihood function log p(X|λ u ). The standard procedure for MLE is the Expectation Maximization (EM) algorithm [START_REF] Dempster | [END_REF]. For the E-step, the values γ i (x t ) are computed. We provide here for completeness the M-step re-estimation equations [Bilmes 1998]:

ŵu i = 1 T T t=1 γ i (x t ) , (4.3
)

μu i = T t=1 γ i (x t )x t T t=1 γ i (x t ) , ( 4.4
)

Σu i = T t=1 γ i (x t )x t x t T t=1 γ i (x t ) -μu i μu i . (4.5)

Training Adapted Image Models

Our primary motivation for learning the image GMMs through the adaptation of a universal model is to overcome the scarcity of the training material. Indeed, only a small number of low-level feature vectors (typically from a few hundreds up to a few thousands) are extracted from one image. We will observe in section 4.3 that this is insucient to train robustly a mixture with a large number of Gaussians (e.g. 100) for each image. In the following, λ a denotes the parameters of an adapted model.

Let X = {x t , t = 1...T } now denote the set of adaptation samples extracted from one image. We use the MAP criterion to adapt a GMM. The goal of MAP estimation is to maximize the posterior probability p(λ a |X) or equivalently log p(X|λ a ) + log p(λ a ). Hence, the dierence with MLE is in the assumption of a prior distribution p(λ a ). To perform MAP learning, one has to (i) choose the prior distribution family and (ii) specify the parameters of the prior distribution.

It was shown in [Gauvain & Lee 1994] that the prior densities for GMM parameters could be adequately represented as a product of Dirichlet (prior on weight parameters) and normal-Wishart densities (prior on Gaussian parameters). When adapting a universal model with MAP to more specic conditions, it is natural to use the parameters of the universal model as a priori information on the location of the adapted parameters in the parameter space. As shown in [Gauvain & Lee 1994], one can also apply the EM procedure for MAP estimation. The M-step re-estimation equations are provided here for completeness:

ŵa i = T t=1 γ i (x t ) + τ T + N × τ , ( 4.6
)

μa i = T t=1 γ i (x t )x t + τ µ u i T t=1 γ i (x t ) + τ , ( 4.7
)

Σa i = T t=1 γ i (x t )x t x t + τ [Σ u i + µ u i µ u i ] T t=1 γ i (x t ) + τ -μa i μa i . (4.8)
The relevance factor τ keeps a balance between the a priori information contained in the generic model λ u and the new evidence contained in X. If a mixture component i was estimated with a small number of observations T t=1 γ i (x t ), then more emphasis is put on the a priori information. On the other hand, if it was estimated with a large number of observations, more emphasis is put on the new evidence. Hence MAP provides a more robust estimate than MLE when little training data is available. The parameter τ is generally set manually [Gauvain & Lee 1994, Reynolds et al. 2000].

For a given number of Gaussians, the cost of one EM iteration is (almost) identical for MLE and MAP. The only dierence is the addition in the M-step of MAP of the a priori information in the statistics (compare equations 4.3, 4.4 and 4.5 to 4.6, 4.7 and 4.8 resp.) However, as MAP uses some a priori information on the location of the parameters, it requires a smaller number of EM iterations to reach an accurate estimate. Therefore, it is signicantly faster compared to MLE. This statement will be veried experimentally.

We nally note that an adapted model contains the same number of Gaussians as the universal model from which it is adapted.

Measures of Similarity of GMMs

In the following, we rst present two measures of similarity between distributions and review how they were approximated in state-of-the-art. We then propose our approximations.

Probability Product Kernel

Previous Approximatins

We recall that the probability product kernel (PPK) [START_REF] Jebara | [END_REF]] between probability distributions p and q is dened as follows:

K ρ ppk (p, q) = x∈R D p(x) ρ q(x) ρ dx . (4.9)
There is a closed form solution for the PPK between two Gaussians:

K ρ ppk (p, q) = (2π) (1-2ρ)D/2 | Σ | 1/2 | Σ p | -ρ/2 | Σ q | -ρ/2 exp - ρ 2 µ p Σ -1 p µ p - ρ 2 µ q Σ -1 q µ q + 1 2 µ Σµ , (4.10)

Measures of Similarity of GMMs 25

where µ p , Σ p and µ q , Σ q are respectively the mean and covariance matrix of Gaussian p and q, Σ = (ρΣ

-1 p + ρΣ -1 q ) -1 , µ = ρ(Σ -1 p µ p + Σ -1 q µ q )
and D is the dimensionality of the feature vectors.

However there is no closed form solution for the PPK in the case of mixtures of Gaussians except for the special case ρ = 1 (which led to poor results in preliminary experiments). In the case of a mixture model, we have p(x) = N i=1 α i p i (x) and q(x) = M j=1 β j q j (x). In [Jebara & Kondor 2003] (section 4) the following approxi- mation is suggested:

K ρ ppk (p, q) ≈ N i=1 M j=1 α i β j K ρ ppk (p i , q j ) . (4.11)
When ρ ≤ 1 this approximation corresponds to an upper-bound on the true value of K ρ ppk (p, q) and when ρ ≥ 1 it is a lower-bound. [Hershey & Olsen 2008] proposed a variational bound method to approximate the Bhattacharyya Kernel (BHA), i.e. when ρ = 1/2 (c.f. formula 2.18). It leads to the following bound:

K bha (p, q) ≥ N i=1 M j=1 α i β j K 2 bha (p i , q j ). (4.12)
In all experiments, we used 4.11 as an approximation of K bha1 .

The evaluation of the PPK between two GMMs which contain respectively M and N Gaussians requires the computation of M × N PPKs between individual Gaussians. This cost may be a handicap in the case of large values of M and N.

Proposed Approximation

We make use of the fact that two mixtures of Gaussians have been adapted from the same generic model to speed-up the computation. Indeed, [Reynolds et al. 2000] rst noticed that there is a one-to-one correspondence between the i-th Gaussian of an adapted GMM and the i-th Gaussian of the GMM it is adapted from. By transitivity, it means that there is a one-to-one correspondence between the i-th Gaussians of two GMMs adapted from the same GMM (we recall that we necessarily have M = N in our adaptation framework). Consequently, in our case, the terms K ρ ppk (p i , q i ) dominate the previous sum and the PPK may be further approximated as follows:

K ρ ppk (p, q) ≈ N i=1 α i β i K ρ ppk (p i , q i ) . (4.13)
This evaluation requires only the computation of N PPKs between individual Gaussians.

Kullback-Leibler Kernel

Previous Approximations

We recall that the Kullback-Leibler Divergence (KLD) between two continuous distributions is dened as follows:

KL(p||q) = x∈R D p(x) log p(x) q(x) dx . (4.14)
There is also a closed form solution for the KLD between two Gaussians:

KL(p||q) = 1 2 log | Σ q | | Σ p | + Tr(Σ -1 q Σ p ) + (µ p -µ q ) T Σ -1 q (µ p -µ q ) -D . (4.15)
However, no closed-form expression exists for the KLD between two GMMs. [START_REF] Moreno | [END_REF]] and [START_REF] Vasconcelos | The Kullback-Leibler kernel as a framework for discriminant and localized representations for visual recognition[END_REF]] approximate the KLD using Monte Carlo (MC) sampling:

KL(p||q) = E p [log p q ] ≈ 1 T T t=1 log p(x t ) q(x t ) (4.16)
where x 1 , ..., x T are sampled from p. [Goldberger et al. 2003] used the unscented transform mechanism to obtain an approximation for KLD between two GMMs:

KL(p||q) ≈ 1 2d N i=1 α i 2d k=1 log p(x i,k ) q(x i,k ) (4.17)
such that:

x i,k = µ p i + ( dΣ p i ) k k = 1, ...d, (4.18) x i,d+k = µ p i -( dΣ p i ) k k = 1, ...d. (4.19)
where d is the number of chosen "sigma" points, µ p i is the mean of Gaussian p i and ( Σ p i ) k is the k-th column of the matrix square root of Σ p i . The unscented transform is similar to the Monte Carlo technique except that the samples are chosen deterministically. However, the cost of both methods can be prohibitive as one has to draw a large number of samples to obtain a reasonable estimate. [Goldberger et al. 2003] and [Vasconcelos 2004] proposed two very similar approximations of the KLD. They are based on a two-step approach: it rst consists in nding a mapping π from the Gaussians of p to the Gaussians of q as follows:

π(i) = arg min j (KL(p i ||q j ) -log β j ) . (4.20)
Then π is used to approximate the KLD:

KL(p||q) ≈ N i=1 α i KL(p i ||q π(i) ) + log α i β π(i) . (4.21)
This approximation is well motivated when Gaussians have little overlap, e.g. when the dimensionality D of the feature space is high. In our experiments, D = 50 (c.f. section 4.3.1). If two GMMs contain respectively M and N Gaussians, computing the mapping function π requires the computation of M × N KLDs between individual Gaussians. [Hershey & Olsen 2007] also proposed a variational approximation for the KLD. The idea is to write:

KL(p||q) = H(p, q) -H(p, p). (4.22)
where H(p, q) is the cross-entropy between p and q and to compute a variational bound on H:

H(p, q) ≤ - N i=1 α i log   M j=1 β j exp(-H(p i , q j ))   . (4.23)
Since this KL approximation is the dierence of two bounds, it is not a bound.

In our experiments we used 4.20 and 4.21 to approximate the KLD2 .

Proposed Approximation

Once again, we can make use of the fact that there is a one-to-one correspondence between the Gaussians of two GMMs adapted from the same model to perform the following approximation: π(i) = i. Under this assumption, the KLD can be rewritten:

KL(p||q) ≈ N i=1 α i KL(p i ||q i ) + log α i β i . (4.24)
Hence, the computation of the KLD requires only N Gaussian computations in our case. We recall that the Kullback-Leibler Kernel (KLK) is dened as:

K klk = exp(-γ(KL(p||q) + KL(q||p)). (4.25)

Experiments

We rst describe our experimental setup. We then report results on three datasets: the PASCAL VOC2007, Scene-15 and Caltech-256 databases.

Experimental Setup

Low-level feature vectors are extracted on regular grids at multiple scales in our experiments. There is an average of 1,000 feature vectors extracted per image per feature type. We make use of two types of low-level features. The rst features are based on local histograms of orientations as described in [Lowe 2004] (128 dimensional features, later referred to as ORH). The second ones are based on RGB Chapter 4. Images as Adapted Mixtures of Gaussians statistics (96 dimensional features, later referred to as COL). In both cases, the dimensionality of the feature vectors is reduced to 50 through Principal Component Analysis (PCA). The universal GMM is trained using the following iterative strategy inspired by HTK [START_REF] Young | [END_REF]. We rst train a GMM with a single Gaussian. We then split it into two by introducing a small perturbation in the mean parameter and retrain the GMM using several iterations of EM. The process of splitting and retraining is repeated until the desired number of Gaussians is obtained. To train the adapted image GMMs with MAP, the default value for the relevance factor is τ = 10.

For the PPK, we choose ρ = 1/2 (i.e. the Bhattacharyya Kernel) as this value leads to the best results in preliminary experiments. To set parameter γ for the KLK (c.f. equation 2.21) we followed [START_REF] Zhang | [END_REF]: γ is equal to the inverse of the mean of the symmetric KL divergence SKL(p, q) between two GMMs (c.f. equation 2.20) as estimated on a subset of the whole training set.

For the classication, we used Sparse Logistic Regression (SLR) [START_REF] Krishnapruam | [END_REF] as a discriminative classier. One linear classier is trained per class in a one-versus-all manner.

We have two separate systems: one for each feature type. The end result is the average of the scores of the two systems (later referred to as ORH+COL).

PASCAL VOC2007

During the VOC2007 competition, the accuracy was primarily measured with the Average Precision (AP). Therefore, we use the mean of AP (averaged over the 20 categories) to make our results easily comparable to the state-of-the-art.

In the following, we start with a comparative evaluation of the proposed approach. We then proceed with the analysis of the impact of parameter τ . We also carry out cross-database experiments showing that, even if the universal model is learned on a dierent database, the performance does not vary signicantly. Finally, we analyze the computational cost of the proposed method on this database.

Results

We compare the performance of the following systems: (i) A system which learns the image BOVs with χ 2 kernel. This system is later referred to as BOV_CHI2.

(ii) The proposed approach with MAP adaptation and the fast one-to-one mapping of Gaussian components (c.f. formula (4.13) for PPK and formula (4.24) for KLK). This system is later referred to as MAP_OTO.

(iii) A system which learns the image GMMs with MLE (using the same iterative strategy which was employed to train the universal model) and the slow one-to-many mapping of Gaussian components (c.f. formula (4.11) for PPK and formulae (4.20) and (4.21) for KLK). This system is later referred to as MLE_OTM.

(iv) An intermediate system which makes use of MAP adaptation as is the case of (ii) but which uses the slow one-to-many scoring of (iii). This system is later referred to as MAP_OTM.

Hence, when comparing (i) and (ii), we can measure the advantage of image GMMs compared to image BOVs. When comparing (iii) and (iv), we can measure the benet of MAP compared to MLE. When comparing (ii) and (iv) we can measure the impact on the accuracy of the fast one-to-one scoring versus the slow one-tomany scoring.

Results are provided on Figure 4.1. We did not represent the performance of BOV_CHI2 on this gure because BOV typically requires a larger number of Gaussians. The best results we obtained with BOV_CHI2 was a mean AP of 52.6% with approximately 4000 Gaussians (for ORH + COL). Then the following conclusions could be drawn from the gures.

• First, the proposed method consistently outperforms the BOV_CHI2.

• Second, because of computationally expensive cost of one-to-many scoring for both MLE and MAP, we only show the performances with 16, 32 and 64 Gaussians. From the results we have shown, we can see that MAP clearly outperforms MLE for both PPK and KLK. Especially the performance of the MLE_OTM system starts to drop for more Gaussians while for MAP it continues to increase. This shows that we can learn robustly a larger number of Gaussians with MAP than with MLE.

• Third, the accuracy of PPK_OTO is superior to that of PPK_OTM. This observation came as a surprise as we rst thought that by dropping terms in equation 4.11, we would lose information. Our best explanation is that the bound 4.11 is too coarse an approximation of the PPK. This suggests an alternative approach for computing the PPK similar to that used for KLK: rst nd a matching between the Gaussians of p and q and then approximate the PPK as a weighted sum of PPKs between the matched Gaussians (this approximation might be worth testing in the future).

• Fourth, the accuracy of KLK_OTO is inferior to that of KLK_OTM, but not signicantly so, showing that our one-to-one approximation is a good one.

As we used the standard VOC2007 protocol, our best result is 55.4% which can be compared to those published in the literature. The best result reported on this dataset during the challenge was 59.4% (INRIA-genetic) [START_REF] Marszalek | [END_REF]]. We would like to outline that the cost of training and testing our system is signicantly lower compared to that of the winning system as it made use of 21 channels (while we make use of only 2: ORH + COL) and a sophisticated approach to combine them.

Inuence of Parameters

We now analyze the inuence of the relevance factor τ . τ impacts two competing aspects of our system: • First τ inuences the robustness of the estimation. We can consider two extreme cases. When τ = 0, MAP turns into MLE and the parameters are not estimated robustly as was shown in the previous experiments. When τ = ∞, the image GMMs remain equal to the universal model. As the distance between any pair of images is constant no kernel classier can be learned. The best performance will thus be obtained when an intermediate value between these two extremes is chosen.

• Second τ impacts the proposed fast scoring. Indeed, our fast scoring is only possible if there is a one-to-one correspondence between the Gaussians of two adapted GMMs. The strength of the correspondence will depend on τ . If τ = ∞, the correspondence is maximized and the one-to-one mapping is exact. When τ = 0, the correspondence is weaker.

Hence, the τ which optimizes the robustness (0 < τ < ∞) is necessarily dierent from the τ which optimizes the Gaussian correspondence (τ = ∞).

We present the result in Figure 4.2. This analysis was performed on the 16 Gaussians model using the KLK kernel. We can see that for small values of τ MAP_OTM outperforms MAP_OTO. This shows that, when τ is small the correspondence between the Gaussian of two adapted models is loose and that our one-to-one assumption is too naïve. However, as expected, as τ increases to more reasonable values, the dierence between the two systems becomes narrower. For Chapter 4. Images as Adapted Mixtures of Gaussians both systems the best performance is obtained for τ = 10.

Cross database experiments

As the estimation of the image models with MAP relies on the a priori information contained in the universal model, it is important to understand how the performance of our approach is aected when the universal model is learned on another dataset.

The alternate dataset we used to learn the visual vocabulary contains 120,000 unannotated images from a printing workow of photo albums. We had a look at a small sample of these images to try to understand whether they were representative of the 20 categories found in the PASCAL VOC2007 database. While this set of images contains a very large number of photos of persons, it seems to contain very few (if no) occurrences of the 19 other classes. Hence, we believe that there is a strong mismatch between this dataset and VOC2007. To learn a universal vocabulary, we took a random sub-sample of 2,000 images. This experiment was repeated 10 times with 10 dierent subsamples. We restricted this analysis to the case where we employ the fast one-to-one scoring.

For the PPK and the KLK kernels, the average precision with the standard deviation were 0.542±0.002 and 0.538±0.002 respectively. Clearly, the proposed approach does not seem to be sensitive to the set of images used to train the universal model. Hence the same universal model can be used across dierent category sets. This is a clear advantage when one grows a category set incrementally as one does not need to relearn the universal GMMs, and thus the image GMMs, every time a new category is added.

Computational Cost

We now perform a brief analysis of the computational cost of the proposed approach. For this analysis, we considered GMMs containing 128 Gaussians. The following durations were measured on a 3.1 GHz Xeon TM machine.

The cost of training the GMM of one image with MLE using the iterative strategy of [START_REF] Young | [END_REF] is approximately 430ms while it is only 15ms for MAP. We recall that this dierence is due to the greater number of EM iterations required for MLE compared to MAP. Note that, instead of the iterative approach of [START_REF] Young | [END_REF], we could have used the alternative strategy which consists in starting from multiple random initializations of the parameters and picking the best one, i.e. the one which leads to the highest log-likelihood. However, the cost of this alternative would have been even greater.

We now consider the cost of the kernel computations. On the VOC2007 database, classifying one image takes approximately 240s for the PPK and 31s for the KLK. We estimated it would take almost 28 days to run the experiments with the PPK (128 Gaussians) on this dataset (9,963 images in total). As for the proposed fast scoring based on the one-to-one correspondence, the classication cost is reduced to 2.0s for PPK and 0.4s for KLK. These gures are consistent with the fact that, for both kernels, we expect the proposed one-to-one scoring to be 128 times faster than the one-to-many scoring when GMMs contain 128 Gaussians (linear versus quadratic cost).

Scene-15

For the Scene-15, we only consider the ORH features as the database is only available in grayscale. We choose 100 images per class for training and used the rest for testing which is the standard evaluation procedure [Lazebnik et al. 2006]. We made use of 128 Gaussians to run our PPK and KLK systems. For the BOV baseline with χ 2 kernel, we considered 4096 Gaussians. The nal result was reported as the mean and standard deviation of the results from 10 individual runs. We obtain a 80.4% accuracy (0.7% standard deviation) on the KLK system and 79.0% (0.8% standard deviation) on the PPK system. Both results are better than that of BOV baseline: 78.4% (0.9% standard deviation). Our proposed systems are close to the state-of-the-art reported in [Lazebnik et al. 2006] (81.4% with 0.5% standard deviation) which makes use of the Spatial Pyramid Matching. We do not use geometric information. Our results can also be compared to the very recent results of [START_REF] Zhou | [END_REF]. They report a 75.8% of classication accuracy using a GMM-based modeling of images and up to 85.2% using additional geometric information. Figure 4.3 presents the categories with the best and worst classication rates according to the result of our KLK approach.

Caltech-256

For the Caltech-256, we only considered the ORH features as well because many works report results only in grayscale. Our results are evaluated by using 10, 20 and 50 images per class respectively for training and 25 images per class for testing. We consider GMMs containing 128 Gaussian components with our proposed systems and compare to the baseline BOV_CHI2 (4096 Gaussians). We report the mean and standard deviation of classication rate over 5 individual runs. baseline. However, the KLK approach gains no improvement over the baseline. We obtain a 35.4% (0.5% standard deviation) with 50 training images on PPK which is close to the result reported by Lazebnik et al. (39.0% of accuracy in the challenge of [Grin 2007]). Figure 4.5 shows sample images for the categories with the best and worst classication rate based on the PPK approach.

Conclusion

In this chapter, we introduced a novel approach to compute the similarity between two unordered vector sets. The main contribution was to model each vector set with a generative model a GMM in our case adapted from a common universal model using MAP. We showed that this adaptation framework oers two major advantages compared to the case where the distributions are trained with MLE. First MAP provides a more accurate estimate compared to MLE when the cardinality of the vector sets is small. Second, there is a one-to-one correspondence between the components of adapted mixture models which may be used for fast scoring. This correspondence was used to derive ecient approximations for two kernels on distributions: the probability product kernel and the Kullback-Leibler kernel. This approach was applied to the image categorization problem. We showed that this approach is practical. First, the classication cost is reasonable. Second, the a priori information contained in the universal model needs not to be perfectly representative of the category set under consideration to obtain good results.

Future work could consider the use adaptation techniques other than MAP. Especially, techniques such as maximum likelihood linear regression (MLLR) [START_REF] Leggetter | Maximum likelihood linear regression for speaker adaptation of continuous density hidden Markov models[END_REF], Gales 1998], cluster adaptive training (CAT) [Gales 2000] or eigenvoices [Kuhn et al. 2000] have been shown to yield signicantly better results than MAP in the speech recognition literature when the amount of adaptation data is extremely scarce. We also note that the PPK outperforms the KLK on VOC2007 and Caltech-256 and the KLK outperforms the PPK on Scene-15. This seems to indicate that no kernel always outperforms the other. To avoid the per-database selection of kernel, we could consider principled combinations of kernels using Multiple Kernel Learning (e.g. [START_REF] Varma | [END_REF]).

Introduction

One limitation of previous probabilistic kernels between two GMMs such as the KL and the PPK is that they measure a global match of distributions. In this chapter, we propose to approximate an image, modeled as a GMM, as a convex combination of K reference image GMMs and then to describe the image as the K-dimensional vector of mixture weights. The computed weights encode a similarity that favors local matches (i.e. matches of individual Gaussians) and is therefore fundamentally dierent from the KL or PPK. The vector of mixture weights may then be used as input to a discriminative classier for categorization.

Our approach is related to dissimilarity-based learning which is an alternative to traditional kernel-based learning. In [Pekalska et al. 2002], Pekalska et al. propose to represent an object as a vector of distances with respect to a set of reference objects. The main dierence with ours is that in [Pekalska et al. 2002] each reference object contributes independently to the representation. For instance, if we use the KL as a measure of distance, the distance-based representation will be plagued with the limitations of KL. In our case the reference images contribute jointly to the image representation. This results in a measure of similarity which better takes into account strong matches.

Our approach can also be related to [START_REF] Quelhas | [END_REF], Bosch et al. 2006, Rasiwasia et al. 2007, Rasiwasia & Vasconcelos 2008]. While the BOV represents an image as a vector of posterior visual word probabilities (when using probabilistic vocabularies), these papers propose to represent an image as a vector of posterior concept probabilities. The assumption is that concepts are more semantically meaningful than visual words. These concepts may be learned in an unsupervised fashion [START_REF] Quelhas | [END_REF], Bosch et al. 2006], in which case there is no guarantee that they are semantically meaningful, or in a supervised manner [START_REF] Rasiwasia | [END_REF], Rasiwasia & Vasconcelos 2008] which requires large amounts of training material. Our work is signicantly dierent from those as we score images with respect to other images, not reference concepts. Our intuition is that reference images might be less semantically meaningful than concepts learned in a supervised manner, but more meaningful than visual words. Figure 5.1 displays this intuition.

The rest of this chapter is organized as follows. In section 5.2, we analyze the limitations of traditional approaches between GMMs through a toy example. This leads us to introduce our novel image representation in section 5.3. We show that the vector of mixture weights can be computed through the optimization of a convex objective function. As the direct optimization is dicult, we propose two possible approximations: the rst one based on sampling, the second one based on a variational bound of the objective function. We also discuss convergence issues. In section 5.4 we provide experimental results showing that the proposed framework outperforms a standard kernel-based classier employing the KLK or the PPK. Finally, we draw our conclusions in section 5.5.

Toy Example

Let N (µ, σ) denote the one dimensional Gaussian with mean µ and standard deviation σ. Let us consider the following toy example. Let q be a mixture of two Gaussians:

q = 1 2 N (+2, 1) + 1 2 N (-2, 1
).

(5.1)

We will compare the SKL and PPK between q and three distributions:

p 1 = N (-2, 1) , (5.2) p 2 = N (2, 1) ,
(5.3)

p 3 = 1 2 N (2 + δ, 1) + 1 2 N (-2 -δ, 1). (5.4)
where δ is a non-negative value (c.f. Figure 5.2). To study the limitations of the SKL (c.f. formula 2.20) and the BHA (c.f. formula 2.18) (and not of their approximations), we estimated the measures numerically, replacing the integral by a sum over many tiny intervals.

We have SKL(q, p 1 ) = SKL(q, p 2 ) and BHA(q, p 1 ) = BHA(q, p 2 ) by symmetry. SKL(q, p 3 ) (resp. BHA(q, p 3 )) is an increasing (resp. decreasing) function of δ with SKL(q, p 3 ) = 0 (resp. BHA(q, p 3 ) = 1) if δ = 0. We are interested in the value δ SKL such that SKL(q, p 1 ) = SKL(q, p 2 ) = SKL(q, p 3 ) and δ BHA such that BHA(q, p 1 ) = BHA(q, p 2 ) = BHA(q, p 3 ). We found numerically δ SKL ≈ 2.0 and δ BHA ≈ 1.5. The value δ SKL was chosen to represent p 3 on Figure 5.2. We can see that with such a value, while q and p 3 share a similar shape (bimodal) they are signicantly dierent. On the other hand p 1 and p 2 perfectly match one of the Gaussian components of q but are strongly penalized because they match a single component.

Let us now try to translate what this toy example means in the image domain. Even if there is a strong match between the components of two images, e.g. the two images contain the same object, the SKL (resp. the PPK) might be large (resp. small) because the object occurs in dierent backgrounds or because it is occluded in one of the two images.

Mixtures of Mixtures

Let q = N i=1 π i q i be the GMM that models the image we want to describe. N denotes the number of Gaussian components, π i is the mixture weight for Gaussian i and q i is the i-th Gaussian component. Let {p k , k = 1...K} be a set of K reference GMMs, each one modeling a reference image. We write p k = N k j=1 π k,j p k,j where N k denotes the number of Gaussian components in p k , π k,j is the mixture weight for Gaussian j and p k,j is the j-th Gaussian component.

Our goal is to approximate q as a convex combination of p k 's. Let ω k denote the mixture weight associated with p k . We choose the optimal ω k 's as those which minimize the KL between q and K k=1 ω k p k . This is equivalent to maximizing the following objective function: The SKL between q (black straight line) and p 1 or p 2 (green and blue dashed lines respectively) is approximately the same as the SKL between q and p 3 (dotted red line). This is a convex optimization problem which can be solved iteratively using the Expectation-Maximization (EM) algorithm [START_REF] Dempster | [END_REF]. The E-step consists in computing the occupancy probability γ k (x) i.e. the probability that observation x was generated by the k-th reference image:

E = x∈R D q(x) log K k=1 ω k p k (x) dx . ( 5
γ k (x) = ω k p k (x) K j=1 ω j p j (x)
.

(5.7)

The M-step leads to the following estimate:

ωk = x∈R D q(x)γ k (x)dx. (5.8)
However, the computation of the previous integral is dicult as there is no closed form formula for ratios of GMMs. We consider two possible approximations using: (i) a sampling method and (ii) a lower-bound method.

Sampling Approximation

Let {X = x t , t = 1...T } be a set of T vectors distributed according to q. This might be a set of feature vectors drawn from q (Monte-Carlo sampling). This might also be the set of low-level feature vectors directly extracted from the image we want to characterize.

If the number of samples T is large enough, we can use the law of large numbers and approximate the objective function (5.5) as follows:

E ≈ 1 T T t=1 log K k=1 ω k p k (x t ) .
(5.9)

This remains a convex objective function which can be optimized with respect to the ω k 's using the EM algorithm. The E-step consists in computing the values γ k (x t ) for each sample x t and each reference GMM p k . The M-step gives the following estimates:

ωk = 1 T T t=1 γ k (x t ).
(5.10)

We note that we would have obtained the same re-estimation formula if we had applied the law of large numbers on equation 5.8 directly.

Lower-Bound Approximation

As explained in the previous sub-section, the mixture weights ω k can be estimated directly from the low-level features extracted from the image to be described as in a Maximum Likelihood Estimation (MLE) framework the samples used to estimate q are supposed to be distributed according to q. In such a case there is no need to estimate q, which might be seen as an advantage of the sampling approximation. However, we will see that it can be benecial to estimate q for two main reasons:

• The rst reason is a practical one. If we want the approximation (5.9) to be reasonably good, T should be large enough which can result in a high computational cost during the E-step at the number of Gaussian computations grows linearly with T .

• Secondly, one can incorporate a-priori information in the model q. In chapter 4, we proposed to estimate the per-image GMMs through the adaptation of a universal GMM using the Maximum a Posteriori (MAP) criterion. This was shown to have two advantages. First MAP estimation leads to a more robust estimate of parameters than MLE in the case of scarce training data. Second, there is a correspondence between the Gaussians of two GMMs adapted from a common distribution and one can take advantage of this fact to speed-up the similarity computation.

We rst present the estimation of the ω k 's in the general case, i.e. whatever the criterion used to estimate q. We then show how it can be speeded-up using the framework of chapter 4.

We rewrite the objective function (5.5) as follows: .11) We use the idea proposed by Hershey and Olsen [Hershey & Olsen 2007] to approximate the KL divergence between two GMMs and introduce a set of variational parameters γ i,k,j which are subject to the constraints:

E = N i=1 π i x∈R D q i (x) log   K k=1 ω k N k j=1 π k,j p k,j (x)   dx. ( 5
0 ≤ γ i,k,j ≤ 1 and K k=1 N k j=1 γ i,k,j = 1.
(5.12)

The function (5.11) becomes:

E = i π i x∈R D q i (x) log   k,j γ i,k,j ω k π k,j p k,j (x) γ i,k,j   dx.
(5.13) Applying Jensen's inequality to the concave log-function, we obtain the following lower-bound:

E ≥ i π i x∈R D q i (x) k,j γ i,k,j log ω k π k,j p k,j (x) γ i,k,j dx . (5.14)
Maximizing the lower-bound with respect to γ i,k,j 's leads to the following bound: .15) where H i,k,j is dened as follows:

E ≥ i π i log   k,j ω k π k,j exp(-H i,k,j )   . ( 5
H i,k,j = H(q i , p k,j ) = - x∈R D
q i (x) log p k,j (x)dx.

(5.16)

H i,k,j is the cross-entropy between q i and p k,j and we recall that it can be computed in closed form in the case where q i and p k,j are Gaussians. We propose to compute the set of ω k 's which optimize the bound on E rather than E. One more time, this is a convex optimization problem which can be solved with an EM-like algorithm. The E-step consists in computing the values γ i,k,j that maximize the bound:

γ i,k,j = ω k π k,j exp(-H i,k,j ) k,j ω k π k,j exp(-H i,k,j )
(5.17)

Taking the derivative with respect to ω k and equating it to zero leads to the M-step: ωk = i,j π i γ i,k,j .

( 5.18) This shows that our similarity computation takes into account the cross-entropy between the individual Gaussians, as is the case of the KL approximation between two GMMs (c.f. equation 4.23). However, our measure of similarity is fundamentally dierent. γ i,k,j is a measure of soft-matching between the Gaussian components q i and p k,j . Hence, the optimal ω k measures the number of soft matches between the components of q and the components of p k . This point will be made clearer in the next subsection. The cross-entropy computations dominate the cost of the EM algorithm. EM requires the computation of N × K k=1 N k cross-entropies which is comparable to the cost of computing K KL divergences between GMMs. If we make use of the framework of chapter 4, all GMMs are trained through the adaptation of a common GMM which contains N Gaussians (N k = N ). In such a case, we can use the fact that there is a correspondence between the Gaussian components of two GMMs adapted from the same GMM, i.e. that H i,k,j is small if i = j and large if i = j. This means that γ i,k,j ≈ 0 if i = j. The previous approximation reduces the cost to N × K cross-entropy computations.

Convergence Issues

Let us go back to our toy example of section 5.2. We want to approximate q as a convex combination of p 1 , p 2 and p 3 . As we have q = 1 2 p 1 + 1 2 p 2 , it is trivial to see that the optimal weights that maximize the objective function (5.11) are

ω 1 = ω 2 = 1
2 and ω 3 = 0 in the case where δ > 0 (if δ = 0 there is an innite number of solutions). Hence, ω 3 = 0 whether δ is very large, meaning that q and p 3 are very dierent, or δ is very small, meaning that q and p 3 are near-identical. Although the perfect matching of Gaussian components, as is the case of our toy example, happens seldom, this shows that our objective function might give too much weight to the near perfect matching of Gaussians, as opposed to SKL or PPK which give too much weight to a global match. Clearly, the optimal solution is a balance between global and local matching.

A simple solution that we found to be very eective to nd a middle-ground between these two extreme situtations is early stopping, i.e. stopping EM after few iterations. An important fact is that early stopping does not change the ranking of the ω's (this property was observed empirically and a formal proof is under investigation). The larger δ, the faster ω 3 will converge to zero.

Early stopping solves also the problematic case where q belongs to the reference distributions. This happens in our image categorization scenario when the reference images are the set of labeled images. If q = p j , then our objective function (5.5) is maximized by ω j = 1 and ω i = 0, ∀i = j. This undesired eect is prevented by early stopping.

Note that we experimented with more elaborate strategies than early stopping. For instance, adding a Dirichlet prior on the parameters ω and performing MAP estimation of the ω's rather than MLE would also avoid the ω's to go to zero. However, we did not nd this approach to be more eective than early stopping.

Beyond KL

As explained in section 5.3.2, the mixture weights ω k are based on the cross-entropy between individual Gaussians. It would be interesting to extend this framework to other measures such as the Bhattacharyya similarity. A heuristic would for instance consist in replacing exp(-H i,k,j ) by B i,k,j = K bha (q i , p k,j ) in the E-step (5.17).

Chapter 5. Images as Mixtures of Reference Images

A more principled approach consists in modifying the objective function. Instead of minimizing the KL between q and K k=1 ω k p k , we propose to maximize their Bhattacharyya similarity:

E = x∈R D q(x) K k=1 ω k p k (x)dx (5.19) = x∈R D N i=1 π i q i (x) K k=1 ω k N k j=1 π k,j p k,j (x)dx.
( 5.20) This leads to a convex objective function which is dicult to optimize directly. One more time, we can optimize a bound on the true objective function rather than the objective function itself. We apply a rst time Jensen's inequality and write:

E ≥ i π i x∈R D q i (x) k ω k j π k,j p k,j (x)dx.
(5.21)

We then introduce a set of variables γ i,k,j which are subject to the constraints: 0 ≤ γ i,k,j ≤ 1 and k,j γ i,k,j = 1. The bound becomes:

i π i x∈R D q i (x) k,j γ i,k,j ω k π k,j p k,j (x) γ i,k,j dx. (5.22)
Applying again Jensen's inequality we obtain the following lower-bound: .23) where B i,k,j is the Bhattacharyya similarity between the two Gaussians q i and p k,j .

E ≥ i π i k,j √ ω k π k,j γ i,k,j B i,k,j . ( 5
Computing derivatives with respect to γ i,k,j and ω k and equating them to zero leads respectively to the E-and M-step. E-step:

γ i,k,j = ω k π k,j B 2 i,k,j k,j ω k π k,j B 2 i,k,j . (5.24) M-step: ωk = ( i π i j √ π k,j γ i,k,j B i,k,j ) 2 k ( i π i j √ π k,j γ i,k,j B i,k,j ) 2 .
(5.25)

Preliminary experiments showed that the principled computation of weights always outperformed the heuristic approach. Again, we use the one-to-one correspondence to speed-up the scoring and set B i,k,j = 0 for i = j.

Experiments

Experimental Setup

We make use of the same experimental setup as in section 4.3.1: including the extraction of features, dimension reduction through PCA, classication using SLR classier.

We evaluated two baseline systems:

• The method of chapter 4 with the KLK.

• The method of chapter 4 with the Bhattacharyya Kernel (PPK with ρ = 1/2).

For two baselines, a universal GMM is rst estimated with all training images. Then the per-image GMMs are estimated through MAP adaptation of the universal GMM. For both the baselines KLK and PPK and the method proposed in this chapter, we used the one-to-one fast scoring described in chapter 4. For the two baselines, an image is represented as a vector of similarities/distances to the set of training images.

PASCAL VOC2007

We compared these two baselines to the three versions of our approach (later referred to as MOM for mixture of mixtures):

• MOM KL sampling: c.f. section 5.3.1.

• MOM KL lower-bound: c.f. section 5.3.2.

• MOM PPK: c.f. section 5.3.4.

We used as reference images the 5,011 training images. For the three proposed approaches, we apply SLR classier directly to the vectors of mixture weights.

Lower-bound vs sampling. We start with the comparison of the sampling and lower-bound approximations for MOM KL. For the sampling approximation, we used directly the low-level features extracted from the image to be described as samples.

Results are shown on Figure 5.3 for the system based on ORH features as a function of the number of Gaussian components in the per-image GMMs. Similar results were obtained for the COL features. The lower-bound approximation clearly outperforms the sampling one. We believe that this dierence can be explained by the a priori information incorporated in q in the case of the lower-bound approximation. In the following, we will not consider the MOM KL sampling approximation anymore.

Inuence of the number of EM iterations. We now study the inuence of the number of EM iterations on the performance of our algorithm. This is shown on Figure 5.4 for the system based on ORH features as a function of the number of Gaussian components in the per-image GMMs. Similar results were obtained for MOM PPK or for COL features. In all cases, the best results are obtained for 3 to 5 iterations. With more than 5 iterations, the accuracy decreases quite rapidly. This demonstrates the importance of early stopping. This shows that the best measure should not only consider global or local similarity but a mix between the two. We can see that the proposed method consistently outperforms the baseline for all feature types, for both KL and PPK and for various numbers of Gaussians. We note that the dierence is more pronounced for KL than it is for PPK. We believe that this is because PPK is more resilient than KLK to the poor matching of individual Gaussian components (c.f. the toy example in section 5.2).

We note that an alternative to the proposed approach would have been to model an image, not as vector of similarities/distances to N reference/training images, but as a vector of K 2 × N similarities/distances between the K components of the image to be described and the K × N components of the N reference images. Using our proposed framework of chapter 4 (i.e. taking into account the correspondence between adapted Gaussians), we can reduce the vector size to K × N . Our initial intuition was that, since this representation contains K times more information than the proposed representation, it should perform better. However in practice, this approach performed worse than the proposed approach. Our best explanation is the very high dimensionality of the vectors: 640,000 dimensions for N = 5, 000 and K = 128.

Scene-15

With the same experimental setup as in 4.3.3, we evaluate our approaches based on lower-bound approximation on Scene-15. Figure 5.6 shows the average classication rate over 10 individual runs. We compare our results with the two baseline systems and observe that our lower-bound approximations outperform the baselines. Our best classication rate is 82.4% (0.6% standard deviation)with the MOM PPK and it is better than the result reported 81.4% in [Lazebnik et al. 2006] and still below [START_REF] Zhou | [END_REF] which makes use of geometric information (85.2%).

Caltech-256

We report the average classication rate over 5 individual runs on Caltech-256 database. Figure 5.7 shows that MOM KL outperforms the baseline KLK and obtains a 38.4% accuracy (0.4% standard deviation) which is much closer to the state-of-the-art of Lazebnik et al. (39.0% of accuracy) reported in the challenge [Grin 2007]. We also observe that MOM PPK gives better result than the baseline PPK when using more training images. In the case of lower-bound approximation, the MOM KL is better than the MOM PPK.

Conclusion

We presented in this chapter a novel image representation. The idea was to approximate an image, modeled by a GMM, as a convex combination of K reference image GMMs and then to describe the image as the K-dimensional vector of mixture weights. We explained that these mixture weights encode a similarity which favors strong local matches of Gaussians components rather than a global match of the distribution, as is the case of traditional distance/similarity measures such as the SKL or PPK.

We applied this framework to image classication and showed on several databases a consistent increase for classication accuracy. This increase seems more important on those datasets where the background inuence is reduced (e.g. . In the next chapter, we discuss the limitations of our previous work and propose a solution to go beyond those limitations. Chapter 6. A Family of Contextual Measures of Similarity Between Distributions of the structure of the contextual set (dened as the neighboring points). Two measures of structural integrity were proposed: a geometric one and an informative one respectively based on the center of gravity and the coding length of the contextual set.

Of highest interest to us are those measures which were proposed in the information retrieval community. [Ponte & Croft 1998] proposed the so-called language modeling (LM) approach. If p, q and u are respectively a template, a query and a context multinomial of dimension D, one can measure the dissimilarity of q and p in the context of u as the Kullback-Leibler (KL) divergence between q and a smoothed version of p:

D i=1 q i log q i ωp i + (1 -ω)u i . (6.1)
Smoothing has two benets over a standard KL divergence between q and p. First, it avoids log(0) eects in the case of sparse vectors. Second, by rewriting equation 6.1 as:

- D i=1 q i log 1 + ω 1 -ω p i u i + C (6.2)
where C is independent of p, we can see that it downweights the inuence of frequent words (indices i with large values u i ) as is the case of TF-IDF. A major issue is the sensitivity to the choice of ω (see e.g. [START_REF] Zhai | [END_REF]] for a study of the impact of ω as well as dierent smoothing schemes).

In this chapter, we introduce a novel family of contextual measures of similarity between distributions: the similarity between two distributions q and p is measured in the context of a third distribution u. In our framework any traditional measure of similarity/dissimilarity has its contextual counterpart. We show that for two important families of divergences (Bregman and Csiszár), the contextual similarity computation consists in solving a convex optimization problem. We apply the contextual similarity to the case of continuous distributions and report the comparison of performance with our previous approach MOM KL in chapter 5 on several datasets.

This chapter is organized as follows. In section 6.2 we give the denition of our contextual measure and discuss its properties. In our framework any traditional measure of similarity/dissimilarity has its contextual counterpart. We show that when the measure to be contextualized belongs to one of two important families of divergences (Bregman and Csiszár), the contextual similarity computation consists in solving a convex optimization problem. In section 6.3 we specialize our method to the case of continuous mixture distributions. The idea is similar in spirit of that used in chapter 5. We provide in section 6.4 categorization results. Finally, we draw conclusions in section 6.5.

Contextual Similarity

We rst introduce a broad denition of contextual similarities which is valid for discrete or continuous distributions, parametric or non-parametric distributions, 6.2. Contextual Similarity 53 etc.

Denition

Let p and q be two distributions to be compared and let u be the distribution that models the context. Typically, in our case, p and q will be two GMMs describing two images. Let f be a traditional (i.e. non-contextual) measure of similarity between distributions. We introduce the following function:

φ f (ω; q, p, u) = f (q, ωp + (1 -ω)u) .
(6.3)

As we are dealing with distributions, φ f is dened over the interval 0 ≤ ω ≤ 1.

We note that in the case where f (q, p) = E q [log p], where E q denotes the expectation under q, φ f (ω; q, p, u) is the distance used in the LM approach to retrieval [Ponte & Croft 1998] (c.f. the introduction).

We dene the contextual similarity cs f as:

cs f (q, p|u) = arg max 0≤ω≤1 φ f (ω; q, p, u). (6.4)
cs f is ill-dened for p = u and we choose the convention cs f = 1/2 in such a case. The intuition behind this measure of similarity is the following one. By maximizing φ f (ω; q, p, u) over ω, we estimate the mixture of p and u that best approximates q. The weight ω which maximizes φ f (ω; q, p, u) reects how much p contributes to the approximation, i.e. whether q is best modeled by the broad domain information contained in u or the specialized information contained in p. Our similarity is fundamentally dierent from the traditional LM approach. Especially, there is no parameter tuning required. The dierence with the contextual similarity dened in the previous chapter 5 is the following one. While in the previous chapter the similarity depends on an explicit set of reference image, here the similarity depends only implicitly on the set of reference images through u (the reference images are used to train u).

By denition cs f is guaranteed to have values in the interval [0, 1]. We note that q = p ⇒ cs f (ω; q, p, u) = 1 but that the converse does not hold. φ f and thus cs f are asymmetric in p and q even if f is symmetric, i.e. cs f (q, p|u) = cs f (p, q|u) in general. There exist various ways to symmetrize the contextual similarity if needed. One way is to combine cs f (p, q|u) and cs f (q, p|u) using for instance a sum or product rule. Another way is to symmetrize φ f , e.g. as follows:

φ f (ω; q, p, u) = f (q, ωp + (1 -ω)u) + f (p, ωq + (1 -ω)u) .
(6.5)

In our experiments, we always made us of the symmetric contextual measure.

Choice of the Function f

We have not yet dened a similarity measure but a family of similarity measures parametrized by the particular choice of the function f . cs f can thus be understood Chapter 6. A Family of Contextual Measures of Similarity Between Distributions as a contextualized version of f . f can be virtually any measure of similarity between distributions. Obviously, f can be a dissimilarity instead of a similarity: this just requires changing the max by a min in (6.4).

Interestingly, not all measures f are good candidates for contextualization.

A simple counter-example is the Expected Likelihood (EL) kernel [START_REF] Jebara | [END_REF]: EL(q, p) = E q [p] = E p [q]. Except in the case where E q [p -u] = 0, it is easy to show that cs EL gives binary values (0/1).

It is advantageous to choose φ to be concave (resp. convex) in ω if f is a similarity (resp. dissimilarity) as one is thus guaranteed to have a unique optimum which simplies the optimization process. In the following, we consider the case of continuous distributions. We show that when f belongs to one of two important families of divergences, φ f is convex in ω.

Bregman divergences. The Bregman divergence between two distributions x and y for a convex function h : Ω → R is dened as:

B h (x, y) = h(x) -h(y) -∇h(y), (x -y) (6.6)
where ∇h denotes the gradient vector of h and ., . the dot product. Intuitively, B h (x, y) can be understood as the dierence between the value of h at point x and the value of the rst-order Taylor expansion of h around y evaluated at x. Special cases of Bregman divergences include the Euclidean distance, the Mahalanobis distance, the Kullback-Leibler divergence or the Itakura-Saito divergence. If φ(ω; q, p, u) = B h (ωp + (1 -ω)u, q), then φ(ω; q, p, u) is convex in ω. To prove this assertion, it is sucient to show that the second order derivative is positive. We have:

∂ 2 ∂ω 2 B h (ωp + (1 -ω)u, q) = (p -u) T ∇ 2 h (ωp + (1 -ω)u) (p -u) (6.7)
where ∇ 2 h denotes the Hessian matrix of h and T the transposition. As h is convex, this quantity is positive by denition and thus φ is convex in ω.

We note however that if φ(ω; q, p, u) = B h (q, ωp + (1 -ω)u), we cannot conclude on the convexity of φ (the second order derivative with respect to ω includes third order derivatives of h).

Csiszár divergences. The Csiszár divergence between two distributions x and y for a convex function h : R → R is given by:

f h (x, y) = z∈R D x(z)h y(z) x(z) dz. (6.8)
where z is an observation vector. Special cases of Csiszár divergences include the Manhattan distance, the Kullback-Leibler divergence, the Hellinger distance or the Rényi divergence. If φ(ω; q, p, u) = f h (q, ωp + (1 -ω)u), then φ(ω; q, p, u) is convex in ω. One more time, it is sucient to show that the second order derivative is positive. We 6.3. Continuous Distributions 55 have:

∂ 2 ∂ω 2 f h (q, ωp + (1 -ω)u) = z∈R D (p(z) -u(z)) 2 q(z) h ωp(z) + (1 -ω)u(z) q(z) dz (6.9)
where h is the second order derivative of h. As h is convex, h ≥ 0 and the previous quantity is positive.

Similarly, if φ(ω; q, p, u) = f h (ωp + (1 -ω)u, q), φ is convex in ω as:

∂ 2 ∂ω 2 f h (ωp + (1 -ω)u, q) = z∈R D q 2 (z)(p(z) -u(z)) 2 (ωp(z) + (1 -ω)u(z)) 3 h q(z) ωp(z) + (1 -ω)u(z) dz (6.10)
is a positive quantity.

Continuous Distributions

We now assume that q, p and u are continuous distributions and let z be an observation vector. In this chapter, we focus on the case of the KL divergence although we could also apply our framework to the Bhattacharyya similarity.

Kullback Leibler (KL)

By denition, we have:

φ KL (ω; q, p, u) = z∈R D q(z) log q(z) ωp(z) + (1 -ω)u(z)
dz. (6.11)

Minimizing the equation 6.11 is equivalent to maximizing:

E = z∈R D q(z) log(ωp(z) + (1 -ω)u(z))dz.
(6.12)

We will focus on the case where q, p and u are mixture models: q = i π i q i , p = j π p j p j and u = j π u j u j where π i , π p j and π u j are respectively the mixture weight for Gaussian q i , Gaussian p j and Gaussian u j . Using previous lower-bound approximation proposed in chapter 5, we have the following lower bound:

E ≥ i π i log   ω j π p j exp(-H q i ,p j ) + (1 -ω) j π u j exp(-H q i ,u j )   .
(6.13) where H q i ,p j and H q i ,u j are dened as follows (cross-entropies):

H q i ,p j = -E q i [log p j ] , (6.14) H q i ,u j = -E q i [log u j ].
(6.15) 56 Chapter 6. A Family of Contextual Measures of Similarity Between Distributions

In the case where q, p and u are Gaussian mixture models (GMMs), there is a closedform formula for H q i ,p j and H q i ,u j . Equation 6.13 can thus be optimized iteratively using the expectation maximization algorithm. At iteration (k + 1), we have: E-step:

γ (k+1) i,j = ω (k) π p j exp(-H q i ,p j ) ω (k) π p j exp(-H q i ,p j ) + (1 -ω (k) )π u j exp(-H q i ,u j ) (6.16)
M-step:

ω (k+1) = i,j π i γ (k+1) i,j
(6.17)

Note that in this case, the cost of the contextual KL is largely dominated by the cost of computing H q i ,p j and H q i ,u j , and not by the optimization process itself. As those values also have to be computed in the case of the KL, the added cost of the contextual KL compared to KL can be neglected. As is the case in the previous chapter 5, we can speed-up the computation by using the one-to-one correspondence discussed in chapter 4 and this leads to γ

(k+1) i,j = 0 if i = j.
6.4 Experiments

Experimental Setup

We make use of the same experimental setup as in section 5.4.1: including feature extraction, PCA reduction, per-image GMMs through MAP adaptation of the universal GMM and classication using SLR classier. We choose the method of chapter 5 with the lower-bound MOM KL as the baseline system. We compare the baseline with our symmetric contextual measure based on the KL (later referred to as CTXT KL).

For the cross-entropy computations, we make use of the one-to-one fast scoring described in chapter 4 which eciently reduces the computational cost. For the early stopping of EM algorithm, we vary the number of iteration from 1 to 5 and report the best accuracy. Each image is represented by the vector of similarities to the set of training images. As opposed to the previous chapter, in general these weights (similarities) do not sum to 1. We apply the SLR classier directly to the vectors of mixture weights for both systems.

PASCAL VOC2007

We report the mean Average Precision on VOC2007 dataset. From the Figure 6.1, we can see that the CTXT KL approach outperforms the MOM KL for various numbers of Gaussians. We obtain a 57.1% AP which is comparable to the performance reported by the leading participants during the challenge (59.4% [Everingham et al. 2007]).

Scene-15

With the same experimental setup as in 5.4.3, we report the average classication rate over 10 individual runs to evaluate the CTXT KL on Scene-15. Figure 6.2 shows that the CTXT KL obtains more improvement of performance than the MOM KL baseline with a small number of Gaussians. However, both approaches reach the same accuracy (81.2%) when the number of Gaussians is 128.

Caltech-256

We report the average classication rate over 5 individual runs on the Caltech-256 database. Figure 6.3 shows that the CTXT KL approach obtains a 39.0% accuracy (0.4% standard deviation) which gives a very slight improvement over the MOM KL approach (38.4% with 0.4% standard deviation).

Conclusion

In this chapter, we presented a novel family of contextual measures of similarity between distributions. We explained that in our framework any measure of similarity or dissimilarity had its contextual counterpart. We showed that for two important families of divergences (Bregman and Csiszár) the contextual similarity computation is a convex optimization problem. We focused on the case of continuous distribution and explained how to compute in practice the similarity for several well-known measures.

Note that this contextual similarity is not signicantly better than the one introduced in the previous chapter 5 but constitutes an interesting alternative. Especially the implicit dependence on the set of reference images makes this similarity much more eective for retrieval.

In the future, we intend to focus on the application of this framework to clustering. Indeed, clustering consists in grouping "similar" images where the notion of similarity depends on the other images contained in the dataset. For instance, while it might make sense to group images of dierent breeds of cats in a general dataset of animal images, it might not in a dataset of cat images. Hence, we believe that clustering is a problem that could benet greatly from the proposed family of measures.

Introduction

Within the computer vision community, annotated data for training and evaluating image categorization algorithms has long been viewed as a scarce resource. This is because the traditional approach to building such datasets is a time consuming process. As a consequence, the datasets which have been (and are still currently) employed to benchmark image categorization algorithms are fairly modest in size. For instance, Scene-15 [Lazebnik et al. 2006], PASCAL VOC2007 [Everingham et al. 2007] and CalTech-256 [START_REF] Grin | Caltech-256 Object Category Dataset[END_REF], three of the most popular benchmarks, contain 4,485, 9,963 and 29,780 images respectively.

However, this perception is drastically changing as large quantities of quality labeled data are becoming available. The ImageNet dataset (www.imagenet.org) is certainly the best example of this trend [Deng et al. 2009]. As a consequence, the problem is shifting from how to learn a category from a single image? [START_REF] Fei-Fei | [END_REF] to "how to handle these large quantities of data?" [START_REF] Wang | [END_REF], Maji & Berg 2009, Li et al. 2009].

As explained in chapter 2, one of the leading approaches to image categorization has been to describe images with bag-of-visual-words (BOV) histograms and to classify them using Support Vector Machines (SVM) classiers (see [START_REF] Csurka | [END_REF], Zhang et al. 2007, Vedaldi et al. 2009] for a few examples). While non-linear SVMs are perfectly suited to the small datasets which are typically employed, they do not scale well with the number N of training samples: between O(N 2 ) and O(N 3 ) . This is to be contrasted with linear SVMs which can be learned in O(N ) using, for instance, a cutting-plane algorithm [Joachims 2006] or Stochastic Gradient Descent (SGD) [START_REF] Shalev-Shwartz | [END_REF]. It is even shown in [Shalev-Shwartz & Srebro 2008] that, to achieve a target loss, the runtime of the SGD solver PEGASOS [START_REF] Shalev-Shwartz | [END_REF] decreases with the training set size (see also section 2 of [Shalev-Shwartz & Srebro 2008] for additional background on the cost of training non-linear and linear SVMs). This is a very compelling argument for using linear SVMs. Yet, it has been repeatedly reported that non-linear SVMs outperform linear SVMs for image categorization (see e.g. [START_REF] Maji | [END_REF], Wang et al. 2009, Maji & Berg 2009, Vedaldi et al. 2009]).

However, non-linear kernel classiers are linear-classiers. Indeed, if K is a positive semi-denite (psd) kernel, there exists an implicit mapping ϕ in a new (possibly innite-dimensional) space such that K(x, z) = ϕ(x) ϕ(z). Let X = {x i , i = 1...N } denote the set of training samples. The kernel classier f (z) = N i=1 a i K(z, x i ) + b can be re-written as f (z) = N i=1 α i ϕ(x i ) ϕ(z) + b which is a linear classier in the new space. Since we know that there exist linear classiers which perform well in this new space, it is extremely tempting to perform an explicit (possibly approximate) mapping of the data and learn linear classiers directly in this new space.

In previous chapters, we introduced novel image representations and similarity measures between such representations. In this chapter, our goal is somewhat dierent, yet related. Given an image representation (the BOV) and a kernel, the question is how to transform the representation such that the dot product in the new space is equivalent to the kernel similarity in the original space. Several approaches have been proposed along this line. Kernel Principal Component Analysis (kPCA) [START_REF] Schölkopf | [END_REF]], which was successfully applied in [START_REF] Williams | [END_REF], can be employed with any kernel. [START_REF] Rahimi | [END_REF] proposed an embedding based on random projections (RPs) for shift-invariant kernels. Recently, [Maji & Berg 2009] proposed an embedding for the intersection kernel. We note that the accuracy of an embedding approach depends directly on the accuracy of the kernel which is approximated: good kernels lead to good embeddings as veried in our experiments.

In this chapter we explore several approaches to performing explicit embedding on various kernels. More precisely, our contributions are the following ones:

• We show that square-rooting BOV vectors, which corresponds to an exact mapping in the case of the Bhattacharyya kernel, already leads to large improvements.

• To go beyond this simple strategy, we propose addkPCA: a novel kPCA-based embedding for additive kernels. We demonstrate that it leads to additional improvements at a very aordable cost.

• We go one step further and experiment with embedding for non-additive kernels. We show that the fairly small gain in classication accuracy over additive kernels is obtained at the expense of a very signicant increase of the computational cost.

• Using ImageNet data, we show experimentally that we continuously improve the classication accuracy using up to 10,000 training images per class. This clearly justies the use of very large training sets.

The remainder of this chapter is organized as follows. In section 7.2, we discuss the choice of kernels for BOV histograms (i.e. multinomials). In section 7.3, we briey review kP CA. In section 7.4, we show how to adapt this framework to additive kernels. In section 7.5, we review embedding with RPs for shift-invariant kernels. In section 7.6.2, we present experimental results on datasets: PASCAL VOC2007 and ImageNet. We also give a very brief introduction to the SGD solver we use in our experiments in Appendix A.1. The remainder of the relevant literature will be reviewed throughout the chapter1 .

Kernels for BOV Histograms

Additive Kernels

Additive kernels can be written as K(x, z) = D d=1 k(x(d), z(d)) where x(d) denotes the d-th dimension of vector x. They have gained considerable popularity since [START_REF] Maji | [END_REF] showed that the classication of a sample by an additive kernel SVM can be done approximately at a cost which is independent of the number of support vectors. This is because the classication function f

(z) = N i=1 a i K(z, x i )+ b can be rewritten as f (z) = D d=1 f d (z(d))+b with f d (z(d)) = N i=1 a i k(z(d), x i (d))
and each of the 1-D f d functions can be approximated by piecewise-constant orlinear functions. The most popular additive kernels are the Bhattacharyya kernel, the χ 2 kernel and the intersection kernel (c.f. equations 2.10, 2.11 and 2.12).

While the Bhattacharyya kernel has been successfully applied to continuous distributions [START_REF] Jebara | [END_REF], Farquhar et al. 2005] in our experience, it remains under-exploited in the case of BOV histograms. K bha can be directly related to K chi2 . Indeed, we have the following bounds (c.f. Appendix A.2):

K chi2 (x, z) ≤ K bha (x, z) ≤ 1 2 (1 + K chi2 (x, z)) (7.1)
and if x ≈ z, K bha (x, z) ≈ 1 2 (1+K chi2 (x, z)). Now, going back to our data embedding problem, we see that in the case of K bha the mapping is trivial: ϕ(z) = √ z (where 7.4 Embedding for Additive Kernels: addkPCA While kPCA can be applied as is to additive kernels, it does not exploit their additive structure. We now propose addkPCA: an ecient kPCA embedding for additive kernels. Although the function k is the same for all dimensions, we learn dierent embedding functions ϕ d,e in each dimension because the distribution of samples is dierent in each dimension. Also, a variable number of functions ϕ d,e is selected automatically by the algorithm in each dimension d (c.f. step 2)). This enables to put more emphasis on those dimensions which contain more energy.

The cost of computing the D kernel matrices is in O(M 2 D) and the cost of the D eigenvector decompositions is in O(M 3 D). The crucial dierence between kPCA and addkPCA is that, in the rst case, one approximates a kernel K : R D ×R D → R while, in the second case, one approximates D times a kernel k : R × R → R. Since K operates in a much higher dimensional space than k, the number M of vectors necessary to learn a good approximation of K is typically much larger than for k.

In our experiments, we found that M = 128 was sucient to learn addkPCA as opposed to several thousands for kPCA. Learning addkPCA on BOV histograms of dimensionality D = 4, 000 with M = 128 takes less than 30s on a single CPU of a 3GHz Xeon machine.

We show in Figure 7.1 the rst eigenfunctions in the case of K chi2 . An important question is: how many dimensions E will typically be needed to obtain a good embedding? We show that K chi2 can already be correctly approximated using a single eigenfunction. We will show in section 7.6.2 that with E = 2D (i.e. by doubling the dimensionality of our representations) we can do as well as additive kernel SVMs. v). Using a single eigenfunction already leads to a very good approximation of k. Bottom: the rst 3 eigenfunctions of k. For this example, we learned the embedding using samples regularly spaced on the [0,1] interval. Notice that ϕ 1 (u) ≈ √ u.

Embedding a new sample

We can embed a sample using the Nyström approximation: However, we can make the embedding cost independent of M using the same trick as [START_REF] Maji | [END_REF] As already mentioned, to obtain top accuracy with our approach, we typically set E = 2D which may lead to think that the second option is cheaper. Actually, this is incorrect as the O() notation hides constants. For the rst option, the computation of f c (z) relies on dot-products which are very ecient operations while for the second option it relies on look-up table accesses which are much slower2 . In practice, using a C++ implementation and setting E = 2D, we found that a standard dotproduct was approximately 5 times faster than look-up tables. Using the SSE23 implementation of the dot-product of [Bottou ], the speed-up was a factor of 15. Note that SSE2 instructions cannot speed-up look-up table accesses.

Chapter 7. Explicit Data Embedding for Large-Scale Learning

To learn the linear SVM for class c we use an SGD solver (c.f. Appendix A.1). At each iteration, the value f c (x i ) is evaluated with a dierent training sample x i (c.f. the term δ i in equation A.4). To train our linear classiers, we also prefer the direct approach to computing f c (x i ) (embedding + dot-product) over the approach based on look-up tables. This is much more ecient when the same sample is used multiples times by the SGD solver (5 times on average in our experiments).

Related Work

Closest to our approach is [Maji & Berg 2009] which proposes an explicit embedding for the intersection kernel. Each dimension of the BOV vector is embedded into a B-dimensional space. Per dimension, only 2 values are non-zero. This leads to a BD-dimensional embedding with 2D non-zero values. As is the case of [Maji & Berg 2009], addkPCA is as accurate as the additive kernel SVM it approximates. The main advantages of the proposed approach with respect to [Maji & Berg 2009] are the following ones:

• Our approach preserves data sparsity. Let z be a D-dimensional vector and let nz be the proportion of non-zero values in z. According to equation 7.6, if z(d) = 0, then k(z(d), .) is the null vector (at least in the case of K int , K chi2 or K bha ) and ϕ d,e (z(d)) = 0. Hence, the proportion of non-zero values in ϕ(z) is approximately nz (this is only approximate because we keep a variable number of eigenvectors per dimension). This is to be contrasted with [Maji & Berg 2009] where 2D values are non-zero (independently of nz). This can be a limitation for very sparse data. For instance, in the case of object segmentation with a sliding window classier, the classier typically has to consider many small windows described by very sparse histograms (each window containing a few patches).

• The training cost of [Maji & Berg 2009] is in O(N BD) with B ranging from 30 to 100. Our training cost is in O(ED) with E = 2D typically.

• [Maji & Berg 2009] reports that their work makes training and testing an additive classier only a small (constant factor) slower than training a linear classier. The classication as well as the SGD training in [Maji & Berg 2009] are based on look-up table accesses while our approach is based on dot-products. We explained in the previous subsection that the second type of operation is much more ecient: up to 15 times faster (hardly a small constant) with a good implementation of a dot-product.

[ [START_REF] Wang | [END_REF], which proposes an algorithm to learn intersection kernel SVMs, is closely related to [Maji & Berg 2009] and to addkPCA. The advantages of our approach with respect to [START_REF] Wang | [END_REF] are the same as the advantages with respect to [Maji & Berg 2009]: we preserve sparsity and classication as well as training are more ecient. We provide a brief introduction to embedding with random projections (RPs) for shift-invariant kernels. For more details, please refer to [START_REF] Rahimi | [END_REF].

Let K : R D × R D → R be a kernel. It is shift-invariant if it can be written under the form K(x, z) = K(x -z). For instance K int is shift-invariant since K int (x, z) = 1 -1 2 |x -z| where |.| is the L1 norm. Consequently K exp int is also shift-invariant. Similarly, K exp bha (x, z) can be rewritten as an rbf kernel:

K exp bha (x, z) = K rbf ( √ x- √ z). Therefore, K exp
bha is shift-invariant in the space of the square-rooted BOV vectors. In our experiments, we will focus on K exp bha . K(x-z) is psd if and only if it is the Fourier transform of a non-negative measure p (Bochner's theorem). If K is properly scaled, p is a probability distribution. For instance if K is the rbf kernel, then p is the Gaussian distribution. We have:

K(x -z) = ω∈R D p(ω)e jω (x-z) dω (7.7)
As K and p are real, we can replace e jω (x-z) by cos(ω (x -z)). Introducing the 2D vector ζ ω (x) = [cos(ω x) sin(ω x)], we have:

K(x -z) = E ω ζ ω (x) ζ ω (z) (7.8)
In practice, to compute an embedding ϕ : R D → R E , one draws a set of E/2 iid Gaussian vectors ω 1 , . . . , ω E/2 ∈ R D and the mapping is ϕ

(x) = 1 √ D [cos(ω 1 x), . . . , cos(ω E/2 x), sin(ω 1 x), . . . , sin(ω E/2 x)]. As E → ∞, ϕ(x) ϕ(z) → K(x -z).
We highlight that this approach does not require any learning. The cost of embedding a vector is in O(DE).

Experiments

We follow the same experimental setup as in section 4.3.1 but with SIFT features only. We did not make use of color features in our experiments. This is because some of our large scale experiments were already time-consuming and running experiments with color features would have doubled the runtime. We train visual codebooks of 4,000 visual words. An image is described by the L1-normalized histogram of visual-word occurrences (D = 4, 000). To learn linear SVMs, we use the SGD code available at [Bottou ] (c.f. Appendix A.1). To learn non-linear SVMs, we use libsvm [START_REF] Chang | [END_REF].

Small-Scale Experiments

For the small-scale experiments, we focus on accuracy, not on the training time. Indeed, training non-linear SVMs on small datasets is not an issue. Our goal is to verify to which extent the 3 approaches to explicit data embedding can approximate the non-linear kernel classiers.

Chapter 7. Explicit Data Embedding for Large-Scale Learning Linear SVM [Bottou ] 44.1

Non-Linear SVM [START_REF] Chang | [END_REF] Additive kernels Exponential kernels Datasets: We experimented with PASCAL VOC2007 [START_REF] Everingham | [END_REF]].

K bha K chi2 K int K exp bha K exp chi2 K exp
Classication accuracy is measured using Average Precision (AP). We report the average over the 20 classes. To tune the SVM regularization parameters, we trained them on the train set and used the val set for validation.

Baseline. We report baseline linear and non-linear SVM results in Table 7.1 for VOC2007. As expected non-linear SVMs perform signicantly better than linear ones, and exponential kernels somewhat better than their additive counterparts. All additive kernels perform similarly and the same can be said about exponential kernels.

Embedding additive kernels. We start with linear classiers on square-rooted BOV vectors (exact embedding for K bha ). We obtain a 49.0% AP on VOC2007. Compared to the linear baseline, this corresponds to absolute increases of 4.9%.

We now turn to addkPCA. We used a subset of M = 128 samples to learn the embedding. We repeated the experiments 10 times with dierent subsets to learn the embedding and we report the average for K chi2 in Table 7.2. With E = D = 4k, we get results which are slightly better than the simple square-rooting approach. With E = 2D = 8k, we get results as good as those obtained with the best additive kernels.

Embedding exponential kernels. We focus on K exp bha since (i) it gives the best (or very close to the best) results and (ii) it is based on the dot-product between square-rooted vectors which is very fast to compute. We report experiments with kPCA and RPs.

For kPCA, we repeated the experiments 10 times using dierent subsets of the training data to learn the embedding. We report the accuracy in Table 7.3. On both datasets, kPCA does its best job when all samples are used to learn the embedding. This not surprising given the high-dimensionality of the data and the small training set sizes. Accuracy (and standard deviation) of the approach of [START_REF] Rahimi | [END_REF] applied to K exp bha . E is the dimensionality of the embedded vectors.

For RPs, we also repeated each experiment 10 times with dierent random matrices. Results are reported in Table 7.4 for various values E of the embedding dimensionality. On the challenging VOC2007 dataset, even with E = 5D = 20k, we do not reach the accuracy of the baseline K exp bha .

7.6. (9,702), sofa (7,474), train (9,982) and tvmonitor (1,202).

To avoid the bias which typically occurs when training classiers and evaluating their accuracy on the same dataset, we used as test data the VOC2007 test set. Training and testing on datasets collected separately reduces over-tting eects and oers a much more realistic (and interesting) challenge. As is the case of VOC2007, we use AP (averaged over the 18 classes) to measure classication accuracy.

Each experiment was repeated 5 times on 5 dierent training subsets (later referred to as folds) and we report the average value as well as the standard deviation. For the 3 embedding techniques, we used on the top plot the best system, i.e. the one with the highest value E on the bottom plot (and therefore the highest training cost) .

To tune the SVM regularization parameters, we trained the classiers on 50% of the training data of the rst fold and used the second 50% of this fold as validation set. The same parameters were used for the 5 folds. Does more data help? We rst evaluate the inuence of the training set size on the classication accuracy. This is an important question that remains largely unexplored. For example, [START_REF] Wang | [END_REF], Maji & Berg 2009, Li et al. 2009] report experiments on large training sets but do not quantify the benet of using the full training set as opposed to only a fraction. Results are reported in Figure 7.2 (top). As a comparison, the smallest training set (250 images per class = 4.5k images in total) is comparable in size to the train+val set of VOC2007. We do not report results with libsvm beyond 42k training images as training the 18 categories on 42k images already takes approx. 38h of CPU time per fold. We observe a continuous improvement of the AP up to 10k images per class (140k images in total). This clearly justies the use of very large training sets.

On the 140k image training sets, square-rooting BOV vectors already leads to a large improvement: +5.4% AP (39.8% vs 45.2%). Using addkPCA leads to an additional 1.6% increase (46.8%). Finally, the largest increase we obtained with exponential kernels was another 1.4% (48.2%).

Training cost. We report in Figure 7. Memory requirements should also be taken into account. For instance, with RPs, one has to set E = 10D to obtain a mere 1% AP improvement over the best addkPCA results and the 140k image signatures already take approx. 20GB. We did not experiment with E = 20D for instance, as the training data would not have tted in the RAM of our 32GB machine. An important conclusion is that RPs for shift-invariant kernels seem better suited to problems where the input vectors are small dimensional as is the case of the datasets employed in [START_REF] Rahimi | [END_REF] (127 dimensions max.).

Testing cost. We report the testing time of the systems trained on the 140k images. As a comparison, the extraction of the BOV histograms from the 4,952 test images takes approx. 8 min. The baseline linear SVM and the linear SVM on the square-rooted vectors classify the whole test set in approx. 0.45s. addkPCA with E = 2D takes approx. 2s using explicit embedding (1.4s) + dot products (0.65s). If we were to use look-up tables instead (c.f. section 7.4.3) the test time would be approx. 10s. The benet of dot-products as opposed to look-up tables increases with the number of categories (i.e. when the embedding cost becomes negligible with respect to dot-products). kPCA with E = 3D takes approx. 22 min and RPs with E = 10D approx. 10 min. For both kPCA and RPs, the classication time is Chapter 7. Explicit Data Embedding for Large-Scale Learning fully dominated by the embedding cost.

Conclusion

In this chapter, we considered the problem of learning image classiers with large training sets. We explored explicit embedding as an approach to scale non-linear SVMs and experimented with several techniques. We demonstrated that simply square-rooting BOV vectors, which corresponds to an exact embedding for K bha , already leads to large improvements. We then proposed addkPCA: a simple and ecient embedding based on kPCA for additive kernels. We showed that it improved over the square-rooting at a very aordable cost. Finally, we experimented with kPCA and random projections to approximate exponential kernels and showed that it led to additional improvements but at a much higher cost this time.

This study focused on large training sets but did not address the problem of dealing with a large number of categories (e.g. thousands) which is a very challenging problem on its own. While we focused on the BOV, extensions to more complex representations would also be interesting such as the GMM-based representations introduced in the previous chapters.

Summary

This thesis addressed the problem of deriving novel image representations and computing similarities between such representations with application to image classication. The major contributions of this thesis are the following ones.

• In chapter 4 we presented a novel approach to compute the similarity between two unordered vector sets. We characterized each bag-of-patch model with a continuous GMM which was adapted from a common universal GMM using MAP. This adaptation provides a more accurate estimation than MLE when the number of features is small and allows a one-to-one correspondence between the Gaussians of image GMMs for fast scoring. We derived ecient approximations for two probabilistic kernels: the Probability Product Kernel and the Kullback-Leibler Kernel. We applied this approach to image classication and showed its eciency in terms of classication accuracy and cost.

• In chapter 5 a novel image representation was introduced. It consists in approximating an image, modeled for instance by a GMM, as a convex combination of K reference image GMMs and then characterizing the image as a K-dimensional vector of mixture weights. We proposed two approximate optimization algorithms for the computation of the mixture weights: one based on sampling and one based on variational bounds. This approach was applied to image classication and it was shown to outperform the GMM approach introduced in chapter 4.

• In chapter 6 we also introduced a novel family of contextual measures of similarity between distributions. The idea was to measure the similarity between two distributions p and q in the context of a third distribution u. We showed that for two important families of divergences (Bregman and Csiszár) the contextual similarity computation is a convex optimization problem. We focused on the case of continuous distributions, typically GMMs, and applied this similarity to the problem of kernel-based image classication. With respect to the Chapter 8. Conclusion approach of chapter 5, we did not observe a signicant increase of accuracy. However, an advantage of this contextual similarity is that the context does not depend explicitly on a set of reference images.

• Finally, in chapter 7 we explored explicit embedding as an approach to scale non-linear SVMs on BOV representations. We experimented with two state-ofthe-art techniques to embedding: kernel PCA (kPCA) and random projection for shift-invariant kernels. We also proposed a simple and ecient embedding based on kPCA for additive kernels, addkPCA. We observed that a simple square-rooting of BOV vectors (which corresponds to an exact embedding in the case of the Bhattacharyya kernel) already led to signicant improvements. We also showed that additional improvements could be gained with addkPCA at a very aordable cost. Finally, we observed that, while it is possible to improve over additive kernels, the gain in classication accuracy was obtained at a very high computational cost.

Future work

We have tried to outline some future work at the end of chapters 4, 6 and 7. We now summarize them here:

• Adaptation Techniques. The proposed MAP adaptation provides accurate estimation and improves the performance. We believe that other adaptation techniques could also be employed, such as Maximum Likelihood Linear Regression (MLLR) [START_REF] Leggetter | Maximum likelihood linear regression for speaker adaptation of continuous density hidden Markov models[END_REF], Gales 1998], Cluster Adaptive Training (CAT) [Gales 2000] or Eigenvoices [Kuhn et al. 2000]. They have been shown to yield signicantly better results than MAP in the speech recognition literature for smaller adaptation set.

• Multiple Kernel Learning. From the experimental results with PPK and KLK, we note that there is no clear winner between these two kernels. It might be interesting to consider principled combinations of kernels using Multiple Kernel Learning (MKL) [START_REF] Varma | [END_REF] to avoid the per-dataset selection of kernels.

• Clustering based on Contextual Similarity. Clustering consists in grouping "similar" images where the notion of similarity depends on the other images contained in the dataset. For instance, while it might make sense to group images of dierent breeds of cats in a general dataset of animal images, it might not in a dataset of cat images. Hence, we believe that clustering is a problem that could benet greatly from the proposed family of contextual measures of similarity.

• Extension of Explicit Data Embedding. In this thesis we have shown that GMM-based representation obtain signicantly improvements over the BOV. We believe that it would be interesting to extend explicit embedding methods to these more complex GMM-based representations.

Figure 1 . 1 :

 11 Figure 1.1: Sample images for the category "cat" from the PASCAL VOC2007 Dataset.

  Figure 3.1: Sample images from the PASCAL VOC2007 database for all 20 categories.

Chapter 4 .

 4 Images as Adapted Mixtures of Gaussians

Figure 4 . 1 :

 41 Figure 4.1: Performance on the PASCAL VOC2007 database of the PPK (top) and KLK (bottom) for a varying number of Gaussian components. The mean AP is shown for system based on ORH+COL features.

Figure 4 . 2 :

 42 Figure 4.2: The mean AP based on ORH+COL features with KLK on the VOC2007 database as a function of parameter τ . We used GMMs with 16 Gaussians for this experiment.

Figure 4

 4 Figure 4.3: Image examples of the best and the worst Scene-15 classes. On the left the three classes with the best classication rates and on the right those with the lowest rates.

Figure 4 .Figure 4 . 4 :Figure 4 . 5 :

 44445 Figure 4.4: Classication rate (%) on Caltech-256 database with 128 Gaussian components by varying the number of training images.

Figure 5 . 1 :

 51 Figure 5.1: Comparison of dierent representations on the semantic axis.

  Figure 5.2: The SKL between q (black straight line) and p 1 or p 2 (green and blue dashed lines respectively) is approximately the same as the SKL between q and p 3 (dotted red line).

Figure 5

 5 Figure 5.3: Mean AP for the sampling and lower-bound approximations of MOM KL for the system based on ORH features only.

Figure 5 . 4 :

 54 Figure 5.4: Inuence of the number of EM iterations on the mean AP for MOM KL lower-bound for dierent numbers of Gaussian components (system based on ORH features only).

Figure 5 . 5 :Figure 5 . 6 :

 5556 Figure 5.5: Comparison of the proposed algorithms to traditional kernel methods: MOM PPK versus PPK (top) and MOM KL versus KLK (bottom). The mean AP is shown as a function of the number of Gaussian components in the per-image GMMs for the dierent features (ORH, COL, ORH+COL).

Figure 5 . 7 :

 57 Figure 5.7: Classication rate (%) on Caltech-256 database of the MOM PPK (top) and MOM KL (bottom) with 128 Gaussian components with dierent number of training images.

Figure 6 . 1 :

 61 Figure 6.1: The mean AP on the PASCAL VOC2007 of the CTXT KL based on the ORH+COL features for a varying number of Gaussian components.

Figure 6 . 2 :

 62 Figure 6.2: Classication rate (%) on Scene-15 database by varying the number of Gaussian components.

Figure 6

 6 Figure 6.3: Classication rate (%) on Caltech-256 database with 128 Gaussian components by varying the number of training images.

7. 4 . 1

 41 Learning the EmbeddingAs noted in[Maji & Berg 2009], a possible way to nd an embedding ϕ for additive kernels is to nd separate embeddings ϕ d for each dimension d and then to concatenate them. Therefore, we propose to apply the kPCA framework separately in each dimension. Given an additive kernelK(x, z) = D d=1 k(x(d), z(d))and a set of samples {x i , i = 1 . . . M }, the embedding is learned as follows:1) For each dimension d:a) Compute the M × M kernel matrix k d with entries k(x i (d), x j (d)) b) Compute the F largest eigenvalues σ 2 d,1 , . . . , σ 2 d,F of k d (e.g. F = 10) and their associated eigenvectors ψ d,1 , . . . , ψ d,F . 2) Sort the D × F eigenvalues σ 2 d,e for d = 1 . . . D and e = 1 . . . F and keep the E largest ones with their associated eigenvectors.

Figure 7 . 1 :

 71 Figure 7.1: Top-left: the function k(u, v) = 2 uvu+v which corresponds to K chi2 . Topright: its approximation ϕ 1 (u) ϕ 1 (v). Using a single eigenfunction already leads to a very good approximation of k. Bottom: the rst 3 eigenfunctions of k. For this example, we learned the embedding using samples regularly spaced on the [0,1] interval. Notice that ϕ 1 (u) ≈ √ u.

  z(d), .) = [k(z(d), x 1 (d)), . . . , k(z(d), x M (d))]. In this case, the embedding cost is in O(M (D + E)).

  ]. We split each of the D dimensions into a set of B bins (by regularly sampling the interval between the smallest and largest values). Let c d,b be the center of the b-th bin in dimension d. We pre-compute the values ϕ d,e (c d,b ) for the E dimensions of the embedding using Nyström. Given a new sample z, we compute for each dimension the bin index (O(D)) and then use a piecewise-constant or -linear approximation of ϕ d,e (O(E)).

  7.4.3 Classication of a sampleWe assume that we have learned a set of C linear classiers on the embedded samples:f c (z) = w c ϕ(z) + b c . We can compute f c (ϕ(z))in two dierent ways: 1. The simplest way is to perform the explicit embedding ϕ(z) (O(D + E)) and then to do C dot-products (O(CE)). 2. Using again the trick of [Maji et al. 2008], we can rewrite the classiers f c as non-linear classiers in the original space. f c (z) = D d=1 f c,d (z(d))+b where each 1D function f c,d can be approximated by binning the d-th dimension and then by using a piecewise-constant or -linear approximation. The cost of computing the bin indices in each dimension is in O(D) and the cost of the C classications is in O(CD).

  2 (bottom) the accuracy as a function of the training time on the 140k training sets. The training time includes the combined time of learning the embedding, embedding the training vectors and training the 18 classiers. All the CPU times correspond to training on a single fold and were measured on a 3GHz Xeon machine using a single CPU. As a comparison, it takes less than 4h to compute SIFT features and extract BOV histograms from 140k images (approx. 100ms per image). While kPCA or RPs can outperform addkPCA, the benet comes at a high cost: several hours of training as opposed to 2 min. Note that the cost of kPCA and RPs is largely dominated by the embedding, not by the linear SVM training.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

  Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problems and Contributions . . . . . . . . . . . . . . . . . . . 2 1.2.1 Modeling Image as Adapted Gaussian Mixture Model . . . . 2 1.2.2 Modeling Images as Mixtures of Reference Images . . . . . . 3 1.2.3 Contextual Similarity based on MOM . . . . . . . . . . . . . 4 1.2.4 Explicit Data Embedding for Large-Scale Learning . . . . . .

	Introduction
	Contents
	1.1

4 1.3 Outline of thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1 Context

  Patch Detection and Extraction . . . . . . . . . . . . . . . . . 7 2.2 Measuring the Similarity between Bags-of-Patches . . . . . 8 2.2.1 Model-Free Approaches . . . . . . . . . . . . . . . . . . . . .

	Chapter 2
	Literature Review
	Contents
	2.1

8 2.2.2 Model-Based Approaches: Discrete Distributions . . . . . . . 10 2.2.3 Model-Based Approaches: Continuous Distributions . . . . . 12 2.3 Kernel-Based Learning . . . . . . . . . . . . . . . . . . . . . . 13

Table 7 .

 7 2: Accuracy (and standard deviation) of the proposed addkPCA applied to K chi2 . E is the dimensionality of the embedded vectors.

	int

Table 7 .

 7 3: kPCA accuracy (and standard deviation) with K exp bha . E is the number of training samples used to learn the embedding and therefore the dimensionality of the embedded vectors. Full corresponds to using all training samples to learn the embedding (5,011 for VOC2007).

	E =	256	512 1024 2048 Full
		PASCAL VOC2007
	AP	45.6 47.9 49.8 51.2 52.4
	(in %) (0.3) (0.4) (0.2) (0.2) (0.0)
	E =	4k	8k	12k	16k	20k
		PASCAL VOC2007
	AP	46.7 49.0 50.0 50.7 51.0
	(in %) (0.5) (0.3) (0.2) (0.2) (0.2)

Table 7 . 4 :

 74

  2 Large-Scale ExperimentsWe now evaluate how the various embedding techniques scale to large training sets. To train classiers, we used a subset of ImageNet[Deng et al. 2009]. Our goal was to create a training set with the same 20 classes as PASCAL VOC2007. At the time when we downloaded the data, only 18 classes had at least one synset in ImageNet: aeroplane, bicycle, bird, boat, bottle, bus, car, cat, chair, cow, diningtable, dog, horse, motorbike, sheep, sofa, train and tvmonitor. We downloaded images from these 18 categories as well as their sub-categories (i.e. children synsets). In our experiments, we trained classiers with up to 10k images per class.

	Half of the
	classes have less than 10k images: bicycle (6,653 images), bus (5,224), cow (1,572),
	dining table (4,061), motorbike (3,779), sheep

  Chapter 7. Explicit Data Embedding for Large-Scale Learning Top: classication accuracy as a function of the number of training images. Bottom: classication accuracy as a function of the training time (i.e. for various sizes E of the embedding space) using a training set of 140k images. lin SVM = linear SVM baseline. sqrt + lin SVM = linear SVM on square-rooted vectors. add kPCA + lin SVM = proposed addkPCA for K chi2 . rand + lin SVM = random projections to approximate K exp bha . kPCA + lin SVM = standard kPCA with K exp bha . sqrt + rbf SVM = baseline kernel SVM with K exp bha .

	AP (in %)
					sqrt + rbf SVM
					kPCA + lin SVM
					rand + lin SVM
					add kPCA + lin SVM
					sqrt + lin SVM
					lin SVM
	0.25k (4.5k)	0.5k (9k)	1k (18k)	2.5k (42k)	5k (80k)	10k (140k)
	Max number of training images per class (total number of training images)
						E=10D	E=3D
					E=D	E=2D
			E=3D			E=5D
		E=D E=2D	E=D/2	E=3D
	AP (in %)		E=D/4	E=2D
		kPCA + lin SVM
		rand + lin SVM add kPCA + lin SVM	E=D
		sqrt + lin SVM
		lin SVM
	10s	1min	10min		1h	6h	1day
			Training time
	Figure 7.2:

Mechanical Turk (AMT:www.mturk.com). The database is publicly available at http://www.image-net.org.

We became aware of[Hershey & Olsen

2008] more than a year after this work was done. However, we do not believe that 4.12 would lead to signicantly better results than 4.11.

Similarly, we became aware of[Hershey & Olsen 2007] more than a year after this work was done. Again, we do not believe that the variational approximation would lead to signicantly better results.

While in the previous chapters we used SLR for linear classication, we switched to linear SVMs in this chapter. This is because our SLR code did not scale to the large amounts of images employed in section 7.6.2 (up to 140k) as opposed to the SGD code of[Bottou ] which dealt easily with such large quantities of data.

On modern processors, the main bottleneck is often not the execution of the instructions but the access to the data. To reduce the access time, processors perform prefetching, i.e. when accessing the data at a given position in RAM, they also retrieve the data at subsequent positions. Prefetching results in a very signicant speed-up provided that data is accessed sequentially. This is the case when performing dot-products and this is generally not the case when accessing look-up tables.

Modern processors, support single instruction with multiple data (SIMD) commands. SSE2 instructions perform multiple simple operations, such as additions or multiplications, in parallel.

• More generally, we believe that the ability to scale on algorithms to a large number of classes is necessarily to make image classication useful for real world applications. Doing so eciently requires the ability to deal with class hierarchies, a problem we did not address in this thesis.

Introduction

In the previous chapter, we modeled images as mixtures of reference images. We explained that each mixture weight expressed a similarity between the image to be described and each reference image. We can say that this measure of similarity is contextual as it depends on the set of reference images: the context. However, nding the similarity between two images using such an explicit set of context images is both costly and cumbersome. We note that several authors have already proposed contextual measures of similarity. [Jégou et al. 2007] proposes a contextual measure of distance between points which consists in symmetrizing the K-NN relationship. The initial distance is contextualized by adding a multiplicative penalty term which can be computed iteratively. In eect, it downweights those images which are located in a dense region of the image space. [Zhao et al. 2007] proposes a contextual distance between data points which is dened as the dierence of their contributions to the integrity Chapter 7. Explicit Data Embedding for Large-Scale Learning the square-root of a vector should be understood as a term-by-term operation). Hence, in the case of K bha the mapping can be done exactly at (almost) zero cost, simply by square-rooting the BOV vectors.

Exponential Kernels

All the previous additive kernels can be exponentiated and their exponential versions are also guaranteed to be psd kernels (c.f. equations 2.13, 2.14 and 2.15). Recently, [Vedaldi et al. 2009] reported on an object segmentation task that K exp chi2 outperformed K chi2 . In section 7.6.2, we systematically compare the accuracy of the additive kernels with their exponential counterparts and conrm the superiority of exponential kernels.

Embedding with Kernel PCA

We just provide a brief introduction to embedding with kPCA. For more background on kPCA, please refer to [START_REF] Schölkopf | [END_REF]]. Let {x i , i = 1 . . . M } be a set of samples in R D provided to learn the embedding. Given a kernel K : R D × R D → R, we seek a mapping ϕ : R D → R E such that K(x i , x j ) ≈ ϕ(x i ) ϕ(x j ), ∀(i, j). A possible criterion to nd an optimal ϕ is to minimize:

where ϕ e (x i ) denotes the e-th dimension of ϕ(x i ). The constraints (7.3) translate the fact that we want the dimensions of ϕ to be uncorrelated. Let K be the M × M kernel matrix and φ e = [ϕ e (x 1 ), . . . , ϕ e (x M )]. We write φ e = σ e ψ e where σ e is the L2 norm of φ e (and consequently ψ e is the L2-normalized version of φ e ). Taking the derivatives of the equation 7.2 with respect to the ϕ e (x i )'s leads to:

e ψ e for e = 1 . . . E. (7.4) This is a standard eigenvalue problem. The solution to minimizing the equation 7.2 is to take the E eigenvectors ψ e corresponding to the E largest eigenvalues σ 2 e and to set ϕ e (x i ) = σ e ψ e (i).

We dene K(z, .) = [K(z, x 1 ), . . . , K(z, x M )]. To extend the mapping to a new sample z, we use the Nyström approximation [START_REF] Williams | [END_REF]: We give a brief overview of the SGD solver available at [Bottou ] inspired by [START_REF] Shalev-Shwartz | [END_REF]]. Given a training set of labeled samples {(x i , y i ), i = 1, . . . , N }, with y i ∈ {-1, +1}, we consider the problem of minimizing the regularized loss:

where λ is the regularization parameter. In the SVM case, λ(w x i , y i ) = max{0, 1y i w x i }. We did not include a bias term to simplify the presentation. Assuming that at iteration t the SGD algorithm considers only sample x i , the loss (A.1) is approximated by:

w is updated as follows: .4) with δ i = 1 if λ(w x i , y i ) > 0 and δ i = 0 otherwise. The learning rate has the form η t = 1 λ(t+t 0 ) where t 0 is set heuristically in [Bottou ].

A.2 Relationship between K chi2 and K bha Let x and z be two D-dimensional multinomials. Let us rst show that

We have: .6) which leads trivially to K bha (x, z) ≥ K chi2 (x, z).

Let us now show that:

We have:

Multiplying the previous expression by β we obtain:

Therefore, we have: .10) which leads trivially to 1 2 (1 + K chi2 (x, z)) ≥ K bha (x, z). We can actually show that 1 2 (1 + K chi2 (x, z)) is a rst-order Taylor expansion of K bha (x, z). Let m = (x + z)/2 and ε = x -z. Replacing m and ε by their denitions and reshuing the terms leads to: .16)