This notebook contains the code samples found in Chapter 3, Section 6 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.


In the previous section we saw how to classify vector inputs into two mutually exclusive classes using a densely-connected neural network. But what happens when you have more than two classes?

In this section, we will build a network to classify Reuters newswires into 46 different mutually-exclusive topics. Since we have many classes, this problem is an instance of “multi-class classification”, and since each data point should be classified into only one category, the problem is more specifically an instance of “single-label, multi-class classification”. If each data point could have belonged to multiple categories (in our case, topics) then we would be facing a “multi-label, multi-class classification” problem.

The Reuters dataset

We will be working with the Reuters dataset, a set of short newswires and their topics, published by Reuters in 1986. It’s a very simple, widely used toy dataset for text classification. There are 46 different topics; some topics are more represented than others, but each topic has at least 10 examples in the training set.

Like IMDB and MNIST, the Reuters dataset comes packaged as part of Keras. Let’s take a look right away:

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

Like with the IMDB dataset, the argument num_words = 10000 restricts the data to the 10,000 most frequently occurring words found in the data.

We have 8,982 training examples and 2,246 test examples:

length(train_data)
[1] 8982
length(test_data)
[1] 2246

As with the IMDB reviews, each example is a list of integers (word indices):

train_data[[1]]
 [1]    1    2    2    8   43   10  447    5   25  207  270    5 3095  111   16  369  186   90   67    7
[21]   89    5   19  102    6   19  124   15   90   67   84   22  482   26    7   48    4   49    8  864
[41]   39  209  154    6  151    6   83   11   15   22  155   11   15    7   48    9 4579 1005  504    6
[61]  258    6  272   11   15   22  134   44   11   15   16    8  197 1245   90   67   52   29  209   30
[81]   32  132    6  109   15   17   12

Here’s how you can decode it back to words, in case you are curious:

word_index <- dataset_reuters_word_index()
reverse_word_index <- names(word_index)
names(reverse_word_index) <- word_index
decoded_newswire <- sapply(train_data[[1]], function(index) {
  # Note that our indices were offset by 3 because 0, 1, and 2
  # are reserved indices for "padding", "start of sequence", and "unknown".
  word <- if (index >= 3) reverse_word_index[[as.character(index - 3)]]
  if (!is.null(word)) word else "?"
})
cat(decoded_newswire)
? ? ? said as a result of its december acquisition of space co it expects earnings per share in 1987 of 1 15 to 1 30 dlrs per share up from 70 cts in 1986 the company said pretax net should rise to nine to 10 mln dlrs from six mln dlrs in 1986 and rental operation revenues to 19 to 22 mln dlrs from 12 5 mln dlrs it said cash flow per share this year should be 2 50 to three dlrs reuter 3

The label associated with an example is an integer between 0 and 45: a topic index.

train_labels[[1]]
[1] 3

Preparing the data

We can vectorize the data with the exact same code as in our previous example:

vectorize_sequences <- function(sequences, dimension = 10000) {
  results <- matrix(0, nrow = length(sequences), ncol = dimension)
  for (i in 1:length(sequences))
    results[i, sequences[[i]]] <- 1
  results
}
x_train <- vectorize_sequences(train_data)
x_test <- vectorize_sequences(test_data)

To vectorize the labels, there are two possibilities: we could just cast the label list as an integer tensor, or we could use a “one-hot” encoding. One-hot encoding is a widely used format for categorical data, also called “categorical encoding”. For a more detailed explanation of one-hot encoding, you can refer to Chapter 6, Section 1. In our case, one-hot encoding of our labels consists in embedding each label as an all-zero vector with a 1 in the place of the label index, e.g.:

to_one_hot <- function(labels, dimension = 46) {
  results <- matrix(0, nrow = length(labels), ncol = dimension)
  for (i in 1:length(labels))
    results[i, labels[[i]] + 1] <- 1
  results
}
one_hot_train_labels <- to_one_hot(train_labels)
one_hot_test_labels <- to_one_hot(test_labels)

Note that there is a built-in way to do this in Keras, which you have already seen in action in our MNIST example:

one_hot_train_labels <- to_categorical(train_labels)
one_hot_test_labels <- to_categorical(test_labels)

Building our network

This topic classification problem looks very similar to our previous movie review classification problem: in both cases, we are trying to classify short snippets of text. There is however a new constraint here: the number of output classes has gone from 2 to 46, i.e. the dimensionality of the output space is much larger.

In a stack of dense layers like what we were using, each layer can only access information present in the output of the previous layer. If one layer drops some information relevant to the classification problem, this information can never be recovered by later layers: each layer can potentially become an “information bottleneck”. In our previous example, we were using 16-dimensional intermediate layers, but a 16-dimensional space may be too limited to learn to separate 46 different classes: such small layers may act as information bottlenecks, permanently dropping relevant information.

For this reason we will use larger layers. Let’s go with 64 units:

model <- keras_model_sequential() %>% 
  layer_dense(units = 64, activation = "relu", input_shape = c(10000)) %>% 
  layer_dense(units = 64, activation = "relu") %>% 
  layer_dense(units = 46, activation = "softmax")

There are two other things you should note about this architecture:

The best loss function to use in this case is categorical_crossentropy. It measures the distance between two probability distributions: in our case, between the probability distribution output by our network, and the true distribution of the labels. By minimizing the distance between these two distributions, we train our network to output something as close as possible to the true labels.

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

Validating our approach

Let’s set apart 1,000 samples in our training data to use as a validation set:

val_indices <- 1:1000
x_val <- x_train[val_indices,]
partial_x_train <- x_train[-val_indices,]
y_val <- one_hot_train_labels[val_indices,]
partial_y_train = one_hot_train_labels[-val_indices,]

Now let’s train our network for 20 epochs:

history <- model %>% fit(
  partial_x_train,
  partial_y_train,
  epochs = 20,
  batch_size = 512,
  validation_data = list(x_val, y_val)
)

