What is Keras?
Keras is a deep learning framework that provides a convenient framework to define and train any kind of deep learning model. It has a user friendly API and the same code can run on both CPU and GPUs.
Keras is a model-level library meaning it provides a high-level building blocks for developing deep learning models. It cannot handle low level operations like tensor manipulation or differentiation. Keras depends on well optimized tensor library to do so, which serves as the backend engine for Keras. Several backend engines can be plugged into Keras - TensorFlow developed by Google, CNTK developed by Microsoft and Theano.
So, Keras depends on a backend to do the low-level computations like TensorFlow. When run on a CPU, TensorFlow itself is wrapping a low-level library for tensor operations, called Eigen. On a GPU, TensorFlow wraps a library called the NVIDIA CUDA Deep Neural Network library- cuDNN.
The default and the recommended backend in TensorFlow. In R, when you install Keras library it will automatically install TensorFlow. And the default installation is for a CPU.
If you are using a GPU, then do -
#install_keras(tensorflow = "gpu")
MNIST Dataset
The MNIST dataset is often considered as the “hello world” of deep learning. It’s basically a set of grayscale images (28 x 28 pixels) of hand written single digits that fall into 10 categories - 0 through 9.
Sample = Image; Feature = Pixels; Outcome = 10 categories;
This is a standard dataset, so it comes with train and test split. There are 60,000 images in train data and 10,000 images in test data.
The MNIST dataset comes preloaded in Keras, in the form of train and test lists, each of which includes a set of images (x) and their associated labels (y).
Check out some other datasets available in Keras package
?dataset_
No documentation for ‘dataset_’ in specified packages and libraries:
you could try ‘??dataset_’
Load the MNIST Dataset
mnist <- dataset_mnist() #mnist is a list
/home/auggy/.virtualenvs/r-tensorflow/lib/python2.7/site-packages/h5py/__init__.py:36: FutureWarning: Conversion of the second argument of issubdtype from `float` to `np.floating` is deprecated. In future, it will be treated as `np.float64 == np.dtype(float).type`.
from ._conv import register_converters as _register_converters
Using TensorFlow backend.
train_images <- mnist$train$x
train_labels <- mnist$train$y
test_images <- mnist$test$x
test_labels <- mnist$test$y
Understand your data structure..
What is the structure of training data?
class(train_images)
[1] "array"
str(train_images)
int [1:60000, 1:28, 1:28] 0 0 0 0 0 0 0 0 0 0 ...
class(train_labels)
[1] "array"
str(train_labels)
int [1:60000(1d)] 5 0 4 1 9 2 1 3 1 4 ...
What is the structure of test data?
class(test_images)
[1] "array"
str(test_images)
int [1:10000, 1:28, 1:28] 0 0 0 0 0 0 0 0 0 0 ...
class(test_labels)
[1] "array"
str(test_labels)
int [1:10000(1d)] 7 2 1 0 4 1 4 9 5 9 ...
The structure we see in training data for ex, is an array of 60,000 matrices of 28 x 28 integers. Since it’s grayscale, the coefficients will range from 0 to 255.
min(train_images)
[1] 0
max(train_images)
[1] 255
Let’s look at a digit!
digit<-train_images[1,,]
plot(as.raster(digit,max = 255))

Where are the tensors?
The array train_images is actually a tensor! And so is train_labels. Tensors are multidimensional arrays. We’ve all dealt with tensors before!
Scalar is a 0D tensor; a vector is a 1D Tensor; a matrix is a 2D tensor.
If you pack a bunch of matrices in an array then it’s a 3D tensor; if you pack a bunch of 3D tensors in an array then you will get a 4D tensor and so on.
You can think of grayscale images as 3D tensor, color images as 4D tensor and videos as 5D Tensor.
What are the dimensions in each of those?
3D - Grayscale images = samples, height, width 4D - Color images = samples, height, width, channels-R,B,G 5D - Videos = samples, frames, height, width, channels
paste("The number of axes in our training data")
[1] "The number of axes in our training data"
length(dim(train_images))
[1] 3
Building the Neural Network
There are 2 broad things that we need to do - one is to pick a network architecture and the 2nd is to compilation step that includes optimization.
Define the network architecture
network <- keras_model_sequential() %>% #linear layers
layer_dense(units = 512, activation = "relu", input_shape = c(28 * 28)) %>% #in a NN, each layer is made of unit, each unit has a function called activations
layer_dense(units = 10, activation = "softmax") #output
Layers are the core building blocks of a NN. Think of it as a filter of data, as some data goes in, it comes out in a more useful form. This useful form is fed into another layer and you might get more refined data.
Layers extract representations out of the data fed into them. Most of deep learning consists of chaining together simple layers that will implement a form of progressive data distillation.
Our network consists of 2 layers which are densely connected i.e. fully connected neural layers.The last layer is a 10-way softmax layer - it gives an array of 10 probability scores one for each class that sums to 1. Think of softmax as a generalized logistic function - instead of 2 classes we have 10 classes.
Compilation Step
There are 3 things that we need to pick within compilation.
network %>% compile(
optimizer = "rmsprop", #network will update itself based on the training data & loss
loss = "categorical_crossentropy", #measure mismatch between y_pred and y
metrics = c("accuracy") #measure of performace - correctly classified images
)
Pre-Processing the data
Just like several other ML models, we need to preprocess the data into the right shape and scale the pixels so it ranges from 0 to 1 instead of 0 to 255
train_images <- array_reshape(train_images, c(60000, 28 * 28))
train_images <- train_images / 255
test_images <- array_reshape(test_images, c(10000, 28 * 28))
test_images <- test_images / 255
dim(train_images)
[1] 60000 784
dim(test_images)
[1] 10000 784
Prepare the labels
train_labels <- to_categorical(train_labels)
test_labels <- to_categorical(test_labels)
dim(train_labels)
[1] 60000 10
dim(test_labels)
[1] 10000 10
Fit the model
history <-network %>% fit(train_images, train_labels, epochs = 10, batch_size = 128,validation_split = 0.1) #epoch is an interation. Every iteration a random batch of 128 images are passed through the network
plot(history)

