The Reuters dataset

Build a network to classify Reuters newswires from 1986 into 46 mutually exclusive topics.

The argument num_words = 10000 restricts the data to the 10,000 most frequently occurring words found in the data.

library(keras)

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

There are 8982 training samples and 2246 testing samples.

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

Again, we have a list of integers that serve as 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   89    5   19
[24]  102    6   19  124   15   90   67   84   22  482   26    7   48    4   49    8  864   39  209  154    6  151    6
[47]   83   11   15   22  155   11   15    7   48    9 4579 1005  504    6  258    6  272   11   15   22  134   44   11
[70]   15   16    8  197 1245   90   67   52   29  209   30   32  132    6  109   15   17   12

Decoding back to words.

# word_index is a named list mapping words to an integer index
word_index <- dataset_reuters_word_index()

# Reverses it, mapping integer indices to words
reverse_word_index <- names(word_index)
names(reverse_word_index) <- word_index

# Decodes the 1st wire. Note that the indices are offset by 3 because 0, 1, and 2 are reserved indices for "padding," "start of sequence," and "unknown."
decoded_newswire <- sapply(train_data[[1]], function(index) {
  word <- if (index >= 3) reverse_word_index[[as.character(index - 3)]]
  if (!is.null(word)) word else "?"
})

paste(decoded_newswire, collapse = " ")
[1] "? ? ? 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 a sample is an integer between 0 and 45 – a topic index.

train_labels[[1]]
[1] 3

Preparing the data

Vectorize and apply one-hot encoding as done before.

vectorize_sequences <- function(sequences, dimension = 10000) {
  # Initialize a matrix with all zeroes
  results <- matrix(0, nrow = length(sequences), ncol = dimension)
  # Replace 0 with a 1 for each column of the matrix given in the list
  for (i in 1:length(sequences))
    results[i, sequences[[i]]] <- 1
  results
}

x_train <- vectorize_sequences(train_data)
x_test <- vectorize_sequences(test_data)

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

One-hot encode the labels also. For the first sample, we see that the label was properly encoded from the integer 3 (from above) to index 3 equal to 1 in the new structure.

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

str(one_hot_train_labels[1,])
 num [1:46] 0 0 0 1 0 0 0 0 0 0 ...

Building the network

The dimensionality of the output space is now 46 adding complexity compared to the binary classification problem.

In the binary problem, 16-dimension intermediate layers were used. For this problem, more will be needed to allow for more learning due to the 46 separate classes. Use of smaller layers may act as information bottlenecks, permanently dropping relevant information. In this case we will go with 64 units.

The last layer uses a softmax activation. You saw this pattern in the MNIST example. It means the network will output a probability distribution over the 46 different output classes. For every input sample, the network will produce a 46-dimensional output vector, where output[[i]] is the probability that the sample belongs to class i. The 46 scores will sum to 1.

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")

Compiling the model

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

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

Validation step

Let’s set apart 1,000 samples in the 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,]

Training the model

Now, let’s train the 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)
)
Epoch 1/20

 1/16 [>.............................] - ETA: 4s - loss: 3.8699 - accuracy: 0.0059
 3/16 [====>.........................] - ETA: 0s - loss: 3.7811 - accuracy: 0.1094
 6/16 [==========>...................] - ETA: 0s - loss: 3.5998 - accuracy: 0.2946
10/16 [=================>............] - ETA: 0s - loss: 3.3187 - accuracy: 0.3867
15/16 [===========================>..] - ETA: 0s - loss: 2.9925 - accuracy: 0.4639
16/16 [==============================] - 1s 15ms/step - loss: 2.9587 - accuracy: 0.4711

16/16 [==============================] - 1s 20ms/step - loss: 2.9587 - accuracy: 0.4711 - val_loss: 2.0052 - val_accuracy: 0.6250
Epoch 2/20

 1/16 [>.............................] - ETA: 0s - loss: 1.9019 - accuracy: 0.6680
 5/16 [========>.....................] - ETA: 0s - loss: 1.7927 - accuracy: 0.6754
10/16 [=================>............] - ETA: 0s - loss: 1.6621 - accuracy: 0.6932
13/16 [=======================>......] - ETA: 0s - loss: 1.6019 - accuracy: 0.7012
16/16 [==============================] - 0s 16ms/step - loss: 1.5721 - accuracy: 0.7041

16/16 [==============================] - 0s 18ms/step - loss: 1.5721 - accuracy: 0.7041 - val_loss: 1.3750 - val_accuracy: 0.7160
Epoch 3/20

 1/16 [>.............................] - ETA: 0s - loss: 1.1183 - accuracy: 0.7832
 6/16 [==========>...................] - ETA: 0s - loss: 1.1671 - accuracy: 0.7686
11/16 [===================>..........] - ETA: 0s - loss: 1.1251 - accuracy: 0.7752
15/16 [===========================>..] - ETA: 0s - loss: 1.1054 - accuracy: 0.7785
16/16 [==============================] - 0s 13ms/step - loss: 1.1015 - accuracy: 0.7790

16/16 [==============================] - 0s 15ms/step - loss: 1.1015 - accuracy: 0.7790 - val_loss: 1.1533 - val_accuracy: 0.7550
Epoch 4/20

 1/16 [>.............................] - ETA: 0s - loss: 0.9423 - accuracy: 0.7949
 6/16 [==========>...................] - ETA: 0s - loss: 0.9085 - accuracy: 0.8115
