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