Metrics
metrics <- network %>% evaluate(test_images, test_labels)
metrics
$loss
[1] 0.06858944
$acc
[1] 0.9824
The test accuracy is lower than train accuracy - Overfitting! What should we do when there’s over fitting?
network %>% predict_classes(test_images[1:10,])
[1] 7 2 1 0 4 1 4 9 5 9
Try another architecture!
model<-keras_model_sequential()
model %>%
layer_dense(units=512,activation = "relu",input_shape = c(28*28)) %>%
layer_dropout(rate = 0.4) %>%
layer_dense(units=512,activation = "relu") %>%
layer_dropout(rate = 0.3) %>%
layer_dense(units=512,activation = "relu") %>%
layer_dropout(rate = 0.2) %>%
layer_dense(units=10,activation = "softmax")
model %>% compile(
optimizer = "rmsprop",
loss = "categorical_crossentropy",
metrics = c("accuracy"))
Fit the model
history <- model %>% fit(
train_images, train_labels,
epochs = 10, batch_size = 128,
validation_split = 0.1
)
plot(history)

Since training and validation accuracy is almost equal this model has a good fit. There’s no overfitting or underfitting - hence this model can be generalized.
metrics
$loss
[1] 0.06858944
$acc
[1] 0.9824
Break down the architecture
What we’ve seen so far in designing and fitting a neural network is a whole bunch of tensor operations - adding a tensor, multiplying a tensor etc…
Consider the following -
layer_dense(units = 512, activation = “relu”)
This is basically the first layer which contains 512 units and each unit is defined by a function called ‘activation’ and the function chosen here is - ReLu. ReLu stands for Rectified Linear Unit. It’s just a fancy way of saying -
relu(z) = max(z,0)
When we use tensors - stacked matrices - and when we want to perform operations we dont have to use for loops, we can just apply matrix algebra! This significantly improves performance and efficiency in running complex networks with 10’s or 100’s of layers!! This is called vectorized implementation.
z=W.X+b where X=input, b=bias, W=weights
at every unit of the 1st layer we are calculating-
max(W.X+b,0)
Gradient based optimization
W,b are tensors that are attributes of a layer. Initially, the weights are given random values - called random initialization.
What comes next is to gradually adjust these weights, based on a feedback signal. This gradual adjustment, also called training, is basically the learning that machine learning is all about.
What happens in a training loop?
- Draw a batch of training samples x and corresponding targets y.
- Run the network on x (a step called the forward pass) to obtain predictions y_pred forward propagation
- Compute the loss of the network on the batch, a measure of the mismatch between y_pred and y
- Update all the weights in a way that it slightly reduces the loss in this batch. backward propagation
Step 1-3 is straightforward. Step 4 is the challenge.
The difficult part is step 4: updating the net- work’s weights. Given an individual weight coefficient in the network, how can you compute whether the coefficient should be increased or decreased, and by how much?
All operations used in the network are differentiable, and compute the gradient of the loss with regard to the network’s coefficients
A gradient is a derivative of a multidimensional input like a tensor. You can think of back prop as a chain of partial differential equations. If a function is differentiable then we can find a min of that function.
In a NN framework, what this means is that we need to find the combination of weights such that yields lowest possible loss.
1.Draw a batch of training samples x and corresponding targets y. 2 Run the network on x to obtain predictions y_pred. 3 Compute the loss of the network on the batch, a measure of the mismatch between y_pred and y. 4 Compute the gradient of the loss with regard to the network’s parameters (a backward pass). 5 Move the parameters a little in the opposite direction from the gradient—for example, W=W-(step*gradient)—thus reducing the loss on the batch a bit.
This is called a mini batch Stochastic Gradient Descent.
The step factor is called learning rate. Picking a reasonable learning rate is important in DL models because if it’s too small then the model will learn very slowly, and if it’s too large then the model might miss the global min of loss function!
LS0tCnRpdGxlOiAiS2VyYXMiCm91dHB1dDoKICBodG1sX25vdGVib29rOiBudWxsCiAgaGlnaGxpZ2h0OiB0ZXh0bWF0ZQogIGh0bWxfZG9jdW1lbnQ6CiAgICBkZl9wcmludDogcGFnZWQKICB0aGVtZTogY2VydWxlYW4KLS0tCgoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSkKYGBgCgojIyMgV2hhdCBpcyBLZXJhcz8KCktlcmFzIGlzIGEgZGVlcCBsZWFybmluZyBmcmFtZXdvcmsgdGhhdCBwcm92aWRlcyBhIGNvbnZlbmllbnQgZnJhbWV3b3JrIHRvIGRlZmluZSBhbmQgdHJhaW4gYW55IGtpbmQgb2YgZGVlcCBsZWFybmluZyBtb2RlbC4gSXQgaGFzIGEgdXNlciBmcmllbmRseSBBUEkgYW5kIHRoZSBzYW1lIGNvZGUgY2FuIHJ1biBvbiBib3RoIENQVSBhbmQgR1BVcy4KCktlcmFzIGlzIGEgbW9kZWwtbGV2ZWwgbGlicmFyeSBtZWFuaW5nIGl0IHByb3ZpZGVzIGEgaGlnaC1sZXZlbCBidWlsZGluZyBibG9ja3MgZm9yIGRldmVsb3BpbmcgZGVlcCBsZWFybmluZyBtb2RlbHMuIEl0IGNhbm5vdCBoYW5kbGUgbG93IGxldmVsIG9wZXJhdGlvbnMgbGlrZSB0ZW5zb3IgbWFuaXB1bGF0aW9uIG9yIGRpZmZlcmVudGlhdGlvbi4gS2VyYXMgZGVwZW5kcyBvbiB3ZWxsIG9wdGltaXplZCB0ZW5zb3IgbGlicmFyeSB0byBkbyBzbywgd2hpY2ggc2VydmVzIGFzIHRoZSBfYmFja2VuZCBlbmdpbmVfIGZvciBLZXJhcy4gU2V2ZXJhbCBiYWNrZW5kIGVuZ2luZXMgY2FuIGJlIHBsdWdnZWQgaW50byBLZXJhcyAtIFRlbnNvckZsb3cgZGV2ZWxvcGVkIGJ5IEdvb2dsZSwgQ05USyBkZXZlbG9wZWQgYnkgTWljcm9zb2Z0IGFuZCBUaGVhbm8uIAoKU28sIEtlcmFzIGRlcGVuZHMgb24gYSBiYWNrZW5kIHRvIGRvIHRoZSBsb3ctbGV2ZWwgY29tcHV0YXRpb25zIGxpa2UgVGVuc29yRmxvdy4gV2hlbiBydW4gb24gYSBDUFUsIFRlbnNvckZsb3cgaXRzZWxmIGlzIHdyYXBwaW5nIGEgbG93LWxldmVsIGxpYnJhcnkgZm9yIHRlbnNvciBvcGVyYXRpb25zLCBjYWxsZWQgRWlnZW4uIE9uIGEgR1BVLCBUZW5zb3JGbG93IHdyYXBzIGEgbGlicmFyeSBjYWxsZWQgdGhlIE5WSURJQSBDVURBIERlZXAgTmV1cmFsIE5ldHdvcmsgbGlicmFyeS0gY3VETk4uCgpUaGUgZGVmYXVsdCBhbmQgdGhlIHJlY29tbWVuZGVkIGJhY2tlbmQgaW4gVGVuc29yRmxvdy4gSW4gUiwgd2hlbiB5b3UgaW5zdGFsbCBLZXJhcyBsaWJyYXJ5IGl0IHdpbGwgYXV0b21hdGljYWxseSBpbnN0YWxsIFRlbnNvckZsb3cuIEFuZCB0aGUgZGVmYXVsdCBpbnN0YWxsYXRpb24gaXMgZm9yIGEgQ1BVLiAKCmBgYHtyfQppbnN0YWxsLnBhY2thZ2VzKCJrZXJhcyIpCmxpYnJhcnkoa2VyYXMpCmluc3RhbGxfa2VyYXMoKQpgYGAKCklmIHlvdSBhcmUgdXNpbmcgYSBHUFUsIHRoZW4gZG8gLSAKCmBgYHtyfQojaW5zdGFsbF9rZXJhcyh0ZW5zb3JmbG93ID0gImdwdSIpCmBgYAoKCiMjIyBNTklTVCBEYXRhc2V0CgpUaGUgTU5JU1QgZGF0YXNldCBpcyBvZnRlbiBjb25zaWRlcmVkIGFzIHRoZSAiaGVsbG8gd29ybGQiIG9mIGRlZXAgbGVhcm5pbmcuIEl0J3MgYmFzaWNhbGx5IGEgc2V0IG9mIGdyYXlzY2FsZSBpbWFnZXMgKDI4IHggMjggcGl4ZWxzKSBvZiBoYW5kIHdyaXR0ZW4gc2luZ2xlIGRpZ2l0cyB0aGF0IGZhbGwgaW50byAxMCBjYXRlZ29yaWVzIC0gMCB0aHJvdWdoIDkuIAoKU2FtcGxlID0gSW1hZ2U7CkZlYXR1cmUgPSBQaXhlbHM7Ck91dGNvbWUgPSAxMCBjYXRlZ29yaWVzOwoKVGhpcyBpcyBhIHN0YW5kYXJkIGRhdGFzZXQsIHNvIGl0IGNvbWVzIHdpdGggX3RyYWluXyBhbmQgX3Rlc3RfIHNwbGl0LiBUaGVyZSBhcmUgNjAsMDAwIGltYWdlcyBpbiB0cmFpbiBkYXRhIGFuZCAxMCwwMDAgaW1hZ2VzIGluIHRlc3QgZGF0YS4KClRoZSBNTklTVCBkYXRhc2V0IGNvbWVzIHByZWxvYWRlZCBpbiBLZXJhcywgaW4gdGhlIGZvcm0gb2YgdHJhaW4gYW5kIHRlc3QgbGlzdHMsIGVhY2ggb2Ygd2hpY2ggaW5jbHVkZXMgYSBzZXQgb2YgaW1hZ2VzICh4KSBhbmQgdGhlaXIgYXNzb2NpYXRlZCBsYWJlbHMgKHkpLgoKQ2hlY2sgb3V0IHNvbWUgb3RoZXIgZGF0YXNldHMgYXZhaWxhYmxlIGluIEtlcmFzIHBhY2thZ2UgCgpgYGB7cn0KP2RhdGFzZXRfCmBgYAoKIyMjIyBMb2FkIHRoZSBNTklTVCBEYXRhc2V0CmBgYHtyfQptbmlzdCA8LSBkYXRhc2V0X21uaXN0KCkgI21uaXN0IGlzIGEgbGlzdAp0cmFpbl9pbWFnZXMgPC0gbW5pc3QkdHJhaW4keCAKdHJhaW5fbGFiZWxzIDwtIG1uaXN0JHRyYWluJHkKdGVzdF9pbWFnZXMgPC0gbW5pc3QkdGVzdCR4CnRlc3RfbGFiZWxzIDwtIG1uaXN0JHRlc3QkeQpgYGAKCgpVbmRlcnN0YW5kIHlvdXIgZGF0YSBzdHJ1Y3R1cmUuLgoKV2hhdCBpcyB0aGUgc3RydWN0dXJlIG9mIHRyYWluaW5nIGRhdGE/CgpgYGB7cn0KY2xhc3ModHJhaW5faW1hZ2VzKQpzdHIodHJhaW5faW1hZ2VzKQoKY2xhc3ModHJhaW5fbGFiZWxzKQpzdHIodHJhaW5fbGFiZWxzKQpgYGAKCgpXaGF0IGlzIHRoZSBzdHJ1Y3R1cmUgb2YgdGVzdCBkYXRhPwoKYGBge3J9CmNsYXNzKHRlc3RfaW1hZ2VzKQpzdHIodGVzdF9pbWFnZXMpCgpjbGFzcyh0ZXN0X2xhYmVscykKc3RyKHRlc3RfbGFiZWxzKQpgYGAKClRoZSBzdHJ1Y3R1cmUgd2Ugc2VlIGluIHRyYWluaW5nIGRhdGEgZm9yIGV4LCBpcyBhbiBhcnJheSBvZiA2MCwwMDAgbWF0cmljZXMgb2YgMjggeCAyOCBpbnRlZ2Vycy4gU2luY2UgaXQncyBncmF5c2NhbGUsIHRoZSBjb2VmZmljaWVudHMgd2lsbCByYW5nZSBmcm9tIDAgdG8gMjU1LgoKYGBge3J9Cm1pbih0cmFpbl9pbWFnZXMpCm1heCh0cmFpbl9pbWFnZXMpCmBgYAoKCkxldCdzIGxvb2sgYXQgYSBkaWdpdCEKCgpgYGB7cn0KZGlnaXQ8LXRyYWluX2ltYWdlc1sxLCxdCnBsb3QoYXMucmFzdGVyKGRpZ2l0LG1heCA9IDI1NSkpCmBgYAoKCiMjIyMjIFdoZXJlIGFyZSB0aGUgdGVuc29ycz8KClRoZSBhcnJheSB0cmFpbl9pbWFnZXMgaXMgYWN0dWFsbHkgYSB0ZW5zb3IhIEFuZCBzbyBpcyB0cmFpbl9sYWJlbHMuIFRlbnNvcnMgYXJlIG11bHRpZGltZW5zaW9uYWwgYXJyYXlzLiBXZSd2ZSBhbGwgZGVhbHQgd2l0aCB0ZW5zb3JzIGJlZm9yZSEgCgpTY2FsYXIgaXMgYSAwRCB0ZW5zb3I7IGEgdmVjdG9yIGlzIGEgMUQgVGVuc29yOyBhIG1hdHJpeCBpcyBhIDJEIHRlbnNvci4KCklmIHlvdSBwYWNrIGEgYnVuY2ggb2YgbWF0cmljZXMgaW4gYW4gYXJyYXkgdGhlbiBpdCdzIGEgM0QgdGVuc29yOyBpZiB5b3UgcGFjayBhIGJ1bmNoIG9mIDNEIHRlbnNvcnMgaW4gYW4gYXJyYXkgdGhlbiB5b3Ugd2lsbCBnZXQgYSA0RCB0ZW5zb3IgYW5kIHNvIG9uLgoKWW91IGNhbiB0aGluayBvZiBncmF5c2NhbGUgaW1hZ2VzIGFzIDNEIHRlbnNvciwgY29sb3IgaW1hZ2VzIGFzIDREIHRlbnNvciBhbmQgdmlkZW9zIGFzIDVEIFRlbnNvci4KCldoYXQgYXJlIHRoZSBkaW1lbnNpb25zIGluIGVhY2ggb2YgdGhvc2U/CgozRCAtIEdyYXlzY2FsZSBpbWFnZXMgPSBzYW1wbGVzLCBoZWlnaHQsIHdpZHRoCjREIC0gQ29sb3IgaW1hZ2VzID0gc2FtcGxlcywgaGVpZ2h0LCB3aWR0aCwgY2hhbm5lbHMtUixCLEcKNUQgLSBWaWRlb3MgPSBzYW1wbGVzLCBmcmFtZXMsIGhlaWdodCwgd2lkdGgsIGNoYW5uZWxzCgpgYGB7cn0KcGFzdGUoIlRoZSBudW1iZXIgb2YgYXhlcyBpbiBvdXIgdHJhaW5pbmcgZGF0YSIpCmxlbmd0aChkaW0odHJhaW5faW1hZ2VzKSkKYGBgCgoKIyMjIEJ1aWxkaW5nIHRoZSBOZXVyYWwgTmV0d29yawoKVGhlcmUgYXJlIDIgYnJvYWQgdGhpbmdzIHRoYXQgd2UgbmVlZCB0byBkbyAtIG9uZSBpcyB0byBwaWNrIGEgbmV0d29yayBhcmNoaXRlY3R1cmUgYW5kIHRoZSAybmQgaXMgdG8gY29tcGlsYXRpb24gc3RlcCB0aGF0IGluY2x1ZGVzIG9wdGltaXphdGlvbi4KCgojIyMjIERlZmluZSB0aGUgbmV0d29yayBhcmNoaXRlY3R1cmUKCmBgYHtyfQpuZXR3b3JrIDwtIGtlcmFzX21vZGVsX3NlcXVlbnRpYWwoKSAlPiUgICNsaW5lYXIgbGF5ZXJzCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA1MTIsIGFjdGl2YXRpb24gPSAicmVsdSIsIGlucHV0X3NoYXBlID0gYygyOCAqIDI4KSkgJT4lICNpbiBhIE5OLCBlYWNoIGxheWVyIGlzIG1hZGUgb2YgdW5pdCwgZWFjaCB1bml0IGhhcyBhIGZ1bmN0aW9uIGNhbGxlZCBhY3RpdmF0aW9ucwogIGxheWVyX2RlbnNlKHVuaXRzID0gMTAsIGFjdGl2YXRpb24gPSAic29mdG1heCIpICNvdXRwdXQKYGBgCgpMYXllcnMgYXJlIHRoZSBjb3JlIGJ1aWxkaW5nIGJsb2NrcyBvZiBhIE5OLiBUaGluayBvZiBpdCBhcyBhIGZpbHRlciBvZiBkYXRhLCBhcyBzb21lIGRhdGEgZ29lcyBpbiwgaXQgY29tZXMgb3V0IGluIGEgbW9yZSB1c2VmdWwgZm9ybS4gVGhpcyB1c2VmdWwgZm9ybSBpcyBmZWQgaW50byBhbm90aGVyIGxheWVyIGFuZCB5b3UgbWlnaHQgZ2V0IG1vcmUgcmVmaW5lZCBkYXRhLiAKCkxheWVycyBleHRyYWN0IF9yZXByZXNlbnRhdGlvbnNfIG91dCBvZiB0aGUgZGF0YSBmZWQgaW50byB0aGVtLiBNb3N0IG9mIGRlZXAgbGVhcm5pbmcgY29uc2lzdHMgb2YgY2hhaW5pbmcgdG9nZXRoZXIgc2ltcGxlIGxheWVycyB0aGF0IHdpbGwgaW1wbGVtZW50IGEgZm9ybSBvZiBwcm9ncmVzc2l2ZSBfZGF0YSBkaXN0aWxsYXRpb25fLgoKT3VyIG5ldHdvcmsgY29uc2lzdHMgb2YgMiBsYXllcnMgd2hpY2ggYXJlIGRlbnNlbHkgY29ubmVjdGVkIGkuZS4gZnVsbHkgY29ubmVjdGVkIG5ldXJhbCBsYXllcnMuVGhlIGxhc3QgbGF5ZXIgaXMgYSAxMC13YXkgc29mdG1heCBsYXllciAtIGl0IGdpdmVzIGFuIGFycmF5IG9mIDEwIHByb2JhYmlsaXR5IHNjb3JlcyBvbmUgZm9yIGVhY2ggY2xhc3MgdGhhdCBzdW1zIHRvIDEuIFRoaW5rIG9mIHNvZnRtYXggYXMgYSBnZW5lcmFsaXplZCBsb2dpc3RpYyBmdW5jdGlvbiAtIGluc3RlYWQgb2YgMiBjbGFzc2VzIHdlIGhhdmUgMTAgY2xhc3Nlcy4KCgojIyMjIENvbXBpbGF0aW9uIFN0ZXAKClRoZXJlIGFyZSAzIHRoaW5ncyB0aGF0IHdlIG5lZWQgdG8gcGljayB3aXRoaW4gY29tcGlsYXRpb24uCgpgYGB7cn0KbmV0d29yayAlPiUgY29tcGlsZSgKICBvcHRpbWl6ZXIgPSAicm1zcHJvcCIsICNuZXR3b3JrIHdpbGwgdXBkYXRlIGl0c2VsZiBiYXNlZCBvbiB0aGUgdHJhaW5pbmcgZGF0YSAmIGxvc3MKICBsb3NzID0gImNhdGVnb3JpY2FsX2Nyb3NzZW50cm9weSIsICNtZWFzdXJlIG1pc21hdGNoIGJldHdlZW4geV9wcmVkIGFuZCB5CiAgbWV0cmljcyA9IGMoImFjY3VyYWN5IikgI21lYXN1cmUgb2YgcGVyZm9ybWFjZSAtIGNvcnJlY3RseSBjbGFzc2lmaWVkIGltYWdlcwopCmBgYAoKIyMjIyBQcmUtUHJvY2Vzc2luZyB0aGUgZGF0YQoKSnVzdCBsaWtlIHNldmVyYWwgb3RoZXIgTUwgbW9kZWxzLCB3ZSBuZWVkIHRvIHByZXByb2Nlc3MgdGhlIGRhdGEgaW50byB0aGUgcmlnaHQgc2hhcGUgYW5kIHNjYWxlIHRoZSBwaXhlbHMgc28gaXQgcmFuZ2VzIGZyb20gMCB0byAxIGluc3RlYWQgb2YgMCB0byAyNTUKCmBgYHtyfQp0cmFpbl9pbWFnZXMgPC0gYXJyYXlfcmVzaGFwZSh0cmFpbl9pbWFnZXMsIGMoNjAwMDAsIDI4ICogMjgpKQp0cmFpbl9pbWFnZXMgPC0gdHJhaW5faW1hZ2VzIC8gMjU1Cgp0ZXN0X2ltYWdlcyA8LSBhcnJheV9yZXNoYXBlKHRlc3RfaW1hZ2VzLCBjKDEwMDAwLCAyOCAqIDI4KSkKdGVzdF9pbWFnZXMgPC0gdGVzdF9pbWFnZXMgLyAyNTUKCmRpbSh0cmFpbl9pbWFnZXMpCmRpbSh0ZXN0X2ltYWdlcykKYGBgCgoKIyMjIyBQcmVwYXJlIHRoZSBsYWJlbHMKCmBgYHtyfQp0cmFpbl9sYWJlbHMgPC0gdG9fY2F0ZWdvcmljYWwodHJhaW5fbGFiZWxzKQp0ZXN0X2xhYmVscyA8LSB0b19jYXRlZ29yaWNhbCh0ZXN0X2xhYmVscykKCmRpbSh0cmFpbl9sYWJlbHMpCmRpbSh0ZXN0X2xhYmVscykKYGBgCgoKIyMjIyBGaXQgdGhlIG1vZGVsCgpgYGB7ciByZXN1bHRzPSdoaWRlJ30KaGlzdG9yeSA8LW5ldHdvcmsgJT4lIGZpdCh0cmFpbl9pbWFnZXMsIHRyYWluX2xhYmVscywgZXBvY2hzID0gMTAsIGJhdGNoX3NpemUgPSAxMjgsdmFsaWRhdGlvbl9zcGxpdCA9IDAuMSkgI2Vwb2NoIGlzIGFuIGludGVyYXRpb24uIEV2ZXJ5IGl0ZXJhdGlvbiBhIHJhbmRvbSBiYXRjaCBvZiAxMjggaW1hZ2VzIGFyZSBwYXNzZWQgdGhyb3VnaCB0aGUgbmV0d29yawpgYGAKCmBgYHtyfQpwbG90KGhpc3RvcnkpCmBgYAoKCiMjIyMgTWV0cmljcwoKYGBge3IgcmVzdWx0cz0naGlkZSd9Cm1ldHJpY3MgPC0gbmV0d29yayAlPiUgZXZhbHVhdGUodGVzdF9pbWFnZXMsIHRlc3RfbGFiZWxzKQpgYGAKCmBgYHtyfQptZXRyaWNzCmBgYAoKVGhlIHRlc3QgYWNjdXJhY3kgaXMgbG93ZXIgdGhhbiB0cmFpbiBhY2N1cmFjeSAtIE92ZXJmaXR0aW5nISBXaGF0IHNob3VsZCB3ZSBkbyB3aGVuIHRoZXJlJ3Mgb3ZlciBmaXR0aW5nPwoKYGBge3J9Cm5ldHdvcmsgJT4lIHByZWRpY3RfY2xhc3Nlcyh0ZXN0X2ltYWdlc1sxOjEwLF0pCmBgYAoKCiMjIyMgVHJ5IGFub3RoZXIgYXJjaGl0ZWN0dXJlIQoKYGBge3J9Cm1vZGVsPC1rZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkKbW9kZWwgJT4lIAogIGxheWVyX2RlbnNlKHVuaXRzPTUxMixhY3RpdmF0aW9uID0gInJlbHUiLGlucHV0X3NoYXBlID0gYygyOCoyOCkpICU+JQogIGxheWVyX2Ryb3BvdXQocmF0ZSA9IDAuNCkgJT4lCiAgbGF5ZXJfZGVuc2UodW5pdHM9NTEyLGFjdGl2YXRpb24gPSAicmVsdSIpICU+JQogIGxheWVyX2Ryb3BvdXQocmF0ZSA9IDAuMykgJT4lCiAgbGF5ZXJfZGVuc2UodW5pdHM9NTEyLGFjdGl2YXRpb24gPSAicmVsdSIpICU+JQogIGxheWVyX2Ryb3BvdXQocmF0ZSA9IDAuMikgJT4lCiAgbGF5ZXJfZGVuc2UodW5pdHM9MTAsYWN0aXZhdGlvbiA9ICJzb2Z0bWF4IikKCm1vZGVsICU+JSBjb21waWxlKAogIG9wdGltaXplciA9ICJybXNwcm9wIiwgCiAgbG9zcyA9ICJjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkiLCAKICBtZXRyaWNzID0gYygiYWNjdXJhY3kiKSkgCmBgYAoKCkZpdCB0aGUgbW9kZWwKCgpgYGB7ciByZXN1bHRzPSdoaWRlJ30KaGlzdG9yeSA8LSBtb2RlbCAlPiUgZml0KAogIHRyYWluX2ltYWdlcywgdHJhaW5fbGFiZWxzLCAKICBlcG9jaHMgPSAxMCwgYmF0Y2hfc2l6ZSA9IDEyOCwgCiAgdmFsaWRhdGlvbl9zcGxpdCA9IDAuMQopCmBgYAoKCmBgYHtyfQpwbG90KGhpc3RvcnkpCmBgYAoKU2luY2UgdHJhaW5pbmcgYW5kIHZhbGlkYXRpb24gYWNjdXJhY3kgaXMgYWxtb3N0IGVxdWFsIHRoaXMgbW9kZWwgaGFzIGEgZ29vZCBmaXQuIFRoZXJlJ3Mgbm8gb3ZlcmZpdHRpbmcgb3IgdW5kZXJmaXR0aW5nIC0gaGVuY2UgdGhpcyBtb2RlbCBjYW4gYmUgZ2VuZXJhbGl6ZWQuCgpgYGB7ciByZXN1bHRzPSdoaWRlJ30KbWV0cmljczwtbW9kZWwlPiVldmFsdWF0ZSh0ZXN0X2ltYWdlcyx0ZXN0X2xhYmVscykKYGBgCgpgYGB7cn0KbWV0cmljcwpgYGAKCiMjIyBCcmVhayBkb3duIHRoZSBhcmNoaXRlY3R1cmUKCldoYXQgd2UndmUgc2VlbiBzbyBmYXIgaW4gZGVzaWduaW5nIGFuZCBmaXR0aW5nIGEgbmV1cmFsIG5ldHdvcmsgaXMgYSB3aG9sZSBidW5jaCBvZiB0ZW5zb3Igb3BlcmF0aW9ucyAtIGFkZGluZyBhIHRlbnNvciwgbXVsdGlwbHlpbmcgYSB0ZW5zb3IgZXRjLi4uCgpDb25zaWRlciB0aGUgZm9sbG93aW5nIC0KCmxheWVyX2RlbnNlKHVuaXRzID0gNTEyLCBhY3RpdmF0aW9uID0gInJlbHUiKQoKVGhpcyBpcyBiYXNpY2FsbHkgdGhlIGZpcnN0IGxheWVyIHdoaWNoIGNvbnRhaW5zIDUxMiB1bml0cyBhbmQgZWFjaCB1bml0IGlzIGRlZmluZWQgYnkgYSBmdW5jdGlvbiBjYWxsZWQgJ2FjdGl2YXRpb24nIGFuZCB0aGUgZnVuY3Rpb24gY2hvc2VuIGhlcmUgaXMgLSBSZUx1LiBSZUx1IHN0YW5kcyBmb3IgUmVjdGlmaWVkIExpbmVhciBVbml0LiBJdCdzIGp1c3QgYSBmYW5jeSB3YXkgb2Ygc2F5aW5nIC0gCgpyZWx1KHopID0gbWF4KHosMCkKCldoZW4gd2UgdXNlIHRlbnNvcnMgLSBzdGFja2VkIG1hdHJpY2VzIC0gYW5kIHdoZW4gd2Ugd2FudCB0byBwZXJmb3JtIG9wZXJhdGlvbnMgd2UgZG9udCBoYXZlIHRvIHVzZSBmb3IgbG9vcHMsIHdlIGNhbiBqdXN0IGFwcGx5IG1hdHJpeCBhbGdlYnJhISBUaGlzIHNpZ25pZmljYW50bHkgaW1wcm92ZXMgcGVyZm9ybWFuY2UgYW5kIGVmZmljaWVuY3kgaW4gcnVubmluZyBjb21wbGV4IG5ldHdvcmtzIHdpdGggMTAncyBvciAxMDAncyBvZiBsYXllcnMhISBUaGlzIGlzIGNhbGxlZCBfdmVjdG9yaXplZF8gaW1wbGVtZW50YXRpb24uCgoKej1XLlgrYgp3aGVyZSBYPWlucHV0LCBiPWJpYXMsIFc9d2VpZ2h0cwoKYXQgZXZlcnkgdW5pdCBvZiB0aGUgMXN0IGxheWVyIHdlIGFyZSBjYWxjdWxhdGluZy0KCm1heChXLlgrYiwwKQoKCiMjIyBHcmFkaWVudCBiYXNlZCBvcHRpbWl6YXRpb24KClcsYiBhcmUgdGVuc29ycyB0aGF0IGFyZSBhdHRyaWJ1dGVzIG9mIGEgbGF5ZXIuIEluaXRpYWxseSwgdGhlIHdlaWdodHMgYXJlIGdpdmVuIHJhbmRvbSB2YWx1ZXMgLSBjYWxsZWQgX3JhbmRvbSBpbml0aWFsaXphdGlvbl8uCgpXaGF0IGNvbWVzIG5leHQgaXMgdG8gZ3JhZHVhbGx5IGFkanVzdCB0aGVzZSB3ZWlnaHRzLCBiYXNlZCBvbiBhIGZlZWRiYWNrIHNpZ25hbC4gVGhpcyBncmFkdWFsIGFkanVzdG1lbnQsIGFsc28gY2FsbGVkIHRyYWluaW5nLCBpcyBiYXNpY2FsbHkgdGhlIGxlYXJuaW5nIHRoYXQgbWFjaGluZSBsZWFybmluZyBpcyBhbGwgYWJvdXQuCgpXaGF0IGhhcHBlbnMgaW4gYSB0cmFpbmluZyBsb29wPwoKMS4gRHJhdyBhIGJhdGNoIG9mIHRyYWluaW5nIHNhbXBsZXMgeCBhbmQgY29ycmVzcG9uZGluZyB0YXJnZXRzIHkuCjIuIFJ1biB0aGUgbmV0d29yayBvbiB4IChhIHN0ZXAgY2FsbGVkIHRoZSBmb3J3YXJkIHBhc3MpIHRvIG9idGFpbiBwcmVkaWN0aW9ucyB5X3ByZWQgX2ZvcndhcmQgcHJvcGFnYXRpb25fCjMuIENvbXB1dGUgdGhlIF9sb3NzXyBvZiB0aGUgbmV0d29yayBvbiB0aGUgYmF0Y2gsIGEgbWVhc3VyZSBvZiB0aGUgbWlzbWF0Y2ggYmV0d2VlbiB5X3ByZWQgYW5kIHkKNC4gVXBkYXRlIGFsbCB0aGUgd2VpZ2h0cyBpbiBhIHdheSB0aGF0IGl0IHNsaWdodGx5IHJlZHVjZXMgdGhlIGxvc3MgaW4gdGhpcyBiYXRjaC4gX2JhY2t3YXJkIHByb3BhZ2F0aW9uXwoKU3RlcCAxLTMgaXMgc3RyYWlnaHRmb3J3YXJkLiBTdGVwIDQgaXMgdGhlIGNoYWxsZW5nZS4gCgpUaGUgZGlmZmljdWx0IHBhcnQgaXMgc3RlcCA0OiB1cGRhdGluZyB0aGUgbmV0LSB3b3Jr4oCZcyB3ZWlnaHRzLiBHaXZlbiBhbiBpbmRpdmlkdWFsIHdlaWdodCBjb2VmZmljaWVudCBpbiB0aGUgbmV0d29yaywgaG93IGNhbiB5b3UgY29tcHV0ZSB3aGV0aGVyIHRoZSBjb2VmZmljaWVudCBzaG91bGQgYmUgaW5jcmVhc2VkIG9yIGRlY3JlYXNlZCwgYW5kIGJ5IGhvdyBtdWNoPwoKQWxsIG9wZXJhdGlvbnMgdXNlZCBpbiB0aGUgbmV0d29yayBhcmUgX2RpZmZlcmVudGlhYmxlXywgYW5kIGNvbXB1dGUgdGhlIF9ncmFkaWVudF8gb2YgdGhlIGxvc3Mgd2l0aCByZWdhcmQgdG8gdGhlIG5ldHdvcmvigJlzIGNvZWZmaWNpZW50cwoKQSBncmFkaWVudCBpcyBhIGRlcml2YXRpdmUgb2YgYSBtdWx0aWRpbWVuc2lvbmFsIGlucHV0IGxpa2UgYSB0ZW5zb3IuIFlvdSBjYW4gdGhpbmsgb2YgYmFjayBwcm9wIGFzIGEgY2hhaW4gb2YgcGFydGlhbCBkaWZmZXJlbnRpYWwgZXF1YXRpb25zLiBJZiBhIGZ1bmN0aW9uIGlzIGRpZmZlcmVudGlhYmxlIHRoZW4gd2UgY2FuIGZpbmQgYSBtaW4gb2YgdGhhdCBmdW5jdGlvbi4KCkluIGEgTk4gZnJhbWV3b3JrLCB3aGF0IHRoaXMgbWVhbnMgaXMgdGhhdCB3ZSBuZWVkIHRvIGZpbmQgdGhlIGNvbWJpbmF0aW9uIG9mIHdlaWdodHMgc3VjaCB0aGF0IHlpZWxkcyBsb3dlc3QgcG9zc2libGUgbG9zcy4gCgoxLkRyYXcgYSBiYXRjaCBvZiB0cmFpbmluZyBzYW1wbGVzIHggYW5kIGNvcnJlc3BvbmRpbmcgdGFyZ2V0cyB5LgoyIFJ1biB0aGUgbmV0d29yayBvbiB4IHRvIG9idGFpbiBwcmVkaWN0aW9ucyB5X3ByZWQuCjMgQ29tcHV0ZSB0aGUgbG9zcyBvZiB0aGUgbmV0d29yayBvbiB0aGUgYmF0Y2gsIGEgbWVhc3VyZSBvZiB0aGUgbWlzbWF0Y2ggYmV0d2VlbiB5X3ByZWQgYW5kIHkuCjQgQ29tcHV0ZSB0aGUgZ3JhZGllbnQgb2YgdGhlIGxvc3Mgd2l0aCByZWdhcmQgdG8gdGhlIG5ldHdvcmvigJlzIHBhcmFtZXRlcnMgKGEgYmFja3dhcmQgcGFzcykuCjUgTW92ZSB0aGUgcGFyYW1ldGVycyBhIGxpdHRsZSBpbiB0aGUgb3Bwb3NpdGUgZGlyZWN0aW9uIGZyb20gdGhlIGdyYWRpZW504oCUZm9yIGV4YW1wbGUsIFc9Vy0oc3RlcCpncmFkaWVudCnigJR0aHVzIHJlZHVjaW5nIHRoZSBsb3NzIG9uIHRoZSBiYXRjaCBhIGJpdC4KClRoaXMgaXMgY2FsbGVkIGEgX21pbmkgYmF0Y2ggU3RvY2hhc3RpYyBHcmFkaWVudCBEZXNjZW50Xy4KClRoZSBfc3RlcF8gZmFjdG9yIGlzIGNhbGxlZCBsZWFybmluZyByYXRlLiBQaWNraW5nIGEgcmVhc29uYWJsZSBsZWFybmluZyByYXRlIGlzIGltcG9ydGFudCBpbiBETCBtb2RlbHMgYmVjYXVzZSBpZiBpdCdzIHRvbyBzbWFsbCB0aGVuIHRoZSBtb2RlbCB3aWxsIGxlYXJuIHZlcnkgc2xvd2x5LCBhbmQgaWYgaXQncyB0b28gbGFyZ2UgdGhlbiB0aGUgbW9kZWwgbWlnaHQgbWlzcyB0aGUgZ2xvYmFsIG1pbiBvZiBsb3NzIGZ1bmN0aW9uIQoKCgoKCgoK