Modelo Básico- Clase 1
library(tidyverse)
library(modelr)
options(na.action = na.warn)
datos sim1
El paquete modlr viene con un set de datos de juguete llamado sim1
ggplot(sim1, aes(x, y)) +
geom_point()
Se puede ver un patrón fuerte en los datos. Pareciera que el modelo lineal y = a_0 + a_1 * x
podría servir.
Modelos al azar
Para empezar, generemos aleatoriamente varios modelos lineales para ver qué pinta tienen. Para eso, podemos usar geom_abline ()
que toma una pendiente e intercepto como parámetros.
models <- tibble(
a1 = runif(250, -20, 40),
a2 = runif(250, -5, 5)
)
ggplot(sim1, aes(x, y)) +
geom_abline(aes(intercept = a1, slope = a2), data = models, alpha = 1/4) +
geom_point()
A simple vista podemos apreciar que algunos modelos son mejores que otros. Pero necesitamos una forma de cuantificar cuales son los mejores modelos.
distancias
Una forma de definir mejor es pensar en aquel modelo que minimiza la distancia vertical con cada punto:
Para eso, eligamos un modelo cualquiera:
\[ y= 7 + 1.5*x\]
(para que se vean mejor las distancias, corremos un poquito cada punto sobre el eje x)
dist1 <- sim1 %>%
mutate(
dodge = rep(c(-1, 0, 1) / 20, 10),
x1 = x + dodge,
pred = 7 + x1 * 1.5
)
ggplot(dist1, aes(x1, y)) +
geom_abline(intercept = 7, slope = 1.5, colour = "grey40") +
geom_point(colour = "grey40") +
geom_linerange(aes(ymin = y, ymax = pred), colour = "#3366FF")
La distancia de cada punto a la recta es la diferencia entre lo que predice nuestro modelo y el valor real
Para computar la distancia, primero necesitamos una función que represente a nuestro modelo:
Ejercicio 1
Crear una función que reciba un vector con los parametros del modelo, y el set de datos, y genere la predicción:
model1 <- function(a, data) {
a[1] + data$x * a[2]
}
model1(c(7, 1.5), sim1)
[1] 8.5 8.5 8.5 10.0 10.0 10.0 11.5 11.5 11.5 13.0 13.0 13.0 14.5 14.5 14.5 16.0 16.0 16.0 17.5 17.5 17.5 19.0 19.0 19.0 20.5 20.5 20.5
[28] 22.0 22.0 22.0
Ahora, necesitamos una forma de calcular los residuos y agruparlos. Como se vió en la clase teórica, esto lo vamos a hacer con el error cuadrático medio
Ejercicio 2
Necesitamos una función, con el mismo input que la anterior, que calcule el promedio de los errores cuadráticos (ECM)
\[ECM = \sqrt\frac{\sum_i^n{(\hat{y_i} - y_i)^2}}{n}\]
measure_distance <- function(mod, data) {
diff <- data$y - model1(mod, data)
sqrt(mean(diff ^ 2))
}
measure_distance(c(7, 1.5), sim1)
[1] 2.665212
Evaluando los modelos aleatorios
Ahora podemos calcular el ECM para todos los modelos del dataframe models. Para eso utilizamos el paquete purrr, para ejecutar varias veces la misma función sobre varios elementos.
MAP
La función map toma un input, una función para aplicar, y alguna otra cosa (por ejemplo parametros que necesite la función)
- map(.x, .f, …)
- map(VECTOR_OR_LIST_INPUT, FUNCTION_TO_APPLY, OPTIONAL_OTHER_STUFF)
Usamos map2 cuando tenemos que pasar dos input, que se aplican sobre una función:
- map2(.x, .y, .f, …)
- map2(INPUT_ONE, INPUT_TWO, FUNCTION_TO_APPLY, OPTIONAL_OTHER_STUFF)
Si tenemos más de dos…
- pmap(.l, .f, …)
- pmap(LIST_OF_INPUT_LISTS, FUNCTION_TO_APPLY, OPTIONAL_OTHER_STUFF)
Nosotros tenemos que pasar pasar los valores de a1 y a2 (dos parámetros –> map2), pero como nuestra función toma sólo uno (el vector a), nos armamos una función de ayuda para wrapear a1 y a2
sim1_dist <- function(a1, a2) {
measure_distance(c(a1, a2), sim1)
}
models <- models %>%
mutate(dist = purrr::map2_dbl(a1, a2, sim1_dist))
models
A continuación, superpongamos los 10 mejores modelos a los datos. Coloreamos los modelos por -dist
: esta es una manera fácil de asegurarse de que los mejores modelos (es decir, los que tienen la menor distancia) obtengan los colores más brillantes.
ggplot(sim1, aes(x, y)) +
geom_point(size = 2, colour = "grey30") +
geom_abline(
aes(intercept = a1, slope = a2, colour = -dist),
data = filter(models, rank(dist) <= 10)
)
También podemos pensar en estos modelos como observaciones y visualizar con un gráfico de dispersión de a1
vsa2
, nuevamente coloreado por -dist
. Ya no podemos ver directamente cómo se compara el modelo con los datos, pero podemos ver muchos modelos a la vez. Nuevamente, destaqué los 10 mejores modelos, esta vez dibujando círculos rojos debajo de ellos.
ggplot(models, aes(a1, a2)) +
geom_point(data = filter(models, rank(dist) <= 10), size = 4, colour = "red") +
geom_point(aes(colour = -dist))
Grid search
En lugar de probar muchos modelos aleatorios, podríamos ser más sistemáticos y generar una cuadrícula de puntos uniformemente espaciada (esto se denomina grid search). Elegimos los parámetros de la grilla aproximadamente mirando dónde estaban los mejores modelos en el gráfico anterior.
grid <- expand.grid(
a1 = seq(-5, 20, length = 25),
a2 = seq(1, 3, length = 25)
) %>%
mutate(dist = purrr::map2_dbl(a1, a2, sim1_dist))
grid %>%
ggplot(aes(a1, a2)) +
geom_point(data = filter(grid, rank(dist) <= 10), size = 4, colour = "red") +
geom_point(aes(colour = -dist))
Cuando superponemos los 10 mejores modelos en los datos originales, todos se ven bastante bien:
ggplot(sim1, aes(x, y)) +
geom_point(size = 2, colour = "grey30") +
geom_abline(
aes(intercept = a1, slope = a2, colour = -dist),
data = filter(grid, rank(dist) <= 10)
)
Modelo Básico- Clase 2
óptimo por métodos numéricos
Podríamos imaginar iterativamente haciendo la cuadrícula más fina y fina hasta que nos centramos en el mejor modelo. Pero hay una forma mejor de abordar ese problema: una herramienta de minimización numérica llamada búsqueda Newton-Raphson.
La intuición de Newton-Raphson es bastante simple: Se elige un punto de partida y se busca la pendiente más inclinada. Luego, desciende por esa pendiente un poco, y se repite una y otra vez, hasta que no se puede seguir bajando.
En R, podemos hacer eso con optim ()
:
- necesitamos pasarle un vector de puntos iniciales. Elegimos el origen por poner cualquier cosa
- le pasamos nuestra función de distancia, y los parámetros que nuestra función necesita (data)
optim(c(4,2), measure_distance, data = sim1)
$par
[1] 4.221029 2.051528
$value
[1] 2.128181
$counts
function gradient
49 NA
$convergence
[1] 0
$message
NULL
best <- optim(c(0, 0), measure_distance, data = sim1)
best$par
[1] 4.222248 2.051204
ggplot(sim1, aes(x, y)) +
geom_point(size = 2, colour = "grey30") +
geom_abline(intercept = best$par[1], slope = best$par[2])
Óptimo para el modelo lineal
Este procedimiento es válido para muchas familias de modelos. Pero para el caso del modelo lineal, conocemos otras formas de resolverlo
Si nuestro modelo es
\[
y = a_1 + a_2x + \epsilon
\]
La solución del óptima es
\[
\hat{a_1} = \bar{y} - \hat{a_2}\bar{x}
\]
\[
\hat{a_2} = \frac{\sum_i^n (y_i -\bar{y})(x_i -\bar{x})}{\sum_i^n (x_i- \bar{x})}
\]
R tiene una función específica para el modelo lineal lm()
. Cómo esta función sirve tanto para regresiones lineales simples como múltiples, debemos especificar el modelo en las formulas: y ~ x
sim1_mod <- lm(y ~ x, data = sim1)
coef(sim1_mod)
(Intercept) x
4.220822 2.051533
Predicciones
Para visualizar las predicciones de un modelo, comenzamos por generar una cuadrícula de valores espaciados uniformemente que cubre la región donde se encuentran nuestros datos. La forma más fácil de hacerlo es usar modelr :: data_grid ()
. Su primer argumento es un dataframe, y para cada argumento posterior encuentra las variables únicas y luego genera todas las combinaciones:
grid <- sim1 %>%
data_grid(x)
grid
(Cuando tengamos modelos de varias variables, esta función va a ser de mucha utilidad)
A continuación, agregamos predicciones. Usaremos modelr :: add_predictions ()
que toma un dataframe y un modelo. Agrega las predicciones del modelo a una nueva columna en el dataframe:
grid <- grid %>%
add_predictions(sim1_mod)
grid
(También podríamos agregar predicciones al dataset original)
A continuación, trazamos las predicciones. La ventaja de este enfoque respecto de geom_abline ()
es que funcionará con cualquier modelo en R, desde el más simple hasta el más complejo.
ggplot(sim1, aes(x)) +
geom_point(aes(y = y)) +
geom_line(aes(y = pred), data = grid, colour = "red", size = 1)
Residuos del modelo
Agregamos residuos al DF con add_residuals ()
, que funciona de forma muy similar a add_predictions ()
. Sin embargo, tengan en cuenta que usamos el conjunto de datos original, no una cuadrícula fabricada. Esto se debe a que para calcular los residuos necesitamos valores y reales.
sim1 <- sim1 %>%
add_residuals(sim1_mod)
sim1
Hay varias formas diferentes de entender lo que nos dicen los residuos sobre el modelo. Una forma es simplemente dibujar un polígono de frecuencia que nos ayude a entender la dispersión de los residuos:
ggplot(sim1, aes(resid)) +
geom_freqpoly(binwidth = 0.5)
Noten que en promedio los residuos deben ser un valor muy cercano a 0
mean(sim1$resid)
[1] 5.121872e-15
Otra forma de graficar los residuos s
ggplot(sim1, aes(x, resid)) +
geom_ref_line(h = 0, size = 2,colour = "firebrick") +
geom_point()
Si los residuos no tienen estructura es que hicimos las cosas bien.
LS0tCnRpdGxlOiAiTW9kZWxvIExpbmVhbCBzaW1wbGVeW0VzdGFzIG5vdGFzIGVzdGFuIGJhc2FkYXMgZW4gSGFkbGV5IFdpY2toYW0gYW5kIEdhcnJldHQgR3JvbGVtdW5kLiAyMDE3LiBSIGZvciBEYXRhIFNjaWVuY2UgSW1wb3J0LCBUaWR5LCBUcmFuc2Zvcm0sIFZpc3VhbGl6ZSwgYW5kIE1vZGVsIERhdGEgKDFzdCBlZC4pLiBPJ1JlaWxseSBNZWRpYSwgSW5jLiAgaHR0cDovL3I0ZHMuaGFkLmNvLm56Ll0iCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdGhlbWU6IHNwYWNlbGFiCiAgICB0b2M6IHllcwogICAgdG9jX2Zsb2F0OiB5ZXMKICAgIGRmX3ByaW50OiBwYWdlZAotLS0KCiMgTW9kZWxvIELDoXNpY28tIENsYXNlIDEKCgpgYGB7ciBzZXR1cCwgbWVzc2FnZSA9IEZBTFNFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKCmxpYnJhcnkobW9kZWxyKQpvcHRpb25zKG5hLmFjdGlvbiA9IG5hLndhcm4pCmBgYAoKIyMgZGF0b3Mgc2ltMQoKRWwgcGFxdWV0ZSBtb2RsciB2aWVuZSBjb24gdW4gc2V0IGRlIGRhdG9zIGRlIGp1Z3VldGUgbGxhbWFkbyBzaW0xCgpgYGB7cn0KZ2dwbG90KHNpbTEsIGFlcyh4LCB5KSkgKyAKICBnZW9tX3BvaW50KCkKYGBgCgpTZSBwdWVkZSB2ZXIgdW4gcGF0csOzbiBmdWVydGUgZW4gbG9zIGRhdG9zLiBQYXJlY2llcmEgcXVlIGVsIG1vZGVsbyBsaW5lYWwgYHkgPSBhXzAgKyBhXzEgKiB4YCBwb2Ryw61hIHNlcnZpci4gCgojIyBNb2RlbG9zIGFsIGF6YXIKClBhcmEgZW1wZXphciwgZ2VuZXJlbW9zIGFsZWF0b3JpYW1lbnRlIHZhcmlvcyBtb2RlbG9zIGxpbmVhbGVzIHBhcmEgdmVyIHF1w6kgcGludGEgdGllbmVuLiBQYXJhIGVzbywgcG9kZW1vcyB1c2FyIGBnZW9tX2FibGluZSAoKWAgcXVlIHRvbWEgdW5hIHBlbmRpZW50ZSBlIGludGVyY2VwdG8gY29tbyBwYXLDoW1ldHJvcy4gCgpgYGB7cn0KbW9kZWxzIDwtIHRpYmJsZSgKICBhMSA9IHJ1bmlmKDI1MCwgLTIwLCA0MCksCiAgYTIgPSBydW5pZigyNTAsIC01LCA1KQopCgpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fYWJsaW5lKGFlcyhpbnRlcmNlcHQgPSBhMSwgc2xvcGUgPSBhMiksIGRhdGEgPSBtb2RlbHMsIGFscGhhID0gMS80KSArCiAgZ2VvbV9wb2ludCgpIApgYGAKCgpBIHNpbXBsZSB2aXN0YSBwb2RlbW9zIGFwcmVjaWFyIHF1ZSBhbGd1bm9zIG1vZGVsb3Mgc29uIG1lam9yZXMgcXVlIG90cm9zLiBQZXJvIG5lY2VzaXRhbW9zIHVuYSBmb3JtYSBkZSBjdWFudGlmaWNhciBjdWFsZXMgc29uIGxvcyBfbWVqb3Jlc18gbW9kZWxvcy4gCgojIyBkaXN0YW5jaWFzCgpVbmEgZm9ybWEgZGUgZGVmaW5pciBfbWVqb3JfIGVzIHBlbnNhciBlbiBhcXVlbCBtb2RlbG8gcXVlIG1pbmltaXphIGxhIGRpc3RhbmNpYSB2ZXJ0aWNhbCBjb24gY2FkYSBwdW50bzoKClBhcmEgZXNvLCBlbGlnYW1vcyB1biBtb2RlbG8gY3VhbHF1aWVyYToKCiQkIHk9IDcgKyAxLjUqeCQkCgoocGFyYSBxdWUgc2UgdmVhbiBtZWpvciBsYXMgZGlzdGFuY2lhcywgY29ycmVtb3MgdW4gcG9xdWl0byBjYWRhIHB1bnRvIHNvYnJlIGVsIGVqZSB4KQoKYGBge3J9CmRpc3QxIDwtIHNpbTEgJT4lIAogIG11dGF0ZSgKICAgIGRvZGdlID0gcmVwKGMoLTEsIDAsIDEpIC8gMjAsIDEwKSwKICAgIHgxID0geCArIGRvZGdlLAogICAgcHJlZCA9IDcgKyB4MSAqIDEuNQogICkKCmdncGxvdChkaXN0MSwgYWVzKHgxLCB5KSkgKyAKICBnZW9tX2FibGluZShpbnRlcmNlcHQgPSA3LCBzbG9wZSA9IDEuNSwgY29sb3VyID0gImdyZXk0MCIpICsKICBnZW9tX3BvaW50KGNvbG91ciA9ICJncmV5NDAiKSArCiAgZ2VvbV9saW5lcmFuZ2UoYWVzKHltaW4gPSB5LCB5bWF4ID0gcHJlZCksIGNvbG91ciA9ICIjMzM2NkZGIikgCmBgYAoKCkxhIGRpc3RhbmNpYSBkZSBjYWRhIHB1bnRvIGEgbGEgcmVjdGEgZXMgbGEgZGlmZXJlbmNpYSBlbnRyZSBsbyBxdWUgcHJlZGljZSBudWVzdHJvIG1vZGVsbyB5IGVsIHZhbG9yIHJlYWwKCgpQYXJhIGNvbXB1dGFyIGxhIGRpc3RhbmNpYSwgcHJpbWVybyBuZWNlc2l0YW1vcyB1bmEgZnVuY2nDs24gcXVlIHJlcHJlc2VudGUgYSBudWVzdHJvIG1vZGVsbzogCgojIyBFamVyY2ljaW8gMQoKICBDcmVhciB1bmEgZnVuY2nDs24gcXVlIHJlY2liYSB1biB2ZWN0b3IgY29uIGxvcyBwYXJhbWV0cm9zIGRlbCBtb2RlbG8sIHkgZWwgc2V0IGRlIGRhdG9zLCB5IGdlbmVyZSBsYSBwcmVkaWNjacOzbjoKICAKYGBge3J9Cm1vZGVsMSA8LSBmdW5jdGlvbihhLCBkYXRhKSB7CiAgYVsxXSArIGRhdGEkeCAqIGFbMl0KfQoKbW9kZWwxKGMoNywgMS41KSwgc2ltMSkKYGBgCgoKCkFob3JhLCBuZWNlc2l0YW1vcyB1bmEgZm9ybWEgZGUgY2FsY3VsYXIgbG9zIHJlc2lkdW9zIHkgYWdydXBhcmxvcy4gQ29tbyBzZSB2acOzIGVuIGxhIGNsYXNlIHRlw7NyaWNhLCBlc3RvIGxvIHZhbW9zIGEgaGFjZXIgY29uIGVsIGVycm9yIGN1YWRyw6F0aWNvIG1lZGlvCgojIyBFamVyY2ljaW8gMgoKTmVjZXNpdGFtb3MgdW5hIGZ1bmNpw7NuLCBjb24gZWwgbWlzbW8gaW5wdXQgcXVlIGxhIGFudGVyaW9yLCBxdWUgY2FsY3VsZSBlbCBwcm9tZWRpbyBkZSBsb3MgZXJyb3JlcyBjdWFkcsOhdGljb3MgKEVDTSkKIAokJEVDTSA9IFxzcXJ0XGZyYWN7XHN1bV9pXm57KFxoYXR7eV9pfSAtIHlfaSleMn19e259JCQKCmBgYHtyfQptZWFzdXJlX2Rpc3RhbmNlIDwtIGZ1bmN0aW9uKG1vZCwgZGF0YSkgewogIGRpZmYgPC0gZGF0YSR5IC0gbW9kZWwxKG1vZCwgZGF0YSkKICBzcXJ0KG1lYW4oZGlmZiBeIDIpKQp9CgptZWFzdXJlX2Rpc3RhbmNlKGMoNywgMS41KSwgc2ltMSkKYGBgCgoKCiMjIEV2YWx1YW5kbyBsb3MgbW9kZWxvcyBhbGVhdG9yaW9zCgpBaG9yYSBwb2RlbW9zIGNhbGN1bGFyIGVsIF9fRUNNX18gcGFyYSB0b2RvcyBsb3MgbW9kZWxvcyBkZWwgZGF0YWZyYW1lIF9tb2RlbHNfLiBQYXJhIGVzbyB1dGlsaXphbW9zIGVsIHBhcXVldGUgX19wdXJycl9fLCBwYXJhIGVqZWN1dGFyIHZhcmlhcyB2ZWNlcyBsYSBtaXNtYSBmdW5jacOzbiBzb2JyZSB2YXJpb3MgZWxlbWVudG9zLiAKCgojIyMgTUFQXltiYXNhZG8gZW4gaHR0cHM6Ly9qZW5ueWJjLmdpdGh1Yi5pby9wdXJyci10dXRvcmlhbC9sczAzX21hcC1mdW5jdGlvbi1zeW50YXguaHRtbCwgZ3JhY2lhcyBKZW5ueSFdCgpMYSBmdW5jacOzbiBfX21hcF9fIHRvbWEgdW4gaW5wdXQsIHVuYSBmdW5jacOzbiBwYXJhIGFwbGljYXIsIHkgYWxndW5hIG90cmEgY29zYSAocG9yIGVqZW1wbG8gcGFyYW1ldHJvcyBxdWUgbmVjZXNpdGUgbGEgZnVuY2nDs24pCgotIG1hcCgueCwgLmYsIC4uLikKLSBtYXAoVkVDVE9SX09SX0xJU1RfSU5QVVQsIEZVTkNUSU9OX1RPX0FQUExZLCBPUFRJT05BTF9PVEhFUl9TVFVGRikKCgpVc2Ftb3MgX19tYXAyX18gY3VhbmRvIHRlbmVtb3MgcXVlIHBhc2FyIGRvcyBpbnB1dCwgcXVlIHNlIGFwbGljYW4gc29icmUgdW5hIGZ1bmNpw7NuOgoKLSBtYXAyKC54LCAueSwgLmYsIC4uLikKLSBtYXAyKElOUFVUX09ORSwgSU5QVVRfVFdPLCBGVU5DVElPTl9UT19BUFBMWSwgT1BUSU9OQUxfT1RIRVJfU1RVRkYpCgpTaSB0ZW5lbW9zIG3DoXMgZGUgZG9zLi4uCgotIHBtYXAoLmwsIC5mLCAuLi4pCi0gcG1hcChMSVNUX09GX0lOUFVUX0xJU1RTLCBGVU5DVElPTl9UT19BUFBMWSwgT1BUSU9OQUxfT1RIRVJfU1RVRkYpCgoKTm9zb3Ryb3MgdGVuZW1vcyBxdWUgcGFzYXIgcGFzYXIgbG9zIHZhbG9yZXMgZGUgYTEgeSBhMiAoZG9zIHBhcsOhbWV0cm9zIC0tPiBtYXAyKSwgcGVybyBjb21vIG51ZXN0cmEgZnVuY2nDs24gdG9tYSBzw7NsbyB1bm8gKGVsIHZlY3RvciBhKSwgbm9zIGFybWFtb3MgdW5hIGZ1bmNpw7NuIGRlIGF5dWRhIHBhcmEgd3JhcGVhciBhMSB5IGEyCgoKCmBgYHtyfQpzaW0xX2Rpc3QgPC0gZnVuY3Rpb24oYTEsIGEyKSB7CiAgbWVhc3VyZV9kaXN0YW5jZShjKGExLCBhMiksIHNpbTEpCn0KCm1vZGVscyA8LSBtb2RlbHMgJT4lIAogIG11dGF0ZShkaXN0ID0gcHVycnI6Om1hcDJfZGJsKGExLCBhMiwgc2ltMV9kaXN0KSkKbW9kZWxzCmBgYAoKCkEgY29udGludWFjacOzbiwgc3VwZXJwb25nYW1vcyBsb3MgMTAgbWVqb3JlcyBtb2RlbG9zIGEgbG9zIGRhdG9zLiBDb2xvcmVhbW9zIGxvcyBtb2RlbG9zIHBvciBgLWRpc3RgOiBlc3RhIGVzIHVuYSBtYW5lcmEgZsOhY2lsIGRlIGFzZWd1cmFyc2UgZGUgcXVlIGxvcyBtZWpvcmVzIG1vZGVsb3MgKGVzIGRlY2lyLCBsb3MgcXVlIHRpZW5lbiBsYSBtZW5vciBkaXN0YW5jaWEpIG9idGVuZ2FuIGxvcyBjb2xvcmVzIG3DoXMgYnJpbGxhbnRlcy4KCgpgYGB7cn0KZ2dwbG90KHNpbTEsIGFlcyh4LCB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAyLCBjb2xvdXIgPSAiZ3JleTMwIikgKyAKICBnZW9tX2FibGluZSgKICAgIGFlcyhpbnRlcmNlcHQgPSBhMSwgc2xvcGUgPSBhMiwgY29sb3VyID0gLWRpc3QpLCAKICAgIGRhdGEgPSBmaWx0ZXIobW9kZWxzLCByYW5rKGRpc3QpIDw9IDEwKQogICkKYGBgCgoKVGFtYmnDqW4gcG9kZW1vcyBwZW5zYXIgZW4gZXN0b3MgbW9kZWxvcyBjb21vIG9ic2VydmFjaW9uZXMgeSB2aXN1YWxpemFyIGNvbiB1biBncsOhZmljbyBkZSBkaXNwZXJzacOzbiBkZSBgYTFgIHZzYCBhMmAsIG51ZXZhbWVudGUgY29sb3JlYWRvIHBvciBgLWRpc3RgLiBZYSBubyBwb2RlbW9zIHZlciBkaXJlY3RhbWVudGUgY8OzbW8gc2UgY29tcGFyYSBlbCBtb2RlbG8gY29uIGxvcyBkYXRvcywgcGVybyBwb2RlbW9zIHZlciBtdWNob3MgbW9kZWxvcyBhIGxhIHZlei4gTnVldmFtZW50ZSwgZGVzdGFxdcOpIGxvcyAxMCBtZWpvcmVzIG1vZGVsb3MsIGVzdGEgdmV6IGRpYnVqYW5kbyBjw61yY3Vsb3Mgcm9qb3MgZGViYWpvIGRlIGVsbG9zLgoKYGBge3J9CmdncGxvdChtb2RlbHMsIGFlcyhhMSwgYTIpKSArCiAgZ2VvbV9wb2ludChkYXRhID0gZmlsdGVyKG1vZGVscywgcmFuayhkaXN0KSA8PSAxMCksIHNpemUgPSA0LCBjb2xvdXIgPSAicmVkIikgKwogIGdlb21fcG9pbnQoYWVzKGNvbG91ciA9IC1kaXN0KSkKYGBgCgojIyBHcmlkIHNlYXJjaAoKRW4gbHVnYXIgZGUgcHJvYmFyIG11Y2hvcyBtb2RlbG9zIGFsZWF0b3Jpb3MsIHBvZHLDrWFtb3Mgc2VyIG3DoXMgc2lzdGVtw6F0aWNvcyB5IGdlbmVyYXIgdW5hIGN1YWRyw61jdWxhIGRlIHB1bnRvcyB1bmlmb3JtZW1lbnRlIGVzcGFjaWFkYSAoZXN0byBzZSBkZW5vbWluYSBncmlkIHNlYXJjaCkuIEVsZWdpbW9zIGxvcyBwYXLDoW1ldHJvcyBkZSBsYSBncmlsbGEgYXByb3hpbWFkYW1lbnRlIG1pcmFuZG8gZMOzbmRlIGVzdGFiYW4gbG9zIG1lam9yZXMgbW9kZWxvcyBlbiBlbCBncsOhZmljbyBhbnRlcmlvci4KCgpgYGB7cn0KZ3JpZCA8LSBleHBhbmQuZ3JpZCgKICBhMSA9IHNlcSgtNSwgMjAsIGxlbmd0aCA9IDI1KSwKICBhMiA9IHNlcSgxLCAzLCBsZW5ndGggPSAyNSkKICApICU+JSAKICBtdXRhdGUoZGlzdCA9IHB1cnJyOjptYXAyX2RibChhMSwgYTIsIHNpbTFfZGlzdCkpCgpncmlkICU+JSAKICBnZ3Bsb3QoYWVzKGExLCBhMikpICsKICBnZW9tX3BvaW50KGRhdGEgPSBmaWx0ZXIoZ3JpZCwgcmFuayhkaXN0KSA8PSAxMCksIHNpemUgPSA0LCBjb2xvdXIgPSAicmVkIikgKwogIGdlb21fcG9pbnQoYWVzKGNvbG91ciA9IC1kaXN0KSkgCmBgYAoKQ3VhbmRvIHN1cGVycG9uZW1vcyBsb3MgMTAgbWVqb3JlcyBtb2RlbG9zIGVuIGxvcyBkYXRvcyBvcmlnaW5hbGVzLCB0b2RvcyBzZSB2ZW4gYmFzdGFudGUgYmllbjoKCmBgYHtyfQpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9ICJncmV5MzAiKSArIAogIGdlb21fYWJsaW5lKAogICAgYWVzKGludGVyY2VwdCA9IGExLCBzbG9wZSA9IGEyLCBjb2xvdXIgPSAtZGlzdCksIAogICAgZGF0YSA9IGZpbHRlcihncmlkLCByYW5rKGRpc3QpIDw9IDEwKQogICkKYGBgCgoKIyBNb2RlbG8gQsOhc2ljby0gQ2xhc2UgMgoKIyMgw7NwdGltbyBwb3IgbcOpdG9kb3MgbnVtw6lyaWNvcyAKClBvZHLDrWFtb3MgaW1hZ2luYXIgaXRlcmF0aXZhbWVudGUgaGFjaWVuZG8gbGEgY3VhZHLDrWN1bGEgbcOhcyBmaW5hIHkgZmluYSBoYXN0YSBxdWUgbm9zIGNlbnRyYW1vcyBlbiBlbCBtZWpvciBtb2RlbG8uIFBlcm8gaGF5IHVuYSBmb3JtYSBtZWpvciBkZSBhYm9yZGFyIGVzZSBwcm9ibGVtYTogdW5hIGhlcnJhbWllbnRhIGRlIG1pbmltaXphY2nDs24gbnVtw6lyaWNhIGxsYW1hZGEgYsO6c3F1ZWRhIF9fTmV3dG9uLVJhcGhzb25fXy4KCkxhIGludHVpY2nDs24gZGUgTmV3dG9uLVJhcGhzb24gZXMgYmFzdGFudGUgc2ltcGxlOiBTZSBlbGlnZSB1biBwdW50byBkZSBwYXJ0aWRhIHkgc2UgYnVzY2EgbGEgcGVuZGllbnRlIG3DoXMgaW5jbGluYWRhLiBMdWVnbywgZGVzY2llbmRlIHBvciBlc2EgcGVuZGllbnRlIHVuIHBvY28sIHkgc2UgcmVwaXRlIHVuYSB5IG90cmEgdmV6LCBoYXN0YSBxdWUgbm8gc2UgcHVlZGUgc2VndWlyIGJhamFuZG8uIAoKCkVuIFIsIHBvZGVtb3MgaGFjZXIgZXNvIGNvbiBgb3B0aW0gKClgOgoKLSBuZWNlc2l0YW1vcyBwYXNhcmxlIHVuIHZlY3RvciBkZSBwdW50b3MgaW5pY2lhbGVzLiBFbGVnaW1vcyBlbCBvcmlnZW4gcG9yIHBvbmVyIGN1YWxxdWllciBjb3NhCi0gbGUgcGFzYW1vcyBudWVzdHJhIGZ1bmNpw7NuIGRlIGRpc3RhbmNpYSwgeSBsb3MgcGFyw6FtZXRyb3MgcXVlIG51ZXN0cmEgZnVuY2nDs24gbmVjZXNpdGEgKGRhdGEpCgoKYGBge3J9Cm9wdGltKGMoNCwyKSwgbWVhc3VyZV9kaXN0YW5jZSwgZGF0YSA9IHNpbTEpCmBgYAoKYGBge3J9CmJlc3QgPC0gb3B0aW0oYygwLCAwKSwgbWVhc3VyZV9kaXN0YW5jZSwgZGF0YSA9IHNpbTEpCmJlc3QkcGFyCgpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9ICJncmV5MzAiKSArIAogIGdlb21fYWJsaW5lKGludGVyY2VwdCA9IGJlc3QkcGFyWzFdLCBzbG9wZSA9IGJlc3QkcGFyWzJdKQpgYGAKCgojIyDDk3B0aW1vIHBhcmEgZWwgbW9kZWxvIGxpbmVhbAoKRXN0ZSBwcm9jZWRpbWllbnRvIGVzIHbDoWxpZG8gcGFyYSBtdWNoYXMgZmFtaWxpYXMgZGUgbW9kZWxvcy4gUGVybyBwYXJhIGVsIGNhc28gZGVsIG1vZGVsbyBsaW5lYWwsIGNvbm9jZW1vcyBvdHJhcyBmb3JtYXMgZGUgcmVzb2x2ZXJsbwoKClNpIG51ZXN0cm8gbW9kZWxvIGVzCgokJAp5ID0gYV8xICsgYV8yeCArIFxlcHNpbG9uCiQkCgpMYSBzb2x1Y2nDs24gZGVsIMOzcHRpbWEgZXMKCiQkClxoYXR7YV8xfSA9IFxiYXJ7eX0gLSBcaGF0e2FfMn1cYmFye3h9IAokJAoKJCQKXGhhdHthXzJ9ID0gXGZyYWN7XHN1bV9pXm4gKHlfaSAtXGJhcnt5fSkoeF9pIC1cYmFye3h9KX17XHN1bV9pXm4gKHhfaS0gXGJhcnt4fSl9CiQkCgpSIHRpZW5lIHVuYSBmdW5jacOzbiBlc3BlY8OtZmljYSBwYXJhIGVsIG1vZGVsbyBsaW5lYWwgYGxtKClgLiBDw7NtbyBlc3RhIGZ1bmNpw7NuIHNpcnZlIHRhbnRvIHBhcmEgcmVncmVzaW9uZXMgbGluZWFsZXMgc2ltcGxlcyBjb21vIG3Dumx0aXBsZXMsIGRlYmVtb3MgZXNwZWNpZmljYXIgZWwgbW9kZWxvIGVuIGxhcyBfZm9ybXVsYXNfOiBgeSB+IHhgCgoKYGBge3J9CnNpbTFfbW9kIDwtIGxtKHkgfiB4LCBkYXRhID0gc2ltMSkKY29lZihzaW0xX21vZCkKYGBgCgoKCiMjIFByZWRpY2Npb25lcwoKClBhcmEgdmlzdWFsaXphciBsYXMgcHJlZGljY2lvbmVzIGRlIHVuIG1vZGVsbywgY29tZW56YW1vcyBwb3IgZ2VuZXJhciB1bmEgY3VhZHLDrWN1bGEgZGUgdmFsb3JlcyBlc3BhY2lhZG9zIHVuaWZvcm1lbWVudGUgcXVlIGN1YnJlIGxhIHJlZ2nDs24gZG9uZGUgc2UgZW5jdWVudHJhbiBudWVzdHJvcyBkYXRvcy4gTGEgZm9ybWEgbcOhcyBmw6FjaWwgZGUgaGFjZXJsbyBlcyB1c2FyIGBtb2RlbHIgOjogZGF0YV9ncmlkICgpYC4gU3UgcHJpbWVyIGFyZ3VtZW50byBlcyB1biBkYXRhZnJhbWUsIHkgcGFyYSBjYWRhIGFyZ3VtZW50byBwb3N0ZXJpb3IgZW5jdWVudHJhIGxhcyB2YXJpYWJsZXMgw7puaWNhcyB5IGx1ZWdvIGdlbmVyYSB0b2RhcyBsYXMgY29tYmluYWNpb25lczoKCmBgYHtyfQpncmlkIDwtIHNpbTEgJT4lIAogIGRhdGFfZ3JpZCh4KSAKZ3JpZApgYGAKCihDdWFuZG8gdGVuZ2Ftb3MgbW9kZWxvcyBkZSB2YXJpYXMgdmFyaWFibGVzLCBlc3RhIGZ1bmNpw7NuIHZhIGEgc2VyIGRlIG11Y2hhIHV0aWxpZGFkKQoKQSBjb250aW51YWNpw7NuLCBhZ3JlZ2Ftb3MgcHJlZGljY2lvbmVzLiBVc2FyZW1vcyBgbW9kZWxyIDo6IGFkZF9wcmVkaWN0aW9ucyAoKWAgcXVlIHRvbWEgdW4gZGF0YWZyYW1lIHkgdW4gbW9kZWxvLiBBZ3JlZ2EgbGFzIHByZWRpY2Npb25lcyBkZWwgbW9kZWxvIGEgdW5hIG51ZXZhIGNvbHVtbmEgZW4gZWwgZGF0YWZyYW1lOgoKYGBge3J9CmdyaWQgPC0gZ3JpZCAlPiUgCiAgYWRkX3ByZWRpY3Rpb25zKHNpbTFfbW9kKSAKZ3JpZApgYGAKCihUYW1iacOpbiBwb2Ryw61hbW9zIGFncmVnYXIgcHJlZGljY2lvbmVzIGFsIGRhdGFzZXQgb3JpZ2luYWwpCgogQSBjb250aW51YWNpw7NuLCB0cmF6YW1vcyBsYXMgcHJlZGljY2lvbmVzLiBMYSB2ZW50YWphIGRlIGVzdGUgZW5mb3F1ZSByZXNwZWN0byBkZSBgZ2VvbV9hYmxpbmUgKClgIGVzIHF1ZSBmdW5jaW9uYXLDoSBjb24gX19jdWFscXVpZXJfXyBtb2RlbG8gZW4gUiwgZGVzZGUgZWwgbcOhcyBzaW1wbGUgaGFzdGEgZWwgbcOhcyBjb21wbGVqby4KCmBgYHtyfQpnZ3Bsb3Qoc2ltMSwgYWVzKHgpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHkpKSArCiAgZ2VvbV9saW5lKGFlcyh5ID0gcHJlZCksIGRhdGEgPSBncmlkLCBjb2xvdXIgPSAicmVkIiwgc2l6ZSA9IDEpCmBgYAoKIyMgUmVzaWR1b3MgZGVsIG1vZGVsbwoKQWdyZWdhbW9zIHJlc2lkdW9zIGFsIERGIGNvbiBgYWRkX3Jlc2lkdWFscyAoKWAsIHF1ZSBmdW5jaW9uYSBkZSBmb3JtYSBtdXkgc2ltaWxhciBhIGBhZGRfcHJlZGljdGlvbnMgKClgLiBTaW4gZW1iYXJnbywgdGVuZ2FuIGVuIGN1ZW50YSBxdWUgdXNhbW9zIGVsIGNvbmp1bnRvIGRlIGRhdG9zIG9yaWdpbmFsLCBubyB1bmEgY3VhZHLDrWN1bGEgZmFicmljYWRhLiBFc3RvIHNlIGRlYmUgYSBxdWUgcGFyYSBjYWxjdWxhciBsb3MgcmVzaWR1b3MgbmVjZXNpdGFtb3MgdmFsb3JlcyB5IHJlYWxlcy4KCgpgYGB7cn0Kc2ltMSA8LSBzaW0xICU+JSAKICBhZGRfcmVzaWR1YWxzKHNpbTFfbW9kKQpzaW0xCmBgYAoKSGF5IHZhcmlhcyBmb3JtYXMgZGlmZXJlbnRlcyBkZSBlbnRlbmRlciBsbyBxdWUgbm9zIGRpY2VuIGxvcyByZXNpZHVvcyBzb2JyZSBlbCBtb2RlbG8uIFVuYSBmb3JtYSBlcyBzaW1wbGVtZW50ZSBkaWJ1amFyIHVuIHBvbMOtZ29ubyBkZSBmcmVjdWVuY2lhIHF1ZSBub3MgYXl1ZGUgYSBlbnRlbmRlciBsYSBkaXNwZXJzacOzbiBkZSBsb3MgcmVzaWR1b3M6CgpgYGB7cn0KZ2dwbG90KHNpbTEsIGFlcyhyZXNpZCkpICsgCiAgZ2VvbV9mcmVxcG9seShiaW53aWR0aCA9IDAuNSkKYGBgCgpOb3RlbiBxdWUgZW4gcHJvbWVkaW8gbG9zIHJlc2lkdW9zIGRlYmVuIHNlciB1biB2YWxvciBtdXkgY2VyY2FubyBhIDAKCmBgYHtyfQptZWFuKHNpbTEkcmVzaWQpCmBgYAoKT3RyYSBmb3JtYSBkZSBncmFmaWNhciBsb3MgcmVzaWR1b3MgcwoKYGBge3J9CmdncGxvdChzaW0xLCBhZXMoeCwgcmVzaWQpKSArIAogIGdlb21fcmVmX2xpbmUoaCA9IDAsIHNpemUgPSAyLGNvbG91ciA9ICJmaXJlYnJpY2siKSArCiAgZ2VvbV9wb2ludCgpIApgYGAKClNpIGxvcyByZXNpZHVvcyBfX25vIHRpZW5lbiBlc3RydWN0dXJhX18gZXMgcXVlIGhpY2ltb3MgbGFzIGNvc2FzIGJpZW4u