This notebook contains the code samples found in Chapter 3, Section 5 of Deep Learning with R. Note that the original text features far more content, in particular further explanations and figures: in this notebook, you will only find source code and related comments.


Two-class classification, or binary classification, may be the most widely applied kind of machine learning problem. In this example, we will learn to classify movie reviews into “positive” reviews and “negative” reviews, just based on the text content of the reviews.

The IMDB dataset

We’ll be working with “IMDB dataset”, a set of 50,000 highly-polarized reviews from the Internet Movie Database. They are split into 25,000 reviews for training and 25,000 reviews for testing, each set consisting in 50% negative and 50% positive reviews.

Why do we have these two separate training and test sets? You should never test a machine learning model on the same data that you used to train it! Just because a model performs well on its training data doesn’t mean that it will perform well on data it has never seen, and what you actually care about is your model’s performance on new data (since you already know the labels of your training data – obviously you don’t need your model to predict those). For instance, it is possible that your model could end up merely memorizing a mapping between your training samples and their targets – which would be completely useless for the task of predicting targets for data never seen before. We will go over this point in much more detail in the next chapter.

Just like the MNIST dataset, the IMDB dataset comes packaged with Keras. It has already been preprocessed: the reviews (sequences of words) have been turned into sequences of integers, where each integer stands for a specific word in a dictionary.

The following code will load the dataset (when you run it for the first time, about 80MB of data will be downloaded to your machine):

library(keras)
imdb <- dataset_imdb(num_words = 10000)
c(c(train_data, train_labels), c(test_data, test_labels)) %<-% imdb

The argument num_words = 10000 means that we will only keep the top 10,000 most frequently occurring words in the training data. Rare words will be discarded. This allows us to work with vector data of manageable size.

The variables train_data and test_data are lists of reviews, each review being a list of word indices (encoding a sequence of words). train_labels and test_labels are lists of 0s and 1s, where 0 stands for “negative” and 1 stands for “positive”:

str(train_data[[1]])
 int [1:218] 1 14 22 16 43 530 973 1622 1385 65 ...
train_labels[[1]]
[1] 1

Since we restricted ourselves to the top 10,000 most frequent words, no word index will exceed 10,000:

max(sapply(train_data, max))
[1] 9999

For kicks, here’s how you can quickly decode one of these reviews back to English words:

# word_index is a dictionary mapping words to an integer index
word_index <- dataset_imdb_word_index()
# We reverse it, mapping integer indices to words
reverse_word_index <- names(word_index)
names(reverse_word_index) <- word_index
# We decode the review; note that our indices were offset by 3
# because 0, 1 and 2 are reserved indices for "padding", "start of sequence", and "unknown".
decoded_review <- sapply(train_data[[1]], function(index) {
  word <- if (index >= 3) reverse_word_index[[as.character(index - 3)]]
  if (!is.null(word)) word else "?"
})
cat(decoded_review)
? this film was just brilliant casting location scenery story direction everyone's really suited the part they played and you could just imagine being there robert ? is an amazing actor and now the same being director ? father came from the same scottish island as myself so i loved the fact there was a real connection with this film the witty remarks throughout the film were great it was just brilliant so much that i bought the film as soon as it was released for ? and would recommend it to everyone to watch and the fly fishing was amazing really cried at the end it was so sad and you know what they say if you cry at a film it must have been good and this definitely was also ? to the two little boy's that played the ? of norman and paul they were just brilliant children are often left out of the ? list i think because the stars that play them all grown up are such a big profile for the whole film but these children are amazing and should be praised for what they have done don't you think the whole story was so lovely because it was true and was someone's life after all that was shared with us all

Preparing the data

You can’t feed lists of integers into a neural network. You have to turn your lists into tensors. There are two ways to do that:

Let’s go with the latter solution and vectorize the data, which you’ll do manually for maximum clarity.

vectorize_sequences <- function(sequences, dimension = 10000) {
  # Create an all-zero matrix of shape (len(sequences), dimension)
  results <- matrix(0, nrow = length(sequences), ncol = dimension)
  for (i in 1:length(sequences))
    # Sets specific indices of results[i] to 1s
    results[i, sequences[[i]]] <- 1
  results
}
# Our vectorized training data
x_train <- vectorize_sequences(train_data)
# Our vectorized test data
x_test <- vectorize_sequences(test_data)

Here’s what our samples look like now:

str(x_train[1,])
 num [1:10000] 1 1 0 1 1 1 1 1 1 0 ...

We should also vectorize our labels, which is straightforward:

# Our vectorized labels
y_train <- as.numeric(train_labels)
y_test <- as.numeric(test_labels)

Now our data is ready to be fed into a neural network.

Building our network

The input data is vectors, and the labels are scalars (1s and 0s): this is the easiest setup you’ll ever encounter. A type of network that performs well on such a problem is a simple stack of fully connected (“dense”) layers with relu activations: layer_dense(units = 16, activation = "relu").

The argument being passed to each dense layer (16) is the number of hidden units of the layer. A hidden unit is a dimension in the representation space of the layer. You may remember from chapter 2 that each such dense layer with a relu activation implements the following chain of tensor operations:

output = relu(dot(W, input) + b)

