In the R notebook illustrating challenges of multiple regression I illustrated why we might want to reduce the number of covariates in our regression. In this notebook I’m going to illustrate a couple of different approaches:

  1. Retaining only the covariates that have a “real” relationship with the response variable.
  2. Selecting covariates from (relatively) uncorrelated clusters of covariates

Retaining covariates with a “real” relationship

In the example we’ve been playing with so far, we know that only x1, x2, and x3 have a “real” relationship with y, because the process we used to generate the data has 0s for the coefficient relating x4-x9 to y. Let’s regenerate the data from our last example, with \(R^2 \approx 0.4\), restrict our analysis to only x1, x2, and x3 and see if we encounter the instability in parameter estimates and predictions we saw last time.

library(tidyverse)
library(reshape2)
library(ggplot2)
library(cowplot)
library(mvtnorm)
library(corrplot)
## intetcept
##
beta0 <- 1.0
## regression coefficients
##
beta <- c(1.0, -1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
## pattern of correlation matrix, all non-zero entries are set to saem
## correlation, covariance matrix caldulated from individual variances and a 
## single association parameter governing the non-zero correlation coefficients
##
## Note: Not just any pattern will work here. The correlation matrix and
## covariance matrix generated from this pattern must be positive definite.
## If you change this pattern, you may get an error when you try to generate
## data with a non-zero association parameter.
##
Rho <- matrix(nrow = 9, ncol = , byrow = TRUE, 
              data = c(1,0,1,0,1,0,1,0,1,
                       0,1,0,1,0,1,0,1,0,
                       1,0,1,0,1,0,1,0,1,
                       0,1,0,1,0,1,0,1,0,
                       1,0,1,0,1,0,1,0,1,
                       0,1,0,1,0,1,0,1,0,
                       1,0,1,0,1,0,1,0,1,
                       0,1,0,1,0,1,0,1,0,
                       1,0,1,0,1,0,1,0,1
                       ))
## vector of standard deviations for covariates
##
sigma <- rep(1, 9)

## construct a covariance matrix from the pattern, standard deviations, and
## one parameter in [-1,1] that governs the magnitude of non-zero correlation
## coefficients
##
## Rho - the pattern of associations
## sigma - the vector of standard deviations
## rho - the association parameter
##
construct_Sigma <- function(Rho, sigma, rho) {
  ## get the correlation matris
  ##
  Rho <- Rho*rho
  for (i in 1:ncol(Rho)) {
    Rho[i,i] <- 1.0
  }
  ## notice the use of matrix multiplication
  ##
  Sigma <- diag(sigma) %*% Rho %*% diag(sigma)
  return(Sigma)
}

## set the random number seed manually so that every run of the code will 
## produce the same numbers
##
set.seed(1234)

n_samp <- 100
cov_str <- rmvnorm(n_samp,
                   mean = rep(0, nrow(Rho)),
                   sigma = construct_Sigma(Rho, sigma, 0.8))

resid <- rep(2.0, n_samp)

y_str <- rnorm(nrow(cov_str), mean = beta0 + cov_str %*% beta, sd = resid)
dat_1 <- data.frame(y_str, cov_str, rep("Strong", length(y_str)))

cov_str <- rmvnorm(n_samp,
                   mean = rep(0, nrow(Rho)),
                   sigma = construct_Sigma(Rho, sigma, 0.8))
y_str <- rnorm(nrow(cov_str), mean = beta0 + cov_str %*% beta, sd = resid)
dat_2 <- data.frame(y_str, cov_str, rep("Strong", length(y_str)))

column_names <- c("y", paste("x", seq(1, length(beta)), sep = ""), "Scenario")
colnames(dat_1) <- column_names
colnames(dat_2) <- column_names

Now that the data are generated, let’s run the analyses

lm_for_pred_1 <- lm(y ~ x1 + x2 + x3, data = dat_1)
lm_for_pred_2 <- lm(y ~ x1 + x2 + x3, data = dat_2)
summary(lm_for_pred_1)

Call:
lm(formula = y ~ x1 + x2 + x3, data = dat_1)

Residuals:
    Min      1Q  Median      3Q     Max 
-5.5057 -1.3596  0.0372  1.0451  4.9972 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)   0.8951     0.2076   4.311 3.93e-05 ***
x1            0.9918     0.3274   3.029 0.003150 ** 
x2           -0.5504     0.2232  -2.466 0.015419 *  
x3            1.0247     0.2942   3.483 0.000748 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.07 on 96 degrees of freedom
Multiple R-squared:  0.4006,    Adjusted R-squared:  0.3819 
F-statistic: 21.39 on 3 and 96 DF,  p-value: 1.079e-10
summary(lm_for_pred_2)

Call:
lm(formula = y ~ x1 + x2 + x3, data = dat_2)

Residuals:
    Min      1Q  Median      3Q     Max 
-4.5624 -1.3991 -0.0468  1.3177  4.1804 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)   1.0206     0.2001   5.099 1.71e-06 ***
x1            0.6424     0.3398   1.891 0.061704 .  
x2           -1.0993     0.1900  -5.787 8.99e-08 ***
x3            1.1957     0.3199   3.737 0.000316 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.93 on 96 degrees of freedom
Multiple R-squared:  0.4848,    Adjusted R-squared:  0.4687 
F-statistic: 30.11 on 3 and 96 DF,  p-value: 8.283e-14

