Goals:
- Hand-code partially linear Double ML
Data generating process
Consider the following DGP:
\(p=5\) independent covariates
\(X_1,...,X_k,...,X_{5}\) drawn from a
uniform distribution: \(X_k \sim
uniform(-\pi,\pi)\)
The treatment model is \(W =
\underbrace{sin(X_1)}_{e(X)} + \epsilon\), with \(\epsilon \sim N(0,1)\)
The outcome model is \(Y =
\underbrace{0.1}_{\theta} W + \underbrace{sin(X_1)}_{m(X)}+
\varepsilon\), with \(\varepsilon \sim
N(0,1)\)
This means that we are in a highly nonlinear setting, but only one
variable (\(X_1\)) is relevant and the
others are just noise. We draw a sample of \(N=100\) and inspect it.
if (!require("grf")) install.packages("grf", dependencies = TRUE); library(grf)
if (!require("estimatr")) install.packages("estimatr", dependencies = TRUE); library(estimatr)
if (!require("tidyverse")) install.packages("tidyverse", dependencies = TRUE); library(tidyverse)
if (!require("patchwork")) install.packages("patchwork", dependencies = TRUE); library(patchwork)
if (!require("hdm")) install.packages("hdm", dependencies = TRUE); library(hdm)
if (!require("causalDML")) {
if (!require("devtools")) install.packages("devtools", dependencies = TRUE); library(devtools)
install_github(repo="MCKnaus/causalDML")
}; library(causalDML)
set.seed(1234)
n = 200
p = 5
theta = 0.1
x = matrix(runif(n*p,-pi,pi),ncol=p)
e = function(x){sin(x)}
m = function(x){theta*e(x) + sin(x)}
w = e(x[,1]) + rnorm(n,0,1)
y = theta*w + sin(x[,1]) + rnorm(n,0,1)
df = data.frame(x=x[,1],w,y)
g1 = ggplot(df,aes(x=x, y=w)) + stat_function(fun=e,linewidth=1) + ylab("W and e(x)") + geom_point() + xlab("X1")
g2 = ggplot(df,aes(x=x, y=y)) + stat_function(fun=m,linewidth=1) + ylab("Y and m(x)") + geom_point() + xlab("X1")
g1 | g2
Hand-coded residual-on-residual regression w/o cross-fitting
We estimate the nuisance parameters \(e(X)=E[W|X]\) and \(m(X)=E[Y|X]\) using random forest without
honesty (sample size too small for honesty) and use the respective
residuals in a residual-on-residual regression (RORR) w/o constant:
# No cross-fitting
rf = regression_forest(x,w,honesty=F)
ehat = predict(rf,newdata=x)$predictions
# Predict outcome in-sample
rf = regression_forest(x,y,honesty=F)
mhat = predict(rf,newdata=x)$predictions
# Get residuals
res_y = y-mhat
res_w = w-ehat
# Run residual-on-residual regression (RORR)
lm_robust(res_y ~ 0 + res_w)
Estimate Std. Error t value Pr(>|t|) CI Lower CI Upper DF
res_w 0.09796347 0.09097973 1.076761 0.2828904 -0.0814446 0.2773715 199
Note that the ultimate hand-coded version uses the equation of the
slides, which gives the equivalent estimate \[\hat{\theta} = \frac{\frac{1}{N}\sum_{i=1}^N (Y_i
- \hat{m}(X_i)) (W_i - \hat{e}(X_i))}{\frac{1}{N}\sum_{i=1}^N (W_i -
\hat{e}(X_i))^2}\]
cat("Fully hand-coded:\n",mean(res_y * res_w) / mean(res_w^2))
Fully hand-coded:
0.09796347
Hand-coded residual-on-residual regression with 2-fold
cross-fitting
The theoretical results require that we 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 RORR with the combined predictions
# Initialize nuisance vectors
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,honesty=F)
ehat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1,y1,honesty=F)
mhat[-index_s1] = predict(rf,newdata=x2)$predictions
# Model in S2, predict in S1
rf = regression_forest(x2,w2,honesty=F)
ehat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2,y2,honesty=F)
mhat[index_s1] = predict(rf,newdata=x1)$predictions
# RORR
res_y = y-mhat
res_w = w-ehat
lm_robust(res_y ~ 0 + res_w)
Estimate Std. Error t value Pr(>|t|) CI Lower CI Upper DF
res_w 0.1233961 0.08663449 1.42433 0.1559172 -0.04744335 0.2942356 199
Residual-on-residual regression with 5-fold cross-fitting
2-fold cross-fitting is easy to implement 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 now, we focus again on the plain random
forest.
With 5-fold cross-fitting, we split the sample in 5 folds and use 4
folds (80% of the data) to predict the left out fold (20% of the data).
We iterate such that every fold is left out once.
# 5-fold cross-fitting with causalDML package
# Create learner
forest = create_method("forest_grf",args=list(honesty=F))
# Run partially linear model
pl_cf5 = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
summary(pl_cf5)
Coefficient SE t p
[1,] 0.093355 0.084427 1.1057 0.2702
Simulation study
To check whether the above results are just by chance, we run a
simulation study drawing \(M=100\)
samples from the DGP described above and estimate the effect with six
different methods:
Double Selection with only the 5 main variables
Double Selection with the 5 main variables and their squared
values
Double Selection including up to the third order polynomial of
the main variables (the results do not improve for at least fifth order
while increasing computational costs)
Partially linear model estimated w/o cross-fitting
Partially linear model estimated with 2-fold
cross-fitting
Partially linear model estimated with 5-fold
cross-fitting
# set number of replications
n_rep = 100
# Initialize results matrix
results = matrix(NA,n_rep,6)
colnames(results) = c("DS1","DS2","DS3","PL no cf","PL cf2","PL cf5")
# run the simulation
for (i in 1:n_rep) {
x = matrix(runif(n*p,-pi,pi),ncol=p)
w = e(x[,1]) + rnorm(n,0,1)
y = theta*w + sin(x[,1]) + rnorm(n,0,1)
# double selections
results[i,1] = rlassoEffect(x,y,w)$alpha
x2 = cbind(x,x^2)
results[i,2] = rlassoEffect(x2,y,w)$alpha
x3 = cbind(x2,x^3)
results[i,3] = rlassoEffect(x3,y,w)$alpha
# No cross-fitting
rf = regression_forest(x,w,honesty=F)
ehat = predict(rf,newdata=x)$predictions
rf = regression_forest(x,y,honesty=F)
mhat = predict(rf,newdata=x)$predictions
res_y = y-mhat
res_w = w-ehat
results[i,4] = lm(res_y ~ 0+res_w)$coefficients
# 2-fold cross-fitting
mhat = ehat = rep(NA,n)
index_s1 = sample(1:n,n/2)
x1 = x[index_s1,]
w1 = w[index_s1]
y1 = y[index_s1]
x2 = x[-index_s1,]
w2 = w[-index_s1]
y2 = y[-index_s1]
rf = regression_forest(x1,w1,honesty=F)
ehat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1,y1,honesty=F)
mhat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x2,w2,honesty=F)
ehat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2,y2,honesty=F)
mhat[index_s1] = predict(rf,newdata=x1)$predictions
res_y = y-mhat
res_w = w-ehat
results[i,5] = lm(res_y ~ 0+res_w)$coefficients
# 5-fold cross-fitting
results[i,6] = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)$result[1]
}
We plot the histograms of Double Selection with third order
polynomials (those with lower order look identical because all of them
select no controls), and the three partially linear estimators.
as.data.frame(results[,c(3:6)]) %>% pivot_longer(cols=everything(),names_to = "Estimator",values_to = "coef") %>%
ggplot(aes(x = coef, fill = Estimator)) + geom_density(alpha=0.4) + theme_bw() + geom_vline(xintercept=theta)
The Double Selection estimator is clearly biased. Those based on the
partially linear model also a little bit, but they are remarkably close
given that we use only 200 observations.
Let’s have a closer look at the performance and check the MSE of the
estimators and its decomposition, where \(\hat{\theta}_m\) is the estimated parameter
in the \(m\)-th replication:
\[MSE(\hat{\theta)} = M^{-1} \sum_m
(\hat{\theta}_m - \theta)^2 = \underbrace{(\overbrace{M^{-1} \sum_m
\hat{\theta}_m}^{\bar{\theta}} - \theta)^2}_{Bias^2} +
\underbrace{M^{-1} \sum_m (\hat{\theta}_m - \bar{\theta})^2}_{Variance}
\]
data.frame(method = colnames(results),
bias2 = colMeans(results-theta)^2,
var = colMeans(sweep(results,2,colMeans(results))^2)) %>%
pivot_longer(-method,names_to = "Component",values_to = "MSE") %>%
ggplot(aes(fill=factor(Component,levels=c("var","bias2")), y=MSE, x=method)) +
geom_bar(position="stack", stat="identity") + scale_fill_discrete(name = "Component")
We observe that all Double Selection estimators are severely biased,
while the bias of the partially linear estimators is negligible.
The worse performance of 2-fold cross-fitting should disappear with
larger sample sizes.
In this setting cross-fitting seems not to be required. However, the
next notebooks will look closer into this issue and show that it can be
crucial to get valid inference.
Take-away
We can program a cross-fit Double ML partially linear estimator
in less than 20 lines of code.
Double Selection can fail in non-linear DGPs, even if provided
with a lot of polynomials.
In small samples, we should use more than two folds to exploit
more information in forming the prediction models.
Suggestions to play with the toy model
Feel free to play around with the code. This is useful to sharpen and
challenge your understanding of the methods. Think about the
consequences of a modification before you run it and check whether the
results are in line with your expectation. Some suggestions:
Modify DGP (increase theta, correlation of covariates,
coefficients, noise term, …)
Increase the number of observations
Increase cross-fitting folds to 10 and/or 20
LS0tDQp0aXRsZTogIkNhdXNhbCBNTDogUGFydGlhbGx5IGxpbmVhciBEb3VibGUgTUwiDQpzdWJ0aXRsZTogIlNpbXVsYXRpb24gbm90ZWJvb2siDQphdXRob3I6ICJNaWNoYWVsIEtuYXVzIg0KZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJW0vJXknKWAiDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KICAgIGNvZGVfZm9sZGluZzogc2hvdw0KLS0tDQoNCg0KR29hbHM6DQoNCi0gSGFuZC1jb2RlIHBhcnRpYWxseSBsaW5lYXIgRG91YmxlIE1MDQoNCjxicj4NCg0KIyBEYXRhIGdlbmVyYXRpbmcgcHJvY2Vzcw0KDQpDb25zaWRlciB0aGUgZm9sbG93aW5nIERHUDoNCg0KLSAkcD01JCBpbmRlcGVuZGVudCBjb3ZhcmlhdGVzICRYXzEsLi4uLFhfaywuLi4sWF97NX0kIGRyYXduIGZyb20gYSB1bmlmb3JtIGRpc3RyaWJ1dGlvbjogJFhfayBcc2ltIHVuaWZvcm0oLVxwaSxccGkpJA0KDQotIFRoZSB0cmVhdG1lbnQgbW9kZWwgaXMgJFcgPSBcdW5kZXJicmFjZXtzaW4oWF8xKX1fe2UoWCl9ICsgXGVwc2lsb24kLCB3aXRoICRcZXBzaWxvbiBcc2ltIE4oMCwxKSQNCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBpcyAkWSA9IFx1bmRlcmJyYWNlezAuMX1fe1x0aGV0YX0gVyArIFx1bmRlcmJyYWNle3NpbihYXzEpfV97bShYKX0rIFx2YXJlcHNpbG9uJCwgd2l0aCAkXHZhcmVwc2lsb24gXHNpbSBOKDAsMSkkDQoNClRoaXMgbWVhbnMgdGhhdCB3ZSBhcmUgaW4gYSBoaWdobHkgbm9ubGluZWFyIHNldHRpbmcsIGJ1dCBvbmx5IG9uZSB2YXJpYWJsZSAoJFhfMSQpIGlzIHJlbGV2YW50IGFuZCB0aGUgb3RoZXJzIGFyZSBqdXN0IG5vaXNlLiBXZSBkcmF3IGEgc2FtcGxlIG9mICROPTEwMCQgYW5kIGluc3BlY3QgaXQuDQoNCg0KYGBge3IsIHdhcm5pbmcgPSBGLCBtZXNzYWdlID0gRn0NCmlmICghcmVxdWlyZSgiZ3JmIikpIGluc3RhbGwucGFja2FnZXMoImdyZiIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGdyZikNCmlmICghcmVxdWlyZSgiZXN0aW1hdHIiKSkgaW5zdGFsbC5wYWNrYWdlcygiZXN0aW1hdHIiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShlc3RpbWF0cikNCmlmICghcmVxdWlyZSgidGlkeXZlcnNlIikpIGluc3RhbGwucGFja2FnZXMoInRpZHl2ZXJzZSIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHRpZHl2ZXJzZSkNCmlmICghcmVxdWlyZSgicGF0Y2h3b3JrIikpIGluc3RhbGwucGFja2FnZXMoInBhdGNod29yayIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHBhdGNod29yaykNCmlmICghcmVxdWlyZSgiaGRtIikpIGluc3RhbGwucGFja2FnZXMoImhkbSIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGhkbSkNCmlmICghcmVxdWlyZSgiY2F1c2FsRE1MIikpIHsNCiAgaWYgKCFyZXF1aXJlKCJkZXZ0b29scyIpKSBpbnN0YWxsLnBhY2thZ2VzKCJkZXZ0b29scyIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGRldnRvb2xzKQ0KICBpbnN0YWxsX2dpdGh1YihyZXBvPSJNQ0tuYXVzL2NhdXNhbERNTCIpIA0KfTsgbGlicmFyeShjYXVzYWxETUwpDQoNCnNldC5zZWVkKDEyMzQpDQoNCm4gPSAyMDANCnAgPSA1DQoNCnRoZXRhID0gMC4xDQoNCnggPSBtYXRyaXgocnVuaWYobipwLC1waSxwaSksbmNvbD1wKQ0KZSA9IGZ1bmN0aW9uKHgpe3Npbih4KX0NCm0gPSBmdW5jdGlvbih4KXt0aGV0YSplKHgpICsgc2luKHgpfQ0KdyA9IGUoeFssMV0pICsgcm5vcm0obiwwLDEpDQp5ID0gdGhldGEqdyArIHNpbih4WywxXSkgKyBybm9ybShuLDAsMSkNCg0KZGYgPSBkYXRhLmZyYW1lKHg9eFssMV0sdyx5KQ0KZzEgPSBnZ3Bsb3QoZGYsYWVzKHg9eCwgeT13KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1lLGxpbmV3aWR0aD0xKSArIHlsYWIoIlcgYW5kIGUoeCkiKSArIGdlb21fcG9pbnQoKSArIHhsYWIoIlgxIikNCmcyID0gZ2dwbG90KGRmLGFlcyh4PXgsIHk9eSkpICsgc3RhdF9mdW5jdGlvbihmdW49bSxsaW5ld2lkdGg9MSkgKyB5bGFiKCJZIGFuZCBtKHgpIikgKyBnZW9tX3BvaW50KCkgKyB4bGFiKCJYMSIpDQpnMSB8IGcyDQpgYGANCg0KPGJyPiANCg0KIyBIYW5kLWNvZGVkIHJlc2lkdWFsLW9uLXJlc2lkdWFsIHJlZ3Jlc3Npb24gdy9vIGNyb3NzLWZpdHRpbmcNCg0KV2UgZXN0aW1hdGUgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgJGUoWCk9RVtXfFhdJCBhbmQgJG0oWCk9RVtZfFhdJCB1c2luZyByYW5kb20gZm9yZXN0IHdpdGhvdXQgaG9uZXN0eSAoc2FtcGxlIHNpemUgdG9vIHNtYWxsIGZvciBob25lc3R5KSBhbmQgdXNlIHRoZSByZXNwZWN0aXZlIHJlc2lkdWFscyBpbiBhIHJlc2lkdWFsLW9uLXJlc2lkdWFsIHJlZ3Jlc3Npb24gKFJPUlIpIHcvbyBjb25zdGFudDoNCg0KYGBge3J9DQojIE5vIGNyb3NzLWZpdHRpbmcNCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeCx3LGhvbmVzdHk9RikNCmVoYXQgPSBwcmVkaWN0KHJmLG5ld2RhdGE9eCkkcHJlZGljdGlvbnMNCiMgUHJlZGljdCBvdXRjb21lIGluLXNhbXBsZQ0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4LHksaG9uZXN0eT1GKQ0KbWhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KIyBHZXQgcmVzaWR1YWxzDQpyZXNfeSA9IHktbWhhdA0KcmVzX3cgPSB3LWVoYXQNCiMgUnVuIHJlc2lkdWFsLW9uLXJlc2lkdWFsIHJlZ3Jlc3Npb24gKFJPUlIpDQpsbV9yb2J1c3QocmVzX3kgfiAwICsgcmVzX3cpDQpgYGANCg0KTm90ZSB0aGF0IHRoZSB1bHRpbWF0ZSBoYW5kLWNvZGVkIHZlcnNpb24gdXNlcyB0aGUgZXF1YXRpb24gb2YgdGhlIHNsaWRlcywgd2hpY2ggZ2l2ZXMgdGhlIGVxdWl2YWxlbnQgZXN0aW1hdGUNCiQkXGhhdHtcdGhldGF9ID0gXGZyYWN7XGZyYWN7MX17Tn1cc3VtX3tpPTF9Xk4gKFlfaSAtIFxoYXR7bX0oWF9pKSkgKFdfaSAtIFxoYXR7ZX0oWF9pKSl9e1xmcmFjezF9e059XHN1bV97aT0xfV5OIChXX2kgLSBcaGF0e2V9KFhfaSkpXjJ9JCQNCg0KDQpgYGB7cn0NCmNhdCgiRnVsbHkgaGFuZC1jb2RlZDpcbiIsbWVhbihyZXNfeSAqIHJlc193KSAvIG1lYW4ocmVzX3deMikpDQpgYGANCg0KDQo8YnI+DQoNCiMgSGFuZC1jb2RlZCByZXNpZHVhbC1vbi1yZXNpZHVhbCByZWdyZXNzaW9uIHdpdGggMi1mb2xkIGNyb3NzLWZpdHRpbmcNCg0KVGhlIHRoZW9yZXRpY2FsIHJlc3VsdHMgcmVxdWlyZSB0aGF0IHdlIHByZWRpY3QgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgb3V0LW9mLXNhbXBsZS4gVGhlIGVhc2llc3Qgd2F5IHRvIGRvIHRoaXMgaXMgdmlhIHR3by1mb2xkIGNyb3NzLWZpdHRpbmc6DQoNCi0gU3BsaXQgdGhlIHNhbXBsZSBpbiB0d28gcmFuZG9tIHN1YnNhbXBsZXMsIFMxIGFuZCBTMg0KDQotIEZvcm0gcHJlZGljdGlvbiBtb2RlbHMgaW4gUzEsIHVzZSBpdCB0byBwcmVkaWN0IGluIFMyDQoNCi0gRm9ybSBwcmVkaWN0aW9uIG1vZGVscyBpbiBTMiwgdXNlIGl0IHRvIHByZWRpY3QgaW4gUzENCg0KLSBSdW4gUk9SUiB3aXRoIHRoZSBjb21iaW5lZCBwcmVkaWN0aW9ucw0KDQoNCmBgYHtyfQ0KIyBJbml0aWFsaXplIG51aXNhbmNlIHZlY3RvcnMNCm1oYXQgPSBlaGF0ID0gcmVwKE5BLG4pDQojIERyYXcgcmFuZG9tIGluZGljZXMgZm9yIHNhbXBsZSAxDQppbmRleF9zMSA9IHNhbXBsZSgxOm4sbi8yKQ0KIyBDcmVhdGUgUzENCngxID0geFtpbmRleF9zMSxdDQp3MSA9IHdbaW5kZXhfczFdDQp5MSA9IHlbaW5kZXhfczFdDQojIENyZWF0ZSBzYW1wbGUgMiB3aXRoIHRob3NlIG5vdCBpbiBTMQ0KeDIgPSB4Wy1pbmRleF9zMSxdDQp3MiA9IHdbLWluZGV4X3MxXQ0KeTIgPSB5Wy1pbmRleF9zMV0NCiMgTW9kZWwgaW4gUzEsIHByZWRpY3QgaW4gUzINCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDEsdzEsaG9uZXN0eT1GKQ0KZWhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MSx5MSxob25lc3R5PUYpDQptaGF0Wy1pbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDIpJHByZWRpY3Rpb25zDQojIE1vZGVsIGluIFMyLCBwcmVkaWN0IGluIFMxDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgyLHcyLGhvbmVzdHk9RikNCmVoYXRbaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgxKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4Mix5Mixob25lc3R5PUYpDQptaGF0W2luZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MSkkcHJlZGljdGlvbnMNCiMgUk9SUg0KcmVzX3kgPSB5LW1oYXQNCnJlc193ID0gdy1laGF0DQpsbV9yb2J1c3QocmVzX3kgfiAwICsgcmVzX3cpDQpgYGANCg0KPGJyPg0KDQoNCiMgUmVzaWR1YWwtb24tcmVzaWR1YWwgcmVncmVzc2lvbiB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCjItZm9sZCBjcm9zcy1maXR0aW5nIGlzIGVhc3kgdG8gaW1wbGVtZW50IGJ1dCBlc3BlY2lhbGx5IGluIHNtYWxsIHNhbXBsZSBzaXplcywgdXNpbmcgb25seSA1MCUgb2YgdGhlIGRhdGEgdG8gZXN0aW1hdGUgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgbWlnaHQgbGVhZCB0byB1bnN0YWJsZSBwcmVkaWN0aW9ucy4NCg0KVGh1cywgd2UgdXNlIHRoZSBgRE1MX3BhcnRpYWxfbGluZWFyYCBmdW5jdGlvbiBvZiB0aGUgYGNhdXNhbERNTGAgcGFja2FnZSB0byBydW4gNS1mb2xkIGNyb3NzLWZpdHRpbmcuIFRoaXMgcGFja2FnZSByZXF1aXJlcyB0byBjcmVhdGUgdGhlIG1ldGhvZHMgdGhhdCB3ZSB1c2UgYmVjYXVzZSBpdCBhbGxvd3MgZm9yIGVuc2VtYmxlIG1ldGhvZHMuIEZvciBub3csIHdlIGZvY3VzIGFnYWluIG9uIHRoZSBwbGFpbiByYW5kb20gZm9yZXN0Lg0KDQpXaXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nLCB3ZSBzcGxpdCB0aGUgc2FtcGxlIGluIDUgZm9sZHMgYW5kIHVzZSA0IGZvbGRzICg4MCUgb2YgdGhlIGRhdGEpIHRvIHByZWRpY3QgdGhlIGxlZnQgb3V0IGZvbGQgKDIwJSBvZiB0aGUgZGF0YSkuIFdlIGl0ZXJhdGUgc3VjaCB0aGF0IGV2ZXJ5IGZvbGQgaXMgbGVmdCBvdXQgb25jZS4NCg0KYGBge3J9DQojIDUtZm9sZCBjcm9zcy1maXR0aW5nIHdpdGggY2F1c2FsRE1MIHBhY2thZ2UNCiMgQ3JlYXRlIGxlYXJuZXINCmZvcmVzdCA9IGNyZWF0ZV9tZXRob2QoImZvcmVzdF9ncmYiLGFyZ3M9bGlzdChob25lc3R5PUYpKQ0KIyBSdW4gcGFydGlhbGx5IGxpbmVhciBtb2RlbA0KcGxfY2Y1ID0gRE1MX3BhcnRpYWxfbGluZWFyKHksdyx4LG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQpzdW1tYXJ5KHBsX2NmNSkNCmBgYA0KDQo8YnI+DQoNCg0KIyBTaW11bGF0aW9uIHN0dWR5DQoNClRvIGNoZWNrIHdoZXRoZXIgdGhlIGFib3ZlIHJlc3VsdHMgYXJlIGp1c3QgYnkgY2hhbmNlLCB3ZSBydW4gYSBzaW11bGF0aW9uIHN0dWR5IGRyYXdpbmcgJE09MTAwJCBzYW1wbGVzIGZyb20gdGhlIERHUCBkZXNjcmliZWQgYWJvdmUgYW5kIGVzdGltYXRlIHRoZSBlZmZlY3Qgd2l0aCBzaXggZGlmZmVyZW50IG1ldGhvZHM6DQoNCi0gRG91YmxlIFNlbGVjdGlvbiB3aXRoIG9ubHkgdGhlIDUgbWFpbiB2YXJpYWJsZXMNCg0KLSBEb3VibGUgU2VsZWN0aW9uIHdpdGggdGhlIDUgbWFpbiB2YXJpYWJsZXMgYW5kIHRoZWlyIHNxdWFyZWQgdmFsdWVzDQoNCi0gRG91YmxlIFNlbGVjdGlvbiBpbmNsdWRpbmcgdXAgdG8gdGhlIHRoaXJkIG9yZGVyIHBvbHlub21pYWwgb2YgdGhlIG1haW4gdmFyaWFibGVzICh0aGUgcmVzdWx0cyBkbyBub3QgaW1wcm92ZSBmb3IgYXQgbGVhc3QgZmlmdGggb3JkZXIgd2hpbGUgaW5jcmVhc2luZyBjb21wdXRhdGlvbmFsIGNvc3RzKQ0KDQotIFBhcnRpYWxseSBsaW5lYXIgbW9kZWwgZXN0aW1hdGVkIHcvbyBjcm9zcy1maXR0aW5nDQoNCi0gUGFydGlhbGx5IGxpbmVhciBtb2RlbCBlc3RpbWF0ZWQgd2l0aCAyLWZvbGQgY3Jvc3MtZml0dGluZw0KDQotIFBhcnRpYWxseSBsaW5lYXIgbW9kZWwgZXN0aW1hdGVkIHdpdGggNS1mb2xkIGNyb3NzLWZpdHRpbmcNCg0KYGBge3J9DQojIHNldCBudW1iZXIgb2YgcmVwbGljYXRpb25zDQpuX3JlcCA9IDEwMA0KIyBJbml0aWFsaXplIHJlc3VsdHMgbWF0cml4DQpyZXN1bHRzID0gbWF0cml4KE5BLG5fcmVwLDYpDQpjb2xuYW1lcyhyZXN1bHRzKSA9IGMoIkRTMSIsIkRTMiIsIkRTMyIsIlBMIG5vIGNmIiwiUEwgY2YyIiwiUEwgY2Y1IikNCiMgcnVuIHRoZSBzaW11bGF0aW9uDQpmb3IgKGkgaW4gMTpuX3JlcCkgew0KICB4ID0gbWF0cml4KHJ1bmlmKG4qcCwtcGkscGkpLG5jb2w9cCkNCiAgdyA9IGUoeFssMV0pICsgcm5vcm0obiwwLDEpDQogIHkgPSB0aGV0YSp3ICsgc2luKHhbLDFdKSArIHJub3JtKG4sMCwxKQ0KICANCiAgIyBkb3VibGUgc2VsZWN0aW9ucw0KICByZXN1bHRzW2ksMV0gPSBybGFzc29FZmZlY3QoeCx5LHcpJGFscGhhDQogIHgyID0gY2JpbmQoeCx4XjIpDQogIHJlc3VsdHNbaSwyXSA9IHJsYXNzb0VmZmVjdCh4Mix5LHcpJGFscGhhDQogIHgzID0gY2JpbmQoeDIseF4zKQ0KICByZXN1bHRzW2ksM10gPSBybGFzc29FZmZlY3QoeDMseSx3KSRhbHBoYQ0KDQogICMgTm8gY3Jvc3MtZml0dGluZw0KICByZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgsdyxob25lc3R5PUYpDQogIGVoYXQgPSBwcmVkaWN0KHJmLG5ld2RhdGE9eCkkcHJlZGljdGlvbnMNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4LHksaG9uZXN0eT1GKQ0KICBtaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJlc195ID0geS1taGF0DQogIHJlc193ID0gdy1laGF0DQogIHJlc3VsdHNbaSw0XSA9IGxtKHJlc195IH4gMCtyZXNfdykkY29lZmZpY2llbnRzDQogIA0KICAjIDItZm9sZCBjcm9zcy1maXR0aW5nDQogIG1oYXQgPSBlaGF0ID0gcmVwKE5BLG4pDQogIGluZGV4X3MxID0gc2FtcGxlKDE6bixuLzIpDQogIHgxID0geFtpbmRleF9zMSxdDQogIHcxID0gd1tpbmRleF9zMV0NCiAgeTEgPSB5W2luZGV4X3MxXQ0KICB4MiA9IHhbLWluZGV4X3MxLF0NCiAgdzIgPSB3Wy1pbmRleF9zMV0NCiAgeTIgPSB5Wy1pbmRleF9zMV0NCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MSx3MSxob25lc3R5PUYpDQogIGVoYXRbLWluZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MikkcHJlZGljdGlvbnMNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MSx5MSxob25lc3R5PUYpDQogIG1oYXRbLWluZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MikkcHJlZGljdGlvbnMNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4Mix3Mixob25lc3R5PUYpDQogIGVoYXRbaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgxKSRwcmVkaWN0aW9ucw0KICByZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgyLHkyLGhvbmVzdHk9RikNCiAgbWhhdFtpbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDEpJHByZWRpY3Rpb25zDQogIHJlc195ID0geS1taGF0DQogIHJlc193ID0gdy1laGF0DQogIHJlc3VsdHNbaSw1XSA9IGxtKHJlc195IH4gMCtyZXNfdykkY29lZmZpY2llbnRzDQogIA0KICAjIDUtZm9sZCBjcm9zcy1maXR0aW5nDQogIHJlc3VsdHNbaSw2XSA9IERNTF9wYXJ0aWFsX2xpbmVhcih5LHcseCxtbF93PWxpc3QoZm9yZXN0KSxtbF95PWxpc3QoZm9yZXN0KSxjZj01KSRyZXN1bHRbMV0NCn0NCmBgYA0KDQpXZSBwbG90IHRoZSBoaXN0b2dyYW1zIG9mIERvdWJsZSBTZWxlY3Rpb24gd2l0aCB0aGlyZCBvcmRlciBwb2x5bm9taWFscyAodGhvc2Ugd2l0aCBsb3dlciBvcmRlciBsb29rIGlkZW50aWNhbCBiZWNhdXNlIGFsbCBvZiB0aGVtIHNlbGVjdCBubyBjb250cm9scyksIGFuZCB0aGUgdGhyZWUgcGFydGlhbGx5IGxpbmVhciBlc3RpbWF0b3JzLg0KDQpgYGB7cn0NCmFzLmRhdGEuZnJhbWUocmVzdWx0c1ssYygzOjYpXSkgJT4lIHBpdm90X2xvbmdlcihjb2xzPWV2ZXJ5dGhpbmcoKSxuYW1lc190byA9ICJFc3RpbWF0b3IiLHZhbHVlc190byA9ICJjb2VmIikgJT4lDQogIGdncGxvdChhZXMoeCA9IGNvZWYsIGZpbGwgPSBFc3RpbWF0b3IpKSArIGdlb21fZGVuc2l0eShhbHBoYT0wLjQpICsgdGhlbWVfYncoKSArIGdlb21fdmxpbmUoeGludGVyY2VwdD10aGV0YSkNCmBgYA0KDQoNClRoZSBEb3VibGUgU2VsZWN0aW9uIGVzdGltYXRvciBpcyBjbGVhcmx5IGJpYXNlZC4gVGhvc2UgYmFzZWQgb24gdGhlIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwgYWxzbyBhIGxpdHRsZSBiaXQsIGJ1dCB0aGV5IGFyZSByZW1hcmthYmx5IGNsb3NlIGdpdmVuIHRoYXQgd2UgdXNlIG9ubHkgMjAwIG9ic2VydmF0aW9ucy4NCg0KTGV0J3MgaGF2ZSBhIGNsb3NlciBsb29rIGF0IHRoZSBwZXJmb3JtYW5jZSBhbmQgY2hlY2sgdGhlIE1TRSBvZiB0aGUgZXN0aW1hdG9ycyBhbmQgaXRzIGRlY29tcG9zaXRpb24sIHdoZXJlICRcaGF0e1x0aGV0YX1fbSQgaXMgdGhlIGVzdGltYXRlZCBwYXJhbWV0ZXIgaW4gdGhlICRtJC10aCByZXBsaWNhdGlvbjoNCg0KJCRNU0UoXGhhdHtcdGhldGEpfSA9IE1eey0xfSBcc3VtX20gKFxoYXR7XHRoZXRhfV9tIC0gXHRoZXRhKV4yID0gIFx1bmRlcmJyYWNleyhcb3ZlcmJyYWNle01eey0xfSBcc3VtX20gXGhhdHtcdGhldGF9X219XntcYmFye1x0aGV0YX19IC0gXHRoZXRhKV4yfV97Qmlhc14yfSArIFx1bmRlcmJyYWNle01eey0xfSBcc3VtX20gKFxoYXR7XHRoZXRhfV9tIC0gXGJhcntcdGhldGF9KV4yfV97VmFyaWFuY2V9ICQkDQoNCmBgYHtyfQ0KZGF0YS5mcmFtZShtZXRob2QgPSBjb2xuYW1lcyhyZXN1bHRzKSwNCiAgICAgICAgICAgYmlhczIgPSBjb2xNZWFucyhyZXN1bHRzLXRoZXRhKV4yLA0KICAgICAgICAgICB2YXIgPSBjb2xNZWFucyhzd2VlcChyZXN1bHRzLDIsY29sTWVhbnMocmVzdWx0cykpXjIpKSAlPiUgDQogIHBpdm90X2xvbmdlcigtbWV0aG9kLG5hbWVzX3RvID0gIkNvbXBvbmVudCIsdmFsdWVzX3RvID0gIk1TRSIpICU+JQ0KICBnZ3Bsb3QoYWVzKGZpbGw9ZmFjdG9yKENvbXBvbmVudCxsZXZlbHM9YygidmFyIiwiYmlhczIiKSksIHk9TVNFLCB4PW1ldGhvZCkpICsgDQogIGdlb21fYmFyKHBvc2l0aW9uPSJzdGFjayIsIHN0YXQ9ImlkZW50aXR5IikgKyBzY2FsZV9maWxsX2Rpc2NyZXRlKG5hbWUgPSAiQ29tcG9uZW50IikNCmBgYA0KDQpXZSBvYnNlcnZlIHRoYXQgYWxsIERvdWJsZSBTZWxlY3Rpb24gZXN0aW1hdG9ycyBhcmUgc2V2ZXJlbHkgYmlhc2VkLCB3aGlsZSB0aGUgYmlhcyBvZiB0aGUgcGFydGlhbGx5IGxpbmVhciBlc3RpbWF0b3JzIGlzIG5lZ2xpZ2libGUuIA0KDQpUaGUgd29yc2UgcGVyZm9ybWFuY2Ugb2YgMi1mb2xkIGNyb3NzLWZpdHRpbmcgc2hvdWxkIGRpc2FwcGVhciB3aXRoIGxhcmdlciBzYW1wbGUgc2l6ZXMuDQoNCkluIHRoaXMgc2V0dGluZyBjcm9zcy1maXR0aW5nIHNlZW1zIG5vdCB0byBiZSByZXF1aXJlZC4gSG93ZXZlciwgdGhlIG5leHQgbm90ZWJvb2tzIHdpbGwgbG9vayBjbG9zZXIgaW50byB0aGlzIGlzc3VlIGFuZCBzaG93IHRoYXQgaXQgY2FuIGJlIGNydWNpYWwgdG8gZ2V0IHZhbGlkIGluZmVyZW5jZS4NCg0KDQo8YnI+DQo8YnI+DQoNCiMjIFRha2UtYXdheQ0KIA0KIC0gV2UgY2FuIHByb2dyYW0gYSBjcm9zcy1maXQgRG91YmxlIE1MIHBhcnRpYWxseSBsaW5lYXIgZXN0aW1hdG9yIGluIGxlc3MgdGhhbiAyMCBsaW5lcyBvZiBjb2RlLg0KIA0KIC0gRG91YmxlIFNlbGVjdGlvbiBjYW4gZmFpbCBpbiBub24tbGluZWFyIERHUHMsIGV2ZW4gaWYgcHJvdmlkZWQgd2l0aCBhIGxvdCBvZiBwb2x5bm9taWFscy4NCiANCiAtIEluIHNtYWxsIHNhbXBsZXMsIHdlIHNob3VsZCB1c2UgbW9yZSB0aGFuIHR3byBmb2xkcyB0byBleHBsb2l0IG1vcmUgaW5mb3JtYXRpb24gaW4gZm9ybWluZyB0aGUgcHJlZGljdGlvbiBtb2RlbHMuDQogDQo8YnI+DQo8YnI+DQogDQogDQojIyBTdWdnZXN0aW9ucyB0byBwbGF5IHdpdGggdGhlIHRveSBtb2RlbA0KDQpGZWVsIGZyZWUgdG8gcGxheSBhcm91bmQgd2l0aCB0aGUgY29kZS4gVGhpcyBpcyB1c2VmdWwgdG8gc2hhcnBlbiBhbmQgY2hhbGxlbmdlIHlvdXIgdW5kZXJzdGFuZGluZyBvZiB0aGUgbWV0aG9kcy4gVGhpbmsgYWJvdXQgdGhlIGNvbnNlcXVlbmNlcyBvZiBhIG1vZGlmaWNhdGlvbiBiZWZvcmUgeW91IHJ1biBpdCBhbmQgY2hlY2sgd2hldGhlciB0aGUgcmVzdWx0cyBhcmUgaW4gbGluZSB3aXRoIHlvdXIgZXhwZWN0YXRpb24uIFNvbWUgc3VnZ2VzdGlvbnM6DQogDQotIE1vZGlmeSBER1AgKGluY3JlYXNlIHRoZXRhLCBjb3JyZWxhdGlvbiBvZiBjb3ZhcmlhdGVzLCBjb2VmZmljaWVudHMsIG5vaXNlIHRlcm0sIC4uLikNCg0KLSBJbmNyZWFzZSB0aGUgbnVtYmVyIG9mIG9ic2VydmF0aW9ucw0KDQotIEluY3JlYXNlIGNyb3NzLWZpdHRpbmcgZm9sZHMgdG8gMTAgYW5kL29yIDIwDQoNCiA=