5.3 Lab: Cross-Validation and the Bootstrap (RESAMPLING)

5.3.1 The Validation Set Aproach

Utilizamos el dataset de Auto. Tambien la libreria ISLR.

setwd("~/CICLO 6/FIABILIDAD")
getwd()
[1] "C:/Users/Ericka/Documents/CICLO 6/FIABILIDAD"
library(dplyr)
library(ggplot2)
library(ISLR)
Auto <- read.csv(file = "auto.csv")
names(Auto)
[1] "mpg"          "cylinders"    "displacement" "horsepower"   "weight"       "acceleration" "year"        
[8] "origin"       "name"        
dim(Auto)
[1] 397   9
Auto$horsepower <- as.numeric(Auto$horsepower)
print(Auto)

Realizamos un split seleccionando 196 observaciones en forma aleatoria de las 397.

set.seed (1) ## Generando un numero aleatorio
train=sample(397, 196)
length(train)
[1] 196

Realizamos una regresion linear lm utilizando la informacion de train

lm.fit =lm(mpg~horsepower, data=Auto, subset= train )
summary(lm.fit)

Call:
lm(formula = mpg ~ horsepower, data = Auto, subset = train)

Residuals:
     Min       1Q   Median       3Q      Max 
-13.4692  -5.3321  -0.4667   4.8524  21.7856 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) 17.89059    1.00936  17.725  < 2e-16 ***
horsepower   0.11167    0.01709   6.535 5.48e-10 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 7.172 on 194 degrees of freedom
Multiple R-squared:  0.1804,    Adjusted R-squared:  0.1762 
F-statistic:  42.7 on 1 and 194 DF,  p-value: 5.479e-10

Utilizamos la funcion predict para estimar la respuesta de los 397 observaciones, y utilizamos mean para calcular la media o MSE de los 196

#attach(Auto)
mean((mpg-predict(lm.fit, Auto))[-train ]^2) # -train seleciona los que nos estan en el training set
[1] 49.47809

Por lo tanto el estimado de la media en test es MSE = 49.47809

Utilizando la funcion poly para estimar el error en el test para las regresiones polinomiales y cubicas

lm.fit2=lm(mpg~poly(horsepower,2) ,data=Auto ,subset =train ) ## Regresion polinomial
mean((mpg-predict(lm.fit2,Auto))[-train ]^2)
[1] 49.28182
lm.fit3=lm(mpg~poly(horsepower,3) ,data=Auto ,subset =train ) ## Regresion cubica
mean((mpg-predict(lm.fit3 ,Auto))[-train ]^2)
[1] 31.69728

Los errores son de 49.28 y 31.69, asi que es mejor utilizar otro train

Calculamos de nuevo las regresiones polinomiales y cubicas para ver si mejora el error

set.seed (2)
train=sample(397,196)
lm.fit=lm(mpg~horsepower,subset=train) ## Lineal
mean((mpg-predict (lm.fit,Auto))[-train]^2)
[1] 44.79806
lm.fit2=lm(mpg~poly(horsepower,2),data=Auto ,subset =train ) ## Polinomial
mean((mpg-predict (lm.fit2 ,Auto))[-train]^2)
[1] 44.51045
lm.fit3=lm(mpg~poly(horsepower,3),data=Auto ,subset =train ) ## Cubica
mean((mpg-predict (lm.fit3 ,Auto))[-train]^2)
[1] 30.70154

Y si vemos que mejora un poco pero no significativamente, y si son consistentes a los calculos anteriores

5.3.2 Leave-One-Out Cross-Validation

Abreviado como estimacion de LOOCV, se puede calcular utilizando la funcion glm, este puede realizar la regresion lineal sin incluir la familia family=“binomial”, y al relizarlo nos da como resultado lo que nos da el lm

glm.fit=glm(mpg~horsepower, data=Auto)
coef(glm.fit)
(Intercept)  horsepower 
 17.8076120   0.1108047 
