What Does Classifying More Than 10,000 Image
Categories Tell Us?
Jia Deng1,3 , Alexander C. Berg2 , Kai Li1 , and Li Fei-Fei3
1

Princeton University
Columbia University
3
Stanford University

2

Abstract. Image classiﬁcation is a critical task for both humans andcomputers. One of the challenges lies in the large scale of the semantic
space. In particular, humans can recognize tens of thousands of object
classes and scenes. No computer vision algorithm today has been tested
at this scale. This paper presents a study of large scale categorization
including a series of challenging experiments on classiﬁcation with morethan 10, 000 image classes. We ﬁnd that a) computational issues become crucial in algorithm design; b) conventional wisdom from a coupleof hundred image categories on relative performance of diﬀerent classiﬁers does not necessarily hold when the number of categories increases;c) there is a surprisingly strong relationship between the structure of
WordNet (developed for studying language) and the diﬃculty of visual
categorization; d) classiﬁcation can be improved by exploiting the semantic hierarchy. Toward the future goal of developing automatic visionalgorithms to recognize tens of thousands or even millions of image categories, we make a series of observations and arguments about dataset
scale, category density, and image hierarchy.

1

Introduction

Recognizing categories of objects and scenes is a fundamental human ability
and an important, yet elusive, goal for computer vision research. One of the
major challenges is the sheer scale of the problem, both in terms of the very
high dimensional physical space of images, and the large semantic space humans
use to describe visual stimuli. In particular, psychologists have postulated thathumans are able to categorize at least tens of thousands of objects and scenes [1].
The breadth of the semantic space has important implications. For many realworld vision applications, the ability to handle a large number of object classes
becomes a minimum requirement, e.g. an image search engine or an automatic
photo annotator is signiﬁcantly less useful if it is unable to cover a wide rangeof object classes. Even for tasks in restricted domains, e.g. car detection, to beeﬀective in the real world, an algorithm needs to discriminate against a large
number of distractor object categories.
Recent progress on image categorization has been impressive and has introduced a range of features, models, classiﬁers, and frameworks [2,3,4,5,6,7,8,9,10].
In this paper we explore scaling up the number of categories considered in recognition experiments from hundreds to over 10 thousand in order to move toward
K. Daniilidis, P. Maragos, N. Paragios (Eds.): ECCV 2010, Part V, LNCS 6315, pp. 71–84, 2010.
c Springer-Verlag Berlin Heidelberg 2010


72

J. Deng et al.

reducing the gap between machine performance and human abilities. Note that
this is not simply a matter of training more and more classiﬁers (although thatis a challenging task on its own). With such large numbers of categories there
is a concomitant shift in the diﬃculty of discriminating between them as thecategories sample the semantic space more densely. The previously unexplored
scale of the experiments in this paper allow this eﬀect to be measured.
Recognition encompasses a wide range of speciﬁc tasks, including classiﬁcation, detection, viewpoint understanding, segmentation, veriﬁcation and more.
In this paper we focus on category recognition, in particular the task of assigning a single category label to an image that contains one or more instances of acategory of object following the work of [11,12,13,14].
We conduct the ﬁrst empirical study of image categorization at near humanscale. Some results are intuitive – discriminating between thousands of categories
is in fact more diﬃcult that discriminating between hundreds – but other results
reveal structure in the diﬃculty of recognition that was previously unknown.
Our key contributions include:– The ﬁrst in-depth study of image classiﬁcation at such a large scale. Suchexperiments are technically challenging, and we present a series of techniques
to overcome the diﬃculty. (Sec. 5)– We show that conventional wisdom obtained from current datasets does notnecessarily hold in some cases at a larger scale. For example, the ordering
by performance of techniques on hundreds of categories is not preserved on
thousands of categories. Thus, we cannot solely rely on experiments on the
Caltech [13,14] and PASCAL [12] datasets to predict performance on large
classiﬁcation problems. (Sec. 6)– We propose a measure of similarity between categories based on WordNet[15]– a hierarchy of concepts developed for studying language. Experiments show
a surprisingly strong correlation between this purely linguistic metric and theperformance of visual classiﬁcation algorithms. We also show that the categories used in previous object recognition experiments are relatively sparse– distinguishing them from each other is signiﬁcantly less diﬃcult than distinguishing many other denser subsets of the 10,000 categories. (Sec. 7)– Object categories are naturally hierarchical. We propose and evaluate a technique to perform hierarchy aware classiﬁcation, and show that more informative classiﬁcation results can be obtained. (Sec. 8)2Related Work

Much recent work on image classiﬁcation has converged on bag of visual wordmodels (BoW) [16] based on quantized local descriptors [17,3,4] and support vector machines [3,2] as basic techniques. These are enhanced by multi-scale spatial
pyramids (SPM) [4] on BoW or histogram of oriented gradient (HOG) [18,4]
features. In the current state-of-the-art, multiple descriptors and kernels are
combined using either ad hoc or multiple kernel learning approaches [19,5,20,21].
Work in machine learning supports using winner-takes-all between 1-vs-allWhat Does Classifying More Than 10,000 Image Categories Tell Us?