Well, the first thing we discover is that the parameter estimates are not as stable as we might hope. They’re all in the right direction - x1 and x3 have positive coefficients, x2 has a negative coefficient -, but the magnitude of x2 is a long way off in the first data set and the magnitude of x1 is a long way off in the second data set. If we compare predictions, here’s what we get:

new_data <- data.frame(x1 = 4.0, x2 = 4.0, x3 = 4.0,
                       x4 = 4.0, x5 = 4.0, x6 = 4.0,
                       x7 = 4.0, x8 = 4.0, x9 = 4.0)
pred_from_1 <- predict.lm(lm_for_pred_1, new_data)
pred_from_2 <- predict.lm(lm_for_pred_2, new_data)

cat("Prediction from data set 1: ", pred_from_1, "\n",
    "Prediction from data set 2: ", pred_from_2, "\n",
    "True answer:                ", beta0 + as.matrix(new_data) %*% beta, "\n", sep = "")
Prediction from data set 1: 6.7596
Prediction from data set 2: 3.975488
True answer:                5

That doesn’t look very good either. This isn’t good news, because we know that x1, x2, and x3 have an association with y and even though we excluded irrelevant covariates our parameter estimates aren’t very stable and our predictions can be pretty variable. Let’s try another approach.

Selecting (relatively) uncorrelated covariates

One thing we could observe from the data even if we didn’t know how it was constructed is how the covariates are associated with one another. Let’s visualize those associations using corrplot() on each of the data sets.

corrplot(cor(dat_1[,2:10]), order = "hclust", title = "Data set 1")

corrplot(cor(dat_2[,2:10]), order = "hclust", title = "Data set 2")

Not surprisingly, both data sets show pretty clearly that there are two sets of coefficients within which there is a high correlation and between which there’s very little correlation at all.1 Let’s see what happens if we take one covariate from the first cluster and one from the second cluster, say x2 and x1. You should get similar results regardless of which covariate you pick from each cluster, but I’ll let you check that out on your own.

lm_for_pred_1 <- lm(y ~ x1 + x2, data = dat_1)
lm_for_pred_2 <- lm(y ~ x1 + x2, data = dat_2)
summary(lm_for_pred_1)

Call:
lm(formula = y ~ x1 + x2, data = dat_1)

Residuals:
    Min      1Q  Median      3Q     Max 
-5.5904 -1.2933 -0.0243  1.3791  5.3443 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)   0.8728     0.2191   3.984 0.000131 ***
x1            1.7472     0.2590   6.745 1.11e-09 ***
x2           -0.5170     0.2354  -2.196 0.030459 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.185 on 97 degrees of freedom
Multiple R-squared:  0.3249,    Adjusted R-squared:  0.311 
F-statistic: 23.34 on 2 and 97 DF,  p-value: 5.302e-09
summary(lm_for_pred_2)

Call:
lm(formula = y ~ x1 + x2, data = dat_2)

Residuals:
    Min      1Q  Median      3Q     Max 
-5.1753 -1.5097  0.0831  1.5921  4.2268 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)   0.9310     0.2116   4.400 2.78e-05 ***
x1            1.5923     0.2401   6.632 1.88e-09 ***
x2           -1.0565     0.2019  -5.232 9.66e-07 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.055 on 97 degrees of freedom
Multiple R-squared:  0.4099,    Adjusted R-squared:  0.3977 
F-statistic: 33.68 on 2 and 97 DF,  p-value: 7.789e-12
new_data <- data.frame(x1 = 4.0, x2 = 4.0, x3 = 4.0,
                       x4 = 4.0, x5 = 4.0, x6 = 4.0,
                       x7 = 4.0, x8 = 4.0, x9 = 4.0)
pred_from_1 <- predict.lm(lm_for_pred_1, new_data)
pred_from_2 <- predict.lm(lm_for_pred_2, new_data)

cat("Prediction from data set 1: ", pred_from_1, "\n",
    "Prediction from data set 2: ", pred_from_2, "\n",
    "True answer:                ", beta0 + as.matrix(new_data) %*% beta, "\n", sep = "")
Prediction from data set 1: 5.793525
Prediction from data set 2: 3.07432
True answer:                5

That’s a bit better, but not a lot. Just for the record, a Bayesian version of the analysis gives similar results.

library(rstanarm)
Loading required package: Rcpp
rstanarm (Version 2.18.2, packaged: 2018-11-08 22:19:38 UTC)
- Do not expect the default priors to remain the same in future rstanarm versions.
Thus, R scripts should specify priors explicitly, even if they are just the defaults.
- For execution on a local, multicore CPU with excess RAM we recommend calling
options(mc.cores = parallel::detectCores())
- Plotting theme set to bayesplot::theme_default().
options(mc.cores = parallel::detectCores())

stan_lm_for_pred_1 <- stan_glm(y ~ x1 + x2, data = dat_1, family = gaussian(), refresh = 0)
stan_lm_for_pred_2 <- stan_glm(y ~ x1 + x2, data = dat_2, family = gaussian(), refresh = 0)
summary(stan_lm_for_pred_1, digits = 3)

Model Info:

 function:     stan_glm
 family:       gaussian [identity]
 formula:      y ~ x1 + x2
 algorithm:    sampling
 priors:       see help('prior_summary')
 sample:       4000 (posterior sample size)
 observations: 100
 predictors:   3

Estimates:
                mean     sd       2.5%     25%      50%      75%      97.5% 
