nips nips2008 nips2008-56 knowledge-graph by maker-knowledge-mining

56 nips-2008-Deep Learning with Kernel Regularization for Visual Recognition

Source: pdf

Author: Kai Yu, Wei Xu, Yihong Gong

Abstract: In this paper we aim to train deep neural networks for rapid visual recognition. The task is highly challenging, largely due to the lack of a meaningful regularizer on the functions realized by the networks. We propose a novel regularization method that takes advantage of kernel methods, where an oracle kernel function represents prior knowledge about the recognition task of interest. We derive an efﬁcient algorithm using stochastic gradient descent, and demonstrate encouraging results on a wide range of recognition tasks, in terms of both accuracy and speed. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract In this paper we aim to train deep neural networks for rapid visual recognition. [sent-3, score-0.569]

2 We propose a novel regularization method that takes advantage of kernel methods, where an oracle kernel function represents prior knowledge about the recognition task of interest. [sent-5, score-0.783]

3 We derive an efﬁcient algorithm using stochastic gradient descent, and demonstrate encouraging results on a wide range of recognition tasks, in terms of both accuracy and speed. [sent-6, score-0.376]

4 1 Introduction Visual recognition remains a challenging task for machines. [sent-7, score-0.236]

5 This difﬁculty stems from the large pattern variations under which a recognition system must operate. [sent-8, score-0.236]

6 The task is extremely easy for a human, largely due to the expressive deep architecture employed by human visual cortex systems. [sent-9, score-0.56]

7 Deep neural networks (DNNs) are argued to have a greater capacity to recognize a larger variety of visual patterns than shallow models, because they are considered biologically plausible. [sent-10, score-0.168]

8 However, training deep architectures is difﬁcult because the large number of parameters to be tuned necessitates an enormous amount of labeled training data that is often unavailable. [sent-11, score-0.548]

9 Several authors have recently proposed training methods by using unlabeled data. [sent-12, score-0.157]

10 These methods perform a greedy layer-wise pre-training using unlabeled data, followed by a supervised ﬁne-tuning [9, 4, 15]. [sent-13, score-0.132]

11 Even though the strategy notably improves the performance, to date, the best reported recognition accuracy on popular benchmarks such as Caltech101 by deep models is still largely behind the results of shallow models. [sent-14, score-0.717]

12 Beside using unlabeled data, in this paper we tackle the problem by leveraging additional prior knowledge. [sent-15, score-0.171]

13 In the last few decades, researchers have developed successful kernel-based systems for a wide range of visual recognition tasks. [sent-16, score-0.338]

14 Those sensibly-designed kernel functions provide an extremely valuable source of prior knowledge, which we believe should be exploited in deep learning. [sent-17, score-0.588]

15 In this paper, we propose an informative kernel-based regularizer, which makes it possible to train DNNs with prior knowledge about the recognition task. [sent-18, score-0.377]

16 Computationally, we propose to solve the learning problem using stochastic gradient descent (SGD), as it is the de facto method for neural network training. [sent-19, score-0.206]

17 To this end we transform the kernel regularizer into a loss function represented as a sum of costs by individual examples. [sent-20, score-0.304]

18 This results in a simple multi-task architecture where a number of extra nodes at the output layer are added to ﬁt a set of auxiliary functions automatically constructed from the kernel function. [sent-21, score-0.388]

19 We apply the described method to train convolutional neural networks (CNNs) for a wide range of visual recognition tasks, including handwritten digit recognition, gender classiﬁcation, ethnic origin recognition, and object recognition. [sent-22, score-0.79]

20 Our results show that incorporation of prior knowledge can boost the performance of CNNs by a large margin when the training set is small or the learning problem is difﬁcult. [sent-24, score-0.17]

21 1 2 DNNs with Kernel Regularization In our setting, the learning model, a deep neural network (DNN), aims to learn a predictive function f : X → R that can achieve a low expected discrepancy E[ (y, f (x))] over the distribution p(x, y). [sent-25, score-0.369]

22 We exploit this prior knowledge via imposing a kernel regularization on K(θ) = [Ki,j ]m , such i,j=1 that the learning problem seeks Problem 2. [sent-29, score-0.366]

23 min L(β, θ) + γΩ(θ) (3) Ω(θ) = tr K(θ)−1 Σ + log det[K(θ)] (4) β,θ where γ > 0 and Ω(θ) is deﬁned by This is a case of semi-supervised learning if m > n. [sent-31, score-0.168]

24 The regularization can be explained from an information-theoretic perspective. [sent-36, score-0.113]

25 We note that the regularization does not require Σ to be positive deﬁnite — it can be semideﬁnite. [sent-40, score-0.113]

26 In this paper we emphasize large-scale optimizations using stochastic gradient descent (SGD), because the method is fast when the size m of total data is large and backpropagation, a typical SGD, has been the de facto method to train neural networks for large-scale learning tasks. [sent-43, score-0.354]

27 A standard batch gradient descent updates the model parameters by using the true gradient summed over the whole training set, while SGD approximates the true gradient by the gradient caused by a single random training example. [sent-45, score-0.543]

28 2 From a Gaussian process point of view, a kernel function deﬁnes the prior distribution of a function f , such that the marginal distribution of the function values f on any ﬁnite set of inputs is a multivariate Gaussian. [sent-50, score-0.219]

29 1 Shrinkage on the Kernel Matrix We consider a large-scale problem where the data size m may grow over time, while the size of the last hidden layer (q) of the DNN is ﬁxed. [sent-57, score-0.181]

30 Therefore the computed kernel K can be rank deﬁcient. [sent-58, score-0.181]