73

classiﬁers for the ﬁnal multi-class classiﬁcation decision [22]. We choose SPM
using BoW because it is a key component of many of the best recognition results [19,5,20,21] and is relatively eﬃcient. Recent work allows fast approximation of the histogram intersection kernel SVM, used for SPM, by a linear SVM
on specially encoded SPM features [23]. See Appendix for the modiﬁcations necessary to allow even that very eﬃcient solution to scale to very large problems.
There are very few multi-class image datasets with many images for morethan 200 categories. One is Tiny Images [6], 32x32 pixel versions of images
collected by performing web queries for the nouns in the WordNet [15] hierarchy,
without veriﬁcation of content. The other is ImageNet [24], also collected fromweb searches for the nouns in WordNet, but containing full images veriﬁed byhuman labelers. To date there have been no recognition results on large numbersof categories published for either dataset1 . Fergus et al . explore semi-supervised
learning on 126 hand labeled Tiny Images categories [25] and Wang et al . showclassiﬁcation on a maximum of 315 categories (< 5%) [26].
Recent work considering hierarchies for image recognition or categorization[27,28,29,30] has shown impressive improvements in accuracy and eﬃciency, but
has not studied classiﬁcation minimizing hierarchical cost. Related to classiﬁcation is the problem of detection, often treated as repeated 1-vs-all classiﬁcationin sliding windows. In many cases such localization of objects might be usefulfor improving classiﬁcation, but even the most eﬃcient of the state of the art
techniques [7,20,31] take orders of magnitude more time per image than theones we consider in this study, and thus cannot be utilized given the scale of ourexperiments.

3

Datasets

The goals of this paper are to study categorization performance on a signiﬁcantly
larger number of categories than the current state of the art, and furthermore
to delve deeper toward understanding the factors that aﬀect performance. In
order to achieve this, a dataset with a large number of categories spanning awide range of concepts and containing many images is required. The recently
released ImageNet dataset consists of more than 10,000,000 images in over 10,000
categories organized by the WordNet hierarchy [24]. The size and breadth of
this data allow us to perform multiple longitudinal probes of the classiﬁcation
problem. Speciﬁcally we consider the following datasets:– ImageNet10K. 10184 categories from the Fall 2009 release of ImageNet [32],including both internal and leaf nodes with more than 200 images each (atotal of 9 million images).
– ImageNet7K. 7404 leaf categories from ImageNet10K. Internal nodes may
overlap with their descendants, so we also consider this leaf only subset.
– ImageNet1K. 1000 leaf categories randomly sampled from ImageNet7K.
1Previous work on Tiny Images [6] and ImageNet [24] shows only proof of concept
classiﬁcation on fewer than 50 categories.

74

J. Deng et al.

– Rand200{a,b,c}. Three datasets, each containing 200 randomly selectedleaf categories. The categories in Rand200a are sampled from ImageNet1K
while Rand200b and Rand200c are sampled directly from ImageNet7K.
– Ungulate183, Fungus134, Vehicle262. Three datasets containing all theleaf nodes that are descendants of particular parent nodes in ImageNet10K(named by the parent node and number of leaves).
– CalNet200. This dataset serves as a surrogate for the Caltech256 dataset –containing the 200 image categories from Caltech256 that exist in ImageNet.
Note that all datasets have non-overlapping categories except ImageNet10K.
Following the convention of the PASCAL VOC Challenge, each category is randomly split 50%-50% into a set of training and test images, with a total of 4.5
million images for training and 4.5 million images for testing. All results areaveraged over two runs by swapping training and test, except for ImageNet7K
and ImageNet10K due to extremely heavy computational cost. In all cases weprovide statistical estimates of the expected variation. The number of training
images per category ranges from 200 to 1500, with an average of 450.

4Procedure

The main thrust of this paper is image classiﬁcation: given an image and K
classes, the task is to select one class label. We employ two evaluation measures:
Mean accuracy. The accuracy of each class is the percentage of correct predictions, i.e. predictions identical to the ground truth class labels. The mean
accuracy is the average accuracy across all classes.
Mean misclassiﬁcation cost. To exploit the hierarchical organization of object
classes, we also consider the scenario where it is desirable to have non-uniform
misclassiﬁcation cost. For example, misclassifying “dog” as “cat” might not be
penalized as much as misclassifying “dog” as “microwave”. Speciﬁcally, for each(k)(k)
image xi ∈ X, i = 1, . . . , m from class k, we consider predictions f (xi ) : X →{1, . . . , K}, where K is the number of classes
m(e.g. K = 1000 for ImageNet1K)1, where C is a K × K
and evaluate the cost for class k as Lk = m
i=1 Cf (x(k)
i ),kcost matrix and Ci,j is the cost of classifying the true class j as class i. The
mean cost is the average cost across all classes. Evaluation using a cost based on
the ImageNet hierarchy is discussed in Sec. 8.
We use the following four algorithms in our evaluation experiments as samples
of some major techniques used in object recognition:– GIST+NN Represent each image by a single GIST [33] descriptor (a commonly accepted baseline descriptor for scene classiﬁcation) and classify using
k-nearest-neighbors (kNN) on L2 distance.
– BOW+NN Represent each image by a histogram of SIFT [17] codewords andclassify using kNN on L1 distance, as a baseline for BoW NN-based methods.
– BOW+SVM Represent each image by a histogram of SIFT codewords, and train
and classify using linear SVMs. Each SVM is trained to distinguish one classfrom the rest. Images are classiﬁed by the class with largest score (a 1-vs-all
framework). This serves as a baseline for classiﬁer-based algorithms.