Having 16 hidden units means that the weight matrix W will have shape (input_dimension, 16), i.e. the dot product with W will project the input data onto a 16-dimensional representation space (and then we would add the bias vector b and apply the relu operation). You can intuitively understand the dimensionality of your representation space as “how much freedom you are allowing the network to have when learning internal representations”. Having more hidden units (a higher-dimensional representation space) allows your network to learn more complex representations, but it makes your network more computationally expensive and may lead to learning unwanted patterns (patterns that will improve performance on the training data but not on the test data).

There are two key architecture decisions to be made about such stack of dense layers:

In the next chapter, you will learn formal principles to guide you in making these choices. For the time being, you will have to trust us with the following architecture choice: two intermediate layers with 16 hidden units each, and a third layer which will output the scalar prediction regarding the sentiment of the current review. The intermediate layers will use relu as their “activation function”, and the final layer will use a sigmoid activation so as to output a probability (a score between 0 and 1, indicating how likely the sample is to have the target “1”, i.e. how likely the review is to be positive). A relu (rectified linear unit) is a function meant to zero-out negative values, while a sigmoid “squashes” arbitrary values into the [0, 1] interval, thus outputting something that can be interpreted as a probability.

Here’s what our network looks like:

3-layer network

3-layer network

And here’s the Keras implementation, very similar to the MNIST example you saw previously:

library(keras)
model <- keras_model_sequential() %>% 
  layer_dense(units = 16, activation = "relu", input_shape = c(10000)) %>% 
  layer_dense(units = 16, activation = "relu") %>% 
  layer_dense(units = 1, activation = "sigmoid")

Lastly, we need to pick a loss function and an optimizer. Since we are facing a binary classification problem and the output of our network is a probability (we end our network with a single-unit layer with a sigmoid activation), is it best to use the binary_crossentropy loss. It isn’t the only viable choice: you could use, for instance, mean_squared_error. But crossentropy is usually the best choice when you are dealing with models that output probabilities. Crossentropy is a quantity from the field of Information Theory, that measures the “distance” between probability distributions, or in our case, between the ground-truth distribution and our predictions.

Here’s the step where we configure our model with the rmsprop optimizer and the binary_crossentropy loss function. Note that we will also monitor accuracy during training.

model %>% compile(
  optimizer = "rmsprop",
  loss = "binary_crossentropy",
  metrics = c("accuracy")
)

You’re passing your optimizer, loss function, and metrics as strings, which is possible because rmsprop, binary_crossentropy, and accuracy are packaged as part of Keras. Sometimes you may want to configure the parameters of your optimizer or pass a custom loss function or metric function. The former can be done by passing an optimizer instance as the optimizer argument:

model %>% compile(
  optimizer = optimizer_rmsprop(lr=0.001),
  loss = "binary_crossentropy",
  metrics = c("accuracy")
) 

The latter can be done by passing function objects as the loss or metrics arguments:

model %>% compile(
  optimizer = optimizer_rmsprop(lr = 0.001),
  loss = loss_binary_crossentropy,
  metrics = metric_binary_accuracy
) 

Validating our approach

In order to monitor during training the accuracy of the model on data that it has never seen before, we will create a “validation set” by setting apart 10,000 samples from the original training data:

val_indices <- 1:10000
x_val <- x_train[val_indices,]
partial_x_train <- x_train[-val_indices,]
y_val <- y_train[val_indices]
partial_y_train <- y_train[-val_indices]

We will now train our model for 20 epochs (20 iterations over all samples in the x_train and y_train tensors), in mini-batches of 512 samples. At this same time we will monitor loss and accuracy on the 10,000 samples that we set apart. This is done by passing the validation data as the validation_data argument:

On CPU, this will take less than two seconds per epoch – training is over in 20 seconds. At the end of every epoch, there is a slight pause as the model computes its loss and accuracy on the 10,000 samples of the validation data.

Note that the call to fit() returns a history object. Let’s take a look at it:

str(history)
List of 2
 $ params :List of 8
  ..$ metrics           : chr [1:4] "loss" "acc" "val_loss" "val_acc"
  ..$ epochs            : int 20
  ..$ steps             : NULL
  ..$ do_validation     : logi TRUE
  ..$ samples           : int 15000
  ..$ batch_size        : int 512
  ..$ verbose           : int 1
  ..$ validation_samples: int 10000
 $ metrics:List of 4
  ..$ acc     : num [1:20] 0.785 0.904 0.93 0.943 0.954 ...
  ..$ loss    : num [1:20] 0.507 0.299 0.216 0.174 0.141 ...
  ..$ val_acc : num [1:20] 0.869 0.89 0.88 0.888 0.887 ...
  ..$ val_loss: num [1:20] 0.379 0.299 0.3 0.279 0.283 ...
 - attr(*, "class")= chr "keras_training_history"

The history object includes various parameters used to fit the model (history$params) as well as data for each of the metrics being monitored (history$metrics).

The history object has a plot() method that enables us to visualize the training and validation metrics by epoch:

plot(history)

The accuracy is plotted on the top panel and the loss on the bottom panel. Note that your own results may vary slightly due to a different random initialization of your network.

The dots are the training loss and accuracy, while the solid lines are the validation loss and accuracy. Note that your own results may vary slightly due to a different random initialization of your network.