lm.fit=lm(mpg~horsepower,data=Auto)
coef(lm.fit)
(Intercept)  horsepower 
 17.8076120   0.1108047 

Podemos ver que son los mismos resultados

En este laboratorio utilizamos glm, y con ello la funcion cv.glm(), con la libreria boot, cv es cross-validation

library(boot)
glm.fit=glm(mpg~horsepower,data=Auto)
cv.err=cv.glm(Auto,glm.fit)
cv.err$delta
[1] 50.59100 50.59047

La funcion cv.glm() produce varios componentes, y los dos calores en el delta son los resultados de cross-validation

En este caso son iguales y corresponden a LOOCV, nuestro estimado de cv es 50.59100

Podemos realizar los calculos de nuevo corriendo un for de 1 a 5 con el fin de buscar una mejora en la regresion polinomial

cv.error=rep (0,5)
for (i in 1:5){
  glm.fit=glm(mpg~poly(horsepower,i),data=Auto)
  cv.error[i]=cv.glm (Auto,glm.fit)$delta[1] }
cv.error
[1] 50.59100 50.65400 32.51864 32.72261 27.32256

5.3.3 k-Fold Cross-Validation

La funcion cv.glm tambien nos ayuda a implementar k-Fold Cross-Validation

En este ejemplo realizamos la busqueda de 1 a 10 iteracciones para regresiones polinomiales

set.seed (17)
cv.error.10= rep(0 ,10)
for (i in 1:10) {
glm.fit=glm(mpg~poly(horsepower,i),data=Auto)
cv.error.10[i]=cv.glm (Auto,glm.fit,K=10)$delta [1] }
cv.error.10
 [1] 50.37182 50.65488 32.46844 32.49507 27.20315 27.43767 24.16583 24.35135 23.54375 23.80250

Como principio el tiempo de computo de LOOCV para modelos cuadraticos debe ser mas rapido que k-fold CV

5.3.4 The Bootstrap

Aplicable a casi todas las situaciones, no es complicado y tiene solo dos pasos

1: creamos la funcion que deseamos utilizadar en la estadisticas, 2: utilizamos la funcion boot que esta en la libreria boot

Utilizando el dataset de Portfolio en ISLR

library(ISLR)
dim(Portfolio)
[1] 100   2

Paso 1: creamos la funcion alpha.fn - el cual ingresa la data x, y, asi como el vector de las observaciones para estimar el ??

alpha.fn=function(data ,index){
X=data$X [index]
Y=data$Y [index]
return((var(Y)-cov(X,Y))/(var(X)+var(Y)-2*cov(X,Y)))}

Entonces alfa, colocamos la data, y el indice de 1 a 100 obsevaciones

alpha.fn(Portfolio,1:100)
[1] 0.5758321

Alfa de Portfolio de las cien observaciones es 0.5758

Utilizamos aqui la funcion sample para seleccionar un grupo de observaciones aleatoreamente de 1 a 100, y se reemplazan. Con la finalidad de reconstruir un nuevo bootstrap dataset y recalcular el alfa

set.seed (1)
alpha.fn(Portfolio,sample(100,100,replace=T))
[1] 0.5963833

El nuevo alfa el 0.5963

Utilizando la funcion boot - Realizamos un bootstrap analisis con calculo de alfa por 1000 veces, y computando la desviacion standard.

boot(Portfolio,alpha.fn,R=1000)

ORDINARY NONPARAMETRIC BOOTSTRAP


Call:
boot(data = Portfolio, statistic = alpha.fn, R = 1000)


Bootstrap Statistics :
     original        bias    std. error
t1* 0.5758321 -7.315422e-05  0.08861826

El resultado es que utilizando la data original es decir Portfolio ?? = 0.5758, y la desviacion standard SE(^??) es 0.0886.

Ahora estimamos la exactitud del modelos de la regresion lineal para el dataset de Auto

Utilizando la funcion creada para boot