What Does Classifying More Than 10,000 Image Categories Tell Us?

75– SPM+SVM Represent each image by a spatial pyramid of histograms of SIFT
codewords [4]. Again a 1-vs-all framework is used, but with approximate
histogram intersection kernel SVMs [23,3,4]. This represents a signiﬁcantcomponent of many state of the art classiﬁers [19,5,20,21].

5

Computation Matters

Working at the scale of 10,000 categories and 9 million images moves computational considerations to the forefront. Many common approaches becomecomputationally infeasible at such large scale.
As a reference, for this data it takes 1 hour on a 2.66GHz Intel Xeon CPU
to train one binary linear SVM on bag of visual words histograms (including
a minimum amount of parameter search using cross validation), using the extremely eﬃcient LIBLINEAR [34]. In order to perform multi-class classiﬁcation,
one common approach is 1-vs-all, which entails training 10,000 such classiﬁers –requiring more than 1 CPU year for training and 16 hours for testing. Anotherapproach is 1-vs-1, requiring 50 million pairwise classiﬁers. Training takes a similar amount of time, but testing takes about 8 years due to the huge number ofclassiﬁers. A third alternative is the “single machine” approach, e.g. Crammer &Singer [35], which is comparable in training time but is not readily parallelizable.
We choose 1-vs-all as it is the only aﬀordable option.
Training SPM+SVM is even more challenging. Directly running intersection kernel SVM is impractical because it is at least 100× slower ( 100+ years ) thanlinear SVM [23]. We use the approximate encoding proposed by Maji & Berg [23]that allows fast training with LIBLINEAR. This reduces the total training timeto 6 years. However, even this very eﬃcient approach must be modiﬁed because
memory becomes a bottleneck 2 – a direct application of the eﬃcient encoding of[23] requires 75GB memory, far exceeding our memory limit (16GB). We reduce
it to 12G through a combination of techniques detailed in Appendix A.
For NN based methods, we use brute force linear scan. It takes 1 year to run
through all testing examples for GIST or BOW features. It is possible to use
approximation techniques such as locality sensitive hashing [36], but due to thehigh feature dimensionality (e.g. 960 for GIST), we have found relatively small
speed-up. Thus we choose linear scan to avoid unnecessary approximation.
In practice, all algorithms are parallelized on a computer cluster of 66 multicore machines, but it still takes weeks for a single run of all our experiments. Our
experience demonstrates that computational issues need to be confronted at theoutset of algorithm design when we move toward large scale image classiﬁcation,otherwise even a baseline evaluation would be infeasible. Our experiments suggest that to tackle massive amount of data, distributed computing and eﬃcientlearning will need to be integrated into any vision algorithm or system geared
toward real-world large scale image classiﬁcation.
2

While it is possible to use online methods, e.g. stochastic subgradient descent, they
can be slower to converge [34].

76

J. Deng et al.
35

SPM+SVM
BOW+SVM
BOW+NN
GIST+NN30

Accuracy (%)

25
20
15
10
5
0

200

1000
7k10k
# of Categories ( log spacing )Fig. 1. Given a query image, the task of “image classiﬁcation” is to assign it to oneof the classes (represented by a stack of images) that the algorithm has learned. Left:
Most traditional vision algorithms have been tested on a small number of somewhat distinct categories. Middle: Real world image classiﬁcation problems may involve a muchlarger number of categories – so large that the categories can no longer be easily separated. Right: Mean classiﬁcation accuracy of various methods on Rand200{a, b, c},
ImageNet1K, ImageNet7K and ImageNet10K.

6Size Matters

We ﬁrst investigate the broad eﬀects on performance and computation of scaling
to ten-thousand categories. As the number of categories in a dataset increases,
the accuracy of classiﬁcation algorithms decreases, from a maximum of 34% for
Rand200{a,b,c} to 6.4% for ImageNet10K (Fig. 1 right). While the performancedrop comes at no surprise, the speed of decrease is slower than might be expected– roughly a 2× decrease in accuracy with 10× increase in the number of classes,
signiﬁcantly better than the 10× decrease of a random baseline.
There is a surprise from k-nearest-neighbor (kNN) classiﬁers, either using GIST
features or BoW features. For Rand200{a,b,c}, these techniques are signiﬁcantly
worse than linear classiﬁers using BoW features, around 10% lower in accuracy.
This is consistent with the experience of the ﬁeld – methods that do use kNN
must be augmented in order to provide competitive performance [2,37]. But the
picture is diﬀerent for ImageNet7K or ImageNet10K categories, where simple
kNN actually outperforms linear SVMs on BoW features (BOW+SVM), with 11-16%
higher accuracy. The small absolute gain in mean accuracy, around 0.5%, is madesigniﬁcant by the very small expected standard deviation of the means 0.1% 3 .
A technique that signiﬁcantly outperforms others on small datasets
may actually underperform them on large numbers of categories.
This apparent breakdown for 1-vs-all with linear classiﬁers comes despite aconsistent line of work promoting this general strategy for multi-class classiﬁcation [22]. It seems to reveal issues with calibration between classiﬁers, as the majority of categories have comparable discriminative power on ImageNet7K and
Rand200a (Fig 2 left), but multi-way classiﬁcation is quite poor for ImageNet7K
3

