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

Solved: Kernel Methods for Deep Learning Youngmin Cho and Lawrence K. Saul De

Home
questions and answers
kernel methods for deep learning youngmin cho and lawrence k saul depa

Question

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