Load Data
The Prostate data can be found [here]. The
data is to examine the correlation between the level of
prostate-specific antigen and a number of clinical measures in men who
were about to receive a radical prostatectomy.
lcavol
: log cancer volume
lweight
: log prostate weight
age
: in years
lbph
: log of the amount of benign prostatic
hyperplasia
svi
: seminal vesicle invasion
lcp
: log of capsular penetration
gleason
: a numeric vector
pgg45
: percent of Gleason score 4 or 5
lpsa
: response
The first 8 columns are predictors; column 9 is the outcome/response.
We do not use column 10, which indicates which 67 observations were used
as the “training set” and which 30 as the test set, as described on page
48 in the ESL book.
myData = read.table(file = "https://hastie.su.domains/ElemStatLearn/datasets/prostate.data", header = TRUE)
dim(myData)
names(myData)
Remove column 10 and run a quick summary of each column of the data.
For convenience, we rename the response column with a generic name
Y.
myData = myData[, -10]
names(myData)[9] = 'Y'
summary(myData)
Produce a pair-wise scatter plot. Caution: a big figure.
pairs(myData, pch='.')
Fit a Linear Model
Fit a linear regression model using all the predictors and print the
summary of the LS results
lmfit <- lm(Y ~ ., data = myData)
summary(lmfit)
Call:
lm(formula = Y ~ ., data = myData)
Residuals:
Min 1Q Median 3Q Max
-1.76644 -0.35510 -0.00328 0.38087 1.55770
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.181561 1.320568 0.137 0.89096
lcavol 0.564341 0.087833 6.425 6.55e-09 ***
lweight 0.622020 0.200897 3.096 0.00263 **
age -0.021248 0.011084 -1.917 0.05848 .
lbph 0.096713 0.057913 1.670 0.09848 .
svi 0.761673 0.241176 3.158 0.00218 **
lcp -0.106051 0.089868 -1.180 0.24115
gleason 0.049228 0.155341 0.317 0.75207
pgg45 0.004458 0.004365 1.021 0.31000
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 0.6995 on 88 degrees of freedom
Multiple R-squared: 0.6634, Adjusted R-squared: 0.6328
F-statistic: 21.68 on 8 and 88 DF, p-value: < 2.2e-16
Check what are returned by lm
and learn how to retrieve
those results.
names(lmfit) # What are returned by "lm"?
[1] "coefficients" "residuals" "effects" "rank" "fitted.values"
[6] "assign" "qr" "df.residual" "xlevels" "call"
[11] "terms" "model"
names(summary(lmfit)) # What are returned by the summary of lmfit
[1] "call" "terms" "residuals" "coefficients" "aliased"
[6] "sigma" "df" "r.squared" "adj.r.squared" "fstatistic"
[11] "cov.unscaled"
# Regression coefficients including the intercept
lmfit$coef
lmfit$residuals[1]
length(lmfit$residuals)
Check the calculation for Residual standard error
and
Multiple R-squared
in the summary output: \[
\sigma = \sqrt{\frac{\sum_{i=1}^n r_i^2}{n - p-1}}, \quad p = \text{ #
of non-intercept predictors}
\] \[
R^2 = \frac{\sum_{i=1}^n r_i^2}{\sum_{i=1}^n (y_i - \bar{y})^2} =
\frac{\sum_{i=1}^n r_i^2}{\text{SampleVar}(y_i)\times (n-1)} =
\frac{\text{SampleVar}(r_i)}{\text{SampleVar}(y_i)}
\]
n = dim(myData)[1]
p = dim(myData)[2] - 1
# Residual standard error
c(sqrt(sum(lmfit$residuals^2)/(n- p - 1)), summary(lmfit)$sigma)
# R-squared
c(1 - sum(lmfit$residuals^2)/(var(myData$Y)*(n-1)), summary(lmfit)$r.squared)
1 - var(lmfit$residuals)/var(myData$Y)
Prediction
Predicting responses for new observations can be accomplished through
two methods:
Method 1: Begin by organizing the new
observations into a matrix or vector. Then, apply the following formula:
newX * beta + beta0, where (beta0, beta) represent the coefficients
obtained through LS regression.
Method 2: Alternatively, structure the new
observations as a data frame with identical column names as those in
myData
. Subsequently, utilize the predict
function.
To exemplify these methods, we consider two novel patients. One
individual is 50 years old, while the other is 70 years old. All other
attributes assume median values from the existing dataset encompassing
97 patients.
Method 1
apply(myData, 2, median)
lcavol lweight age lbph svi lcp gleason
1.4469190 3.6230070 65.0000000 0.3001046 0.0000000 -0.7985077 7.0000000
pgg45 Y
15.0000000 2.5915164
newx1 = c(1.45, 3.62, 50, 0.30, 0, -0.80, 7, 15) #1st patient: age = 50
newx2 = newx1
newx2[3] = 70 #2nd patient: age = 70
newx = rbind(newx1, newx2)
newx %*% lmfit$coef[-1] + lmfit$coef[1]
[,1]
newx1 2.714471
newx2 2.289507
Method 2
newdf = data.frame(newx)
names(newdf) = names(myData[, -dim(myData)[2]]) # assign col names after dropping the last col
An advantage of the predict
function is that once
columns have names, their order does not matter. So, let’s shuffle the
columns of newdf
and then predict. The result should be the
same as what is returned by Method 1.
newdf
newdf = newdf[, sample(1:dim(newdf)[2])]
newdf
predict(lmfit, newdata = newdf)
Rank Deficiency
In cases where the design matrix, including the intercept, does not
have full rank, the coefficient vector returned by R will contain some
NA elements. An NA estimate for a column signifies that that column can
be written as a linear combination of preceding columns, rendering it
redundant.
NA values do not indicate errors. They simply
indicate that in the LS fitting process, R discards columns with NA
coefficients. However, this doesn’t hinder the utility of the fitted
model for prediction purposes. The predictions derived from this model
will align with those obtained from fitting a linear regression model
excluding the columns with NA coefficients.
## Add a fake column named "junk", which is a linear combination of the first two predictors
myData$junk <- myData[, 1] + myData[, 2]
tmp.lm <- lm(Y ~ ., myData)
summary(tmp.lm)
The fitted values from the original lmfit
and the new
fit tmp.lim
are the same.
tmp.lm$fitted[1:3]
lmfit$fitted[1:3]
## drop the "junk" column
myData = myData[, !names(myData) == 'junk' ]
Training vs Test Errors
In linear regression models, as we introduce more variables, training
error (measured by RSS or MSE) consistently decreases. However, this
reduction in training error does not guarantee a corresponding decrease
in test error, which measures prediction accuracy on independent test
data. To demonstrate this, we randomly split our dataset into 60%
training and 40% test portions, progressively adding predictors. This
approach highlights how additional predictors can lower training error
while test error may not follow the same trend.
n <- dim(myData)[1] # sample size
p <- dim(myData)[2] - 1 # number of non-intercept predictors
ntrain <- round(n*0.6)
train.id <- sample(1:n, ntrain)
train.MSE <- rep(0, p)
test.MSE <- rep(0, p)
for(i in 1:p){
myfit <- lm(Y ~ ., myData[train.id, c(1:i, (p+1))])
train.Y <- myData[train.id, (p+1)]
train.Y.pred <- myfit$fitted
train.MSE[i] <- mean((train.Y - train.Y.pred)^2)
test.Y <- myData[-train.id, (p+1)]
test.Y.pred <- predict(myfit, newdata = myData[-train.id, ])
test.MSE[i] <- mean((test.Y - test.Y.pred)^2)
}
## type="n": don't plot; just set the plotting region
plot(c(1, p), range(train.MSE, test.MSE), type="n", xlab="# of variables", ylab="MSE")
points(train.MSE, col = "blue", pch = 1)
lines(train.MSE, col = "blue", pch = 1)
points(test.MSE, col = "red", pch = 2)
lines(test.MSE, col = "red", pch = 2)
Feel free to run the provided code multiple times. You’ll observe the
following patterns:
In most instances, the blue line (representing training error)
tends to be positioned below the red line (representing test error),
indicating that the training error is generally superior to the test
error. However, due to the inherent randomness, there might be instances
where the red line falls below the blue line, indicating that the test
error outperforms the training error occasionally.
In each iteration, the blue line consistently exhibits a
monotonically decreasing trend, signifying the reduction of training
error as more predictors are incorporated. On the other hand, the red
line’s trajectory may not uniformly decrease. Upon closer examination of
the differences between adjacent terms, you’ll observe negative values
consistently for the blue line, but for the red line, these differences
might encompass some positive values.
diff(train.MSE) ## always negative
diff(test.MSE) ## not always negative
Interpret LS Coefficients
How to interpret LS coefficients? LS coefficients express how changes
in predictors affect the response while holding all other predictors
constant. For instance, the coefficient for age
quantifies
the average change in the response variable for each year increase in
age, holding all other predictors constant.
It’s noteworthy that results from Simple Linear Regression (SLR),
which involves only one non-intercept predictor, might differ from
results in Multiple Linear Regression (MLR), which incorporates multiple
predictors. This divergence can arise due to correlations among
predictors.
For instance, consider the case where age
is positively
correlated with some predictors that have a positive effect on the
response. In a joint model (MLR), the coefficient for age
appears negative, seemingly contrary to its positive effect in an
isolated model (SLR). This adjustment compensates for the positive
contribution introduced by other predictors, ensuring that the overall
model accurately represents the relationships between predictors and the
response variable.
summary(lm(Y~ age, myData))
Call:
lm(formula = Y ~ age, data = myData)
Residuals:
Min 1Q Median 3Q Max
-2.90738 -0.71234 0.06967 0.66187 2.99584
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.79906 1.00793 0.793 0.4299
age 0.02629 0.01568 1.677 0.0968 .
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 1.144 on 95 degrees of freedom
Multiple R-squared: 0.02876, Adjusted R-squared: 0.01854
F-statistic: 2.813 on 1 and 95 DF, p-value: 0.09677
round(cor(myData), dig=2)
lcavol lweight age lbph svi lcp gleason pgg45 Y
lcavol 1.00 0.28 0.22 0.03 0.54 0.68 0.43 0.43 0.73
lweight 0.28 1.00 0.35 0.44 0.16 0.16 0.06 0.11 0.43
age 0.22 0.35 1.00 0.35 0.12 0.13 0.27 0.28 0.17
lbph 0.03 0.44 0.35 1.00 -0.09 -0.01 0.08 0.08 0.18
svi 0.54 0.16 0.12 -0.09 1.00 0.67 0.32 0.46 0.57
lcp 0.68 0.16 0.13 -0.01 0.67 1.00 0.51 0.63 0.55
gleason 0.43 0.06 0.27 0.08 0.32 0.51 1.00 0.75 0.37
pgg45 0.43 0.11 0.28 0.08 0.46 0.63 0.75 1.00 0.42
Y 0.73 0.43 0.17 0.18 0.57 0.55 0.37 0.42 1.00
Partial Regression Coef
Check how to retrieve the LS coefficient for age
using
Algorithm 3.1
y.star <- lm(Y ~ ., data = subset(myData, select = -age))$res
age.star <- lm(age ~ ., data = subset(myData, select = -Y))$res
tmpfit <- lm(y.star ~ age.star)
The LS coefficient for age
(from lmfit
) is
the same as the one from tmpfit
. The residuals from the two
LS models are also the same.
tmpfit$coef
sum((lmfit$res - tmpfit$res)^2)
F-test
Test a single predictor (in this case, F-test = t-test).
lmfit0 <- lm(Y ~ ., data = subset(myData, select = -age))
anova(lmfit0, lmfit)
Test multiple predictors.
lmfit0 <- lm(Y ~ ., data = myData[, -c(1:3)])
anova(lmfit0, lmfit)
Collinearity
Check the Car Seat Position Data from faraway package.
Car drivers like to adjust the seat position for their own comfort.
Car designers would find it helpful to know how different drivers will
position the seat depending on their size and age. Researchers at the HuMoSim laboratory at the University of
Michigan collected data on 38 drivers.
Age
:
Weight
:
HtShoes
: height with shoes in cm
Ht
: height without shoes in cm
Seated
: seated height in cm
Arm
: lower arm length in cm
Thigh
: thigh length in cm
Leg
: lower leg length in cm
hipcenter
: horizontal distance of the midpoint of the
hips from a fixed location in the car in mm
The researchers were interested in determining if a relationship
exists between hipcenter
and the other variables. Due to
the high correlations among the predictors, we see high R-square,
significant overall F-test, but no individual variables are
significant.
library(faraway)
data(seatpos)
pairs(seatpos, pch = ".")
summary(lm(hipcenter ~ . , data=seatpos))
## check pairwise correlation
round(cor(seatpos), dig=2)
If we remove some (almost) redundant variables, the LS results make
much more sense.
summary(lm(hipcenter ~ Age + Weight + Ht + Seated, data=seatpos))
summary(lm(hipcenter ~ Ht, data=seatpos))
LS0tCnRpdGxlOiAiUFNMOiBMaW5lYXIgUmVncmVzc2lvbiIKZGF0ZTogIkZhbGwgMjAyMyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICB0aGVtZTogcmVhZGFibGUKICAgIHRvYzogVFJVRQogICAgdG9jX2Zsb2F0OiBUUlVFCi0tLQoKIyMgTG9hZCBEYXRhCgpUaGUgKipQcm9zdGF0ZSBkYXRhKiogY2FuIGJlIGZvdW5kIFtbaGVyZV0oaHR0cHM6Ly9oYXN0aWUuc3UuZG9tYWlucy9FbGVtU3RhdExlYXJuL2RhdGEuaHRtbCldLiBUaGUgZGF0YSBpcyB0byBleGFtaW5lIHRoZSBjb3JyZWxhdGlvbiBiZXR3ZWVuIHRoZSBsZXZlbCBvZiBwcm9zdGF0ZS1zcGVjaWZpYyBhbnRpZ2VuIGFuZCBhIG51bWJlciBvZiBjbGluaWNhbCBtZWFzdXJlcyBpbiBtZW4gd2hvIHdlcmUgYWJvdXQgdG8gcmVjZWl2ZSBhIHJhZGljYWwgcHJvc3RhdGVjdG9teS4KCi0gYGxjYXZvbGA6ICBsb2cgY2FuY2VyIHZvbHVtZQotIGBsd2VpZ2h0YDogbG9nIHByb3N0YXRlIHdlaWdodAotIGBhZ2VgOiBpbiB5ZWFycwotIGBsYnBoYDogbG9nIG9mIHRoZSBhbW91bnQgb2YgYmVuaWduIHByb3N0YXRpYyBoeXBlcnBsYXNpYQotIGBzdmlgOiBzZW1pbmFsIHZlc2ljbGUgaW52YXNpb24KLSBgbGNwYDogbG9nIG9mIGNhcHN1bGFyIHBlbmV0cmF0aW9uCi0gYGdsZWFzb25gOiBhIG51bWVyaWMgdmVjdG9yCi0gYHBnZzQ1YDogcGVyY2VudCBvZiBHbGVhc29uIHNjb3JlIDQgb3IgNQotIGBscHNhYDogcmVzcG9uc2UKClRoZSBmaXJzdCA4IGNvbHVtbnMgYXJlIHByZWRpY3RvcnM7IGNvbHVtbiA5IGlzIHRoZSBvdXRjb21lL3Jlc3BvbnNlLiBXZSBkbyBub3QgdXNlIGNvbHVtbiAxMCwgd2hpY2ggaW5kaWNhdGVzIHdoaWNoIDY3IG9ic2VydmF0aW9ucyB3ZXJlIHVzZWQgYXMgdGhlICJ0cmFpbmluZyBzZXQiIGFuZCB3aGljaCAzMCBhcyB0aGUgdGVzdCBzZXQsIGFzIGRlc2NyaWJlZCBvbiBwYWdlIDQ4IGluIHRoZSBFU0wgYm9vay4gCgoKCmBgYHtyfQpteURhdGEgPSByZWFkLnRhYmxlKGZpbGUgPSAiaHR0cHM6Ly9oYXN0aWUuc3UuZG9tYWlucy9FbGVtU3RhdExlYXJuL2RhdGFzZXRzL3Byb3N0YXRlLmRhdGEiLCBoZWFkZXIgPSBUUlVFKQpkaW0obXlEYXRhKQpuYW1lcyhteURhdGEpCmBgYAoKUmVtb3ZlIGNvbHVtbiAxMCBhbmQgcnVuIGEgcXVpY2sgc3VtbWFyeSBvZiBlYWNoIGNvbHVtbiBvZiB0aGUgZGF0YS4gRm9yIGNvbnZlbmllbmNlLCB3ZSByZW5hbWUgdGhlIHJlc3BvbnNlIGNvbHVtbiB3aXRoIGEgZ2VuZXJpYyBuYW1lIFkuCgpgYGB7cn0KbXlEYXRhID0gbXlEYXRhWywgLTEwXQpuYW1lcyhteURhdGEpWzldID0gJ1knCnN1bW1hcnkobXlEYXRhKQpgYGAKClByb2R1Y2UgYSBwYWlyLXdpc2Ugc2NhdHRlciBwbG90LiBDYXV0aW9uOiBhIGJpZyBmaWd1cmUuCgpgYGB7cn0KcGFpcnMobXlEYXRhLCBwY2g9Jy4nKQpgYGAKCiMjIEZpdCBhIExpbmVhciBNb2RlbAoKRml0IGEgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgdXNpbmcgYWxsIHRoZSBwcmVkaWN0b3JzIGFuZCBwcmludCB0aGUgc3VtbWFyeSBvZiB0aGUgTFMgcmVzdWx0cwoKYGBge3J9CmxtZml0IDwtICBsbShZIH4gLiwgZGF0YSA9IG15RGF0YSkKc3VtbWFyeShsbWZpdCkKYGBgCgpDaGVjayB3aGF0IGFyZSByZXR1cm5lZCBieSBgbG1gIGFuZCBsZWFybiBob3cgdG8gcmV0cmlldmUgdGhvc2UgcmVzdWx0cy4KCmBgYHtyfQpuYW1lcyhsbWZpdCkgICMgV2hhdCBhcmUgcmV0dXJuZWQgYnkgImxtIj8KbmFtZXMoc3VtbWFyeShsbWZpdCkpICMgV2hhdCBhcmUgcmV0dXJuZWQgYnkgdGhlIHN1bW1hcnkgb2YgbG1maXQKYGBgCgpgYGB7ciwgZXZhbD1GQUxTRX0KIyBSZWdyZXNzaW9uIGNvZWZmaWNpZW50cyBpbmNsdWRpbmcgdGhlIGludGVyY2VwdApsbWZpdCRjb2VmICAgIApsbWZpdCRyZXNpZHVhbHNbMV0KbGVuZ3RoKGxtZml0JHJlc2lkdWFscykKYGBgCgpDaGVjayB0aGUgY2FsY3VsYXRpb24gZm9yIGBSZXNpZHVhbCBzdGFuZGFyZCBlcnJvcmAgYW5kIGBNdWx0aXBsZSBSLXNxdWFyZWRgIGluIHRoZSBzdW1tYXJ5IG91dHB1dDoKJCQKXHNpZ21hID0gXHNxcnR7XGZyYWN7XHN1bV97aT0xfV5uIHJfaV4yfXtuIC0gcC0xfX0sIFxxdWFkIHAgPSBcdGV4dHsgIyBvZiBub24taW50ZXJjZXB0IHByZWRpY3RvcnN9CiQkCiQkIApSXjIgPSBcZnJhY3tcc3VtX3tpPTF9Xm4gcl9pXjJ9e1xzdW1fe2k9MX1ebiAoeV9pIC0gXGJhcnt5fSleMn0gPSBcZnJhY3tcc3VtX3tpPTF9Xm4gcl9pXjJ9e1x0ZXh0e1NhbXBsZVZhcn0oeV9pKVx0aW1lcyAobi0xKX0gPSBcZnJhY3tcdGV4dHtTYW1wbGVWYXJ9KHJfaSl9e1x0ZXh0e1NhbXBsZVZhcn0oeV9pKX0KJCQKCmBgYHtyfQpuID0gZGltKG15RGF0YSlbMV0KcCA9IGRpbShteURhdGEpWzJdIC0gMQojIFJlc2lkdWFsIHN0YW5kYXJkIGVycm9yCmMoc3FydChzdW0obG1maXQkcmVzaWR1YWxzXjIpLyhuLSBwIC0gMSkpLCBzdW1tYXJ5KGxtZml0KSRzaWdtYSkgIAojIFItc3F1YXJlZApjKDEgLSBzdW0obG1maXQkcmVzaWR1YWxzXjIpLyh2YXIobXlEYXRhJFkpKihuLTEpKSwgc3VtbWFyeShsbWZpdCkkci5zcXVhcmVkKSAKMSAtIHZhcihsbWZpdCRyZXNpZHVhbHMpL3ZhcihteURhdGEkWSkKYGBgCgojIyBQcmVkaWN0aW9uCgpQcmVkaWN0aW5nIHJlc3BvbnNlcyBmb3IgbmV3IG9ic2VydmF0aW9ucyBjYW4gYmUgYWNjb21wbGlzaGVkIHRocm91Z2ggdHdvIG1ldGhvZHM6CgotICoqTWV0aG9kIDEqKjogQmVnaW4gYnkgb3JnYW5pemluZyB0aGUgbmV3IG9ic2VydmF0aW9ucyBpbnRvIGEgbWF0cml4IG9yIHZlY3Rvci4gVGhlbiwgYXBwbHkgdGhlIGZvbGxvd2luZyBmb3JtdWxhOiBuZXdYICogYmV0YSArIGJldGEwLCB3aGVyZSAoYmV0YTAsIGJldGEpIHJlcHJlc2VudCB0aGUgY29lZmZpY2llbnRzIG9idGFpbmVkIHRocm91Z2ggTFMgcmVncmVzc2lvbi4KCi0gKipNZXRob2QgMioqOiBBbHRlcm5hdGl2ZWx5LCBzdHJ1Y3R1cmUgdGhlIG5ldyBvYnNlcnZhdGlvbnMgYXMgYSBkYXRhIGZyYW1lIHdpdGggaWRlbnRpY2FsIGNvbHVtbiBuYW1lcyBhcyB0aG9zZSBpbiBgbXlEYXRhYC4gU3Vic2VxdWVudGx5LCB1dGlsaXplIHRoZSBgcHJlZGljdGAgZnVuY3Rpb24uCgpUbyBleGVtcGxpZnkgdGhlc2UgbWV0aG9kcywgd2UgY29uc2lkZXIgdHdvIG5vdmVsIHBhdGllbnRzLiBPbmUgaW5kaXZpZHVhbCBpcyA1MCB5ZWFycyBvbGQsIHdoaWxlIHRoZSBvdGhlciBpcyA3MCB5ZWFycyBvbGQuIEFsbCBvdGhlciBhdHRyaWJ1dGVzIGFzc3VtZSBtZWRpYW4gdmFsdWVzIGZyb20gdGhlIGV4aXN0aW5nIGRhdGFzZXQgZW5jb21wYXNzaW5nIDk3IHBhdGllbnRzLgoKIyMjIyBNZXRob2QgMQoKYGBge3J9CmFwcGx5KG15RGF0YSwgMiwgbWVkaWFuKQpuZXd4MSA9IGMoMS40NSwgMy42MiwgNTAsIDAuMzAsIDAsIC0wLjgwLCA3LCAxNSkgIzFzdCBwYXRpZW50OiBhZ2UgPSA1MApuZXd4MiA9IG5ld3gxCm5ld3gyWzNdID0gNzAgIzJuZCBwYXRpZW50OiBhZ2UgPSA3MApuZXd4ID0gcmJpbmQobmV3eDEsIG5ld3gyKQpuZXd4ICUqJSBsbWZpdCRjb2VmWy0xXSArIGxtZml0JGNvZWZbMV0KYGBgCgojIyMjIE1ldGhvZCAyCgoKYGBge3J9Cm5ld2RmID0gZGF0YS5mcmFtZShuZXd4KQoKIyBhc3NpZ24gY29sIG5hbWVzIGFmdGVyIGRyb3BwaW5nIHRoZSBsYXN0IGNvbApuYW1lcyhuZXdkZikgPSBuYW1lcyhteURhdGFbLCAtZGltKG15RGF0YSlbMl1dKSAKYGBgCgpBbiBhZHZhbnRhZ2Ugb2YgdGhlIGBwcmVkaWN0YCBmdW5jdGlvbiBpcyB0aGF0IG9uY2UgY29sdW1ucyBoYXZlIG5hbWVzLCB0aGVpciBvcmRlciBkb2VzIG5vdCBtYXR0ZXIuIFNvLCBsZXQncyBzaHVmZmxlIHRoZSBjb2x1bW5zIG9mIGBuZXdkZmAgYW5kIHRoZW4gcHJlZGljdC4gVGhlIHJlc3VsdCBzaG91bGQgYmUgdGhlIHNhbWUgYXMgd2hhdCBpcyByZXR1cm5lZCBieSBNZXRob2QgMS4gCgpgYGB7cn0KbmV3ZGYKbmV3ZGYgPSBuZXdkZlssIHNhbXBsZSgxOmRpbShuZXdkZilbMl0pXQpuZXdkZgpwcmVkaWN0KGxtZml0LCBuZXdkYXRhID0gbmV3ZGYpCmBgYAoKIyMgUmFuayBEZWZpY2llbmN5CgpJbiBjYXNlcyB3aGVyZSB0aGUgZGVzaWduIG1hdHJpeCwgaW5jbHVkaW5nIHRoZSBpbnRlcmNlcHQsIGRvZXMgbm90IGhhdmUgZnVsbCByYW5rLCB0aGUgY29lZmZpY2llbnQgdmVjdG9yIHJldHVybmVkIGJ5IFIgd2lsbCBjb250YWluIHNvbWUgTkEgZWxlbWVudHMuIEFuIE5BIGVzdGltYXRlIGZvciBhIGNvbHVtbiBzaWduaWZpZXMgdGhhdCB0aGF0IGNvbHVtbiBjYW4gYmUgd3JpdHRlbiBhcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiBwcmVjZWRpbmcgY29sdW1ucywgcmVuZGVyaW5nIGl0IHJlZHVuZGFudC4KCioqTkEgdmFsdWVzIGRvIG5vdCBpbmRpY2F0ZSBlcnJvcnMqKi4gVGhleSBzaW1wbHkgaW5kaWNhdGUgdGhhdCBpbiB0aGUgTFMgZml0dGluZyBwcm9jZXNzLCBSIGRpc2NhcmRzIGNvbHVtbnMgd2l0aCBOQSBjb2VmZmljaWVudHMuIEhvd2V2ZXIsIHRoaXMgZG9lc24ndCBoaW5kZXIgdGhlIHV0aWxpdHkgb2YgdGhlIGZpdHRlZCBtb2RlbCBmb3IgcHJlZGljdGlvbiBwdXJwb3Nlcy4gVGhlIHByZWRpY3Rpb25zIGRlcml2ZWQgZnJvbSB0aGlzIG1vZGVsIHdpbGwgYWxpZ24gd2l0aCB0aG9zZSBvYnRhaW5lZCBmcm9tIGZpdHRpbmcgYSBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbCBleGNsdWRpbmcgdGhlIGNvbHVtbnMgd2l0aCBOQSBjb2VmZmljaWVudHMuCgpgYGB7cn0KIyMgQWRkIGEgZmFrZSBjb2x1bW4gbmFtZWQgImp1bmsiLCB3aGljaCBpcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiB0aGUgZmlyc3QgdHdvIHByZWRpY3RvcnMKbXlEYXRhJGp1bmsgPC0gIG15RGF0YVssIDFdICsgbXlEYXRhWywgMl0KdG1wLmxtIDwtICBsbShZIH4gLiwgbXlEYXRhKQpzdW1tYXJ5KHRtcC5sbSkKYGBgCgpUaGUgZml0dGVkIHZhbHVlcyBmcm9tIHRoZSBvcmlnaW5hbCBgbG1maXRgIGFuZCB0aGUgbmV3IGZpdCBgdG1wLmxpbWAgYXJlIHRoZSBzYW1lLiAKYGBge3J9CnRtcC5sbSRmaXR0ZWRbMTozXQpsbWZpdCRmaXR0ZWRbMTozXQoKIyMgZHJvcCB0aGUgImp1bmsiIGNvbHVtbgpteURhdGEgPSBteURhdGFbLCAhbmFtZXMobXlEYXRhKSA9PSAnanVuaycgXQpgYGAKCiMjIFRyYWluaW5nIHZzIFRlc3QgRXJyb3JzCgpJbiBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbHMsIGFzIHdlIGludHJvZHVjZSBtb3JlIHZhcmlhYmxlcywgdHJhaW5pbmcgZXJyb3IgKG1lYXN1cmVkIGJ5IFJTUyBvciBNU0UpIGNvbnNpc3RlbnRseSBkZWNyZWFzZXMuIEhvd2V2ZXIsIHRoaXMgcmVkdWN0aW9uIGluIHRyYWluaW5nIGVycm9yIGRvZXMgbm90IGd1YXJhbnRlZSBhIGNvcnJlc3BvbmRpbmcgZGVjcmVhc2UgaW4gdGVzdCBlcnJvciwgd2hpY2ggbWVhc3VyZXMgcHJlZGljdGlvbiBhY2N1cmFjeSBvbiBpbmRlcGVuZGVudCB0ZXN0IGRhdGEuIFRvIGRlbW9uc3RyYXRlIHRoaXMsIHdlIHJhbmRvbWx5IHNwbGl0IG91ciBkYXRhc2V0IGludG8gNjBcJSB0cmFpbmluZyBhbmQgNDBcJSB0ZXN0IHBvcnRpb25zLCBwcm9ncmVzc2l2ZWx5IGFkZGluZyBwcmVkaWN0b3JzLiBUaGlzIGFwcHJvYWNoIGhpZ2hsaWdodHMgaG93IGFkZGl0aW9uYWwgcHJlZGljdG9ycyBjYW4gbG93ZXIgdHJhaW5pbmcgZXJyb3Igd2hpbGUgdGVzdCBlcnJvciBtYXkgbm90IGZvbGxvdyB0aGUgc2FtZSB0cmVuZC4KCmBgYHtyfQpuIDwtIGRpbShteURhdGEpWzFdICMgc2FtcGxlIHNpemUKcCA8LSAgZGltKG15RGF0YSlbMl0gLSAxICMgbnVtYmVyIG9mIG5vbi1pbnRlcmNlcHQgcHJlZGljdG9ycwoKbnRyYWluIDwtICByb3VuZChuKjAuNikKdHJhaW4uaWQgPC0gIHNhbXBsZSgxOm4sIG50cmFpbikKdHJhaW4uTVNFIDwtICByZXAoMCwgcCkKdGVzdC5NU0UgPC0gIHJlcCgwLCBwKQoKZm9yKGkgaW4gMTpwKXsKICBteWZpdCA8LSAgbG0oWSB+IC4sIG15RGF0YVt0cmFpbi5pZCwgYygxOmksIChwKzEpKV0pCiAgdHJhaW4uWSA8LSAgbXlEYXRhW3RyYWluLmlkLCAocCsxKV0KICB0cmFpbi5ZLnByZWQgPC0gIG15Zml0JGZpdHRlZAogIHRyYWluLk1TRVtpXSA8LSAgbWVhbigodHJhaW4uWSAtIHRyYWluLlkucHJlZCleMikKICAKICB0ZXN0LlkgPC0gIG15RGF0YVstdHJhaW4uaWQsIChwKzEpXQogIHRlc3QuWS5wcmVkIDwtICBwcmVkaWN0KG15Zml0LCBuZXdkYXRhID0gbXlEYXRhWy10cmFpbi5pZCwgXSkKICB0ZXN0Lk1TRVtpXSA8LSAgbWVhbigodGVzdC5ZIC0gdGVzdC5ZLnByZWQpXjIpCn0KCiMjIHR5cGU9Im4iOiBkb24ndCBwbG90OyBqdXN0IHNldCB0aGUgcGxvdHRpbmcgcmVnaW9uCiAgcGxvdChjKDEsIHApLCByYW5nZSh0cmFpbi5NU0UsIHRlc3QuTVNFKSwgdHlwZT0ibiIsIHhsYWI9IiMgb2YgdmFyaWFibGVzIiwgeWxhYj0iTVNFIikKICBwb2ludHModHJhaW4uTVNFLCBjb2wgPSAiYmx1ZSIsIHBjaCA9IDEpCiAgbGluZXModHJhaW4uTVNFLCBjb2wgPSAiYmx1ZSIsIHBjaCA9IDEpCiAgcG9pbnRzKHRlc3QuTVNFLCBjb2wgPSAicmVkIiwgcGNoID0gMikKICBsaW5lcyh0ZXN0Lk1TRSwgY29sID0gInJlZCIsIHBjaCA9IDIpCmBgYAoKRmVlbCBmcmVlIHRvIHJ1biB0aGUgcHJvdmlkZWQgY29kZSBtdWx0aXBsZSB0aW1lcy4gWW91J2xsIG9ic2VydmUgdGhlIGZvbGxvd2luZyBwYXR0ZXJuczoKCi0gSW4gbW9zdCBpbnN0YW5jZXMsIHRoZSBibHVlIGxpbmUgKHJlcHJlc2VudGluZyB0cmFpbmluZyBlcnJvcikgdGVuZHMgdG8gYmUgcG9zaXRpb25lZCBiZWxvdyB0aGUgcmVkIGxpbmUgKHJlcHJlc2VudGluZyB0ZXN0IGVycm9yKSwgaW5kaWNhdGluZyB0aGF0IHRoZSB0cmFpbmluZyBlcnJvciBpcyBnZW5lcmFsbHkgc3VwZXJpb3IgdG8gdGhlIHRlc3QgZXJyb3IuIEhvd2V2ZXIsIGR1ZSB0byB0aGUgaW5oZXJlbnQgcmFuZG9tbmVzcywgdGhlcmUgbWlnaHQgYmUgaW5zdGFuY2VzIHdoZXJlIHRoZSByZWQgbGluZSBmYWxscyBiZWxvdyB0aGUgYmx1ZSBsaW5lLCBpbmRpY2F0aW5nIHRoYXQgdGhlIHRlc3QgZXJyb3Igb3V0cGVyZm9ybXMgdGhlIHRyYWluaW5nIGVycm9yIG9jY2FzaW9uYWxseS4KCi0gSW4gZWFjaCBpdGVyYXRpb24sIHRoZSBibHVlIGxpbmUgY29uc2lzdGVudGx5IGV4aGliaXRzIGEgbW9ub3RvbmljYWxseSBkZWNyZWFzaW5nIHRyZW5kLCBzaWduaWZ5aW5nIHRoZSByZWR1Y3Rpb24gb2YgdHJhaW5pbmcgZXJyb3IgYXMgbW9yZSBwcmVkaWN0b3JzIGFyZSBpbmNvcnBvcmF0ZWQuIE9uIHRoZSBvdGhlciBoYW5kLCB0aGUgcmVkIGxpbmUncyB0cmFqZWN0b3J5IG1heSBub3QgdW5pZm9ybWx5IGRlY3JlYXNlLiBVcG9uIGNsb3NlciBleGFtaW5hdGlvbiBvZiB0aGUgZGlmZmVyZW5jZXMgYmV0d2VlbiBhZGphY2VudCB0ZXJtcywgIHlvdSdsbCBvYnNlcnZlIG5lZ2F0aXZlIHZhbHVlcyBjb25zaXN0ZW50bHkgZm9yIHRoZSBibHVlIGxpbmUsIGJ1dCBmb3IgdGhlIHJlZCBsaW5lLCB0aGVzZSBkaWZmZXJlbmNlcyBtaWdodCBlbmNvbXBhc3Mgc29tZSBwb3NpdGl2ZSB2YWx1ZXMuIAoKYGBge3IsIGV2YWw9RkFMU0V9CmRpZmYodHJhaW4uTVNFKSAjIyBhbHdheXMgbmVnYXRpdmUKZGlmZih0ZXN0Lk1TRSkgICMjIG5vdCBhbHdheXMgbmVnYXRpdmUKYGBgCgojIyBJbnRlcnByZXQgTFMgQ29lZmZpY2llbnRzCgpIb3cgdG8gaW50ZXJwcmV0IExTIGNvZWZmaWNpZW50cz8gTFMgY29lZmZpY2llbnRzIGV4cHJlc3MgaG93IGNoYW5nZXMgaW4gcHJlZGljdG9ycyBhZmZlY3QgdGhlIHJlc3BvbnNlIHdoaWxlIGhvbGRpbmcgYWxsIG90aGVyIHByZWRpY3RvcnMgY29uc3RhbnQuIEZvciBpbnN0YW5jZSwgdGhlIGNvZWZmaWNpZW50IGZvciBgYWdlYCBxdWFudGlmaWVzIHRoZSBhdmVyYWdlIGNoYW5nZSBpbiB0aGUgcmVzcG9uc2UgdmFyaWFibGUgZm9yIGVhY2ggeWVhciBpbmNyZWFzZSBpbiBhZ2UsICoqaG9sZGluZyBhbGwgb3RoZXIgcHJlZGljdG9ycyBjb25zdGFudCoqLiAKCkl0J3Mgbm90ZXdvcnRoeSB0aGF0IHJlc3VsdHMgZnJvbSBTaW1wbGUgTGluZWFyIFJlZ3Jlc3Npb24gKFNMUiksIHdoaWNoIGludm9sdmVzIG9ubHkgb25lIG5vbi1pbnRlcmNlcHQgcHJlZGljdG9yLCBtaWdodCBkaWZmZXIgZnJvbSByZXN1bHRzIGluIE11bHRpcGxlIExpbmVhciBSZWdyZXNzaW9uIChNTFIpLCB3aGljaCBpbmNvcnBvcmF0ZXMgbXVsdGlwbGUgcHJlZGljdG9ycy4gVGhpcyBkaXZlcmdlbmNlIGNhbiBhcmlzZSBkdWUgdG8gY29ycmVsYXRpb25zIGFtb25nIHByZWRpY3RvcnMuCiAKRm9yIGluc3RhbmNlLCBjb25zaWRlciB0aGUgY2FzZSB3aGVyZSBgYWdlYCBpcyBwb3NpdGl2ZWx5IGNvcnJlbGF0ZWQgd2l0aCBzb21lIHByZWRpY3RvcnMgdGhhdCBoYXZlIGEgcG9zaXRpdmUgZWZmZWN0IG9uIHRoZSByZXNwb25zZS4gSW4gYSBqb2ludCBtb2RlbCAoTUxSKSwgdGhlIGNvZWZmaWNpZW50IGZvciBgYWdlYCBhcHBlYXJzIG5lZ2F0aXZlLCBzZWVtaW5nbHkgY29udHJhcnkgdG8gaXRzIHBvc2l0aXZlIGVmZmVjdCBpbiBhbiBpc29sYXRlZCBtb2RlbCAoU0xSKS4gVGhpcyBhZGp1c3RtZW50IGNvbXBlbnNhdGVzIGZvciB0aGUgcG9zaXRpdmUgY29udHJpYnV0aW9uIGludHJvZHVjZWQgYnkgb3RoZXIgcHJlZGljdG9ycywgZW5zdXJpbmcgdGhhdCB0aGUgb3ZlcmFsbCBtb2RlbCBhY2N1cmF0ZWx5IHJlcHJlc2VudHMgdGhlIHJlbGF0aW9uc2hpcHMgYmV0d2VlbiBwcmVkaWN0b3JzIGFuZCB0aGUgcmVzcG9uc2UgdmFyaWFibGUuCiAKCmBgYHtyfQpzdW1tYXJ5KGxtKFl+IGFnZSwgbXlEYXRhKSkKcm91bmQoY29yKG15RGF0YSksIGRpZz0yKQpgYGAKCgojIyBQYXJ0aWFsIFJlZ3Jlc3Npb24gQ29lZgoKQ2hlY2sgaG93IHRvIHJldHJpZXZlIHRoZSBMUyBjb2VmZmljaWVudCBmb3IgYGFnZWAgdXNpbmcgQWxnb3JpdGhtIDMuMQoKYGBge3J9Cnkuc3RhciA8LSAgbG0oWSB+IC4sIGRhdGEgPSBzdWJzZXQobXlEYXRhLCBzZWxlY3QgPSAtYWdlKSkkcmVzCmFnZS5zdGFyIDwtICBsbShhZ2UgfiAuLCBkYXRhID0gc3Vic2V0KG15RGF0YSwgc2VsZWN0ID0gLVkpKSRyZXMKdG1wZml0IDwtICBsbSh5LnN0YXIgfiBhZ2Uuc3RhcikKYGBgCgpUaGUgTFMgY29lZmZpY2llbnQgZm9yIGBhZ2VgIChmcm9tIGBsbWZpdGApIGlzIHRoZSBzYW1lIGFzIHRoZSBvbmUgZnJvbSBgdG1wZml0YC4gVGhlIHJlc2lkdWFscyBmcm9tIHRoZSB0d28gTFMgbW9kZWxzIGFyZSBhbHNvIHRoZSBzYW1lLgoKYGBge3J9CnRtcGZpdCRjb2VmCnN1bSgobG1maXQkcmVzIC0gdG1wZml0JHJlcyleMikKYGBgCgojIyBGLXRlc3QKClRlc3QgYSBzaW5nbGUgcHJlZGljdG9yIChpbiB0aGlzIGNhc2UsIEYtdGVzdCA9IHQtdGVzdCkuCgpgYGB7cn0KbG1maXQwIDwtIGxtKFkgfiAuLCBkYXRhID0gc3Vic2V0KG15RGF0YSwgc2VsZWN0ID0gLWFnZSkpCmFub3ZhKGxtZml0MCwgbG1maXQpCmBgYAoKVGVzdCBtdWx0aXBsZSBwcmVkaWN0b3JzLgoKYGBge3J9CmxtZml0MCA8LSBsbShZIH4gLiwgZGF0YSA9IG15RGF0YVssIC1jKDE6MyldKQphbm92YShsbWZpdDAsIGxtZml0KQpgYGAKCgojIyBDb2xsaW5lYXJpdHkKCkNoZWNrIHRoZSBDYXIgU2VhdCBQb3NpdGlvbiBEYXRhIGZyb20gZmFyYXdheSBwYWNrYWdlLgoKQ2FyIGRyaXZlcnMgbGlrZSB0byBhZGp1c3QgdGhlIHNlYXQgcG9zaXRpb24gZm9yIHRoZWlyIG93biBjb21mb3J0LiBDYXIgZGVzaWduZXJzIHdvdWxkIGZpbmQgaXQgaGVscGZ1bCB0byBrbm93IGhvdyBkaWZmZXJlbnQgZHJpdmVycyB3aWxsIHBvc2l0aW9uIHRoZSBzZWF0IGRlcGVuZGluZyBvbiB0aGVpciBzaXplIGFuZCBhZ2UuIFJlc2VhcmNoZXJzIGF0IHRoZSBbSHVNb1NpbSBsYWJvcmF0b3J5XShodHRwOi8vaHVtb3NpbS5vcmcvKSBhdCB0aGUgVW5pdmVyc2l0eSBvZiBNaWNoaWdhbiBjb2xsZWN0ZWQgZGF0YSBvbiAzOCBkcml2ZXJzLgoKLSBgQWdlYDoKLSBgV2VpZ2h0YDoKLSBgSHRTaG9lc2A6IGhlaWdodCB3aXRoIHNob2VzIGluIGNtCi0gYEh0YDogaGVpZ2h0IHdpdGhvdXQgc2hvZXMgaW4gY20KLSBgU2VhdGVkYDogc2VhdGVkIGhlaWdodCBpbiBjbQotIGBBcm1gOiBsb3dlciBhcm0gbGVuZ3RoIGluIGNtCi0gYFRoaWdoYDogdGhpZ2ggbGVuZ3RoIGluIGNtCi0gYExlZ2A6IGxvd2VyIGxlZyBsZW5ndGggaW4gY20KLSBgaGlwY2VudGVyYDogaG9yaXpvbnRhbCBkaXN0YW5jZSBvZiB0aGUgbWlkcG9pbnQgb2YgdGhlIGhpcHMgZnJvbSBhIGZpeGVkIGxvY2F0aW9uIGluIHRoZSBjYXIgaW4gbW0KClRoZSByZXNlYXJjaGVycyB3ZXJlIGludGVyZXN0ZWQgaW4gZGV0ZXJtaW5pbmcgaWYgYSByZWxhdGlvbnNoaXAgZXhpc3RzIGJldHdlZW4gYGhpcGNlbnRlcmAgYW5kIHRoZSBvdGhlciB2YXJpYWJsZXMuIER1ZSB0byB0aGUgaGlnaCBjb3JyZWxhdGlvbnMgYW1vbmcgdGhlIHByZWRpY3RvcnMsIHdlIHNlZSBoaWdoIFItc3F1YXJlLCBzaWduaWZpY2FudCBvdmVyYWxsIEYtdGVzdCwgYnV0IG5vIGluZGl2aWR1YWwgdmFyaWFibGVzIGFyZSBzaWduaWZpY2FudC4KCmBgYHtyfQpsaWJyYXJ5KGZhcmF3YXkpCmRhdGEoc2VhdHBvcykKcGFpcnMoc2VhdHBvcywgcGNoID0gIi4iKQpzdW1tYXJ5KGxtKGhpcGNlbnRlciB+IC4gLCBkYXRhPXNlYXRwb3MpKQojIyBjaGVjayBwYWlyd2lzZSBjb3JyZWxhdGlvbgpyb3VuZChjb3Ioc2VhdHBvcyksIGRpZz0yKQpgYGAKCklmIHdlIHJlbW92ZSBzb21lIChhbG1vc3QpIHJlZHVuZGFudCB2YXJpYWJsZXMsIHRoZSBMUyByZXN1bHRzIG1ha2UgbXVjaCBtb3JlIHNlbnNlLgoKYGBge3J9CnN1bW1hcnkobG0oaGlwY2VudGVyIH4gQWdlICsgV2VpZ2h0ICsgSHQgKyBTZWF0ZWQsIGRhdGE9c2VhdHBvcykpCnN1bW1hcnkobG0oaGlwY2VudGVyIH4gSHQsIGRhdGE9c2VhdHBvcykpCmBgYA==