Stdev for ImageNet7K and ImageNet10K are estimated using the individual category
variances, but are very small cf standard error and the central limit theorem.

What Does Classifying More Than 10,000 Image Categories Tell Us?

77

Percentage

1

0.95

0.9

Percentage

SegwayUrsinia

0.85

Spirit stove
Fall webworm

0.8

Percentage

AUC on ImageNet7K

Angus

Water jug
0.75

TrivetMine detector

0.7
0.7

0.75

0.8

0.85

0.9

AUC on Rand200a

0.95

1

15

Rand200a

10
5
0
0
40

Bee orchid

20

40

60

ImageNet1K
20
0
0

Lobster pot

20

60

ImageNet7K

50
0
0

40

20

40
Accuracy (%)

Shaver60
MinivanFig. 2. Left: Scatter plot comparing the area under ROC curve (AUC) of BOW+SVM forthe 200 categories in Rand200a when trained and evaluated against themselves(x-axis)
and when trained and evaluated against ImageNet7K(y-axis). Right: Histograms ofaccuracies for the same 200 categories in Rand200a, ImageNet1K, and ImageNet7K,
example categories indicated with colored markers.

(Fig 2 right). One explanation is that for the one-against-all approach, a correct
prediction would require that the true classiﬁer be more conﬁdent than any otherclassiﬁers, which becomes more diﬃcult with a larger number of classes as the
chance of false alarms from others greatly increases. Then the behavior starts toresemble kNN methods, which are only conﬁdent about close neighbors.
Looking in more detail at the confusion between the categories in ImageNet7K
reveals additional structure (Fig. 3). Most notable is the generally block diagonal
structure, indicating a correlation between the structure of the semantichierarchy (by WordNet) and visual confusion between the categories.
The two most apparent blocks roughly align with “artifacts” and “animals”,
two very high level nodes in WordNet, suggesting the least amount of confusion
between these two classes with more confusion within. This is consistent withboth computational studies on smaller numbers of classes [30] and some humanabilities [38]. Sections of the confusion matrix are further expanded in Fig. 3.
These also show roughly block diagonal structures at increasingly ﬁner levels
not available in other datasets. The pattern is roughly block diagonal, but by
no means exact. There is a great deal of noise and a fainter “plaid”, oscillating
pattern of stripes, indicating that the ordering of categories in WordNet is notcompletely in agreement with the visual confusion between them.
The block patterns indicate that it is possible to speed up the classiﬁcation byusing a sublinear number of classiﬁers in a hierarchy, as Griﬃn & Perona havedemonstrated on Caltech256 [30]. They built a hierarchy of classiﬁers directlyfrom the confusion matrix. Here we conﬁrm their ﬁndings by observing a muchstronger pattern on a large number of classes. Moreover we note that such agrouping may actually be directly obtained from WordNet, in which case, theoutput of an internal classiﬁer in the hierarchy would be semantically meaningful.
Also of note is that in scaling to many classes, only a small subset of the
distractor classes are truly distracting, possibly explaining the smaller than

78

J. Deng et al.
Bird RepƟle Fish

AnimalAquaƟc birdArƟfact
BirdAquaƟc bird?

RepƟleRedshank

Fish?
Copper rockĮsh

Yellowhammer Triceratops ^ŽůĚŝĞƌĮƐŚ

Shelduck Ruddy turnstone

Structure Covering

Building

Structure
Building?
Sod house

Covering?
01

Cardigan20

Accuracy (%)

Rope bridge DishragViaduct

Ziggurat

Fig. 3. Confusion matrix and sub-matrices of classifying the 7404 leaf categories in ImageNet7K, ordered by a depth ﬁrst traversal of the WordNet hierarchy, using SPM+SVM.
Left: Downsampled 7404 × 7404 confusion matrix, each pixel representing max confusion over 4 × 4 entries. Middle: Zoom-in to two sub-matrices ( top: 949 × 949;
bottom: 1368 × 1368 ), each pixel 2 × 2 entries. One row of the matrix is plotted below each matrix (corresponding to red outlined images). The correct class is indicatedby a red triangle. Examples of other classes are also shown. Right: Further zoom-in(top: 188 × 188; bottom: 145 × 145), each pixel representing the confusion between two
individual categories.

expected performance drop. For example, to classify “German shepherd”, mostof the distractor classes are “easy” ones like “dishrag”, while only a few semantically related classes like “husky” add to the diﬃculty. It suggests that one key toimproving large scale classiﬁcation is to focus on those classes, whose diﬃculty
correlates with semantic relatedness. We quantify this correlation in Sec. 7.

