Question? Leave a message!

Introduction to Machine Learning

Introduction to Machine Learning 17
Introduction to Machine Learning CMU10701 Deep Learning Barnabás Póczos Aarti Singh Credits Many of the pictures, results, and other materials are taken from: Ruslan Salakhutdinov Joshua Bengio Geoffrey Hinton Yann LeCun 2 Contents  Definition and Motivation  History of Deep architectures  Deep architectures  Convolutional networks  Deep Belief networks  Applications 3 Deep architectures Defintion: Deep architectures are composed of multiple levels of nonlinear operations, such as neural nets with many hidden layers. Output layer Hidden layers Input layer 4 Goal of Deep architectures Goal: Deep learning methods aim at  learning feature hierarchies  where features from higher levels of the hierarchy are formed by lower level features. edges, local shapes, object parts Low level representation 5 Figure is from Yoshua Bengio Neurobiological Motivation  Most current learning algorithms are shallow architectures (13 levels) (SVM, kNN, MoG, KDE, Parzen Kernel regression, PCA, Perceptron,…)  The mammal brain is organized in a deep architecture (Serre, Kreiman, Kouh, Cadieu, Knoblich, Poggio, 2007) (E.g. visual system has 5 to 10 levels) 6 Deep Learning History  Inspired by the architectural depth of the brain, researchers wanted for decades to train deep multilayer neural networks.  No successful attempts were reported before 2006 … Researchers reported positive experimental results with typically two or three levels (i.e. one or two hidden layers), but training deeper networks consistently yielded poorer results.  Exception: convolutional neural networks, LeCun 1998  SVM: Vapnik and his coworkers developed the Support Vector Machine (1993). It is a shallow architecture.  Digression: In the 1990’s, many researchers abandoned neural networks with multiple adaptive hidden layers because SVMs worked better, and there was no successful attempts to train deep networks.  Breakthrough in 2006 7 Breakthrough Deep Belief Networks (DBN) Hinton, G. E, Osindero, S., and Teh, Y. W. (2006). A fast learning algorithm for deep belief nets. Neural Computation, 18:15271554. Autoencoders Bengio, Y., Lamblin, P., Popovici, P., Larochelle, H. (2007). Greedy LayerWise Training of Deep Networks, Advances in Neural Information Processing Systems 19 8 Theoretical Advantages of Deep Architectures  Some functions cannot be efficiently represented (in terms of number of tunable elements) by architectures that are too shallow.  Deep architectures might be able to represent some functions otherwise not efficiently representable.  More formally: Functions that can be compactly represented by a depth k architecture might require an exponential number of computational elements to be represented by a depth k − 1 architecture  The consequences are  Computational: We don’t need exponentially many elements in the layers  Statistical: poor generalization may be expected when using an insufficiently deep architecture for representing some functions. 9 Theoretical Advantages of Deep Architectures The Polynoimal circuit: 10 Deep Convolutional Networks 11 Deep Convolutional Networks  Deep supervised neural networks are generally too difficult to train.  One notable exception: convolutional neural networks (CNN)  Convolutional nets were inspired by the visual system’s structure  They typically have five, six or seven layers, a number of layers which makes fullyconnected neural networks almost impossible to train properly when initialized randomly. 12 Deep Convolutional Networks Compared to standard feedforward neural networks with similarlysized layers,  CNNs have much fewer connections and parameters  and so they are easier to train,  while their theoreticallybest performance is likely to be only slightly worse. LeNet 5 Y. LeCun, L. Bottou, Y. Bengio and P. Haffner: GradientBased Learning Applied to Document Recognition, Proceedings of the IEEE, 86(11):22782324, November 1998 13 LeNet 5, LeCun 1998  Input: 32x32 pixel image. Largest character is 20x20 (All important info should be in the center of the receptive field of the highest level feature detectors)  Cx: Convolutional layer  Sx: Subsample layer  Fx: Fully connected layer  Black and White pixel values are normalized: E.g. White = 0.1, Black =1.175 (Mean of pixels = 0, Std of pixels =1) 14 LeNet 5, Layer C1 C1: Convolutional layer with 6 feature maps of size 28x28. C1 (k=1…6) k Each unit of C1 has a 5x5 receptive field in the input layer.  Topological structure  Sparse connections  Shared weights (55+1)6=156 parameters to learn Connections: 2828(55+1)6=122304 15 If it was fully connected we had (3232+1)(2828)6 parameters LeNet 5, Layer S2 S2: Subsampling layer with 6 feature maps of size 14x14 2x2 nonoverlapping receptive fields in C1 Layer S2: 62=12 trainable parameters. Connections: 1414(22+1)6=5880 16 LeNet 5, Layer C3  C3: Convolutional layer with 16 feature maps of size 10x10  Each unit in C3 is connected to several 5x5 receptive fields at identical locations in S2 Layer C3: 1516 trainable parameters. Connections: 151600 17 LeNet 5, Layer S4  S4: Subsampling layer with 16 feature maps of size 5x5  Each unit in S4 is connected to the corresponding 2x2 receptive field at C3 Layer S4: 162=32 trainable parameters. Connections: 55(22+1)16=2000 18 LeNet 5, Layer C5  C5: Convolutional layer with 120 feature maps of size 1x1  Each unit in C5 is connected to all 16 5x5 receptive fields in S4 Layer C5: 120(1625+1) = 48120 trainable parameters and connections (Fully connected) 19 LeNet 5, Layer C5 Layer F6: 84 fully connected units. 84(120+1)=10164 trainable parameters and connections. Output layer: 10RBF (One for each digit) 84=7x12, stylized image Weight update: Backpropagation 20 MINIST Dataset 60,000 original datasets Test error: 0.95 540,000 artificial distortions + 60,000 original Test error: 0.8 21 Misclassified examples 22 LeNet 5 in Action Input S4 C1 C3 23 LeNet 5, Shift invariance 24 LeNet 5, Rotation invariance 25 LeNet 5, Nosie resistance 26 LeNet 5, Unusual Patterns 27 ImageNet Classification with Deep Convolutional Neural Networks Alex Krizhevsky, Ilya Sutskever, Geoffrey Hinton, Advances in Neural Information Processing Systems 2012 28 ImageNet  15M images  22K categories  Images collected from Web  Human labelers (Amazon’s Mechanical Turk crowdsourcing)  ImageNet Large Scale Visual Recognition Challenge (ILSVRC2010) o 1K categories o 1.2M training images (1000 per category) o 50,000 validation images o 150,000 testing images  RGB images  Variableresolution, but this architecture scales them to 256x256 size 29 ImageNet Classification goals:  Make 1 guess about the label (Top1 error)  make 5 guesses about the label (Top5 error) 30 The Architecture Typical nonlinearities: Here, however, Rectified Linear Units (ReLU) are used: Empirical observation: Deep convolutional neural networks with ReLUs train several times faster than their equivalents with tanh units A fourlayer convolutional neural network with ReLUs (solid line) reaches a 25 training error rate on CIFAR10 six times faster than an equivalent network with tanh neurons (dashed line) 31 The Architecture The first convolutional layer filters the 224×224×3 input image with 96 kernels of size 11×11×3 with a stride of 4 pixels (this is the distance between the receptive field centers of neighboring neurons in the kernel map. 224/4=56 The pooling layer: form of nonlinear downsampling. Maxpooling partitions the input image into a set of rectangles and, for each such sub region, outputs the maximum value 32 The Architecture  Trained with stochastic gradient descent  on two NVIDIA GTX 580 3GB GPUs  for about a week  650,000 neurons  60,000,000 parameters  630,000,000 connections  5 convolutional layer, 3 fully connected layer  Final feature layer: 4096dimensional 33 Data Augmentation The easiest and most common method to reduce overfitting on image data is to artificially enlarge the dataset using labelpreserving transformations. We employ two distinct forms of data augmentation:  image translation  horizontal reflections  changing RGB intensities 34 Dropout  We know that combining different models can be very useful (Mixture of experts, majority voting, boosting, etc)  Training many different models, however, is very time consuming. The solution: Dropout: set the output of each hidden neuron to zero w.p. 0.5. 35 Dropout Dropout: set the output of each hidden neuron to zero w.p. 0.5.  The neurons which are “dropped out” in this way do not contribute to the forward pass and do not participate in backpropagation.  So every time an input is presented, the neural network samples a different architecture, but all these architectures share weights.  This technique reduces complex coadaptations of neurons, since a neuron cannot rely on the presence of particular other neurons.  It is, therefore, forced to learn more robust features that are useful in conjunction with many different random subsets of the other neurons.  Without dropout, our network exhibits substantial overfitting.  Dropout roughly doubles the number of iterations required to converge. 36 The first convolutional layer 96 convolutional kernels of size 11×11×3 learned by the first convolutional layer on the 224×224×3 input images. The top 48 kernels were learned on GPU1 while the bottom 48 kernels were learned on GPU2 Looks like Gabor wavelets, ICA filters… 37 Results Results on the test data: top1 error rate: 37.5 top5 error rate: 17.0 ILSVRC2012 competition: 15.3 accuracy nd 2 best team: 26.2 accuracy 38 Results 39 Results: Image similarity six training images that produce feature vectors in Test column the last hidden layer with the smallest Euclidean distance 40 from the feature vector for the test image. Deep Belief Networks 41 What is wrong with back propagation  It requires labeled training data.  Almost all data is unlabeled.  The learning time does not scale well.  It is very slow in networks with multiple hidden layers.  It can get stuck in poor local optima.  Usually in deep nets they are far from optimal.  MLP is not a generative model, it only focuses on P(YX). We would like a generative approach that could learn P(X) as well.  Solution: Deep Belief Networks, a generative graphical model 42 Deep Belief Network Deep Belief Networks (DBN’s)  are probabilistic generative models  contain many layers of hidden variables  each layer captures highorder correlations between the activities of hidden features in the layer below  the top two layers of the DBN form an undirected bipartite graph called Restricted Boltzmann Machine  the lower layers forming a directed sigmoid belief network 43 Deep Belief Network Restricted Boltzmann Machine sigmoid belief network sigmoid belief network 44 Data vector Deep Belief Network Joint likelihood: 45 Boltzmann Machines 46 Boltzmann Machines Boltzmann machine: a network of symmetrically coupled stochastic binary units 0,1 Parameters: Hidden layer W: visibletohidden L: visibletovisible, diag(L)=0 J: hiddentohidden, diag(J)=0 Visible layer Energy of the Boltzmann machine: 47 Boltzmann Machines Energy of the Boltzmann machine: Generative model: Joint likelihood: Probability of a visible vector v: Exponentially large set 48 Restricted Boltzmann Machines No hiddentohidden and no visibletovisible connections. W: visibletohidden L = 0: visibletovisible Hidden layer J = 0: hiddentohidden Energy of RBM: Visible layer Joint likelihood: 49 Restricted Boltzmann Machines Top layer: vector of stochastic binary hidden units h Bottom layer: a vector of stochastic binary visible variables v. Figure is taken from R. Salakhutdinov 50 Training RBM Due to the special bipartite structure of RBM’s, the hidden units can be explicitly marginalized out: 51 Training RBM Gradient descent: The exact calculations are intractable because the expectation operator in EPModel takes exponential time in min(D,F) Efficient Gibbs sampling based approximation exists (Contrastive divergence) 52 Inference in RBM Inference is simple in RBM: 53 Training Deep Belief Networks 54 Training Deep Belief Networks Greedy layerwise unsupervised learning: Much better results could be achieved when pretraining each layer with an unsupervised learning algorithm, one layer after the other, starting with the first layer (that directly takes in the observed x as input).  The initial experiments used the RBM generative model for each layer.  Later variants: autoencoders for training each layer (Bengio et al., 2007; Ranzato et al., 2007; Vincent et al., 2008  After having initialized a number of layers, the whole neural network can be finetuned with respect to a supervised training criterion as usual 55 Training Deep Belief Networks The unsupervised greedy layerwise training serves as initialization, replacing the traditional random initialization of multilayer networks. Data 56 Training Deep Belief Networks 57  Deep architecture trained online with 10 million examples of digit images, either with pretraining (triangles) or without (circles).  The first 2.5 million examples are used for unsupervised pretraining.  One can see that without pretraining, training converges to a poorer apparent local minimum: unsupervised pretraining helps to find a 58 better minimum of the online error. Experiments performed by Dumitru Erhan. Results 59 Deep Boltzmann Machines Results 60 Deep Boltzmann Machines Results 61 Deep Boltzmann Machines Results 62 Deep Boltzmann Machines Results 63 Thanks for your Attention  64