Wariacyjne autoenkodery
Wariacyjne autoenkodery zostały opracowane jednocześnie przez Kingmę i Wellinga w grudniu 2013 r. i Rezende, Mohameda i Wierstrę w styczniu 2014 r.. Sá to generatywne modele spraw-dzające się szczególnie w zadaniach edycji obrazu przy użyciu wektorów koncepcyjnych. Wariacyjne autoenkodery to nowoczesne podejście do autoenkoderów — sieci, która ma na celu zakodowanie danych wejściowych w postaci niskopoziomowej niejawnej przestrzeni, a następnie ich dekodowanie — jest to połączenie uczenia głębokiego z wnioskowaniem bayesowskim.
Klasyczny autoenkoder obrazu przetwarza obraz wejściowy, mapuje go na niejawną przestrzeń wektorową z zastosowaniem modułu kodera, a następnie dekoduje go do postaci wejściowej o takich samych wymiarach jak obraz oryginalny przy użyciu modułu dekodera. Autoenkoder jest trenowany tak, aby mógł dokonać rekonstrukcji obrazów wejściowych. Nakładając różne ograniczenia na wyjście kodera, można zmusić autoenkoder do uczenia się interesujących nas niejawnych reprezentacji danych. Zwykle kod ma być niskopoziomowy i rzadki (powinien zawierać głównie zera). W takim przypadku koder działa tak, jakby kompresował dane wejściowe do postaci formy składającej się z kilku bitów informacji.
W praktyce takie klasyczne autoenkodery nie pozwalają na uzyskanie szczególnie przydatnej przestrzeni o ładnej strukturze. Nie są one również zbyt wydajne w roli mechanizmów kompresji danych. W związku z tym wyszły z użycia. Technika kodowania VAE usprawniła działanie autoenkoderów, dodając do nich nieco magii statystyki, dzięki której są one w stanie uczyć się ciągłych przestrzeni charakteryzujących się określoną strukturą. W ten sposób powstało solidne narzędzie służące do generowania obrazów.
Koder VAE zamiast kompresować obraz wejściowy do określonej formy kodu niejawnej przestrzeni, zamienia obraz w parametry rozkładu statystycznego: średnią i wariancję. Oznacza to założenie, że obraz wejściowy został wygenerowany przez proces statystyczny i podczas kodowania i dekodowania należy wziąć pod uwagę losowość tego procesu. Koder VAE korzysta następnie z parametrów średniej i wariancji w celu losowego próbkowania jednego elementu rozkładu i zdekodowania go z powrotem do oryginalnej postaci. Stochastyczność tego procesu poprawia jego siłę i zmusza niejawną przestrzeń do zapisywania wszędzie reprezentacji mających znaczenie: każdy punkt próbkowany w tej przestrzeni jest dekodowany do postaci poprawnego obiektu wejściowego.
Z technicznego punktu widzenia koder VAE działa w następujący sposób: * 1. Moduł kodera zamienia próbki wejściowe input_img na dwa parametry niejawnej przestrzeni reprezentacji: z_mean i z_log_variance. * 2. Punkt z jest losowo próbkowany z niejawnego rozkładu normalnego, co ma doprowadzić do wygenerowania obrazu wejściowego za pomocą działania z = z_mean + exp(z_log_variance) * epsilon, gdzie epsilon jest losowym tensorem o małych wartościach. * 3. Moduł dekodera mapuje ten punkt w niejawnej przestrzeni z powrotem na formę oryginalnego obrazu.
Parametry kodera VAE są trenowane przy użyciu dwóch funkcji straty: straty rekonstrukcji, która wymusza dopasowanie dekodowanych próbek do obrazów wejściowych, i straty regularyzacji, która wspiera tworzenie niejawnych przestrzeni o poprawnej formie, a także umożliwia zmniejszenie nadmiernego dopasowania do treningowego zbioru danych.
Przeanalizujmy szybko implementację kodera VAE w pakiecie Keras. Schematycznie wygląda ona tak:
# EKodowanie obrazu wejściowego za pomocą parametrów średniej i wariancji.
c(z_mean, z_log_variance) %<% encoder(input_img)
# Wyciąganie punktu z przestrzeni przy użyciu małej losowej wartości epsilon.
z <- z_mean + exp(z_log_variance) * epsilon
# Dekodowanie obrazu.
reconstructed_img <- decoder(z)
# Tworzenie instancji modelu autoenkodera mapującego obraz wejściowy na jego rekonstrukcję.
model <- keras_model(input_img, reconstructed_img)
Poniższy kod pokazuje sieć kodera mapującą obrazy na parametry rozkładu prawdopodobieństwa umieszczone w przestrzeni o niejawnym charakterze. W praktyce jest to prosta sieć konwo-lucyjna przypisująca obraz wejściowy x do dwóch wektorów: z_mean i z_log_var.
r
r
library(keras)
img_shape <- c(28, 28, 1)
batch_size <- 16
latent_dim <- 2L # Dimensionality of the latent space: a plane
input_img <- layer_input(shape = img_shape)
x <- input_img %>%
layer_conv_2d(filters = 32, kernel_size = 3, padding = \same\,
activation = \relu\) %>%
layer_conv_2d(filters = 64, kernel_size = 3, padding = \same\,
activation = \relu\, strides = c(2, 2)) %>%
layer_conv_2d(filters = 64, kernel_size = 3, padding = \same\,
activation = \relu\) %>%
layer_conv_2d(filters = 64, kernel_size = 3, padding = \same\,
activation = \relu\)
shape_before_flattening <- k_int_shape(x)
x <- x %>%
layer_flatten() %>%
layer_dense(units = 32, activation = \relu\)
z_mean <- x %>%
layer_dense(units = latent_dim)
z_log_var <- x %>%
layer_dense(units = latent_dim)
Oto kod pozwalający na użycie parametrów rozkładu statystycz-nego z_mean i z_log_var, które z założenia mają pozwalać na utworzenie obrazu input_img w celu wygenerowania punktu z niejawnej przestrzeni. Część kodu R korzystającego z zaplecza pakietu Keras obudowujemy warstwą layer_lambda. W Keras wszystko musi być warstwą, a więc kod, który nie należy do wbudowanej warstwy, powinien mieć formę warstwy layer_lambda lub innej samodzielnie zdefiniowanej warstwy.
r
r
sampling <- function(args) {
c(z_mean, z_log_var) %<-% args
epsilon <- k_random_normal(shape = list(k_shape(z_mean)[1], latent_dim),
mean = 0, stddev = 1)
z_mean + k_exp(z_log_var) * epsilon
}
z <- list(z_mean, z_log_var) %>%
layer_lambda(sampling)
Poniższy fragment kodu przedstawia implementację dekodera. Wektor z jest modyfikowany tak, aby uzyskał wymiary obrazu, a następnie używanych jest kilka warstw konwolucyjnych w celu wygenerowania ostatecznej postaci obrazu wyjściowego mającego takie same wymiary jak oryginalny obraz input_img.
r
r
# This is the input where we will feed `z`.
decoder_input <- layer_input(k_int_shape(z)[-1])
x <- decoder_input %>%
# Upsample to the correct number of units
layer_dense(units = prod(as.integer(shape_before_flattening[-1])),
activation = \relu\) %>%
# Reshapes into an image of the same shape as before the last flatten layer
layer_reshape(target_shape = shape_before_flattening[-1]) %>%
# Applies and then reverses the operation to the initial stack of
# convolution layers
layer_conv_2d_transpose(filters = 32, kernel_size = 3, padding = \same\,
activation = \relu\, strides = c(2, 2)) %>%
layer_conv_2d(filters = 1, kernel_size = 3, padding = \same\,
activation = \sigmoid\)
# We end up with a feature map of the same size as the original input.
# This is our decoder model.
decoder <- keras_model(decoder_input, x)
# We then apply it to `z` to recover the decoded `z`.
z_decoded <- decoder(z)
Dualizm funkcji straty kodera VAE nie wpasowuje się w tradycyjne ramy funkcji próbującej w formie loss(input, target). W związku z tym zdefiniujemy dodatkową warstwę, która będzie wewnętrznie korzystać z metody add_loss w celu wygenerowania wartości straty.
r
r
library(R6)
CustomVariationalLayer <- R6Class(\CustomVariationalLayer\,
inherit = KerasLayer,
public = list(
vae_loss = function(x, z_decoded) {
x <- k_flatten(x)
z_decoded <- k_flatten(z_decoded)
xent_loss <- metric_binary_crossentropy(x, z_decoded)
kl_loss <- -5e-4 * k_mean(
1 + z_log_var - k_square(z_mean) - k_exp(z_log_var),
axis = -1L
)
k_mean(xent_loss + kl_loss)
},
call = function(inputs, mask = NULL) {
x <- inputs[[1]]
z_decoded <- inputs[[2]]
loss <- self$vae_loss(x, z_decoded)
self$add_loss(loss, inputs = inputs)
x
}
)
)
layer_variational <- function(object) {
create_layer(CustomVariationalLayer, object, list())
}
# Call the custom layer on the input and the decoded output to obtain
# the final model output
y <- list(input_img, z_decoded) %>%
layer_variational()
Teraz możemy utworzyć instancję modelu i ją wytrenować. Wartością straty zajęliśmy się w utworzonej ręcznie warstwie, a więc nie musimy określać zewnętrznej funkcji straty w czasie kompilacji (loss=NULL), co z kolei oznacza, że nie będziemy przekazywać docelowych danych w czasie trenowania (do funkcji fit() modelu przekazujemy tylko argument x_train).
r
r
vae <- keras_model(input_img, y)
vae %>% compile(
optimizer = \rmsprop\,
loss = NULL
)
# Trains the VAE on MNIST digits
mnist <- dataset_mnist()
c(c(x_train, y_train), c(x_test, y_test)) %<-% mnist
x_train <- x_train / 255
x_train <- array_reshape(x_train, dim =c(dim(x_train), 1))
x_test <- x_test / 255
x_test <- array_reshape(x_test, dim =c(dim(x_test), 1))
vae %>% fit(
x = x_train, y = NULL,
epochs = 10,
batch_size = batch_size,
validation_data = list(x_test, NULL)
)
Po wytrenowaniu modelu na zbiorze MNIST możemy użyć sieci de-coder w celu wygenerowania obrazów na podstawie dowolnej nie-jawnej przestrzeni wektorów:
r
r
n <- 15 # Number of rows / columns of digits
digit_size <- 28 # Height / width of digits in pixels
# Transforms linearly spaced coordinates on the unit square through the inverse
# CDF (ppf) of the Gaussian to produce values of the latent variables z,
# because the prior of the latent space is Gaussian
grid_x <- qnorm(seq(0.05, 0.95, length.out = n))
grid_y <- qnorm(seq(0.05, 0.95, length.out = n))
op <- par(mfrow = c(n, n), mar = c(0,0,0,0), bg = \black\)
for (i in 1:length(grid_x)) {
yi <- grid_x[[i]]
for (j in 1:length(grid_y)) {
xi <- grid_y[[j]]
z_sample <- matrix(c(xi, yi), nrow = 1, ncol = 2)
z_sample <- t(replicate(batch_size, z_sample, simplify = \matrix\))
x_decoded <- decoder %>% predict(z_sample, batch_size = batch_size)
digit <- array_reshape(x_decoded[1,,,], dim = c(digit_size, digit_size))
plot(as.raster(digit))
}
}
par(op)