7

Density Matters

Our discussion so far has focused on the challenges arising from the sheer numberof categories. Figure 3 reveals that the diﬃculty of recognition varies signiﬁcantly
over diﬀerent parts of the semantic space. Some classiﬁers must tackle more semantically related, and possibly visually similar, categories. Accurate classiﬁcation of such categories leads to useful applications, e.g. classifying groceries
for assisting the visually impaired, classifying home appliances for housekeeping
robots, or classifying insect species for environmental monitoring [39]. We referto sets of such categories as dense and study the eﬀect of density on classiﬁcation.
We begin by comparing mean classiﬁcation accuracy for classiﬁers trained
and tested on each of the small datasets – Fungus134, Ungulate183, Vehicle262,

What Does Classifying More Than 10,000 Image Categories Tell Us?

Accuracy (%)

30

SPM+SVM
BOW+SVM
BOW+NN
GIST+NN2030
Accuracy (%)

40

10

20
10
0
0

0

4
2
83
0
us13 late1 icle26alNet20 and200
R
C
Fung Ungu Veh

Dense

79

SparseDense

5Fungus134
Ungulate183
Vehicle262
CalNet200
Rand200{abc}10Sparsity

SparseFig. 4. Left: Accuracy on datasets of varying density. Note that CalNet200 (the Caltech 256 categories in ImageNet) has low density and diﬃculty on par with a set of 200
randomly sampled categories. Right: Accuracy (using SPM+SVM) versus dataset density
measured by mean distance in WordNet (see Sec. 7).

CalNet200, Rand200 – across descriptors and classiﬁers in Fig. 4. Note that while
SPM+SVM produces consistently higher accuracies than the other approaches, theordering of datasets by performance is exactly the same for each approach4 .
This indicates that there is a signiﬁcant diﬀerence in diﬃculty between
diﬀerent datasets, independent of feature and classiﬁer choice.
Next we try to predict the diﬃculty of a particular dataset by measuring thedensity of the categories, based on the hierarchical graph structure of WordNet.
We deﬁne the distance, h(i, j), between categories i and j, as the height of theirlowest common ancestor. The height of a node is the length of the longest path
down to a leaf node (leaf nodes have height 0). We measure the density of adataset as the mean h(i, j) between all pairs of categories – smaller implies
denser. See Fig. 5 for an illustration and for examples of pairs of categories fromeach dataset that have distance closest to the mean for that dataset. There is avery clear correlation between the density in WordNet and accuracyof visual classiﬁcation; denser datasets predict lower accuracy (Fig. 4).
This is despite the fact that WordNet was not created as a visual hierarchy!
Classiﬁcation accuracy on 200 randomly chosen categories (Rand200{a,b,c})
is more than 3 times higher than on the 134 categories from Fungus134. The large
gap suggests that the methods studied here are not well equipped for classifying
dense sets of categories. In fact, there have been relatively few eﬀorts on “denseclassiﬁcation” with some notable exceptions, e.g. [40,41,39]. The results seemto call for perhaps more specialized features and models, since it is one key toimproving large scale classiﬁcation performance as discussed in Sec. 6
Also of note is that the Caltech256 categories that occur in ImageNet (CalNet200) have very low density and relatively high accuracy – in almost exactly
the same range as random sets of categories. The Caltech categories are very
sparse and do not exhibit the diﬃculty of dense sets of categories,
4

Ordering of datasets is consistent, but ordering of methods may change between
datasets as noted in Sec. 6 where BOW+SVM and the kNN approaches switch order.

80

J. Deng et al.
CraŌ

Fungus134

6
WatercraŌ

AircraŌ

5

6

Boletus chrysenteron

Tricholoma vaccinum

Ungulate183

Sailing vessel

5 Ship2

Muntjac

Llama

Sailboat

Galleon

Vehicle262

20

Skidder1

11Trimaran

Catboat2

5

Streamroller

CalNet200

6

Catamaran

0 2 4 6 8 10 12Baseball glove

Mean distance

Skyscraper

Fig. 5. Left: Illustration of the inter-class distance (indicated by the numbers) between “sailboat” and other classes, as deﬁned in Sec. 7. Any descendant of ship isfurther from sailboat than gallon but closer than those in aircraft. Note that one stepup the hierarchy may increase the distance by more than one as the tree height is thelength of the longest path to a leaf node. Right: Each row shows a pair of example
categories from the dataset indicated in the center column. The pairs are chosen tohave distance near the mean distance in WordNet (Sec. 7) between categories in thedataset, indicated by the bars in the center column.

making Caltech-like datasets incomplete as an evaluation resource towards some of the real-world image classiﬁcation problems.
Finally we note that our WordNet based measure is not without limitations,e.g. “food tuna” and “ﬁsh tuna” are semantically related but belong to “food”
and “ﬁsh” subtrees respectively, so are far away from each other. Nonetheless asa starting point for quantifying semantic density, the results are encouraging.

8

Hierarchy Matters

