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]:
This paper presents a theoretical analysis and empirical validation of a novel view of feature extraction systems based on the idea of Nystrom sampling for kernel methods.  The main idea is to analyze the kernel matrix for a feature space defined by an off-the-shelf feature extraction system.  In such a system, a bound is identified for the error in representing the 'full' dictionary composed of all data points by a Nystrom approximated version (i.e., represented by subsampling the data points randomly).  The bound is then extended to show that the approximate kernel matrix obtained using the Nystrom-sampled dictionary is close to the true kernel matrix, and it is argued that the quality of the approximation is a reasonable proxy for the classification error we can expect after training.  It is shown that this approximation model qualitatively predicts the monotonic rise in accuracy of feature extraction with larger dictionaries and saturation of performance in experiments.

This is a short paper, but the main idea and analysis are interesting.  It is nice to have some theoretical machinery to talk about the empirical finding of rising, saturating performance.  In some places I think more detail could have been useful.

One undiscussed point is the fact that many dictionary-learning methods do more than populate the dictionary with exemplars so it's possible that a 'learning' method might do substantially better (perhaps reaching top performance much sooner).  This doesn't appear to be terribly important in low-dimensional spaces where sampling strategies work about as well as learning, but could be critical for high-dimensional spaces (where sampling might asymptote much more slowly than learning).  It seems worth explaining the limitations of this analysis and how it relates to learning.  

A few other questions / comments:

The calibration of constants for the bound in the experiments was not clear to me.  How is the mapping from the bound (Eq. 2) to classification accuracy actually done?

The empirical validation of the lower bound relies on a calibration procedure that, as I understand it, effectively ends up rescaling a fixed-shape curve to fit observed trend in accuracy on the real problem.  As a result, it seems like we could come up with a 'nonsense' bound that happened to have such a shape and then make a similar empirical claim.  Is there a way to extend the analysis to rule this out?  Or perhaps I misunderstand the origin of the shape of this curve.

Pros:  
(1)  A novel view of feature extraction that appears to yield a reasonable explanation for the widely observed performance curves of these methods is presented.  I don't know how much profit this view might yield, but perhaps that will be made clear by the 'overshooting' method foreshadowed in the conclusion.
(2) A pleasingly short read adequate to cover the main idea.  (Though a few more details might be nice.)

Cons:
(1)  How this bound relates to the more common case of 'trained' dictionaries is unclear.
(2)  The empirical validation shows the basic relationship qualitatively, but it is possible that this does not adequately validate the theoretical ideas and their connection to the observed phenomenon.