Kernel Methods for Deep Learning
Youngmin Cho and Lawrence K. Saul
Department of Computer Science and Engineering
University of California, San Diego
9500 Gilman Drive, Mail Code 0404
La Jolla, CA 92093-0404
{yoc002, saul}@cs.ucsd.edu
Abstract
We introduce a new family of positive-definite kernel functions that mimic the
computation in large, multilayer neural nets. These kernel functions can be used
in shallow architectures, such as support vector machines (SVMs), or in deep
kernel-based architectures that we call multilayer kernel machines (MKMs). We
evaluate SVMs and MKMs with these kernel functions on problems designed to
illustrate the advantages of deep architectures. On several problems, we obtain
better results than previous, leading benchmarks from both SVMs with Gaussian
kernels as well as deep belief nets.
1 Introduction
Recent work in machine learning has highlighted the circumstances that appear to favor deep archi-
tectures, such as multilayer neural nets, over shallow architectures, such as support vector machines
(SVMs) [1]. Deep architectures learn complex mappings by transforming their inputs through mul-
tiple layers of nonlinear processing [2]. Researchers have advanced several motivations for deep
architectures: the wide range of functions that can be parameterized by composing weakly non-
linear transformations, the appeal of hierarchical distributed representations, and the potential for
combining unsupervised and supervised methods. Experiments have also shown the benefits of
deep learning in several interesting applications [3, 4, 5].
Many issues surround the ongoing debate over deep versus shallow architectures [1, 6]. Deep ar-
chitectures are generally more difficult to train than shallow ones. They involve difficult nonlinear
optimizations and many heuristics. The challenges of deep learning explain the early and continued
appeal of SVMs, which learn nonlinear classifiers via the "kernel trick”. Unlike deep architectures,
SVMs are trained by solving a simple problem in quadratic programming. However, SVMs cannot
seemingly benefit from the advantages of deep learning.
Like many, we are intrigued by the successes of deep architectures yet drawn to the elegance of ker-
nel methods. In this paper, we explore the possibility of deep learning in kernel machines. Though
we share a similar motivation as previous authors [7], our approach is very different. Our paper
makes two main contributions. First, we develop a new family of kernel functions that mimic the
computation in large neural nets. Second, using these kernel functions, we show how to train multi-
layer kernel machines (MKMs) that benefit from many advantages of deep learning.
The organization of this paper is as follows. In section 2, we describe a new family of kernel
functions and experiment with their use in SVMs. Our results on SVMs are interesting in their own
right; they also foreshadow certain trends that we observe (and certain choices that we make) for the
MKMs introduced in section 3. In this section, we describe a kernel-based architecture with multiple
layers of nonlinear transformation. The different layers are trained using a simple combination of
supervised and unsupervised methods. Finally, we conclude in section 4 by evaluating the strengths
and weaknesses of our approach.
1 2 Arc-cosine kernels
In this section, we develop a new family of kernel functions for computing the similarity of vector
inputs x, y Є Rd. As shorthand, let (z) = ½ (1 + sign(z)) denote the Heaviside step function. We
define the nth order arc-cosine kernel function via the integral representation:
|| w ||
kn(x, y) = 2
/dv
dw
(2π)d/2
O(w x) (wy) (w⋅ x)" (w·y)"
(1)
The integral representation makes it straightforward to show that these kernel functions are positive-
semidefinite. The kernel function in eq. (1) has interesting connections to neural computation [8]
that we explore further in sections 2.2-2.3. However, we begin by elucidating its basic properties.
2.1
Basic properties
We show how to evaluate the integral in eq. (1) analytically in the appendix. The final result is most
easily expressed in terms of the angle 0 between the inputs:
Ꮎ = COS
-1
x.y
|x||||y||
The integral in eq. (1) has a simple, trivial dependence on the magnitudes of the inputs x and y,
a complex, interesting dependence on the angle between them. In particular, we can write:
(2)
but
1
kn(x, y) =
||x|| ||y|| Jn (0)
(3)
П
where all the angular dependence is captured by the family of functions Jn (0). Evaluating the
integral in the appendix, we show that this angular dependence is given by:
n
Jn (0)
=
(−1)" (sin 0) 2n+1 (si 10 00
1 მ
;)" (
π-
sin
(4)
For n= 0, this expression reduces to the supplement of the angle between the inputs. However, for
n>0, the angular dependence is more complicated. The first few expressions are:
eq.
Jo(0)
= п-0
J1(0)
J2(0)
=
=
sin
(0) cos 0
‚-1 x.y
3 sin cos 0+ ( − 0) (1 + 2 cos² 0)
=
(5)
(7)
We describe (3) as an arc-cosine kernel because for n 0, it takes the simple form
ko(x, y) = 1−= COS
|||||||| . In fact, the zeroth and first order kernels in this family are strongly
motivated by previous work in neural computation. We explore these connections in the next section.
Arc-cosine kernels have other intriguing properties. From the magnitude dependence in eq. (3),
we observe the following: (i) the n = 0 arc-cosine kernel maps inputs x to the unit hypersphere
in feature space, with ko(x,x) = 1; (ii) the n = 1 arc-cosine kernel preserves the norm of inputs,
with k₁(x, x) = ||x||2; (iii) higher order (n> 1) arc-cosine kernels expand the dynamic range of the
inputs, with kn(x, x) ~ ||x||2n. Properties (i)–(iii) are shared respectively by radial basis function
(RBF), linear, and polynomial kernels. Interestingly, though, the n = 1 arc-cosine kernel is highly
nonlinear, also satisfying k₁ (x, -x) = 0 for all inputs x. As a practical matter, we note that arc-
cosine kernels do not have any continuous tuning parameters (such as the kernel width in RBF
kernels), which can be laborious to set by cross-validation.
2.2 Computation in single-layer threshold networks
Consider the single-layer network shown in Fig. 1 (left) whose weights Wij connect the jth input
unit to the ith output unit. The network maps inputs x to outputs f(x) by applying an elementwise
nonlinearity to the matrix-vector product of the inputs and the weight matrix: f(x) = g(Wx). The
nonlinearity is described by the network's so-called activation function. Here we consider the family
of one-sided polynomial activation functions gn (2) = O(z)z" illustrated in the right panel of Fig. 1.
2 f₁
f;
fm
W
0.5
X
Step (n=0)
1
1
Ramp (n=1)
1
Quarter-pipe (n=2)
JJJ
0.5
0.5
0
0
0
-1
0
1
-1
0
1
-1 0 1
Figure 1: Single layer network and activation functions
For n=0, the activation function is a step function, and the network is an array of perceptrons. For
n=1, the activation function is a ramp function (or rectification nonlinearity [9]), and the mapping
f(x) is piecewise linear. More generally, the nonlinear (non-polynomial) behavior of these networks
is induced by thresholding on weighted sums. We refer to networks with these activation functions
as single-layer threshold networks of degree n.
Computation in these networks is closely connected to computation with the arc-cosine kernel func-
tion in eq. (1). To see the connection, consider how inner products are transformed by the mapping
in single-layer threshold networks. As notation, let the vector w; denote ith row of the weight
matrix W. Then we can express the inner product between different outputs of the network as:
f(x) · f(y)
=
m
(w₁ x)O(w₁ y)(Wi ⋅ x)" (W¿ ⋅ y)”,
i=1
(8)
where m is the number of output units. The connection with the arc-cosine kernel function emerges
in the limit of very large networks [10, 8]. Imagine that the network has an infinite number of
output units, and that the weights Wij are Gaussian distributed with zero mean and unit vari-
ance. In this limit, we see that eq. (8) reduces to eq. (1) up to a trivial multiplicative factor:
limm∞ f(x) f(y) = kn(x, y). Thus the arc-cosine kernel function in eq. (1) can be viewed
as the inner product between feature vectors derived from the mapping of an infinite single-layer
threshold network [8].
m
Many researchers have noted the general connection between kernel machines and neural networks
with one layer of hidden units [1]. The n=0 arc-cosine kernel in eq. (1) can also be derived from
an earlier result obtained in the context of Gaussian processes [8]. However, we are unaware of any
previous theoretical or empirical work on the general family of these kernels for degrees n ≥0.
Arc-cosine kernels differ from polynomial and RBF kernels in one especially interesting respect.
As highlighted by the integral representation in eq. (1), arc-cosine kernels induce feature spaces
that mimic the sparse, nonnegative, distributed representations of single-layer threshold networks.
Polynomial and RBF kernels do not encode their inputs in this way. In particular, the feature vector
induced by polynomial kernels is neither sparse nor nonnegative, while the feature vector induced
by RBF kernels resembles the localized output of a soft vector quantizer. Further implications of
this difference are explored in the next section.
2.3 Computation in multilayer threshold networks
A kernel function can be viewed as inducing a nonlinear mapping from inputs x to fea-
ture vectors (x). The kernel computes the inner product in the induced feature space:
k(x, y) = (x) (y). In this section, we consider how to compose the nonlinear mappings in-
duced by kernel functions. Specifically, we show how to derive new kernel functions
k(l) (x, y)
=
Þ(Þ(…..Þ(x))) · Þ(Þ(...Þ(y)))
e times
e times
(9)
which compute the inner product after / successive applications of the nonlinear mapping (.). Our
motivation is the following: intuitively, if the base kernel function k(x, y) = Þ(x) · (y) mimics
the computation in a single-layer network, then the iterated mapping in eq. (9) should mimic the
computation in a multilayer network.
3 Test error rate (%)
26
24
SVM-RBF
22
1 2 3 4 5 6
Step (n=0)
1 2 3 4 5 6
Ramp (n=1)
1 2 3 4 5 6 (l).
Quarter-pipe (n=2)
DBN-3
Figure 2: Left: examples from the rectangles-image data set. Right: classification error rates on the
test set. SVMs with arc-cosine kernels have error rates from 22.36-25.64%. Results are shown for
kernels of varying degree (n) and levels of recursion (l). The best previous results are 24.04% for
SVMs with RBF kernels and 22.50% for deep belief nets [11]. See text for details.
We first examine the results of this procedure for widely used kernels. Here we find that the iterated
mapping in eq. (9) does not yield particularly interesting results. Consider the two-fold composition
that maps x to (Þ(x)). For linear kernels k(x, y) = x y, the composition is trivial: we obtain
the identity map (4(x)) = $(x) = x. For homogeneous polynomial kernels k(x, y) = (x · y)d,
the composition yields:
(P(x)) P(P(y)) = ((x) . Đ(y)) = ((x - y)d)d = (x - y).
(10)
The above result is not especially interesting: the kernel implied by this composition is also polyno-
mial, just of higher degree (d² versus d) than the one from which it was constructed. Likewise, for
RBF kernels k(x, y) = e¯\||×-y||², the composition yields:
Þ(Þ(x)) · Þ(Þ(y)) = e¯\||Þ(x)—Þ(y)||2
= e
-2λ(1-k(x,y))
(11)
Though non-trivial, eq. (11) does not represent a particularly interesting computation. Recall that
RBF kernels mimic the computation of soft vector quantizers, with k(x, y) < 1 when ||x − y|| is
large compared to the kernel width. It is hard to see how the iterated mapping Þ(Þ(x)) would
generate a qualitatively different representation than the original mapping Þ(x).
Next we consider the l-fold composition in eq. (9) for arc-cosine kernel functions. We state the
result in the form of a recursion. The base case is given by eq. (3) for kernels of depth l = 1 and
degree n. The inductive step is given by:
/2
k(l+1) (x, y) = ± [k? (x, x) kg) (y, y) ]"/² Jn (0%),
П
(12)
where 0(e) is the angle between the images of x and y in the feature space induced by the l-fold
composition. In particular, we can write:
0(e)
n
COS
=
(l)
| (k) (x, y) [k) (x, x) k (y, y)]]
(y,y)] = 1/2).
(13)
The recursion in eq. (12) is simple to compute in practice. The resulting kernels mimic the com-
putations in large multilayer threshold networks. Above, for simplicity, we have assumed that the
arc-cosine kernels have the same degree n at every level (or layer) l of the recursion. We can also
use kernels of different degrees at different layers. In the next section, we experiment with SVMs
whose kernel functions are constructed in this way.
2.4 Experiments on binary classification
We evaluated SVMs with arc-cosine kernels on two challenging data sets of 28 × 28 grayscale pixel
images. These data sets were specifically constructed to compare deep architectures and kernel
machines [11]. In the first data set, known as rectangles-image, each image contains an occluding
rectangle, and the task is to determine whether the width of the rectangle exceeds its height; ex-
amples are shown in Fig. 2 (left). In the second data set, known as convex, each image contains a
white region, and the task is to determine whether the white region is convex; examples are shown
4 21
20
19 F
18
Test error rate (%)
SVM-RBF
DBN-3
17
1 2 3 4 5 6
Step (n=0)
1 2 3 4 5 6
Ramp (n=1)
1 2 3 4 5 6 (l).
Quarter-pipe (n=2)
Figure 3: Left: examples from the convex data set. Right: classification error rates on the test set.
SVMs with arc-cosine kernels have error rates from 17.15-20.51%. Results are shown for kernels
of varying degree (n) and levels of recursion (l). The best previous results are 19.13% for SVMs
with RBF kernels and 18.63% for deep belief nets [11]. See text for details.
in Fig. 3 (left). The rectangles-image data set has 12000 training examples, while the convex data
set has 8000 training examples; both data sets have 50000 test examples. These data sets have
been extensively benchmarked by previous authors [11]. Our experiments in binary classification
focused on these data sets because in previously reported benchmarks, they exhibited the biggest
performance gap between deep architectures (e.g., deep belief nets) and traditional SVMs.
We followed the same experimental methodology as previous authors [11]. SVMs were trained using
libSVM (version 2.88) [12], a publicly available software package. For each SVM, we used the last
2000 training examples as a validation set to choose the margin penalty parameter; after choosing
this parameter by cross-validation, we then retrained each SVM using all the training examples.
For reference, we also report the best results obtained previously from three-layer deep belief nets
(DBN-3) and SVMs with RBF kernels (SVM-RBF). These references appear to be representative of
the current state-of-the-art for deep and shallow architectures on these data sets.
Figures 2 and 3 show the test set error rates from arc-cosine kernels of varying degree (n) and levels
of recursion (l). We experimented with kernels of degree n = 0, 1 and 2, corresponding to thresh-
old networks with “step”, “ramp”, and “quarter-pipe” activation functions. We also experimented
with the multilayer kernels described in section 2.3, composed from one to six levels of recursion.
Overall, the figures show that many SVMs with arc-cosine kernels outperform traditional SVMs,
and a certain number also outperform deep belief nets. In addition to their solid performance, we
note that SVMs with arc-cosine kernels are very straightforward to train; unlike SVMs with RBF
kernels, they do not require tuning a kernel width parameter, and unlike deep belief nets, they do not
require solving a difficult nonlinear optimization or searching over possible architectures.
Our experiments with multilayer kernels revealed that these SVMs only performed well when arc-
cosine kernels of degree n = 1 were used at higher (l > 1) levels in the recursion. Figs. 2 and
3 therefore show only these sets of results; in particular, each group of bars shows the test error
rates when a particular kernel (of degree n = 0,1,2) was used at the first layer of nonlinearity,
while the n = 1 kernel was used at successive layers. We hypothesize that only n = 1 arc-cosine
kernels preserve sufficient information about the magnitude of their inputs to work effectively in
composition with other kernels. Recall that only the n = 1 arc-cosine kernel preserves the norm of
its inputs: the n = 0 kernel maps all inputs onto a unit hypersphere in feature space, while higher-
order (n> 1) kernels induce feature spaces with different dynamic ranges.
Finally, the results on both data sets reveal an interesting trend: the multilayer arc-cosine kernels
often perform better than their single-layer counterparts. Though SVMs are (inherently) shallow
architectures, this trend suggests that for these problems in binary classification, arc-cosine kernels
may be yielding some of the advantages typically associated with deep architectures.
3 Deep learning
In this section, we explore how to use kernel methods in deep architectures [7]. We show how to train
deep kernel-based architectures by a simple combination of supervised and unsupervised methods.
Using the arc-cosine kernels in the previous section, these multilayer kernel machines (MKMs)
perform very competitively on multiclass data sets designed to foil shallow architectures [11].
5/n Just need report on the paper in word doc not in pdf
Report should follow the instruction mentioned in the file. Like the format.
APA
3 PAGES
Need CITATION and Reference also
No code