boot.fn=function(data,index)
return (coef(lm(mpg~horsepower,data=data,subset =index)))
boot.fn(Auto,1:397)
(Intercept)  horsepower 
 17.8076120   0.1108047 

Creando bootstraps para auto

set.seed(1)
boot.fn(Auto,sample(397,397, replace =T))
(Intercept)  horsepower 
 17.4674883   0.1125574 
boot.fn(Auto,sample(397,397, replace =T))
(Intercept)  horsepower 
 16.7417737   0.1315611 

E igual como hicimos para portfolio aqui realizamos un boot para Auto con 1000 corridas de desviacion standards

boot(Auto,boot.fn,1000)

ORDINARY NONPARAMETRIC BOOTSTRAP


Call:
boot(data = Auto, statistic = boot.fn, R = 1000)


Bootstrap Statistics :
      original       bias    std. error
t1* 17.8076120 0.0011771179 0.581449335
t2*  0.1108047 0.0001112272 0.009547989

Estimade de SE Bo para el boostrap es de 0.58, y el SE B1 es de 0.00954

Igualmente se puede utilizar summary para ver las SE

summary(lm(mpg~horsepower,data=Auto))$coef
              Estimate Std. Error  t value     Pr(>|t|)
(Intercept) 17.8076120  0.7112886 25.03571 1.542017e-83
horsepower   0.1108047  0.0119490  9.27314 1.197223e-18

Pero los resultados dan un poco diferentes al calculo con strapboot

boot.fn=function(data,index)
coefficients(lm(mpg~horsepower+I(horsepower^2),data=data, subset=index))
set.seed (1)
boot(Auto,boot.fn,1000)

ORDINARY NONPARAMETRIC BOOTSTRAP


Call:
boot(data = Auto, statistic = boot.fn, R = 1000)


Bootstrap Statistics :
         original        bias     std. error
t1* 16.8389455597 -0.0261845064 0.8982609661
t2*  0.1801991803  0.0013580196 0.0560723042
t3* -0.0007355174 -0.0000106461 0.0005759085
summary(lm(mpg~horsepower+I(horsepower^2),data=Auto))$coef
                     Estimate   Std. Error   t value     Pr(>|t|)
(Intercept)     16.8389455597 0.9890343218 17.025643 4.087631e-49
horsepower       0.1801991803 0.0507204803  3.552789 4.273549e-04
I(horsepower^2) -0.0007355174 0.0005224972 -1.407696 1.600095e-01

Y aqui vemos los resultados iguales del uno al otro