For recognition at the scale of human ability, categories will necessarily overlap
and display a hierarchical structure [11]. For example, a human may label “redshank” as “shorebird”, “bird”, or “animal”, all of which are correct but with adecreasing amount of information. Humans make mistakes too, but to diﬀerent
degrees at diﬀerent levels – a “redshank” might be mistaken as a “red-backed
sandpiper”, but almost never as anything under “home appliance”.
The implications for real world object classiﬁcation algorithms are two fold.
First a learning algorithm needs to exploit real world data that inevitably haslabels at diﬀerent semantic levels. Second, it is desirable to output labels as
informative as possible while minimizing mistakes at higher semantic levels.
Consider an automatic photo annotator. If it cannot classify “redshank” reliably, an answer of “bird” still carries much more information than “microwave”.
However, our classiﬁers so far, trained to minimize the 0-1 loss 5 , have no incentive to do so – predicting “microwave” costs the same as predicting “bird”.

5

The standard loss function for classiﬁcation, where a correct classiﬁcation costs zeroand any incorrect classiﬁcation costs 1.

11

Flat
Hierarchical

10
9
8

81

11

HeightHierarchical cost

What Does Classifying More Than 10,000 Image Categories Tell Us?

10
9
8

NN
NN
SVM
SVM
SPM+ BOW+ BOW+ GIST+

05000 10000
Average # of descendents

Fig. 6. Left: Hierarchical cost of ﬂat classiﬁcation and hierarchical classiﬁcation on
ImageNet10K across diﬀerent methods. Right: Mean number of descendants for nodes
at each height, indicating the eﬀective log-scale for hierarchical cost.

Here we explore ways to make classiﬁers more informative. We deﬁne a hierarchical cost Ci,j for classifying an image of class j as class i as Ci,j = 0 wheni = j or when i is a descendant of j, and Ci,j = h(i, j), the height of their lowest
common ancestor in WordNet, otherwise. This cost deﬁnition directly measures
the semantic level at which a misclassiﬁcation occurs – a more informative classiﬁer, one able to discriminate ﬁner details, would have lower cost. It also takes
care of the overlapping categories – there is penalty for classifying an image in
an internal node as its (more general) ancestor but no cost for classifying it as
any of its (more speciﬁc) descendants. As an example, in Fig. 5 left, for an image labeled as “sailboat”, classifying it as “catamaran” or any other descendant
incurs no cost 6 while classifying as any descendant of “aircraft” incurs cost 6.
We can make various classiﬁcation approaches cost sensitive by obtaining
probability estimates (Appendix). For a query image x, given posterior probability estimates p̂j (x) for class j, j ∈ {1, . . . K}, according to Bayesian decision
theory, the optimal prediction is obtained
by predicting the label that minimizes
the expected cost f (x) = arg mini=1,...,K K
j=1 Ci,j p̂j (x).
Comparing the mean hierarchical cost for the original (ﬂat) classiﬁer withthe mean cost for the cost sensitive (hierarchical) classiﬁer, we ﬁnd a consistent
reduction in cost on ImageNet10K(Fig. 6). It shows that the hierarchical classiﬁer
can discriminate at more informative semantic levels. While these reductions may
seem small, the cost is eﬀectively on a log scale. It is measured by the height in
the hierarchy of the lowest common ancestor, and moving up a level can morethan double the number of descendants (Fig. 6 right).
The reduction of mean cost on its own would not be interesting without aclear beneﬁt to the results of classiﬁcation. The examples in Fig. 7 show query
images and their assigned class for ﬂat classiﬁcation and for classiﬁcation using hierarchical cost. While a whipsnake is misclassiﬁed as ribbon snake, it isstill correct at the “snake” level, thus giving a more useful answer than “sundial”. It demonstrates that classiﬁcation based on hierarchical cost canbe signiﬁcantly more informative.
6

The image can in fact be a “trimaran”, in which case it is not entirely correct topredict “catamaran”. This is a limitation of intermediate level ground truth labels.

82

J. Deng et al.
WƌĞĚŝĐƟŽŶŇĂƚĐŽƐƚ

QueryWƌĞĚŝĐƟŽŶŚŝĞƌĂƌĐŚŝĐĂůĐŽƐƚQuery^ŚŝƉǁƌĞĐŬ

/ĐĞďĞƌŐ;ϭϳͿƌƵŝƐĞƐŚŝƉ;ϰͿBoaƚertŚŝƉƐŶĂŬĞ

^ƵŶĚŝĂů;ϭϲͿZŝďďŽŶƐŶĂŬĞ;ϯͿ^ƉĞĞĚŽŵĞƚĞƌ

WƌĞĚŝĐƟŽŶŇĂƚĐŽƐƚ

WƌĞĚŝĐƟŽŶŚŝĞƌĂƌĐŚŝĐĂůĐŽƐƚQueryWƌĞĚŝĐƟŽŶŇĂƚĐŽƐƚ

WƌĞĚŝĐƟŽŶŚŝĞƌĂƌĐŚŝĐĂůĐŽƐƚ

Barred owl (16) ĂƫŶŐŚĞůŵĞƚ;ϯͿŽīĞĞĐƵƉ