11/16 [===================>..........] - ETA: 0s - loss: 0.8690 - accuracy: 0.8232
16/16 [==============================] - 0s 11ms/step - loss: 0.8570 - accuracy: 0.8236

16/16 [==============================] - 0s 13ms/step - loss: 0.8570 - accuracy: 0.8236 - val_loss: 1.0368 - val_accuracy: 0.7950
Epoch 5/20

 1/16 [>.............................] - ETA: 0s - loss: 0.7957 - accuracy: 0.8398
 6/16 [==========>...................] - ETA: 0s - loss: 0.7248 - accuracy: 0.8496
11/16 [===================>..........] - ETA: 0s - loss: 0.6994 - accuracy: 0.8517
16/16 [==============================] - 0s 11ms/step - loss: 0.6864 - accuracy: 0.8581

16/16 [==============================] - 0s 12ms/step - loss: 0.6864 - accuracy: 0.8581 - val_loss: 0.9683 - val_accuracy: 0.8090
Epoch 6/20

 1/16 [>.............................] - ETA: 0s - loss: 0.5589 - accuracy: 0.8926
 6/16 [==========>...................] - ETA: 0s - loss: 0.5625 - accuracy: 0.8906
11/16 [===================>..........] - ETA: 0s - loss: 0.5530 - accuracy: 0.8908
16/16 [==============================] - 0s 11ms/step - loss: 0.5521 - accuracy: 0.8879

16/16 [==============================] - 0s 12ms/step - loss: 0.5521 - accuracy: 0.8879 - val_loss: 0.9294 - val_accuracy: 0.8030
Epoch 7/20

 1/16 [>.............................] - ETA: 0s - loss: 0.4947 - accuracy: 0.9004
 6/16 [==========>...................] - ETA: 0s - loss: 0.4510 - accuracy: 0.9082
11/16 [===================>..........] - ETA: 0s - loss: 0.4449 - accuracy: 0.9089
16/16 [==============================] - 0s 11ms/step - loss: 0.4465 - accuracy: 0.9069

16/16 [==============================] - 0s 12ms/step - loss: 0.4465 - accuracy: 0.9069 - val_loss: 0.9028 - val_accuracy: 0.8190
Epoch 8/20

 1/16 [>.............................] - ETA: 0s - loss: 0.3109 - accuracy: 0.9395
 6/16 [==========>...................] - ETA: 0s - loss: 0.3468 - accuracy: 0.9287
12/16 [=====================>........] - ETA: 0s - loss: 0.3592 - accuracy: 0.9251
16/16 [==============================] - 0s 10ms/step - loss: 0.3621 - accuracy: 0.9245

16/16 [==============================] - 0s 11ms/step - loss: 0.3621 - accuracy: 0.9245 - val_loss: 0.8920 - val_accuracy: 0.8160
Epoch 9/20

 1/16 [>.............................] - ETA: 0s - loss: 0.3324 - accuracy: 0.9414
 6/16 [==========>...................] - ETA: 0s - loss: 0.3086 - accuracy: 0.9365
12/16 [=====================>........] - ETA: 0s - loss: 0.3003 - accuracy: 0.9338
16/16 [==============================] - 0s 10ms/step - loss: 0.2984 - accuracy: 0.9344

16/16 [==============================] - 0s 11ms/step - loss: 0.2984 - accuracy: 0.9344 - val_loss: 0.9076 - val_accuracy: 0.8150
Epoch 10/20

 1/16 [>.............................] - ETA: 0s - loss: 0.2236 - accuracy: 0.9629
 6/16 [==========>...................] - ETA: 0s - loss: 0.2431 - accuracy: 0.9505
12/16 [=====================>........] - ETA: 0s - loss: 0.2453 - accuracy: 0.9465
16/16 [==============================] - 0s 10ms/step - loss: 0.2539 - accuracy: 0.9424

16/16 [==============================] - 0s 11ms/step - loss: 0.2539 - accuracy: 0.9424 - val_loss: 0.8895 - val_accuracy: 0.8240
Epoch 11/20

 1/16 [>.............................] - ETA: 0s - loss: 0.2606 - accuracy: 0.9453
 7/16 [============>.................] - ETA: 0s - loss: 0.2237 - accuracy: 0.9528
11/16 [===================>..........] - ETA: 0s - loss: 0.2216 - accuracy: 0.9485
16/16 [==============================] - 0s 10ms/step - loss: 0.2175 - accuracy: 0.9474

16/16 [==============================] - 0s 12ms/step - loss: 0.2175 - accuracy: 0.9474 - val_loss: 0.9538 - val_accuracy: 0.8070
Epoch 12/20

 1/16 [>.............................] - ETA: 0s - loss: 0.2022 - accuracy: 0.9473
 6/16 [==========>...................] - ETA: 0s - loss: 0.1725 - accuracy: 0.9613
11/16 [===================>..........] - ETA: 0s - loss: 0.1875 - accuracy: 0.9540
16/16 [==============================] - 0s 11ms/step - loss: 0.1905 - accuracy: 0.9528

16/16 [==============================] - 0s 12ms/step - loss: 0.1905 - accuracy: 0.9528 - val_loss: 0.9623 - val_accuracy: 0.8010
Epoch 13/20

 1/16 [>.............................] - ETA: 0s - loss: 0.1785 - accuracy: 0.9551
 6/16 [==========>...................] - ETA: 0s - loss: 0.1564 - accuracy: 0.9593