Let’s display its loss and accuracy curves:

plot(history)

The network begins to overfit after nine epochs. Let’s train a new network from scratch for nine epochs and then evaluate it on the test set.

model <- keras_model_sequential() %>% 
  layer_dense(units = 64, activation = "relu", input_shape = c(10000)) %>% 
  layer_dense(units = 64, activation = "relu") %>% 
  layer_dense(units = 46, activation = "softmax")
  
model %>% compile(
  optimizer = "rmsprop",
  loss = "categorical_crossentropy",
  metrics = c("accuracy")
)
history <- model %>% fit(
  partial_x_train,
  partial_y_train,
  epochs = 9,
  batch_size = 512,
  validation_data = list(x_val, y_val)
)
results <- model %>% evaluate(x_test, one_hot_test_labels)
results
$loss
[1] 1.019141

$acc
[1] 0.7764915

Our approach reaches an accuracy of ~78%. With a balanced binary classification problem, the accuracy reached by a purely random classifier would be 50%, but in our case it is closer to 19%, so our results seem pretty good, at least when compared to a random baseline:

test_labels_copy <- test_labels
test_labels_copy <- sample(test_labels_copy)
length(which(test_labels == test_labels_copy)) / length(test_labels)
[1] 0.1892253

Generating predictions on new data

We can verify that the predict method of our model instance returns a probability distribution over all 46 topics. Let’s generate topic predictions for all of the test data:

predictions <- model %>% predict(x_test)

Each entry in predictions is a vector of length 46:

dim(predictions)
[1] 2246   46

The coefficients in this vector sum to 1:

sum(predictions[1,])
[1] 1

The largest entry is the predicted class, i.e. the class with the highest probability:

which.max(predictions[1,])
[1] 4

A different way to handle the labels and the loss

We mentioned earlier that another way to encode the labels would be to preserve their integer values. The only thing this approach would change is the choice of the loss function. The previous loss, categorical_crossentropy, expects the labels to follow a categorical encoding. With integer labels, you should use sparse_categorical_crossentropy:

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

This new loss function is still mathematically the same as categorical_crossentropy; it just has a different interface.

On the importance of having sufficiently large intermediate layers

We mentioned earlier that since our final outputs were 46-dimensional, we should avoid intermediate layers with much less than 46 hidden units. Now let’s try to see what happens when we introduce an information bottleneck by having intermediate layers significantly less than 46-dimensional, e.g. 4-dimensional.

model <- keras_model_sequential() %>% 
  layer_dense(units = 64, activation = "relu", input_shape = c(10000)) %>% 
  layer_dense(units = 4, activation = "relu") %>% 
  layer_dense(units = 46, activation = "softmax")
  
model %>% compile(
  optimizer = "rmsprop",
  loss = "categorical_crossentropy",
  metrics = c("accuracy")
)
model %>% fit(
  partial_x_train,
  partial_y_train,
  epochs = 20,
  batch_size = 128,
  validation_data = list(x_val, y_val)
)

Our network now seems to peak at ~71% test accuracy, a 8% absolute drop. This drop is mostly due to the fact that we are now trying to compress a lot of information (enough information to recover the separation hyperplanes of 46 classes) into an intermediate space that is too low-dimensional. The network is able to cram most of the necessary information into these 8-dimensional representations, but not all of it.

Further experiments

Wrapping up

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

