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=