1. Multikolinearita – definícia

Uvažujme lineárny regresný model

\[ y_i = \beta_0 + \beta_1 x_{1i} + \cdots + \beta_k x_{ki} + u_i, \]

alebo maticovo

\[ y = X\beta + u. \]

Multikolinearita znamená, že niektoré vysvetľujúce premenné v matici \(X\) sú silno lineárne závislé. Dokonalá multikolinearita nastáva vtedy, keď existuje nenulový vektor \(a\), pre ktorý

\[ Xa = 0. \]

Vtedy matica \(X'X\) nie je regulárna a OLS odhad

\[ \hat\beta = (X'X)^{-1}X'y \]

neexistuje.

V praxi častejšie pozorujeme nedokonalú, ale silnú multikolinearitu. Potom \(X'X\) je síce invertibilná, ale zle podmienená. Odhady existujú, no môžu byť veľmi nepresné.

Simulované dáta

Vytvoríme hlavný dátový súbor data_main, ktorý budeme používať v ďalších častiach.

Premenné:

  • y je závislá premenná,
  • x1, x2, x3 sú vysvetľujúce premenné,
  • x2 je konštruovaná tak, aby bola silno korelovaná s x1,
  • x3 je približne nezávislá od x1 a x2.
n <- 200

x1 <- rnorm(n)
x2 <- 0.95 * x1 + rnorm(n, sd = 0.15)
x3 <- rnorm(n)

u <- rnorm(n)

y <- 1 + 2*x1 - 1.5*x2 + 0.8*x3 + u

data_main <- data.frame(y = y, x1 = x1, x2 = x2, x3 = x3)

head(data_main)

2.Dôsledky multikolinearity pre OLS odhad

Pri multikolinearite OLS odhad zostáva nestranný za štandardných exogenitných predpokladov,

\[ E(u)=0, \]

ale jeho rozptyl môže byť veľký:

\[ Var(\hat\beta)=\sigma^2(X'X)^{-1}. \]

Ak sú stĺpce matice \(X\) takmer lineárne závislé, niektoré prvky matice \((X'X)^{-1}\) sú veľké.

X <- cbind(1, x1, x2, x3)
colnames(X) <- c("intercept", "x1", "x2", "x3")

XtX <- t(X) %*% X

XtX_inv <- solve(XtX)

XtX_inv
              intercept           x1           x2            x3
intercept  0.0050154322  0.001439290 -0.001476833 -0.0001822219
x1         0.0014392904  0.207599270 -0.213616763 -0.0015627618
x2        -0.0014768332 -0.213616763  0.225963071  0.0018298489
x3        -0.0001822219 -0.001562762  0.001829849  0.0054181885

To vedie k veľkým štandardným chybám, nízkym t-štatistikám a nestabilným odhadom \(\beta\) koeficientov. Pripomíname

\[var(\hat\beta_i) = \sigma^2 (X^TX)^{-1}_{ii}\]

model_ols <- lm(y ~ x1 + x2 + x3, data = data_main)
summary(model_ols)

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

Residuals:
     Min       1Q   Median       3Q      Max 
-2.53250 -0.67022  0.07388  0.70545  2.68627 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  0.97304    0.07277  13.372  < 2e-16 ***
x1           1.42700    0.46815   3.048  0.00262 ** 
x2          -0.94615    0.48842  -1.937  0.05416 .  
x3           0.83698    0.07563  11.067  < 2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.027 on 196 degrees of freedom
Multiple R-squared:  0.4671,    Adjusted R-squared:  0.459 
F-statistic: 57.27 on 3 and 196 DF,  p-value: < 2.2e-16

3. Multicollinearity detection and testing

3.1 Korelačná analýza vysvetľujúcich premenných

Najjednoduchší diagnostický krok je korelačná matica medzi vysvetľujúcimi premennými.

X <- data_main[, c("x1", "x2", "x3")]

cor_matrix <- cor(X)
round(cor_matrix, 4)
        x1      x2      x3
x1  1.0000  0.9863 -0.0302
x2  0.9863  1.0000 -0.0384
x3 -0.0302 -0.0384  1.0000

Vysoká absolútna hodnota korelácie, napríklad \(|r_{ij}| > 0.8\), môže indikovať problém multikolinearity. Sama o sebe však nestačí, pretože multikolinearita môže byť aj viacrozmerná: premenná môže byť lineárnou kombináciou viacerých ostatných premenných.

cor.test(data_main$x1, data_main$x2)

    Pearson's product-moment correlation

data:  data_main$x1 and data_main$x2
t = 84.039, df = 198, p-value < 2.2e-16
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
 0.9818871 0.9895986
sample estimates:
      cor 
0.9862705 
cor.test(data_main$x1, data_main$x3)

    Pearson's product-moment correlation

data:  data_main$x1 and data_main$x3
t = -0.4256, df = 198, p-value = 0.6709
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
 -0.1682678  0.1089655
sample estimates:
        cor 
-0.03023254 
cor.test(data_main$x2, data_main$x3)

    Pearson's product-moment correlation

data:  data_main$x2 and data_main$x3
t = -0.54143, df = 198, p-value = 0.5888
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
 -0.1762504  0.1008293
sample estimates:
       cor 
-0.0384496 
if (!requireNamespace("corrplot", quietly = TRUE)) {
  install.packages("corrplot")
}

library(corrplot)

corrplot(cor_matrix, method = "number", type = "upper")

3.2 Variance Inflation Factor

Pre premennú \(x_j\) definujeme

\[ VIF_j = \frac{1}{1-R_j^2}, \]

kde \(R_j^2\) je koeficient determinácie z pomocnej regresie, v ktorej je \(x_j\) vysvetľovaná ostatnými regresormi.

Ak je \(R_j^2\) blízko jednej, potom je \(VIF_j\) veľký a premenná \(x_j\) je silno lineárne vysvetliteľná ostatnými premennými.

install.packages(“car”) # run once if not installed

library(car)
# Variance Inflation Factors
vif_values <- vif(model)

vif_values
      x1       x2       x3 
36.74934 36.77011  1.00366 

Interpretation:

3.3 Číslo podmienenosti

Číslo podmienenosti je založené na vlastných číslach matice \(X'X\). Ak sú vlastné čísla veľmi rozdielne, matica je zle podmienená.

\[ \kappa = \sqrt{\frac{\lambda_{\max}}{\lambda_{\min}}}. \]

X_scaled <- scale(X)
eigen_values <- eigen(cor(X_scaled))$values

condition_number <- sqrt(max(eigen_values) / min(eigen_values))
eigen_values
[1] 1.98865618 0.99764855 0.01369527
condition_number
[1] 12.05021

Interpretácia čísla podmienenosti: - \(\kappa \approx 1\): žiadna multikolinearita, - \(\kappa > 10\): mierna multikolinearita, - \(\kappa > 30\): silná multikolinearita.

3.4 Farrar–Glauberov test

Farrar–Glauberov test skúma multikolinearitu pomocou korelačnej matice regresorov. Nech \(R\) je korelačná matica vysvetľujúcich premenných, \(n\) je počet pozorovaní a \(k\) počet regresorov.

Celkový \(\chi^2\) test

Testujeme nulovú hypotézu, že regresory nie sú navzájom korelované:

\[ H_0: R = I_k. \]

Testovacia štatistika je

\[ \chi^2 = -\left(n-1-\frac{2k+5}{6}\right)\ln |R|. \]

Stupne voľnosti sú

\[ df = \frac{k(k-1)}{2}. \]

fg_chi_square <- function(X) {
  X <- as.data.frame(X)
  R <- cor(X)
  n <- nrow(X)
  k <- ncol(X)

  chi_stat <- -(n - 1 - (2*k + 5)/6) * log(det(R))
  df <- k * (k - 1) / 2
  p_value <- 1 - pchisq(chi_stat, df = df)

  data.frame(
    chi_square = chi_stat,
    df = df,
    p_value = p_value,
    det_R = det(R)
  )
}

fg_chi <- fg_chi_square(X)
round(fg_chi, 4)

Malá p-hodnota znamená, že zamietame hypotézu \(R=I_k\), teda medzi vysvetľujúcimi premennými existuje štatisticky významná korelačná štruktúra.

4. Eliminácia problému multikolinearity

Multikolinearita nie je porušením exogenity. Nie je teda automaticky dôvodom na zamietnutie OLS modelu. Problém je hlavne inferenčný: veľké štandardné chyby a nestabilné individuálne koeficienty.

Možné riešenia:

  1. získať viac dát,
  2. odstrániť alebo spojiť silno korelované premenné,
  3. transformovať premenné,
  4. použiť teoretické obmedzenia,
  5. použiť regularizačné metódy, napríklad ridge regresiu.

4.1 Odstránenie jednej z korelovaných premenných

Ak sú dve premenné takmer rovnaké a ekonomická teória nevyžaduje obe, môžeme jednu z nich vynechať.

model_reduced <- lm(y ~ x1 + x3, data = data_main)

summary(model_ols)

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

Residuals:
     Min       1Q   Median       3Q      Max 
-2.53250 -0.67022  0.07388  0.70545  2.68627 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  0.97304    0.07277  13.372  < 2e-16 ***
x1           1.42700    0.46815   3.048  0.00262 ** 
x2          -0.94615    0.48842  -1.937  0.05416 .  
x3           0.83698    0.07563  11.067  < 2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.027 on 196 degrees of freedom
Multiple R-squared:  0.4671,    Adjusted R-squared:  0.459 
F-statistic: 57.27 on 3 and 196 DF,  p-value: < 2.2e-16
summary(model_reduced)

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

Residuals:
     Min       1Q   Median       3Q      Max 
-2.75173 -0.64762  0.09045  0.69569  2.69396 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  0.96686    0.07320  13.208  < 2e-16 ***
x1           0.53254    0.07780   6.845 9.46e-11 ***
x3           0.84464    0.07605  11.106  < 2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.035 on 197 degrees of freedom
Multiple R-squared:  0.4569,    Adjusted R-squared:  0.4514 
F-statistic: 82.87 on 2 and 197 DF,  p-value: < 2.2e-16

Pozor: vynechanie relevantnej premennej môže viesť k vychýleniu odhadov. Preto sa premenné nemajú vyhadzovať mechanicky iba podľa korelácie.

4.2 Ridge regression

Ridge regresia rieši problém nestability tým, že minimalizuje penalizovanú sumu štvorcov:

\[ \hat\beta^{ridge} = \arg\min_{\beta} \left[ \sum_{i=1}^n (y_i - x_i'\beta)^2 + \lambda \sum_{j=1}^k \beta_j^2 \right]. \]

Parameter \(\lambda \geq 0\) určuje silu penalizácie. Ak \(\lambda=0\), dostaneme OLS. Ak \(\lambda\) rastie, koeficienty sa zmenšujú smerom k nule.

Maticovo, pri centrovaných a škálovaných regresoroch,

\[ \hat\beta^{ridge} = (X'X+\lambda I)^{-1}X'y. \]

Ridge znižuje rozptyl odhadov za cenu určitého vychýlenia. Preto je užitočná najmä pri predikcii alebo pri veľmi nestabilných OLS koeficientoch.

if (!requireNamespace("glmnet", quietly = TRUE)) {
  install.packages("glmnet")
}

library(glmnet)

X_mat <- model.matrix(y ~ x1 + x2 + x3, data = data_main)[, -1]
y_vec <- data_main$y

ridge_cv <- cv.glmnet(
  x = X_mat,
  y = y_vec,
  alpha = 0,
  standardize = TRUE
)

ridge_cv$lambda.min
[1] 0.07977274
ridge_cv$lambda.1se
[1] 0.8164987
coef(ridge_cv, s = "lambda.min")
4 x 1 sparse Matrix of class "dgCMatrix"
            lambda.min
(Intercept) 0.96790458
x1          0.47731517
x2          0.02760042
x3          0.79830075
plot(ridge_cv)

Porovnajme OLS a ridge koeficienty.

ols_coef <- coef(model_ols)

ridge_coef <- as.matrix(coef(ridge_cv, s = "lambda.min"))

comparison <- data.frame(
  coefficient = rownames(ridge_coef),
  OLS = as.numeric(ols_coef[rownames(ridge_coef)]),
  Ridge = as.numeric(ridge_coef[, 1])
)

round_numeric(comparison, 4)

Ridge regresia typicky nemení cieľ z inferencie na jednotlivé nepenalizované parametre, ale pomáha stabilizovať odhady a zlepšiť predikčnú výkonnosť v prítomnosti silnej multikolinearity.

4.3 Predikčné porovnanie OLS a ridge

set.seed(321)

train_id <- sample(1:nrow(data_main), size = 0.7*nrow(data_main))

train <- data_main[train_id, ]
test <- data_main[-train_id, ]

ols_train <- lm(y ~ x1 + x2 + x3, data = train)

X_train <- model.matrix(y ~ x1 + x2 + x3, data = train)[, -1]
y_train <- train$y

X_test <- model.matrix(y ~ x1 + x2 + x3, data = test)[, -1]
y_test <- test$y

ridge_train_cv <- cv.glmnet(
  x = X_train,
  y = y_train,
  alpha = 0,
  standardize = TRUE
)

pred_ols <- predict(ols_train, newdata = test)
pred_ridge <- predict(ridge_train_cv, newx = X_test, s = "lambda.min")

mse_ols <- mean((y_test - pred_ols)^2)
mse_ridge <- mean((y_test - pred_ridge)^2)

data.frame(
  model = c("OLS", "Ridge"),
  test_MSE = c(mse_ols, as.numeric(mse_ridge))
)

Zhrnutie

Multikolinearita znamená silnú lineárnu závislosť medzi vysvetľujúcimi premennými. Pri dokonalej multikolinearite OLS odhad neexistuje. Pri silnej, ale nedokonalej multikolinearite OLS existuje, no štandardné chyby môžu byť veľké a odhady nestabilné.

V praxi je vhodné použiť viacero diagnostík: korelačnú maticu, VIF, číslo podmienenosti a Farrar–Glauberov test. Pri riešení problému treba zohľadniť ekonomickú teóriu. Ridge regresia je vhodná najmä vtedy, keď je cieľom stabilná predikcia.

LS0tCnRpdGxlOiAiTXVsdGlrb2xpbmVhcml0YSB2IGxpbmXDoXJuZWogcmVncmVzaWkiCmF1dGhvcjogIkVjb25vbWV0cmljcyBHUFQiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSkKc2V0LnNlZWQoMTIzKQpgYGAKCiMgMS4gTXVsdGlrb2xpbmVhcml0YSDigJMgZGVmaW7DrWNpYQoKVXZhxb51am1lIGxpbmXDoXJueSByZWdyZXNuw70gbW9kZWwKClxbCnlfaSA9IFxiZXRhXzAgKyBcYmV0YV8xIHhfezFpfSArIFxjZG90cyArIFxiZXRhX2sgeF97a2l9ICsgdV9pLApcXQoKYWxlYm8gbWF0aWNvdm8KClxbCnkgPSBYXGJldGEgKyB1LgpcXQoKTXVsdGlrb2xpbmVhcml0YSB6bmFtZW7DoSwgxb5lIG5pZWt0b3LDqSB2eXN2ZXTEvnVqw7pjZSBwcmVtZW5uw6kgdiBtYXRpY2kgXChYXCkgc8O6IHNpbG5vIGxpbmXDoXJuZSB6w6F2aXNsw6kuIERva29uYWzDoSBtdWx0aWtvbGluZWFyaXRhIG5hc3TDoXZhIHZ0ZWR5LCBrZcSPIGV4aXN0dWplIG5lbnVsb3bDvSB2ZWt0b3IgXChhXCksIHByZSBrdG9yw70KClxbClhhID0gMC4KXF0KClZ0ZWR5IG1hdGljYSBcKFgnWFwpIG5pZSBqZSByZWd1bMOhcm5hIGEgT0xTIG9kaGFkCgpcWwpcaGF0XGJldGEgPSAoWCdYKV57LTF9WCd5ClxdCgpuZWV4aXN0dWplLgoKViBwcmF4aSDEjWFzdGVqxaFpZSBwb3pvcnVqZW1lIG5lZG9rb25hbMO6LCBhbGUgc2lsbsO6IG11bHRpa29saW5lYXJpdHUuIFBvdG9tIFwoWCdYXCkgamUgc8OtY2UgaW52ZXJ0aWJpbG7DoSwgYWxlIHpsZSBwb2RtaWVuZW7DoS4gT2RoYWR5IGV4aXN0dWrDuiwgbm8gbcO0xb51IGJ5xaUgdmXEvm1pIG5lcHJlc27DqS4KCiMjIFNpbXVsb3ZhbsOpIGTDoXRhCgpWeXR2b3LDrW1lIGhsYXZuw70gZMOhdG92w70gc8O6Ym9yIGBkYXRhX21haW5gLCBrdG9yw70gYnVkZW1lIHBvdcW+w612YcWlIHYgxI9hbMWhw61jaCDEjWFzdGlhY2guCgpQcmVtZW5uw6k6CgotIGB5YCBqZSB6w6F2aXNsw6EgcHJlbWVubsOhLAotIGB4MWAsIGB4MmAsIGB4M2Agc8O6IHZ5c3ZldMS+dWrDumNlIHByZW1lbm7DqSwKLSBgeDJgIGplIGtvbsWhdHJ1b3ZhbsOhIHRhaywgYWJ5IGJvbGEgc2lsbm8ga29yZWxvdmFuw6EgcyBgeDFgLAotIGB4M2AgamUgcHJpYmxpxb5uZSBuZXrDoXZpc2zDoSBvZCBgeDFgIGEgYHgyYC4KCmBgYHtyIGRhdGEtbWFpbn0KbiA8LSAyMDAKCngxIDwtIHJub3JtKG4pCngyIDwtIDAuOTUgKiB4MSArIHJub3JtKG4sIHNkID0gMC4xNSkKeDMgPC0gcm5vcm0obikKCnUgPC0gcm5vcm0obikKCnkgPC0gMSArIDIqeDEgLSAxLjUqeDIgKyAwLjgqeDMgKyB1CgpkYXRhX21haW4gPC0gZGF0YS5mcmFtZSh5ID0geSwgeDEgPSB4MSwgeDIgPSB4MiwgeDMgPSB4MykKCmhlYWQoZGF0YV9tYWluKQpgYGAKCiMgMi5Ew7RzbGVka3kgbXVsdGlrb2xpbmVhcml0eSBwcmUgT0xTIG9kaGFkCgpQcmkgbXVsdGlrb2xpbmVhcml0ZSBPTFMgb2RoYWQgem9zdMOhdmEgbmVzdHJhbm7DvSB6YSDFoXRhbmRhcmRuw71jaCBleG9nZW5pdG7DvWNoIHByZWRwb2tsYWRvdiwKClxbCkUodSk9MCwKXF0KCmFsZSBqZWhvIHJvenB0eWwgbcO0xb5lIGJ5xaUgdmXEvmvDvToKClxbClZhcihcaGF0XGJldGEpPVxzaWdtYV4yKFgnWCleey0xfS4KXF0KCkFrIHPDuiBzdMS6cGNlIG1hdGljZSBcKFhcKSB0YWttZXIgbGluZcOhcm5lIHrDoXZpc2zDqSwgbmlla3RvcsOpIHBydmt5IG1hdGljZSBcKChYJ1gpXnstMX1cKSBzw7ogdmXEvmvDqS4KCmBgYHtyfQpYIDwtIGNiaW5kKDEsIHgxLCB4MiwgeDMpCmNvbG5hbWVzKFgpIDwtIGMoImludGVyY2VwdCIsICJ4MSIsICJ4MiIsICJ4MyIpCgpYdFggPC0gdChYKSAlKiUgWAoKWHRYX2ludiA8LSBzb2x2ZShYdFgpCgpYdFhfaW52CmBgYAoKCgoKVG8gdmVkaWUgayB2ZcS+a8O9bSDFoXRhbmRhcmRuw71tIGNoeWLDoW0sIG7DrXpreW0gdC3FoXRhdGlzdGlrw6FtIGEgbmVzdGFiaWxuw71tIG9kaGFkb20gJFxiZXRhJCBrb2VmaWNpZW50b3YuIFByaXBvbcOtbmFtZQoKJCR2YXIoXGhhdFxiZXRhX2kpID0gXHNpZ21hXjIgKFheVFgpXnstMX1fe2lpfSQkCgpgYGB7ciBvbHMtbWFpbn0KbW9kZWxfb2xzIDwtIGxtKHkgfiB4MSArIHgyICsgeDMsIGRhdGEgPSBkYXRhX21haW4pCnN1bW1hcnkobW9kZWxfb2xzKQpgYGAKCgoKIyAzLiBNdWx0aWNvbGxpbmVhcml0eSBkZXRlY3Rpb24gYW5kIHRlc3RpbmcKCiMjIDMuMSBLb3JlbGHEjW7DoSBhbmFsw716YSB2eXN2ZXTEvnVqw7pjaWNoIHByZW1lbm7DvWNoCgpOYWpqZWRub2R1Y2jFocOtIGRpYWdub3N0aWNrw70ga3JvayBqZSBrb3JlbGHEjW7DoSBtYXRpY2EgbWVkemkgdnlzdmV0xL51asO6Y2ltaSBwcmVtZW5uw71taS4KCmBgYHtyIGNvcnJlbGF0aW9uLW1hdHJpeH0KWCA8LSBkYXRhX21haW5bLCBjKCJ4MSIsICJ4MiIsICJ4MyIpXQoKY29yX21hdHJpeCA8LSBjb3IoWCkKcm91bmQoY29yX21hdHJpeCwgNCkKYGBgCgpWeXNva8OhIGFic29sw7p0bmEgaG9kbm90YSBrb3JlbMOhY2llLCBuYXByw61rbGFkIFwofHJfe2lqfXwgPiAwLjhcKSwgbcO0xb5lIGluZGlrb3ZhxaUgcHJvYmzDqW0gbXVsdGlrb2xpbmVhcml0eS4gU2FtYSBvIHNlYmUgdsWhYWsgbmVzdGHEjcOtLCBwcmV0b8W+ZSBtdWx0aWtvbGluZWFyaXRhIG3DtMW+ZSBiecWlIGFqIHZpYWNyb3ptZXJuw6E6IHByZW1lbm7DoSBtw7TFvmUgYnnFpSBsaW5lw6Fybm91IGtvbWJpbsOhY2lvdSB2aWFjZXLDvWNoIG9zdGF0bsO9Y2ggcHJlbWVubsO9Y2guCgpgYGB7ciBjb3JyZWxhdGlvbi10ZXN0c30KY29yLnRlc3QoZGF0YV9tYWluJHgxLCBkYXRhX21haW4keDIpCmNvci50ZXN0KGRhdGFfbWFpbiR4MSwgZGF0YV9tYWluJHgzKQpjb3IudGVzdChkYXRhX21haW4keDIsIGRhdGFfbWFpbiR4MykKYGBgCgpgYGB7ciBjb3JyZWxhdGlvbi1wbG90fQppZiAoIXJlcXVpcmVOYW1lc3BhY2UoImNvcnJwbG90IiwgcXVpZXRseSA9IFRSVUUpKSB7CiAgaW5zdGFsbC5wYWNrYWdlcygiY29ycnBsb3QiKQp9CgpsaWJyYXJ5KGNvcnJwbG90KQoKY29ycnBsb3QoY29yX21hdHJpeCwgbWV0aG9kID0gIm51bWJlciIsIHR5cGUgPSAidXBwZXIiKQpgYGAKCiMjIDMuMiBWYXJpYW5jZSBJbmZsYXRpb24gRmFjdG9yCgpQcmUgcHJlbWVubsO6IFwoeF9qXCkgZGVmaW51amVtZQoKXFsKVklGX2ogPSBcZnJhY3sxfXsxLVJfal4yfSwKXF0KCmtkZSBcKFJfal4yXCkgamUga29lZmljaWVudCBkZXRlcm1pbsOhY2llIHogcG9tb2NuZWogcmVncmVzaWUsIHYga3RvcmVqIGplIFwoeF9qXCkgdnlzdmV0xL5vdmFuw6Egb3N0YXRuw71taSByZWdyZXNvcm1pLgoKQWsgamUgXChSX2peMlwpIGJsw616a28gamVkbmVqLCBwb3RvbSBqZSBcKFZJRl9qXCkgdmXEvmvDvSBhIHByZW1lbm7DoSBcKHhfalwpIGplIHNpbG5vIGxpbmXDoXJuZSB2eXN2ZXRsaXRlxL5uw6Egb3N0YXRuw71taSBwcmVtZW5uw71taS4KCiMgaW5zdGFsbC5wYWNrYWdlcygiY2FyIikgICMgcnVuIG9uY2UgaWYgbm90IGluc3RhbGxlZAoKCmBgYHtyfQpsaWJyYXJ5KGNhcikKIyBWYXJpYW5jZSBJbmZsYXRpb24gRmFjdG9ycwp2aWZfdmFsdWVzIDwtIHZpZihtb2RlbCkKCnZpZl92YWx1ZXMKYGBgCgoqKkludGVycHJldGF0aW9uOioqCgotIFwoVklGX2ogPSAxXCk6IMW+aWFkbmEgbXVsdGlrb2xpbmVhcml0YSwKLSBcKDEgPCBWSUZfaiA8IDVcKTogbWllcm5hIG11bHRpa29saW5lYXJpdGEKLSBcKFZJRl9qIFxnZXEgNVwpOiBzaWxuw6EgbXVsdGlrb2xpbmVhcml0YSAobmlla3RvcsOtIGF1dG9yaSBwb3XFvsOtdmFqw7ogcHLDrXNuZWrFocOtIHByYWggXChWSUZfaiBcZ2VxIDEwXCkpLgoKIyMgMy4zIMSMw61zbG8gcG9kbWllbmVub3N0aQoKxIzDrXNsbyBwb2RtaWVuZW5vc3RpIGplIHphbG/FvmVuw6kgbmEgdmxhc3Ruw71jaCDEjcOtc2xhY2ggbWF0aWNlIFwoWCdYXCkuIEFrIHPDuiB2bGFzdG7DqSDEjcOtc2xhIHZlxL5taSByb3pkaWVsbmUsIG1hdGljYSBqZSB6bGUgcG9kbWllbmVuw6EuCgpcWwpca2FwcGEgPSBcc3FydHtcZnJhY3tcbGFtYmRhX3tcbWF4fX17XGxhbWJkYV97XG1pbn19fS4KXF0KCmBgYHtyIGNvbmRpdGlvbi1udW1iZXJ9Clhfc2NhbGVkIDwtIHNjYWxlKFgpCmVpZ2VuX3ZhbHVlcyA8LSBlaWdlbihjb3IoWF9zY2FsZWQpKSR2YWx1ZXMKCmNvbmRpdGlvbl9udW1iZXIgPC0gc3FydChtYXgoZWlnZW5fdmFsdWVzKSAvIG1pbihlaWdlbl92YWx1ZXMpKQplaWdlbl92YWx1ZXMKY29uZGl0aW9uX251bWJlcgpgYGAKICAKKipJbnRlcnByZXTDoWNpYSDEjcOtc2xhIHBvZG1pZW5lbm9zdGk6KiogCi0gXChca2FwcGEgXGFwcHJveCAxXCk6IMW+aWFkbmEgbXVsdGlrb2xpbmVhcml0YSwKLSBcKFxrYXBwYSA+IDEwXCk6IG1pZXJuYSBtdWx0aWtvbGluZWFyaXRhLAotIFwoXGthcHBhID4gMzBcKTogc2lsbsOhIG11bHRpa29saW5lYXJpdGEuCgogIAojIyAzLjQgRmFycmFy4oCTR2xhdWJlcm92IHRlc3QKCkZhcnJhcuKAk0dsYXViZXJvdiB0ZXN0IHNrw7ptYSBtdWx0aWtvbGluZWFyaXR1IHBvbW9jb3Uga29yZWxhxI1uZWogbWF0aWNlIHJlZ3Jlc29yb3YuIE5lY2ggXChSXCkgamUga29yZWxhxI1uw6EgbWF0aWNhIHZ5c3ZldMS+dWrDumNpY2ggcHJlbWVubsO9Y2gsIFwoblwpIGplIHBvxI1ldCBwb3pvcm92YW7DrSBhIFwoa1wpIHBvxI1ldCByZWdyZXNvcm92LgoKIyMjIENlbGtvdsO9IFwoXGNoaV4yXCkgdGVzdAoKVGVzdHVqZW1lIG51bG92w7ogaHlwb3TDqXp1LCDFvmUgcmVncmVzb3J5IG5pZSBzw7ogbmF2esOham9tIGtvcmVsb3ZhbsOpOgoKXFsKSF8wOiBSID0gSV9rLgpcXQoKVGVzdG92YWNpYSDFoXRhdGlzdGlrYSBqZQoKXFsKXGNoaV4yID0KLVxsZWZ0KG4tMS1cZnJhY3syays1fXs2fVxyaWdodClcbG4gfFJ8LgpcXQoKU3R1cG5lIHZvxL5ub3N0aSBzw7oKClxbCmRmID0gXGZyYWN7ayhrLTEpfXsyfS4KXF0KCmBgYHtyIGZhcnJhci1nbGF1YmVyLWNoaS1zcXVhcmV9CmZnX2NoaV9zcXVhcmUgPC0gZnVuY3Rpb24oWCkgewogIFggPC0gYXMuZGF0YS5mcmFtZShYKQogIFIgPC0gY29yKFgpCiAgbiA8LSBucm93KFgpCiAgayA8LSBuY29sKFgpCgogIGNoaV9zdGF0IDwtIC0obiAtIDEgLSAoMiprICsgNSkvNikgKiBsb2coZGV0KFIpKQogIGRmIDwtIGsgKiAoayAtIDEpIC8gMgogIHBfdmFsdWUgPC0gMSAtIHBjaGlzcShjaGlfc3RhdCwgZGYgPSBkZikKCiAgZGF0YS5mcmFtZSgKICAgIGNoaV9zcXVhcmUgPSBjaGlfc3RhdCwKICAgIGRmID0gZGYsCiAgICBwX3ZhbHVlID0gcF92YWx1ZSwKICAgIGRldF9SID0gZGV0KFIpCiAgKQp9CgpmZ19jaGkgPC0gZmdfY2hpX3NxdWFyZShYKQpyb3VuZChmZ19jaGksIDQpCmBgYAoKTWFsw6EgcC1ob2Rub3RhIHpuYW1lbsOhLCDFvmUgemFtaWV0YW1lIGh5cG90w6l6dSBcKFI9SV9rXCksIHRlZGEgbWVkemkgdnlzdmV0xL51asO6Y2ltaSBwcmVtZW5uw71taSBleGlzdHVqZSDFoXRhdGlzdGlja3kgdsO9em5hbW7DoSBrb3JlbGHEjW7DoSDFoXRydWt0w7pyYS4KCgoKIyA0LiBFbGltaW7DoWNpYSBwcm9ibMOpbXUgbXVsdGlrb2xpbmVhcml0eQoKTXVsdGlrb2xpbmVhcml0YSBuaWUgamUgcG9ydcWhZW7DrW0gZXhvZ2VuaXR5LiBOaWUgamUgdGVkYSBhdXRvbWF0aWNreSBkw7R2b2RvbSBuYSB6YW1pZXRudXRpZSBPTFMgbW9kZWx1LiBQcm9ibMOpbSBqZSBobGF2bmUgaW5mZXJlbsSNbsO9OiB2ZcS+a8OpIMWhdGFuZGFyZG7DqSBjaHlieSBhIG5lc3RhYmlsbsOpIGluZGl2aWR1w6FsbmUga29lZmljaWVudHkuCgpNb8W+bsOpIHJpZcWhZW5pYToKCjEuIHrDrXNrYcWlIHZpYWMgZMOhdCwKMi4gb2RzdHLDoW5pxaUgYWxlYm8gc3BvamnFpSBzaWxubyBrb3JlbG92YW7DqSBwcmVtZW5uw6ksCjMuIHRyYW5zZm9ybW92YcWlIHByZW1lbm7DqSwKNC4gcG91xb5pxaUgdGVvcmV0aWNrw6kgb2JtZWR6ZW5pYSwKNS4gcG91xb5pxaUgcmVndWxhcml6YcSNbsOpIG1ldMOzZHksIG5hcHLDrWtsYWQgcmlkZ2UgcmVncmVzaXUuCgojIyA0LjEgT2RzdHLDoW5lbmllIGplZG5laiB6IGtvcmVsb3ZhbsO9Y2ggcHJlbWVubsO9Y2gKCkFrIHPDuiBkdmUgcHJlbWVubsOpIHRha21lciByb3ZuYWvDqSBhIGVrb25vbWlja8OhIHRlw7NyaWEgbmV2ecW+YWR1amUgb2JlLCBtw7TFvmVtZSBqZWRudSB6IG5pY2ggdnluZWNoYcWlLgoKYGBge3IgcmVkdWNlZC1tb2RlbH0KbW9kZWxfcmVkdWNlZCA8LSBsbSh5IH4geDEgKyB4MywgZGF0YSA9IGRhdGFfbWFpbikKCnN1bW1hcnkobW9kZWxfb2xzKQpzdW1tYXJ5KG1vZGVsX3JlZHVjZWQpCmBgYAoKUG96b3I6IHZ5bmVjaGFuaWUgcmVsZXZhbnRuZWogcHJlbWVubmVqIG3DtMW+ZSB2aWVzxaUgayB2eWNow71sZW5pdSBvZGhhZG92LiBQcmV0byBzYSBwcmVtZW5uw6kgbmVtYWrDuiB2eWhhZHpvdmHFpSBtZWNoYW5pY2t5IGliYSBwb2TEvmEga29yZWzDoWNpZS4KCiMjIDQuMiBSaWRnZSByZWdyZXNzaW9uCgpSaWRnZSByZWdyZXNpYSByaWXFoWkgcHJvYmzDqW0gbmVzdGFiaWxpdHkgdMO9bSwgxb5lIG1pbmltYWxpenVqZSBwZW5hbGl6b3ZhbsO6IHN1bXUgxaF0dm9yY292OgoKXFsKXGhhdFxiZXRhXntyaWRnZX0KPQpcYXJnXG1pbl97XGJldGF9ClxsZWZ0Wwpcc3VtX3tpPTF9Xm4gKHlfaSAtIHhfaSdcYmV0YSleMgorClxsYW1iZGEgXHN1bV97aj0xfV5rIFxiZXRhX2peMgpccmlnaHRdLgpcXQoKUGFyYW1ldGVyIFwoXGxhbWJkYSBcZ2VxIDBcKSB1csSNdWplIHNpbHUgcGVuYWxpesOhY2llLiBBayBcKFxsYW1iZGE9MFwpLCBkb3N0YW5lbWUgT0xTLiBBayBcKFxsYW1iZGFcKSByYXN0aWUsIGtvZWZpY2llbnR5IHNhIHptZW7FoXVqw7ogc21lcm9tIGsgbnVsZS4KCk1hdGljb3ZvLCBwcmkgY2VudHJvdmFuw71jaCBhIMWha8OhbG92YW7DvWNoIHJlZ3Jlc29yb2NoLAoKXFsKXGhhdFxiZXRhXntyaWRnZX0KPQooWCdYK1xsYW1iZGEgSSleey0xfVgneS4KXF0KClJpZGdlIHpuacW+dWplIHJvenB0eWwgb2RoYWRvdiB6YSBjZW51IHVyxI1pdMOpaG8gdnljaMO9bGVuaWEuIFByZXRvIGplIHXFvml0b8SNbsOhIG5ham3DpCBwcmkgcHJlZGlrY2lpIGFsZWJvIHByaSB2ZcS+bWkgbmVzdGFiaWxuw71jaCBPTFMga29lZmljaWVudG9jaC4KCmBgYHtyIHJpZGdlLXJlZ3Jlc3Npb259CmlmICghcmVxdWlyZU5hbWVzcGFjZSgiZ2xtbmV0IiwgcXVpZXRseSA9IFRSVUUpKSB7CiAgaW5zdGFsbC5wYWNrYWdlcygiZ2xtbmV0IikKfQoKbGlicmFyeShnbG1uZXQpCgpYX21hdCA8LSBtb2RlbC5tYXRyaXgoeSB+IHgxICsgeDIgKyB4MywgZGF0YSA9IGRhdGFfbWFpbilbLCAtMV0KeV92ZWMgPC0gZGF0YV9tYWluJHkKCnJpZGdlX2N2IDwtIGN2LmdsbW5ldCgKICB4ID0gWF9tYXQsCiAgeSA9IHlfdmVjLAogIGFscGhhID0gMCwKICBzdGFuZGFyZGl6ZSA9IFRSVUUKKQoKcmlkZ2VfY3YkbGFtYmRhLm1pbgpyaWRnZV9jdiRsYW1iZGEuMXNlCmBgYAoKYGBge3IgcmlkZ2UtY29lZmZpY2llbnRzfQpjb2VmKHJpZGdlX2N2LCBzID0gImxhbWJkYS5taW4iKQpgYGAKCmBgYHtyIHJpZGdlLXBsb3R9CnBsb3QocmlkZ2VfY3YpCmBgYAoKUG9yb3ZuYWptZSBPTFMgYSByaWRnZSBrb2VmaWNpZW50eS4KCmBgYHtyIGNvbXBhcmUtb2xzLXJpZGdlfQpvbHNfY29lZiA8LSBjb2VmKG1vZGVsX29scykKCnJpZGdlX2NvZWYgPC0gYXMubWF0cml4KGNvZWYocmlkZ2VfY3YsIHMgPSAibGFtYmRhLm1pbiIpKQoKY29tcGFyaXNvbiA8LSBkYXRhLmZyYW1lKAogIGNvZWZmaWNpZW50ID0gcm93bmFtZXMocmlkZ2VfY29lZiksCiAgT0xTID0gYXMubnVtZXJpYyhvbHNfY29lZltyb3duYW1lcyhyaWRnZV9jb2VmKV0pLAogIFJpZGdlID0gYXMubnVtZXJpYyhyaWRnZV9jb2VmWywgMV0pCikKCnJvdW5kX251bWVyaWMoY29tcGFyaXNvbiwgNCkKYGBgCgpSaWRnZSByZWdyZXNpYSB0eXBpY2t5IG5lbWVuw60gY2llxL4geiBpbmZlcmVuY2llIG5hIGplZG5vdGxpdsOpIG5lcGVuYWxpem92YW7DqSBwYXJhbWV0cmUsIGFsZSBwb23DoWhhIHN0YWJpbGl6b3ZhxaUgb2RoYWR5IGEgemxlcMWhacWlIHByZWRpa8SNbsO6IHbDvWtvbm5vc8WlIHYgcHLDrXRvbW5vc3RpIHNpbG5laiBtdWx0aWtvbGluZWFyaXR5LgoKIyMgNC4zIFByZWRpa8SNbsOpIHBvcm92bmFuaWUgT0xTIGEgcmlkZ2UKCmBgYHtyIHByZWRpY3Rpb24tY29tcGFyaXNvbn0Kc2V0LnNlZWQoMzIxKQoKdHJhaW5faWQgPC0gc2FtcGxlKDE6bnJvdyhkYXRhX21haW4pLCBzaXplID0gMC43Km5yb3coZGF0YV9tYWluKSkKCnRyYWluIDwtIGRhdGFfbWFpblt0cmFpbl9pZCwgXQp0ZXN0IDwtIGRhdGFfbWFpblstdHJhaW5faWQsIF0KCm9sc190cmFpbiA8LSBsbSh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gdHJhaW4pCgpYX3RyYWluIDwtIG1vZGVsLm1hdHJpeCh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gdHJhaW4pWywgLTFdCnlfdHJhaW4gPC0gdHJhaW4keQoKWF90ZXN0IDwtIG1vZGVsLm1hdHJpeCh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gdGVzdClbLCAtMV0KeV90ZXN0IDwtIHRlc3QkeQoKcmlkZ2VfdHJhaW5fY3YgPC0gY3YuZ2xtbmV0KAogIHggPSBYX3RyYWluLAogIHkgPSB5X3RyYWluLAogIGFscGhhID0gMCwKICBzdGFuZGFyZGl6ZSA9IFRSVUUKKQoKcHJlZF9vbHMgPC0gcHJlZGljdChvbHNfdHJhaW4sIG5ld2RhdGEgPSB0ZXN0KQpwcmVkX3JpZGdlIDwtIHByZWRpY3QocmlkZ2VfdHJhaW5fY3YsIG5ld3ggPSBYX3Rlc3QsIHMgPSAibGFtYmRhLm1pbiIpCgptc2Vfb2xzIDwtIG1lYW4oKHlfdGVzdCAtIHByZWRfb2xzKV4yKQptc2VfcmlkZ2UgPC0gbWVhbigoeV90ZXN0IC0gcHJlZF9yaWRnZSleMikKCmRhdGEuZnJhbWUoCiAgbW9kZWwgPSBjKCJPTFMiLCAiUmlkZ2UiKSwKICB0ZXN0X01TRSA9IGMobXNlX29scywgYXMubnVtZXJpYyhtc2VfcmlkZ2UpKQopCmBgYAoKIyBaaHJudXRpZQoKTXVsdGlrb2xpbmVhcml0YSB6bmFtZW7DoSBzaWxuw7ogbGluZcOhcm51IHrDoXZpc2xvc8WlIG1lZHppIHZ5c3ZldMS+dWrDumNpbWkgcHJlbWVubsO9bWkuIFByaSBkb2tvbmFsZWogbXVsdGlrb2xpbmVhcml0ZSBPTFMgb2RoYWQgbmVleGlzdHVqZS4gUHJpIHNpbG5laiwgYWxlIG5lZG9rb25hbGVqIG11bHRpa29saW5lYXJpdGUgT0xTIGV4aXN0dWplLCBubyDFoXRhbmRhcmRuw6kgY2h5YnkgbcO0xb51IGJ5xaUgdmXEvmvDqSBhIG9kaGFkeSBuZXN0YWJpbG7DqS4KClYgcHJheGkgamUgdmhvZG7DqSBwb3XFvmnFpSB2aWFjZXJvIGRpYWdub3N0w61rOiBrb3JlbGHEjW7DuiBtYXRpY3UsIFZJRiwgxI3DrXNsbyBwb2RtaWVuZW5vc3RpIGEgRmFycmFy4oCTR2xhdWJlcm92IHRlc3QuIFByaSByaWXFoWVuw60gcHJvYmzDqW11IHRyZWJhIHpvaMS+YWRuacWlIGVrb25vbWlja8O6IHRlw7NyaXUuIFJpZGdlIHJlZ3Jlc2lhIGplIHZob2Ruw6EgbmFqbcOkIHZ0ZWR5LCBrZcSPIGplIGNpZcS+b20gc3RhYmlsbsOhIHByZWRpa2NpYS4K