Introduction to cross-validation for linear regression. See Chapter 11 in Regression and Other Stories.


Load packages

library("rprojroot")
root<-has_file(".ROS-Examples-root")$make_fix_file()
library("rstanarm")
library("loo")
library("ggplot2")
library("bayesplot")
theme_set(bayesplot::theme_default(base_family = "sans", base_size=16))
library("foreign")
# for reproducibility
SEED <- 1507

Simulation data example

Simulate fake data

x <- 1:20
n <- length(x)
a <- 0.2
b <- 0.3
sigma <- 1
# set the random seed to get reproducible results
# change the seed to experiment with variation due to random noise
set.seed(2141) 
y <- a + b*x + sigma*rnorm(n)
fake <- data.frame(x, y)

Fit linear model

fit_all <- stan_glm(y ~ x, data = fake, seed=2141, chains=10, refresh=0)

Fit linear model without 18th observation

fit_minus_18 <- stan_glm(y ~ x, data = fake[-18,], seed=2141, refresh=0)

Extract posterior draws

sims <- as.matrix(fit_all)
sims_minus_18 <- as.matrix(fit_minus_18)

Compute posterior predictive distribution given x=18

condpred<-data.frame(y=seq(0,9,length.out=100))
condpred$x <- sapply(condpred$y, FUN=function(y) mean(dnorm(y, sims[,1] + sims[,2]*18, sims[,3])*6+18))

Compute LOO posterior predictive distribution given x=18

condpredloo<-data.frame(y=seq(0,9,length.out=100))
condpredloo$x <- sapply(condpredloo$y, FUN=function(y) mean(dnorm(y, sims_minus_18[,1] + sims_minus_18[,2]*18, sims_minus_18[,3])*6+18))

Create a plot with posterior mean and posterior predictive distribution

p1 <- ggplot(fake, aes(x = x, y = y)) +
  geom_point(color = "white", size = 3) +
  geom_point(color = "black", size = 2)
p2 <- p1 +
  geom_abline(
    intercept = mean(sims[, 1]),
    slope = mean(sims[, 2]),
    size = 1,
    color = "black"
  )
p3 <- p2 + 
  geom_path(data=condpred,aes(x=x,y=y), color="black") +
  geom_vline(xintercept=18, linetype=3, color="grey")

Add LOO mean and LOO predictive distribution when x=18 is left out

p4 <- p3 +
  geom_point(data=fake[18,], color = "grey50", size = 5, shape=1) +
  geom_abline(
    intercept = mean(sims_minus_18[, 1]),
    slope = mean(sims_minus_18[, 2]),
    size = 1,
    color = "grey50",
    linetype=2
  ) +
  geom_path(data=condpredloo,aes(x=x,y=y), color="grey50", linetype=2)
p4

Compute posterior and LOO residuals

loo_predict() computes mean of LOO predictive distribution.

fake$residual <- fake$y-fit_all$fitted
fake$looresidual <- fake$y-loo_predict(fit_all)$value

Plot posterior and LOO residuals

p1 <- ggplot(fake, aes(x = x, y = residual)) +
  geom_point(color = "black", size = 2, shape=16) +
  geom_point(aes(y=looresidual), color = "grey50", size = 2, shape=1) +
  geom_segment(aes(xend=x, y=residual, yend=looresidual)) +
  geom_hline(yintercept=0, linetype=2)
p1

Standard deviations of posterior and LOO residuals

round(sd(fake$residual),2)
[1] 0.92
round(sd(fake$looresidual),2)
[1] 1.03

Variance of residuals is connected to R^2, which can be defined as 1-var(res)/var(y)

round(1-var(fake$residual)/var(y),2)
[1] 0.74
round(1-var(fake$looresidual)/var(y),2)
[1] 0.68

Compute log posterior predictive densities

log_lik returns \(\log(p(y_i|\theta^{(s)}))\)

ll_1 <- log_lik(fit_all)