Calla (16)^ŽƵƉďŽǁů;ϯͿ,ĞŵĂƚŽĐƌŝƚ;ϰͿWƵŐͲĚŽŐDŽŚĂŝƌ;ϭϲͿWƵƉƉǇ;ϱͿ

Salp (16)Fig. 7. Example errors using a ﬂat vs. hierarchical classiﬁer with SPM+SVM on ImageNet10K, shown in horizontal groups of three: a query, prediction by a ﬂat classiﬁer(minimizing 0-1 loss), and by a hierarchical classiﬁer (minimizing hierarchical cost).
Numbers indicate the hierarchical cost of that misclassiﬁcation.

9

Conclusion

We have presented the ﬁrst large scale recognition experiments on 10,000+ categories and 9+ million images. We show that challenges arise from the sizeand density of the semantic space. Surprisingly the ordering of NN and Linear
classiﬁcation approaches swap from previous datasets to our very large scale experiments – we cannot always rely on experiments on small datasets to predict
performance at large scale. We produce a measure of category distance based on
the WordNet hierarchy and show that it is well correlated with the diﬃculty ofvarious datasets. We present a hierarchy aware cost function for classiﬁcation andshow that it produces more informative classiﬁcation results. These experiments
point to future research directions for large scale image classiﬁcation, as well as
critical dataset and benchmarking issues for evaluating diﬀerent algorithms.
Acknowledgments. We thank Chris Baldassano, Jia Li, Olga Russakovsky,
Hao Su, Bangpeng Yao and anonymous reviewers for their helpful comments.
This work is partially supported by an NSF CAREER grant and a Google Award
to L.F-F, and by NSF grant 0849512, Intel Research Council and Gigascale
Systems Research Center.

References
1. Biederman, I.: Recognition by components: A theory of human image understanding. PsychR 94, 115–147 (1987)
2. Zhang, H., Berg, A.C., Maire, M., Malik, J.: SVM-KNN: Discriminative Nearest
Neighbor Classiﬁcation for Visual Category Recognition. In: CVPR 2006 (2006)
3. Grauman, K., Darrell, T.: The pyramid match kernel: Discriminative classiﬁcation
with sets of image features. In: ICCV (2005)
4. Lazebnik, S., Schmid, C., Ponce, J.: Beyond bags of features: Spatial pyramid
matching for recognizing natural scene categories. In: CVPR 2006 (2006)
5. Varma, M., Ray, D.: Learning the discriminative power-invariance trade-oﬀ. In:
ICCV (2007)
6. Torralba, A., Fergus, R., Freeman, W.: 80 million tiny images: A large data set for
nonparametric object and scene recognition. PAMI 30, 1958–1970 (2008)

What Does Classifying More Than 10,000 Image Categories Tell Us?

83

7. Felzenszwalb, P., Mcallester, D., Ramanan, D.: A discriminatively trained, multiscale, deformable part model. In: CVPR 2008 (2008)
8. Tuytelaars, T., Mikolajczyk, K.: Local Invariant Feature Detectors: A Survey.
Foundations and Trends in Computer Graphics and Vision 3, 177–820 (2008)
9. Fei-Fei, L., Fergus, R., Torralba, A.: Recognizing and learning object categories.
CVPR Short Course (2007)
10. Fei-Fei, L., Fergus, R., Torralba, A.: Recognizing and learning object categories.
ICCV Short Course (2009)
11. Rosch, E., Mervis, C.B., Gray, W.D., Johnson, D.M., Braem, P.B.: Basic objects
in natural categories. Cognitive Psychology 8, 382–439 (1976)
12. Everingham, M., Zisserman, A., Williams, C.K.I., van Gool, L., et al.: The 2005 pascal visual object classes challenge. In: Quiñonero-Candela, J., Dagan, I., Magnini,B., d’Alché-Buc, F. (eds.) MLCW 2005. LNCS (LNAI), vol. 3944, pp. 117–176.
Springer, Heidelberg (2006)
13. Fei-Fei, L., Fergus, R., Perona, P.: One-shot learning of object categories. PAMI 28,
594–611 (2006)
14. Griﬃn, G., Holub, A., Perona, P.: Caltech-256 object category dataset. Technical
Report 7694, Caltech (2007)
15. Fellbaum, C.: WordNet: An Electronic Lexical Database. MIT Press, Cambridge(1998)
16. Dance, C., Willamowski, J., Fan, L., Bray, C., Csurka, G.: Visual categorization
with bags of keypoints. In: ECCV International Workshop on Statistical Learningin Computer Vision (2004)
17. Lowe, D.: Distinctive image features from scale-invariant keypoints. IJCV 60, 91–
110 (2004)
18. Dalal, N., Triggs, B.: Histograms of oriented gradients for human detection. In:
CVPR 2005, pp. 886–893 (2005)
19. Chum, O., Zisserman, A.: An exemplar model for learning object classes. In: CVPR
2007, pp. 1–8 (2007)
20. Vedaldi, A., Gulshan, V., Varma, M., Zisserman, A.: Multiple kernels for object
detection. In: ICCV (2009)
21. Gehler, P.V., Nowozin, S.: On feature combination for multiclass object classiﬁcation. In: ICCV (2009)
22. Rifkin, R., Klautau, A.: In defense of one-vs-all classiﬁcation. JMLR 5, 101–141(2004)
23. Maji, S., Berg, A.C.: Max-margin additive models for detection. In: ICCV (2009)24. Deng, J., Dong, W., Socher, R., Li, L., Li, K., Fei-Fei, L.: ImageNet: A large-scale
hierarchical image database. In: CVPR 2009 (2009)
25. Fergus, R., Weiss, Y., Torralba, A.: Semi-supervised learning in gigantic image
collections. In: NIPS (2009)
26. Wang, C., Yan, S., Zhang, H.J.: Large scale natural image classiﬁcation by sparsity
exploration. ICASP (2009)
27. Nister, D., Stewenius, H.: Scalable recognition with a vocabulary tree. In: CVPR
2006, pp. II: 2161–2168 (2006)
28. Marszalek, M., Schmid, C.: Semantic hierarchies for visual object recognition. In:
CVPR 2007, pp. 1–7 (2007)
29. Zweig, A., Weinshall, D.: Exploiting object hierarchy: Combining models from
diﬀerent category levels. In: ICCV 2007, pp. 1–8 (2007)
30. Griﬃn, G., Perona, P.: Learning and using taxonomies for fast visual categorization. In: CVPR 2008 (2008)

