Goals:
- Illustrate why naive implementations of model selection using Lasso
are problematic
Introducing the data
The Application Notebook builds on the dataset that is kindly
provided in the hdm
package. The data was used in Chernozhukov
and Hansen (2004). Their paper investigates the effect of
participation in the employer-sponsored 401(k) retirement savings plan
(p401
) on net assets (net_tfa
). Since then the
data was used to showcase many new methods. It is not the most
comprehensive dataset with basically ten
covariates/regressors/predictors:
age: age
db: defined benefit pension
educ: education (in years)
fsize: family size
hown: home owner
inc: income (in US $)
male: male
marr: married
pira: participation in individual retirement account
(IRA)
twoearn: two earners
However, it is publicly available and the relatively few covariates
ensure that the programs do not run too long.
# To install the causalDML package uncomment the following two lines
# library(devtools)
# install_github(repo="MCKnaus/causalDML")
# Load the packages required for later
library(hdm)
library(tidyverse)
library(causalDML)
library(grf)
library(estimatr)
set.seed(1234) # for replicability
data(pension)
# Outcome
Y = pension$net_tfa
# Treatment
W = pension$p401
# Create main effects matrix
X = model.matrix(~ 0 + age + db + educ + fsize + hown + inc + male + marr + pira + twoearn, data = pension)
Hand-coded Double Selection
To understand the procedure of Double Selection, we proceed step by
step using only the main effects for simplicity:
- Select variables in the outcome regression without the
treatment:
# Select variables in outcome regression
sel_y = rlasso(X,Y)
# Which variables are selected?
which(sel_y$beta != 0)
age fsize hown inc pira twoearn
1 4 5 6 9 10
- Select variables in the treatment regression:
# Select variables in treatment regression
sel_w = rlasso(X,W)
which(sel_w$beta != 0)
db hown inc pira twoearn
2 5 6 9 10
Note that variable db is now selected which was not selected
in step one.
- Use the union of the in total seven selected variables to run a
standard OLS regression with robust standard errors:
# Double selection
X_sel_union = X[,sel_y$beta != 0 | sel_w$beta != 0]
ds_hand = lm_robust(Y ~ W + X_sel_union)
summary(ds_hand)
Call:
lm_robust(formula = Y ~ W + X_sel_union)
Standard error type: HC2
Coefficients:
Estimate Std. Error t value Pr(>|t|) CI Lower CI Upper DF
(Intercept) -4.268e+04 3298.4608 -12.9386 5.530e-38 -4.914e+04 -36211.86 9906
W 1.158e+04 1811.3259 6.3953 1.675e-10 8.033e+03 15134.49 9906
X_sel_unionage 6.733e+02 58.9094 11.4298 4.579e-30 5.578e+02 788.80 9906
X_sel_uniondb -5.465e+03 1359.2053 -4.0208 5.844e-05 -8.129e+03 -2800.73 9906
X_sel_unionfsize -6.872e+02 301.2848 -2.2810 2.257e-02 -1.278e+03 -96.65 9906
X_sel_unionhown 9.267e+02 950.5966 0.9749 3.296e-01 -9.366e+02 2790.08 9906
X_sel_unioninc 8.904e-01 0.1019 8.7390 2.733e-18 6.907e-01 1.09 9906
X_sel_unionpira 2.849e+04 1819.6634 15.6541 1.400e-54 2.492e+04 32052.14 9906
X_sel_uniontwoearn -1.866e+04 2315.0448 -8.0607 8.465e-16 -2.320e+04 -14122.83 9906
Multiple R-squared: 0.2346 , Adjusted R-squared: 0.234
F-statistic: 135 on 8 and 9906 DF, p-value: < 2.2e-16
Double Selection with hdm
package
In practice we want to have one function that does everything at
once. This is the rlassoEffect
command of the
hdm
package.
ds1 = rlassoEffect(X,Y,W)
summary(ds1)
[1] "Estimates and significance testing of the effect of target variables"
Estimate. Std. Error t value Pr(>|t|)
d1 11584 1809 6.405 1.51e-10 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
It produces the same point estimate as the hand-coded version:
all.equal(as.numeric(ds1$alpha),as.numeric(ds_hand$coefficients[2]))
[1] TRUE
Only the standard error differs slightly because of different
defaults. If you do not like this, applying se_type = "HC1
in the lm_robust()
function replicates the standard error
of rlassoEffect()
.
More flexible dictionaries
We can check whether more flexible covariate matrices provide
different results:
X2
with 88 variables: Second order polynomials of
the continuous variables age, education and income as well as second
order interactions of all variables
X3
with 567 variables: Third order polynomials of
the continuous variables age, education and income as well as third
order interactions of all variables
X2 = model.matrix(~ 0 + (fsize + marr + twoearn + db + pira + hown + male +
poly(age,2) + poly(educ,2) + poly(inc,2))^2, data = pension)
X3 = model.matrix(~ 0 + (fsize + marr + twoearn + db + pira + hown + male +
poly(age,3) + poly(educ,3) + poly(inc,3))^3, data = pension)
Indeed, the effects are by more than $2000 Dollars higher, but going
from two to three order terms makes basically no difference:
ds2 = rlassoEffect(X2,Y,W)
summary(ds2)
[1] "Estimates and significance testing of the effect of target variables"
Estimate. Std. Error t value Pr(>|t|)
d1 13893 1484 9.36 <2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
ds3 = rlassoEffect(X3,Y,W)
summary(ds3)
[1] "Estimates and significance testing of the effect of target variables"
Estimate. Std. Error t value Pr(>|t|)
d1 13839 1491 9.281 <2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Hand-coded Double ML for partially linear model
If we are not willing to assume a linear model and use for example
random forest to estimate the nuisance parameters of a partially linear
model, we need to predict the nuisance parameters out-of-sample. The
easiest way to do this is via two-fold cross-fitting:
Split the sample in two random subsamples, S1 and S2
Form prediction models in S1, use it to predict in S2
Form prediction models in S2, use it to predict in S1
Run residual-on-residual regression with the combined
predictions
# Initialize nuisance vectors
n = length(Y)
mhat = ehat = rep(NA,n)
# Draw random indices for sample 1
index_s1 = sample(1:n,n/2)
# Create S1
x1 = X[index_s1,]
w1 = W[index_s1]
y1 = Y[index_s1]
# Create sample 2 with those not in S1
x2 = X[-index_s1,]
w2 = W[-index_s1]
y2 = Y[-index_s1]
# Model in S1, predict in S2
rf = regression_forest(x1,w1)
ehat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1,y1)
mhat[-index_s1] = predict(rf,newdata=x2)$predictions
# Model in S2, predict in S1
rf = regression_forest(x2,w2)
ehat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2,y2)
mhat[index_s1] = predict(rf,newdata=x1)$predictions
# RORR
res_y = Y-mhat
res_w = W-ehat
pl_2f = lm_robust(res_y ~ 0+res_w)
summary(pl_2f)
Call:
lm_robust(formula = res_y ~ 0 + res_w)
Standard error type: HC2
Coefficients:
Estimate Std. Error t value Pr(>|t|) CI Lower CI Upper DF
res_w 13944 1517 9.191 4.68e-20 10970 16918 9914
Multiple R-squared: 0.01129 , Adjusted R-squared: 0.01119
F-statistic: 84.47 on 1 and 9914 DF, p-value: < 2.2e-16
Double ML for partially linear model with causalDML
package
2-fold cross-fitting is easy to implement by hand but especially in
small sample sizes, using only 50% of the data to estimate the nuisance
parameters might lead to unstable predictions.
Thus, we use the DML_partial_linear
function of the
causalDML
package to run 5-fold cross-fitting. This package
requires to create the methods that we use because it allows for
ensemble methods (for a more detailed intro see the GitHub page). For now,
we focus again on the random forest.
With 5-fold cross-fitting, the program splits the sample in 5 folds
and uses 4 folds (80% of the data) to predict the left out fold (20% of
the data). It iterates such that every fold is left out once.
# 5-fold cross-fitting with causalDML package
# Create learner
forest = create_method("forest_grf",args=list(tune.parameters = "all"))
# Run partially linear model
pl_5f = DML_partial_linear(Y,W,X,ml_w=list(forest),ml_y=list(forest),cf=5)
summary(pl_5f)
Coefficient SE t p
[1,] 13756.4 1514.7 9.0818 < 2.2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Comparison of results
We can now compare all the different methods. Besides Double
Selection with only the main effects all methods agree on an effect of
401(k) participation of wealth of about $14k:
# Collect the results
Coefficient = c(ds1$alpha,ds2$alpha,ds3$alpha,pl_2f$coefficients,pl_5f$result[1])
se = c(ds1$se,ds2$se,ds3$se,pl_2f$std.error,pl_5f$result[2])
data.frame(Coefficient,se,
Method = c("DS1","DS2","DS3","PL 2-fold","PL 5-fold"),
cil = Coefficient - 1.96*se,
ciu = Coefficient + 1.96*se) %>%
ggplot(aes(x=Method,y=Coefficient,ymin=cil,ymax=ciu)) + geom_point(size=2.5) + geom_errorbar(width=0.15) +
geom_hline(yintercept=0)
LS0tDQp0aXRsZTogIkNhdXNhbCBNTDogRG91YmxlIFNlbGVjdGlvbiBhbmQgUGFydGlhbGx5IExpbmVhciBEb3VibGUgTUwiDQpzdWJ0aXRsZTogIkFwcGxpY2F0aW9uIG5vdGVib29rIg0KYXV0aG9yOiAiTWljaGFlbCBLbmF1cyINCmRhdGU6ICJgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVtLyV5JylgIg0Kb3V0cHV0OiANCiAgaHRtbF9ub3RlYm9vazoNCiAgICB0b2M6IHRydWUNCiAgICB0b2NfZmxvYXQ6IHRydWUNCiAgICBjb2RlX2ZvbGRpbmc6IHNob3cNCi0tLQ0KDQo8YnI+DQoNCkdvYWxzOg0KDQotIElsbHVzdHJhdGUgd2h5IG5haXZlIGltcGxlbWVudGF0aW9ucyBvZiBtb2RlbCBzZWxlY3Rpb24gdXNpbmcgTGFzc28gYXJlIHByb2JsZW1hdGljDQoNCjxicj4NCg0KIyBJbnRyb2R1Y2luZyB0aGUgZGF0YQ0KDQpUaGUgQXBwbGljYXRpb24gTm90ZWJvb2sgYnVpbGRzIG9uIHRoZSBkYXRhc2V0IHRoYXQgaXMga2luZGx5IHByb3ZpZGVkIGluIHRoZSBgaGRtYCBwYWNrYWdlLiBUaGUgZGF0YSB3YXMgdXNlZCBpbiBbQ2hlcm5vemh1a292IGFuZCBIYW5zZW4gKDIwMDQpXShodHRwczovL2RpcmVjdC5taXQuZWR1L3Jlc3QvYXJ0aWNsZS84Ni8zLzczNS81NzU4Ni9UaGUtRWZmZWN0cy1vZi00MDEtSy1QYXJ0aWNpcGF0aW9uLW9uLXRoZS1XZWFsdGgpLiBUaGVpciBwYXBlciBpbnZlc3RpZ2F0ZXMgdGhlIGVmZmVjdCBvZiBwYXJ0aWNpcGF0aW9uIGluIHRoZSBlbXBsb3llci1zcG9uc29yZWQgNDAxKGspIHJldGlyZW1lbnQgc2F2aW5ncyBwbGFuIChgcDQwMWApIG9uIG5ldCBhc3NldHMgKGBuZXRfdGZhYCkuIFNpbmNlIHRoZW4gdGhlIGRhdGEgd2FzIHVzZWQgdG8gc2hvd2Nhc2UgbWFueSBuZXcgbWV0aG9kcy4gSXQgaXMgbm90IHRoZSBtb3N0IGNvbXByZWhlbnNpdmUgZGF0YXNldCB3aXRoIGJhc2ljYWxseSB0ZW4gY292YXJpYXRlcy9yZWdyZXNzb3JzL3ByZWRpY3RvcnM6DQoNCi0gKmFnZSo6IGFnZQ0KDQotICpkYio6IGRlZmluZWQgYmVuZWZpdCBwZW5zaW9uDQoNCi0gKmVkdWMqOiBlZHVjYXRpb24gKGluIHllYXJzKQ0KDQotICpmc2l6ZSo6IGZhbWlseSBzaXplDQoNCi0gKmhvd24qOiBob21lIG93bmVyDQoNCi0gKmluYyo6IGluY29tZSAoaW4gVVMgJCkNCg0KLSAqbWFsZSo6IG1hbGUNCg0KLSAqbWFycio6IG1hcnJpZWQNCg0KLSAqcGlyYSo6IHBhcnRpY2lwYXRpb24gaW4gaW5kaXZpZHVhbCByZXRpcmVtZW50IGFjY291bnQgKElSQSkNCg0KLSAqdHdvZWFybio6IHR3byBlYXJuZXJzDQoNCkhvd2V2ZXIsIGl0IGlzIHB1YmxpY2x5IGF2YWlsYWJsZSBhbmQgdGhlIHJlbGF0aXZlbHkgZmV3IGNvdmFyaWF0ZXMgZW5zdXJlIHRoYXQgdGhlIHByb2dyYW1zIGRvIG5vdCBydW4gdG9vIGxvbmcuDQoNCmBgYHtyLCB3YXJuaW5nID0gRiwgbWVzc2FnZSA9IEZ9DQojIFRvIGluc3RhbGwgdGhlIGNhdXNhbERNTCBwYWNrYWdlIHVuY29tbWVudCB0aGUgZm9sbG93aW5nIHR3byBsaW5lcw0KIyBsaWJyYXJ5KGRldnRvb2xzKQ0KIyBpbnN0YWxsX2dpdGh1YihyZXBvPSJNQ0tuYXVzL2NhdXNhbERNTCIpDQoNCiMgTG9hZCB0aGUgcGFja2FnZXMgcmVxdWlyZWQgZm9yIGxhdGVyDQpsaWJyYXJ5KGhkbSkNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShjYXVzYWxETUwpDQpsaWJyYXJ5KGdyZikNCmxpYnJhcnkoZXN0aW1hdHIpDQoNCnNldC5zZWVkKDEyMzQpICMgZm9yIHJlcGxpY2FiaWxpdHkNCg0KZGF0YShwZW5zaW9uKQ0KIyBPdXRjb21lDQpZID0gcGVuc2lvbiRuZXRfdGZhDQojIFRyZWF0bWVudA0KVyA9IHBlbnNpb24kcDQwMQ0KIyBDcmVhdGUgbWFpbiBlZmZlY3RzIG1hdHJpeA0KWCA9IG1vZGVsLm1hdHJpeCh+IDAgKyBhZ2UgKyBkYiArIGVkdWMgKyBmc2l6ZSArIGhvd24gKyBpbmMgKyBtYWxlICsgbWFyciArIHBpcmEgKyB0d29lYXJuLCBkYXRhID0gcGVuc2lvbikNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCiMgSGFuZC1jb2RlZCBEb3VibGUgU2VsZWN0aW9uDQoNClRvIHVuZGVyc3RhbmQgdGhlIHByb2NlZHVyZSBvZiBEb3VibGUgU2VsZWN0aW9uLCB3ZSBwcm9jZWVkIHN0ZXAgYnkgc3RlcCB1c2luZyBvbmx5IHRoZSBtYWluIGVmZmVjdHMgZm9yIHNpbXBsaWNpdHk6DQoNCjEuIFNlbGVjdCB2YXJpYWJsZXMgaW4gdGhlIG91dGNvbWUgcmVncmVzc2lvbiB3aXRob3V0IHRoZSB0cmVhdG1lbnQ6DQoNCmBgYHtyfQ0KIyBTZWxlY3QgdmFyaWFibGVzIGluIG91dGNvbWUgcmVncmVzc2lvbg0Kc2VsX3kgPSBybGFzc28oWCxZKQ0KIyBXaGljaCB2YXJpYWJsZXMgYXJlIHNlbGVjdGVkPw0Kd2hpY2goc2VsX3kkYmV0YSAhPSAwKQ0KYGBgDQoNCjxicj4NCg0KMi4gU2VsZWN0IHZhcmlhYmxlcyBpbiB0aGUgdHJlYXRtZW50IHJlZ3Jlc3Npb246DQoNCmBgYHtyfQ0KIyBTZWxlY3QgdmFyaWFibGVzIGluIHRyZWF0bWVudCByZWdyZXNzaW9uDQpzZWxfdyA9IHJsYXNzbyhYLFcpDQp3aGljaChzZWxfdyRiZXRhICE9IDApDQpgYGANCk5vdGUgdGhhdCB2YXJpYWJsZSAqZGIqIGlzIG5vdyBzZWxlY3RlZCB3aGljaCB3YXMgbm90IHNlbGVjdGVkIGluIHN0ZXAgb25lLiANCg0KPGJyPg0KDQozLiBVc2UgdGhlIHVuaW9uIG9mIHRoZSBpbiB0b3RhbCBzZXZlbiBzZWxlY3RlZCB2YXJpYWJsZXMgdG8gcnVuIGEgc3RhbmRhcmQgT0xTIHJlZ3Jlc3Npb24gd2l0aCByb2J1c3Qgc3RhbmRhcmQgZXJyb3JzOg0KDQpgYGB7cn0NCiMgRG91YmxlIHNlbGVjdGlvbg0KWF9zZWxfdW5pb24gPSBYWyxzZWxfeSRiZXRhICE9IDAgfCBzZWxfdyRiZXRhICE9IDBdDQpkc19oYW5kID0gbG1fcm9idXN0KFkgfiBXICsgWF9zZWxfdW5pb24pDQpzdW1tYXJ5KGRzX2hhbmQpDQpgYGANCg0KDQo8YnI+DQo8YnI+DQoNCiMgRG91YmxlIFNlbGVjdGlvbiB3aXRoIGBoZG1gIHBhY2thZ2UNCg0KSW4gcHJhY3RpY2Ugd2Ugd2FudCB0byBoYXZlIG9uZSBmdW5jdGlvbiB0aGF0IGRvZXMgZXZlcnl0aGluZyBhdCBvbmNlLiBUaGlzIGlzIHRoZSBgcmxhc3NvRWZmZWN0YCBjb21tYW5kIG9mIHRoZSBgaGRtYCBwYWNrYWdlLg0KDQpgYGB7cn0NCmRzMSA9IHJsYXNzb0VmZmVjdChYLFksVykNCnN1bW1hcnkoZHMxKQ0KYGBgDQoNCkl0IHByb2R1Y2VzIHRoZSBzYW1lIHBvaW50IGVzdGltYXRlIGFzIHRoZSBoYW5kLWNvZGVkIHZlcnNpb246DQoNCmBgYHtyfQ0KYWxsLmVxdWFsKGFzLm51bWVyaWMoZHMxJGFscGhhKSxhcy5udW1lcmljKGRzX2hhbmQkY29lZmZpY2llbnRzWzJdKSkNCmBgYA0KDQpPbmx5IHRoZSBzdGFuZGFyZCBlcnJvciBkaWZmZXJzIHNsaWdodGx5IGJlY2F1c2Ugb2YgZGlmZmVyZW50IGRlZmF1bHRzLiBJZiB5b3UgZG8gbm90IGxpa2UgdGhpcywgYXBwbHlpbmcgYHNlX3R5cGUgPSAiSEMxYCBpbiB0aGUgYGxtX3JvYnVzdCgpYCBmdW5jdGlvbiByZXBsaWNhdGVzIHRoZSBzdGFuZGFyZCBlcnJvciBvZiBgcmxhc3NvRWZmZWN0KClgLg0KDQo8YnI+DQoNCiMjIE1vcmUgZmxleGlibGUgZGljdGlvbmFyaWVzDQoNCldlIGNhbiBjaGVjayB3aGV0aGVyIG1vcmUgZmxleGlibGUgY292YXJpYXRlIG1hdHJpY2VzIHByb3ZpZGUgZGlmZmVyZW50IHJlc3VsdHM6DQoNCi0gYFgyYCB3aXRoIDg4IHZhcmlhYmxlczogU2Vjb25kIG9yZGVyIHBvbHlub21pYWxzIG9mIHRoZSBjb250aW51b3VzIHZhcmlhYmxlcyBhZ2UsIGVkdWNhdGlvbiBhbmQgaW5jb21lIGFzIHdlbGwgYXMgc2Vjb25kIG9yZGVyIGludGVyYWN0aW9ucyBvZiBhbGwgdmFyaWFibGVzDQoNCi0gYFgzYCB3aXRoIDU2NyB2YXJpYWJsZXM6IFRoaXJkIG9yZGVyIHBvbHlub21pYWxzIG9mIHRoZSBjb250aW51b3VzIHZhcmlhYmxlcyBhZ2UsIGVkdWNhdGlvbiBhbmQgaW5jb21lIGFzIHdlbGwgYXMgdGhpcmQgb3JkZXIgaW50ZXJhY3Rpb25zIG9mIGFsbCB2YXJpYWJsZXMNCg0KDQpgYGB7cn0NClgyID0gbW9kZWwubWF0cml4KH4gMCArIChmc2l6ZSArIG1hcnIgKyB0d29lYXJuICsgZGIgKyBwaXJhICsgaG93biArIG1hbGUgKw0KICAgICAgICAgICAgICAgICAgICAgICAgICAgcG9seShhZ2UsMikgKyBwb2x5KGVkdWMsMikgKyBwb2x5KGluYywyKSleMiwgZGF0YSA9IHBlbnNpb24pDQpYMyA9IG1vZGVsLm1hdHJpeCh+IDAgKyAoZnNpemUgKyBtYXJyICsgdHdvZWFybiArIGRiICsgcGlyYSArIGhvd24gKyBtYWxlICsNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHBvbHkoYWdlLDMpICsgcG9seShlZHVjLDMpICsgcG9seShpbmMsMykpXjMsIGRhdGEgPSBwZW5zaW9uKQ0KYGBgDQoNCkluZGVlZCwgdGhlIGVmZmVjdHMgYXJlIGJ5IG1vcmUgdGhhbiAkMjAwMCBEb2xsYXJzIGhpZ2hlciwgYnV0IGdvaW5nIGZyb20gdHdvIHRvIHRocmVlIG9yZGVyIHRlcm1zIG1ha2VzIGJhc2ljYWxseSBubyBkaWZmZXJlbmNlOg0KDQpgYGB7cn0NCmRzMiA9IHJsYXNzb0VmZmVjdChYMixZLFcpDQpzdW1tYXJ5KGRzMikNCmRzMyA9IHJsYXNzb0VmZmVjdChYMyxZLFcpDQpzdW1tYXJ5KGRzMykNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCg0KIyBIYW5kLWNvZGVkIERvdWJsZSBNTCBmb3IgcGFydGlhbGx5IGxpbmVhciBtb2RlbA0KDQpJZiB3ZSBhcmUgbm90IHdpbGxpbmcgdG8gYXNzdW1lIGEgbGluZWFyIG1vZGVsIGFuZCB1c2UgZm9yIGV4YW1wbGUgcmFuZG9tIGZvcmVzdCB0byBlc3RpbWF0ZSB0aGUgbnVpc2FuY2UgcGFyYW1ldGVycyBvZiBhIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwsIHdlIG5lZWQgdG8gcHJlZGljdCB0aGUgbnVpc2FuY2UgcGFyYW1ldGVycyBvdXQtb2Ytc2FtcGxlLiBUaGUgZWFzaWVzdCB3YXkgdG8gZG8gdGhpcyBpcyB2aWEgdHdvLWZvbGQgY3Jvc3MtZml0dGluZzoNCg0KLSBTcGxpdCB0aGUgc2FtcGxlIGluIHR3byByYW5kb20gc3Vic2FtcGxlcywgUzEgYW5kIFMyDQoNCi0gRm9ybSBwcmVkaWN0aW9uIG1vZGVscyBpbiBTMSwgdXNlIGl0IHRvIHByZWRpY3QgaW4gUzINCg0KLSBGb3JtIHByZWRpY3Rpb24gbW9kZWxzIGluIFMyLCB1c2UgaXQgdG8gcHJlZGljdCBpbiBTMQ0KDQotIFJ1biByZXNpZHVhbC1vbi1yZXNpZHVhbCByZWdyZXNzaW9uIHdpdGggdGhlIGNvbWJpbmVkIHByZWRpY3Rpb25zDQoNCg0KYGBge3J9DQojIEluaXRpYWxpemUgbnVpc2FuY2UgdmVjdG9ycw0KbiA9IGxlbmd0aChZKQ0KbWhhdCA9IGVoYXQgPSByZXAoTkEsbikNCiMgRHJhdyByYW5kb20gaW5kaWNlcyBmb3Igc2FtcGxlIDENCmluZGV4X3MxID0gc2FtcGxlKDE6bixuLzIpDQojIENyZWF0ZSBTMQ0KeDEgPSBYW2luZGV4X3MxLF0NCncxID0gV1tpbmRleF9zMV0NCnkxID0gWVtpbmRleF9zMV0NCiMgQ3JlYXRlIHNhbXBsZSAyIHdpdGggdGhvc2Ugbm90IGluIFMxDQp4MiA9IFhbLWluZGV4X3MxLF0NCncyID0gV1staW5kZXhfczFdDQp5MiA9IFlbLWluZGV4X3MxXQ0KIyBNb2RlbCBpbiBTMSwgcHJlZGljdCBpbiBTMg0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MSx3MSkNCmVoYXRbLWluZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MikkcHJlZGljdGlvbnMNCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDEseTEpDQptaGF0Wy1pbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDIpJHByZWRpY3Rpb25zDQojIE1vZGVsIGluIFMyLCBwcmVkaWN0IGluIFMxDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgyLHcyKQ0KZWhhdFtpbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDEpJHByZWRpY3Rpb25zDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgyLHkyKQ0KbWhhdFtpbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDEpJHByZWRpY3Rpb25zDQojIFJPUlINCnJlc195ID0gWS1taGF0DQpyZXNfdyA9IFctZWhhdA0KcGxfMmYgPSBsbV9yb2J1c3QocmVzX3kgfiAwK3Jlc193KQ0Kc3VtbWFyeShwbF8yZikNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCg0KIyBEb3VibGUgTUwgZm9yIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwgd2l0aCBgY2F1c2FsRE1MYCBwYWNrYWdlDQoNCjItZm9sZCBjcm9zcy1maXR0aW5nIGlzIGVhc3kgdG8gaW1wbGVtZW50IGJ5IGhhbmQgYnV0IGVzcGVjaWFsbHkgaW4gc21hbGwgc2FtcGxlIHNpemVzLCB1c2luZyBvbmx5IDUwJSBvZiB0aGUgZGF0YSB0byBlc3RpbWF0ZSB0aGUgbnVpc2FuY2UgcGFyYW1ldGVycyBtaWdodCBsZWFkIHRvIHVuc3RhYmxlIHByZWRpY3Rpb25zLg0KDQpUaHVzLCB3ZSB1c2UgdGhlIGBETUxfcGFydGlhbF9saW5lYXJgIGZ1bmN0aW9uIG9mIHRoZSBgY2F1c2FsRE1MYCBwYWNrYWdlIHRvIHJ1biA1LWZvbGQgY3Jvc3MtZml0dGluZy4gVGhpcyBwYWNrYWdlIHJlcXVpcmVzIHRvIGNyZWF0ZSB0aGUgbWV0aG9kcyB0aGF0IHdlIHVzZSBiZWNhdXNlIGl0IGFsbG93cyBmb3IgZW5zZW1ibGUgbWV0aG9kcyAoZm9yIGEgbW9yZSBkZXRhaWxlZCBpbnRybyBzZWUgdGhlIFtHaXRIdWIgcGFnZV0oaHR0cHM6Ly9naXRodWIuY29tL01DS25hdXMvY2F1c2FsRE1MKSkuIEZvciBub3csIHdlIGZvY3VzIGFnYWluIG9uIHRoZSByYW5kb20gZm9yZXN0Lg0KDQpXaXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nLCB0aGUgcHJvZ3JhbSBzcGxpdHMgdGhlIHNhbXBsZSBpbiA1IGZvbGRzIGFuZCB1c2VzIDQgZm9sZHMgKDgwJSBvZiB0aGUgZGF0YSkgdG8gcHJlZGljdCB0aGUgbGVmdCBvdXQgZm9sZCAoMjAlIG9mIHRoZSBkYXRhKS4gSXQgaXRlcmF0ZXMgc3VjaCB0aGF0IGV2ZXJ5IGZvbGQgaXMgbGVmdCBvdXQgb25jZS4NCg0KDQpgYGB7cn0NCiMgNS1mb2xkIGNyb3NzLWZpdHRpbmcgd2l0aCBjYXVzYWxETUwgcGFja2FnZQ0KIyBDcmVhdGUgbGVhcm5lcg0KZm9yZXN0ID0gY3JlYXRlX21ldGhvZCgiZm9yZXN0X2dyZiIsYXJncz1saXN0KHR1bmUucGFyYW1ldGVycyA9ICJhbGwiKSkNCiMgUnVuIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwNCnBsXzVmID0gRE1MX3BhcnRpYWxfbGluZWFyKFksVyxYLG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQpzdW1tYXJ5KHBsXzVmKQ0KYGBgDQoNCjxicj4NCjxicj4NCg0KDQojIENvbXBhcmlzb24gb2YgcmVzdWx0cw0KDQpXZSBjYW4gbm93IGNvbXBhcmUgYWxsIHRoZSBkaWZmZXJlbnQgbWV0aG9kcy4gQmVzaWRlcyBEb3VibGUgU2VsZWN0aW9uIHdpdGggb25seSB0aGUgbWFpbiBlZmZlY3RzIGFsbCBtZXRob2RzIGFncmVlIG9uIGFuIGVmZmVjdCBvZiA0MDEoaykgcGFydGljaXBhdGlvbiBvZiB3ZWFsdGggb2YgYWJvdXQgJDE0azoNCg0KYGBge3J9DQojIENvbGxlY3QgdGhlIHJlc3VsdHMNCkNvZWZmaWNpZW50ID0gYyhkczEkYWxwaGEsZHMyJGFscGhhLGRzMyRhbHBoYSxwbF8yZiRjb2VmZmljaWVudHMscGxfNWYkcmVzdWx0WzFdKQ0Kc2UgPSBjKGRzMSRzZSxkczIkc2UsZHMzJHNlLHBsXzJmJHN0ZC5lcnJvcixwbF81ZiRyZXN1bHRbMl0pDQpkYXRhLmZyYW1lKENvZWZmaWNpZW50LHNlLA0KICAgICAgICAgICAgICAgIE1ldGhvZCA9IGMoIkRTMSIsIkRTMiIsIkRTMyIsIlBMIDItZm9sZCIsIlBMIDUtZm9sZCIpLA0KICAgICAgICAgICAgICAgIGNpbCA9IENvZWZmaWNpZW50IC0gMS45NipzZSwNCiAgICAgICAgICAgICAgICBjaXUgPSBDb2VmZmljaWVudCArIDEuOTYqc2UpICAlPiUgDQogIGdncGxvdChhZXMoeD1NZXRob2QseT1Db2VmZmljaWVudCx5bWluPWNpbCx5bWF4PWNpdSkpICsgZ2VvbV9wb2ludChzaXplPTIuNSkgKyBnZW9tX2Vycm9yYmFyKHdpZHRoPTAuMTUpICArDQogIGdlb21faGxpbmUoeWludGVyY2VwdD0wKQ0KYGBgDQoNCg0KPGJyPg0KPGJyPg0KDQog