Problem 1: Example with LASSO
The file available at https://charlotte-ngs.github.io/gelasmss2021/data/asm_ex06_p01_lasso.txt contains a dataset with genotypes from 100 SNP-Loci. In addition to the genomic information, the dataset also holds observations of a certain trait for 50 animals. The dataset can be read into a matrix in R with the following statement.
mat_lasso_data <- matrix(scan("https://charlotte-ngs.github.io/gelasmss2021/data/asm_ex06_p01_lasso.txt"), nrow = 50, byrow = TRUE)
Let us have a look at the first 5 rows and the first 5 columns of the matrix that stores the dataset.
mat_lasso_data[1:n_nr_row,1:n_nr_col]
[,1] [,2] [,3] [,4] [,5]
[1,] -40.39872 -1 0 -1 -1
[2,] -46.35871 -1 -1 -1 0
[3,] -33.60278 -1 -1 -1 -1
[4,] -48.47177 0 -1 -1 -1
[5,] -38.82089 -1 -1 0 -1
From this output, we can see that the observations of all animals can be found in the first column of the data matrix mat_lasso_data
. In columns 2 to 101 of the data matrix there are the genotypes of all SNP loci. The linear model is fitted with LASSO using the function glmnet()
from the package glmnet
. The SNP genotypes are used as explanatory variables and the observations are the response variables.
Your Tasks
- Use the following R-Statement to estimate the SNP-effects using LASSO
require(glmnet)
fitsnp <- glmnet(x = mat_lasso_data[, -1], y = mat_lasso_data[, 1])
- Visualize the dependency between the value of the penalty term \(\lambda\) and the number of explanatory variables which are not \(0\).
plot(fitsnp, xvar = "lambda", label = TRUE)
- Use a cross-validation to determine the value of \(\lambda\).
cvfitsnp <- cv.glmnet(x = mat_lasso_data[, -1], y = mat_lasso_data[, 1])
- Show the results of the cross-validation in a plot using the function
plot()
.
plot(cvfitsnp)
- In the plot of the cross-validation results there are two dashed lines which both indicated special values for \(\lambda\). The first value is the minimum of all \(\lambda\)-values and the second is the one that sets the most explanatory variables to \(0\) with the restriction that the sum of squared errors is not further away than one standard deviation from its minimum. The two \(\lambda\)-values are obtained with
cvfitsnp$lambda.min
cvfitsnp$lambda.1se
- Find all coefficients which are not \(0\) for both \(\lambda\)-values and compare them to the true values taken from the simulation.
coefmin <- coef(cvfitsnp, s = "lambda.min")
(cofminnz <- coefmin[coefmin[, 1] != 0,])
coef1se <- coef(cvfitsnp, s = "lambda.1se")
(coef1senz <- coef1se[coef1se[, 1] != 0, ])
The true SNP-positions from the simulation are:
(vec_sign_snp_idx <- c(73,54,26,30,7))
[1] 73 54 26 30 7
Your Solution
Run the R-statements as they are shown in the hints. This will result in a set of SNP-positions with an effect that is different from \(0\). These SNP-positions can then be compared to the true positions from the simulation. The LASSO-estimates of the SNP-effects are obtained with the following steps.
# fit the linear model with glmnet
# Visualize the results using the plot() function
# Determine lambda using cross-validation with the function cv.glmnet()
# Show the results of the cross-validation using the plot() function
# determine the two lambda values, given in the above plot
# determine the non-zero coefficients for the SNP-effects which are not zero for the two lambda values
# compare the SNP-positions with a non-zero effect to the true SNP positions used in the simulation
Problem 2: Bayesian Regression Analysis
Given is the earlier used dataset of breast circumference
and body weight
.
Dataset for Regression of Body Weight on Breast Circumference for ten Animals
1 |
176 |
471 |
2 |
177 |
463 |
3 |
178 |
481 |
4 |
179 |
470 |
5 |
179 |
496 |
6 |
180 |
491 |
7 |
181 |
518 |
8 |
182 |
511 |
9 |
183 |
510 |
10 |
184 |
541 |
The model that is used is a simple linear regression model given by
\[y_i = \beta_0 + \beta_1 * x_i + \epsilon_i\].
where \(y_i\) corresponds to the body weight of animal \(i\), \(x_i\) is the breast circumference of animal \(i\), \(\beta_0\) is the unknown intercept and \(\beta_1\) is the unknown regression coefficient. For reasons of simplicity, we assume the residual variance \(\sigma^2\) to be known. For the later computations, we insert the estimate that is obtained from the lm()
function. This value corresponds to \(\sigma^2 = 122.8\).
Bayesian Estimation Of Unknowns
As already mentioned during the lecture, Bayesian estimates of unknowns are based on the posterior distribution of the unknowns given the knowns. For our regression model the unknowns correspond to
\[\beta = \left[\begin{array}{c}\beta_0 \\ \beta_1 \end{array}\right]\]
The posterior distribution of the unknowns given the knowns is \(f(\beta | y)\). Using Bayesโ Theorem we can write \(f(\beta | y)\) as
\[\begin{align}
f(\beta | y) & = \frac{f(\beta, y)}{f(y)} \notag \\
& = \frac{f(y | \beta)f(\beta)}{f(y)} \notag \\
& \propto f(y | \beta)f(\beta) \notag
\end{align}\]
When we do not have any specific prior knowledge about \(\beta\), the prior distribution \(f(\beta)\) for the unknown \(\beta\) is set to a constant. Therefore we can write
\[\begin{align}
f(\beta | y) & \propto f(y | \beta)f(\beta) \notag \\
& \propto f(y | \beta) \notag
\end{align}\]
Assuming a normal distribution for the data causes the likelihood \(f(y | \beta)\) to be a multivariate normal distribution.
\[\begin{align}
f(\beta | y) & \propto f(y | \beta) \notag \\
& = (2\pi\sigma^2)^{-n/2} exp \left\{ -{1 \over 2} \frac{(y - X\beta)^T(y - X\beta)}{\sigma^2} \right\}
(\#eq:BayesLikelihood)
\end{align}\]
The above expression @ref(eq:BayesLikelihood) is an \(n-\) dimensional normal distribution with expected value \(X\beta\) and variance-covariance matrix corresponding to \(I\sigma^2\). But because we have just two unknowns \(\beta_0\) and \(\beta_1\) the posterior distribution \(f(\beta | y)\) must have two dimensions and not \(n\). The following re-arrangement can solve this problem. Let us set the variable \(Q\) to
\[Q = (y - X\beta)^T(y - X\beta) = y^Ty - 2y^TX\beta + \beta^T(X^TX)\beta\]
Introducing the least squares estimate \(\hat{\beta} = (X^TX)^{-1}X^Ty\) into the above equation by replacing \(y^TX\) with \(\hat{\beta}^T(X^TX)\) results in
\[Q = y^Ty - 2 \hat{\beta}^T(X^TX)\beta + \beta^T(X^TX)\beta = y^Ty + (\beta-\hat{\beta})^T(X^TX)(\beta-\hat{\beta}) - \hat{\beta}^T(X^TX)\hat{\beta}\]
Inserting this last result back into @ref(eq:BayesLikelihood) gives
\[\begin{align}
f(\beta | y) & \propto f(y | \beta) \notag \\
& = (2\pi\sigma^2)^{-n/2} exp \left\{ -{1 \over 2} \frac{(y - X\beta)^T(y - X\beta)}{\sigma^2} \right\} \notag \\
& = (2\pi\sigma^2)^{-n/2} exp \left\{ -{1 \over 2} \frac{y^Ty + (\beta-\hat{\beta})^T(X^TX)(\beta-\hat{\beta}) - \hat{\beta}^T(X^TX)\hat{\beta}}{\sigma^2} \right\} \notag \\
& = (2\pi\sigma^2)^{-n/2} \left[exp \left\{ -{1 \over 2} \frac{y^Ty}{\sigma^2}\right\}
* exp\left\{ -{1 \over 2} \frac{ (\beta-\hat{\beta})^T(X^TX)(\beta-\hat{\beta})}{\sigma^2} \right\}
* exp\left\{ -{1 \over 2} \frac{ - \hat{\beta}^T(X^TX)\hat{\beta}}{\sigma^2} \right\} \right] \notag \\
& \propto exp\left\{ -{1 \over 2} \frac{ (\beta-\hat{\beta})^T(X^TX)(\beta-\hat{\beta})}{\sigma^2} \right\}
(\#eq:BayesLikelihoodRef)
\end{align}\]
The last proportionality results from the fact that only the term depending on \(\beta\) is retained. All other terms not depending on \(\beta\) are constant factors with respect to \(\beta\) and can therefore be dropped. Thus \(f(\beta|y)\) can be written as
\[f(\beta | y) \propto exp\left\{ -{1 \over 2} \frac{ (\beta-\hat{\beta})^T(X^TX)(\beta-\hat{\beta})}{\sigma^2} \right\}\] which is recognized as proportional to a two dimensional normal density with mean \(\hat{\beta}\) and variance \((X^TX)^{-1}\sigma^2\). Thus in the simple setting the mean of the posterior mean can already be seen from the above formula. But in a more complex setting, the posterior distribution does not have a standard form and we need to setup a sampling scheme which allows us to draw random numbers from the posterior distribution. The sampling scheme that we are introducing here is called the Gibbs Sampler.
Gibbs Sampler for \(\beta\)
The simple regression model that we are using for the breast circumference and the body weight data can be written in matrix-vector notation as
\[y = 1\beta_0 + x\beta_1 + \epsilon\]
In the Gibbs sampling scheme both unknowns \(\beta_0\) and \(\beta_1\) are sampled from their full conditional distributions. For \(\beta_0\) the full conditional posterior distribution is \(f(\beta_0 | \beta_1, y)\) which is computed for the current value of \(\beta_1\). Separating \(\beta_0\) from the other unknowns yields the linear model
\[w_0 = 1\beta_0 + \epsilon\] where \(w_0 = y - x\beta_1\). The least squares estimator of \(\beta_0\) is
\[\hat{\beta}_0 = (1^T1)^{-1}1^Tw_0\] with variance
\[var(\hat{\beta}_0) = (1^T1)^{-1} \sigma^2\]
Applying the same strategy as for \(f(\beta | y)\), it can be shown that \(f(\beta_0 | \beta_1, y)\) is a normal distribution with mean \(\hat{\beta}_0\) as mean and \((1^T1)^{-1} \sigma^2\) as variance. The full-conditional posterior of \(\beta_1\) can be derived the same way, leading to
\[\hat{\beta}_1 = (x^Tx)^{-1}x^Tw_1\]
with variance \(var(\hat{\beta}_1) = (x^Tx)^{-1} \sigma^2\) where \(w_1 = y - 1\beta_0\).
Your Task
- Create a Gibbs Sampling scheme for the dataset shown in Table @ref(tab:dataregression).
- Use the mean of the generated samples as an estimate for the unknowns \(\beta_0\) and \(\beta_1\).
Your Solution
In the problem description, the residual variance \(\sigma^2\) is assumed to be known. Instead of using a fixed value, we use the estimate that can be computed based on the residuals from a least squares model.
# compute residual variance based on residuals of fitting lm() to data
# prepare the vector y of observations and the matrix X for the intercept and the predictor variable
# initialise a vector beta for the current estimate and a vector meanBeta for the mean of all the samples
# loop over a given number of iterations to produce the samples for the unknowns
Latest Changes: 2021-04-12 01:02:11 (peter)
LS0tCnRpdGxlOiBBcHBsaWVkIFN0YXRpc3RpY2FsIE1ldGhvZHMgLSBOb3RlYm9vayA2CmF1dGhvcjogUGV0ZXIgdm9uIFJvaHIKZGF0ZTogMjAyMS0wMy0yOQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0KIyBrbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IEZBTFNFLCByZXN1bHRzID0gJ2FzaXMnLCBmaWcucG9zID0gJ0gnKQprbml0cjo6a25pdF9ob29rcyRzZXQoaG9va19jb252ZXJ0X29kZyA9IHJtZGhlbHA6Omhvb2tfY29udmVydF9vZGcpCnZlY19wa2cgPC0gYygiZ2xtbmV0IikKaWYgKCFpcy5lbGVtZW50KHZlY19wa2csIGluc3RhbGxlZC5wYWNrYWdlcygpKSkKICBpbnN0YWxsLnBhY2thZ2VzKHZlY19wa2csIGRlcGVuZGVuY2llcyA9IFRSVUUpCmBgYAoKCiMjIFByb2JsZW0gMTogRXhhbXBsZSB3aXRoIExBU1NPCgpgYGB7ciBwMDEtc2V0dXAsIGVjaG89RkFMU0V9Cm5fbnJfYW5pIDwtIDUwCm5fbnJfc25wIDwtIDEwMApzX2xhc3NvX2RhdGFfZmlsZW5hbWUgPC0gImFzbV9leDA2X3AwMV9sYXNzby50eHQiCnNfY291cnNlX3VybCA8LSAiaHR0cHM6Ly9jaGFybG90dGUtbmdzLmdpdGh1Yi5pby9nZWxhc21zczIwMjEiCnNfbGFzc29fZGF0YV9wYXRoIDwtIGZpbGUucGF0aChzX2NvdXJzZV91cmwsICJkYXRhIiwgc19sYXNzb19kYXRhX2ZpbGVuYW1lKQpgYGAKClRoZSBmaWxlIGF2YWlsYWJsZSBhdCBgciBzX2xhc3NvX2RhdGFfcGF0aGAgY29udGFpbnMgYSBkYXRhc2V0IHdpdGggZ2Vub3R5cGVzIGZyb20gYHIgbl9ucl9zbnBgIFNOUC1Mb2NpLiBJbiBhZGRpdGlvbiB0byB0aGUgZ2Vub21pYyBpbmZvcm1hdGlvbiwgdGhlIGRhdGFzZXQgYWxzbyBob2xkcyBvYnNlcnZhdGlvbnMgb2YgYSBjZXJ0YWluIHRyYWl0IGZvciBgciBuX25yX2FuaWAgYW5pbWFscy4gVGhlIGRhdGFzZXQgY2FuIGJlIHJlYWQgaW50byBhIG1hdHJpeCBpbiBSIHdpdGggdGhlIGZvbGxvd2luZyBzdGF0ZW1lbnQuCgpgYGB7ciBkYXRhLXNjYW4tc3RtdCwgZWNobz1GQUxTRSwgcmVzdWx0cz0nYXNpcyd9CnNfaW5wdXRfY21kIDwtIHBhc3RlMCgibWF0X2xhc3NvX2RhdGEgPC0gbWF0cml4KHNjYW4oXCIiLCBzX2xhc3NvX2RhdGFfcGF0aCwgIlwiKSwgbnJvdyA9ICIsIG5fbnJfYW5pLCAiLCBieXJvdyA9IFRSVUUpIiwgY29sbGFwc2UgPSAiIikKY2F0KCJcXHNjcmlwdHNpemVcbmAiLCBzX2lucHV0X2NtZCwgImBcblxcbm9ybWFsc2l6ZSBcbiIsIHNlcCA9ICIiKQpgYGAKCmBgYHtyIGV2YWwtc2Nhbi1zdG10LCBlY2hvPUZBTFNFLCBtZXNzYWdlPUZBTFNFLCByZXN1bHRzPSdoaWRlJ30KZXZhbChwYXJzZSh0ZXh0ID0gc19pbnB1dF9jbWQpKQpuX25yX3JvdyA8LSA1Cm5fbnJfY29sIDwtIDUKYGBgCgpMZXQgdXMgaGF2ZSBhIGxvb2sgYXQgdGhlIGZpcnN0IGByIG5fbnJfcm93YCByb3dzIGFuZCB0aGUgZmlyc3QgYHIgbl9ucl9jb2xgIGNvbHVtbnMgb2YgdGhlIG1hdHJpeCB0aGF0IHN0b3JlcyB0aGUgZGF0YXNldC4KCmBgYHtyLCByZXN1bHRzPSdtYXJrdXAnfQptYXRfbGFzc29fZGF0YVsxOm5fbnJfcm93LDE6bl9ucl9jb2xdCmBgYAoKRnJvbSB0aGlzIG91dHB1dCwgd2UgY2FuIHNlZSB0aGF0IHRoZSBvYnNlcnZhdGlvbnMgb2YgYWxsIGFuaW1hbHMgY2FuIGJlIGZvdW5kIGluIHRoZSBmaXJzdCBjb2x1bW4gb2YgdGhlIGRhdGEgbWF0cml4IGBtYXRfbGFzc29fZGF0YWAuIEluIGNvbHVtbnMgIDIgdG8gYHIgbmNvbChtYXRfbGFzc29fZGF0YSlgIG9mIHRoZSBkYXRhIG1hdHJpeCB0aGVyZSBhcmUgdGhlIGdlbm90eXBlcyBvZiBhbGwgU05QIGxvY2kuIFRoZSBsaW5lYXIgbW9kZWwgaXMgZml0dGVkIHdpdGggTEFTU08gdXNpbmcgdGhlIGZ1bmN0aW9uIGBnbG1uZXQoKWAgZnJvbSB0aGUgcGFja2FnZSBgZ2xtbmV0YC4gVGhlIFNOUCBnZW5vdHlwZXMgYXJlIHVzZWQgYXMgZXhwbGFuYXRvcnkgdmFyaWFibGVzIGFuZCB0aGUgb2JzZXJ2YXRpb25zIGFyZSB0aGUgcmVzcG9uc2UgdmFyaWFibGVzLgoKCiMjIyBZb3VyIFRhc2tzCiogVXNlIHRoZSBmb2xsb3dpbmcgUi1TdGF0ZW1lbnQgdG8gZXN0aW1hdGUgdGhlIFNOUC1lZmZlY3RzIHVzaW5nIExBU1NPCgpgYGB7ciBtb2RlbC1maXQsIGV2YWw9RkFMU0UsIGVjaG89VFJVRSwgcmVzdWx0cz0nbWFya3VwJ30KcmVxdWlyZShnbG1uZXQpCmZpdHNucCA8LSBnbG1uZXQoeCA9IG1hdF9sYXNzb19kYXRhWywgLTFdLCB5ID0gbWF0X2xhc3NvX2RhdGFbLCAxXSkKYGBgCgoqIFZpc3VhbGl6ZSB0aGUgZGVwZW5kZW5jeSBiZXR3ZWVuIHRoZSB2YWx1ZSBvZiB0aGUgcGVuYWx0eSB0ZXJtICRcbGFtYmRhJCBhbmQgdGhlIG51bWJlciBvZiBleHBsYW5hdG9yeSB2YXJpYWJsZXMgd2hpY2ggYXJlIG5vdCAkMCQuCgpgYGB7ciBwbG90LWZpdCwgZXZhbD1GQUxTRSwgZWNobz1UUlVFLCByZXN1bHRzPSdtYXJrdXAnfQpwbG90KGZpdHNucCwgeHZhciA9ICJsYW1iZGEiLCBsYWJlbCA9IFRSVUUpCmBgYAoKKiBVc2UgYSBjcm9zcy12YWxpZGF0aW9uIHRvIGRldGVybWluZSB0aGUgdmFsdWUgb2YgJFxsYW1iZGEkLgoKYGBge3IgY3YtZml0LCBldmFsPUZBTFNFLCBlY2hvPVRSVUUsIHJlc3VsdHM9J21hcmt1cCd9CmN2Zml0c25wIDwtIGN2LmdsbW5ldCh4ID0gbWF0X2xhc3NvX2RhdGFbLCAtMV0sIHkgPSBtYXRfbGFzc29fZGF0YVssIDFdKQpgYGAKCiogU2hvdyB0aGUgcmVzdWx0cyBvZiB0aGUgY3Jvc3MtdmFsaWRhdGlvbiBpbiBhIHBsb3QgdXNpbmcgdGhlIGZ1bmN0aW9uIGBwbG90KClgLgoKYGBge3IgcGxvdC1jdiwgZXZhbD1GQUxTRSwgZWNobz1UUlVFLCByZXN1bHRzPSdtYXJrdXAnfQpwbG90KGN2Zml0c25wKQpgYGAKCiogSW4gdGhlIHBsb3Qgb2YgdGhlIGNyb3NzLXZhbGlkYXRpb24gcmVzdWx0cyB0aGVyZSBhcmUgdHdvIGRhc2hlZCBsaW5lcyB3aGljaCBib3RoIGluZGljYXRlZCBzcGVjaWFsIHZhbHVlcyBmb3IgJFxsYW1iZGEkLiBUaGUgZmlyc3QgdmFsdWUgaXMgdGhlIG1pbmltdW0gb2YgYWxsICAkXGxhbWJkYSQtdmFsdWVzIGFuZCB0aGUgc2Vjb25kIGlzIHRoZSBvbmUgdGhhdCBzZXRzIHRoZSBtb3N0IGV4cGxhbmF0b3J5IHZhcmlhYmxlcyB0byAkMCQgd2l0aCB0aGUgcmVzdHJpY3Rpb24gdGhhdCB0aGUgc3VtIG9mIHNxdWFyZWQgZXJyb3JzIGlzIG5vdCBmdXJ0aGVyIGF3YXkgdGhhbiBvbmUgc3RhbmRhcmQgZGV2aWF0aW9uIGZyb20gaXRzIG1pbmltdW0uIFRoZSB0d28gJFxsYW1iZGEkLXZhbHVlcyBhcmUgb2J0YWluZWQgd2l0aCAKCmBgYHtyIHNwZWNpYWwtbGFtYmRhLCBldmFsPUZBTFNFLCBlY2hvPVRSVUUsIHJlc3VsdHM9J21hcmt1cCd9CmN2Zml0c25wJGxhbWJkYS5taW4KY3ZmaXRzbnAkbGFtYmRhLjFzZQpgYGAKCiogRmluZCBhbGwgY29lZmZpY2llbnRzIHdoaWNoIGFyZSBub3QgJDAkIGZvciBib3RoICRcbGFtYmRhJC12YWx1ZXMgYW5kIGNvbXBhcmUgdGhlbSB0byB0aGUgdHJ1ZSB2YWx1ZXMgdGFrZW4gZnJvbSB0aGUgc2ltdWxhdGlvbi4gCgpgYGB7ciBjb2VmLW1pbiwgZXZhbD1GQUxTRSwgZWNobz1UUlVFLCByZXN1bHRzPSdtYXJrdXAnfQpjb2VmbWluIDwtIGNvZWYoY3ZmaXRzbnAsIHMgPSAibGFtYmRhLm1pbiIpCihjb2ZtaW5ueiA8LSBjb2VmbWluW2NvZWZtaW5bLCAxXSAhPSAwLF0pCmBgYAoKYGBge3IgY29lZi1zZSwgZXZhbD1GQUxTRSwgZWNobz1UUlVFLCByZXN1bHRzPSdtYXJrdXAnfQpjb2VmMXNlIDwtIGNvZWYoY3ZmaXRzbnAsIHMgPSAibGFtYmRhLjFzZSIpCihjb2VmMXNlbnogPC0gY29lZjFzZVtjb2VmMXNlWywgMV0gIT0gMCwgXSkKYGBgCgpUaGUgdHJ1ZSBTTlAtcG9zaXRpb25zIGZyb20gdGhlIHNpbXVsYXRpb24gYXJlOgoKYGBge3IsIGV2YWw9VFJVRSwgZWNobz1UUlVFLCByZXN1bHRzPSdtYXJrdXAnfQoodmVjX3NpZ25fc25wX2lkeCA8LSBjKDczLDU0LDI2LDMwLDcpKQpgYGAKCiMjIyBZb3VyIFNvbHV0aW9uClJ1biB0aGUgUi1zdGF0ZW1lbnRzIGFzIHRoZXkgYXJlIHNob3duIGluIHRoZSBoaW50cy4gVGhpcyB3aWxsIHJlc3VsdCBpbiBhIHNldCBvZiBTTlAtcG9zaXRpb25zIHdpdGggYW4gZWZmZWN0IHRoYXQgaXMgZGlmZmVyZW50IGZyb20gJDAkLiBUaGVzZSBTTlAtcG9zaXRpb25zIGNhbiB0aGVuIGJlIGNvbXBhcmVkIHRvIHRoZSB0cnVlIHBvc2l0aW9ucyBmcm9tIHRoZSBzaW11bGF0aW9uLiBUaGUgTEFTU08tZXN0aW1hdGVzIG9mIHRoZSBTTlAtZWZmZWN0cyBhcmUgb2J0YWluZWQgd2l0aCB0aGUgZm9sbG93aW5nIHN0ZXBzLgoKYGBge3J9CiMgZml0IHRoZSBsaW5lYXIgbW9kZWwgd2l0aCBnbG1uZXQKCmBgYAoKYGBge3J9CiMgVmlzdWFsaXplIHRoZSByZXN1bHRzIHVzaW5nIHRoZSBwbG90KCkgZnVuY3Rpb24KCmBgYAoKYGBge3J9CiMgRGV0ZXJtaW5lIGxhbWJkYSB1c2luZyBjcm9zcy12YWxpZGF0aW9uIHdpdGggdGhlIGZ1bmN0aW9uIGN2LmdsbW5ldCgpCgpgYGAKCmBgYHtyfQojIFNob3cgdGhlIHJlc3VsdHMgb2YgdGhlIGNyb3NzLXZhbGlkYXRpb24gdXNpbmcgdGhlIHBsb3QoKSBmdW5jdGlvbgoKYGBgCgpgYGB7cn0KIyBkZXRlcm1pbmUgdGhlIHR3byBsYW1iZGEgdmFsdWVzLCBnaXZlbiBpbiB0aGUgYWJvdmUgcGxvdAoKYGBgCgpgYGB7cn0KIyBkZXRlcm1pbmUgdGhlIG5vbi16ZXJvIGNvZWZmaWNpZW50cyBmb3IgdGhlIFNOUC1lZmZlY3RzIHdoaWNoIGFyZSBub3QgemVybyBmb3IgdGhlIHR3byBsYW1iZGEgdmFsdWVzCgpgYGAKCmBgYHtyfQojIGNvbXBhcmUgdGhlIFNOUC1wb3NpdGlvbnMgd2l0aCBhIG5vbi16ZXJvIGVmZmVjdCB0byB0aGUgdHJ1ZSBTTlAgcG9zaXRpb25zIHVzZWQgaW4gdGhlIHNpbXVsYXRpb24KCmBgYAoKCgoKCgojIyBQcm9ibGVtIDI6IEJheWVzaWFuIFJlZ3Jlc3Npb24gQW5hbHlzaXMKR2l2ZW4gaXMgdGhlIGVhcmxpZXIgdXNlZCBkYXRhc2V0IG9mIGBicmVhc3QgY2lyY3VtZmVyZW5jZWAgYW5kIGBib2R5IHdlaWdodGAuIAoKYGBge3IgZGF0YXJlZ3Jlc3Npb24sIGVjaG89RkFMU0UsIHJlc3VsdHM9J2FzaXMnfQp0YmxfcmVnIDwtIHRpYmJsZTo6dGliYmxlKEFuaW1hbCA9IGMoMToxMCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgYEJyZWFzdCBDaXJjdW1mZXJlbmNlYCA9IGMoMTc2LCAxNzcsIDE3OCwgMTc5LCAxNzksIDE4MCwgMTgxLCAxODIsMTgzLCAxODQpLAogICAgICAgICAgICAgICAgICAgICAgICAgIGBCb2R5IFdlaWdodGAgPSBjKDQ3MSwgNDYzLCA0ODEsIDQ3MCwgNDk2LCA0OTEsIDUxOCwgNTExLCA1MTAsIDU0MSkpCmtuaXRyOjprYWJsZSh0YmxfcmVnLAogICAgICAgICAgICAgYm9va3RhYnMgPSBUUlVFLAogICAgICAgICAgICAgbG9uZ3RhYmxlID0gVFJVRSwKICAgICAgICAgICAgIGNhcHRpb24gPSAiRGF0YXNldCBmb3IgUmVncmVzc2lvbiBvZiBCb2R5IFdlaWdodCBvbiBCcmVhc3QgQ2lyY3VtZmVyZW5jZSBmb3IgdGVuIEFuaW1hbHMiKQpgYGAKCmBgYHtyIGxtcmVnYW5hbHlzaXMsIGVjaG89RkFMU0V9CmxtX3JlZ19id2JjIDwtIGxtKGBCb2R5IFdlaWdodGAgfiBgQnJlYXN0IENpcmN1bWZlcmVuY2VgLCBkYXRhID0gdGJsX3JlZykKbl9yZXNfdmFyIDwtIHN1bShsbV9yZWdfYndiYyRyZXNpZHVhbHNeMikvbG1fcmVnX2J3YmMkZGYucmVzaWR1YWwKbl9yZXNfdmFyX3JvdW5kZWQgPC0gcm91bmQobl9yZXNfdmFyLCBkaWdpdHMgPSAxKQpgYGAKClRoZSBtb2RlbCB0aGF0IGlzIHVzZWQgaXMgYSBzaW1wbGUgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgZ2l2ZW4gYnkgCgokJHlfaSA9IFxiZXRhXzAgKyBcYmV0YV8xICogeF9pICsgXGVwc2lsb25faSQkLiAKCndoZXJlICR5X2kkIGNvcnJlc3BvbmRzIHRvIHRoZSBib2R5IHdlaWdodCBvZiBhbmltYWwgJGkkLCAkeF9pJCBpcyB0aGUgYnJlYXN0IGNpcmN1bWZlcmVuY2Ugb2YgYW5pbWFsICRpJCwgJFxiZXRhXzAkIGlzIHRoZSB1bmtub3duIGludGVyY2VwdCBhbmQgJFxiZXRhXzEkIGlzIHRoZSB1bmtub3duIHJlZ3Jlc3Npb24gY29lZmZpY2llbnQuIEZvciByZWFzb25zIG9mIHNpbXBsaWNpdHksIHdlIGFzc3VtZSB0aGUgcmVzaWR1YWwgdmFyaWFuY2UgJFxzaWdtYV4yJCB0byBiZSBrbm93bi4gRm9yIHRoZSBsYXRlciBjb21wdXRhdGlvbnMsIHdlIGluc2VydCB0aGUgZXN0aW1hdGUgdGhhdCBpcyBvYnRhaW5lZCBmcm9tIHRoZSBgbG0oKWAgZnVuY3Rpb24uIFRoaXMgdmFsdWUgY29ycmVzcG9uZHMgdG8gJFxzaWdtYV4yID0gYHIgbl9yZXNfdmFyX3JvdW5kZWRgJC4gCgojIyMgQmF5ZXNpYW4gRXN0aW1hdGlvbiBPZiBVbmtub3ducwpBcyBhbHJlYWR5IG1lbnRpb25lZCBkdXJpbmcgdGhlIGxlY3R1cmUsIEJheWVzaWFuIGVzdGltYXRlcyBvZiB1bmtub3ducyBhcmUgYmFzZWQgb24gdGhlIHBvc3RlcmlvciBkaXN0cmlidXRpb24gb2YgdGhlIHVua25vd25zIGdpdmVuIHRoZSBrbm93bnMuIEZvciBvdXIgcmVncmVzc2lvbiBtb2RlbCB0aGUgdW5rbm93bnMgY29ycmVzcG9uZCB0byAKCiQkXGJldGEgPSBcbGVmdFtcYmVnaW57YXJyYXl9e2N9XGJldGFfMCBcXCBcYmV0YV8xIFxlbmR7YXJyYXl9XHJpZ2h0XSQkCgogVGhlIHBvc3RlcmlvciBkaXN0cmlidXRpb24gb2YgdGhlIHVua25vd25zIGdpdmVuIHRoZSBrbm93bnMgaXMgJGYoXGJldGEgfCB5KSQuIFVzaW5nIEJheWVzJyBUaGVvcmVtIHdlIGNhbiB3cml0ZSAkZihcYmV0YSB8IHkpJCBhcwogClxiZWdpbnthbGlnbn0KZihcYmV0YSB8IHkpICYgPSAgICAgICBcZnJhY3tmKFxiZXRhLCB5KX17Zih5KX0gXG5vdGFnIFxcCiAgICAgICAgICAgICAmID0gICAgICAgXGZyYWN7Zih5IHwgXGJldGEpZihcYmV0YSl9e2YoeSl9IFxub3RhZyBcXAogICAgICAgICAgICAgJiBccHJvcHRvICBmKHkgfCBcYmV0YSlmKFxiZXRhKSBcbm90YWcKXGVuZHthbGlnbn0KCldoZW4gd2UgZG8gbm90IGhhdmUgYW55IHNwZWNpZmljIHByaW9yIGtub3dsZWRnZSBhYm91dCAkXGJldGEkLCB0aGUgcHJpb3IgZGlzdHJpYnV0aW9uICRmKFxiZXRhKSQgZm9yIHRoZSB1bmtub3duICRcYmV0YSQgaXMgc2V0IHRvIGEgY29uc3RhbnQuIFRoZXJlZm9yZSB3ZSBjYW4gd3JpdGUKClxiZWdpbnthbGlnbn0KZihcYmV0YSB8IHkpICAmIFxwcm9wdG8gIGYoeSB8IFxiZXRhKWYoXGJldGEpIFxub3RhZyBcXAogICAgICAgICAgICAgICYgXHByb3B0byAgZih5IHwgXGJldGEpIFxub3RhZwpcZW5ke2FsaWdufQoKQXNzdW1pbmcgYSBub3JtYWwgZGlzdHJpYnV0aW9uIGZvciB0aGUgZGF0YSBjYXVzZXMgdGhlIGxpa2VsaWhvb2QgJGYoeSB8IFxiZXRhKSQgdG8gYmUgYSBtdWx0aXZhcmlhdGUgbm9ybWFsIGRpc3RyaWJ1dGlvbi4gCgpcYmVnaW57YWxpZ259CmYoXGJldGEgfCB5KSAgJiBccHJvcHRvICBmKHkgfCBcYmV0YSkgXG5vdGFnIFxcCiAgICAgICAgICAgICAgJiA9ICgyXHBpXHNpZ21hXjIpXnstbi8yfSBleHAgXGxlZnRceyAtezEgXG92ZXIgMn0gXGZyYWN7KHkgLSBYXGJldGEpXlQoeSAtIFhcYmV0YSl9e1xzaWdtYV4yfSBccmlnaHRcfQooXCNlcTpCYXllc0xpa2VsaWhvb2QpClxlbmR7YWxpZ259CgpUaGUgYWJvdmUgZXhwcmVzc2lvbiBcQHJlZihlcTpCYXllc0xpa2VsaWhvb2QpIGlzIGFuICRuLSQgZGltZW5zaW9uYWwgbm9ybWFsIGRpc3RyaWJ1dGlvbiB3aXRoIGV4cGVjdGVkIHZhbHVlICRYXGJldGEkIGFuZCB2YXJpYW5jZS1jb3ZhcmlhbmNlIG1hdHJpeCBjb3JyZXNwb25kaW5nIHRvICRJXHNpZ21hXjIkLiBCdXQgYmVjYXVzZSB3ZSBoYXZlIGp1c3QgdHdvIHVua25vd25zICRcYmV0YV8wJCBhbmQgJFxiZXRhXzEkIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uICRmKFxiZXRhIHwgeSkkIG11c3QgaGF2ZSB0d28gZGltZW5zaW9ucyBhbmQgbm90ICRuJC4gVGhlIGZvbGxvd2luZyByZS1hcnJhbmdlbWVudCBjYW4gc29sdmUgdGhpcyBwcm9ibGVtLiBMZXQgdXMgc2V0IHRoZSB2YXJpYWJsZSAkUSQgdG8gCgokJFEgPSAoeSAtIFhcYmV0YSleVCh5IC0gWFxiZXRhKSA9IHleVHkgLSAyeV5UWFxiZXRhICsgXGJldGFeVChYXlRYKVxiZXRhJCQKCkludHJvZHVjaW5nIHRoZSBsZWFzdCBzcXVhcmVzIGVzdGltYXRlICRcaGF0e1xiZXRhfSA9IChYXlRYKV57LTF9WF5UeSQgaW50byB0aGUgYWJvdmUgZXF1YXRpb24gYnkgcmVwbGFjaW5nICR5XlRYJCB3aXRoICRcaGF0e1xiZXRhfV5UKFheVFgpJCByZXN1bHRzIGluIAoKJCRRID0geV5UeSAtIDIgXGhhdHtcYmV0YX1eVChYXlRYKVxiZXRhICsgXGJldGFeVChYXlRYKVxiZXRhID0geV5UeSArIChcYmV0YS1caGF0e1xiZXRhfSleVChYXlRYKShcYmV0YS1caGF0e1xiZXRhfSkgLSBcaGF0e1xiZXRhfV5UKFheVFgpXGhhdHtcYmV0YX0kJAoKSW5zZXJ0aW5nIHRoaXMgbGFzdCByZXN1bHQgYmFjayBpbnRvIFxAcmVmKGVxOkJheWVzTGlrZWxpaG9vZCkgZ2l2ZXMKClxiZWdpbnthbGlnbn0KZihcYmV0YSB8IHkpICAmIFxwcm9wdG8gIGYoeSB8IFxiZXRhKSBcbm90YWcgXFwKICAgICAgICAgICAgICAmID0gKDJccGlcc2lnbWFeMileey1uLzJ9IGV4cCBcbGVmdFx7IC17MSBcb3ZlciAyfSBcZnJhY3soeSAtIFhcYmV0YSleVCh5IC0gWFxiZXRhKX17XHNpZ21hXjJ9IFxyaWdodFx9IFxub3RhZyBcXAogICAgICAgICAgICAgICYgPSAoMlxwaVxzaWdtYV4yKV57LW4vMn0gZXhwIFxsZWZ0XHsgLXsxIFxvdmVyIDJ9IFxmcmFje3leVHkgKyAoXGJldGEtXGhhdHtcYmV0YX0pXlQoWF5UWCkoXGJldGEtXGhhdHtcYmV0YX0pIC0gXGhhdHtcYmV0YX1eVChYXlRYKVxoYXR7XGJldGF9fXtcc2lnbWFeMn0gXHJpZ2h0XH0gXG5vdGFnIFxcCiAgICAgICAgICAgICAgJiA9ICgyXHBpXHNpZ21hXjIpXnstbi8yfSBcbGVmdFtleHAgXGxlZnRceyAtezEgXG92ZXIgMn0gXGZyYWN7eV5UeX17XHNpZ21hXjJ9XHJpZ2h0XH0gCiAgICAgICAgICAgICAgICAgICogZXhwXGxlZnRceyAtezEgXG92ZXIgMn0gXGZyYWN7IChcYmV0YS1caGF0e1xiZXRhfSleVChYXlRYKShcYmV0YS1caGF0e1xiZXRhfSl9e1xzaWdtYV4yfSBccmlnaHRcfQogICAgICAgICAgICAgICAgICAqIGV4cFxsZWZ0XHsgLXsxIFxvdmVyIDJ9IFxmcmFjeyAtIFxoYXR7XGJldGF9XlQoWF5UWClcaGF0e1xiZXRhfX17XHNpZ21hXjJ9IFxyaWdodFx9IFxyaWdodF0gIFxub3RhZyBcXAogICAgICAgICAgICAgICYgXHByb3B0byBleHBcbGVmdFx7IC17MSBcb3ZlciAyfSBcZnJhY3sgKFxiZXRhLVxoYXR7XGJldGF9KV5UKFheVFgpKFxiZXRhLVxoYXR7XGJldGF9KX17XHNpZ21hXjJ9IFxyaWdodFx9ICAgIAooXCNlcTpCYXllc0xpa2VsaWhvb2RSZWYpClxlbmR7YWxpZ259CgpUaGUgbGFzdCBwcm9wb3J0aW9uYWxpdHkgcmVzdWx0cyBmcm9tIHRoZSBmYWN0IHRoYXQgb25seSB0aGUgdGVybSBkZXBlbmRpbmcgb24gJFxiZXRhJCBpcyByZXRhaW5lZC4gQWxsIG90aGVyIHRlcm1zIG5vdCBkZXBlbmRpbmcgb24gJFxiZXRhJCBhcmUgY29uc3RhbnQgZmFjdG9ycyB3aXRoIHJlc3BlY3QgdG8gJFxiZXRhJCBhbmQgY2FuIHRoZXJlZm9yZSBiZSBkcm9wcGVkLiBUaHVzICRmKFxiZXRhfHkpJCBjYW4gYmUgd3JpdHRlbiBhcwoKJCRmKFxiZXRhIHwgeSkgIFxwcm9wdG8gZXhwXGxlZnRceyAtezEgXG92ZXIgMn0gXGZyYWN7IChcYmV0YS1caGF0e1xiZXRhfSleVChYXlRYKShcYmV0YS1caGF0e1xiZXRhfSl9e1xzaWdtYV4yfSBccmlnaHRcfSQkCndoaWNoIGlzIHJlY29nbml6ZWQgYXMgcHJvcG9ydGlvbmFsIHRvIGEgdHdvIGRpbWVuc2lvbmFsIG5vcm1hbCBkZW5zaXR5IHdpdGggbWVhbiAkXGhhdHtcYmV0YX0kIGFuZCB2YXJpYW5jZSAkKFheVFgpXnstMX1cc2lnbWFeMiQuIFRodXMgaW4gdGhlIHNpbXBsZSBzZXR0aW5nIHRoZSBtZWFuIG9mIHRoZSBwb3N0ZXJpb3IgbWVhbiBjYW4gYWxyZWFkeSBiZSBzZWVuIGZyb20gdGhlIGFib3ZlIGZvcm11bGEuIEJ1dCBpbiBhIG1vcmUgY29tcGxleCBzZXR0aW5nLCB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBkb2VzIG5vdCBoYXZlIGEgc3RhbmRhcmQgZm9ybSBhbmQgd2UgbmVlZCB0byBzZXR1cCBhIHNhbXBsaW5nIHNjaGVtZSB3aGljaCBhbGxvd3MgdXMgdG8gZHJhdyByYW5kb20gbnVtYmVycyBmcm9tIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uLiBUaGUgc2FtcGxpbmcgc2NoZW1lIHRoYXQgd2UgYXJlIGludHJvZHVjaW5nIGhlcmUgaXMgY2FsbGVkIHRoZSBfX0dpYmJzIFNhbXBsZXJfXy4gCgoKIyMjIEdpYmJzIFNhbXBsZXIgZm9yICRcYmV0YSQKVGhlIHNpbXBsZSByZWdyZXNzaW9uIG1vZGVsIHRoYXQgd2UgYXJlIHVzaW5nIGZvciB0aGUgYnJlYXN0IGNpcmN1bWZlcmVuY2UgYW5kIHRoZSBib2R5IHdlaWdodCBkYXRhIGNhbiBiZSB3cml0dGVuIGluIG1hdHJpeC12ZWN0b3Igbm90YXRpb24gYXMgCgokJHkgPSAxXGJldGFfMCArIHhcYmV0YV8xICsgXGVwc2lsb24kJAoKSW4gdGhlIEdpYmJzIHNhbXBsaW5nIHNjaGVtZSBib3RoIHVua25vd25zICRcYmV0YV8wJCBhbmQgJFxiZXRhXzEkIGFyZSBzYW1wbGVkIGZyb20gdGhlaXIgZnVsbCBjb25kaXRpb25hbCBkaXN0cmlidXRpb25zLiBGb3IgJFxiZXRhXzAkIHRoZSBmdWxsIGNvbmRpdGlvbmFsIHBvc3RlcmlvciBkaXN0cmlidXRpb24gaXMgJGYoXGJldGFfMCB8IFxiZXRhXzEsIHkpJCB3aGljaCBpcyBjb21wdXRlZCBmb3IgdGhlIGN1cnJlbnQgdmFsdWUgb2YgJFxiZXRhXzEkLiBTZXBhcmF0aW5nICRcYmV0YV8wJCBmcm9tIHRoZSBvdGhlciB1bmtub3ducyB5aWVsZHMgdGhlIGxpbmVhciBtb2RlbCAKCiQkd18wID0gMVxiZXRhXzAgKyBcZXBzaWxvbiQkCndoZXJlICR3XzAgPSB5IC0geFxiZXRhXzEkLiBUaGUgbGVhc3Qgc3F1YXJlcyBlc3RpbWF0b3Igb2YgJFxiZXRhXzAkIGlzIAoKJCRcaGF0e1xiZXRhfV8wID0gKDFeVDEpXnstMX0xXlR3XzAkJAp3aXRoIHZhcmlhbmNlIAoKJCR2YXIoXGhhdHtcYmV0YX1fMCkgPSAgKDFeVDEpXnstMX0gXHNpZ21hXjIkJAoKQXBwbHlpbmcgdGhlIHNhbWUgc3RyYXRlZ3kgYXMgZm9yICRmKFxiZXRhIHwgeSkkLCBpdCBjYW4gYmUgc2hvd24gdGhhdCAkZihcYmV0YV8wIHwgXGJldGFfMSwgeSkkIGlzIGEgbm9ybWFsIGRpc3RyaWJ1dGlvbiB3aXRoIG1lYW4gJFxoYXR7XGJldGF9XzAkIGFzIG1lYW4gYW5kICQoMV5UMSleey0xfSBcc2lnbWFeMiQgYXMgdmFyaWFuY2UuIFRoZSBmdWxsLWNvbmRpdGlvbmFsIHBvc3RlcmlvciBvZiAkXGJldGFfMSQgY2FuIGJlIGRlcml2ZWQgdGhlIHNhbWUgd2F5LCBsZWFkaW5nIHRvIAoKJCRcaGF0e1xiZXRhfV8xID0gKHheVHgpXnstMX14XlR3XzEkJAoKd2l0aCB2YXJpYW5jZSAkdmFyKFxoYXR7XGJldGF9XzEpID0gKHheVHgpXnstMX0gXHNpZ21hXjIkIHdoZXJlICR3XzEgPSB5IC0gMVxiZXRhXzAkLiAKCgojIyMgWW91ciBUYXNrCiogQ3JlYXRlIGEgR2liYnMgU2FtcGxpbmcgc2NoZW1lIGZvciB0aGUgZGF0YXNldCBzaG93biBpbiBUYWJsZSBcQHJlZih0YWI6ZGF0YXJlZ3Jlc3Npb24pLiAKKiBVc2UgdGhlIG1lYW4gb2YgdGhlIGdlbmVyYXRlZCBzYW1wbGVzIGFzIGFuIGVzdGltYXRlIGZvciB0aGUgdW5rbm93bnMgJFxiZXRhXzAkIGFuZCAkXGJldGFfMSQuCgoKIyMjIFlvdXIgU29sdXRpb24KSW4gdGhlIHByb2JsZW0gZGVzY3JpcHRpb24sIHRoZSByZXNpZHVhbCB2YXJpYW5jZSAkXHNpZ21hXjIkIGlzIGFzc3VtZWQgdG8gYmUga25vd24uIEluc3RlYWQgb2YgdXNpbmcgYSBmaXhlZCB2YWx1ZSwgd2UgdXNlIHRoZSBlc3RpbWF0ZSB0aGF0IGNhbiBiZSBjb21wdXRlZCBiYXNlZCBvbiB0aGUgcmVzaWR1YWxzIGZyb20gYSBsZWFzdCBzcXVhcmVzIG1vZGVsLgoKYGBge3J9CiMgY29tcHV0ZSByZXNpZHVhbCB2YXJpYW5jZSBiYXNlZCBvbiByZXNpZHVhbHMgb2YgZml0dGluZyBsbSgpIHRvIGRhdGEKCiMgcHJlcGFyZSB0aGUgdmVjdG9yIHkgb2Ygb2JzZXJ2YXRpb25zIGFuZCB0aGUgbWF0cml4IFggZm9yIHRoZSBpbnRlcmNlcHQgYW5kIHRoZSBwcmVkaWN0b3IgdmFyaWFibGUKCiMgaW5pdGlhbGlzZSBhIHZlY3RvciBiZXRhIGZvciB0aGUgY3VycmVudCBlc3RpbWF0ZSBhbmQgYSB2ZWN0b3IgbWVhbkJldGEgZm9yIHRoZSBtZWFuIG9mIGFsbCB0aGUgc2FtcGxlcwoKIyBsb29wIG92ZXIgYSBnaXZlbiBudW1iZXIgb2YgaXRlcmF0aW9ucyB0byBwcm9kdWNlIHRoZSBzYW1wbGVzIGZvciB0aGUgdW5rbm93bnMKCmBgYAoKCgoKCgpgYGB7ciwgZWNobz1GQUxTRSwgcmVzdWx0cz0nYXNpcyd9CmNhdCgnXG4tLS1cblxuIF9MYXRlc3QgQ2hhbmdlczogJywgZm9ybWF0KFN5cy50aW1lKCksICclWS0lbS0lZCAlSDolTTolUycpLCAnICgnLCBTeXMuaW5mbygpWyd1c2VyJ10sICcpX1xuJywgc2VwID0gJycpCmBgYAogCg==