31 Thus the log-determinant acts on a much smaller q ×q matrix3 log det(K + δI) = log det Φ Φ + δI + const where Φ = [φ1 , . [sent-60, score-0.33]

32 Omitting all the irrelevant constants, we then turn the kernel regularization into Ω(θ) = tr (ΦΦ + δI)−1 Σ + log det(Φ Φ + δI) (5) The kernel shrinkage not only remedies the ill-posedness, but also yields other conveniences in our later development. [sent-64, score-0.68]

33 For a concave function g(a), the conjugate function of its conjugate function is itself, i. [sent-76, score-0.14]

34 Since log-determinant is concave for q × q positive deﬁnite matrices A, the conjugate function of log det(A) is log det(Ψ) + q. [sent-90, score-0.181]

35 (5) is turned into a variational representation m φi Ψφi + δ · tr(Ψ) − log det(Ψ) + const log det Φ Φ + δI = min + Ψ∈Sq i=1 where Ψ ∈ S+ is a q × q positive deﬁnite matrix, and const = −q. [sent-93, score-0.525]

36 As we can see, the upper bound q is a convex function of auxiliary variables Ψ and more importantly, it amounts to a sum of local quantities caused by each of the m data examples. [sent-94, score-0.187]

37 3 Transformation of the Trace Term We assume that the kernel matrix Σ is presented in a decomposed form Σ = U U , with U = [u1 , . [sent-98, score-0.215]

38 We have found that the trace term can be cast as a variational problem by introducing an q × p auxiliary variable matrix η. [sent-102, score-0.207]

39 (5) is equivalent to a convex variational representation m tr (ΦΦ + δI)−1 Σ = min η∈Rq×p i=1 1 √ ui − η φi δ 2 +δ η 2 F 1 Proof. [sent-106, score-0.291]

40 Then, plugging it back into the function, we have 1 1 1 U U − 2 √ U Φη ∗ + η ∗ Φ Φη ∗ + U Φ(Φ Φ + δI)−2 Φ U δ δ δ 1 = tr U U − U Φ(Φ Φ + δI)−1 Φ U = tr (ΦΦ + δI)−1 U U δ where the last step is derived by applying the Woodbury matrix identity. [sent-108, score-0.208]

41 tr Again, we note that the upper bound is a convex function of η, and consists of a sum of local costs over data examples. [sent-109, score-0.18]

42 4 An Equivalent Learning Framework Combining the previous results, we obtain the convex upper bound for the kernel regularization Eq. [sent-111, score-0.342]

43 (5), which amounts to a sum of costs over examples under some regularization m 1 √ ui − η φi δ Ω(θ) ≤ L(η, Ψ, θ) = i=1 2 + φi Ψφi +δ η 2 F + δ · tr(Ψ) − log det(Ψ) where we omit all the terms irrelevant to η, Ψ and θ. [sent-112, score-0.364]

44 (5) is equivalent to the convex variational problem m Ω(θ) = min η,ψ i=1 1 √ ui − η φi δ q 2 + ψ φ2 i +δ η 2 F +δ·ψ e− log ψk (8) k=1 where ψ = [ψ1 , . [sent-125, score-0.247]

45 min β,η,ψ,θ L(β, η, ψ, θ) = 1 γ γ L1 (β, θ) + L2 (η, θ) + L3 (ψ, θ) n mn mn (9) where L1 (β, θ) is deﬁned by Eq. [sent-146, score-0.094]

46 (1), and m L2 (η, θ) = i=1 m 1 √ ui − η φi δ 2 +δ η q ψ φ2 + δ · ψ e − i L3 (ψ, θ) = 2 F i=1 log ψk k=1 To ensure the estimator of β and θ is consistent, the effect of regularization should vanish as n → ∞. [sent-147, score-0.219]

47 Since each of the loss functions amounts to a summation of local costs caused by individual data examples, the whole learning problem can be conveniently implemented by SGD, as described in Algorithm 1. [sent-150, score-0.198]

48 the self-taught learning [14] based on sparse coding), applied on a large set of unlabeled data; (iii) If a nonlinear kernel function is available, U can be obtained by applying incomplete Cholesky decomposition on an m × m kernel matrix Σ. [sent-153, score-0.573]

49 In the third case, when m is so large that the matrix decomposition cannot be computed in the main memory, we apply the Nystr¨ m method [19]: We ﬁrst randomly sample m1 examples p < m1 < m, o such that the computed kernel matrix Σ1 can be decomposed in the memory. [sent-154, score-0.327]

50 Let V DV be the prank eigenvalue decomposition of Σ1 , then the p-rank decomposition of Σ can be approximated by 1 Σ ≈ U U , U = Σ:,1 V D− 2 , where Σ:,1 is the m × m1 kernel matrix between all the m examples and the subset of size m1 . [sent-155, score-0.382]

51 In each of these tasks, we choose a kernel function that has been reported to have state-of-the-art or otherwise good performances in the literature. [sent-157, score-0.181]

52 We will see whether a kernel-regularizer can improve the recognition accuracy of the deep models, and how it is compared with the support vector machine (SVM) using the exactly the same kernel. [sent-158, score-0.641]

53 5 Table 1: Percentage error rates of handwritten digit recognition on MNIST Training Size 100 600 1000 3000 60000 SVM (RBF) 22. [sent-159, score-0.331]

54 07 − Throughout all the experiments, “kCNN” denotes CNNs regularized by nonlinear kernels, processed by either Cholesky or Nystr¨ m approximation, with parameters p = 600, m1 = 5000, and m the o size of each whole data set. [sent-208, score-0.182]

55 The remaining two hyperparameters are: the learning rates = {10−3 , 10−4 , 10−5 } and the kernel regularization weights γ = {102 , 103 , 104 , 105 }. [sent-211, score-0.294]

56 Their values are set once for each of the 4 recognition tasks based on a 5-fold cross validation using 500 labeled examples. [sent-212, score-0.33]

57 1 Handwritten Digit Recognition on MNIST Dataset The data contains a training set with 60000 examples and a test set with 10000 examples. [sent-214, score-0.108]

58 The CNN employs 50 ﬁlters of size 7 × 7 on 34 × 34 input images, followed by down-sampling by 1/2, then 128 ﬁlters of size 5 × 5, followed by down-sampling by 1/2, and then 200 ﬁlters of size 5 × 5, giving rise to 200 dimensional features that are fed to the output layer. [sent-215, score-0.238]

59 Two nonlinear kernels are used: (1) RBF kernel, and (2) Graph kernel on 10 nearest neighbor graph [6]. [sent-216, score-0.319]

60 We perform 600-dimension Cholesky decomposition on the whole 70000 × 70000 graph kernel because it is very sparse. [sent-217, score-0.305]

61 In addition to using the whole training set, we train the models on 100, 600, 1000 and 3000 random examples from the training set and evaluate the classiﬁers on the whole test set, and repeat each setting by 5 times independently. [sent-218, score-0.35]

62 0 dataset [13] contains 568 individuals’ 14714 face images under various lighting conditions and backgrounds. [sent-225, score-0.133]

63 Beside person identities, each image is annotated with gender and ethnicity, which we put into 3 classes, “white”, “asian”, and “other”. [sent-226, score-0.153]

64 We ﬁx 114 persons’ 3014 images (randomly chosen) as the testing set, and randomly selected 5%, 10%, 20%, 50%, and “All” images from the rest 454 individuals’ 11700 images. [sent-227, score-0.132]

65 For each training size, we randomize the training data 5 times and report the average error rates. [sent-228, score-0.138]

66 In this experiment, CNNs operate on images represented by R/G/B planes plus horizontal and vertical gradient maps of gray intensities. [sent-229, score-0.179]

67 The 5 input planes of size 140 × 140 are processed by 16 convolution ﬁlters with size 16 × 16, followed by max pooling within each disjoint 5 × 5 neighborhood. [sent-230, score-0.254]

68 The obtained 16 feature maps of size 25 × 25 are connected to the next layer by 256 ﬁlters of size 6 × 6, with 50% random sparse connections, followed by max pooling within each 5 × 5 neighborhood. [sent-231, score-0.257]

69 The nonlinear kernel used in this experiment is the RBF kernel computed directly on images, which has demonstrated state-of-the-art accuracy for gender recognition [3]. [sent-233, score-0.837]

70 3 demonstrate that kCNNs signiﬁcantly boost the recognition accuracy of CNNs for both gender and ethnicity recognition. [sent-236, score-0.59]

71 3 Object Recognition on Caltech101 Dataset Caltech101 [7] contains 9144 images from 101 object categories and a background category. [sent-239, score-0.133]

72 It is considered one of the most diverse object databases available today, and is probably the most popular benchmark for object recognition. [sent-240, score-0.134]

73 We follow the common setting to train on 15 and 30 images per class and test on the rest. [sent-241, score-0.135]

74 The 6 Table 2: Percentage error rates of gender recognition on FRGC Training Size 5% 10% 20% 50% All SVM (RBF) 16. [sent-243, score-0.389]

75 4 Table 3: Percentage error rates of ethnicity recognition on FRGC Training Size 5% 10% 20% 50% All SVM (RBF) 22. [sent-263, score-0.372]

76 8 recognition accuracy was normalized by class sizes and evaluated over 5 random data splits. [sent-283, score-0.272]

77 The nonlinear kernel is the spatial pyramid matching (SPM) kernel developed in [10]. [sent-285, score-0.447]

78 4 shows our results together with those reported in [12, 15] using deep hierarchical architectures. [sent-287, score-0.369]

79 The task is much more challenging than the previous three tasks for CNNs, because in each category the data size is very small while the visual patterns are highly diverse. [sent-288, score-0.205]

80 Thanks to the regularization by SPM kernel, kCNN dramatically improves the accuracy of CNN, and outperforms SVM using the same kernel. [sent-289, score-0.149]

81 This is perhaps the best performance by (trainable and hand-crafted) deep hierarchical models on the Caltech101 dataset. [sent-290, score-0.369]

82 Some ﬁlters trained with and without kernel regularization are visualized in Fig. [sent-291, score-0.294]

83 5 Related Work, Discussion, and Conclusion Recent work on deep visual recognition models includes [17, 12, 15]. [sent-293, score-0.707]

84 In [17] and [12] the ﬁrst layer consisted of hard-wired Gabor ﬁlters, and then a large number of patches were sampled from the second layer and used as the basis of the representation which was then used to train a discriminative classiﬁer. [sent-294, score-0.231]

85 Hinton and his coworkers proposed training deep belief networks with layer-wise unsupervised pre-training, followed by supervised ﬁne-tuning [9]. [sent-296, score-0.544]

86 The strategy was subsequently studied for other deep models like CNNs [15], autoassociators [4], and for document coding [16]. [sent-297, score-0.398]

87 In recent work [18], the authors proposed training a deep model jointly with an unsupervised embedding task, which led to improved results as well. [sent-298, score-0.471]

88 Though using unlabeled data too, our work differs from previous work at the emphasis on leveraging the prior knowledge, which suggests that it can be combined with those approaches, including neighborhood component analysis [8], to further enhance the deep learning. [sent-299, score-0.54]

89 This work is also related to transfer learning [2] that used auxiliary learning tasks to learn a linear feature mapping, and more directly, our previous work [1], which created pseudo auxiliary tasks based on hand-craft image features to train nonlinear deep networks. [sent-300, score-0.811]

90 The reason is computational speed – kCNN pays an extra cost to exploit a kernel matrix in the training phase, but in the prediction phase the system uses CNN alone. [sent-302, score-0.284]

91 We conjecture that kCNN could be further improved by using multiple kernels without sacriﬁcing recognition speed. [sent-317, score-0.291]

92 To conclude, we proposed using kernels to improve the training of deep models. [sent-318, score-0.493]

93 The approach was implemented by stochastic gradient descent, and demonstrated excellent performances on a range of visual recognition tasks. [sent-319, score-0.47]

94 Our experiments showed that prior knowledge could signiﬁcantly improve the performance of deep models when insufﬁcient labeled data were available in hard recognition problems. [sent-320, score-0.718]

95 The trained model was much faster than kernel systems for making predictions. [sent-321, score-0.181]

96 Training hierarchical feed-forward visual recognition models using transfer learning from pseudo tasks. [sent-330, score-0.403]

97 A framework for learning predictive structures from multiple tasks and unlabeled data. [sent-336, score-0.141]

98 Learning generative visual models from few training examples: An incremental Bayesian approach tested on 101 object categories. [sent-367, score-0.238]

99 Semi-supervised learning of compact document representations with deep networks. [sent-434, score-0.398]

100 Using the Nystr¨ m method to speed up kernel machines. [sent-451, score-0.181]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('deep', 0.369), ('cnn', 0.333), ('kcnn', 0.299), ('cnns', 0.245), ('recognition', 0.236), ('sgd', 0.204), ('kernel', 0.181), ('gender', 0.153), ('frgc', 0.143), ('det', 0.142), ('ethnicity', 0.136), ('spm', 0.136), ('nystr', 0.129), ('rbf', 0.119), ('regularization', 0.113), ('svm', 0.111), ('const', 0.102), ('visual', 0.102), ('lters', 0.098), ('unlabeled', 0.088), ('tr', 0.087), ('dnns', 0.082), ('layer', 0.081), ('auxiliary', 0.076), ('train', 0.069), ('training', 0.069), ('cholesky', 0.068), ('object', 0.067), ('images', 0.066), ('gradient', 0.065), ('ui', 0.063), ('descent', 0.058), ('variational', 0.055), ('kernels', 0.055), ('dnn', 0.054), ('kcnns', 0.054), ('digit', 0.054), ('tasks', 0.053), ('whole', 0.052), ('nonlinear', 0.05), ('architecture', 0.05), ('concave', 0.05), ('size', 0.05), ('convex', 0.048), ('planes', 0.048), ('pretrain', 0.048), ('percentage', 0.046), ('costs', 0.045), ('mnist', 0.045), ('leveraging', 0.045), ('conjugate', 0.045), ('followed', 0.044), ('facto', 0.044), ('gong', 0.044), ('ranzato', 0.044), ('log', 0.043), ('trace', 0.042), ('vision', 0.042), ('shrinkage', 0.042), ('labeled', 0.041), ('beside', 0.041), ('hinton', 0.041), ('handwritten', 0.041), ('regularizer', 0.04), ('stochastic', 0.039), ('minimizing', 0.039), ('largely', 0.039), ('decomposition', 0.039), ('examples', 0.039), ('convolutional', 0.039), ('loss', 0.038), ('min', 0.038), ('prior', 0.038), ('face', 0.037), ('abuse', 0.037), ('shallow', 0.037), ('accuracy', 0.036), ('caused', 0.035), ('pyramid', 0.035), ('transformation', 0.035), ('conference', 0.034), ('knowledge', 0.034), ('matrix', 0.034), ('transfer', 0.033), ('graph', 0.033), ('unsupervised', 0.033), ('irrelevant', 0.033), ('pseudo', 0.032), ('pooling', 0.032), ('bengio', 0.031), ('dataset', 0.03), ('processed', 0.03), ('weston', 0.03), ('individuals', 0.03), ('document', 0.029), ('boost', 0.029), ('networks', 0.029), ('mn', 0.028), ('amounts', 0.028), ('excellent', 0.028)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 56 nips-2008-Deep Learning with Kernel Regularization for Visual Recognition

Author: Kai Yu, Wei Xu, Yihong Gong

2 0.17075519 62 nips-2008-Differentiable Sparse Coding

Author: J. A. Bagnell, David M. Bradley

Abstract: Prior work has shown that features which appear to be biologically plausible as well as empirically useful can be found by sparse coding with a prior such as a laplacian (L1 ) that promotes sparsity. We show how smoother priors can preserve the beneﬁts of these sparse priors while adding stability to the Maximum A-Posteriori (MAP) estimate that makes it more useful for prediction problems. Additionally, we show how to calculate the derivative of the MAP estimate efﬁciently with implicit differentiation. One prior that can be differentiated this way is KL-regularization. We demonstrate its effectiveness on a wide variety of applications, and ﬁnd that online optimization of the parameters of the KL-regularized model can signiﬁcantly improve prediction performance. 1

3 0.1384861 63 nips-2008-Dimensionality Reduction for Data in Multiple Feature Representations

Author: Yen-yu Lin, Tyng-luh Liu, Chiou-shann Fuh

Abstract: In solving complex visual learning tasks, adopting multiple descriptors to more precisely characterize the data has been a feasible way for improving performance. These representations are typically high dimensional and assume diverse forms. Thus ﬁnding a way to transform them into a uniﬁed space of lower dimension generally facilitates the underlying tasks, such as object recognition or clustering. We describe an approach that incorporates multiple kernel learning with dimensionality reduction (MKL-DR). While the proposed framework is ﬂexible in simultaneously tackling data in various feature representations, the formulation itself is general in that it is established upon graph embedding. It follows that any dimensionality reduction techniques explainable by graph embedding can be generalized by our method to consider data in multiple feature representations.

4 0.1324098 79 nips-2008-Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

Author: Francis R. Bach

Abstract: For supervised and unsupervised learning, positive deﬁnite kernels allow to use large and potentially inﬁnite dimensional feature spaces with a computational cost that only depends on the number of observations. This is usually done through the penalization of predictor functions by Euclidean or Hilbertian norms. In this paper, we explore penalizing by sparsity-inducing norms such as the ℓ1 -norm or the block ℓ1 -norm. We assume that the kernel decomposes into a large sum of individual basis kernels which can be embedded in a directed acyclic graph; we show that it is then possible to perform kernel selection through a hierarchical multiple kernel learning framework, in polynomial time in the number of selected kernels. This framework is naturally applied to non linear variable selection; our extensive simulations on synthetic datasets and datasets from the UCI repository show that efﬁciently exploring the large feature space through sparsity-inducing norms leads to state-of-the-art predictive performance.

5 0.1116423 148 nips-2008-Natural Image Denoising with Convolutional Networks

Author: Viren Jain, Sebastian Seung

Abstract: We present an approach to low-level vision that combines two main ideas: the use of convolutional networks as an image processing architecture and an unsupervised learning procedure that synthesizes training samples from speciﬁc noise models. We demonstrate this approach on the challenging problem of natural image denoising. Using a test set with a hundred natural images, we ﬁnd that convolutional networks provide comparable and in some cases superior performance to state of the art wavelet and Markov random ﬁeld (MRF) methods. Moreover, we ﬁnd that a convolutional network offers similar performance in the blind denoising setting as compared to other techniques in the non-blind setting. We also show how convolutional networks are mathematically related to MRF approaches by presenting a mean ﬁeld theory for an MRF specially designed for image denoising. Although these approaches are related, convolutional networks avoid computational difﬁculties in MRF approaches that arise from probabilistic learning and inference. This makes it possible to learn image processing architectures that have a high degree of representational power (we train models with over 15,000 parameters), but whose computational expense is signiﬁcantly less than that associated with inference in MRF approaches with even hundreds of parameters. 1 Background Low-level image processing tasks include edge detection, interpolation, and deconvolution. These tasks are useful both in themselves, and as a front-end for high-level visual tasks like object recognition. This paper focuses on the task of denoising, deﬁned as the recovery of an underlying image from an observation that has been subjected to Gaussian noise. One approach to image denoising is to transform an image from pixel intensities into another representation where statistical regularities are more easily captured. For example, the Gaussian scale mixture (GSM) model introduced by Portilla and colleagues is based on a multiscale wavelet decomposition that provides an effective description of local image statistics [1, 2]. Another approach is to try and capture statistical regularities of pixel intensities directly using Markov random ﬁelds (MRFs) to deﬁne a prior over the image space. Initial work used handdesigned settings of the parameters, but recently there has been increasing success in learning the parameters of such models from databases of natural images [3, 4, 5, 6, 7, 8]. Prior models can be used for tasks such as image denoising by augmenting the prior with a noise model. Alternatively, an MRF can be used to model the probability distribution of the clean image conditioned on the noisy image. This conditional random ﬁeld (CRF) approach is said to be discriminative, in contrast to the generative MRF approach. Several researchers have shown that the CRF approach can outperform generative learning on various image restoration and labeling tasks [9, 10]. CRFs have recently been applied to the problem of image denoising as well [5]. 1 The present work is most closely related to the CRF approach. Indeed, certain special cases of convolutional networks can be seen as performing maximum likelihood inference on a CRF [11]. The advantage of the convolutional network approach is that it avoids a general difﬁculty with applying MRF-based methods to image analysis: the computational expense associated with both parameter estimation and inference in probabilistic models. For example, naive methods of learning MRFbased models involve calculation of the partition function, a normalization factor that is generally intractable for realistic models and image dimensions. As a result, a great deal of research has been devoted to approximate MRF learning and inference techniques that meliorate computational difﬁculties, generally at the cost of either representational power or theoretical guarantees [12, 13]. Convolutional networks largely avoid these difﬁculties by posing the computational task within the statistical framework of regression rather than density estimation. Regression is a more tractable computation and therefore permits models with greater representational power than methods based on density estimation. This claim will be argued for with empirical results on the denoising problem, as well as mathematical connections between MRF and convolutional network approaches. 2 Convolutional Networks Convolutional networks have been extensively applied to visual object recognition using architectures that accept an image as input and, through alternating layers of convolution and subsampling, produce one or more output values that are thresholded to yield binary predictions regarding object identity [14, 15]. In contrast, we study networks that accept an image as input and produce an entire image as output. Previous work has used such architectures to produce images with binary targets in image restoration problems for specialized microscopy data [11, 16]. Here we show that similar architectures can also be used to produce images with the analog ﬂuctuations found in the intensity distributions of natural images. Network Dynamics and Architecture A convolutional network is an alternating sequence of linear ﬁltering and nonlinear transformation operations. The input and output layers include one or more images, while intermediate layers contain “hidden

6 0.1077394 118 nips-2008-Learning Transformational Invariants from Natural Movies

7 0.099155545 80 nips-2008-Extended Grassmann Kernels for Subspace-Based Learning

8 0.09724503 143 nips-2008-Multi-label Multiple Kernel Learning

9 0.097082771 226 nips-2008-Supervised Dictionary Learning

10 0.09425234 196 nips-2008-Relative Margin Machines

11 0.09232638 241 nips-2008-Transfer Learning by Distribution Matching for Targeted Advertising

12 0.092308208 194 nips-2008-Regularized Learning with Networks of Features

13 0.091500856 142 nips-2008-Multi-Level Active Prediction of Useful Image Annotations for Recognition

14 0.090480916 77 nips-2008-Evaluating probabilities under high-dimensional latent variable models

15 0.088514514 214 nips-2008-Sparse Online Learning via Truncated Gradient

16 0.087389477 205 nips-2008-Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization

17 0.084077597 145 nips-2008-Multi-stage Convex Relaxation for Learning with Sparse Regularization

18 0.084056079 113 nips-2008-Kernelized Sorting

19 0.083358712 120 nips-2008-Learning the Semantic Correlation: An Alternative Way to Gain from Unlabeled Text

20 0.082164444 3 nips-2008-A Massively Parallel Digital Learning Processor

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.256), (1, -0.126), (2, -0.009), (3, -0.02), (4, 0.037), (5, 0.032), (6, -0.057), (7, -0.05), (8, -0.041), (9, 0.025), (10, 0.2), (11, -0.022), (12, -0.087), (13, 0.022), (14, 0.013), (15, -0.137), (16, -0.003), (17, -0.083), (18, -0.05), (19, 0.044), (20, -0.1), (21, -0.026), (22, 0.007), (23, -0.037), (24, -0.048), (25, 0.018), (26, 0.016), (27, -0.024), (28, -0.021), (29, -0.038), (30, -0.054), (31, 0.059), (32, -0.102), (33, 0.027), (34, -0.024), (35, 0.097), (36, -0.023), (37, 0.015), (38, 0.146), (39, 0.011), (40, 0.026), (41, 0.045), (42, 0.008), (43, -0.021), (44, -0.127), (45, 0.048), (46, 0.035), (47, 0.066), (48, 0.022), (49, -0.045)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95021737 56 nips-2008-Deep Learning with Kernel Regularization for Visual Recognition

Author: Kai Yu, Wei Xu, Yihong Gong

2 0.69564337 63 nips-2008-Dimensionality Reduction for Data in Multiple Feature Representations

Author: Yen-yu Lin, Tyng-luh Liu, Chiou-shann Fuh

3 0.68294573 3 nips-2008-A Massively Parallel Digital Learning Processor

Author: Hans P. Graf, Srihari Cadambi, Venkata Jakkula, Murugan Sankaradass, Eric Cosatto, Srimat Chakradhar, Igor Dourdanovic

Abstract: We present a new, massively parallel architecture for accelerating machine learning algorithms, based on arrays of vector processing elements (VPEs) with variable-resolution arithmetic. Groups of VPEs operate in SIMD (single instruction multiple data) mode, and each group is connected to an independent memory bank. The memory bandwidth thus scales with the number of VPEs, while the main data flows are local, keeping power dissipation low. With 256 VPEs, implemented on two FPGAs (field programmable gate array) chips, we obtain a sustained speed of 19 GMACS (billion multiplyaccumulate per sec.) for SVM training, and 86 GMACS for SVM classification. This performance is more than an order of magnitude higher than that of any FPGA implementation reported so far. The speed on one FPGA is similar to the fastest speeds published on a Graphics Processor for the MNIST problem, despite a clock rate that is an order of magnitude lower. Tests with Convolutional Neural Networks show similar compute performances. This massively parallel architecture is particularly attractive for embedded applications, where low power dissipation is critical. 1 I n trod u cti on Machine learning demands higher and higher compute-performance, but serial processors are not improving that much anymore - at least not as quickly as they used to. Mainstream processor development is moving to multi-core systems, using shared memory technology to hide the parallel nature of the processors. But shared memory technology does not scale to hundreds or thousands of cores. In order to reach such levels of parallelization alternative approaches have to be developed. Massively parallel general-purpose computers had limited success so far, because of difficulties programming these machines, and they remain a niche market, mostly in highperformance computing. Yet processors specialized for certain application domains, such as graphics processors or routing processors 1, have been parallelized to several hundred cores and are successful mass products. They improve performance over general-purpose processors by focusing on a few key algorithmic elements, yet still maintain enough flexibility that they can be programmed for a variety of applications. We explore in this paper if a similar approach can lead to efficient machine learning processors. 1 e.g. Nvidia, Quadro FX 5600 graphics processor; Cisco, CRS-1 routing processor Several processors optimized for machine learning, in particular for neural networks, were developed during the 1980’s and 90’s. Examples are the Synapse-1 architecture [1], or the Connectionist Network Supercomputer, CNS1 [2]. Recently there has been less activity in this field, but some accelerators are sold today for specific applications, such as the Axeon [3] processor for power train control of cars. Beside digital processors a large number of analog circuits were built, emulating neural network structures. Extremely high performance with low power dissipation is achievable, see e.g. [4][5], but these networks have little flexibility. SVM implementations on FPGA have been demonstrated in recent years [6-8], yet reached only low compute-performances. All machine learning processors had only limited success so far, indicating how difficult it is to find a good combination of performance, flexibility, price and ease of use. An important consideration is that many applications of machine learning, such as video analysis, data mining, or personalization of services, show the most promise in embedded systems. Embedded learning requires high compute performance while dissipating little power, a combination that is difficult to achieve, and so far required application specific IC (ASIC). Our aim is to develop architectures that meet the requirements for embedded learning, but are programmable and therefore can be used in a wide range of applications. With the goal of analyzing different architectures we designed a development and testing environment where the parallel computation is mapped onto FPGA’s. Initially this system was intended only for experimentation, but its performance is so high that this platform is useful in its own right as accelerator for high-performance systems. While the experiments shown here emphasize high performance, the architecture has been designed from the start for low power dissipation. The main features for achieving this goal are: low-resolution arithmetic, keeping the main data flow local, low operating frequencies, and a modular design, so that unused parts can be powered down dynamically. All results shown here are from the test platform; migration to lowpower FPGA or chip designs are done in a later stage. 2 Al gori th ms - A ri th meti c - A rch i te ctu re For a substantial improvement over a general purpose processor, the algorithms, the arithmetic units, as well as the architecture have to be optimized simultaneously. This is not just an exercise in hardware design, but algorithms and their software implementations have to be developed concurrently. Most machine learning algorithms have not been developed with parallelization in mind. Therefore, we first need to find good parallel versions, identify their performance bottlenecks, and then extract common computational patterns that can be mapped into accelerator hardware. 2.1 Algorithms Characteristic for machine learning is that large amounts of data need to be processed, often with predictable data access patterns and no dependency between operations over large segments of the computation. This is why data-parallelization can often provide good accelerations on multi-core chips, clusters of machines, or even on loosely coupled networks of machines. Using MapReduce, speedups linear with the number of processors have been reported in [9] for several machine learning algorithms. Up to 16 cores were tested, and simulations indicate good scaling to more processors in some cases. Many algorithms, such as KNN, K-means clustering, LVQ, and Neural Networks can be reduced to forms where the computation is dominated by vector-matrix multiplications, which are easily parallelizable. For Convolutional Neural Networks (CNN) the data flow can be complex, yet the core of the computation is a convolution, an operation which has been studied extensively for parallel implementations. For Support Vector Machines (SVM), several parallel algorithms were described, but most saturate quickly for more than 16 processors. Scaling to larger numbers of processors has been demonstrated, applying MapReduce on a graphics processor with 128 cores [10]. Another implementation on a cluster of 48 dual-core machines (with 384 MMX units) [11] scales even super-linearly, and, according to simulations, scales to thousands of cores. Based on this analysis it is clear that vector-matrix and matrix-matrix multiplications for large vector dimensionalities and large numbers of vectors must be handled efficiently. Yet this alone is not sufficient since data access patterns vary greatly between algorithms. We analyze this here in more detail for SVM and CNN. These algorithms were chosen, because they are widely used for industrial applications and cover a broad range of computation, I/O, and memory requirements. The characteristics of the SVM training are summarized in Table 1. We use an approach similar to the one described in [11] to split different parts of the computation between a host CPU and the FPGA accelerator. For large dimensions d of the vectors the calculation of the columns of the kernel matrix dominates by far. This is needed to update the gradients, and in the present implementation, only this part is mapped onto the FPGA. If the dimensionality d is smaller than around 100, operations 2 and 5 can become bottlenecks and should also be mapped onto the accelerator. Challenging is that for each kernel computation a new data vector has to be loaded 4 into the processor, leading to very high I/O requirements. We consider here dimensions of 10 - 10 5 7 and numbers of training data of 10 - 10 , resulting easily in Gigabytes that need to be transferred to the processors at each iteration. 1 2 3 4 5 6 Operation Initialize all αx, Gx Do Find working set αi, αj Update αi, αj Get 2 columns of kernel matrix Update gradients Gx While not converged Computation 2n IO 2n Unit CPU I I I I I * 2n I*2 I * (2d+2dn) I*n CPU CPU FPGA CPU * * * * 2n 10 2nd n Table 1: Compute- and IO-requirements of each step for SVM training (SMO algorithm). n: number of training data; d: dimension of the vectors; G: gradients; α: support vector factors; I: number of iterations. The last column indicates whether the execution happens on the host CPU or the accelerator FPGA. It is assumed that the kernel computation requires a dot product between vectors (e.g. rbf, polynomial, tanh kernels). Neural network algorithms are essentially sequences of vector-matrix multiplications, but networks with special connectivity patterns, such as convolutional networks have very different IO characteristics than fully connected networks. Table 2 shows the computation and IO requirements for scanning several convolution kernels over one input plane. A full network requires multiple of these operations for one layer, with nonlinearities between layers. We map all operations onto the FPGA accelerator, since intermediate results are re-used right away. The most significant 2 difference to between the SVM and CNN is the Compute/IO ratio: SVM: ~ 1; CNN: ~ L*k > 100. Therefore the requirements for these two algorithms are very different, and handling both cases efficiently is quite a challenge for an architecture design. Operation Load L kernels For all input pixels Shift in new pixel Multiply kernels Shift out result 1 2 3 4 Computation IO 2 L* k n* m 2 n*m*L*k n*m Unit FPGA FPGA FPGA FPGA FPGA Table 2: Compute- and IO-requirements for CNN computation (forward pass), where l kernels of size k*k are scanned simultaneously over an input plane of size n*m. This is representative for implementations with kernel unrolling (kernel pixels processed in parallel). Internal shifts, computation of the non-linearity, and border effects not shown. 2.2 Arithmetic Hardware can be built much more compactly and runs with lower power dissipation, if it uses fixed-point instead of floating-point operations. Fortunately, many learning algorithms tolerate a low resolution in most of the computations. This has been investigated extensively for neural networks [12][13], but less so for other learning algorithms. Learning from data is inherently a noisy process, because we see only a sparse sampling of the true probability distributions. A different type of noise is introduced in gradient descent algorithms, when only a few training data are used at a time to move the optimization forward iteratively. This noise is particularly pronounced for stochastic gradient descent. There is no point in representing noisy variables with high resolution, and it is therefore a property inherent to many algorithms that low-resolution computation can be used. It is important, not to confuse this tolerance to low resolution with the resolution required to avoid numeric instabilities. Some of the computations have to be performed with a high resolution, in particular for variables that are updated incrementally. They maintain the state of the optimization and may change in very small steps. But usually by far the largest part of the computation can be executed at a low resolution. Key is that the hardware is flexible enough and can take advantage of reduced resolution while handling high resolution where necessary. Problem Adult Forest MNIST NORB Kernel: Float Obj. f. # SV 31,930.77 11,486 653,170.7 49,333 4,960.13 6,172 1,243.71 3,077 F-score 77.58 98.29 99.12 93.34 Kernel: 16 bit fixed point Obj. f. # SV F-score 31,930.1 11,490 77.63 652,758 49,299 98.28 4,959.64 6,166 99.11 1,244.76 3,154 93.26 F-sc. (4b in) NA NA 99.11 92.78 Table 3: Comparison of the results of SVM training when the kernels are represented with floating point numbers (32 or 64 bits) (left half) and with 16 bit fixed point (right half). The last column shows the results when the resolution of the training data is reduced from 8 bit to 4 bit. For NORB this reduces the accuracy; all other differences in accuracy are not significant. All are two class problems: Adult: n=32,562, d=122; Forest: n=522,000, d=54 (2 against the rest); MNIST: n=60,000, d=784 (odd–even); NORB: n=48,560, d=5,184. We developed a simulator that allows running the training algorithms with various resolutions in each of the variables. A few examples for SVM training are shown in Table 3. Reducing the resolution of the kernel values from double or float to 16 bit fixed point representations does not affect the accuracy for any of the problems. Therefore all the multiplications in the dot products for the kernel computation can be done in low resolutions (4–16 bit in the factors), but the accumulator needs sufficient resolution to avoid over/under flow (48 bit). Once the calculation of the kernel value is completed, it can be reduced to 16 bit. A low resolution of 16 bit is also tolerable for the α values, but a high resolution is required for the gradients (double). For Neural Networks, including CNN, several studies have confirmed that states and gradients can be kept at low resolutions (<16 bit), but the weights must be maintained at a high resolution (float) (see e.g. [12]). In our own evaluations 24 bits in the weights tend to be sufficient. Once the network is trained, for the classification low resolutions can be used for the weights as well (<16 bit). 2.3 A rc h i t e c t u re Figure 1: Left: Schematic of the architecture with the main data flows; on one FPGA 128 VPE are configured into four SIMD groups; L-S: Load-store units. Right: Picture of an FPGA board; in our experiments one or two of them are used, connected via PCI bus to a host CPU. Based on the analysis above, it is clear that the architecture must be optimized for processing massive amounts of data with relatively low precision. Most of the time, data access patterns are predictable and data are processed in blocks that can be stored contiguously. This type of computation is well suited for vector processing, and simple vector processing elements (VPE) with fixed-point arithmetic can handle the operations. Since typically large blocks of data are processed with the same operation, groups of VPE can work in SIMD (single instruction multiple data) mode. Algorithms must then be segmented to map the highvolume, low precision parts onto the vector accelerators and parts requiring high precision arithmetic onto the CPU. The most important design decision is the organization of the memory. Most memory accesses are done in large blocks, so that the data can be streamed, making complex caching unnecessary. This is fortunate, since the amounts of data to be loaded onto the processor are so large that conventional caching strategies would be overwhelmed anyway. Because the blocks tend to be large, a high data bandwidth is crucial, but latency for starting a block transfer is less critical. Therefore we can use regular DDR memories and still get high IO rates. This led to the design shown schematically in Figure 1, where independent memory banks are connected via separate IO ports for each group of 32 VPE. By connecting multiple of the units shown in Figure 1 to a CPU, this architecture scales to larger numbers of VPE. Parallel data IO and parallel memory access scale simultaneously with the number of parallel cores, and we therefore refer to this as the P3 (P-cube) architecture. Notice also that the main data flow is only local between a group of VPE and its own memory block. Avoiding movements of data over long distances is crucial for low power dissipation. How far this architecture can reasonably scale with one CPU depends on the algorithms, the amount of data and the vector dimensionality (see below). A few hundred VPE per CPU have provided good accelerations in all our tests, and much higher numbers are possible with multi-core CPUs and faster CPU-FPGA connections. 3 I mp l e men tati on of th e P 3 A rch i t ectu re This architecture fits surprisingly well onto some of the recent FPGA chips that are available with several hundred Digital Signal Processors (DSP) units and over 1,000 IO pins for data transfers. The boards used here contain each one Xilinx Virtex 5 LX330T-2 FPGA coupled to 4 independent DDR2 SDRAM with a total of 1GB, and 2 independent 4MB SSRAM memory banks (commercial board from AlphaData). One FPGA chip contains 192 DSP with a maximum speed of 550MHz, which corresponds to a theoretical compute-performance of 105.6 GMACS (18 bit and 25 bit operands). There is a total of 14 Mbit of on-chip memory, and the chip incorporates 960 pins for data IO. Due to routing overhead, not all DSP units can be used and the actual clock frequencies tend to be considerably lower than what is advertised for such chips (typically 230MHz or less for our designs). Nevertheless, we obtain high performances because we can use a large number of DSP units for executing the main computation. The main architecture features are: • Parallel processing (on one chip): 128 VPE (hardware DSP) are divided into 4 blocks of 32, each group controlled by one sequencer with a vector instruction set. • Custom Precision: Data are represented with 1 to 16 bit resolution. Higher resolutions are possible by operating multiple DSP as one processor. • Overlapping Computation and Communication: CPU-FPGA communication is overlapped with the FPGA computation. • Overlap Memory Operations with Computation: All loads and stores from the FPGA to off-chip memory are performed concurrently with computations. • High Off-chip Memory Bandwidth: 6 independent data ports, each 32 bits wide, access banked memories concurrently (12GB/s per chip). • • Streaming Data Flow, Simple Access Patterns: Load/store units are tailored for streaming input and output data, and for simple, bursty access patterns. Caching is done under application control with dual-port memory on chip. Load/store with (de)compression: For an increase of effective IO bandwidth the load/store units provide compression and decompression in hardware. Figure 2 shows the configuration of the VPEs for vector dot product computation used for SVM training and classification. For training, the main computation is the calculation of one column of the kernel matrix. One vector is pre-fetched and stored in on-chip memory. All other vectors are streamed in from off-chip memory banks 1-4. Since this is a regular and predictable access pattern, we can utilize burst-mode, achieving a throughput of close to one memory word per cycle. But the speed is nevertheless IO bound. When several vectors can be stored on-chip, as is the case for classification, then the speed becomes compute-bound. Figure 2: Architecture for vector dot-product computation. The left side shows a high-level schematic with the main data flow. The data are streamed from memory banks 1-4 to the VPE arrays, while memory banks 5 and 6, alternatively receive results or stream them back to the host. The right side shows how a group of VPE is pipelined to improve clock speed. The operation for SVM training on the FPGA corresponds to a vector-matrix multiplication and the one for classification to a matrix-matrix multiplication. Therefore the configuration of Figure 2 is useful for many other algorithms as well, where operations with large vectors and matrices are needed, such as Neural Networks. We implemented a specialized configuration for Convolutional Neural Networks, for more efficiency and lower power dissipation. The VPE are daisy-chained and operate as systolic array. In this way we can take advantage of the high computation to IO ratio (Table 2) to reduce the data transfers from memory. 4 E val u ati on s We evaluated SVM training and classification with the NORB and MNIST problems, the latter with up to 2 million training samples (data from [11]). Both are benchmarks with vectors of high dimensionality, representative for applications in image and video analysis. The computation is split between CPU and FPGA as indicated by Table 1. The DDR2 memory banks are clocked at 230MHz, providing double that rate for data transfers. The data may be compressed to save IO bandwidth. On the FPGA they are decompressed first and distributed to the VPE. In our case, a 32 bit word contains eight 4-bit vector components. Four 32 bit words are needed to feed all 32 VPEs of a group; therefore clocking the VPE faster than 115MHz does not improve performance. A VPE executes a multiplication plus add operation in one clock cycle, resulting in a theoretical maximum of 14.7 GMACS per chip. The sustained compute-rate is lower, about 9.4 GMACS, due to overhead (see Table 4). The computation on the host CPU overlaps with that on the FPGA, and has no effect on the speed in the experiments shown here. For the classification the VPE can be clocked higher, at 230 MHz. By using 4-bit operands we can execute 2 multiply-accumulates simultaneously on one DSP, resulting in speed that is more than four times higher and a sustained 43.0 GMACS limited by the number and speed of the VPE. Adding a second FPGA card doubles the speed, showing little saturation effects yet, but for more FPGA per CPU there will be saturation (see Fig. 3). The compute speed in GMACS obtained for NORB is almost identical. # 60k 2M Iterations 8,000 266,900 CPU time 754s -- speed 0.5 -- CPU+MMX time speed 240 s 1.57 531,534 s 1.58 CPU+FPGA time speed 40 s 9.42 88,589 s 9.48 CPU+2 FPGA time speed 21 s 17.9 48,723 s 17.2 Table 4: Training times and average compute speed for SVM training. Systems tested: CPU, Opteron, 2.2GHz; CPU using MMX; CPU with one FPGA; CPU with two FPGA boards. Results are shown for training sizes of 60k and 2M samples. Compute speed is in GMACS (just kernel computations). Training algorithm: SMO with second order working set selection. Parallelizations of SVM training have been reported recently for a GPU [10] and for a cluster [11], both using the MNIST data. In [10] different bounds for stopping were used than here and in [11]. Nevertheless, a comparison of the compute performance is possible, because based on the number of iterations we can compute the average GMACS for the kernel computations. As can be seen in Table 5 a single FPGA is similar in speed to a GPU with 128 stream processors, despite a clock rate that is about 5.5 times lower for I/O and 11 times lower for the VPE. The cluster with 384 MMX units is about 6 times faster than one FPGA with 128 VPE, but dissipates about two orders of magnitude more electric power. For the FPGA this calculation includes only the computation of the kernel values while the part on the CPU is neglected. This is justified for this study, because the rest of the calculations can be mapped on the FPGA as well and will increase the power dissipation only minimally. Number Clock Operand Power Average of cores speed type dissipation compute speed CPU (Opteron) 1 2.2 GHz float 40 W 0.5 GMACS GPU (from [10]) 128 1.35 GHz float 80 W 7.4 GMACS Cluster (from [11]) 384 1.6 GHz byte > 1 kW 54 GMACS FPGA 128 0.12 GHz 4 bit nibble 9W 9.4 GMACS Table 5: Comparison of performances for SVM training (MNIST data). GPU: Nvidia 8800 GTX. Cluster: 48 dual core CPU (Athlon), 384 MMX units. The GPU was training with 60k samples ([10], table 2, second order), the cluster trained with 2 million samples. Processor Figure 3: Acceleration of SVM training as a function of the number of VPE. MNIST n: 2,000,000, d=784; NORB: n=48,560, d=5,184. The points for 128 and 256 VPE are experimental, the higher ones are simulations. Curves MNIST, NORB: Multiple FPGA are attached to one CPU. Curve MNIST C: Each FPGA is attached to a separate host CPU. Scaling of the acceleration with the number of VPEs is shown in Figure 3. The reference speed is that of one FPGA attached to a CPU. The evaluation has been done experimentally for 128 and 256 VPEs, and beyond that with a simulator. The onset of saturation depends on the dimensionality of the vectors, but to a much lesser extent on the number of training vectors (up to the limit of the memory on the FPGA card). MNIST saturates for more than two FPGAs because then the CPU and FPGA computation times become comparable. For the larger vectors of NORB (d=5,184) this saturation starts to be noticeable for more than 4 FPGA. Alternatively, a system can be scaled by grouping multiple CPU, each with one attached FPGA accelerator. Then the scaling follows a linear or even super-linear acceleration (MNIST C) to several thousand VPE. If the CPUs are working in a cluster arrangement, the scaling is similar to the one described in [11]. For convolutional neural networks, the architecture of Figure 2 is modified to allow a block of VPE to operate as systolic array. In this way convolutions can be implemented with minimal data movements. In addition to the convolution, also sub-sampling and non-linear functions plus the logistics to handle multiple layers with arbitrary numbers of kernels in each layer are done on the FPGA. Four separate blocks of such convolvers are packed onto one FPGA, using 100 VPE. Clocked at 115MHz, this architecture provides a maximum of 11.5 GMACS. Including all the overhead the sustained speed is about 10 GMACS. 5 Con cl u s i on s By systematically exploiting characteristic properties of machine learning algorithms, we developed a new massively parallel processor architecture that is very efficient and can be scaled to thousands of processing elements. The implementation demonstrated here is more than an order of magnitude higher in performance than previous FPGA implementations of SVM or CNN. For the MNIST problem it is comparable to the fastest GPU implementations reported so far. These results underline the importance of flexibility over raw compute-speed for massively parallel systems. The flexibility of the FPGA allows more efficient routing and packing of the data and the use of computations with the lowest resolution an algorithm permits. The results of Table 5 indicate the potential of this architecture for low-power operation in embedded applications. R e f e re n c e s [1] Ramacher, et al. (1995) Synapse-1: A high-speed general purpose parallel neurocomputer system. In Proc. 9th Intl. Symposium on Parallel Processing (IPPS'95), pp. 774-781. [2] Asanovic, K., Beck, Feldman, J., Morgan, N. & Wawrzynek, J. (1994) A Supercomputer for Neural Computation, Proc. IEEE Intl. Joint Conference on Neural Networks, pp. 5-9, Orlando, Florida. [3] Neil, P., (2005) Combining hardware with a powerful automotive MCU for powertrain applications. In Industrial Embedded Resource Guide, p. 88. [4] Korekado, et al. (2003) A Convolutional Neural Network VLSI for Image Recognition Using Merged/Mixed Analog-Digital Architecture, in Proc. 7th KES 2003, Oxford, pp 169-176. [5] Murasaki, M., Arima, Y. & Shinohara, H. (1993) A 20 Tera-CPS Analog Neural Network Board. In Proc. Int. Joint Conf. Neural Networks, pp. 3027 – 3030. [6] Pedersen, R., Schoeberl, M. (2006), An Embedded Support Vector Machine, WISE 2006. [7] Dey, S., Kedia, M. Agarwal, N., Basu, A., Embedded Support Vector Machine: Architectural Enhancements and Evaluation, in Proc 20th Int. Conf. VLSI Design. [8] Anguita, D., Boni, A., Ridella, S., (2003) A Digital Architecture for Support Vector Machines: Theory, Algorithm, and FPGA Implementation, IEEE Trans. Neural Networks, 14/5, pp.993-1009. [9] Chu, C., Kim, S., Lin, Y., Yu, Y., Bradski, G., Ng, A. & Olukotun, K. (2007) Map-Reduce for Machine Learning on Multicore, Advances in Neural Information Processing Systems 19, MIT Press. [10] Catanzaro, B., Sundaram, N., & Keutzer, K. (2008) Fast Support Vector Machine Training and Classification on Graphics Processors, Proc. 25th Int. Conf. Machine Learning, pp 104-111. [11] Durdanovic, I., Cosatto, E. & Graf, H. (2007) Large Scale Parallel SVM Implementation. In L. Bottou, O. Chapelle, D. DeCoste, J. Weston (eds.), Large Scale Kernel Machines, pp. 105-138, MIT Press. [12] Simard, P & Graf, H. (1994) Backpropagation without Multiplication. In J. Cowan, G. Tesauro, J. Alspector, (eds.), Neural Information Processing Systems 6, pp. 232 – 239, Morgan Kaufmann. [13] Savich, A., Moussa, M., Areibi, S., (2007) The Impact of Arithmetic Representation on Implementing MLP-BP on FPGAs: A Study, IEEE Trans. Neural Networks, 18/1, pp. 240-252.

4 0.68033636 62 nips-2008-Differentiable Sparse Coding

Author: J. A. Bagnell, David M. Bradley

5 0.65485549 79 nips-2008-Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

Author: Francis R. Bach

6 0.64284998 80 nips-2008-Extended Grassmann Kernels for Subspace-Based Learning

7 0.61824065 148 nips-2008-Natural Image Denoising with Convolutional Networks

8 0.61744213 68 nips-2008-Efficient Direct Density Ratio Estimation for Non-stationarity Adaptation and Outlier Detection

9 0.60993826 226 nips-2008-Supervised Dictionary Learning

10 0.57728243 203 nips-2008-Scalable Algorithms for String Kernels with Inexact Matching

11 0.55819559 158 nips-2008-Offline Handwriting Recognition with Multidimensional Recurrent Neural Networks

12 0.55712575 196 nips-2008-Relative Margin Machines

13 0.55229473 122 nips-2008-Learning with Consistency between Inductive Functions and Kernels

14 0.53645778 97 nips-2008-Hierarchical Fisher Kernels for Longitudinal Data

15 0.5259456 194 nips-2008-Regularized Learning with Networks of Features

16 0.5014292 225 nips-2008-Supervised Bipartite Graph Inference

17 0.50046283 20 nips-2008-An Extended Level Method for Efficient Multiple Kernel Learning

18 0.49239194 143 nips-2008-Multi-label Multiple Kernel Learning

19 0.48439324 205 nips-2008-Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization

20 0.48415038 66 nips-2008-Dynamic visual attention: searching for coding length increments

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(6, 0.054), (7, 0.547), (28, 0.099), (57, 0.081), (63, 0.025), (77, 0.029), (83, 0.072)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.93865246 109 nips-2008-Interpreting the neural code with Formal Concept Analysis

Author: Dominik Endres, Peter Foldiak

Abstract: We propose a novel application of Formal Concept Analysis (FCA) to neural decoding: instead of just trying to ﬁgure out which stimulus was presented, we demonstrate how to explore the semantic relationships in the neural representation of large sets of stimuli. FCA provides a way of displaying and interpreting such relationships via concept lattices. We explore the effects of neural code sparsity on the lattice. We then analyze neurophysiological data from high-level visual cortical area STSa, using an exact Bayesian approach to construct the formal context needed by FCA. Prominent features of the resulting concept lattices are discussed, including hierarchical face representation and indications for a product-of-experts code in real neurons. 1

2 0.93440628 12 nips-2008-Accelerating Bayesian Inference over Nonlinear Differential Equations with Gaussian Processes

Author: Ben Calderhead, Mark Girolami, Neil D. Lawrence

Abstract: Identiﬁcation and comparison of nonlinear dynamical system models using noisy and sparse experimental data is a vital task in many ﬁelds, however current methods are computationally expensive and prone to error due in part to the nonlinear nature of the likelihood surfaces induced. We present an accelerated sampling procedure which enables Bayesian inference of parameters in nonlinear ordinary and delay differential equations via the novel use of Gaussian processes (GP). Our method involves GP regression over time-series data, and the resulting derivative and time delay estimates make parameter inference possible without solving the dynamical system explicitly, resulting in dramatic savings of computational time. We demonstrate the speed and statistical accuracy of our approach using examples of both ordinary and delay differential equations, and provide a comprehensive comparison with current state of the art methods. 1

same-paper 3 0.93145126 56 nips-2008-Deep Learning with Kernel Regularization for Visual Recognition

Author: Kai Yu, Wei Xu, Yihong Gong

4 0.88181055 51 nips-2008-Convergence and Rate of Convergence of a Manifold-Based Dimension Reduction Algorithm

Author: Andrew Smith, Hongyuan Zha, Xiao-ming Wu

Abstract: We study the convergence and the rate of convergence of a local manifold learning algorithm: LTSA [13]. The main technical tool is the perturbation analysis on the linear invariant subspace that corresponds to the solution of LTSA. We derive a worst-case upper bound of errors for LTSA which naturally leads to a convergence result. We then derive the rate of convergence for LTSA in a special case. 1

5 0.8536517 45 nips-2008-Characterizing neural dependencies with copula models

Author: Pietro Berkes, Frank Wood, Jonathan W. Pillow

Abstract: The coding of information by neural populations depends critically on the statistical dependencies between neuronal responses. However, there is no simple model that can simultaneously account for (1) marginal distributions over single-neuron spike counts that are discrete and non-negative; and (2) joint distributions over the responses of multiple neurons that are often strongly dependent. Here, we show that both marginal and joint properties of neural responses can be captured using copula models. Copulas are joint distributions that allow random variables with arbitrary marginals to be combined while incorporating arbitrary dependencies between them. Different copulas capture different kinds of dependencies, allowing for a richer and more detailed description of dependencies than traditional summary statistics, such as correlation coefﬁcients. We explore a variety of copula models for joint neural response distributions, and derive an efﬁcient maximum likelihood procedure for estimating them. We apply these models to neuronal data collected in macaque pre-motor cortex, and quantify the improvement in coding accuracy afforded by incorporating the dependency structure between pairs of neurons. We ﬁnd that more than one third of neuron pairs shows dependency concentrated in the lower or upper tails for their ﬁring rate distribution. 1

6 0.6601637 71 nips-2008-Efficient Sampling for Gaussian Process Inference using Control Variables

7 0.64668423 137 nips-2008-Modeling Short-term Noise Dependence of Spike Counts in Macaque Prefrontal Cortex

8 0.62458485 213 nips-2008-Sparse Convolved Gaussian Processes for Multi-output Regression

9 0.62313169 221 nips-2008-Stochastic Relational Models for Large-scale Dyadic Data using MCMC

10 0.62173492 188 nips-2008-QUIC-SVD: Fast SVD Using Cosine Trees

11 0.60363138 54 nips-2008-Covariance Estimation for High Dimensional Data Vectors Using the Sparse Matrix Transform

12 0.60102665 60 nips-2008-Designing neurophysiology experiments to optimally constrain receptive field models along parametric submanifolds

13 0.59047079 99 nips-2008-High-dimensional support union recovery in multivariate regression

14 0.58686137 192 nips-2008-Reducing statistical dependencies in natural signals using radial Gaussianization

15 0.58507407 64 nips-2008-DiscLDA: Discriminative Learning for Dimensionality Reduction and Classification

16 0.58366019 248 nips-2008-Using matrices to model symbolic relationship

17 0.58322865 63 nips-2008-Dimensionality Reduction for Data in Multiple Feature Representations

18 0.58026052 62 nips-2008-Differentiable Sparse Coding

19 0.57806295 83 nips-2008-Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method

20 0.57658815 146 nips-2008-Multi-task Gaussian Process Learning of Robot Inverse Dynamics