11/16 [===================>..........] - ETA: 0s - loss: 0.1659 - accuracy: 0.9553
16/16 [==============================] - 0s 10ms/step - loss: 0.1719 - accuracy: 0.9533

16/16 [==============================] - 0s 11ms/step - loss: 0.1719 - accuracy: 0.9533 - val_loss: 0.9416 - val_accuracy: 0.8160
Epoch 14/20

 1/16 [>.............................] - ETA: 0s - loss: 0.1235 - accuracy: 0.9629
 6/16 [==========>...................] - ETA: 0s - loss: 0.1418 - accuracy: 0.9577
11/16 [===================>..........] - ETA: 0s - loss: 0.1525 - accuracy: 0.9558
16/16 [==============================] - 0s 11ms/step - loss: 0.1551 - accuracy: 0.9534

16/16 [==============================] - 0s 13ms/step - loss: 0.1551 - accuracy: 0.9534 - val_loss: 0.9476 - val_accuracy: 0.8060
Epoch 15/20

 1/16 [>.............................] - ETA: 0s - loss: 0.0983 - accuracy: 0.9668
 4/16 [======>.......................] - ETA: 0s - loss: 0.1202 - accuracy: 0.9653
 9/16 [===============>..............] - ETA: 0s - loss: 0.1298 - accuracy: 0.9592
14/16 [=========================>....] - ETA: 0s - loss: 0.1429 - accuracy: 0.9563
16/16 [==============================] - 0s 12ms/step - loss: 0.1438 - accuracy: 0.9551

16/16 [==============================] - 0s 13ms/step - loss: 0.1438 - accuracy: 0.9551 - val_loss: 0.9849 - val_accuracy: 0.8150
Epoch 16/20

 1/16 [>.............................] - ETA: 0s - loss: 0.1102 - accuracy: 0.9648
 6/16 [==========>...................] - ETA: 0s - loss: 0.1100 - accuracy: 0.9655
12/16 [=====================>........] - ETA: 0s - loss: 0.1297 - accuracy: 0.9591
16/16 [==============================] - 0s 10ms/step - loss: 0.1318 - accuracy: 0.9575

16/16 [==============================] - 0s 11ms/step - loss: 0.1318 - accuracy: 0.9575 - val_loss: 1.0448 - val_accuracy: 0.7990
Epoch 17/20

 1/16 [>.............................] - ETA: 0s - loss: 0.1089 - accuracy: 0.9707
 6/16 [==========>...................] - ETA: 0s - loss: 0.1051 - accuracy: 0.9684
11/16 [===================>..........] - ETA: 0s - loss: 0.1210 - accuracy: 0.9631
16/16 [==============================] - 0s 10ms/step - loss: 0.1278 - accuracy: 0.9578

16/16 [==============================] - 0s 11ms/step - loss: 0.1278 - accuracy: 0.9578 - val_loss: 0.9959 - val_accuracy: 0.8150
Epoch 18/20

 1/16 [>.............................] - ETA: 0s - loss: 0.1021 - accuracy: 0.9766
 5/16 [========>.....................] - ETA: 0s - loss: 0.1087 - accuracy: 0.9680
10/16 [=================>............] - ETA: 0s - loss: 0.1141 - accuracy: 0.9635
15/16 [===========================>..] - ETA: 0s - loss: 0.1206 - accuracy: 0.9592
16/16 [==============================] - 0s 11ms/step - loss: 0.1218 - accuracy: 0.9592

16/16 [==============================] - 0s 13ms/step - loss: 0.1218 - accuracy: 0.9592 - val_loss: 1.0678 - val_accuracy: 0.8010
Epoch 19/20

 1/16 [>.............................] - ETA: 0s - loss: 0.0777 - accuracy: 0.9707
 6/16 [==========>...................] - ETA: 0s - loss: 0.1090 - accuracy: 0.9587
12/16 [=====================>........] - ETA: 0s - loss: 0.1163 - accuracy: 0.9570
16/16 [==============================] - 0s 10ms/step - loss: 0.1143 - accuracy: 0.9568

16/16 [==============================] - 0s 11ms/step - loss: 0.1143 - accuracy: 0.9568 - val_loss: 1.0761 - val_accuracy: 0.7990
Epoch 20/20

 1/16 [>.............................] - ETA: 0s - loss: 0.1250 - accuracy: 0.9551
 7/16 [============>.................] - ETA: 0s - loss: 0.1056 - accuracy: 0.9626
13/16 [=======================>......] - ETA: 0s - loss: 0.1137 - accuracy: 0.9588
16/16 [==============================] - 0s 9ms/step - loss: 0.1164 - accuracy: 0.9573

16/16 [==============================] - 0s 10ms/step - loss: 0.1164 - accuracy: 0.9573 - val_loss: 1.0617 - val_accuracy: 0.8090
plot(history)
`geom_smooth()` using formula 'y ~ x'

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)
)
Epoch 1/9

 1/16 [>.............................] - ETA: 3s - loss: 3.8369 - accuracy: 0.0312
 5/16 [========>.....................] - ETA: 0s - loss: 3.5004 - accuracy: 0.3105
 9/16 [===============>..............] - ETA: 0s - loss: 3.1227 - accuracy: 0.4015
