Why Size Matters: Feature Coding as Nystrom Sampling
Authors: Oriol Vinyals, Yangqing Jia, Trevor Darrell
ICLR 2013

Abstract: Recently, the computer vision and machine learning community has been in favor of feature extraction pipelines that rely on a coding step followed by a linear classifier, due to their overall simplicity, well understood properties of linear classifiers, and their computational efficiency. In this paper we propose a novel view of this pipeline based on kernel methods and Nystrom sampling. In particular, we focus on the coding of a data point with a local representation based on a dictionary with fewer elements than the number of data points, and view it as an approximation to the actual function that would compute pair-wise similarity to all data points (often too many to compute in practice), followed by a Nystrom sampling step to select a subset of all data points. Furthermore, since bounds are known on the approximation power of Nystrom sampling as a function of how many samples (i.e. dictionary size) we consider, we can derive bounds on the approximation of the exact (but expensive to compute) kernel matrix, and use it as a proxy to predict accuracy as a function of the dictionary size, which has been observed to increase but also to saturate as we increase its size. This model may help explaining the positive effect of the codebook size and justifying the need to stack more layers (often referred to as deep learning), as flat models empirically saturate as we add more complexity.

Why Size Matters:
Feature Coding as Nystr¨om Sampling
Oriol Vinyals
UC Berkeley
Berkeley, CA
Yangqing Jia
UC Berkeley
Berkeley, CA
Trevor Darrell
UC Berkeley
Berkeley, CA
1 Introduction
Recently, the computer vision and machine learning community has been in favor of feature extrac-
tion pipelines that rely on a coding step followed by a linear classiﬁer, due to their overall simplicity,
well understood properties of linear classiﬁers, and their computational efﬁciency. In this paper we
propose a novel view of this pipeline based on kernel methods and Nystr¨om sampling. In particular,
we focus on the coding of a data point with a local representation based on a dictionary with fewer
elements than the number of data points, and view it as an approximation to the actual function
that would compute pair-wise similarity to all data points (often too many to compute in practice),
followed by a Nystr¨om sampling step to select a subset of all data points.
Furthermore, since bounds are known on the approximation power of Nystr ¨om sampling as a func-
tion of how many samples (i.e. dictionary size) we consider, we can derive bounds on the approx-
imation of the exact (but expensive to compute) kernel matrix, and use it as a proxy to predict
accuracy as a function of the dictionary size, which has been observed to increase but also to satu-
rate as we increase its size. This model may help explaining the positive effect of the codebook size
[2, 7] and justifying the need to stack more layers (often referred to as deep learning), as ﬂat models
empirically saturate as we add more complexity.
2 The Nystr ¨om View
We speciﬁcally consider forming a dictionary by sampling our training set. To encode a new sample
x ∈ Rd, we apply a (generally non-linear) coding function c so that c(x) ∈ Rc. Note that d
is the dimensionality of the original feature space, while c is the dictionary size. The standard
classiﬁcation pipeline considers c(x) as the new feature space, and typically uses a linear classiﬁer
on this space. For example, one may use the threshold encoding function [2] as an example:c(x) =
max(0,x⊤D −α) where D ∈Rd×c is the dictionary. Note that our discussion on coding is valid
for many different feed-forward coding schemes.
In the ideal case (inﬁnite computation and memory), we encode each sample x using the whole
training set X ∈Rd×N, which can be seen as the best local coding of the training set X (as long
as over-ﬁtting is handled by the classiﬁcation algorithm). In general, larger dictionary sizes yield
better performance assuming the linear classiﬁer is well regularized, as it can be seen as a way to do
manifold learning [6]. We deﬁne the new coded feature space as C = max(0,X⊤X −α), where
the i-th row of C corresponds to coding the i-th sample c(xi). The linear kernel function between
samples i and j is k(xi,xj) = c(xi)⊤c(xj). The kernel matrix is then K = CC⊤. Naively
applying Nystr¨om sampling to the matrix K does not save any computation, as every column of K
requires computing an inner product withN samples. However, if we decompose the matrixC with
Nystr¨om sampling (i.e., with a subsampled dictionary) we obtain C′ ≈C, and as a consequence
K′≈K:
C′= EW−1E⊤, K′= C′C′⊤= EW−1E⊤EW−1E⊤= EΛE⊤
1
arXiv:1301.5348v2  [cs.LG]  16 Apr 2013
where the ﬁrst equation comes from applying Nystr ¨om sampling to C, E is a random subsample
of the columns of C, and W the corresponding square matrix with the same random subsample of
both columns and rows of C.
3 Main Results on Approximation Bounds
More interestingly, many bounds on the error made in estimating C by C′exist, and ﬁnding better
sampling schemes that improve such bounds is an active topic in the machine learning community
(see e.g. [4]). The bound we start with is [4]:
||C −C′||F ≤||C −Ck||F + ϵmax(nCii) (1)
valid if c ≥ 64k/ϵ4 (c is the number of columns that we sample from C to form E, i.e. the
codebook size), where kis the sufﬁcient rank to estimate the structure of C, and Ck is the optimal
rank kapproximation (given by Singular Value Decomposition (SVD), which we cannot compute in
practice). Note that, if we assume that our training set can be explained by a manifold of dimension
k(i.e. the ﬁrst term in the right hand side of eq. 1 vanishes), then the error is proportional to ϵtimes
a constant (that is dataset dependent).
Thus, if we ﬁx k to the value that retains enough energy from C, we get a bound that for every c
(dimension of code), gives a minimum ϵto plug in equation 1. This gives us a useful bound of the
form ϵ≥Mc−1
4 for some constant M (that depends on k). Putting it all together, we get:
||C −C′||F ≤O+ Mc−1
4
with Oand M constants that are dataset speciﬁc.
Having bounded the error C is not sufﬁcient to establish how the code size will affect the classiﬁer
performance. In particular, it is not clear how the error onC affect the error on the kernel matrixK.
However, we are able to prove that the error bound onK′is in the same format as that on C:
||K −K′||F ≤O+ Mc−1
4 (2)
Even though we are not aware of an easy way to formally link degradation in Frobenius norm of
our approximation K′to K to classiﬁcation accuracy, the bound above is informative as one may
reasonably expect kernel matrices of different quality to have classiﬁcation performances in the same
trend.
4 Experiments
We empirically evaluate the bound on the kernel matrix, used as a proxy to model classiﬁcation ac-
curacy, which is the measure of interest. To estimate the constants in the bound, we do interpolation
of the observed accuracy in the ﬁrst two samples of accuracy versus codebook size, which is of prac-
tical interest: one may want to quickly run a new dataset through the pipeline with small codebook
sizes, and then quickly estimate what the accuracy would be when running a full experiment with a
much larger dictionary size.
0 1000 2000 3000 4000 5000 600060
65
70
75
80
85
90
95
100
Codebook size
Accuracy
CIFAR
 
 
Empirical Train
Nystrom Bound Train
Empirical Test
0 1000 2000 3000 4000 5000 6000 7000 800035
40
45
50
55
60
65
70
Codebook size
Accuracy
TIMIT
 
 
Empirical Train
Nystrom Bound Train
Empirical Test
Figure 1: Empirical accuracy (solid line) and Nystr¨om model accuracy (dashed line) on the training
(red) and testing (blue) sets versus dictionary size, on CIFAR-10 (left) and TIMIT (right).
Figure 1 shows the results on on the CIFAR-10 image classiﬁcation and TIMIT speech recognition
datasets respectively. It is observed that the derived model closely follow our own empirical ob-
servations, with red dashed line serving as a lower bound of the actual accuracy and following the
2
100 200 400 800 1600 3200
Final Dictionary Size
66
68
70
72
74
76
78
80Accuracy
K-means
2x PDL
4x PDL
8x PDL
100 200 400 800 1600 3200
Final Dictionary Size
50
51
52
53
54
55
56
57
58
59Accuracy
K-means
2x PDL
4x PDL
8x PDL
Figure 2: Accuracy values on the CIFAR-10 (left) and STL (right) datasets under different ﬁnal
dictionary size. “nx PDL” means overshooting the dictionary from a starting dictionary that is n
times larger than the ﬁnal one. We refer to our tech report [3] for more details.
shape of the empirical accuracy, predicting its saturation. The model is never too tight though, due
to various factors of our approximation, e.g., the analytical relationship between the approximation
of K and the classiﬁcation accuracy is not clear.
The Nystr ¨om view of feature encoding and the approximation bounds we proposed helps under-
standing several key observations in the recent literature: (1) the linear classiﬁer performance is al-
ways bounded when using a ﬁxed codebook, and performance increases when the codebook grows
[2], even with a huge codebook [7], and (2) simple dictionary learning techniques have been found
efﬁcient in some classiﬁcation pipelines [1, 5], and K-means works particularly well as a dictionary
learning algorithm albeit its simplicity, a phenomenon that is common in the Nystr ¨om sampling
context [4].
In addition, in many image classiﬁcation tasks the feature extraction pipeline is composed of more
than feature encoding. For example, recent state-of-the-art methods pool locally encoded features
spatially to form the ﬁnal feature vector. The Nystr ¨om view presented in the paper inspires us to
employ ﬁndings in the machine learning ﬁeld to learn better, pooling-aware dictionaries. In one of
our related work [3], we form a dictionary by ﬁrst “overshooting” the coding stage with a larger
dictionary, and then pruning it using K-centers with pooled features. Figure 2 shows an increase in
the ﬁnal classiﬁcation accuracy compared with the baseline that only learns the dictionary on the
patch-level, with no additional computation cost for either feature extraction or classiﬁcation.
References
[1] A Coates, H Lee, and AY Ng. An analysis of single-layer networks in unsupervised feature
learning. In AISTATS, 2011.
[2] A Coates and AY Ng. The importance of encoding versus training with sparse coding and vector
quantization. In ICML, 2011.
[3] Y Jia, O Vinyals, and T Darrell. Pooling-invariant image feature learning.
http://arxiv.org/abs/1302.5056, 2013.
[4] S Kumar, M Mohri, and A Talwalkar. Sampling methods for the nystr ¨om method. JMLR,
13(4):981–1006, 2012.
[5] A Saxe, PW Koh, Z Chen, M Bhand, B Suresh, and AY Ng. On random weights and unsuper-
vised feature learning. In ICML, 2011.
[6] J Wang, J Yang, K Yu, F Lv, T Huang, and Y Gong. Locality-constrained linear coding for
image classiﬁcation. In CVPR, 2010.
[7] J Yang, K Yu, and T Huang. Efﬁcient highly over-complete sparse coding using a mixture
model. In ECCV, 2010.
3


Peer review:
[Review]:
We agree with the reviewer regarding the existence of better dictionary learning methods, and note that many of these are also related to corresponding advanced Nystrom sampling methods, such as [Zhang et al. Improved Nystrom low-rank approximation and error analysis. ICML 08]. These methods could improve performance in absolute terms, but that is an orthogonal issue to our main results.  Nonetheless, we think this is a valuable observation, and will include a discussion of these points in the final version of this paper.

The relationship between a kernel error bound and classification accuracy is discussed in more detail in [Cortes et al. On the Impact of Kernel Approximation on Learning Accuracy. AISTATS 2010]. The main result is that the bounds are proportional, verifying our empirical claims. We will add this reference to the paper.

Regarding the comment on fitting the shape of the curve, we are only using the first two points to fit the 'constants' given in the bound, so the fact that it extrapolates well in many tasks gives us confidence that the bound is accurate.