(Intercept)      0.875    0.218    0.452    0.727    0.875    1.021    1.311
x1               1.744    0.254    1.247    1.579    1.745    1.913    2.238
x2              -0.512    0.232   -0.956   -0.670   -0.513   -0.353   -0.067
sigma            2.200    0.162    1.908    2.088    2.189    2.301    2.543
mean_PPD         0.901    0.314    0.277    0.688    0.902    1.111    1.516
log-posterior -227.611    1.414 -231.265 -228.243 -227.265 -226.592 -225.875

Diagnostics:
              mcse  Rhat  n_eff
(Intercept)   0.003 0.999 4858 
x1            0.004 1.000 4197 
x2            0.003 1.000 4573 
sigma         0.002 1.000 4911 
mean_PPD      0.005 1.000 3894 
log-posterior 0.034 1.002 1706 

For each parameter, mcse is Monte Carlo standard error, n_eff is a crude measure of effective sample size, and Rhat is the potential scale reduction factor on split chains (at convergence Rhat=1).
summary(stan_lm_for_pred_2, digits = 3)

Model Info:

 function:     stan_glm
 family:       gaussian [identity]
 formula:      y ~ x1 + x2
 algorithm:    sampling
 priors:       see help('prior_summary')
 sample:       4000 (posterior sample size)
 observations: 100
 predictors:   3

Estimates:
                mean     sd       2.5%     25%      50%      75%      97.5% 
(Intercept)      0.933    0.220    0.498    0.787    0.934    1.085    1.355
x1               1.588    0.245    1.105    1.422    1.590    1.759    2.066
x2              -1.058    0.201   -1.460   -1.195   -1.057   -0.926   -0.655
sigma            2.070    0.152    1.798    1.966    2.061    2.163    2.401
mean_PPD         1.336    0.300    0.750    1.134    1.334    1.533    1.919
log-posterior -221.590    1.482 -225.291 -222.307 -221.224 -220.513 -219.769

Diagnostics:
              mcse  Rhat  n_eff
(Intercept)   0.003 1.000 5020 
x1            0.004 1.000 4604 
x2            0.003 1.000 4388 
sigma         0.002 1.000 4219 
mean_PPD      0.005 0.999 4417 
log-posterior 0.036 1.001 1696 

For each parameter, mcse is Monte Carlo standard error, n_eff is a crude measure of effective sample size, and Rhat is the potential scale reduction factor on split chains (at convergence Rhat=1).

Conclusion

What have we learned so far? Here’s my quick summary:

So what are we to do? Well, there are some other alternatives to reducing the number of covariates that we’ll explore in notebooks yet to come.


  1. I say “not surprisingly”, of course, because we specifically constructed the correlation matrix this way.

  2. In the sense that if you simulate new data under the same conditions your estimates of regression coefficients are likely to be quite different.

  3. If you knew which ones were important ahead of time, why did you bother measuring all the rest?

  4. To be fair, part of the problem here comes from looking only at the point estimates. Look at the results from rstanarm() again. You’ll see that the credible intervals for x1 and x2 as estimated from data set 1 overlap broadly with those estimated from data set 2. The estimates aren’t as different from one another as they initially appear. Neither are the posterior predictions. (Verifying that is left as an exercise for those who are interested.)