13/16 [=======================>......] - ETA: 0s - loss: 2.8102 - accuracy: 0.4656
16/16 [==============================] - 0s 13ms/step - loss: 2.6486 - accuracy: 0.4986

16/16 [==============================] - 0s 17ms/step - loss: 2.6486 - accuracy: 0.4986 - val_loss: 1.7172 - val_accuracy: 0.6580
Epoch 2/9

 1/16 [>.............................] - ETA: 0s - loss: 1.4873 - accuracy: 0.7363
 6/16 [==========>...................] - ETA: 0s - loss: 1.5088 - accuracy: 0.7061
11/16 [===================>..........] - ETA: 0s - loss: 1.4755 - accuracy: 0.7029
16/16 [==============================] - 0s 10ms/step - loss: 1.4227 - accuracy: 0.7082

16/16 [==============================] - 0s 11ms/step - loss: 1.4227 - accuracy: 0.7082 - val_loss: 1.3113 - val_accuracy: 0.7100
Epoch 3/9

 1/16 [>.............................] - ETA: 0s - loss: 1.1503 - accuracy: 0.7520
 6/16 [==========>...................] - ETA: 0s - loss: 1.0910 - accuracy: 0.7718
11/16 [===================>..........] - ETA: 0s - loss: 1.0699 - accuracy: 0.7747
16/16 [==============================] - 0s 11ms/step - loss: 1.0570 - accuracy: 0.7771

16/16 [==============================] - 0s 12ms/step - loss: 1.0570 - accuracy: 0.7771 - val_loss: 1.1626 - val_accuracy: 0.7460
Epoch 4/9

 1/16 [>.............................] - ETA: 0s - loss: 0.8849 - accuracy: 0.8203
 6/16 [==========>...................] - ETA: 0s - loss: 0.8606 - accuracy: 0.8177
12/16 [=====================>........] - ETA: 0s - loss: 0.8492 - accuracy: 0.8164
16/16 [==============================] - 0s 10ms/step - loss: 0.8331 - accuracy: 0.8211

16/16 [==============================] - 0s 11ms/step - loss: 0.8331 - accuracy: 0.8211 - val_loss: 1.0473 - val_accuracy: 0.7750
Epoch 5/9

 1/16 [>.............................] - ETA: 0s - loss: 0.7235 - accuracy: 0.8457
 7/16 [============>.................] - ETA: 0s - loss: 0.6817 - accuracy: 0.8535
13/16 [=======================>......] - ETA: 0s - loss: 0.6797 - accuracy: 0.8540
16/16 [==============================] - 0s 9ms/step - loss: 0.6616 - accuracy: 0.8578

16/16 [==============================] - 0s 10ms/step - loss: 0.6616 - accuracy: 0.8578 - val_loss: 0.9789 - val_accuracy: 0.7970
Epoch 6/9

 1/16 [>.............................] - ETA: 0s - loss: 0.6526 - accuracy: 0.8613
 6/16 [==========>...................] - ETA: 0s - loss: 0.5290 - accuracy: 0.8916
12/16 [=====================>........] - ETA: 0s - loss: 0.5300 - accuracy: 0.8906
16/16 [==============================] - 0s 9ms/step - loss: 0.5251 - accuracy: 0.8911

16/16 [==============================] - 0s 11ms/step - loss: 0.5251 - accuracy: 0.8911 - val_loss: 0.9226 - val_accuracy: 0.8090
Epoch 7/9

 1/16 [>.............................] - ETA: 0s - loss: 0.4846 - accuracy: 0.9023
 6/16 [==========>...................] - ETA: 0s - loss: 0.4220 - accuracy: 0.9137
11/16 [===================>..........] - ETA: 0s - loss: 0.4176 - accuracy: 0.9112
15/16 [===========================>..] - ETA: 0s - loss: 0.4206 - accuracy: 0.9130
16/16 [==============================] - 0s 11ms/step - loss: 0.4225 - accuracy: 0.9126

16/16 [==============================] - 0s 12ms/step - loss: 0.4225 - accuracy: 0.9126 - val_loss: 0.9009 - val_accuracy: 0.8210
Epoch 8/9

 1/16 [>.............................] - ETA: 0s - loss: 0.3499 - accuracy: 0.9277
 7/16 [============>.................] - ETA: 0s - loss: 0.3597 - accuracy: 0.9241
12/16 [=====================>........] - ETA: 0s - loss: 0.3412 - accuracy: 0.9277
16/16 [==============================] - 0s 10ms/step - loss: 0.3405 - accuracy: 0.9276

16/16 [==============================] - 0s 12ms/step - loss: 0.3405 - accuracy: 0.9276 - val_loss: 0.8964 - val_accuracy: 0.8220
Epoch 9/9

 1/16 [>.............................] - ETA: 0s - loss: 0.2725 - accuracy: 0.9395
 6/16 [==========>...................] - ETA: 0s - loss: 0.2695 - accuracy: 0.9427
12/16 [=====================>........] - ETA: 0s - loss: 0.2798 - accuracy: 0.9404
16/16 [==============================] - 0s 10ms/step - loss: 0.2817 - accuracy: 0.9397

16/16 [==============================] - 0s 11ms/step - loss: 0.2817 - accuracy: 0.9397 - val_loss: 0.9044 - val_accuracy: 0.8200
results <- model %>% evaluate(x_test, one_hot_test_labels)

 1/71 [..............................] - ETA: 0s - loss: 0.5331 - accuracy: 0.9062