compute \(\log(\frac{1}{S}\sum_{s=1}^S p(y_i|\theta^{(s)})\) in computationally stable way

fake$lpd_post <- matrixStats::colLogSumExps(ll_1) - log(nrow(ll_1))

Compute log LOO predictive densities

loo uses fast approximate leave-one-out cross-validation

loo_1 <- loo(fit_all)
fake$lpd_loo <-loo_1$pointwise[,"elpd_loo"]

Plot posterior and LOO log predictive densities

p1 <- ggplot(fake, aes(x = x, y = lpd_post)) +
  geom_point(color = "black", size = 2, shape=16) +
  geom_point(aes(y=lpd_loo), color = "grey50", size = 2, shape=1) +
  geom_segment(aes(xend=x, y=lpd_post, yend=lpd_loo)) +
  ylab("log predictive density")
p1

KidIQ example

Load children's test scores data

kidiq <- read.dta(file=root("KidIQ/data","kidiq.dta"))

Linear regression

fit_3 <- stan_glm(kid_score ~ mom_hs + mom_iq, data=kidiq,
                  seed=SEED, refresh = 0)
print(fit_3)
stan_glm
 family:       gaussian [identity]
 formula:      kid_score ~ mom_hs + mom_iq
 observations: 434
 predictors:   3
------
            Median MAD_SD
(Intercept) 25.8    5.9  
mom_hs       5.9    2.2  
mom_iq       0.6    0.1  

Auxiliary parameter(s):
      Median MAD_SD
sigma 18.2    0.6  

------
* For help interpreting the printed output see ?print.stanreg
* For info on the priors used see ?prior_summary.stanreg

Compute R^2 and LOO-R^2 manually

respost <- kidiq$kid_score-fit_3$fitted
resloo <- kidiq$kid_score-loo_predict(fit_3)$value
round(R2 <- 1 - var(respost)/var(kidiq$kid_score), 2)
[1] 0.21
round(R2loo <- 1 - var(resloo)/var(kidiq$kid_score), 2)
[1] 0.2

Add five pure noise predictors to the data

set.seed(SEED)
n <- nrow(kidiq)
kidiqr <- kidiq
kidiqr$noise <- array(rnorm(5*n), c(n,5))

Linear regression with additional noise predictors

fit_3n <- stan_glm(kid_score ~ mom_hs + mom_iq + noise, data=kidiqr,
                   seed=SEED, refresh = 0)
print(fit_3n)
stan_glm
 family:       gaussian [identity]
 formula:      kid_score ~ mom_hs + mom_iq + noise
 observations: 434
 predictors:   8
------
            Median MAD_SD
(Intercept) 25.4    5.8  
mom_hs       6.0    2.3  
mom_iq       0.6    0.1  
noise1      -0.1    0.9  
noise2      -1.3    0.9  
noise3       0.0    0.9  
noise4       0.2    0.9  
noise5      -0.5    0.9  

Auxiliary parameter(s):
      Median MAD_SD
sigma 18.2    0.6  

------
* For help interpreting the printed output see ?print.stanreg
* For info on the priors used see ?prior_summary.stanreg

Compute R^2 and LOO-R^2 manually

respostn <- kidiq$kid_score-fit_3n$fitted
resloon <- kidiq$kid_score-loo_predict(fit_3n)$value
round(R2n <- 1 - var(respostn)/var(kidiq$kid_score), 2)
[1] 0.22
round(R2loon <- 1 - var(resloon)/var(kidiq$kid_score), 2)
[1] 0.19

Alternative more informative regularized horseshoe prior

fit_3rhs <- stan_glm(kid_score ~ mom_hs + mom_iq, prior=hs(), data=kidiq,
                     seed=SEED, refresh = 0)
fit_3rhsn <- stan_glm(kid_score ~ mom_hs + mom_iq + noise, prior=hs(),
                      data=kidiqr, seed=SEED, refresh = 0)
round(median(bayes_R2(fit_3rhs)), 2)
[1] 0.2
round(median(loo_R2(fit_3rhs)), 2)
[1] 0.2
round(median(bayes_R2(fit_3rhsn)), 2)
[1] 0.2
round(median(loo_R2(fit_3rhsn)), 2)
[1] 0.2

Compute sum of log posterior predictive densities

log_lik returns \(\log(p(y_i|\theta^{(s)}))\)

ll_3 <- log_lik(fit_3)
ll_3n <- log_lik(fit_3n)

compute \(\log(\frac{1}{S}\sum_{s=1}^S p(y_i|\theta^{(s)})\) in computationally stable way

round(sum(matrixStats::colLogSumExps(ll_3) - log(nrow(ll_3))), 1)
[1] -1872
round(sum(matrixStats::colLogSumExps(ll_3n) - log(nrow(ll_3n))), 1)
[1] -1871.1

Compute log LOO predictive densities

loo uses fast approximate leave-one-out cross-validation

loo_3 <- loo(fit_3)
loo_3n <- loo(fit_3n)
round(loo_3$estimate["elpd_loo",1], 1)
[1] -1876.1
round(loo_3n$estimate["elpd_loo",1], 1)
[1] -1879.8

More information on LOO elpd estimate including standard errors

loo_3

Computed from 4000 by 434 log-likelihood matrix

         Estimate   SE
elpd_loo  -1876.1 14.2
p_loo         4.0  0.4
looic      3752.1 28.5
------
Monte Carlo SE of elpd_loo is 0.0.

All Pareto k estimates are good (k < 0.5).
See help('pareto-k-diagnostic') for details.
loo_3n

Computed from 4000 by 434 log-likelihood matrix

         Estimate   SE
elpd_loo  -1879.8 14.2
p_loo         8.7  0.7
looic      3759.6 28.4
------
Monte Carlo SE of elpd_loo is 0.0.

All Pareto k estimates are good (k < 0.5).
See help('pareto-k-diagnostic') for details.

Model using only the maternal high school indicator

fit_1 <- stan_glm(kid_score ~ mom_hs, data=kidiq, refresh = 0)
(loo_1 <- loo(fit_1))

Computed from 4000 by 434 log-likelihood matrix

         Estimate   SE
elpd_loo  -1914.8 13.8
p_loo         3.0  0.3
looic      3829.5 27.6
------
Monte Carlo SE of elpd_loo is 0.0.

All Pareto k estimates are good (k < 0.5).
See help('pareto-k-diagnostic') for details.

Compare models using LOO log score (elpd)

loo_compare(loo_3, loo_1)
      elpd_diff se_diff
fit_3   0.0       0.0  
fit_1 -38.7       8.3  

Compare models using LOO-R^2

# we need to fix the seed to get comparison to work correctly in this case
set.seed(1414)
looR2_1 <- loo_R2(fit_1)
set.seed(1414)
looR2_3 <- loo_R2(fit_3)
round(mean(looR2_1), 2)
[1] 0.05
round(mean(looR2_3), 2)
[1] 0.2
round(mean(looR2_3-looR2_1), 2)
[1] 0.16
round(sd(looR2_3-looR2_1), 2)
[1] 0.04

Model with an interaction

fit_4 <- stan_glm(kid_score ~ mom_hs + mom_iq + mom_hs:mom_iq,
                  data=kidiq, refresh=0)

Compare models using LOO log score (elpd)

loo_4 <- loo(fit_4)
loo_compare(loo_3, loo_4)
      elpd_diff se_diff
fit_4  0.0       0.0   
fit_3 -3.4       2.7   

Compare models using LOO-R^2

set.seed(1414)
looR2_4 <- loo_R2(fit_4)
round(mean(looR2_4), 2)
[1] 0.22
round(mean(looR2_4-looR2_3), 2)
[1] 0.01
round(sd(looR2_4-looR2_3), 2)
[1] 0.05
LS0tCnRpdGxlOiAiUmVncmVzc2lvbiBhbmQgT3RoZXIgU3RvcmllczogQ3Jvc3MtdmFsaWRhdGlvbiIKYXV0aG9yOiAiQW5kcmV3IEdlbG1hbiwgSmVubmlmZXIgSGlsbCwgQWtpIFZlaHRhcmkiCmRhdGU6ICJgciBmb3JtYXQoU3lzLkRhdGUoKSlgIgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDoKICAgIHRoZW1lOiByZWFkYWJsZQogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDIKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgY29kZV9kb3dubG9hZDogdHJ1ZQotLS0KSW50cm9kdWN0aW9uIHRvIGNyb3NzLXZhbGlkYXRpb24gZm9yIGxpbmVhciByZWdyZXNzaW9uLiBTZWUgQ2hhcHRlcgoxMSBpbiBSZWdyZXNzaW9uIGFuZCBPdGhlciBTdG9yaWVzLgoKLS0tLS0tLS0tLS0tLQoKCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQobWVzc2FnZT1GQUxTRSwgZXJyb3I9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIGNvbW1lbnQ9TkEpCiMgc3dpdGNoIHRoaXMgdG8gVFJVRSB0byBzYXZlIGZpZ3VyZXMgaW4gc2VwYXJhdGUgZmlsZXMKc2F2ZWZpZ3MgPC0gRkFMU0UKYGBgCgojIyMjIExvYWQgcGFja2FnZXMKCmBgYHtyIH0KbGlicmFyeSgicnByb2pyb290IikKcm9vdDwtaGFzX2ZpbGUoIi5ST1MtRXhhbXBsZXMtcm9vdCIpJG1ha2VfZml4X2ZpbGUoKQpsaWJyYXJ5KCJyc3RhbmFybSIpCmxpYnJhcnkoImxvbyIpCmxpYnJhcnkoImdncGxvdDIiKQpsaWJyYXJ5KCJiYXllc3Bsb3QiKQp0aGVtZV9zZXQoYmF5ZXNwbG90Ojp0aGVtZV9kZWZhdWx0KGJhc2VfZmFtaWx5ID0gInNhbnMiLCBiYXNlX3NpemU9MTYpKQpsaWJyYXJ5KCJmb3JlaWduIikKIyBmb3IgcmVwcm9kdWNpYmlsaXR5ClNFRUQgPC0gMTUwNwpgYGAKCiMjIFNpbXVsYXRpb24gZGF0YSBleGFtcGxlCiMjIyMgU2ltdWxhdGUgZmFrZSBkYXRhCgpgYGB7ciB9CnggPC0gMToyMApuIDwtIGxlbmd0aCh4KQphIDwtIDAuMgpiIDwtIDAuMwpzaWdtYSA8LSAxCiMgc2V0IHRoZSByYW5kb20gc2VlZCB0byBnZXQgcmVwcm9kdWNpYmxlIHJlc3VsdHMKIyBjaGFuZ2UgdGhlIHNlZWQgdG8gZXhwZXJpbWVudCB3aXRoIHZhcmlhdGlvbiBkdWUgdG8gcmFuZG9tIG5vaXNlCnNldC5zZWVkKDIxNDEpIAp5IDwtIGEgKyBiKnggKyBzaWdtYSpybm9ybShuKQpmYWtlIDwtIGRhdGEuZnJhbWUoeCwgeSkKYGBgCgojIyMjIEZpdCBsaW5lYXIgbW9kZWwKCmBgYHtyIHJlc3VsdHM9J2hpZGUnfQpmaXRfYWxsIDwtIHN0YW5fZ2xtKHkgfiB4LCBkYXRhID0gZmFrZSwgc2VlZD0yMTQxLCBjaGFpbnM9MTAsIHJlZnJlc2g9MCkKYGBgCgojIyMjIEZpdCBsaW5lYXIgbW9kZWwgd2l0aG91dCAxOHRoIG9ic2VydmF0aW9uCgpgYGB7ciB9CmZpdF9taW51c18xOCA8LSBzdGFuX2dsbSh5IH4geCwgZGF0YSA9IGZha2VbLTE4LF0sIHNlZWQ9MjE0MSwgcmVmcmVzaD0wKQpgYGAKCiMjIyMgRXh0cmFjdCBwb3N0ZXJpb3IgZHJhd3MKCmBgYHtyIH0Kc2ltcyA8LSBhcy5tYXRyaXgoZml0X2FsbCkKc2ltc19taW51c18xOCA8LSBhcy5tYXRyaXgoZml0X21pbnVzXzE4KQpgYGAKCiMjIyMgQ29tcHV0ZSBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBkaXN0cmlidXRpb24gZ2l2ZW4geD0xOAoKYGBge3IgfQpjb25kcHJlZDwtZGF0YS5mcmFtZSh5PXNlcSgwLDksbGVuZ3RoLm91dD0xMDApKQpjb25kcHJlZCR4IDwtIHNhcHBseShjb25kcHJlZCR5LCBGVU49ZnVuY3Rpb24oeSkgbWVhbihkbm9ybSh5LCBzaW1zWywxXSArIHNpbXNbLDJdKjE4LCBzaW1zWywzXSkqNisxOCkpCmBgYAoKIyMjIyBDb21wdXRlIExPTyBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBkaXN0cmlidXRpb24gZ2l2ZW4geD0xOAoKYGBge3IgfQpjb25kcHJlZGxvbzwtZGF0YS5mcmFtZSh5PXNlcSgwLDksbGVuZ3RoLm91dD0xMDApKQpjb25kcHJlZGxvbyR4IDwtIHNhcHBseShjb25kcHJlZGxvbyR5LCBGVU49ZnVuY3Rpb24oeSkgbWVhbihkbm9ybSh5LCBzaW1zX21pbnVzXzE4WywxXSArIHNpbXNfbWludXNfMThbLDJdKjE4LCBzaW1zX21pbnVzXzE4WywzXSkqNisxOCkpCmBgYAoKIyMjIyBDcmVhdGUgYSBwbG90IHdpdGggcG9zdGVyaW9yIG1lYW4gYW5kIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbgoKYGBge3IgfQpwMSA8LSBnZ3Bsb3QoZmFrZSwgYWVzKHggPSB4LCB5ID0geSkpICsKICBnZW9tX3BvaW50KGNvbG9yID0gIndoaXRlIiwgc2l6ZSA9IDMpICsKICBnZW9tX3BvaW50KGNvbG9yID0gImJsYWNrIiwgc2l6ZSA9IDIpCnAyIDwtIHAxICsKICBnZW9tX2FibGluZSgKICAgIGludGVyY2VwdCA9IG1lYW4oc2ltc1ssIDFdKSwKICAgIHNsb3BlID0gbWVhbihzaW1zWywgMl0pLAogICAgc2l6ZSA9IDEsCiAgICBjb2xvciA9ICJibGFjayIKICApCnAzIDwtIHAyICsgCiAgZ2VvbV9wYXRoKGRhdGE9Y29uZHByZWQsYWVzKHg9eCx5PXkpLCBjb2xvcj0iYmxhY2siKSArCiAgZ2VvbV92bGluZSh4aW50ZXJjZXB0PTE4LCBsaW5ldHlwZT0zLCBjb2xvcj0iZ3JleSIpCmBgYAoKIyMjIyBBZGQgTE9PIG1lYW4gYW5kIExPTyBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbiB3aGVuIHg9MTggaXMgbGVmdCBvdXQKCmBgYHtyIH0KcDQgPC0gcDMgKwogIGdlb21fcG9pbnQoZGF0YT1mYWtlWzE4LF0sIGNvbG9yID0gImdyZXk1MCIsIHNpemUgPSA1LCBzaGFwZT0xKSArCiAgZ2VvbV9hYmxpbmUoCiAgICBpbnRlcmNlcHQgPSBtZWFuKHNpbXNfbWludXNfMThbLCAxXSksCiAgICBzbG9wZSA9IG1lYW4oc2ltc19taW51c18xOFssIDJdKSwKICAgIHNpemUgPSAxLAogICAgY29sb3IgPSAiZ3JleTUwIiwKICAgIGxpbmV0eXBlPTIKICApICsKICBnZW9tX3BhdGgoZGF0YT1jb25kcHJlZGxvbyxhZXMoeD14LHk9eSksIGNvbG9yPSJncmV5NTAiLCBsaW5ldHlwZT0yKQpwNApgYGAKYGBge3IgZXZhbD1GQUxTRSwgaW5jbHVkZT1GQUxTRX0KaWYgKHNhdmVmaWdzKSBnZ3NhdmUocm9vdCgiQ3Jvc3NWYWxpZGF0aW9uL2ZpZ3MiLCJmYWtlbG9vMWEucGRmIikscDQsd2lkdGg9NixoZWlnaHQ9NSkKYGBgCmBgYHtyIH0KYGBgCgojIyMjIENvbXB1dGUgcG9zdGVyaW9yIGFuZCBMT08gcmVzaWR1YWxzPC9icj4KYGxvb19wcmVkaWN0KClgIGNvbXB1dGVzIG1lYW4gb2YgTE9PIHByZWRpY3RpdmUgZGlzdHJpYnV0aW9uLgoKYGBge3IgfQpmYWtlJHJlc2lkdWFsIDwtIGZha2UkeS1maXRfYWxsJGZpdHRlZApmYWtlJGxvb3Jlc2lkdWFsIDwtIGZha2UkeS1sb29fcHJlZGljdChmaXRfYWxsKSR2YWx1ZQpgYGAKCiMjIyMgUGxvdCBwb3N0ZXJpb3IgYW5kIExPTyByZXNpZHVhbHMKCmBgYHtyIH0KcDEgPC0gZ2dwbG90KGZha2UsIGFlcyh4ID0geCwgeSA9IHJlc2lkdWFsKSkgKwogIGdlb21fcG9pbnQoY29sb3IgPSAiYmxhY2siLCBzaXplID0gMiwgc2hhcGU9MTYpICsKICBnZW9tX3BvaW50KGFlcyh5PWxvb3Jlc2lkdWFsKSwgY29sb3IgPSAiZ3JleTUwIiwgc2l6ZSA9IDIsIHNoYXBlPTEpICsKICBnZW9tX3NlZ21lbnQoYWVzKHhlbmQ9eCwgeT1yZXNpZHVhbCwgeWVuZD1sb29yZXNpZHVhbCkpICsKICBnZW9tX2hsaW5lKHlpbnRlcmNlcHQ9MCwgbGluZXR5cGU9MikKcDEKYGBgCmBgYHtyIGV2YWw9RkFMU0UsIGluY2x1ZGU9RkFMU0V9CmlmIChzYXZlZmlncykgZ2dzYXZlKHJvb3QoIkNyb3NzVmFsaWRhdGlvbi9maWdzIiwiZmFrZWxvbzIucGRmIikscDQsd2lkdGg9NixoZWlnaHQ9NSkKYGBgCmBgYHtyIH0KYGBgCgojIyMjIFN0YW5kYXJkIGRldmlhdGlvbnMgb2YgcG9zdGVyaW9yIGFuZCBMT08gcmVzaWR1YWxzCgpgYGB7ciB9CnJvdW5kKHNkKGZha2UkcmVzaWR1YWwpLDIpCnJvdW5kKHNkKGZha2UkbG9vcmVzaWR1YWwpLDIpCmBgYAoKVmFyaWFuY2Ugb2YgcmVzaWR1YWxzIGlzIGNvbm5lY3RlZCB0byBSXjIsIHdoaWNoIGNhbiBiZSBkZWZpbmVkIGFzCjEtdmFyKHJlcykvdmFyKHkpCgpgYGB7ciB9CnJvdW5kKDEtdmFyKGZha2UkcmVzaWR1YWwpL3Zhcih5KSwyKQpyb3VuZCgxLXZhcihmYWtlJGxvb3Jlc2lkdWFsKS92YXIoeSksMikKYGBgCgojIyMjIENvbXB1dGUgbG9nIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRlbnNpdGllczwvYnI+CmBsb2dfbGlrYCByZXR1cm5zICRcbG9nKHAoeV9pfFx0aGV0YV57KHMpfSkpJAoKYGBge3IgfQpsbF8xIDwtIGxvZ19saWsoZml0X2FsbCkKYGBgCgpjb21wdXRlICRcbG9nKFxmcmFjezF9e1N9XHN1bV97cz0xfV5TIHAoeV9pfFx0aGV0YV57KHMpfSkkIGluCmNvbXB1dGF0aW9uYWxseSBzdGFibGUgd2F5CgpgYGB7ciB9CmZha2UkbHBkX3Bvc3QgPC0gbWF0cml4U3RhdHM6OmNvbExvZ1N1bUV4cHMobGxfMSkgLSBsb2cobnJvdyhsbF8xKSkKYGBgCgojIyMjIENvbXB1dGUgbG9nIExPTyBwcmVkaWN0aXZlIGRlbnNpdGllczwvYnI+CmBsb29gIHVzZXMgZmFzdCBhcHByb3hpbWF0ZSBsZWF2ZS1vbmUtb3V0IGNyb3NzLXZhbGlkYXRpb24KCmBgYHtyIH0KbG9vXzEgPC0gbG9vKGZpdF9hbGwpCmZha2UkbHBkX2xvbyA8LWxvb18xJHBvaW50d2lzZVssImVscGRfbG9vIl0KYGBgCgojIyMjIFBsb3QgcG9zdGVyaW9yIGFuZCBMT08gbG9nIHByZWRpY3RpdmUgZGVuc2l0aWVzCgpgYGB7ciB9CnAxIDwtIGdncGxvdChmYWtlLCBhZXMoeCA9IHgsIHkgPSBscGRfcG9zdCkpICsKICBnZW9tX3BvaW50KGNvbG9yID0gImJsYWNrIiwgc2l6ZSA9IDIsIHNoYXBlPTE2KSArCiAgZ2VvbV9wb2ludChhZXMoeT1scGRfbG9vKSwgY29sb3IgPSAiZ3JleTUwIiwgc2l6ZSA9IDIsIHNoYXBlPTEpICsKICBnZW9tX3NlZ21lbnQoYWVzKHhlbmQ9eCwgeT1scGRfcG9zdCwgeWVuZD1scGRfbG9vKSkgKwogIHlsYWIoImxvZyBwcmVkaWN0aXZlIGRlbnNpdHkiKQpwMQpgYGAKYGBge3IgZXZhbD1GQUxTRSwgaW5jbHVkZT1GQUxTRX0KaWYgKHNhdmVmaWdzKSBnZ3NhdmUocm9vdCgiQ3Jvc3NWYWxpZGF0aW9uL2ZpZ3MiLCJmYWtlbG9vMi5wZGYiKSxwMSx3aWR0aD02LGhlaWdodD01KQpgYGAKYGBge3IgfQpgYGAKCiMjIEtpZElRIGV4YW1wbGUKIyMjIyBMb2FkIGNoaWxkcmVuJ3MgdGVzdCBzY29yZXMgZGF0YQoKYGBge3IgfQpraWRpcSA8LSByZWFkLmR0YShmaWxlPXJvb3QoIktpZElRL2RhdGEiLCJraWRpcS5kdGEiKSkKYGBgCgojIyMjIExpbmVhciByZWdyZXNzaW9uCgpgYGB7ciB9CmZpdF8zIDwtIHN0YW5fZ2xtKGtpZF9zY29yZSB+IG1vbV9ocyArIG1vbV9pcSwgZGF0YT1raWRpcSwKICAgICAgICAgICAgICAgICAgc2VlZD1TRUVELCByZWZyZXNoID0gMCkKcHJpbnQoZml0XzMpCmBgYAoKIyMjIyBDb21wdXRlIFJeMiBhbmQgTE9PLVJeMiBtYW51YWxseQoKYGBge3IgfQpyZXNwb3N0IDwtIGtpZGlxJGtpZF9zY29yZS1maXRfMyRmaXR0ZWQKcmVzbG9vIDwtIGtpZGlxJGtpZF9zY29yZS1sb29fcHJlZGljdChmaXRfMykkdmFsdWUKcm91bmQoUjIgPC0gMSAtIHZhcihyZXNwb3N0KS92YXIoa2lkaXEka2lkX3Njb3JlKSwgMikKcm91bmQoUjJsb28gPC0gMSAtIHZhcihyZXNsb28pL3ZhcihraWRpcSRraWRfc2NvcmUpLCAyKQpgYGAKCiMjIyMgQWRkIGZpdmUgcHVyZSBub2lzZSBwcmVkaWN0b3JzIHRvIHRoZSBkYXRhCgpgYGB7ciB9CnNldC5zZWVkKFNFRUQpCm4gPC0gbnJvdyhraWRpcSkKa2lkaXFyIDwtIGtpZGlxCmtpZGlxciRub2lzZSA8LSBhcnJheShybm9ybSg1Km4pLCBjKG4sNSkpCmBgYAoKIyMjIyBMaW5lYXIgcmVncmVzc2lvbiB3aXRoIGFkZGl0aW9uYWwgbm9pc2UgcHJlZGljdG9ycwoKYGBge3IgfQpmaXRfM24gPC0gc3Rhbl9nbG0oa2lkX3Njb3JlIH4gbW9tX2hzICsgbW9tX2lxICsgbm9pc2UsIGRhdGE9a2lkaXFyLAogICAgICAgICAgICAgICAgICAgc2VlZD1TRUVELCByZWZyZXNoID0gMCkKcHJpbnQoZml0XzNuKQpgYGAKCiMjIyMgQ29tcHV0ZSBSXjIgYW5kIExPTy1SXjIgbWFudWFsbHkKCmBgYHtyIH0KcmVzcG9zdG4gPC0ga2lkaXEka2lkX3Njb3JlLWZpdF8zbiRmaXR0ZWQKcmVzbG9vbiA8LSBraWRpcSRraWRfc2NvcmUtbG9vX3ByZWRpY3QoZml0XzNuKSR2YWx1ZQpyb3VuZChSMm4gPC0gMSAtIHZhcihyZXNwb3N0bikvdmFyKGtpZGlxJGtpZF9zY29yZSksIDIpCnJvdW5kKFIybG9vbiA8LSAxIC0gdmFyKHJlc2xvb24pL3ZhcihraWRpcSRraWRfc2NvcmUpLCAyKQpgYGAKCiMjIyMgQWx0ZXJuYXRpdmUgbW9yZSBpbmZvcm1hdGl2ZSByZWd1bGFyaXplZCBob3JzZXNob2UgcHJpb3IKCmBgYHtyIH0KZml0XzNyaHMgPC0gc3Rhbl9nbG0oa2lkX3Njb3JlIH4gbW9tX2hzICsgbW9tX2lxLCBwcmlvcj1ocygpLCBkYXRhPWtpZGlxLAogICAgICAgICAgICAgICAgICAgICBzZWVkPVNFRUQsIHJlZnJlc2ggPSAwKQpmaXRfM3Joc24gPC0gc3Rhbl9nbG0oa2lkX3Njb3JlIH4gbW9tX2hzICsgbW9tX2lxICsgbm9pc2UsIHByaW9yPWhzKCksCiAgICAgICAgICAgICAgICAgICAgICBkYXRhPWtpZGlxciwgc2VlZD1TRUVELCByZWZyZXNoID0gMCkKcm91bmQobWVkaWFuKGJheWVzX1IyKGZpdF8zcmhzKSksIDIpCnJvdW5kKG1lZGlhbihsb29fUjIoZml0XzNyaHMpKSwgMikKcm91bmQobWVkaWFuKGJheWVzX1IyKGZpdF8zcmhzbikpLCAyKQpyb3VuZChtZWRpYW4obG9vX1IyKGZpdF8zcmhzbikpLCAyKQpgYGAKCiMjIyMgQ29tcHV0ZSBzdW0gb2YgbG9nIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRlbnNpdGllczwvYnI+CmBsb2dfbGlrYCByZXR1cm5zICRcbG9nKHAoeV9pfFx0aGV0YV57KHMpfSkpJAoKYGBge3IgfQpsbF8zIDwtIGxvZ19saWsoZml0XzMpCmxsXzNuIDwtIGxvZ19saWsoZml0XzNuKQpgYGAKCmNvbXB1dGUgJFxsb2coXGZyYWN7MX17U31cc3VtX3tzPTF9XlMgcCh5X2l8XHRoZXRhXnsocyl9KSQgaW4KY29tcHV0YXRpb25hbGx5IHN0YWJsZSB3YXkKCmBgYHtyIH0Kcm91bmQoc3VtKG1hdHJpeFN0YXRzOjpjb2xMb2dTdW1FeHBzKGxsXzMpIC0gbG9nKG5yb3cobGxfMykpKSwgMSkKcm91bmQoc3VtKG1hdHJpeFN0YXRzOjpjb2xMb2dTdW1FeHBzKGxsXzNuKSAtIGxvZyhucm93KGxsXzNuKSkpLCAxKQpgYGAKCiMjIyMgQ29tcHV0ZSBsb2cgTE9PIHByZWRpY3RpdmUgZGVuc2l0aWVzPC9icj4KYGxvb2AgdXNlcyBmYXN0IGFwcHJveGltYXRlIGxlYXZlLW9uZS1vdXQgY3Jvc3MtdmFsaWRhdGlvbgoKYGBge3IgfQpsb29fMyA8LSBsb28oZml0XzMpCmxvb18zbiA8LSBsb28oZml0XzNuKQpyb3VuZChsb29fMyRlc3RpbWF0ZVsiZWxwZF9sb28iLDFdLCAxKQpyb3VuZChsb29fM24kZXN0aW1hdGVbImVscGRfbG9vIiwxXSwgMSkKYGBgCgojIyMjIE1vcmUgaW5mb3JtYXRpb24gb24gTE9PIGVscGQgZXN0aW1hdGUgaW5jbHVkaW5nIHN0YW5kYXJkIGVycm9ycwoKYGBge3IgfQpsb29fMwpsb29fM24KYGBgCgojIyMjIE1vZGVsIHVzaW5nIG9ubHkgdGhlIG1hdGVybmFsIGhpZ2ggc2Nob29sIGluZGljYXRvcgoKCmBgYHtyIH0KZml0XzEgPC0gc3Rhbl9nbG0oa2lkX3Njb3JlIH4gbW9tX2hzLCBkYXRhPWtpZGlxLCByZWZyZXNoID0gMCkKKGxvb18xIDwtIGxvbyhmaXRfMSkpCmBgYAoKIyMjIyBDb21wYXJlIG1vZGVscyB1c2luZyBMT08gbG9nIHNjb3JlIChlbHBkKQoKYGBge3IgfQpsb29fY29tcGFyZShsb29fMywgbG9vXzEpCmBgYAoKIyMjIyBDb21wYXJlIG1vZGVscyB1c2luZyBMT08tUl4yCgpgYGB7ciB9CiMgd2UgbmVlZCB0byBmaXggdGhlIHNlZWQgdG8gZ2V0IGNvbXBhcmlzb24gdG8gd29yayBjb3JyZWN0bHkgaW4gdGhpcyBjYXNlCnNldC5zZWVkKDE0MTQpCmxvb1IyXzEgPC0gbG9vX1IyKGZpdF8xKQpzZXQuc2VlZCgxNDE0KQpsb29SMl8zIDwtIGxvb19SMihmaXRfMykKcm91bmQobWVhbihsb29SMl8xKSwgMikKcm91bmQobWVhbihsb29SMl8zKSwgMikKcm91bmQobWVhbihsb29SMl8zLWxvb1IyXzEpLCAyKQpyb3VuZChzZChsb29SMl8zLWxvb1IyXzEpLCAyKQpgYGAKCiMjIyMgTW9kZWwgd2l0aCBhbiBpbnRlcmFjdGlvbgoKYGBge3IgfQpmaXRfNCA8LSBzdGFuX2dsbShraWRfc2NvcmUgfiBtb21faHMgKyBtb21faXEgKyBtb21faHM6bW9tX2lxLAogICAgICAgICAgICAgICAgICBkYXRhPWtpZGlxLCByZWZyZXNoPTApCmBgYAoKIyMjIyBDb21wYXJlIG1vZGVscyB1c2luZyBMT08gbG9nIHNjb3JlIChlbHBkKQoKYGBge3IgfQpsb29fNCA8LSBsb28oZml0XzQpCmxvb19jb21wYXJlKGxvb18zLCBsb29fNCkKYGBgCgojIyMjIENvbXBhcmUgbW9kZWxzIHVzaW5nIExPTy1SXjIKCmBgYHtyIH0Kc2V0LnNlZWQoMTQxNCkKbG9vUjJfNCA8LSBsb29fUjIoZml0XzQpCnJvdW5kKG1lYW4obG9vUjJfNCksIDIpCnJvdW5kKG1lYW4obG9vUjJfNC1sb29SMl8zKSwgMikKcm91bmQoc2QobG9vUjJfNC1sb29SMl8zKSwgMikKYGBgCgo=