LS0tCnRpdGxlOiAiUmVkdWNpbmcgdGhlIG51bWJlciBvZiBjb3ZhcmlhdGVzIC0gYSBjb3VwbGUgb2YgXCJzaW1wbGVcIiBzdHJhdGVnaWVzIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpJbiB0aGUgUiBub3RlYm9vayBpbGx1c3RyYXRpbmcgW2NoYWxsZW5nZXMgb2YgbXVsdGlwbGUgcmVncmVzc2lvbl0oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L3BhZ2VzL3ZhcmlhYmxlLXNlbGVjdGlvbi9jaGFsbGVuZ2VzLW9mLW11bHRpcGxlLXJlZ3Jlc3Npb24ubmIuaHRtbCkgSSBpbGx1c3RyYXRlZCB3aHkgd2UgbWlnaHQgd2FudCB0byByZWR1Y2UgdGhlIG51bWJlciBvZiBjb3ZhcmlhdGVzIGluIG91ciByZWdyZXNzaW9uLiBJbiB0aGlzIG5vdGVib29rIEknbSBnb2luZyB0byBpbGx1c3RyYXRlIGEgY291cGxlIG9mIGRpZmZlcmVudCBhcHByb2FjaGVzOgoKMS4gUmV0YWluaW5nIG9ubHkgdGhlIGNvdmFyaWF0ZXMgdGhhdCBoYXZlIGEgInJlYWwiIHJlbGF0aW9uc2hpcCB3aXRoIHRoZSByZXNwb25zZSB2YXJpYWJsZS4KMi4gU2VsZWN0aW5nIGNvdmFyaWF0ZXMgZnJvbSAocmVsYXRpdmVseSkgdW5jb3JyZWxhdGVkIGNsdXN0ZXJzIG9mIGNvdmFyaWF0ZXMKCiMjIFJldGFpbmluZyBjb3ZhcmlhdGVzIHdpdGggYSAicmVhbCIgcmVsYXRpb25zaGlwCgpJbiB0aGUgZXhhbXBsZSB3ZSd2ZSBiZWVuIHBsYXlpbmcgd2l0aCBzbyBmYXIsIHdlIGtub3cgdGhhdCBvbmx5IGB4MWAsIGB4MmAsIGFuZCBgeDNgIGhhdmUgYSAicmVhbCIgcmVsYXRpb25zaGlwIHdpdGggYHlgLCBiZWNhdXNlIHRoZSBwcm9jZXNzIHdlIHVzZWQgdG8gZ2VuZXJhdGUgdGhlIGRhdGEgaGFzIDBzIGZvciB0aGUgY29lZmZpY2llbnQgcmVsYXRpbmcgYHg0YC1geDlgIHRvIGB5YC4gTGV0J3MgcmVnZW5lcmF0ZSB0aGUgZGF0YSBmcm9tIG91ciBsYXN0IGV4YW1wbGUsIHdpdGggJFJeMiBcYXBwcm94IDAuNCQsIHJlc3RyaWN0IG91ciBhbmFseXNpcyB0byBvbmx5IGB4MWAsIGB4MmAsIGFuZCBgeDNgIGFuZCBzZWUgaWYgd2UgZW5jb3VudGVyIHRoZSBpbnN0YWJpbGl0eSBpbiBwYXJhbWV0ZXIgZXN0aW1hdGVzIGFuZCBwcmVkaWN0aW9ucyB3ZSBzYXcgbGFzdCB0aW1lLiAKYGBge3Igc2V0dXAsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShyZXNoYXBlMikKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGNvd3Bsb3QpCmxpYnJhcnkobXZ0bm9ybSkKbGlicmFyeShjb3JycGxvdCkKYGBgCgpgYGB7cn0KIyMgaW50ZXRjZXB0CiMjCmJldGEwIDwtIDEuMAojIyByZWdyZXNzaW9uIGNvZWZmaWNpZW50cwojIwpiZXRhIDwtIGMoMS4wLCAtMS4wLCAxLjAsIDAuMCwgMC4wLCAwLjAsIDAuMCwgMC4wLCAwLjApCiMjIHBhdHRlcm4gb2YgY29ycmVsYXRpb24gbWF0cml4LCBhbGwgbm9uLXplcm8gZW50cmllcyBhcmUgc2V0IHRvIHNhZW0KIyMgY29ycmVsYXRpb24sIGNvdmFyaWFuY2UgbWF0cml4IGNhbGR1bGF0ZWQgZnJvbSBpbmRpdmlkdWFsIHZhcmlhbmNlcyBhbmQgYSAKIyMgc2luZ2xlIGFzc29jaWF0aW9uIHBhcmFtZXRlciBnb3Zlcm5pbmcgdGhlIG5vbi16ZXJvIGNvcnJlbGF0aW9uIGNvZWZmaWNpZW50cwojIwojIyBOb3RlOiBOb3QganVzdCBhbnkgcGF0dGVybiB3aWxsIHdvcmsgaGVyZS4gVGhlIGNvcnJlbGF0aW9uIG1hdHJpeCBhbmQKIyMgY292YXJpYW5jZSBtYXRyaXggZ2VuZXJhdGVkIGZyb20gdGhpcyBwYXR0ZXJuIG11c3QgYmUgcG9zaXRpdmUgZGVmaW5pdGUuCiMjIElmIHlvdSBjaGFuZ2UgdGhpcyBwYXR0ZXJuLCB5b3UgbWF5IGdldCBhbiBlcnJvciB3aGVuIHlvdSB0cnkgdG8gZ2VuZXJhdGUKIyMgZGF0YSB3aXRoIGEgbm9uLXplcm8gYXNzb2NpYXRpb24gcGFyYW1ldGVyLgojIwpSaG8gPC0gbWF0cml4KG5yb3cgPSA5LCBuY29sID0gLCBieXJvdyA9IFRSVUUsIAogICAgICAgICAgICAgIGRhdGEgPSBjKDEsMCwxLDAsMSwwLDEsMCwxLAogICAgICAgICAgICAgICAgICAgICAgIDAsMSwwLDEsMCwxLDAsMSwwLAogICAgICAgICAgICAgICAgICAgICAgIDEsMCwxLDAsMSwwLDEsMCwxLAogICAgICAgICAgICAgICAgICAgICAgIDAsMSwwLDEsMCwxLDAsMSwwLAogICAgICAgICAgICAgICAgICAgICAgIDEsMCwxLDAsMSwwLDEsMCwxLAogICAgICAgICAgICAgICAgICAgICAgIDAsMSwwLDEsMCwxLDAsMSwwLAogICAgICAgICAgICAgICAgICAgICAgIDEsMCwxLDAsMSwwLDEsMCwxLAogICAgICAgICAgICAgICAgICAgICAgIDAsMSwwLDEsMCwxLDAsMSwwLAogICAgICAgICAgICAgICAgICAgICAgIDEsMCwxLDAsMSwwLDEsMCwxCiAgICAgICAgICAgICAgICAgICAgICAgKSkKIyMgdmVjdG9yIG9mIHN0YW5kYXJkIGRldmlhdGlvbnMgZm9yIGNvdmFyaWF0ZXMKIyMKc2lnbWEgPC0gcmVwKDEsIDkpCgojIyBjb25zdHJ1Y3QgYSBjb3ZhcmlhbmNlIG1hdHJpeCBmcm9tIHRoZSBwYXR0ZXJuLCBzdGFuZGFyZCBkZXZpYXRpb25zLCBhbmQKIyMgb25lIHBhcmFtZXRlciBpbiBbLTEsMV0gdGhhdCBnb3Zlcm5zIHRoZSBtYWduaXR1ZGUgb2Ygbm9uLXplcm8gY29ycmVsYXRpb24KIyMgY29lZmZpY2llbnRzCiMjCiMjIFJobyAtIHRoZSBwYXR0ZXJuIG9mIGFzc29jaWF0aW9ucwojIyBzaWdtYSAtIHRoZSB2ZWN0b3Igb2Ygc3RhbmRhcmQgZGV2aWF0aW9ucwojIyByaG8gLSB0aGUgYXNzb2NpYXRpb24gcGFyYW1ldGVyCiMjCmNvbnN0cnVjdF9TaWdtYSA8LSBmdW5jdGlvbihSaG8sIHNpZ21hLCByaG8pIHsKICAjIyBnZXQgdGhlIGNvcnJlbGF0aW9uIG1hdHJpcwogICMjCiAgUmhvIDwtIFJobypyaG8KICBmb3IgKGkgaW4gMTpuY29sKFJobykpIHsKICAgIFJob1tpLGldIDwtIDEuMAogIH0KICAjIyBub3RpY2UgdGhlIHVzZSBvZiBtYXRyaXggbXVsdGlwbGljYXRpb24KICAjIwogIFNpZ21hIDwtIGRpYWcoc2lnbWEpICUqJSBSaG8gJSolIGRpYWcoc2lnbWEpCiAgcmV0dXJuKFNpZ21hKQp9CgojIyBzZXQgdGhlIHJhbmRvbSBudW1iZXIgc2VlZCBtYW51YWxseSBzbyB0aGF0IGV2ZXJ5IHJ1biBvZiB0aGUgY29kZSB3aWxsIAojIyBwcm9kdWNlIHRoZSBzYW1lIG51bWJlcnMKIyMKc2V0LnNlZWQoMTIzNCkKCm5fc2FtcCA8LSAxMDAKY292X3N0ciA8LSBybXZub3JtKG5fc2FtcCwKICAgICAgICAgICAgICAgICAgIG1lYW4gPSByZXAoMCwgbnJvdyhSaG8pKSwKICAgICAgICAgICAgICAgICAgIHNpZ21hID0gY29uc3RydWN0X1NpZ21hKFJobywgc2lnbWEsIDAuOCkpCgpyZXNpZCA8LSByZXAoMi4wLCBuX3NhbXApCgp5X3N0ciA8LSBybm9ybShucm93KGNvdl9zdHIpLCBtZWFuID0gYmV0YTAgKyBjb3Zfc3RyICUqJSBiZXRhLCBzZCA9IHJlc2lkKQpkYXRfMSA8LSBkYXRhLmZyYW1lKHlfc3RyLCBjb3Zfc3RyLCByZXAoIlN0cm9uZyIsIGxlbmd0aCh5X3N0cikpKQoKY292X3N0ciA8LSBybXZub3JtKG5fc2FtcCwKICAgICAgICAgICAgICAgICAgIG1lYW4gPSByZXAoMCwgbnJvdyhSaG8pKSwKICAgICAgICAgICAgICAgICAgIHNpZ21hID0gY29uc3RydWN0X1NpZ21hKFJobywgc2lnbWEsIDAuOCkpCnlfc3RyIDwtIHJub3JtKG5yb3coY292X3N0ciksIG1lYW4gPSBiZXRhMCArIGNvdl9zdHIgJSolIGJldGEsIHNkID0gcmVzaWQpCmRhdF8yIDwtIGRhdGEuZnJhbWUoeV9zdHIsIGNvdl9zdHIsIHJlcCgiU3Ryb25nIiwgbGVuZ3RoKHlfc3RyKSkpCgpjb2x1bW5fbmFtZXMgPC0gYygieSIsIHBhc3RlKCJ4Iiwgc2VxKDEsIGxlbmd0aChiZXRhKSksIHNlcCA9ICIiKSwgIlNjZW5hcmlvIikKY29sbmFtZXMoZGF0XzEpIDwtIGNvbHVtbl9uYW1lcwpjb2xuYW1lcyhkYXRfMikgPC0gY29sdW1uX25hbWVzCmBgYAoKTm93IHRoYXQgdGhlIGRhdGEgYXJlIGdlbmVyYXRlZCwgbGV0J3MgcnVuIHRoZSBhbmFseXNlcwpgYGB7cn0KbG1fZm9yX3ByZWRfMSA8LSBsbSh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gZGF0XzEpCmxtX2Zvcl9wcmVkXzIgPC0gbG0oeSB+IHgxICsgeDIgKyB4MywgZGF0YSA9IGRhdF8yKQpzdW1tYXJ5KGxtX2Zvcl9wcmVkXzEpCnN1bW1hcnkobG1fZm9yX3ByZWRfMikKYGBgCldlbGwsIHRoZSBmaXJzdCB0aGluZyB3ZSBkaXNjb3ZlciBpcyB0aGF0IHRoZSBwYXJhbWV0ZXIgZXN0aW1hdGVzIGFyZSBub3QgYXMgc3RhYmxlIGFzIHdlIG1pZ2h0IGhvcGUuIFRoZXkncmUgYWxsIGluIHRoZSByaWdodCBkaXJlY3Rpb24gLSBgeDFgIGFuZCBgeDNgIGhhdmUgcG9zaXRpdmUgY29lZmZpY2llbnRzLCBgeDJgIGhhcyBhIG5lZ2F0aXZlIGNvZWZmaWNpZW50IC0sIGJ1dCB0aGUgbWFnbml0dWRlIG9mIGB4MmAgaXMgYSBsb25nIHdheSBvZmYgaW4gdGhlIGZpcnN0IGRhdGEgc2V0IGFuZCB0aGUgbWFnbml0dWRlIG9mIGB4MWAgaXMgYSBsb25nIHdheSBvZmYgaW4gdGhlIHNlY29uZCBkYXRhIHNldC4gSWYgd2UgY29tcGFyZSBwcmVkaWN0aW9ucywgaGVyZSdzIHdoYXQgd2UgZ2V0OgpgYGB7cn0KbmV3X2RhdGEgPC0gZGF0YS5mcmFtZSh4MSA9IDQuMCwgeDIgPSA0LjAsIHgzID0gNC4wLAogICAgICAgICAgICAgICAgICAgICAgIHg0ID0gNC4wLCB4NSA9IDQuMCwgeDYgPSA0LjAsCiAgICAgICAgICAgICAgICAgICAgICAgeDcgPSA0LjAsIHg4ID0gNC4wLCB4OSA9IDQuMCkKcHJlZF9mcm9tXzEgPC0gcHJlZGljdC5sbShsbV9mb3JfcHJlZF8xLCBuZXdfZGF0YSkKcHJlZF9mcm9tXzIgPC0gcHJlZGljdC5sbShsbV9mb3JfcHJlZF8yLCBuZXdfZGF0YSkKCmNhdCgiUHJlZGljdGlvbiBmcm9tIGRhdGEgc2V0IDE6ICIsIHByZWRfZnJvbV8xLCAiXG4iLAogICAgIlByZWRpY3Rpb24gZnJvbSBkYXRhIHNldCAyOiAiLCBwcmVkX2Zyb21fMiwgIlxuIiwKICAgICJUcnVlIGFuc3dlcjogICAgICAgICAgICAgICAgIiwgYmV0YTAgKyBhcy5tYXRyaXgobmV3X2RhdGEpICUqJSBiZXRhLCAiXG4iLCBzZXAgPSAiIikKYGBgClRoYXQgZG9lc24ndCBsb29rIHZlcnkgZ29vZCBlaXRoZXIuIFRoaXMgaXNuJ3QgZ29vZCBuZXdzLCBiZWNhdXNlIHdlIGtub3cgdGhhdCBgeDFgLCBgeDJgLCBhbmQgYHgzYCBoYXZlIGFuIGFzc29jaWF0aW9uIHdpdGggYHlgIGFuZCBldmVuIHRob3VnaCB3ZSBleGNsdWRlZCBpcnJlbGV2YW50IGNvdmFyaWF0ZXMgb3VyIHBhcmFtZXRlciBlc3RpbWF0ZXMgYXJlbid0IHZlcnkgc3RhYmxlIGFuZCBvdXIgcHJlZGljdGlvbnMgY2FuIGJlIHByZXR0eSB2YXJpYWJsZS4gTGV0J3MgdHJ5IGFub3RoZXIgYXBwcm9hY2guCgojIyBTZWxlY3RpbmcgKHJlbGF0aXZlbHkpIHVuY29ycmVsYXRlZCBjb3ZhcmlhdGVzCgpPbmUgdGhpbmcgd2UgY291bGQgb2JzZXJ2ZSBmcm9tIHRoZSBkYXRhIGV2ZW4gaWYgd2UgZGlkbid0IGtub3cgaG93IGl0IHdhcyBjb25zdHJ1Y3RlZCBpcyBob3cgdGhlIGNvdmFyaWF0ZXMgYXJlIGFzc29jaWF0ZWQgd2l0aCBvbmUgYW5vdGhlci4gTGV0J3MgdmlzdWFsaXplIHRob3NlIGFzc29jaWF0aW9ucyB1c2luZyBgY29ycnBsb3QoKWAgb24gZWFjaCBvZiB0aGUgZGF0YSBzZXRzLgpgYGB7cn0KY29ycnBsb3QoY29yKGRhdF8xWywyOjEwXSksIG9yZGVyID0gImhjbHVzdCIsIHRpdGxlID0gIkRhdGEgc2V0IDEiKQpjb3JycGxvdChjb3IoZGF0XzJbLDI6MTBdKSwgb3JkZXIgPSAiaGNsdXN0IiwgdGl0bGUgPSAiRGF0YSBzZXQgMiIpCmBgYApOb3Qgc3VycHJpc2luZ2x5LCBib3RoIGRhdGEgc2V0cyBzaG93IHByZXR0eSBjbGVhcmx5IHRoYXQgdGhlcmUgYXJlIHR3byBzZXRzIG9mIGNvZWZmaWNpZW50cyB3aXRoaW4gd2hpY2ggdGhlcmUgaXMgYSBoaWdoIGNvcnJlbGF0aW9uIGFuZCBiZXR3ZWVuIHdoaWNoIHRoZXJlJ3MgdmVyeSBsaXR0bGUgY29ycmVsYXRpb24gYXQgYWxsLlteMV0gTGV0J3Mgc2VlIHdoYXQgaGFwcGVucyBpZiB3ZSB0YWtlIG9uZSBjb3ZhcmlhdGUgZnJvbSB0aGUgZmlyc3QgY2x1c3RlciBhbmQgb25lIGZyb20gdGhlIHNlY29uZCBjbHVzdGVyLCBzYXkgYHgyYCBhbmQgYHgxYC4gWW91IHNob3VsZCBnZXQgc2ltaWxhciByZXN1bHRzIHJlZ2FyZGxlc3Mgb2Ygd2hpY2ggY292YXJpYXRlIHlvdSBwaWNrIGZyb20gZWFjaCBjbHVzdGVyLCBidXQgSSdsbCBsZXQgeW91IGNoZWNrIHRoYXQgb3V0IG9uIHlvdXIgb3duLgpgYGB7cn0KbG1fZm9yX3ByZWRfMSA8LSBsbSh5IH4geDEgKyB4MiwgZGF0YSA9IGRhdF8xKQpsbV9mb3JfcHJlZF8yIDwtIGxtKHkgfiB4MSArIHgyLCBkYXRhID0gZGF0XzIpCnN1bW1hcnkobG1fZm9yX3ByZWRfMSkKc3VtbWFyeShsbV9mb3JfcHJlZF8yKQoKbmV3X2RhdGEgPC0gZGF0YS5mcmFtZSh4MSA9IDQuMCwgeDIgPSA0LjAsIHgzID0gNC4wLAogICAgICAgICAgICAgICAgICAgICAgIHg0ID0gNC4wLCB4NSA9IDQuMCwgeDYgPSA0LjAsCiAgICAgICAgICAgICAgICAgICAgICAgeDcgPSA0LjAsIHg4ID0gNC4wLCB4OSA9IDQuMCkKcHJlZF9mcm9tXzEgPC0gcHJlZGljdC5sbShsbV9mb3JfcHJlZF8xLCBuZXdfZGF0YSkKcHJlZF9mcm9tXzIgPC0gcHJlZGljdC5sbShsbV9mb3JfcHJlZF8yLCBuZXdfZGF0YSkKCmNhdCgiUHJlZGljdGlvbiBmcm9tIGRhdGEgc2V0IDE6ICIsIHByZWRfZnJvbV8xLCAiXG4iLAogICAgIlByZWRpY3Rpb24gZnJvbSBkYXRhIHNldCAyOiAiLCBwcmVkX2Zyb21fMiwgIlxuIiwKICAgICJUcnVlIGFuc3dlcjogICAgICAgICAgICAgICAgIiwgYmV0YTAgKyBhcy5tYXRyaXgobmV3X2RhdGEpICUqJSBiZXRhLCAiXG4iLCBzZXAgPSAiIikKYGBgClRoYXQncyBhIGJpdCBiZXR0ZXIsIGJ1dCBub3QgYSBsb3QuIEp1c3QgZm9yIHRoZSByZWNvcmQsIGEgQmF5ZXNpYW4gdmVyc2lvbiBvZiB0aGUgYW5hbHlzaXMgZ2l2ZXMgc2ltaWxhciByZXN1bHRzLgpgYGB7cn0KbGlicmFyeShyc3RhbmFybSkKCm9wdGlvbnMobWMuY29yZXMgPSBwYXJhbGxlbDo6ZGV0ZWN0Q29yZXMoKSkKCnN0YW5fbG1fZm9yX3ByZWRfMSA8LSBzdGFuX2dsbSh5IH4geDEgKyB4MiwgZGF0YSA9IGRhdF8xLCBmYW1pbHkgPSBnYXVzc2lhbigpLCByZWZyZXNoID0gMCkKc3Rhbl9sbV9mb3JfcHJlZF8yIDwtIHN0YW5fZ2xtKHkgfiB4MSArIHgyLCBkYXRhID0gZGF0XzIsIGZhbWlseSA9IGdhdXNzaWFuKCksIHJlZnJlc2ggPSAwKQpzdW1tYXJ5KHN0YW5fbG1fZm9yX3ByZWRfMSwgZGlnaXRzID0gMykKc3VtbWFyeShzdGFuX2xtX2Zvcl9wcmVkXzIsIGRpZ2l0cyA9IDMpCmBgYAoKIyMgQ29uY2x1c2lvbgoKV2hhdCBoYXZlIHdlIGxlYXJuZWQgc28gZmFyPyBIZXJlJ3MgbXkgcXVpY2sgc3VtbWFyeToKCiogW011bHRpcGxlIHJlZ3Jlc3Npb24gaXMgdXNlZnVsXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvdW5jb21tb24tZ3JvdW5kL2Jsb2cvMjAxOS8wOC8xMi9jb2xsZWN0aW5nLW15LXRob3VnaHRzLWFib3V0LXZhcmlhYmxlLXNlbGVjdGlvbi1pbi1tdWx0aXBsZS1yZWdyZXNzaW9uLykuIEl0IF8qbWF5Kl8gdW5kZXIgdGhlIGFwcHJvcHJpYXRlIGNpcmN1bXN0YW5jZXMgYWxsb3cgdXMgdG8gZGlzdGluZ3Vpc2ggInJlYWwiIGZyb20gInNwdXJpb3VzIiBhc3NvY2lhdGlvbnMuCgoqIFtUaGVyZSBhcmUgc29tZSBzaWduaWZpY2FudCBjaGFsbGVuZ2VzXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvdW5jb21tb24tZ3JvdW5kL2Jsb2cvMjAxOS8wOC8xOS9jaGFsbGVuZ2VzLW9mLW11bHRpcGxlLXJlZ3Jlc3Npb24tb3Itd2h5LXdlLW1pZ2h0LXdhbnQtdG8tc2VsZWN0LXZhcmlhYmxlcy8pIHRvIHVzaW5nIG11bHRpcGxlIHJlZ3Jlc3Npb24uIFNwZWNpZmljYWxseSwgaWYgeW91IGluY2x1ZGUgYWxsIG9mIHRoZSBjb3ZhcmlhdGVzIHlvdSd2ZSBtZWFzdXJlZCBhbmQgdGhleSBhcmUgaGlnaGx5IGNvcnJlbGF0ZWQKCiAgKiBZb3VyIGVzdGltYXRlcyBvZiBhc3NvY2lhdGlvbiBhcmUgbGlrZWx5IHRvIGJlIHVuc3RhYmxlLlteMl0KCiAgKiBBcyBhIHJlc3VsdCwgcHJlZGljdGlvbnMgeW91IG1ha2UgZnJvbSB5b3VyIHJlZ3Jlc3Npb24gdGhhdCBleHRyYXBvbGF0ZSBiZXlvbmQgdGhlIGJvdW5kcyBvZiB0aGUgZGF0YSB5b3UgZml0IGFyZSBhbHNvIGxpa2VseSB0byBiZSB1bnN0YWJsZS4KCiogRXZlbiBpZiB5b3Uga25vdyBhaGVhZCBvZiB0aW1lIHdoaWNoIGNvdmFyaWF0ZXMgYXJlIGltcG9ydGFudCxbXjNdIHlvdXIgZXN0aW1hdGVzIG9mIHRoZSBtYWduaXR1ZGUgb2YgYW55IGFzc29jaWF0aW9uIGFyZSBsaWtlbHkgdG8gYmUgdmVyeSBpbXByZWNpc2UuCgoqIEFuZCBpZiB5b3UgcmVzdHJpY3QgeW91IGNvdmFyaWF0ZXMgdG8gdGhvc2UgdGhhdCBhcmUgcm91Z2hseSBpbmRlcGVuZGVudCwgeW91IGFyZW4ndCBtdWNoIGJldHRlciBvZmYuW140XQoKU28gd2hhdCBhcmUgd2UgdG8gZG8/IFdlbGwsIHRoZXJlIGFyZSBzb21lIG90aGVyIGFsdGVybmF0aXZlcyB0byByZWR1Y2luZyB0aGUgbnVtYmVyIG9mIGNvdmFyaWF0ZXMgdGhhdCB3ZSdsbCBleHBsb3JlIGluIG5vdGVib29rcyB5ZXQgdG8gY29tZS4KClteMV06IEkgc2F5ICJub3Qgc3VycHJpc2luZ2x5Iiwgb2YgY291cnNlLCBiZWNhdXNlIHdlIHNwZWNpZmljYWxseSBjb25zdHJ1Y3RlZCB0aGUgY29ycmVsYXRpb24gbWF0cml4IHRoaXMgd2F5LgoKW14yXTogSW4gdGhlIHNlbnNlIHRoYXQgaWYgeW91IHNpbXVsYXRlIG5ldyBkYXRhIHVuZGVyIHRoZSBzYW1lIGNvbmRpdGlvbnMgeW91ciBlc3RpbWF0ZXMgb2YgcmVncmVzc2lvbiBjb2VmZmljaWVudHMgYXJlIGxpa2VseSB0byBiZSBxdWl0ZSBkaWZmZXJlbnQuCgpbXjNdOiBJZiB5b3Uga25ldyB3aGljaCBvbmVzIHdlcmUgaW1wb3J0YW50IGFoZWFkIG9mIHRpbWUsIHdoeSBkaWQgeW91IGJvdGhlciBtZWFzdXJpbmcgYWxsIHRoZSByZXN0PwoKW140XTogVG8gYmUgZmFpciwgcGFydCBvZiB0aGUgcHJvYmxlbSBoZXJlIGNvbWVzIGZyb20gbG9va2luZyBvbmx5IGF0IHRoZSBwb2ludCBlc3RpbWF0ZXMuIExvb2sgYXQgdGhlIHJlc3VsdHMgZnJvbSBgcnN0YW5hcm0oKWAgYWdhaW4uIFlvdSdsbCBzZWUgdGhhdCB0aGUgY3JlZGlibGUgaW50ZXJ2YWxzIGZvciBgeDFgIGFuZCBgeDJgIGFzIGVzdGltYXRlZCBmcm9tIGRhdGEgc2V0IDEgb3ZlcmxhcCBicm9hZGx5IHdpdGggdGhvc2UgZXN0aW1hdGVkIGZyb20gZGF0YSBzZXQgMi4gVGhlIGVzdGltYXRlcyBhcmVuJ3QgYXMgZGlmZmVyZW50IGZyb20gb25lIGFub3RoZXIgYXMgdGhleSBpbml0aWFsbHkgYXBwZWFyLiBOZWl0aGVyIGFyZSB0aGUgcG9zdGVyaW9yIHByZWRpY3Rpb25zLiAoVmVyaWZ5aW5nIHRoYXQgaXMgbGVmdCBhcyBhbiBleGVyY2lzZSBmb3IgdGhvc2Ugd2hvIGFyZSBpbnRlcmVzdGVkLik=