LS0tDQp0aXRsZTogIkxhYm9yYXRvcmlvIDUiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIDUuMyBMYWI6IENyb3NzLVZhbGlkYXRpb24gYW5kIHRoZSBCb290c3RyYXAgKFJFU0FNUExJTkcpDQoNCiMgNS4zLjEgVGhlIFZhbGlkYXRpb24gU2V0IEFwcm9hY2gNCg0KIyMjIFV0aWxpemFtb3MgZWwgZGF0YXNldCBkZSBBdXRvLiAgVGFtYmllbiBsYSBsaWJyZXJpYSBJU0xSLg0KDQpgYGB7cn0NCnNldHdkKCJ+L0NJQ0xPIDYvRklBQklMSURBRCIpDQpnZXR3ZCgpDQpgYGANCg0KYGBge3J9DQpsaWJyYXJ5KGRwbHlyKQ0KbGlicmFyeShnZ3Bsb3QyKQ0KbGlicmFyeShJU0xSKQ0KYGBgDQoNCmBgYHtyfQ0KQXV0byA8LSByZWFkLmNzdihmaWxlID0gImF1dG8uY3N2IikNCm5hbWVzKEF1dG8pDQpkaW0oQXV0bykNCkF1dG8kaG9yc2Vwb3dlciA8LSBhcy5udW1lcmljKEF1dG8kaG9yc2Vwb3dlcikNCnByaW50KEF1dG8pDQpgYGANCg0KIyMjIFJlYWxpemFtb3MgdW4gc3BsaXQgc2VsZWNjaW9uYW5kbyAxOTYgb2JzZXJ2YWNpb25lcyBlbiBmb3JtYSBhbGVhdG9yaWEgZGUgbGFzIDM5Ny4NCmBgYHtyfQ0Kc2V0LnNlZWQgKDEpICMjIEdlbmVyYW5kbyB1biBudW1lcm8gYWxlYXRvcmlvDQp0cmFpbj1zYW1wbGUoMzk3LCAxOTYpDQpsZW5ndGgodHJhaW4pDQpgYGANCg0KIyMjIFJlYWxpemFtb3MgdW5hIHJlZ3Jlc2lvbiBsaW5lYXIgbG0gdXRpbGl6YW5kbyBsYSBpbmZvcm1hY2lvbiBkZSB0cmFpbg0KYGBge3J9DQpsbS5maXQgPWxtKG1wZ35ob3JzZXBvd2VyLCBkYXRhPUF1dG8sIHN1YnNldD0gdHJhaW4gKQ0Kc3VtbWFyeShsbS5maXQpDQpgYGANCg0KIyMjIFV0aWxpemFtb3MgbGEgZnVuY2lvbiBwcmVkaWN0IHBhcmEgZXN0aW1hciBsYSByZXNwdWVzdGEgZGUgbG9zIDM5NyBvYnNlcnZhY2lvbmVzLCB5IHV0aWxpemFtb3MgbWVhbiBwYXJhIGNhbGN1bGFyIGxhIG1lZGlhIG8gTVNFIGRlIGxvcyAxOTYNCmBgYHtyfQ0KI2F0dGFjaChBdXRvKQ0KbWVhbigobXBnLXByZWRpY3QobG0uZml0LCBBdXRvKSlbLXRyYWluIF1eMikgIyAtdHJhaW4gc2VsZWNpb25hIGxvcyBxdWUgbm9zIGVzdGFuIGVuIGVsIHRyYWluaW5nIHNldA0KYGBgDQojIyMgUG9yIGxvIHRhbnRvIGVsIGVzdGltYWRvIGRlIGxhIG1lZGlhIGVuIHRlc3QgZXMgTVNFID0gNDkuNDc4MDkNCg0KIyMjIFV0aWxpemFuZG8gbGEgZnVuY2lvbiBwb2x5IHBhcmEgZXN0aW1hciBlbCBlcnJvciBlbiBlbCB0ZXN0IHBhcmEgbGFzIHJlZ3Jlc2lvbmVzIHBvbGlub21pYWxlcyB5IGN1YmljYXMNCmBgYHtyfQ0KbG0uZml0Mj1sbShtcGd+cG9seShob3JzZXBvd2VyLDIpICxkYXRhPUF1dG8gLHN1YnNldCA9dHJhaW4gKSAjIyBSZWdyZXNpb24gcG9saW5vbWlhbA0KbWVhbigobXBnLXByZWRpY3QobG0uZml0MixBdXRvKSlbLXRyYWluIF1eMikNCg0KbG0uZml0Mz1sbShtcGd+cG9seShob3JzZXBvd2VyLDMpICxkYXRhPUF1dG8gLHN1YnNldCA9dHJhaW4gKSAjIyBSZWdyZXNpb24gY3ViaWNhDQptZWFuKChtcGctcHJlZGljdChsbS5maXQzICxBdXRvKSlbLXRyYWluIF1eMikNCmBgYA0KIyMjIExvcyBlcnJvcmVzIHNvbiBkZSA0OS4yOCB5IDMxLjY5LCBhc2kgcXVlIGVzIG1lam9yIHV0aWxpemFyIG90cm8gdHJhaW4NCiMjIyBDYWxjdWxhbW9zIGRlIG51ZXZvIGxhcyByZWdyZXNpb25lcyBwb2xpbm9taWFsZXMgeSBjdWJpY2FzIHBhcmEgdmVyIHNpIG1lam9yYSBlbCBlcnJvcg0KYGBge3J9DQpzZXQuc2VlZCAoMikNCnRyYWluPXNhbXBsZSgzOTcsMTk2KQ0KbG0uZml0PWxtKG1wZ35ob3JzZXBvd2VyLHN1YnNldD10cmFpbikgIyMgTGluZWFsDQptZWFuKChtcGctcHJlZGljdCAobG0uZml0LEF1dG8pKVstdHJhaW5dXjIpDQoNCmxtLmZpdDI9bG0obXBnfnBvbHkoaG9yc2Vwb3dlciwyKSxkYXRhPUF1dG8gLHN1YnNldCA9dHJhaW4gKSAjIyBQb2xpbm9taWFsDQptZWFuKChtcGctcHJlZGljdCAobG0uZml0MiAsQXV0bykpWy10cmFpbl1eMikNCg0KbG0uZml0Mz1sbShtcGd+cG9seShob3JzZXBvd2VyLDMpLGRhdGE9QXV0byAsc3Vic2V0ID10cmFpbiApICMjIEN1YmljYQ0KbWVhbigobXBnLXByZWRpY3QgKGxtLmZpdDMgLEF1dG8pKVstdHJhaW5dXjIpDQoNCmBgYA0KIyMjIFkgc2kgdmVtb3MgcXVlIG1lam9yYSB1biBwb2NvIHBlcm8gbm8gc2lnbmlmaWNhdGl2YW1lbnRlLCB5IHNpIHNvbiBjb25zaXN0ZW50ZXMgYSBsb3MgY2FsY3Vsb3MgYW50ZXJpb3Jlcw0KDQojIDUuMy4yIExlYXZlLU9uZS1PdXQgQ3Jvc3MtVmFsaWRhdGlvbg0KIyMjIEFicmV2aWFkbyBjb21vIGVzdGltYWNpb24gZGUgTE9PQ1YsIHNlIHB1ZWRlIGNhbGN1bGFyIHV0aWxpemFuZG8gbGEgZnVuY2lvbiBnbG0sIGVzdGUgcHVlZGUgcmVhbGl6YXIgbGEgcmVncmVzaW9uIGxpbmVhbCBzaW4gaW5jbHVpciBsYSBmYW1pbGlhIGZhbWlseT0iYmlub21pYWwiLCB5IGFsIHJlbGl6YXJsbyBub3MgZGEgY29tbyByZXN1bHRhZG8gbG8gcXVlIG5vcyBkYSBlbCBsbQ0KDQpgYGB7cn0NCmdsbS5maXQ9Z2xtKG1wZ35ob3JzZXBvd2VyLCBkYXRhPUF1dG8pDQpjb2VmKGdsbS5maXQpDQpgYGANCg0KYGBge3J9DQpsbS5maXQ9bG0obXBnfmhvcnNlcG93ZXIsZGF0YT1BdXRvKQ0KY29lZihsbS5maXQpDQpgYGANCiMjIyBQb2RlbW9zIHZlciBxdWUgc29uIGxvcyBtaXNtb3MgcmVzdWx0YWRvcw0KDQojIyMgRW4gZXN0ZSBsYWJvcmF0b3JpbyB1dGlsaXphbW9zIGdsbSwgeSBjb24gZWxsbyBsYSBmdW5jaW9uIGN2LmdsbSgpLCBjb24gbGEgbGlicmVyaWEgYm9vdCwgY3YgZXMgY3Jvc3MtdmFsaWRhdGlvbg0KYGBge3J9DQpsaWJyYXJ5KGJvb3QpDQpnbG0uZml0PWdsbShtcGd+aG9yc2Vwb3dlcixkYXRhPUF1dG8pDQpjdi5lcnI9Y3YuZ2xtKEF1dG8sZ2xtLmZpdCkNCmN2LmVyciRkZWx0YQ0KYGBgDQojIyMgTGEgZnVuY2lvbiBjdi5nbG0oKSBwcm9kdWNlIHZhcmlvcyBjb21wb25lbnRlcywgeSBsb3MgZG9zIGNhbG9yZXMgZW4gZWwgZGVsdGEgc29uIGxvcyByZXN1bHRhZG9zIGRlIGNyb3NzLXZhbGlkYXRpb24gDQojIyMgRW4gZXN0ZSBjYXNvIHNvbiBpZ3VhbGVzIHkgY29ycmVzcG9uZGVuIGEgTE9PQ1YsIG51ZXN0cm8gZXN0aW1hZG8gZGUgY3YgZXMgNTAuNTkxMDAgDQoNCiMjIyBQb2RlbW9zIHJlYWxpemFyIGxvcyBjYWxjdWxvcyBkZSBudWV2byBjb3JyaWVuZG8gdW4gZm9yIGRlIDEgYSA1IGNvbiBlbCBmaW4gZGUgYnVzY2FyIHVuYSBtZWpvcmEgZW4gbGEgcmVncmVzaW9uIHBvbGlub21pYWwNCmBgYHtyfQ0KY3YuZXJyb3I9cmVwICgwLDUpDQpmb3IgKGkgaW4gMTo1KXsNCiAgZ2xtLmZpdD1nbG0obXBnfnBvbHkoaG9yc2Vwb3dlcixpKSxkYXRhPUF1dG8pDQogIGN2LmVycm9yW2ldPWN2LmdsbSAoQXV0byxnbG0uZml0KSRkZWx0YVsxXSB9DQpjdi5lcnJvcg0KYGBgDQoNCiMgNS4zLjMgay1Gb2xkIENyb3NzLVZhbGlkYXRpb24NCg0KIyMjIExhIGZ1bmNpb24gY3YuZ2xtIHRhbWJpZW4gbm9zIGF5dWRhIGEgaW1wbGVtZW50YXIgay1Gb2xkIENyb3NzLVZhbGlkYXRpb24NCg0KIyMjIEVuIGVzdGUgZWplbXBsbyByZWFsaXphbW9zIGxhIGJ1c3F1ZWRhIGRlICAxIGEgMTAgaXRlcmFjY2lvbmVzIHBhcmEgcmVncmVzaW9uZXMgcG9saW5vbWlhbGVzDQoNCmBgYHtyfQ0Kc2V0LnNlZWQgKDE3KQ0KY3YuZXJyb3IuMTA9IHJlcCgwICwxMCkNCmZvciAoaSBpbiAxOjEwKSB7DQpnbG0uZml0PWdsbShtcGd+cG9seShob3JzZXBvd2VyLGkpLGRhdGE9QXV0bykNCmN2LmVycm9yLjEwW2ldPWN2LmdsbSAoQXV0byxnbG0uZml0LEs9MTApJGRlbHRhIFsxXSB9DQpjdi5lcnJvci4xMA0KYGBgDQoNCiMjIyBDb21vIHByaW5jaXBpbyBlbCB0aWVtcG8gZGUgY29tcHV0byBkZSBMT09DViBwYXJhIG1vZGVsb3MgY3VhZHJhdGljb3MgZGViZSBzZXIgbWFzIHJhcGlkbyBxdWUgay1mb2xkIENWDQoNCiMgNS4zLjQgVGhlIEJvb3RzdHJhcA0KIyMjIEFwbGljYWJsZSBhIGNhc2kgdG9kYXMgbGFzIHNpdHVhY2lvbmVzLCBubyBlcyBjb21wbGljYWRvIHkgdGllbmUgc29sbyBkb3MgcGFzb3MNCiMjIyAxOiBjcmVhbW9zIGxhIGZ1bmNpb24gcXVlIGRlc2VhbW9zIHV0aWxpemFkYXIgZW4gbGEgZXN0YWRpc3RpY2FzLCAyOiB1dGlsaXphbW9zIGxhIGZ1bmNpb24gYm9vdCBxdWUgZXN0YSBlbiBsYSBsaWJyZXJpYSBib290DQoNCiMjIyBVdGlsaXphbmRvIGVsIGRhdGFzZXQgZGUgUG9ydGZvbGlvIGVuIElTTFINCmBgYHtyfQ0KbGlicmFyeShJU0xSKQ0KZGltKFBvcnRmb2xpbykNCmBgYA0KDQojIyMgUGFzbyAxOiBjcmVhbW9zIGxhIGZ1bmNpb24gYWxwaGEuZm4gLSBlbCBjdWFsIGluZ3Jlc2EgbGEgZGF0YSB4LCB5LCBhc2kgY29tbyBlbCB2ZWN0b3IgZGUgbGFzIG9ic2VydmFjaW9uZXMgcGFyYSBlc3RpbWFyIGVsID8/DQoNCmBgYHtyfQ0KYWxwaGEuZm49ZnVuY3Rpb24oZGF0YSxpbmRleCl7DQpYPWRhdGEkWCBbaW5kZXhdDQpZPWRhdGEkWSBbaW5kZXhdDQpyZXR1cm4oKHZhcihZKS1jb3YoWCxZKSkvKHZhcihYKSt2YXIoWSktMipjb3YoWCxZKSkpfQ0KYGBgDQoNCiMjIyBFbnRvbmNlcyBhbGZhLCBjb2xvY2Ftb3MgbGEgZGF0YSwgeSBlbCBpbmRpY2UgZGUgMSBhIDEwMCBvYnNldmFjaW9uZXMNCmBgYHtyfQ0KYWxwaGEuZm4oUG9ydGZvbGlvLDE6MTAwKQ0KYGBgDQojIyMgQWxmYSBkZSBQb3J0Zm9saW8gZGUgbGFzIGNpZW4gb2JzZXJ2YWNpb25lcyBlcyAwLjU3NTgNCg0KIyMjIFV0aWxpemFtb3MgYXF1aSBsYSBmdW5jaW9uIHNhbXBsZSBwYXJhIHNlbGVjY2lvbmFyIHVuIGdydXBvIGRlIG9ic2VydmFjaW9uZXMgYWxlYXRvcmVhbWVudGUgZGUgMSBhIDEwMCwgeSBzZSByZWVtcGxhemFuLiAgQ29uIGxhIGZpbmFsaWRhZCBkZSByZWNvbnN0cnVpciB1biBudWV2byBib290c3RyYXAgZGF0YXNldCB5IHJlY2FsY3VsYXIgZWwgYWxmYQ0KYGBge3J9DQpzZXQuc2VlZCAoMSkNCmFscGhhLmZuKFBvcnRmb2xpbyxzYW1wbGUoMTAwLDEwMCxyZXBsYWNlPVQpKQ0KYGBgDQojIyMgRWwgbnVldm8gYWxmYSBlbCAwLjU5NjMNCg0KIyMjIFV0aWxpemFuZG8gbGEgZnVuY2lvbiBib290IC0gUmVhbGl6YW1vcyB1biBib290c3RyYXAgYW5hbGlzaXMgY29uIGNhbGN1bG8gZGUgYWxmYSBwb3IgMTAwMCB2ZWNlcywgeSBjb21wdXRhbmRvIGxhIGRlc3ZpYWNpb24gc3RhbmRhcmQuICAgDQoNCmBgYHtyfQ0KYm9vdChQb3J0Zm9saW8sYWxwaGEuZm4sUj0xMDAwKQ0KYGBgDQoNCiMjIyBFbCByZXN1bHRhZG8gZXMgcXVlIHV0aWxpemFuZG8gbGEgZGF0YSBvcmlnaW5hbCBlcyBkZWNpciBQb3J0Zm9saW8gPz8gPSAwLjU3NTgsIHkgbGEgZGVzdmlhY2lvbiBzdGFuZGFyZCBTRShePz8pIGVzIDAuMDg4Ni4NCg0KIyMgQWhvcmEgZXN0aW1hbW9zIGxhIGV4YWN0aXR1ZCBkZWwgbW9kZWxvcyBkZSBsYSByZWdyZXNpb24gbGluZWFsIHBhcmEgZWwgZGF0YXNldCBkZSBBdXRvDQoNCiMjIyBVdGlsaXphbmRvIGxhIGZ1bmNpb24gY3JlYWRhIHBhcmEgYm9vdA0KYGBge3J9DQpib290LmZuPWZ1bmN0aW9uKGRhdGEsaW5kZXgpDQpyZXR1cm4gKGNvZWYobG0obXBnfmhvcnNlcG93ZXIsZGF0YT1kYXRhLHN1YnNldCA9aW5kZXgpKSkNCmJvb3QuZm4oQXV0bywxOjM5NykNCmBgYA0KDQojIyMgQ3JlYW5kbyBib290c3RyYXBzIHBhcmEgYXV0bw0KYGBge3J9DQpzZXQuc2VlZCgxKQ0KYm9vdC5mbihBdXRvLHNhbXBsZSgzOTcsMzk3LCByZXBsYWNlPVQpKQ0KYm9vdC5mbihBdXRvLHNhbXBsZSgzOTcsMzk3LCByZXBsYWNlPVQpKQ0KYGBgDQoNCiMjIyBFIGlndWFsIGNvbW8gaGljaW1vcyBwYXJhIHBvcnRmb2xpbyBhcXVpIHJlYWxpemFtb3MgdW4gYm9vdCBwYXJhIEF1dG8gY29uIDEwMDAgY29ycmlkYXMgZGUgZGVzdmlhY2lvbiBzdGFuZGFyZHMNCmBgYHtyfQ0KYm9vdChBdXRvLGJvb3QuZm4sMTAwMCkNCmBgYA0KDQojIyMgRXN0aW1hZGUgZGUgU0UgQm8gcGFyYSBlbCBib29zdHJhcCBlcyBkZSAwLjU4LCB5IGVsIFNFIEIxIGVzIGRlIDAuMDA5NTQNCg0KIyMjIElndWFsbWVudGUgc2UgcHVlZGUgdXRpbGl6YXIgc3VtbWFyeSBwYXJhIHZlciBsYXMgU0UNCmBgYHtyfQ0Kc3VtbWFyeShsbShtcGd+aG9yc2Vwb3dlcixkYXRhPUF1dG8pKSRjb2VmDQpgYGANCiMjIyBQZXJvIGxvcyByZXN1bHRhZG9zIGRhbiB1biBwb2NvIGRpZmVyZW50ZXMgYWwgY2FsY3VsbyBjb24gc3RyYXBib290DQoNCmBgYHtyfQ0KYm9vdC5mbj1mdW5jdGlvbihkYXRhLGluZGV4KQ0KY29lZmZpY2llbnRzKGxtKG1wZ35ob3JzZXBvd2VyK0koaG9yc2Vwb3dlcl4yKSxkYXRhPWRhdGEsIHN1YnNldD1pbmRleCkpDQpzZXQuc2VlZCAoMSkNCmJvb3QoQXV0byxib290LmZuLDEwMDApDQpgYGANCg0KYGBge3J9DQpzdW1tYXJ5KGxtKG1wZ35ob3JzZXBvd2VyK0koaG9yc2Vwb3dlcl4yKSxkYXRhPUF1dG8pKSRjb2VmDQpgYGANCg0KIyMjIFkgYXF1aSB2ZW1vcyBsb3MgcmVzdWx0YWRvcyBpZ3VhbGVzIGRlbCB1bm8gYWwgb3Rybw0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0K