As you can see, the training loss decreases with every epoch, and the training accuracy increases with every epoch. That’s what you would expect when running a gradient-descent optimization – the quantity you’re trying to minimize should be less with every iteration. But that isn’t the case for the validation loss and accuracy: they seem to peak at the fourth epoch. This is an example of what we warned against earlier: a model that performs better on the training data isn’t necessarily a model that will do better on data it has never seen before. In precise terms, what you’re seeing is overfitting: after the second epoch, you’re over-optimizing on the training data, and you end up learning representations that are specific to the training data and don’t generalize to data outside of the training set.

In this case, to prevent overfitting, you could stop training after three epochs. In general, you can use a range of techniques to mitigate overfitting, which we’ll cover in chapter 4.

Let’s train a new network from scratch for four epochs and then evaluate it on the test data.

model <- keras_model_sequential() %>% 
  layer_dense(units = 16, activation = "relu", input_shape = c(10000)) %>% 
  layer_dense(units = 16, activation = "relu") %>% 
  layer_dense(units = 1, activation = "sigmoid")
model %>% compile(
  optimizer = "rmsprop",
  loss = "binary_crossentropy",
  metrics = c("accuracy")
)
model %>% fit(x_train, y_train, epochs = 4, batch_size = 512)
results <- model %>% evaluate(x_test, y_test)
results
$loss
[1] 0.305657

$acc
[1] 0.87828

Our fairly naive approach achieves an accuracy of 88%. With state-of-the-art approaches, one should be able to get close to 95%.

Using a trained network to generate predictions on new data

After having trained a network, you’ll want to use it in a practical setting. You can generate the likelihood of reviews being positive by using the predict method:

model %>% predict(x_test[1:10,])
            [,1]
 [1,] 0.17220633
 [2,] 0.99992836
 [3,] 0.71722800
 [4,] 0.62230968
 [5,] 0.92568231
 [6,] 0.74008137
 [7,] 0.99818629
 [8,] 0.01314448
 [9,] 0.95776796
[10,] 0.97449195

As you can see, the network is very confident for some samples (0.99 or more, or 0.02 or less) but less confident for others.

Further experiments

These experiments will help convince you that the architecture choices we have made are all fairly reasonable, although they can still be improved!

Conclusions

Here’s what you should take away from this example:

LS0tCnRpdGxlOiAiQ2xhc3NpZnlpbmcgbW92aWUgcmV2aWV3czogYSBiaW5hcnkgY2xhc3NpZmljYXRpb24gZXhhbXBsZSIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOiAKICAgIHRoZW1lOiBjZXJ1bGVhbgogICAgaGlnaGxpZ2h0OiB0ZXh0bWF0ZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQod2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UpCmBgYAoKKioqCgpUaGlzIG5vdGVib29rIGNvbnRhaW5zIHRoZSBjb2RlIHNhbXBsZXMgZm91bmQgaW4gQ2hhcHRlciAzLCBTZWN0aW9uIDUgb2YgW0RlZXAgTGVhcm5pbmcgd2l0aCBSXShodHRwczovL3d3dy5tYW5uaW5nLmNvbS9ib29rcy9kZWVwLWxlYXJuaW5nLXdpdGgtcikuIE5vdGUgdGhhdCB0aGUgb3JpZ2luYWwgdGV4dCBmZWF0dXJlcyBmYXIgbW9yZSBjb250ZW50LCBpbiBwYXJ0aWN1bGFyIGZ1cnRoZXIgZXhwbGFuYXRpb25zIGFuZCBmaWd1cmVzOiBpbiB0aGlzIG5vdGVib29rLCB5b3Ugd2lsbCBvbmx5IGZpbmQgc291cmNlIGNvZGUgYW5kIHJlbGF0ZWQgY29tbWVudHMuCgoqKioKClR3by1jbGFzcyBjbGFzc2lmaWNhdGlvbiwgb3IgYmluYXJ5IGNsYXNzaWZpY2F0aW9uLCBtYXkgYmUgdGhlIG1vc3Qgd2lkZWx5IGFwcGxpZWQga2luZCBvZiBtYWNoaW5lIGxlYXJuaW5nIHByb2JsZW0uIEluIHRoaXMgZXhhbXBsZSwgd2Ugd2lsbCBsZWFybiB0byBjbGFzc2lmeSBtb3ZpZSByZXZpZXdzIGludG8gInBvc2l0aXZlIiByZXZpZXdzIGFuZCAibmVnYXRpdmUiIHJldmlld3MsIGp1c3QgYmFzZWQgb24gdGhlIHRleHQgY29udGVudCBvZiB0aGUgcmV2aWV3cy4KCiMjIFRoZSBJTURCIGRhdGFzZXQKCgpXZSdsbCBiZSB3b3JraW5nIHdpdGggIklNREIgZGF0YXNldCIsIGEgc2V0IG9mIDUwLDAwMCBoaWdobHktcG9sYXJpemVkIHJldmlld3MgZnJvbSB0aGUgSW50ZXJuZXQgTW92aWUgRGF0YWJhc2UuIFRoZXkgYXJlIHNwbGl0IGludG8gMjUsMDAwIHJldmlld3MgZm9yIHRyYWluaW5nIGFuZCAyNSwwMDAgcmV2aWV3cyBmb3IgdGVzdGluZywgZWFjaCBzZXQgY29uc2lzdGluZyBpbiA1MCUgbmVnYXRpdmUgYW5kIDUwJSBwb3NpdGl2ZSByZXZpZXdzLgoKV2h5IGRvIHdlIGhhdmUgdGhlc2UgdHdvIHNlcGFyYXRlIHRyYWluaW5nIGFuZCB0ZXN0IHNldHM/IFlvdSBzaG91bGQgbmV2ZXIgdGVzdCBhIG1hY2hpbmUgbGVhcm5pbmcgbW9kZWwgb24gdGhlIHNhbWUgZGF0YSB0aGF0IHlvdSB1c2VkIHRvIHRyYWluIGl0ISBKdXN0IGJlY2F1c2UgYSBtb2RlbCBwZXJmb3JtcyB3ZWxsIG9uIGl0cyB0cmFpbmluZyBkYXRhIGRvZXNuJ3QgbWVhbiB0aGF0IGl0IHdpbGwgcGVyZm9ybSB3ZWxsIG9uIGRhdGEgaXQgaGFzIG5ldmVyIHNlZW4sIGFuZCB3aGF0IHlvdSBhY3R1YWxseSBjYXJlIGFib3V0IGlzIHlvdXIgbW9kZWwncyBwZXJmb3JtYW5jZSBvbiBuZXcgZGF0YSAoc2luY2UgeW91IGFscmVhZHkga25vdyB0aGUgbGFiZWxzIG9mIHlvdXIgdHJhaW5pbmcgZGF0YSAtLSBvYnZpb3VzbHkgeW91IGRvbid0IG5lZWQgeW91ciBtb2RlbCB0byBwcmVkaWN0IHRob3NlKS4gRm9yIGluc3RhbmNlLCBpdCBpcyBwb3NzaWJsZSB0aGF0IHlvdXIgbW9kZWwgY291bGQgZW5kIHVwIG1lcmVseSBfbWVtb3JpemluZ18gYSBtYXBwaW5nIGJldHdlZW4geW91ciB0cmFpbmluZyBzYW1wbGVzIGFuZCB0aGVpciB0YXJnZXRzIC0tIHdoaWNoIHdvdWxkIGJlIGNvbXBsZXRlbHkgdXNlbGVzcyBmb3IgdGhlIHRhc2sgb2YgcHJlZGljdGluZyB0YXJnZXRzIGZvciBkYXRhIG5ldmVyIHNlZW4gYmVmb3JlLiBXZSB3aWxsIGdvIG92ZXIgdGhpcyBwb2ludCBpbiBtdWNoIG1vcmUgZGV0YWlsIGluIHRoZSBuZXh0IGNoYXB0ZXIuCgpKdXN0IGxpa2UgdGhlIE1OSVNUIGRhdGFzZXQsIHRoZSBJTURCIGRhdGFzZXQgY29tZXMgcGFja2FnZWQgd2l0aCBLZXJhcy4gSXQgaGFzIGFscmVhZHkgYmVlbiBwcmVwcm9jZXNzZWQ6IHRoZSByZXZpZXdzIChzZXF1ZW5jZXMgb2Ygd29yZHMpIGhhdmUgYmVlbiB0dXJuZWQgaW50byBzZXF1ZW5jZXMgb2YgaW50ZWdlcnMsIHdoZXJlIGVhY2ggaW50ZWdlciBzdGFuZHMgZm9yIGEgc3BlY2lmaWMgd29yZCBpbiBhIGRpY3Rpb25hcnkuCgpUaGUgZm9sbG93aW5nIGNvZGUgd2lsbCBsb2FkIHRoZSBkYXRhc2V0ICh3aGVuIHlvdSBydW4gaXQgZm9yIHRoZSBmaXJzdCB0aW1lLCBhYm91dCA4ME1CIG9mIGRhdGEgd2lsbCBiZSBkb3dubG9hZGVkIHRvIHlvdXIgbWFjaGluZSk6CgpgYGB7ciwgcmVzdWx0cz0naGlkZSd9CmxpYnJhcnkoa2VyYXMpCgppbWRiIDwtIGRhdGFzZXRfaW1kYihudW1fd29yZHMgPSAxMDAwMCkKYyhjKHRyYWluX2RhdGEsIHRyYWluX2xhYmVscyksIGModGVzdF9kYXRhLCB0ZXN0X2xhYmVscykpICU8LSUgaW1kYgpgYGAKClRoZSBhcmd1bWVudCBgbnVtX3dvcmRzID0gMTAwMDBgIG1lYW5zIHRoYXQgd2Ugd2lsbCBvbmx5IGtlZXAgdGhlIHRvcCAxMCwwMDAgbW9zdCBmcmVxdWVudGx5IG9jY3VycmluZyB3b3JkcyBpbiB0aGUgdHJhaW5pbmcgZGF0YS4gUmFyZSB3b3JkcyB3aWxsIGJlIGRpc2NhcmRlZC4gVGhpcyBhbGxvd3MgdXMgdG8gd29yayB3aXRoIHZlY3RvciBkYXRhIG9mIG1hbmFnZWFibGUgc2l6ZS4KClRoZSB2YXJpYWJsZXMgYHRyYWluX2RhdGFgIGFuZCBgdGVzdF9kYXRhYCBhcmUgbGlzdHMgb2YgcmV2aWV3cywgZWFjaCByZXZpZXcgYmVpbmcgYSBsaXN0IG9mIHdvcmQgaW5kaWNlcyAoZW5jb2RpbmcgYSBzZXF1ZW5jZSBvZiB3b3JkcykuIGB0cmFpbl9sYWJlbHNgIGFuZCBgdGVzdF9sYWJlbHNgIGFyZSBsaXN0cyBvZiAwcyBhbmQgMXMsIHdoZXJlIDAgc3RhbmRzIGZvciAibmVnYXRpdmUiIGFuZCAxIHN0YW5kcyBmb3IgInBvc2l0aXZlIjoKCmBgYHtyfQpzdHIodHJhaW5fZGF0YVtbMV1dKQpgYGAKCmBgYHtyfQp0cmFpbl9sYWJlbHNbWzFdXQpgYGAKClNpbmNlIHdlIHJlc3RyaWN0ZWQgb3Vyc2VsdmVzIHRvIHRoZSB0b3AgMTAsMDAwIG1vc3QgZnJlcXVlbnQgd29yZHMsIG5vIHdvcmQgaW5kZXggd2lsbCBleGNlZWQgMTAsMDAwOgoKYGBge3J9Cm1heChzYXBwbHkodHJhaW5fZGF0YSwgbWF4KSkKYGBgCgpGb3Iga2lja3MsIGhlcmUncyBob3cgeW91IGNhbiBxdWlja2x5IGRlY29kZSBvbmUgb2YgdGhlc2UgcmV2aWV3cyBiYWNrIHRvIEVuZ2xpc2ggd29yZHM6CgpgYGB7cn0KIyB3b3JkX2luZGV4IGlzIGEgZGljdGlvbmFyeSBtYXBwaW5nIHdvcmRzIHRvIGFuIGludGVnZXIgaW5kZXgKd29yZF9pbmRleCA8LSBkYXRhc2V0X2ltZGJfd29yZF9pbmRleCgpCiMgV2UgcmV2ZXJzZSBpdCwgbWFwcGluZyBpbnRlZ2VyIGluZGljZXMgdG8gd29yZHMKcmV2ZXJzZV93b3JkX2luZGV4IDwtIG5hbWVzKHdvcmRfaW5kZXgpCm5hbWVzKHJldmVyc2Vfd29yZF9pbmRleCkgPC0gd29yZF9pbmRleAojIFdlIGRlY29kZSB0aGUgcmV2aWV3OyBub3RlIHRoYXQgb3VyIGluZGljZXMgd2VyZSBvZmZzZXQgYnkgMwojIGJlY2F1c2UgMCwgMSBhbmQgMiBhcmUgcmVzZXJ2ZWQgaW5kaWNlcyBmb3IgInBhZGRpbmciLCAic3RhcnQgb2Ygc2VxdWVuY2UiLCBhbmQgInVua25vd24iLgpkZWNvZGVkX3JldmlldyA8LSBzYXBwbHkodHJhaW5fZGF0YVtbMV1dLCBmdW5jdGlvbihpbmRleCkgewogIHdvcmQgPC0gaWYgKGluZGV4ID49IDMpIHJldmVyc2Vfd29yZF9pbmRleFtbYXMuY2hhcmFjdGVyKGluZGV4IC0gMyldXQogIGlmICghaXMubnVsbCh3b3JkKSkgd29yZCBlbHNlICI/Igp9KQpgYGAKCmBgYHtyfQpjYXQoZGVjb2RlZF9yZXZpZXcpCmBgYAoKIyMgUHJlcGFyaW5nIHRoZSBkYXRhCgoKWW91IGNhbid0IGZlZWQgbGlzdHMgb2YgaW50ZWdlcnMgaW50byBhIG5ldXJhbCBuZXR3b3JrLiBZb3UgaGF2ZSB0byB0dXJuIHlvdXIgbGlzdHMgaW50byB0ZW5zb3JzLiBUaGVyZSBhcmUgdHdvIHdheXMgdG8gZG8gdGhhdDoKCiogUGFkIHlvdXIgbGlzdHMgc28gdGhhdCB0aGV5IGFsbCBoYXZlIHRoZSBzYW1lIGxlbmd0aCwgdHVybiB0aGVtIGludG8gYW4gaW50ZWdlciB0ZW5zb3Igb2Ygc2hhcGUgYChzYW1wbGVzLCB3b3JkX2luZGljZXMpYCwgYW5kIHRoZW4gdXNlIGFzIHRoZSBmaXJzdCBsYXllciBpbiB5b3VyIG5ldHdvcmsgYSBsYXllciBjYXBhYmxlIG9mIGhhbmRsaW5nIHN1Y2ggaW50ZWdlciB0ZW5zb3JzICh0aGUgImVtYmVkZGluZyIgbGF5ZXIsIHdoaWNoIHdlJ2xsIGNvdmVyIGluIGRldGFpbCBsYXRlciBpbiB0aGUgYm9vaykuCiogT25lLWhvdC1lbmNvZGUgeW91ciBsaXN0cyB0byB0dXJuIHRoZW0gaW50byB2ZWN0b3JzIG9mIDBzIGFuZCAxcy4gVGhpcyB3b3VsZCBtZWFuLCBmb3IgaW5zdGFuY2UsIHR1cm5pbmcgdGhlIHNlcXVlbmNlIGBbMywgNV1gIGludG8gYSAxMCwwMDAtZGltZW5zaW9uYWwgdmVjdG9yIHRoYXQgd291bGQgYmUgYWxsIHplcm9zIGV4Y2VwdCBmb3IgaW5kaWNlcyAzIGFuZCA1LCB3aGljaCB3b3VsZCBiZSBvbmVzLiBUaGVuIHlvdSBjb3VsZCB1c2UgYXMgdGhlIGZpcnN0IGxheWVyIGluIHlvdXIgbmV0d29yayBhIGRlbnNlIGxheWVyLCBjYXBhYmxlIG9mIGhhbmRsaW5nIGZsb2F0aW5nLXBvaW50IHZlY3RvciBkYXRhLgoKTGV0J3MgZ28gd2l0aCB0aGUgbGF0dGVyIHNvbHV0aW9uIGFuZCB2ZWN0b3JpemUgdGhlIGRhdGEsIHdoaWNoIHlvdSdsbCBkbyBtYW51YWxseSBmb3IgbWF4aW11bSBjbGFyaXR5LgoKYGBge3J9CnZlY3Rvcml6ZV9zZXF1ZW5jZXMgPC0gZnVuY3Rpb24oc2VxdWVuY2VzLCBkaW1lbnNpb24gPSAxMDAwMCkgewogICMgQ3JlYXRlIGFuIGFsbC16ZXJvIG1hdHJpeCBvZiBzaGFwZSAobGVuKHNlcXVlbmNlcyksIGRpbWVuc2lvbikKICByZXN1bHRzIDwtIG1hdHJpeCgwLCBucm93ID0gbGVuZ3RoKHNlcXVlbmNlcyksIG5jb2wgPSBkaW1lbnNpb24pCiAgZm9yIChpIGluIDE6bGVuZ3RoKHNlcXVlbmNlcykpCiAgICAjIFNldHMgc3BlY2lmaWMgaW5kaWNlcyBvZiByZXN1bHRzW2ldIHRvIDFzCiAgICByZXN1bHRzW2ksIHNlcXVlbmNlc1tbaV1dXSA8LSAxCiAgcmVzdWx0cwp9CgojIE91ciB2ZWN0b3JpemVkIHRyYWluaW5nIGRhdGEKeF90cmFpbiA8LSB2ZWN0b3JpemVfc2VxdWVuY2VzKHRyYWluX2RhdGEpCiMgT3VyIHZlY3Rvcml6ZWQgdGVzdCBkYXRhCnhfdGVzdCA8LSB2ZWN0b3JpemVfc2VxdWVuY2VzKHRlc3RfZGF0YSkKYGBgCgpIZXJlJ3Mgd2hhdCBvdXIgc2FtcGxlcyBsb29rIGxpa2Ugbm93OgoKYGBge3J9CnN0cih4X3RyYWluWzEsXSkKYGBgCgpXZSBzaG91bGQgYWxzbyB2ZWN0b3JpemUgb3VyIGxhYmVscywgd2hpY2ggaXMgc3RyYWlnaHRmb3J3YXJkOgoKYGBge3J9CiMgT3VyIHZlY3Rvcml6ZWQgbGFiZWxzCnlfdHJhaW4gPC0gYXMubnVtZXJpYyh0cmFpbl9sYWJlbHMpCnlfdGVzdCA8LSBhcy5udW1lcmljKHRlc3RfbGFiZWxzKQpgYGAKCk5vdyBvdXIgZGF0YSBpcyByZWFkeSB0byBiZSBmZWQgaW50byBhIG5ldXJhbCBuZXR3b3JrLgoKIyMgQnVpbGRpbmcgb3VyIG5ldHdvcmsKClRoZSBpbnB1dCBkYXRhIGlzIHZlY3RvcnMsIGFuZCB0aGUgbGFiZWxzIGFyZSBzY2FsYXJzICgxcyBhbmQgMHMpOiB0aGlzIGlzIHRoZSBlYXNpZXN0IHNldHVwIHlvdSdsbCBldmVyIGVuY291bnRlci4gQSB0eXBlIG9mIG5ldHdvcmsgdGhhdCBwZXJmb3JtcyB3ZWxsIG9uIHN1Y2ggYSBwcm9ibGVtIGlzIGEgc2ltcGxlIHN0YWNrIG9mIGZ1bGx5IGNvbm5lY3RlZCAoImRlbnNlIikgbGF5ZXJzIHdpdGggYHJlbHVgIGFjdGl2YXRpb25zOiBgbGF5ZXJfZGVuc2UodW5pdHMgPSAxNiwgYWN0aXZhdGlvbiA9ICJyZWx1IilgLgoKVGhlIGFyZ3VtZW50IGJlaW5nIHBhc3NlZCB0byBlYWNoIGRlbnNlIGxheWVyICgxNikgaXMgdGhlIG51bWJlciBvZiBoaWRkZW4gdW5pdHMgb2YgdGhlIGxheWVyLiBBIF9oaWRkZW4gdW5pdF8gaXMgYSBkaW1lbnNpb24gaW4gdGhlIHJlcHJlc2VudGF0aW9uIHNwYWNlIG9mIHRoZSBsYXllci4gWW91IG1heSByZW1lbWJlciBmcm9tIGNoYXB0ZXIgMiB0aGF0IGVhY2ggc3VjaCBkZW5zZSBsYXllciB3aXRoIGEgYHJlbHVgIGFjdGl2YXRpb24gaW1wbGVtZW50cyB0aGUgZm9sbG93aW5nIGNoYWluIG9mIHRlbnNvciBvcGVyYXRpb25zOgoKYG91dHB1dCA9IHJlbHUoZG90KFcsIGlucHV0KSArIGIpYAoKSGF2aW5nIDE2IGhpZGRlbiB1bml0cyBtZWFucyB0aGF0IHRoZSB3ZWlnaHQgbWF0cml4IGBXYCB3aWxsIGhhdmUgc2hhcGUgYChpbnB1dF9kaW1lbnNpb24sIDE2KWAsIGkuZS4gdGhlIGRvdCBwcm9kdWN0IHdpdGggYFdgIHdpbGwgcHJvamVjdCB0aGUgaW5wdXQgZGF0YSBvbnRvIGEgMTYtZGltZW5zaW9uYWwgcmVwcmVzZW50YXRpb24gc3BhY2UgKGFuZCB0aGVuIHdlIHdvdWxkIGFkZCB0aGUgYmlhcyB2ZWN0b3IgYGJgIGFuZCBhcHBseSB0aGUgYHJlbHVgIG9wZXJhdGlvbikuIFlvdSBjYW4gaW50dWl0aXZlbHkgdW5kZXJzdGFuZCB0aGUgZGltZW5zaW9uYWxpdHkgb2YgeW91ciByZXByZXNlbnRhdGlvbiBzcGFjZSBhcyAiaG93IG11Y2ggZnJlZWRvbSB5b3UgYXJlIGFsbG93aW5nIHRoZSBuZXR3b3JrIHRvIGhhdmUgd2hlbiBsZWFybmluZyBpbnRlcm5hbCByZXByZXNlbnRhdGlvbnMiLiBIYXZpbmcgbW9yZSBoaWRkZW4gdW5pdHMgKGEgaGlnaGVyLWRpbWVuc2lvbmFsIHJlcHJlc2VudGF0aW9uIHNwYWNlKSBhbGxvd3MgeW91ciBuZXR3b3JrIHRvIGxlYXJuIG1vcmUgY29tcGxleCByZXByZXNlbnRhdGlvbnMsIGJ1dCBpdCBtYWtlcyB5b3VyIG5ldHdvcmsgbW9yZSBjb21wdXRhdGlvbmFsbHkgZXhwZW5zaXZlIGFuZCBtYXkgbGVhZCB0byBsZWFybmluZyB1bndhbnRlZCBwYXR0ZXJucyAocGF0dGVybnMgdGhhdCB3aWxsIGltcHJvdmUgcGVyZm9ybWFuY2Ugb24gdGhlIHRyYWluaW5nIGRhdGEgYnV0IG5vdCBvbiB0aGUgdGVzdCBkYXRhKS4KClRoZXJlIGFyZSB0d28ga2V5IGFyY2hpdGVjdHVyZSBkZWNpc2lvbnMgdG8gYmUgbWFkZSBhYm91dCBzdWNoIHN0YWNrIG9mIGRlbnNlIGxheWVyczoKCiogSG93IG1hbnkgbGF5ZXJzIHRvIHVzZS4KKiBIb3cgbWFueSAiaGlkZGVuIHVuaXRzIiB0byBjaG9zZSBmb3IgZWFjaCBsYXllci4KCkluIHRoZSBuZXh0IGNoYXB0ZXIsIHlvdSB3aWxsIGxlYXJuIGZvcm1hbCBwcmluY2lwbGVzIHRvIGd1aWRlIHlvdSBpbiBtYWtpbmcgdGhlc2UgY2hvaWNlcy4gRm9yIHRoZSB0aW1lIGJlaW5nLCB5b3Ugd2lsbCBoYXZlIHRvIHRydXN0IHVzIHdpdGggdGhlIGZvbGxvd2luZyBhcmNoaXRlY3R1cmUgY2hvaWNlOiB0d28gaW50ZXJtZWRpYXRlIGxheWVycyB3aXRoIDE2IGhpZGRlbiB1bml0cyBlYWNoLCBhbmQgYSB0aGlyZCBsYXllciB3aGljaCB3aWxsIG91dHB1dCB0aGUgc2NhbGFyIHByZWRpY3Rpb24gcmVnYXJkaW5nIHRoZSBzZW50aW1lbnQgb2YgdGhlIGN1cnJlbnQgcmV2aWV3LiBUaGUgaW50ZXJtZWRpYXRlIGxheWVycyB3aWxsIHVzZSBgcmVsdWAgYXMgdGhlaXIgImFjdGl2YXRpb24gZnVuY3Rpb24iLCBhbmQgdGhlIGZpbmFsIGxheWVyIHdpbGwgdXNlIGEgc2lnbW9pZCBhY3RpdmF0aW9uIHNvIGFzIHRvIG91dHB1dCBhIHByb2JhYmlsaXR5IChhIHNjb3JlIGJldHdlZW4gMCBhbmQgMSwgaW5kaWNhdGluZyBob3cgbGlrZWx5IHRoZSBzYW1wbGUgaXMgdG8gaGF2ZSB0aGUgdGFyZ2V0ICIxIiwgaS5lLiBob3cgbGlrZWx5IHRoZSByZXZpZXcgaXMgdG8gYmUgcG9zaXRpdmUpLiBBIGByZWx1YCAocmVjdGlmaWVkIGxpbmVhciB1bml0KSBpcyBhIGZ1bmN0aW9uIG1lYW50IHRvIHplcm8tb3V0IG5lZ2F0aXZlIHZhbHVlcywgd2hpbGUgYSBzaWdtb2lkICJzcXVhc2hlcyIgYXJiaXRyYXJ5IHZhbHVlcyBpbnRvIHRoZSBgWzAsIDFdYCBpbnRlcnZhbCwgdGh1cyBvdXRwdXR0aW5nIHNvbWV0aGluZyB0aGF0IGNhbiBiZSBpbnRlcnByZXRlZCBhcyBhIHByb2JhYmlsaXR5LgoKSGVyZSdzIHdoYXQgb3VyIG5ldHdvcmsgbG9va3MgbGlrZToKCiFbMy1sYXllciBuZXR3b3JrXShodHRwczovL3MzLmFtYXpvbmF3cy5jb20vYm9vay5rZXJhcy5pby9pbWcvY2gzLzNfbGF5ZXJfbmV0d29yay5wbmcpCgpBbmQgaGVyZSdzIHRoZSBLZXJhcyBpbXBsZW1lbnRhdGlvbiwgdmVyeSBzaW1pbGFyIHRvIHRoZSBNTklTVCBleGFtcGxlIHlvdSBzYXcgcHJldmlvdXNseToKCmBgYHtyfQpsaWJyYXJ5KGtlcmFzKQoKbW9kZWwgPC0ga2VyYXNfbW9kZWxfc2VxdWVudGlhbCgpICU+JSAKICBsYXllcl9kZW5zZSh1bml0cyA9IDE2LCBhY3RpdmF0aW9uID0gInJlbHUiLCBpbnB1dF9zaGFwZSA9IGMoMTAwMDApKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSAxNiwgYWN0aXZhdGlvbiA9ICJyZWx1IikgJT4lIAogIGxheWVyX2RlbnNlKHVuaXRzID0gMSwgYWN0aXZhdGlvbiA9ICJzaWdtb2lkIikKYGBgCgpMYXN0bHksIHdlIG5lZWQgdG8gcGljayBhIGxvc3MgZnVuY3Rpb24gYW5kIGFuIG9wdGltaXplci4gU2luY2Ugd2UgYXJlIGZhY2luZyBhIGJpbmFyeSBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtIGFuZCB0aGUgb3V0cHV0IG9mIG91ciBuZXR3b3JrIGlzIGEgcHJvYmFiaWxpdHkgKHdlIGVuZCBvdXIgbmV0d29yayB3aXRoIGEgc2luZ2xlLXVuaXQgbGF5ZXIgd2l0aCBhIHNpZ21vaWQgYWN0aXZhdGlvbiksIGlzIGl0IGJlc3QgdG8gdXNlIHRoZSBgYmluYXJ5X2Nyb3NzZW50cm9weWAgbG9zcy4gSXQgaXNuJ3QgdGhlIG9ubHkgdmlhYmxlIGNob2ljZTogeW91IGNvdWxkIHVzZSwgZm9yIGluc3RhbmNlLCBgbWVhbl9zcXVhcmVkX2Vycm9yYC4gQnV0IGNyb3NzZW50cm9weSBpcyB1c3VhbGx5IHRoZSBiZXN0IGNob2ljZSB3aGVuIHlvdSBhcmUgZGVhbGluZyB3aXRoIG1vZGVscyB0aGF0IG91dHB1dCBwcm9iYWJpbGl0aWVzLiBDcm9zc2VudHJvcHkgaXMgYSBxdWFudGl0eSBmcm9tIHRoZSBmaWVsZCBvZiBJbmZvcm1hdGlvbiBUaGVvcnksIHRoYXQgbWVhc3VyZXMgdGhlICJkaXN0YW5jZSIgYmV0d2VlbiBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb25zLCBvciBpbiBvdXIgY2FzZSwgYmV0d2VlbiB0aGUgZ3JvdW5kLXRydXRoIGRpc3RyaWJ1dGlvbiBhbmQgb3VyIHByZWRpY3Rpb25zLgoKSGVyZSdzIHRoZSBzdGVwIHdoZXJlIHdlIGNvbmZpZ3VyZSBvdXIgbW9kZWwgd2l0aCB0aGUgYHJtc3Byb3BgIG9wdGltaXplciBhbmQgdGhlIGBiaW5hcnlfY3Jvc3NlbnRyb3B5YCBsb3NzIGZ1bmN0aW9uLiBOb3RlIHRoYXQgd2Ugd2lsbCBhbHNvIG1vbml0b3IgYWNjdXJhY3kgZHVyaW5nIHRyYWluaW5nLgoKYGBge3J9Cm1vZGVsICU+JSBjb21waWxlKAogIG9wdGltaXplciA9ICJybXNwcm9wIiwKICBsb3NzID0gImJpbmFyeV9jcm9zc2VudHJvcHkiLAogIG1ldHJpY3MgPSBjKCJhY2N1cmFjeSIpCikKYGBgCgpZb3UncmUgcGFzc2luZyB5b3VyIG9wdGltaXplciwgbG9zcyBmdW5jdGl