LS0tCnRpdGxlOiAiQ2xhc3NpZnlpbmcgbmV3c3dpcmVzOiBhIG11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uIGV4YW1wbGUiCm91dHB1dDogCiAgaHRtbF9ub3RlYm9vazogCiAgICB0aGVtZTogY2VydWxlYW4KICAgIGhpZ2hsaWdodDogdGV4dG1hdGUKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFKQpgYGAKCioqKgoKVGhpcyBub3RlYm9vayBjb250YWlucyB0aGUgY29kZSBzYW1wbGVzIGZvdW5kIGluIENoYXB0ZXIgMywgU2VjdGlvbiA2IG9mIFtEZWVwIExlYXJuaW5nIHdpdGggUl0oaHR0cHM6Ly93d3cubWFubmluZy5jb20vYm9va3MvZGVlcC1sZWFybmluZy13aXRoLXIpLiBOb3RlIHRoYXQgdGhlIG9yaWdpbmFsIHRleHQgZmVhdHVyZXMgZmFyIG1vcmUgY29udGVudCwgaW4gcGFydGljdWxhciBmdXJ0aGVyIGV4cGxhbmF0aW9ucyBhbmQgZmlndXJlczogaW4gdGhpcyBub3RlYm9vaywgeW91IHdpbGwgb25seSBmaW5kIHNvdXJjZSBjb2RlIGFuZCByZWxhdGVkIGNvbW1lbnRzLgoKKioqCgpJbiB0aGUgcHJldmlvdXMgc2VjdGlvbiB3ZSBzYXcgaG93IHRvIGNsYXNzaWZ5IHZlY3RvciBpbnB1dHMgaW50byB0d28gbXV0dWFsbHkgZXhjbHVzaXZlIGNsYXNzZXMgdXNpbmcgYSBkZW5zZWx5LWNvbm5lY3RlZCBuZXVyYWwgbmV0d29yay4gQnV0IHdoYXQgaGFwcGVucyB3aGVuIHlvdSBoYXZlIG1vcmUgdGhhbiB0d28gY2xhc3Nlcz8gCgpJbiB0aGlzIHNlY3Rpb24sIHdlIHdpbGwgYnVpbGQgYSBuZXR3b3JrIHRvIGNsYXNzaWZ5IFJldXRlcnMgbmV3c3dpcmVzIGludG8gNDYgZGlmZmVyZW50IG11dHVhbGx5LWV4Y2x1c2l2ZSB0b3BpY3MuIFNpbmNlIHdlIGhhdmUgbWFueSBjbGFzc2VzLCB0aGlzIHByb2JsZW0gaXMgYW4gaW5zdGFuY2Ugb2YgIm11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uIiwgYW5kIHNpbmNlIGVhY2ggZGF0YSBwb2ludCBzaG91bGQgYmUgY2xhc3NpZmllZCBpbnRvIG9ubHkgb25lIGNhdGVnb3J5LCB0aGUgcHJvYmxlbSBpcyBtb3JlIHNwZWNpZmljYWxseSBhbiBpbnN0YW5jZSBvZiAic2luZ2xlLWxhYmVsLCBtdWx0aS1jbGFzcyBjbGFzc2lmaWNhdGlvbiIuIElmIGVhY2ggZGF0YSBwb2ludCBjb3VsZCBoYXZlIGJlbG9uZ2VkIHRvIG11bHRpcGxlIGNhdGVnb3JpZXMgKGluIG91ciBjYXNlLCB0b3BpY3MpIHRoZW4gd2Ugd291bGQgYmUgZmFjaW5nIGEgIm11bHRpLWxhYmVsLCBtdWx0aS1jbGFzcyBjbGFzc2lmaWNhdGlvbiIgcHJvYmxlbS4KCiMjIFRoZSBSZXV0ZXJzIGRhdGFzZXQKCgpXZSB3aWxsIGJlIHdvcmtpbmcgd2l0aCB0aGUgX1JldXRlcnMgZGF0YXNldF8sIGEgc2V0IG9mIHNob3J0IG5ld3N3aXJlcyBhbmQgdGhlaXIgdG9waWNzLCBwdWJsaXNoZWQgYnkgUmV1dGVycyBpbiAxOTg2LiBJdCdzIGEgdmVyeSBzaW1wbGUsIHdpZGVseSB1c2VkIHRveSBkYXRhc2V0IGZvciB0ZXh0IGNsYXNzaWZpY2F0aW9uLiBUaGVyZSBhcmUgNDYgZGlmZmVyZW50IHRvcGljczsgc29tZSB0b3BpY3MgYXJlIG1vcmUgcmVwcmVzZW50ZWQgdGhhbiBvdGhlcnMsIGJ1dCBlYWNoIHRvcGljIGhhcyBhdCBsZWFzdCAxMCBleGFtcGxlcyBpbiB0aGUgdHJhaW5pbmcgc2V0LgoKTGlrZSBJTURCIGFuZCBNTklTVCwgdGhlIFJldXRlcnMgZGF0YXNldCBjb21lcyBwYWNrYWdlZCBhcyBwYXJ0IG9mIEtlcmFzLiBMZXQncyB0YWtlIGEgbG9vayByaWdodCBhd2F5OgoKYGBge3J9CmxpYnJhcnkoa2VyYXMpCgpyZXV0ZXJzIDwtIGRhdGFzZXRfcmV1dGVycyhudW1fd29yZHMgPSAxMDAwMCkKYyhjKHRyYWluX2RhdGEsIHRyYWluX2xhYmVscyksIGModGVzdF9kYXRhLCB0ZXN0X2xhYmVscykpICU8LSUgcmV1dGVycwpgYGAKCkxpa2Ugd2l0aCB0aGUgSU1EQiBkYXRhc2V0LCB0aGUgYXJndW1lbnQgYG51bV93b3JkcyA9IDEwMDAwYCByZXN0cmljdHMgdGhlIGRhdGEgdG8gdGhlIDEwLDAwMCBtb3N0IGZyZXF1ZW50bHkgb2NjdXJyaW5nIHdvcmRzIGZvdW5kIGluIHRoZSBkYXRhLgoKV2UgaGF2ZSA4LDk4MiB0cmFpbmluZyBleGFtcGxlcyBhbmQgMiwyNDYgdGVzdCBleGFtcGxlczoKCmBgYHtyfQpsZW5ndGgodHJhaW5fZGF0YSkKYGBgCgpgYGB7cn0KbGVuZ3RoKHRlc3RfZGF0YSkKYGBgCgpBcyB3aXRoIHRoZSBJTURCIHJldmlld3MsIGVhY2ggZXhhbXBsZSBpcyBhIGxpc3Qgb2YgaW50ZWdlcnMgKHdvcmQgaW5kaWNlcyk6CgpgYGB7cn0KdHJhaW5fZGF0YVtbMV1dCmBgYAoKSGVyZSdzIGhvdyB5b3UgY2FuIGRlY29kZSBpdCBiYWNrIHRvIHdvcmRzLCBpbiBjYXNlIHlvdSBhcmUgY3VyaW91czoKCmBgYHtyfQp3b3JkX2luZGV4IDwtIGRhdGFzZXRfcmV1dGVyc193b3JkX2luZGV4KCkKcmV2ZXJzZV93b3JkX2luZGV4IDwtIG5hbWVzKHdvcmRfaW5kZXgpCm5hbWVzKHJldmVyc2Vfd29yZF9pbmRleCkgPC0gd29yZF9pbmRleApkZWNvZGVkX25ld3N3aXJlIDwtIHNhcHBseSh0cmFpbl9kYXRhW1sxXV0sIGZ1bmN0aW9uKGluZGV4KSB7CiAgIyBOb3RlIHRoYXQgb3VyIGluZGljZXMgd2VyZSBvZmZzZXQgYnkgMyBiZWNhdXNlIDAsIDEsIGFuZCAyCiAgIyBhcmUgcmVzZXJ2ZWQgaW5kaWNlcyBmb3IgInBhZGRpbmciLCAic3RhcnQgb2Ygc2VxdWVuY2UiLCBhbmQgInVua25vd24iLgogIHdvcmQgPC0gaWYgKGluZGV4ID49IDMpIHJldmVyc2Vfd29yZF9pbmRleFtbYXMuY2hhcmFjdGVyKGluZGV4IC0gMyldXQogIGlmICghaXMubnVsbCh3b3JkKSkgd29yZCBlbHNlICI/Igp9KQpgYGAKCmBgYHtyfQpjYXQoZGVjb2RlZF9uZXdzd2lyZSkKYGBgCgpUaGUgbGFiZWwgYXNzb2NpYXRlZCB3aXRoIGFuIGV4YW1wbGUgaXMgYW4gaW50ZWdlciBiZXR3ZWVuIDAgYW5kIDQ1OiBhIHRvcGljIGluZGV4LgoKYGBge3J9CnRyYWluX2xhYmVsc1tbMV1dCmBgYAoKIyMgUHJlcGFyaW5nIHRoZSBkYXRhCgpXZSBjYW4gdmVjdG9yaXplIHRoZSBkYXRhIHdpdGggdGhlIGV4YWN0IHNhbWUgY29kZSBhcyBpbiBvdXIgcHJldmlvdXMgZXhhbXBsZToKCmBgYHtyfQp2ZWN0b3JpemVfc2VxdWVuY2VzIDwtIGZ1bmN0aW9uKHNlcXVlbmNlcywgZGltZW5zaW9uID0gMTAwMDApIHsKICByZXN1bHRzIDwtIG1hdHJpeCgwLCBucm93ID0gbGVuZ3RoKHNlcXVlbmNlcyksIG5jb2wgPSBkaW1lbnNpb24pCiAgZm9yIChpIGluIDE6bGVuZ3RoKHNlcXVlbmNlcykpCiAgICByZXN1bHRzW2ksIHNlcXVlbmNlc1tbaV1dXSA8LSAxCiAgcmVzdWx0cwp9Cgp4X3RyYWluIDwtIHZlY3Rvcml6ZV9zZXF1ZW5jZXModHJhaW5fZGF0YSkKeF90ZXN0IDwtIHZlY3Rvcml6ZV9zZXF1ZW5jZXModGVzdF9kYXRhKQpgYGAKClRvIHZlY3Rvcml6ZSB0aGUgbGFiZWxzLCB0aGVyZSBhcmUgdHdvIHBvc3NpYmlsaXRpZXM6IHdlIGNvdWxkIGp1c3QgY2FzdCB0aGUgbGFiZWwgbGlzdCBhcyBhbiBpbnRlZ2VyIHRlbnNvciwgb3Igd2UgY291bGQgdXNlIGEgIm9uZS1ob3QiIGVuY29kaW5nLiBPbmUtaG90IGVuY29kaW5nIGlzIGEgd2lkZWx5IHVzZWQgZm9ybWF0IGZvciBjYXRlZ29yaWNhbCBkYXRhLCBhbHNvIGNhbGxlZCAiY2F0ZWdvcmljYWwgZW5jb2RpbmciLiBGb3IgYSBtb3JlIGRldGFpbGVkIGV4cGxhbmF0aW9uIG9mIG9uZS1ob3QgZW5jb2RpbmcsIHlvdSBjYW4gcmVmZXIgdG8gQ2hhcHRlciA2LCBTZWN0aW9uIDEuIEluIG91ciBjYXNlLCBvbmUtaG90IGVuY29kaW5nIG9mIG91ciBsYWJlbHMgY29uc2lzdHMgaW4gZW1iZWRkaW5nIGVhY2ggbGFiZWwgYXMgYW4gYWxsLXplcm8gdmVjdG9yIHdpdGggYSAxIGluIHRoZSBwbGFjZSBvZiB0aGUgbGFiZWwgaW5kZXgsIGUuZy46CgpgYGB7cn0KdG9fb25lX2hvdCA8LSBmdW5jdGlvbihsYWJlbHMsIGRpbWVuc2lvbiA9IDQ2KSB7CiAgcmVzdWx0cyA8LSBtYXRyaXgoMCwgbnJvdyA9IGxlbmd0aChsYWJlbHMpLCBuY29sID0gZGltZW5zaW9uKQogIGZvciAoaSBpbiAxOmxlbmd0aChsYWJlbHMpKQogICAgcmVzdWx0c1tpLCBsYWJlbHNbW2ldXSArIDFdIDwtIDEKICByZXN1bHRzCn0KCm9uZV9ob3RfdHJhaW5fbGFiZWxzIDwtIHRvX29uZV9ob3QodHJhaW5fbGFiZWxzKQpvbmVfaG90X3Rlc3RfbGFiZWxzIDwtIHRvX29uZV9ob3QodGVzdF9sYWJlbHMpCmBgYAoKTm90ZSB0aGF0IHRoZXJlIGlzIGEgYnVpbHQtaW4gd2F5IHRvIGRvIHRoaXMgaW4gS2VyYXMsIHdoaWNoIHlvdSBoYXZlIGFscmVhZHkgc2VlbiBpbiBhY3Rpb24gaW4gb3VyIE1OSVNUIGV4YW1wbGU6CgpgYGB7cn0Kb25lX2hvdF90cmFpbl9sYWJlbHMgPC0gdG9fY2F0ZWdvcmljYWwodHJhaW5fbGFiZWxzKQpvbmVfaG90X3Rlc3RfbGFiZWxzIDwtIHRvX2NhdGVnb3JpY2FsKHRlc3RfbGFiZWxzKQpgYGAKCiMjIEJ1aWxkaW5nIG91ciBuZXR3b3JrCgoKVGhpcyB0b3BpYyBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtIGxvb2tzIHZlcnkgc2ltaWxhciB0byBvdXIgcHJldmlvdXMgbW92aWUgcmV2aWV3IGNsYXNzaWZpY2F0aW9uIHByb2JsZW06IGluIGJvdGggY2FzZXMsIHdlIGFyZSB0cnlpbmcgdG8gY2xhc3NpZnkgc2hvcnQgc25pcHBldHMgb2YgdGV4dC4gVGhlcmUgaXMgaG93ZXZlciBhIG5ldyBjb25zdHJhaW50IGhlcmU6IHRoZSBudW1iZXIgb2Ygb3V0cHV0IGNsYXNzZXMgaGFzIGdvbmUgZnJvbSAyIHRvIDQ2LCBpLmUuIHRoZSBkaW1lbnNpb25hbGl0eSBvZiB0aGUgb3V0cHV0IHNwYWNlIGlzIG11Y2ggbGFyZ2VyLiAKCkluIGEgc3RhY2sgb2YgZGVuc2UgbGF5ZXJzIGxpa2Ugd2hhdCB3ZSB3ZXJlIHVzaW5nLCBlYWNoIGxheWVyIGNhbiBvbmx5IGFjY2VzcyBpbmZvcm1hdGlvbiBwcmVzZW50IGluIHRoZSBvdXRwdXQgb2YgdGhlIHByZXZpb3VzIGxheWVyLiBJZiBvbmUgbGF5ZXIgZHJvcHMgc29tZSBpbmZvcm1hdGlvbiByZWxldmFudCB0byB0aGUgY2xhc3NpZmljYXRpb24gcHJvYmxlbSwgdGhpcyBpbmZvcm1hdGlvbiBjYW4gbmV2ZXIgYmUgcmVjb3ZlcmVkIGJ5IGxhdGVyIGxheWVyczogZWFjaCBsYXllciBjYW4gcG90ZW50aWFsbHkgYmVjb21lIGFuICJpbmZvcm1hdGlvbiBib3R0bGVuZWNrIi4gSW4gb3VyIHByZXZpb3VzIGV4YW1wbGUsIHdlIHdlcmUgdXNpbmcgMTYtZGltZW5zaW9uYWwgaW50ZXJtZWRpYXRlIGxheWVycywgYnV0IGEgMTYtZGltZW5zaW9uYWwgc3BhY2UgbWF5IGJlIHRvbyBsaW1pdGVkIHRvIGxlYXJuIHRvIHNlcGFyYXRlIDQ2IGRpZmZlcmVudCBjbGFzc2VzOiBzdWNoIHNtYWxsIGxheWVycyBtYXkgYWN0IGFzIGluZm9ybWF0aW9uIGJvdHRsZW5lY2tzLCBwZXJtYW5lbnRseSBkcm9wcGluZyByZWxldmFudCBpbmZvcm1hdGlvbi4KCkZvciB0aGlzIHJlYXNvbiB3ZSB3aWxsIHVzZSBsYXJnZXIgbGF5ZXJzLiBMZXQncyBnbyB3aXRoIDY0IHVuaXRzOgoKYGBge3J9Cm1vZGVsIDwtIGtlcmFzX21vZGVsX3NlcXVlbnRpYWwoKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA2NCwgYWN0aXZhdGlvbiA9ICJyZWx1IiwgaW5wdXRfc2hhcGUgPSBjKDEwMDAwKSkgJT4lIAogIGxheWVyX2RlbnNlKHVuaXRzID0gNjQsIGFjdGl2YXRpb24gPSAicmVsdSIpICU+JSAKICBsYXllcl9kZW5zZSh1bml0cyA9IDQ2LCBhY3RpdmF0aW9uID0gInNvZnRtYXgiKQpgYGAKClRoZXJlIGFyZSB0d28gb3RoZXIgdGhpbmdzIHlvdSBzaG91bGQgbm90ZSBhYm91dCB0aGlzIGFyY2hpdGVjdHVyZToKCiogWW91IGVuZCB0aGUgbmV0d29yayB3aXRoIGEgZGVuc2UgbGF5ZXIgb2Ygc2l6ZSA0Ni4gVGhpcyBtZWFucyBmb3IgZWFjaCBpbnB1dCBzYW1wbGUsIHRoZSBuZXR3b3JrIHdpbGwgb3V0cHV0IGEgNDYtZGltZW5zaW9uYWwgdmVjdG9yLiBFYWNoIGVudHJ5IGluIHRoaXMgdmVjdG9yIChlYWNoIGRpbWVuc2lvbikgd2lsbCBlbmNvZGUgYSBkaWZmZXJlbnQgb3V0cHV0IGNsYXNzLgoKKiBUaGUgbGFzdCBsYXllciB1c2VzIGEgYHNvZnRtYXhgIGFjdGl2YXRpb24uIFlvdSBzYXcgdGhpcyBwYXR0ZXJuIGluIHRoZSBNTklTVCBleGFtcGxlLiBJdCBtZWFucyB0aGUgbmV0d29yayB3aWxsICBvdXRwdXQgYSBfcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uXyBvdmVyIHRoZSA0NiBkaWZmZXJlbnQgb3V0cHV0IGNsYXNzZXM6IHRoYXQgaXMsICBmb3IgZXZlcnkgaW5wdXQgc2FtcGxlLCB0aGUgbmV0d29yayB3aWxsIHByb2R1Y2UgYSA0Ni1kaW1lbnNpb25hbCBvdXRwdXQgdmVjdG9yLCB3aGVyZSBgb3V0cHV0W1tpXV1gIGlzIHRoZSBwcm9iYWJpbGl0eSB0aGF0IHRoZSBzYW1wbGUgYmVsb25ncyB0byBjbGFzcyBgaWAuIFRoZSA0NiBzY29yZXMgd2lsbCBzdW0gdG8gMS4KCgpUaGUgYmVzdCBsb3NzIGZ1bmN0aW9uIHRvIHVzZSBpbiB0aGlzIGNhc2UgaXMgYGNhdGVnb3JpY2FsX2Nyb3NzZW50cm9weWAuIEl0IG1lYXN1cmVzIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb25zOiBpbiBvdXIgY2FzZSwgYmV0d2VlbiB0aGUgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG91dHB1dCBieSBvdXIgbmV0d29yaywgYW5kIHRoZSB0cnVlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgbGFiZWxzLiBCeSBtaW5pbWl6aW5nIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZXNlIHR3byBkaXN0cmlidXRpb25zLCB3ZSB0cmFpbiBvdXIgbmV0d29yayB0byBvdXRwdXQgc29tZXRoaW5nIGFzIGNsb3NlIGFzIHBvc3NpYmxlIHRvIHRoZSB0cnVlIGxhYmVscy4KCmBgYHtyfQptb2RlbCAlPiUgY29tcGlsZSgKICBvcHRpbWl6ZXIgPSAicm1zcHJvcCIsCiAgbG9zcyA9ICJjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkiLAogIG1ldHJpY3MgPSBjKCJhY2N1cmFjeSIpCikKYGBgCgojIyBWYWxpZGF0aW5nIG91ciBhcHByb2FjaAoKTGV0J3Mgc2V0IGFwYXJ0IDEsMDAwIHNhbXBsZXMgaW4gb3VyIHRyYWluaW5nIGRhdGEgdG8gdXNlIGFzIGEgdmFsaWRhdGlvbiBzZXQ6CgpgYGB7cn0KdmFsX2luZGljZXMgPC0gMToxMDAwCgp4X3ZhbCA8LSB4X3RyYWluW3ZhbF9pbmRpY2VzLF0KcGFydGlhbF94X3RyYWluIDwtIHhfdHJhaW5bLXZhbF9pbmRpY2VzLF0KCnlfdmFsIDwtIG9uZV9ob3RfdHJhaW5fbGFiZWxzW3ZhbF9pbmRpY2VzLF0KcGFydGlhbF95X3RyYWluID0gb25lX2hvdF90cmFpbl9sYWJlbHNbLXZhbF9pbmRpY2VzLF0KYGBgCgpOb3cgbGV0J3MgdHJhaW4gb3VyIG5ldHdvcmsgZm9yIDIwIGVwb2NoczoKCmBgYHtyIGVjaG89VFJVRSwgcmVzdWx0cz0naGlkZSd9Cmhpc3RvcnkgPC0gbW9kZWwgJT4lIGZpdCgKICBwYXJ0aWFsX3hfdHJhaW4sCiAgcGFydGlhbF95X3RyYWluLAogIGVwb2NocyA9IDIwLAogIGJhdGNoX3NpemUgPSA1MTIsCiAgdmFsaWRhdGlvbl9kYXRhID0gbGlzdCh4X3ZhbCwgeV92YWwpCikKYGBgCgpMZXQncyBkaXNwbGF5IGl0cyBsb3NzIGFuZCBhY2N1cmFjeSBjdXJ2ZXM6CgpgYGB7cn0KcGxvdChoaXN0b3J5KQpgYGAKClRoZSBuZXR3b3JrIGJlZ2lucyB0byBvdmVyZml0IGFmdGVyIG5pbmUgZXBvY2hzLiBMZXQncyB0cmFpbiBhIG5ldyBuZXR3b3JrIGZyb20gc2NyYXRjaCBmb3IgbmluZSBlcG9jaHMgYW5kIHRoZW4gZXZhbHVhdGUgaXQgb24gdGhlIHRlc3Qgc2V0LgoKYGBge3IsIGVjaG89VFJVRSwgcmVzdWx0cz0naGlkZSd9Cm1vZGVsIDwtIGtlcmFzX21vZGVsX3NlcXVlbnRpYWwoKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA2NCwgYWN0aXZhdGlvbiA9ICJyZWx1IiwgaW5wdXRfc2hhcGUgPSBjKDEwMDAwKSkgJT4lIAogIGxheWVyX2RlbnNlKHVuaXRzID0gNjQsIGFjdGl2YXRpb24gPSAicmVsdSIpICU+JSAKICBsYXllcl9kZW5zZSh1bml0cyA9IDQ2LCBhY3RpdmF0aW9uID0gInNvZnRtYXgiKQogIAptb2RlbCAlPiUgY29tcGlsZSgKICBvcHRpbWl6ZXIgPSAicm1zcHJvcCIsCiAgbG9zcyA9ICJjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkiLAogIG1ldHJpY3MgPSBjKCJhY2N1cmFjeSIpCikKCmhpc3RvcnkgPC0gbW9kZWwgJT4lIGZpdCgKICBwYXJ0aWFsX3hfdHJhaW4sCiAgcGFydGlhbF95X3RyYWluLAogIGVwb2NocyA9IDksCiAgYmF0Y2hfc2l6ZSA9IDUxMiwKICB2YWxpZGF0aW9uX2RhdGEgPSBsaXN0KHhfdmFsLCB5X3ZhbCkKKQoKcmVzdWx0cyA8LSBtb2RlbCAlPiUgZXZhbHVhdGUoeF90ZXN0LCBvbmVfaG90X3Rlc3RfbGFiZWxzKQpgYGAKCmBgYHtyfQpyZXN1bHRzCmBgYAoKT3VyIGFwcHJvYWNoIHJlYWNoZXMgYW4gYWNjdXJhY3kgb2Ygfjc4JS4gV2l0aCBhIGJhbGFuY2VkIGJpbmFyeSBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLCB0aGUgYWNjdXJhY3kgcmVhY2hlZCBieSBhIHB1cmVseSByYW5kb20gY2xhc3NpZmllciB3b3VsZCBiZSA1MCUsIGJ1dCBpbiBvdXIgY2FzZSBpdCBpcyBjbG9zZXIgdG8gMTklLCBzbyBvdXIgcmVzdWx0cyBzZWVtIHByZXR0eSBnb29kLCBhdCBsZWFzdCB3aGVuIGNvbXBhcmVkIHRvIGEgcmFuZG9tIGJhc2VsaW5lOgoKYGBge3J9CnRlc3RfbGFiZWxzX2NvcHkgPC0gdGVzdF9sYWJlbHMKdGVzdF9sYWJlbHNfY29weSA8LSBzYW1wbGUodGVzdF9sYWJlbHNfY29weSkKbGVuZ3RoKHdoaWNoKHRlc3RfbGFiZWxzID09IHRlc3RfbGFiZWxzX2NvcHkpKSAvIGxlbmd0aCh0ZXN0X2xhYmVscykKYGBgCgojIyBHZW5lcmF0aW5nIHByZWRpY3Rpb25zIG9uIG5ldyBkYXRhCgpXZSBjYW4gdmVyaWZ5IHRoYXQgdGhlIGBwcmVkaWN0YCBtZXRob2Qgb2Ygb3VyIG1vZGVsIGluc3RhbmNlIHJldHVybnMgYSBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb24gb3ZlciBhbGwgNDYgdG9waWNzLiBMZXQncyBnZW5lcmF0ZSB0b3BpYyBwcmVkaWN0aW9ucyBmb3IgYWxsIG9mIHRoZSB0ZXN0IGRhdGE6CgpgYGB7cn0KcHJlZGljdGlvbnMgPC0gbW9kZWwgJT4lIHByZWRpY3QoeF90ZXN0KQpgYGAKCkVhY2ggZW50cnkgaW4gYHByZWRpY3Rpb25zYCBpcyBhIHZlY3RvciBvZiBsZW5ndGggNDY6CgpgYGB7cn0KZGltKHByZWRpY3Rpb25zKQpgYGAKClRoZSBjb2VmZmljaWVudHMgaW4gdGhpcyB2ZWN0b3Igc3VtIHRvIDE6CgpgYGB7cn0Kc3VtKHByZWRpY3Rpb25zWzEsXSkKYGBgCgpUaGUgbGFyZ2VzdCBlbnRyeSBpcyB0aGUgcHJlZGljdGVkIGNsYXNzLCBpLmUuIHRoZSBjbGFzcyB3aXRoIHRoZSBoaWdoZXN0IHByb2JhYmlsaXR5OgoKYGBge3J9CndoaWNoLm1heChwcmVkaWN0aW9uc1sxLF0pCmBgYAoKIyMgQSBkaWZmZXJlbnQgd2F5IHRvIGhhbmRsZSB0aGUgbGFiZWxzIGFuZCB0aGUgbG9zcwoKV2UgbWVudGlvbmVkIGVhcmxpZXIgdGhhdCBhbm90aGVyIHdheSB0byBlbmNvZGUgdGhlIGxhYmVscyB3b3VsZCBiZSB0byBwcmVzZXJ2ZSB0aGVpciBpbnRlZ2VyIHZhbHVlcy4gVGhlIG9ubHkgdGhpbmcgdGhpcyBhcHByb2FjaCB3b3VsZCBjaGFuZ2UgaXMgdGhlIGNob2ljZSBvZiB0aGUgbG9zcyBmdW5jdGlvbi4gVGhlIHByZXZpb3VzIGxvc3MsIGBjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHlgLCBleHBlY3RzIHRoZSBsYWJlbHMgdG8gZm9sbG93IGEgY2F0ZWdvcmljYWwgZW5jb2RpbmcuIFdpdGggaW50ZWdlciBsYWJlbHMsIHlvdSBzaG91bGQgdXNlIGBzcGFyc2VfY2F0ZWdvcmljYWxfY3Jvc3NlbnRyb3B5YDoKCmBgYHtyfQptb2RlbCAlPiUgY29tcGlsZSgKICBvcHRpbWl6ZXIgPSAicm1zcHJvcCIsCiAgbG9zcyA9ICJzcGFyc2VfY2F0ZWdvcmljYWxfY3Jvc3NlbnRyb3B5IiwKICBtZXRyaWNzID0gYygiYWNjdXJhY3kiKQopCmBgYAoKClRoaXMgbmV3IGxvc3MgZnVuY3Rpb24gaXMgc3RpbGwgbWF0aGVtYXRpY2FsbHkgdGhlIHNhbWUgYXMgYGNhdGVnb3JpY2FsX2Nyb3NzZW50cm9weWA7IGl0IGp1c3QgaGFzIGEgZGlmZmVyZW50IGludGVyZmFjZS4KCiMjIE9uIHRoZSBpbXBvcnRhbmNlIG9mIGhhdmluZyBzdWZmaWNpZW50bHkgbGFyZ2UgaW50ZXJtZWRpYXRlIGxheWVycwoKCldlIG1lbnRpb25lZCBlYXJsaWVyIHRoYXQgc2luY2Ugb3VyIGZpbmFsIG91dHB1dHMgd2VyZSA0Ni1kaW1lbnNpb25hbCwgd2Ugc2hvdWxkIGF2b2lkIGludGVybWVkaWF0ZSBsYXllcnMgd2l0aCBtdWNoIGxlc3MgdGhhbiA0NiBoaWRkZW4gdW5pdHMuIE5vdyBsZXQncyB0cnkgdG8gc2VlIHdoYXQgaGFwcGVucyB3aGVuIHdlIGludHJvZHVjZSBhbiBpbmZvcm1hdGlvbiBib3R0bGVuZWNrIGJ5IGhhdmluZyBpbnRlcm1lZGlhdGUgbGF5ZXJzIHNpZ25pZmljYW50bHkgbGVzcyB0aGFuIDQ2LWRpbWVuc2lvbmFsLCBlLmcuIDQtZGltZW5zaW9uYWwuCgpgYGB7ciwgZWNobz1UUlVFLCByZXN1bHRzPSdoaWRlJ30KbW9kZWwgPC0ga2VyYXNfbW9kZWxfc2VxdWVudGlhbCgpICU+JSAKICBsYXllcl9kZW5zZSh1bml0cyA9IDY0LCBhY3RpdmF0aW9uID0gInJlbHUiLCBpbnB1dF9zaGFwZSA9IGMoMTAwMDApKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA0LCBhY3RpdmF0aW9uID0gInJlbHUiKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA0NiwgYWN0aXZhdGlvbiA9ICJzb2Z0bWF4IikKICAKbW9kZWwgJT4lIGNvbXBpbGUoCiAgb3B0aW1pemVyID0gInJtc3Byb3AiLAogIGxvc3MgPSAiY2F0ZWdvcmljYWxfY3Jvc3NlbnRyb3B5IiwKICBtZXRyaWNzID0gYygiYWNjdXJhY3kiKQopCgptb2RlbCAlPiUgZml0KAogIHBhcnRpYWxfeF90cmFpbiwKICBwYXJ0aWFsX3lfdHJhaW4sCiAgZXBvY2hzID0gMjAsCiAgYmF0Y2hfc2l6ZSA9IDEyOCwKICB2YWxpZGF0aW9uX2RhdGEgPSBsaXN0KHhfdmFsLCB5X3ZhbCkKKQpgYGAKCk91ciBuZXR3b3JrIG5vdyBzZWVtcyB0byBwZWFrIGF0IH43MSUgdGVzdCBhY2N1cmFjeSwgYSA4JSBhYnNvbHV0ZSBkcm9wLiBUaGlzIGRyb3AgaXMgbW9zdGx5IGR1ZSB0byB0aGUgZmFjdCB0aGF0IHdlIGFyZSBub3cgdHJ5aW5nIHRvIGNvbXByZXNzIGEgbG90IG9mIGluZm9ybWF0aW9uIChlbm91Z2ggaW5mb3JtYXRpb24gdG8gcmVjb3ZlciB0aGUgc2VwYXJhdGlvbiBoeXBlcnBsYW5lcyBvZiA0NiBjbGFzc2VzKSBpbnRvIGFuIGludGVybWVkaWF0ZSBzcGFjZSB0aGF0IGlzIHRvbyBsb3ctZGltZW5zaW9uYWwuIFRoZSBuZXR3b3JrIGlzIGFibGUgdG8gY3JhbSBfbW9zdF8gb2YgdGhlIG5lY2Vzc2FyeSBpbmZvcm1hdGlvbiBpbnRvIHRoZXNlIDgtZGltZW5zaW9uYWwgcmVwcmVzZW50YXRpb25zLCBidXQgbm90IGFsbCBvZiBpdC4KCiMjIEZ1cnRoZXIgZXhwZXJpbWVudHMKCiogVHJ5IHVzaW5nIGxhcmdlciBvciBzbWFsbGVyIGxheWVyczogMzIgdW5pdHMsIDEyOCB1bml0cy4uLgoqIFdlIHdlcmUgdXNpbmcgdHdvIGhpZGRlbiBsYXllcnMuIE5vdyB0cnkgdG8gdXNlIGEgc2luZ2xlIGhpZGRlbiBsYXllciwgb3IgdGhyZWUgaGlkZGVuIGxheWVycy4KCiMjIFdyYXBwaW5nIHVwCgoKSGVyZSdzIHdoYXQgeW91IHNob3VsZCB0YWtlIGF3YXkgZnJvbSB0aGlzIGV4YW1wbGU6CgoqIElmIHlvdSBhcmUgdHJ5aW5nIHRvIGNsYXNzaWZ5IGRhdGEgcG9pbnRzIGJldHdlZW4gTiBjbGFzc2VzLCB5b3VyIG5ldHdvcmsgc2hvdWxkIGVuZCB3aXRoIGEgZGVuc2UgbGF5ZXIgb2Ygc2l6ZSBOLgoqIEluIGEgc2luZ2xlLWxhYmVsLCBtdWx0aS1jbGFzcyBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLCB5b3VyIG5ldHdvcmsgc2hvdWxkIGVuZCB3aXRoIGEgYHNvZnRtYXhgIGFjdGl2YXRpb24sIHNvIHRoYXQgaXQgd2lsbCBvdXRwdXQgYSBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb24gb3ZlciB0aGUgTiBvdXRwdXQgY2xhc3Nlcy4KKiBfQ2F0ZWdvcmljYWwgY3Jvc3NlbnRyb3B5XyBpcyBhbG1vc3QgYWx3YXlzIHRoZSBsb3NzIGZ1bmN0aW9uIHlvdSBzaG91bGQgdXNlIGZvciBzdWNoIHByb2JsZW1zLiBJdCBtaW5pbWl6ZXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbnMgb3V0cHV0IGJ5IHRoZSBuZXR3b3JrLCBhbmQgdGhlIHRydWUgZGlzdHJpYnV0aW9uIG9mIHRoZSB0YXJnZXRzLgoqIFRoZXJlIGFyZSB0d28gd2F5cyB0byBoYW5kbGUgbGFiZWxzIGluIG11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uOgogICAgKiBFbmNvZGluZyB0aGUgbGFiZWxzIHZpYSAiY2F0ZWdvcmljYWwgZW5jb2RpbmciIChhbHNvIGtub3duIGFzICJvbmUtaG90IGVuY29kaW5nIikgYW5kIHVzaW5nIGBjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHlgIGFzIHlvdXIgbG9zcyBmdW5jdGlvbi4KICAgICogRW5jb2RpbmcgdGhlIGxhYmVscyBhcyBpbnRlZ2VycyBhbmQgdXNpbmcgdGhlIGBzcGFyc2VfY2F0ZWdvcmljYWxfY3Jvc3NlbnRyb3B5YCBsb3NzIGZ1bmN0aW9uLgoqIElmIHlvdSBuZWVkIHRvIGNsYXNzaWZ5IGRhdGEgaW50byBhIGxhcmdlIG51bWJlciBvZiBjYXRlZ29yaWVzLCB0aGVuIHlvdSBzaG91bGQgYXZvaWQgY3JlYXRpbmcgaW5mb3JtYXRpb24gYm90dGxlbmVja3MgaW4geW91ciBuZXR3b3JrIGJ5IGhhdmluZyBpbnRlcm1lZGlhdGUgbGF5ZXJzIHRoYXQgYXJlIHRvbyBzbWFsbC4K