71/71 [==============================] - 0s 635us/step - loss: 0.9809 - accuracy: 0.7943

71/71 [==============================] - 0s 637us/step - loss: 0.9809 - accuracy: 0.7943
results
     loss  accuracy 
0.9808653 0.7943010 

This approach reaches an accuracy of ~79%. With a balanced binary classification problem, the accuracy reached by a purely random classifier would be 50%. But in this case it’s closer to 18%, so the 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.182992

Predicting on new data

The predict method of the 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)
dim(predictions)
[1] 2246   46

The coefficients in each vector sum to 1

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

The largest entry is the predicted class – the class with the highest probability.

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

Other training experiments to try

Takeaways

LS0tCnRpdGxlOiAiU2luZ2xlLUxhYmVsLCBNdWx0aWNsYXNzIENsYXNzaWZpY2F0aW9uIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgojIyBUaGUgUmV1dGVycyBkYXRhc2V0CgpCdWlsZCBhIG5ldHdvcmsgdG8gY2xhc3NpZnkgUmV1dGVycyBuZXdzd2lyZXMgZnJvbSAxOTg2IGludG8gNDYgbXV0dWFsbHkgZXhjbHVzaXZlIHRvcGljcy4KClRoZSBhcmd1bWVudCBgbnVtX3dvcmRzID0gMTAwMDBgIHJlc3RyaWN0cyB0aGUgZGF0YSB0byB0aGUgMTAsMDAwIG1vc3QgZnJlcXVlbnRseSBvY2N1cnJpbmcgd29yZHMgZm91bmQgaW4gdGhlIGRhdGEuCgpgYGB7cn0KbGlicmFyeShrZXJhcykKCnJldXRlcnMgPC0gZGF0YXNldF9yZXV0ZXJzKG51bV93b3JkcyA9IDEwMDAwKQpjKGModHJhaW5fZGF0YSwgdHJhaW5fbGFiZWxzKSwgYyh0ZXN0X2RhdGEsIHRlc3RfbGFiZWxzKSkgJTwtJSByZXV0ZXJzCmBgYAoKVGhlcmUgYXJlIDg5ODIgdHJhaW5pbmcgc2FtcGxlcyBhbmQgMjI0NiB0ZXN0aW5nIHNhbXBsZXMuCgpgYGB7cn0KbGVuZ3RoKHRyYWluX2RhdGEpCmxlbmd0aCh0ZXN0X2RhdGEpCmBgYAoKQWdhaW4sIHdlIGhhdmUgYSBsaXN0IG9mIGludGVnZXJzIHRoYXQgc2VydmUgYXMgd29yZCBpbmRpY2VzLgoKYGBge3J9CnRyYWluX2RhdGFbWzFdXQpgYGAKCkRlY29kaW5nIGJhY2sgdG8gd29yZHMuCgpgYGB7cn0KIyB3b3JkX2luZGV4IGlzIGEgbmFtZWQgbGlzdCBtYXBwaW5nIHdvcmRzIHRvIGFuIGludGVnZXIgaW5kZXgKd29yZF9pbmRleCA8LSBkYXRhc2V0X3JldXRlcnNfd29yZF9pbmRleCgpCgojIFJldmVyc2VzIGl0LCBtYXBwaW5nIGludGVnZXIgaW5kaWNlcyB0byB3b3JkcwpyZXZlcnNlX3dvcmRfaW5kZXggPC0gbmFtZXMod29yZF9pbmRleCkKbmFtZXMocmV2ZXJzZV93b3JkX2luZGV4KSA8LSB3b3JkX2luZGV4CgojIERlY29kZXMgdGhlIDFzdCB3aXJlLiBOb3RlIHRoYXQgdGhlIGluZGljZXMgYXJlIG9mZnNldCBieSAzIGJlY2F1c2UgMCwgMSwgYW5kIDIgYXJlIHJlc2VydmVkIGluZGljZXMgZm9yICJwYWRkaW5nLCIgInN0YXJ0IG9mIHNlcXVlbmNlLCIgYW5kICJ1bmtub3duLiIKZGVjb2RlZF9uZXdzd2lyZSA8LSBzYXBwbHkodHJhaW5fZGF0YVtbMV1dLCBmdW5jdGlvbihpbmRleCkgewogIHdvcmQgPC0gaWYgKGluZGV4ID49IDMpIHJldmVyc2Vfd29yZF9pbmRleFtbYXMuY2hhcmFjdGVyKGluZGV4IC0gMyldXQogIGlmICghaXMubnVsbCh3b3JkKSkgd29yZCBlbHNlICI/Igp9KQoKcGFzdGUoZGVjb2RlZF9uZXdzd2lyZSwgY29sbGFwc2UgPSAiICIpCmBgYAoKVGhlIGxhYmVsIGFzc29jaWF0ZWQgd2l0aCBhIHNhbXBsZSBpcyBhbiBpbnRlZ2VyIGJldHdlZW4gMCBhbmQgNDUgLS0gYSB0b3BpYyBpbmRleC4KCmBgYHtyfQp0cmFpbl9sYWJlbHNbWzFdXQpgYGAKCiMjIFByZXBhcmluZyB0aGUgZGF0YQoKVmVjdG9yaXplIGFuZCBhcHBseSBvbmUtaG90IGVuY29kaW5nIGFzIGRvbmUgYmVmb3JlLgoKYGBge3J9CnZlY3Rvcml6ZV9zZXF1ZW5jZXMgPC0gZnVuY3Rpb24oc2VxdWVuY2VzLCBkaW1lbnNpb24gPSAxMDAwMCkgewogICMgSW5pdGlhbGl6ZSBhIG1hdHJpeCB3aXRoIGFsbCB6ZXJvZXMKICByZXN1bHRzIDwtIG1hdHJpeCgwLCBucm93ID0gbGVuZ3RoKHNlcXVlbmNlcyksIG5jb2wgPSBkaW1lbnNpb24pCiAgIyBSZXBsYWNlIDAgd2l0aCBhIDEgZm9yIGVhY2ggY29sdW1uIG9mIHRoZSBtYXRyaXggZ2l2ZW4gaW4gdGhlIGxpc3QKICBmb3IgKGkgaW4gMTpsZW5ndGgoc2VxdWVuY2VzKSkKICAgIHJlc3VsdHNbaSwgc2VxdWVuY2VzW1tpXV1dIDwtIDEKICByZXN1bHRzCn0KCnhfdHJhaW4gPC0gdmVjdG9yaXplX3NlcXVlbmNlcyh0cmFpbl9kYXRhKQp4X3Rlc3QgPC0gdmVjdG9yaXplX3NlcXVlbmNlcyh0ZXN0X2RhdGEpCgpzdHIoeF90cmFpblsxLF0pCmBgYAoKT25lLWhvdCBlbmNvZGUgdGhlIGxhYmVscyBhbHNvLiBGb3IgdGhlIGZpcnN0IHNhbXBsZSwgd2Ugc2VlIHRoYXQgdGhlIGxhYmVsIHdhcyBwcm9wZXJseSBlbmNvZGVkIGZyb20gdGhlIGludGVnZXIgMyAoZnJvbSBhYm92ZSkgdG8gaW5kZXggMyBlcXVhbCB0byAxIGluIHRoZSBuZXcgc3RydWN0dXJlLgoKYGBge3J9Cm9uZV9ob3RfdHJhaW5fbGFiZWxzIDwtIHRvX2NhdGVnb3JpY2FsKHRyYWluX2xhYmVscykKb25lX2hvdF90ZXN0X2xhYmVscyA8LSB0b19jYXRlZ29yaWNhbCh0ZXN0X2xhYmVscykKCnN0cihvbmVfaG90X3RyYWluX2xhYmVsc1sxLF0pCmBgYAoKIyMgQnVpbGRpbmcgdGhlIG5ldHdvcmsKClRoZSBkaW1lbnNpb25hbGl0eSBvZiB0aGUgb3V0cHV0IHNwYWNlIGlzIG5vdyA0NiBhZGRpbmcgY29tcGxleGl0eSBjb21wYXJlZCB0byB0aGUgYmluYXJ5IGNsYXNzaWZpY2F0aW9uIHByb2JsZW0uCgpJbiB0aGUgYmluYXJ5IHByb2JsZW0sIDE2LWRpbWVuc2lvbiBpbnRlcm1lZGlhdGUgbGF5ZXJzIHdlcmUgdXNlZC4gRm9yIHRoaXMgcHJvYmxlbSwgbW9yZSB3aWxsIGJlIG5lZWRlZCB0byBhbGxvdyBmb3IgbW9yZSBsZWFybmluZyBkdWUgdG8gdGhlIDQ2IHNlcGFyYXRlIGNsYXNzZXMuIFVzZSBvZiBzbWFsbGVyIGxheWVycyBtYXkgYWN0IGFzIGluZm9ybWF0aW9uIGJvdHRsZW5lY2tzLCBwZXJtYW5lbnRseSBkcm9wcGluZyByZWxldmFudCBpbmZvcm1hdGlvbi4gSW4gdGhpcyBjYXNlIHdlIHdpbGwgZ28gd2l0aCA2NCB1bml0cy4KClRoZSBsYXN0IGxheWVyIHVzZXMgYSBgc29mdG1heGAgYWN0aXZhdGlvbi4gWW91IHNhdyB0aGlzIHBhdHRlcm4gaW4gdGhlIE1OSVNUIGV4YW1wbGUuIEl0IG1lYW5zIHRoZSBuZXR3b3JrIHdpbGwgb3V0cHV0IGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG92ZXIgdGhlIDQ2IGRpZmZlcmVudCBvdXRwdXQgY2xhc3Nlcy4gRm9yIGV2ZXJ5IGlucHV0IHNhbXBsZSwgdGhlIG5ldHdvcmsgd2lsbCBwcm9kdWNlIGEgNDYtZGltZW5zaW9uYWwgb3V0cHV0IHZlY3Rvciwgd2hlcmUgYG91dHB1dFtbaV1dYCBpcyB0aGUgcHJvYmFiaWxpdHkgdGhhdCB0aGUgc2FtcGxlIGJlbG9uZ3MgdG8gY2xhc3MgYGlgLiBUaGUgNDYgc2NvcmVzIHdpbGwgc3VtIHRvIDEuCgpgYGB7cn0KbW9kZWwgPC0ga2VyYXNfbW9kZWxfc2VxdWVudGlhbCgpICU+JQogIGxheWVyX2RlbnNlKHVuaXRzID0gNjQsIGFjdGl2YXRpb24gPSAicmVsdSIsIGlucHV0X3NoYXBlID0gYygxMDAwMCkpICU+JQogIGxheWVyX2RlbnNlKHVuaXRzID0gNjQsIGFjdGl2YXRpb24gPSAicmVsdSIpICU+JQogIGxheWVyX2RlbnNlKHVuaXRzID0gNDYsIGFjdGl2YXRpb24gPSAic29mdG1heCIpCmBgYAoKIyMgQ29tcGlsaW5nIHRoZSBtb2RlbAoKVGhlIGJlc3QgbG9zcyBmdW5jdGlvbiB0byB1c2UgaW4gdGhpcyBjYXNlIGlzIGBjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkuYCBJdCBtZWFzdXJlcyB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uczogaGVyZSwgYmV0d2VlbiB0aGUgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG91dHB1dCBieSB0aGUgbmV0d29yayBhbmQgdGhlIHRydWUgZGlzdHJpYnV0aW9uIG9mIHRoZSBsYWJlbHMuIEJ5IG1pbmltaXppbmcgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlc2UgdHdvIGRpc3RyaWJ1dGlvbnMsIHlvdSB0cmFpbiB0aGUgbmV0d29yayB0byBvdXRwdXQgc29tZXRoaW5nIGFzIGNsb3NlIGFzIHBvc3NpYmxlIHRvIHRoZSB0cnVlIGxhYmVscy4KCmBgYHtyfQptb2RlbCAlPiUgY29tcGlsZSgKICBvcHRpbWl6ZXIgPSAicm1zcHJvcCIsCiAgbG9zcyA9ICJjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkiLAogIG1ldHJpY3MgPSBjKCJhY2N1cmFjeSIpCikKYGBgCgojIyBWYWxpZGF0aW9uIHN0ZXAKCkxldCdzIHNldCBhcGFydCAxLDAwMCBzYW1wbGVzIGluIHRoZSB0cmFpbmluZyBkYXRhIHRvIHVzZSBhcyBhIHZhbGlkYXRpb24gc2V0LgoKYGBge3J9CnZhbF9pbmRpY2VzIDwtIDE6MTAwMAoKeF92YWwgPC0geF90cmFpblt2YWxfaW5kaWNlcyxdCnBhcnRpYWxfeF90cmFpbiA8LSB4X3RyYWluWy12YWxfaW5kaWNlcyxdCgp5X3ZhbCA8LSBvbmVfaG90X3RyYWluX2xhYmVsc1t2YWxfaW5kaWNlcyxdCnBhcnRpYWxfeV90cmFpbiA9IG9uZV9ob3RfdHJhaW5fbGFiZWxzWy12YWxfaW5kaWNlcyxdCmBgYAoKIyMgVHJhaW5pbmcgdGhlIG1vZGVsCgpOb3csIGxldCdzIHRyYWluIHRoZSBuZXR3b3JrIGZvciAyMCBlcG9jaHMuCgpgYGB7cn0KaGlzdG9yeSA8LSBtb2RlbCAlPiUgZml0KAogIHBhcnRpYWxfeF90cmFpbiwKICBwYXJ0aWFsX3lfdHJhaW4sCiAgZXBvY2hzID0gMjAsCiAgYmF0Y2hfc2l6ZSA9IDUxMiwKICB2YWxpZGF0aW9uX2RhdGEgPSBsaXN0KHhfdmFsLCB5X3ZhbCkKKQpgYGAKCmBgYHtyfQpwbG90KGhpc3RvcnkpCmBgYAoKVGhlIG5ldHdvcmsgYmVnaW5zIHRvIG92ZXJmaXQgYWZ0ZXIgbmluZSBlcG9jaHMuIExldOKAmXMgdHJhaW4gYSBuZXcgbmV0d29yayBmcm9tIHNjcmF0Y2ggZm9yIG5pbmUgZXBvY2hzIGFuZCB0aGVuIGV2YWx1YXRlIGl0IG9uIHRoZSB0ZXN0IHNldC4KCmBgYHtyfQptb2RlbCA8LSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkgJT4lCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA2NCwgYWN0aXZhdGlvbiA9ICJyZWx1IiwgaW5wdXRfc2hhcGUgPSBjKDEwMDAwKSkgJT4lCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA2NCwgYWN0aXZhdGlvbiA9ICJyZWx1IikgJT4lCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSA0NiwgYWN0aXZhdGlvbiA9ICJzb2Z0bWF4IikKCm1vZGVsICU+JSBjb21waWxlKAogIG9wdGltaXplciA9ICJybXNwcm9wIiwKICBsb3NzID0gImNhdGVnb3JpY2FsX2Nyb3NzZW50cm9weSIsCiAgbWV0cmljcyA9IGMoImFjY3VyYWN5IikKKQoKaGlzdG9yeSA8LSBtb2RlbCAlPiUgZml0KAogIHBhcnRpYWxfeF90cmFpbiwKICBwYXJ0aWFsX3lfdHJhaW4sCiAgZXBvY2hzID0gOSwKICBiYXRjaF9zaXplID0gNTEyLAogIHZhbGlkYXRpb25fZGF0YSA9IGxpc3QoeF92YWwsIHlfdmFsKQopCgpyZXN1bHRzIDwtIG1vZGVsICU+JSBldmFsdWF0ZSh4X3Rlc3QsIG9uZV9ob3RfdGVzdF9sYWJlbHMpCnJlc3VsdHMKYGBgCgpUaGlzIGFwcHJvYWNoIHJlYWNoZXMgYW4gYWNjdXJhY3kgb2Ygfjc5JS4gV2l0aCBhIGJhbGFuY2VkIGJpbmFyeSBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLCB0aGUgYWNjdXJhY3kgcmVhY2hlZCBieSBhIHB1cmVseSByYW5kb20gY2xhc3NpZmllciB3b3VsZCBiZSA1MCUuIEJ1dCBpbiB0aGlzIGNhc2UgaXTigJlzIGNsb3NlciB0byAxOCUsIHNvIHRoZSByZXN1bHRzIHNlZW0gcHJldHR5IGdvb2QsIGF0IGxlYXN0IHdoZW4gY29tcGFyZWQgdG8gYSByYW5kb20gYmFzZWxpbmUuCgpgYGB7cn0KdGVzdF9sYWJlbHNfY29weSA8LSB0ZXN0X2xhYmVscwp0ZXN0X2xhYmVsc19jb3B5IDwtIHNhbXBsZSh0ZXN0X2xhYmVsc19jb3B5KQpsZW5ndGgod2hpY2godGVzdF9sYWJlbHMgPT0gdGVzdF9sYWJlbHNfY29weSkpIC8gbGVuZ3RoKHRlc3RfbGFiZWxzKQpgYGAKCiMjIFByZWRpY3Rpbmcgb24gbmV3IGRhdGEKClRoZSBgcHJlZGljdGAgbWV0aG9kIG9mIHRoZSBtb2RlbCBpbnN0YW5jZSByZXR1cm5zIGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG92ZXIgYWxsIDQ2IHRvcGljcy4gTGV0J3MgZ2VuZXJhdGUgdG9waWMgcHJlZGljdGlvbnMgZm9yIGFsbCBvZiB0aGUgdGVzdCBkYXRhLgoKYGBge3J9CnByZWRpY3Rpb25zIDwtIG1vZGVsICU+JSBwcmVkaWN0KHhfdGVzdCkKZGltKHByZWRpY3Rpb25zKQpgYGAKClRoZSBjb2VmZmljaWVudHMgaW4gZWFjaCB2ZWN0b3Igc3VtIHRvIDEKCmBgYHtyfQpzdW0ocHJlZGljdGlvbnNbMSxdKQpgYGAKClRoZSBsYXJnZXN0IGVudHJ5IGlzIHRoZSBwcmVkaWN0ZWQgY2xhc3MgLS0gdGhlIGNsYXNzIHdpdGggdGhlIGhpZ2hlc3QgcHJvYmFiaWxpdHkuCgpgYGB7cn0Kd2hpY2gubWF4KHByZWRpY3Rpb25zWzEsXSkKYGBgCgojIyBPdGhlciB0cmFpbmluZyBleHBlcmltZW50cyB0byB0cnkKCi0gVXNlIGxhcmdlciBvciBzbWFsbGVyIGxheWVyczogMzIgdW5pdHMsIDEyOCB1bml0cywgYW5kIHNvIG9uLgotIFVzZSBhIHNpbmdsZSBoaWRkZW4gbGF5ZXIgb3IgdGhyZWUgaGlkZGVuIGxheWVycy4KCiMjIFRha2Vhd2F5cwoKLSBJZiB5b3XigJlyZSB0cnlpbmcgdG8gY2xhc3NpZnkgZGF0YSBwb2ludHMgYW1vbmcgTiBjbGFzc2VzLCB5b3VyIG5ldHdvcmsgc2hvdWxkIGVuZCB3aXRoIGEgZGVuc2UgbGF5ZXIgb2Ygc2l6ZSBOLgotIEluIGEgc2luZ2xlLWxhYmVsLCBtdWx0aWNsYXNzIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0sIHlvdXIgbmV0d29yayBzaG91bGQgZW5kIHdpdGggYSBgc29mdG1heGAgYWN0aXZhdGlvbiBzbyB0aGF0IGl0IHdpbGwgb3V0cHV0IGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG92ZXIgdGhlIE4gb3V0cHV0IGNsYXNzZXMuCi0gQ2F0ZWdvcmljYWwgY3Jvc3NlbnRyb3B5IGlzIGFsbW9zdCBhbHdheXMgdGhlIGxvc3MgZnVuY3Rpb24geW91IHNob3VsZCB1c2UgZm9yIHN1Y2ggcHJvYmxlbXMuIEl0IG1pbmltaXplcyB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9ucyBvdXRwdXQgYnkgdGhlIG5ldHdvcmsgYW5kIHRoZSB0cnVlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgdGFyZ2V0cy4KLSBJZiB5b3UgbmVlZCB0byBjbGFzc2lmeSBkYXRhIGludG8gYSBsYXJnZSBudW1iZXIgb2YgY2F0ZWdvcmllcywgeW91IHNob3VsZCBhdm9pZCBjcmVhdGluZyBpbmZvcm1hdGlvbiBib3R0bGVuZWNrcyBpbiB5b3VyIG5ldHdvcmsgZHVlIHRvIGludGVybWVkaWF0ZSBsYXllcnMgdGhhdCBhcmUgdG9vIHNtYWxsLg==