Wygenerowana siatka cyfr pokazuje całkowitą ciągłość rozkładu różnych klas cyfr — na kolejnych obra-zach widać, że cyfry stopniowo przechodzą w siebie. Kierunki w tej przestrzeni mają znaczenie: podążając w jednym z wybranych kierunków, otrzymujemy obraz przypominający bardziej cyfrę 4, a podrażając w innym otrzymujemy obraz przypominający bardziej cyfrę 1 itd.
LS0tDQp0aXRsZTogIkdlbmVyb3dhbmllIG9icmF6w7N3Ig0Kb3V0cHV0OiANCiAgaHRtbF9ub3RlYm9vazogDQogICAgdGhlbWU6IGNlcnVsZWFuDQogICAgaGlnaGxpZ2h0OiB0ZXh0bWF0ZQ0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFKQ0KYGBgDQoNCg0KIyMgV2FyaWFjeWpuZSBhdXRvZW5rb2RlcnkNCg0KDQpXYXJpYWN5am5lIGF1dG9lbmtvZGVyeSB6b3N0YcWCeSBvcHJhY293YW5lIGplZG5vY3plxZtuaWUgcHJ6ZXogS2luZ23EmSBpIFdlbGxpbmdhIHcgZ3J1ZG5pdSAyMDEzIHIuICBpIFJlemVuZGUsIE1vaGFtZWRhIGkgV2llcnN0csSZIHcgc3R5Y3puaXUgMjAxNCByLi4gU8OhIHRvIGdlbmVyYXR5d25lIG1vZGVsZSBzcHJhdy1kemFqxIVjZSBzacSZIHN6Y3plZ8OzbG5pZSB3IHphZGFuaWFjaCBlZHljamkgb2JyYXp1IHByenkgdcW8eWNpdSB3ZWt0b3LDs3cga29uY2VwY3lqbnljaC4gV2FyaWFjeWpuZSBhdXRvZW5rb2RlcnkgdG8gbm93b2N6ZXNuZSBwb2RlasWbY2llIGRvIGF1dG9lbmtvZGVyw7N3IOKAlCBzaWVjaSwga3TDs3JhIG1hIG5hIGNlbHUgemFrb2Rvd2FuaWUgZGFueWNoIHdlasWbY2lvd3ljaCB3IHBvc3RhY2kgbmlza29wb3ppb21vd2VqIG5pZWphd25laiBwcnplc3RyemVuaSwgYSBuYXN0xJlwbmllIGljaCBkZWtvZG93YW5pZSDigJQgamVzdCB0byBwb8WCxIVjemVuaWUgdWN6ZW5pYSBnxYLEmWJva2llZ28geiB3bmlvc2tvd2FuaWVtIGJheWVzb3dza2ltLg0KDQpLbGFzeWN6bnkgYXV0b2Vua29kZXIgb2JyYXp1IHByemV0d2FyemEgb2JyYXogd2VqxZtjaW93eSwgbWFwdWplIGdvIG5hIG5pZWphd27EhSBwcnplc3RyemXFhCB3ZWt0b3Jvd8SFIHogemFzdG9zb3dhbmllbSBtb2R1xYJ1IGtvZGVyYSwgYSBuYXN0xJlwbmllIGRla29kdWplIGdvIGRvIHBvc3RhY2kgd2VqxZtjaW93ZWogbyB0YWtpY2ggc2FteWNoIHd5bWlhcmFjaCBqYWsgb2JyYXogb3J5Z2luYWxueSBwcnp5IHXFvHljaXUgbW9kdcWCdSBkZWtvZGVyYS4gQXV0b2Vua29kZXIgamVzdCB0cmVub3dhbnkgdGFrLCBhYnkgbcOzZ8WCIGRva29uYcSHIHJla29uc3RydWtjamkgb2JyYXrDs3cgd2VqxZtjaW93eWNoLiBOYWvFgmFkYWrEhWMgcsOzxbxuZSBvZ3JhbmljemVuaWEgbmEgd3lqxZtjaWUga29kZXJhLCBtb8W8bmEgem11c2nEhyBhdXRvZW5rb2RlciBkbyB1Y3plbmlhIHNpxJkgaW50ZXJlc3VqxIVjeWNoIG5hcyBuaWVqYXdueWNoIHJlcHJlemVudGFjamkgZGFueWNoLiBad3lrbGUga29kIG1hIGJ5xIcgbmlza29wb3ppb21vd3kgaSByemFka2kgKHBvd2luaWVuIHphd2llcmHEhyBnxYLDs3duaWUgemVyYSkuIFcgdGFraW0gcHJ6eXBhZGt1IGtvZGVyIGR6aWHFgmEgdGFrLCBqYWtieSBrb21wcmVzb3dhxYIgZGFuZSB3ZWrFm2Npb3dlIGRvIHBvc3RhY2kgZm9ybXkgc2vFgmFkYWrEhWNlaiBzacSZIHoga2lsa3UgYml0w7N3IGluZm9ybWFjamkuDQoNCiFbQXV0b2VuY29kZXJdKGltZ1w4XzRhLnBuZykNCg0KVyBwcmFrdHljZSB0YWtpZSBrbGFzeWN6bmUgYXV0b2Vua29kZXJ5IG5pZSBwb3p3YWxhasSFIG5hIHV6eXNrYW5pZSBzemN6ZWfDs2xuaWUgcHJ6eWRhdG5laiBwcnplc3RyemVuaSBvIMWCYWRuZWogc3RydWt0dXJ6ZS4gTmllIHPEhSBvbmUgcsOzd25pZcW8IHpieXQgd3lkYWpuZSB3IHJvbGkgbWVjaGFuaXptw7N3IGtvbXByZXNqaSBkYW55Y2guIFcgendpxIV6a3UgeiB0eW0gd3lzesWCeSB6IHXFvHljaWEuIFRlY2huaWthIGtvZG93YW5pYSBWQUUgdXNwcmF3bmnFgmEgZHppYcWCYW5pZSBhdXRvZW5rb2RlcsOzdywgZG9kYWrEhWMgZG8gbmljaCBuaWVjbyBtYWdpaSBzdGF0eXN0eWtpLCBkemnEmWtpIGt0w7NyZWogc8SFIG9uZSB3IHN0YW5pZSB1Y3p5xIcgc2nEmSBjacSFZ8WCeWNoIHByemVzdHJ6ZW5pIGNoYXJha3Rlcnl6dWrEhWN5Y2ggc2nEmSBva3JlxZtsb27EhSBzdHJ1a3R1csSFLiBXIHRlbiBzcG9zw7NiIHBvd3N0YcWCbyBzb2xpZG5lIG5hcnrEmWR6aWUgc8WCdcW8xIVjZSBkbyBnZW5lcm93YW5pYSBvYnJhesOzdy4NCg0KS29kZXIgVkFFIHphbWlhc3Qga29tcHJlc293YcSHIG9icmF6IHdlasWbY2lvd3kgZG8gb2tyZcWbbG9uZWogZm9ybXkga29kdSBuaWVqYXduZWogcHJ6ZXN0cnplbmksIHphbWllbmlhIG9icmF6IHcgcGFyYW1ldHJ5IHJvemvFgmFkdSBzdGF0eXN0eWN6bmVnbzogxZtyZWRuacSFIGkgd2FyaWFuY2rEmS4gT3puYWN6YSB0byB6YcWCb8W8ZW5pZSwgxbxlIG9icmF6IHdlasWbY2lvd3kgem9zdGHFgiB3eWdlbmVyb3dhbnkgcHJ6ZXogcHJvY2VzIHN0YXR5c3R5Y3pueSBpIHBvZGN6YXMga29kb3dhbmlhIGkgZGVrb2Rvd2FuaWEgbmFsZcW8eSB3emnEhcSHIHBvZCB1d2FnxJkgbG9zb3dvxZvEhyB0ZWdvIHByb2Nlc3UuIEtvZGVyIFZBRSBrb3J6eXN0YSBuYXN0xJlwbmllIHogcGFyYW1ldHLDs3cgxZtyZWRuaWVqIGkgd2FyaWFuY2ppIHcgY2VsdSBsb3Nvd2VnbyBwcsOzYmtvd2FuaWEgamVkbmVnbyBlbGVtZW50dSByb3prxYJhZHUgaSB6ZGVrb2Rvd2FuaWEgZ28geiBwb3dyb3RlbSBkbyBvcnlnaW5hbG5laiBwb3N0YWNpLiBTdG9jaGFzdHljem5vxZvEhyB0ZWdvIHByb2Nlc3UgcG9wcmF3aWEgamVnbyBzacWCxJkgaSB6bXVzemEgbmllamF3bsSFIHByemVzdHJ6ZcWEIGRvIHphcGlzeXdhbmlhIHdzesSZZHppZSByZXByZXplbnRhY2ppIG1hasSFY3ljaCB6bmFjemVuaWU6IGthxbxkeSBwdW5rdCBwcsOzYmtvd2FueSB3IHRlaiBwcnplc3RyemVuaSBqZXN0IGRla29kb3dhbnkgZG8gcG9zdGFjaSBwb3ByYXduZWdvIG9iaWVrdHUgd2VqxZtjaW93ZWdvLg0KDQoNCiFbVkFFXShpbWdcOF80Yi5wbmcpDQoNClogdGVjaG5pY3puZWdvIHB1bmt0dSB3aWR6ZW5pYSBrb2RlciBWQUUgZHppYcWCYSB3IG5hc3TEmXB1asSFY3kgc3Bvc8OzYjoNCiogMS4JTW9kdcWCIGtvZGVyYSB6YW1pZW5pYSBwcsOzYmtpIHdlasWbY2lvd2UgaW5wdXRfaW1nIG5hIGR3YSBwYXJhbWV0cnkgbmllamF3bmVqIHByemVzdHJ6ZW5pIHJlcHJlemVudGFjamk6IHpfbWVhbiBpIHpfbG9nX3ZhcmlhbmNlLg0KKiAyLglQdW5rdCB6IGplc3QgbG9zb3dvIHByw7Nia293YW55IHogbmllamF3bmVnbyByb3prxYJhZHUgbm9ybWFsbmVnbywgY28gbWEgZG9wcm93YWR6acSHIGRvIHd5Z2VuZXJvd2FuaWEgb2JyYXp1IHdlasWbY2lvd2VnbyB6YSBwb21vY8SFIGR6aWHFgmFuaWEgeiA9IHpfbWVhbiArIGV4cCh6X2xvZ192YXJpYW5jZSkgKiBlcHNpbG9uLCBnZHppZSBlcHNpbG9uIGplc3QgbG9zb3d5bSB0ZW5zb3JlbSBvIG1hxYJ5Y2ggd2FydG/Fm2NpYWNoLg0KKiAzLglNb2R1xYIgZGVrb2RlcmEgbWFwdWplIHRlbiBwdW5rdCB3IG5pZWphd25laiBwcnplc3RyemVuaSB6IHBvd3JvdGVtIG5hIGZvcm3EmSBvcnlnaW5hbG5lZ28gb2JyYXp1Lg0KDQpQYXJhbWV0cnkga29kZXJhIFZBRSBzxIUgdHJlbm93YW5lIHByenkgdcW8eWNpdSBkd8OzY2ggZnVua2NqaSBzdHJhdHk6IHN0cmF0eSByZWtvbnN0cnVrY2ppLCBrdMOzcmEgd3ltdXN6YSBkb3Bhc293YW5pZSBkZWtvZG93YW55Y2ggcHLDs2JlayBkbyBvYnJhesOzdyB3ZWrFm2Npb3d5Y2gsIGkgc3RyYXR5IHJlZ3VsYXJ5emFjamksIGt0w7NyYSB3c3BpZXJhIHR3b3J6ZW5pZSBuaWVqYXdueWNoIHByemVzdHJ6ZW5pIG8gcG9wcmF3bmVqIGZvcm1pZSwgYSB0YWvFvGUgdW1vxbxsaXdpYSB6bW5pZWpzemVuaWUgbmFkbWllcm5lZ28gZG9wYXNvd2FuaWEgZG8gdHJlbmluZ293ZWdvIHpiaW9ydSBkYW55Y2guIA0KDQpQcnplYW5hbGl6dWpteSBzenlia28gaW1wbGVtZW50YWNqxJkga29kZXJhIFZBRSB3IHBha2llY2llIEtlcmFzLiBTY2hlbWF0eWN6bmllIHd5Z2zEhWRhIG9uYSB0YWs6DQoNCg0KYGBge3IsIGV2YWw9RkFMU0V9DQojIEVLb2Rvd2FuaWUgb2JyYXp1IHdlasWbY2lvd2VnbyB6YSBwb21vY8SFIHBhcmFtZXRyw7N3IMWbcmVkbmllaiBpIHdhcmlhbmNqaS4NCmMoel9tZWFuLCB6X2xvZ192YXJpYW5jZSkgJTwlIGVuY29kZXIoaW5wdXRfaW1nKQ0KDQojIFd5Y2nEhWdhbmllIHB1bmt0dSB6IHByemVzdHJ6ZW5pIHByenkgdcW8eWNpdSBtYcWCZWogbG9zb3dlaiB3YXJ0b8WbY2kgZXBzaWxvbi4NCnogPC0gel9tZWFuICsgZXhwKHpfbG9nX3ZhcmlhbmNlKSAqIGVwc2lsb24gDQoNCiMgRGVrb2Rvd2FuaWUgb2JyYXp1Lg0KcmVjb25zdHJ1Y3RlZF9pbWcgPC0gZGVjb2Rlcih6KSANCg0KIyBUd29yemVuaWUgaW5zdGFuY2ppIG1vZGVsdSBhdXRvZW5rb2RlcmEgbWFwdWrEhWNlZ28gb2JyYXogd2VqxZtjaW93eSBuYSBqZWdvIHJla29uc3RydWtjasSZLg0KbW9kZWwgPC0ga2VyYXNfbW9kZWwoaW5wdXRfaW1nLCByZWNvbnN0cnVjdGVkX2ltZykNCg0KYGBgDQoNClBvbmnFvHN6eSBrb2QgcG9rYXp1amUgc2llxIcga29kZXJhIG1hcHVqxIVjxIUgb2JyYXp5IG5hIHBhcmFtZXRyeSByb3prxYJhZHUgcHJhd2RvcG9kb2JpZcWEc3R3YSB1bWllc3pjem9uZSB3IHByemVzdHJ6ZW5pIG8gbmllamF3bnltIGNoYXJha3RlcnplLiBXIHByYWt0eWNlIGplc3QgdG8gcHJvc3RhIHNpZcSHIGtvbndvLWx1Y3lqbmEgcHJ6eXBpc3VqxIVjYSBvYnJheiB3ZWrFm2Npb3d5IHggZG8gZHfDs2NoIHdla3RvcsOzdzogel9tZWFuIGkgel9sb2dfdmFyLg0KDQpgYGB7cn0NCmxpYnJhcnkoa2VyYXMpDQoNCmltZ19zaGFwZSA8LSBjKDI4LCAyOCwgMSkNCmJhdGNoX3NpemUgPC0gMTYNCmxhdGVudF9kaW0gPC0gMkwgICMgTGljemJhIHd5bWlhcsOzdyBuaWVqYXduZWogcHJ6ZXN0cnplbmk6IHByYWN1amVteSB6IHByemVzdHJ6ZW5pxIUgZHd1d3ltaWFyb3fEhS4NCg0KaW5wdXRfaW1nIDwtIGxheWVyX2lucHV0KHNoYXBlID0gaW1nX3NoYXBlKQ0KDQp4IDwtIGlucHV0X2ltZyAlPiUgDQogIGxheWVyX2NvbnZfMmQoZmlsdGVycyA9IDMyLCBrZXJuZWxfc2l6ZSA9IDMsIHBhZGRpbmcgPSAic2FtZSIsIA0KICAgICAgICAgICAgICAgIGFjdGl2YXRpb24gPSAicmVsdSIpICU+JSANCiAgbGF5ZXJfY29udl8yZChmaWx0ZXJzID0gNjQsIGtlcm5lbF9zaXplID0gMywgcGFkZGluZyA9ICJzYW1lIiwgDQogICAgICAgICAgICAgICAgYWN0aXZhdGlvbiA9ICJyZWx1Iiwgc3RyaWRlcyA9IGMoMiwgMikpICU+JQ0KICBsYXllcl9jb252XzJkKGZpbHRlcnMgPSA2NCwga2VybmVsX3NpemUgPSAzLCBwYWRkaW5nID0gInNhbWUiLCANCiAgICAgICAgICAgICAgICBhY3RpdmF0aW9uID0gInJlbHUiKSAlPiUNCiAgbGF5ZXJfY29udl8yZChmaWx0ZXJzID0gNjQsIGtlcm5lbF9zaXplID0gMywgcGFkZGluZyA9ICJzYW1lIiwgDQogICAgICAgICAgICAgICAgYWN0aXZhdGlvbiA9ICJyZWx1IikgDQoNCnNoYXBlX2JlZm9yZV9mbGF0dGVuaW5nIDwtIGtfaW50X3NoYXBlKHgpDQoNCnggPC0geCAlPiUgDQogIGxheWVyX2ZsYXR0ZW4oKSAlPiUgDQogIGxheWVyX2RlbnNlKHVuaXRzID0gMzIsIGFjdGl2YXRpb24gPSAicmVsdSIpDQoNCnpfbWVhbiA8LSB4ICU+JSANCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSBsYXRlbnRfZGltKQ0KDQp6X2xvZ192YXIgPC0geCAlPiUgDQogIGxheWVyX2RlbnNlKHVuaXRzID0gbGF0ZW50X2RpbSkNCmBgYA0KDQpPdG8ga29kIHBvendhbGFqxIVjeSBuYSB1xbx5Y2llIHBhcmFtZXRyw7N3IHJvemvFgmFkdSBzdGF0eXN0eWN6LW5lZ28gel9tZWFuIGkgel9sb2dfdmFyLCBrdMOzcmUgeiB6YcWCb8W8ZW5pYSBtYWrEhSBwb3p3YWxhxIcgbmEgdXR3b3J6ZW5pZSBvYnJhenUgaW5wdXRfaW1nIHcgY2VsdSB3eWdlbmVyb3dhbmlhIHB1bmt0dSB6IG5pZWphd25laiBwcnplc3RyemVuaS4gQ3rEmcWbxIcga29kdSBSIGtvcnp5c3RhasSFY2VnbyB6IHphcGxlY3phIHBha2lldHUgS2VyYXMgb2J1ZG93dWplbXkgd2Fyc3R3xIUgbGF5ZXJfbGFtYmRhLiBXIEtlcmFzIHdzenlzdGtvIG11c2kgYnnEhyB3YXJzdHfEhSwgYSB3acSZYyBrb2QsIGt0w7NyeSBuaWUgbmFsZcW8eSBkbyB3YnVkb3dhbmVqIHdhcnN0d3ksIHBvd2luaWVuIG1pZcSHIGZvcm3EmSB3YXJzdHd5IGxheWVyX2xhbWJkYSBsdWIgaW5uZWogc2Ftb2R6aWVsbmllIHpkZWZpbmlvd2FuZWogd2Fyc3R3eS4NCg0KYGBge3J9DQpzYW1wbGluZyA8LSBmdW5jdGlvbihhcmdzKSB7DQogIGMoel9tZWFuLCB6X2xvZ192YXIpICU8LSUgYXJncw0KICBlcHNpbG9uIDwtIGtfcmFuZG9tX25vcm1hbChzaGFwZSA9IGxpc3Qoa19zaGFwZSh6X21lYW4pWzFdLCBsYXRlbnRfZGltKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWVhbiA9IDAsIHN0ZGRldiA9IDEpDQogIHpfbWVhbiArIGtfZXhwKHpfbG9nX3ZhcikgKiBlcHNpbG9uDQp9DQoNCnogPC0gbGlzdCh6X21lYW4sIHpfbG9nX3ZhcikgJT4lIA0KICBsYXllcl9sYW1iZGEoc2FtcGxpbmcpDQpgYGANCg0KUG9uacW8c3p5IGZyYWdtZW50IGtvZHUgcHJ6ZWRzdGF3aWEgaW1wbGVtZW50YWNqxJkgZGVrb2RlcmEuIFdla3RvciB6IGplc3QgbW9keWZpa293YW55IHRhaywgYWJ5IHV6eXNrYcWCIHd5bWlhcnkgb2JyYXp1LCBhIG5hc3TEmXBuaWUgdcW8eXdhbnljaCBqZXN0IGtpbGthIHdhcnN0dyBrb253b2x1Y3lqbnljaCB3IGNlbHUgd3lnZW5lcm93YW5pYSBvc3RhdGVjem5laiBwb3N0YWNpIG9icmF6dSB3eWrFm2Npb3dlZ28gbWFqxIVjZWdvIHRha2llIHNhbWUgd3ltaWFyeSBqYWsgb3J5Z2luYWxueSBvYnJheiBpbnB1dF9pbWcuDQoNCmBgYHtyfQ0KIyBXZWrFm2NpZSB3ZWt0b3JhIHouDQpkZWNvZGVyX2lucHV0IDwtIGxheWVyX2lucHV0KGtfaW50X3NoYXBlKHopWy0xXSkNCg0KeCA8LSBkZWNvZGVyX2lucHV0ICU+JSANCiAgIyBad2nEmWtzemFuaWUgcm96ZHppZWxjem/Fm2NpIG9iaWVrdHUgd2VqxZtjaW93ZWdvLg0KICBsYXllcl9kZW5zZSh1bml0cyA9IHByb2QoYXMuaW50ZWdlcihzaGFwZV9iZWZvcmVfZmxhdHRlbmluZ1stMV0pKSwNCiAgICAgICAgICAgICAgYWN0aXZhdGlvbiA9ICJyZWx1IikgJT4lIA0KICAjIFptaWFuYSBrc3p0YcWCdHUgd2VrdG9yYSB3IGNlbHUgdXp5c2thbmlhIG1hcCBjZWNoIG8gdGFraW0gc2FteW0ga3N6dGHFgmNpZSBqYWsga3N6dGHFgnQgbWFweSBjZWNoIHByemVkIG9zdGF0bmnEhSB3YXJzdHfEhSBmbGF0dGVuIG1vZHXFgnUga29kdWrEhWNlZ28uDQogIGxheWVyX3Jlc2hhcGUodGFyZ2V0X3NoYXBlID0gc2hhcGVfYmVmb3JlX2ZsYXR0ZW5pbmdbLTFdKSAlPiUgDQogICMgV2Fyc3R3eSB1xbx5d2FuZSB3IGNlbHUgb2Rrb2Rvd2FuaWEgd2VrdG9yYSB6IGRvIGZvcm15IG1hcHkgY2VjaCANCiAgIyBvIHRha2ltIHNhbXltIHJvem1pYXJ6ZSBqYWsgb3J5Z2luYWxueSBvYnJheiB3ZWrFm2Npb3d5Lg0KICBsYXllcl9jb252XzJkX3RyYW5zcG9zZShmaWx0ZXJzID0gMzIsIGtlcm5lbF9zaXplID0gMywgcGFkZGluZyA9ICJzYW1lIiwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0aXZhdGlvbiA9ICJyZWx1Iiwgc3RyaWRlcyA9IGMoMiwgMikpICU+JSAgDQogIGxheWVyX2NvbnZfMmQoZmlsdGVycyA9IDEsIGtlcm5lbF9zaXplID0gMywgcGFkZGluZyA9ICJzYW1lIiwNCiAgICAgICAgICAgICAgICBhY3RpdmF0aW9uID0gInNpZ21vaWQiKSAgDQoNCiMgVHdvcnplbmllIGluc3RhbmNqaSBtb2RlbHUgZGVrb2RlcmEgemFtaWVuaWFqxIVjZWdvIG9iaWVrdCBkZWNvZGVyX2lucHV0IG5hIHpkZWtvZG93YW55IG9icmF6Lg0KZGVjb2RlciA8LSBrZXJhc19tb2RlbChkZWNvZGVyX2lucHV0LCB4KQ0KDQojIFByenlqbXVqZSB3ZWt0b3IgeiBpIHp3cmFjYSBqZWdvIHpkZWtvZG93YW7EhSBwb3N0YcSHLg0Kel9kZWNvZGVkIDwtIGRlY29kZXIoeikgDQpgYGANCg0KRHVhbGl6bSBmdW5rY2ppIHN0cmF0eSBrb2RlcmEgVkFFIG5pZSB3cGFzb3d1amUgc2nEmSB3IHRyYWR5Y3lqbmUgcmFteSBmdW5rY2ppIHByw7NidWrEhWNlaiB3IGZvcm1pZSBsb3NzKGlucHV0LCB0YXJnZXQpLiBXIHp3acSFemt1IHogdHltIHpkZWZpbml1amVteSBkb2RhdGtvd8SFIHdhcnN0d8SZLCBrdMOzcmEgYsSZZHppZSB3ZXduxJl0cnpuaWUga29yenlzdGHEhyB6IG1ldG9keSBhZGRfbG9zcyB3IGNlbHUgd3lnZW5lcm93YW5pYSB3YXJ0b8WbY2kgc3RyYXR5Lg0KDQpgYGB7cn0NCmxpYnJhcnkoUjYpDQoNCkN1c3RvbVZhcmlhdGlvbmFsTGF5ZXIgPC0gUjZDbGFzcygiQ3VzdG9tVmFyaWF0aW9uYWxMYXllciIsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgDQogIGluaGVyaXQgPSBLZXJhc0xheWVyLA0KICANCiAgcHVibGljID0gbGlzdCgNCiAgICANCiAgICB2YWVfbG9zcyA9IGZ1bmN0aW9uKHgsIHpfZGVjb2RlZCkgew0KICAgICAgeCA8LSBrX2ZsYXR0ZW4oeCkNCiAgICAgIHpfZGVjb2RlZCA8LSBrX2ZsYXR0ZW4oel9kZWNvZGVkKQ0KICAgICAgeGVudF9sb3NzIDwtIG1ldHJpY19iaW5hcnlfY3Jvc3NlbnRyb3B5KHgsIHpfZGVjb2RlZCkNCiAgICAgIGtsX2xvc3MgPC0gLTVlLTQgKiBrX21lYW4oDQogICAgICAgIDEgKyB6X2xvZ192YXIgLSBrX3NxdWFyZSh6X21lYW4pIC0ga19leHAoel9sb2dfdmFyKSwgDQogICAgICAgIGF4aXMgPSAtMUwNCiAgICAgICkNCiAgICAgIGtfbWVhbih4ZW50X2xvc3MgKyBrbF9sb3NzKQ0KICAgIH0sDQogICAgDQogICAgY2FsbCA9IGZ1bmN0aW9uKGlucHV0cywgbWFzayA9IE5VTEwpIHsNCiAgICAgIHggPC0gaW5wdXRzW1sxXV0NCiAgICAgIHpfZGVjb2RlZCA8LSBpbnB1dHNbWzJdXQ0KICAgICAgbG9zcyA8LSBzZWxmJHZhZV9sb3NzKHgsIHpfZGVjb2RlZCkNCiAgICAgIHNlbGYkYWRkX2xvc3MobG9zcywgaW5wdXRzID0gaW5wdXRzKQ0KICAgICAgeA0KICAgIH0NCiAgKQ0KKQ0KDQpsYXllcl92YXJpYXRpb25hbCA8LSBmdW5jdGlvbihvYmplY3QpIHsgDQogIGNyZWF0ZV9sYXllcihDdXN0b21WYXJpYXRpb25hbExheWVyLCBvYmplY3QsIGxpc3QoKSkNCn0gDQoNCiMgV3l3b8WCdWplbXkgd8WCYXNuxIUgd2Fyc3R3xJkgbmEgb2JpZWtjaWUgd2VqxZtjaW93eW0gaSBvZGtvZG93YW55bSBvYmlla2NpZSB3eWrFm2Npb3d5bSANCiMgdyBjZWx1IHd5Z2VuZXJvd2FuaWEgb3N0YXRlY3puZWdvIG9iaWVrdHUgZ2VuZXJvd2FuZWdvIHByemV6IG1vZGVsLg0KeSA8LSBsaXN0KGlucHV0X2ltZywgel9kZWNvZGVkKSAlPiUgDQogIGxheWVyX3ZhcmlhdGlvbmFsKCkgDQpgYGANCg0KVGVyYXogbW/FvGVteSB1dHdvcnp5xIcgaW5zdGFuY2rEmSBtb2RlbHUgaSBqxIUgd3l0cmVub3dhxIcuIFdhcnRvxZtjacSFIHN0cmF0eSB6YWrEmWxpxZtteSBzacSZIHcgdXR3b3J6b25laiByxJljem5pZSB3YXJzdHdpZSwgYSB3acSZYyBuaWUgbXVzaW15IG9rcmXFm2xhxIcgemV3bsSZdHJ6bmVqIGZ1bmtjamkgc3RyYXR5IHcgY3phc2llIGtvbXBpbGFjamkgKGxvc3M9TlVMTCksIGNvIHoga29sZWkgb3puYWN6YSwgxbxlIG5pZSBixJlkemllbXkgcHJ6ZWthenl3YcSHIGRvY2Vsb3d5Y2ggZGFueWNoIHcgY3phc2llIHRyZW5vd2FuaWEgKGRvIGZ1bmtjamkgZml0KCkgbW9kZWx1IHByemVrYXp1amVteSB0eWxrbyBhcmd1bWVudCB4X3RyYWluKS4NCg0KYGBge3IsIGVjaG89VFJVRSwgcmVzdWx0cz0naGlkZSd9DQp2YWUgPC0ga2VyYXNfbW9kZWwoaW5wdXRfaW1nLCB5KQ0KDQp2YWUgJT4lIGNvbXBpbGUoDQogIG9wdGltaXplciA9ICJybXNwcm9wIiwNCiAgbG9zcyA9IE5VTEwNCikNCg0KIyBUcmVub3dhbmllIG5hIHpiaW9yemUgTU5JU1QuDQptbmlzdCA8LSBkYXRhc2V0X21uaXN0KCkgDQpjKGMoeF90cmFpbiwgeV90cmFpbiksIGMoeF90ZXN0LCB5X3Rlc3QpKSAlPC0lIG1uaXN0DQoNCnhfdHJhaW4gPC0geF90cmFpbiAvIDI1NQ0KeF90cmFpbiA8LSBhcnJheV9yZXNoYXBlKHhfdHJhaW4sIGRpbSA9YyhkaW0oeF90cmFpbiksIDEpKQ0KDQp4X3Rlc3QgPC0geF90ZXN0IC8gMjU1DQp4X3Rlc3QgPC0gYXJyYXlfcmVzaGFwZSh4X3Rlc3QsIGRpbSA9YyhkaW0oeF90ZXN0KSwgMSkpDQoNCnZhZSAlPiUgZml0KA0KICB4ID0geF90cmFpbiwgeSA9IE5VTEwsDQogIGVwb2NocyA9IDEwLA0KICBiYXRjaF9zaXplID0gYmF0Y2hfc2l6ZSwNCiAgdmFsaWRhdGlvbl9kYXRhID0gbGlzdCh4X3Rlc3QsIE5VTEwpDQopDQpgYGANCg0KUG8gd3l0cmVub3dhbml1IG1vZGVsdSBuYSB6YmlvcnplIE1OSVNUIG1vxbxlbXkgdcW8ecSHIHNpZWNpIGRlLWNvZGVyIHcgY2VsdSB3eWdlbmVyb3dhbmlhIG9icmF6w7N3IG5hIHBvZHN0YXdpZSBkb3dvbG5laiBuaWUtamF3bmVqIHByemVzdHJ6ZW5pIHdla3RvcsOzdzoNCg0KYGBge3J9DQpuIDwtIDE1ICAgICAgICAgICAgIyBXecWbd2lldGxhbXkgc2lhdGvEmSAxNe+CtDE1IGN5ZnIgKMWCxIVjem5pZSAyNTUgY3lmcikuDQpkaWdpdF9zaXplIDwtIDI4ICAgIyBXeXNva2/Fm8SHIC8gc3plcm9rb8WbxIcgY3lmciAocGlrc2VsZSkNCg0KIyBUcmFuc2Zvcm1hY2phIGxpbmlvd3ljaCB3c3DDs8WCcnrEmWRueWNoIHByenkgdcW8eWNpdSBmdW5rY2ppIHFub3JtIA0KIyB3IGNlbHUgd3lnZW5lcm93YW5pYSB3YXJ0b8WbY2kgbmllamF3bmVqIHptaWVubmVqIHogKHByYWN1amVteSB6IHByemVzdHJ6ZW5pxIUgR2F1c3NhKS4NCg0KZ3JpZF94IDwtIHFub3JtKHNlcSgwLjA1LCAwLjk1LCBsZW5ndGgub3V0ID0gbikpDQpncmlkX3kgPC0gcW5vcm0oc2VxKDAuMDUsIDAuOTUsIGxlbmd0aC5vdXQgPSBuKSkNCg0Kb3AgPC0gcGFyKG1mcm93ID0gYyhuLCBuKSwgbWFyID0gYygwLDAsMCwwKSwgYmcgPSAiYmxhY2siKQ0KZm9yIChpIGluIDE6bGVuZ3RoKGdyaWRfeCkpIHsNCiAgeWkgPC0gZ3JpZF94W1tpXV0NCiAgZm9yIChqIGluIDE6bGVuZ3RoKGdyaWRfeSkpIHsNCiAgICB4aSA8LSBncmlkX3lbW2pdXQ0KICAgIHpfc2FtcGxlIDwtIG1hdHJpeChjKHhpLCB5aSksIG5yb3cgPSAxLCBuY29sID0gMikNCiAgICB6X3NhbXBsZSA8LSB0KHJlcGxpY2F0ZShiYXRjaF9zaXplLCB6X3NhbXBsZSwgc2ltcGxpZnkgPSAibWF0cml4IikpDQogICAgeF9kZWNvZGVkIDwtIGRlY29kZXIgJT4lIHByZWRpY3Qoel9zYW1wbGUsIGJhdGNoX3NpemUgPSBiYXRjaF9zaXplKQ0KICAgIGRpZ2l0IDwtIGFycmF5X3Jlc2hhcGUoeF9kZWNvZGVkWzEsLCxdLCBkaW0gPSBjKGRpZ2l0X3NpemUsIGRpZ2l0X3NpemUpKQ0KICAgIHBsb3QoYXMucmFzdGVyKGRpZ2l0KSkNCiAgfQ0KfQ0KcGFyKG9wKQ0KYGBgDQoNCld5Z2VuZXJvd2FuYSBzaWF0a2EgY3lmciBwb2thenVqZSBjYcWCa293aXTEhSBjacSFZ8WCb8WbxIcgcm96a8WCYWR1IHLDs8W8bnljaCBrbGFzIGN5ZnIg4oCUIG5hIGtvbGVqbnljaCBvYnJhLXphY2ggd2lkYcSHLCDFvGUgY3lmcnkgc3RvcG5pb3dvIHByemVjaG9kesSFIHcgc2llYmllLiBLaWVydW5raSB3IHRlaiBwcnplc3RyemVuaSBtYWrEhSB6bmFjemVuaWU6IHBvZMSFxbxhasSFYyB3IGplZG55bSB6IHd5YnJhbnljaCBraWVydW5rw7N3LCBvdHJ6eW11amVteSBvYnJheiBwcnp5cG9taW5hasSFY3kgYmFyZHppZWogY3lmcsSZIDQsIGEgcG9kcmHFvGFqxIVjIHcgaW5ueW0gb3RyenltdWplbXkgb2JyYXogcHJ6eXBvbWluYWrEhWN5IGJhcmR6aWVqIGN5ZnLEmSAxIGl0ZC4NCg0K