84

J. Deng et al.

31. Everingham, M., Van Gool, L., Williams, C.K.I., Winn, J., Zisserman, A.: The
PASCAL Visual Object Classes Challenge, VOC 2009 Results (2009),
http://www.pascal-network.org/challenges/VOC/voc2009/workshop/
32. http://www.image-net.org
33. Oliva, A., Torralba, A.: Modeling the shape of the scene: A holistic representationof the spatial envelope. IJCV 42, 145–175 (2001)
34. Fan, R.E., Chang, K.W., Hsieh, C.J., Wang, X.R., Lin, C.J.: LIBLINEAR: A library for large linear classiﬁcation. JMLR 9, 1871–1874 (2008)
35. Crammer, K., Singer, Y., Cristianini, N., Shawe-Taylor, J., Williamson, B.: On thealgorithmic implementation of multiclass kernel-based vector machines. JMLR 2(2001)
36. Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest
neighbor in high dimensions. In: FOCS 2006, pp. 459–468 (2006)
37. Boiman, O., Shechtman, E., Irani, M.: In defense of nearest-neighbor based image
classiﬁcation. In: CVPR 2008 (2008)
38. Thorpe, S., Fize, D., Marlot, C.: Speed of processing in the human visual system.
Nature 381, 520–522 (1996)
39. Martinez-Munoz, G., Larios, N., Mortensen, E., Zhang, W., Yamamuro, A., Paasch,
R., Payet, N., Lytle, D., Shapiro, L., Todorovic, S., Moldenke, A., Dietterich, T.:
Dictionary-free categorization of very similar objects via stacked evidence trees.
In: CVPR 2009 (2009)
40. Nilsback, M.E., Zisserman, A.: A visual vocabulary for ﬂower classiﬁcation. In:
CVPR 2006, pp. 1447–1454 (2006)
41. Ferencz, A., Learned-Miller, E.G., Malik, J.: Building a classiﬁcation cascade forvisual identiﬁcation from one example. In: ICCV 2005, pp. 286–293 (2005)
42. Vedaldi, A., Fulkerson, B.: VLFeat: An open and portable library of computer
vision algorithms (2008), http://www.vlfeat.org
43. Lin, H.T., Lin, C.J., Weng, R.C.: A note on platt’s probabilistic outputs for support
vector machines. Mach. Learn. 68, 267–276 (2007)

A

Experimental Details

We obtain BoW histograms (L1-normalized) using dense SIFT [42] on 20x20
overlapping patches with a spacing of 10 pixels at 3 scales on images resized to a
max side length of 300, and a 1000 codebook from KMeans on 10 million SIFT
vectors. We use the same codewords to obtain spatial pyramid histograms (3levels), φ2 encoded [23] to approximate the intersection kernel with linear SVMs.
Due to high dimensionality (21k), we only encode nonzeros (but add a bias term).
This preserves the approximation for our, non-negative, data, but with slightly
diﬀerent regularization. We found no empirical performance diﬀerence testing up
to 1K categories. To save memory, we use only two bytes for each entry of encoded
vectors (sparse) by delta-coding its index (1 byte) and quantizing its value to
256 levels (1 byte). We further reduce memory by only storing every other entry,
exploiting redundancy in consecutive entries. We use LIBLINEAR [34] to train
linear SVMs, parameter C determined by searching over 3 values (0.01, 0.1, 1 for
ImageNet10K) with 2-fold cross validation. We use smaller weight for negative
examples(100× smaller for ImageNet10K) than positives. We obtain posterior
probability estimates by ﬁtting a sigmoid function to the outputs of SVMs [43],or by taking the percent of neighbors from a class for NN.