Let us talk a little bit about matrix notation and why we use it

  1. MATRIX NOTATION

Suppose you have some data and you have a linear model \[\sum_{i=1}^{N}(y_{i}-\beta_{0}-\beta_{1}x_{i1}-\beta_{2}x_{i2}-\beta_{3}x_{i3}-\beta_{4}x_{i4})^{2}\] It has four variables (\(x_{ij}\)) and it’s a little bit more complicated than the ones we saw before. And you have four parameters (\(\beta_{j}\) for every \(j=1,...,4\)) plus the base level parameter (\(\beta_{0}\)). And you want to find the parameters that fit your data best, so we might consider least squares.

  1. Linear Models as Matrix Multiplication

So we look for the betas that minimize this equation, but before we proceed to the optimization process we can write the above equation in matrix notation as follows:

first, let us define the following matrices, \[\begin{align}X=\begin{pmatrix}1\\x_{i1}\\x_{i2}\\x_{i3}\\x_{i4}\end{pmatrix} & & \text{and} & & \beta=\begin{pmatrix}\beta_{0}\\ \beta_{1}\\ \beta_{2}\\ \beta_{3}\\ \beta_{4}\end{pmatrix}\\ \end{align}\] then we have, \[(Y- X\beta)^{T}(Y-X\beta)\] where \(Y\) is the vector that contains each observation \(y_{i}\) for each \(i=1,...,N\).

Note that this formula is equivalent to the first one, but easier to write down and work with. It is not only easier to write down on a piece of paper, but also faster at least on R.

Here is a simulation example that illustrates how quick R can work with matrix algebra instead of using a more complex formula to compute the sum of squares:

y<-rnorm(1e6)
x<-cbind(rep(1,1e6), rep(0:1, each=5e5))
beta<-c(1,1)
system.time({sum(y-x%*%beta)^2})
   user  system elapsed 
  0.124   0.003   0.129 
system.time({sum(sapply(seq_along(y),function(i) y[i]-x[i,1]*beta[1]-x[i,2]*beta[2])^2)})
   user  system elapsed 
  0.955   0.017   0.981 

So instead of writing down each single model for each element, for each individual we instead write these matrices. \[\begin{align}\underbrace{\begin{pmatrix}x_{10} & x_{11}\\ x_{20} & x_{21}\\ \vdots & \vdots \\ x_{N0} & x_{N1}\end{pmatrix}}_{X} \underbrace{\begin{pmatrix}\beta_{0}\\ \beta_{1}\end{pmatrix}}_{\beta}=\begin{pmatrix}\beta_{0}x_{10}+\beta_{1}x_{11}\\ \beta_{0}x_{20}+\beta_{1}x_{21}\\ \vdots \\ \beta_{0}x_{N0}+\beta_{1}x_{N1} \end{pmatrix}\end{align}\] So when we see \(X\beta\) in our model we assume that \(X\) is a matrix with entries for each individual on the rows, and then the columns represent the different covariates or variables using in the model, on the other hand \(\beta\) is another little matrix that contains the parameters of the model.

Instead of the formula with all the indices, we can actually write these matrices

  1. Some Specific Linear models (Expressing experimental design using R formula)

In this module we’ll show how to use the two R base functions:

in order to produce design matrices for a variety of linear models

We’re going to be building matrices filled by zeros and ones that get multiplied by beta in a linear model.

x<-c(1,1,2,2)
f<-formula(~x) # e.g lm(y~beta1x1+epsilon)
f
~x

The models fit by, e.g., the lm and glm functions are specified in a compact symbolic form. The ~ operator is basic in the formation of such models. An expression of the form y ~ model is interpreted as a specification that the response y is modeled by a linear predictor specified symbolically by model. Such a model consists of a series of terms separated by + operators.

X<-model.matrix(f) # it gives us an intercept filled by a vector of ones and we'll have a column x which gives the variable x as a column
X
  (Intercept) x
1           1 1
2           1 1
3           1 2
4           1 2
attr(,"assign")
[1] 0 1
class(x)
[1] "numeric"
class(X)
[1] "matrix" "array" 

Model.matrix will create a design matrix using that formula if you don’t provide any data, it will use the environment of the object f into the formula

So if we use a factor and build a model matrix using the factor x, it would look different,

x<-factor(c(1,1,2,2))
x
[1] 1 1 2 2
Levels: 1 2
X<-model.matrix(~x)
X
  (Intercept) x2
1           1  0
2           1  0
3           1  1
4           1  1
attr(,"assign")
[1] 0 1
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"

instead of having a column with \((1,1,2,2)\) vector we’ll have a column with \((0,0,1,1)\) vector, that takes the value of 0 when \(x_{ij}=1\) and 1 when \(x_{ij}=2\) (for each \(i\in\{1,...,N\}\) and \(j\in\{1,...,p\}\))

We again have an intercept filled by a vector of ones and a column x2 which gives the variable \(x\) represented as a indicator variable.

Now let’s construct a factor \(x\) which has three different levels:

x<-factor(c(1,1,2,2,3,3))
model.matrix(~x)
  (Intercept) x2 x3
1           1  0  0
2           1  0  0
3           1  1  0
4           1  1  0
5           1  0  1
6           1  0  1
attr(,"assign")
[1] 0 1 1
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"

One can actually define matrices with indicator variables as vectors defining non-numerical entries:

x<-factor(c(1,1,1,1,2,2,2,2))
y<-factor(c("a","a","b","a","b","a","a","b")) 
model.matrix(~x+y)
  (Intercept) x2 yb
1           1  0  0
2           1  0  0
3           1  0  1
4           1  0  0
5           1  1  1
6           1  1  0
7           1  1  0
8           1  1  1
attr(,"assign")
[1] 0 1 2
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"

attr(,"contrasts")$y
[1] "contr.treatment"

As before we have an “intercept” and two vectors expressed as indicator variables. In vector “x2” variable takes value of 0 when \(x_{ij}=1\) and 1 otherwise. Likewise, in vector “yb” variable takes the value of 0 when \(y_{ij}=\)“a” and 1 otherwise.

Also you can specify an interaction between the variables using “:”, so

model.matrix(~x+y+x:y) #this model describes the interaction described below
  (Intercept) x2 yb x2:yb
1           1  0  0     0
2           1  0  0     0
3           1  0  1     0
4           1  0  0     0
5           1  1  1     1
6           1  1  0     0
7           1  1  0     0
8           1  1  1     1
attr(,"assign")
[1] 0 1 2 3
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"

attr(,"contrasts")$y
[1] "contr.treatment"
model.matrix(~x*y) #multiplication. 
  (Intercept) x2 yb x2:yb
1           1  0  0     0
2           1  0  0     0
3           1  0  1     0
4           1  0  0     0
5           1  1  1     1
6           1  1  0     0
7           1  1  0     0
8           1  1  1     1
attr(,"assign")
[1] 0 1 2 3
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"

attr(,"contrasts")$y
[1] "contr.treatment"

So “x2:yb” vector will take value of 1 iff both \(x_{ij}=2\) and \(y_{ij}=\)“b” holds, and 0 otherwise.

We also can create a matrix with the opposite condition for the indicator variable \(x\):

x<- factor(c(1,1,2,2))
model.matrix(~x)
  (Intercept) x2
1           1  0
2           1  0
3           1  1
4           1  1
attr(,"assign")
[1] 0 1
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"
x<-relevel(x, "2")
model.matrix(~x)
  (Intercept) x1
1           1  1
2           1  1
3           1  0
4           1  0
attr(,"assign")
[1] 0 1
attr(,"contrasts")
attr(,"contrasts")$x
[1] "contr.treatment"
x<-factor(x,levels=c("1","2"))
x
[1] 1 1 2 2
Levels: 1 2

Some other operations:

z<-1:4
model.matrix(~z) #z=(1,2,3,4)
  (Intercept) z
1           1 1
2           1 2
3           1 3
4           1 4
attr(,"assign")
[1] 0 1
model.matrix(~0+z) # no intercept vector
  z
1 1
2 2
3 3
4 4
attr(,"assign")
[1] 1
model.matrix(~z+I(z^2)) #adds another column that is the square of z
  (Intercept) z I(z^2)
1           1 1      1
2           1 2      4
3           1 3      9
4           1 4     16
attr(,"assign")
[1] 0 1 2

Now we’re going to show how to perform linear models in R, and we are going to do a simple two group comparison. We need first do load in some data of mice weights, mice which were are given two diets. One was a high-fat diet and one was a control diet.

#install.packeges("downloader","ggplot2")
#library(downloader,ggplot2)
url<-"https://raw.githubusercontent.com/genomicsclass/dagdata/master/inst/extdata/femaleMiceWeights.csv"
filename<-"femaleMiceWeights.csv"
if (!file.exists(filename))download(url,filename)
dat<-read.csv(filename)
p<-ggplot(dat)
p<-p+aes(x=dat$Diet,y=dat$Bodyweight)
p<-p+scale_size_manual(values=c(0.8,0.8,0.8,0.5))
p<-p+geom_point()+geom_jitter(width=0.1)
p<-p+xlab("Diet")+ylab("Body Wheight")+ggtitle("Body Wheight over Diet")
p
Warning: Use of `dat$Diet` is discouraged.
ℹ Use `Diet` instead.
Warning: Use of `dat$Bodyweight` is discouraged.
ℹ Use `Bodyweight` instead.
Warning: Use of `dat$Diet` is discouraged.
ℹ Use `Diet` instead.
Warning: Use of `dat$Bodyweight` is discouraged.
ℹ Use `Bodyweight` instead.

“chow” is the control sample and “hf” is the high-fat diet. In data:

dat[11:14,]

first column indicates whether a mouse was exposed to a high-fat diet or a controlled diet.

Looking only to the chart we can see that mice population which were given the control diet have slightly lower body weights, on average, than the mice that were given the high-fat diet, although there’s overlap between these two groups.

We want to analyze the difference between these two groups using a linear model.

First, let us construct the matrix \(X\) that we have seen in the linear model formula, so we can see what is happening internally and how R is taking the data:

diet<-factor(dat$Diet)
levels(diet)
[1] "chow" "hf"  
X<-model.matrix(~diet,data=dat)
X
   (Intercept) diethf
1            1      0
2            1      0
3            1      0
4            1      0
5            1      0
6            1      0
7            1      0
8            1      0
9            1      0
10           1      0
11           1      0
12           1      0
13           1      1
14           1      1
15           1      1
16           1      1
17           1      1
18           1      1
19           1      1
20           1      1
21           1      1
22           1      1
23           1      1
24           1      1
attr(,"assign")
[1] 0 1
attr(,"contrasts")
attr(,"contrasts")$diet
[1] "contr.treatment"

Now, we’re going to just run the model.

You don’t actually have to specify the \(X\) matrix. We use the lm(y~x) function for linear model.

fit<-lm(Bodyweight~Diet, data=dat)
summary(fit)

Call:
lm(formula = Bodyweight ~ Diet, data = dat)

Residuals:
    Min      1Q  Median      3Q     Max 
-6.1042 -2.4358 -0.4138  2.8335  7.1858 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)   23.813      1.039  22.912   <2e-16 ***
Diethf         3.021      1.470   2.055   0.0519 .  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3.6 on 22 degrees of freedom
Multiple R-squared:  0.1611,    Adjusted R-squared:  0.1229 
F-statistic: 4.224 on 1 and 22 DF,  p-value: 0.05192
(coefs<-coef(fit))
(Intercept)      Diethf 
  23.813333    3.020833 

So we have the intercept \(\hat{\beta}_{0}=23.813333\) and the difference in average weight between high-fat and control diet is \(\hat{\beta}_1=3.020833\).

To show that our mathematical model is consistent with these results, recall \[\hat{\beta}=\begin{pmatrix}\hat{\beta}_{0}\\ \hat{\beta_{1}}\end{pmatrix}=(X^{T}X)^{-1}X^{T}Y\] thus,

Y<-matrix(dat$Bodyweight,ncol=1)
beta.hat<-solve(t(X)%*%X)%*%(t(X)%*%Y)
beta.hat
                 [,1]
(Intercept) 23.813333
diethf       3.020833

We have another way to look at these results from this linear model:

s<-split(dat$Bodyweight,dat$Diet)
mean(s[["chow"]]) # split divides the data in the vector x into the groups defined by f. The replacement forms replace values corresponding to such a division. unsplit reverses the effect of split.
[1] 23.81333
mean(s[["hf"]])-mean(s[["chow"]])
[1] 3.020833
summary(fit)$coefficients
             Estimate Std. Error   t value     Pr(>|t|)
(Intercept) 23.813333   1.039353 22.911684 7.642256e-17
Diethf       3.020833   1.469867  2.055174 5.192480e-02
(ttest<-t.test(s[["chow"]], s[["hf"]],var.equal = T))

    Two Sample t-test

data:  s[["chow"]] and s[["hf"]]
t = -2.0552, df = 22, p-value = 0.05192
alternative hypothesis: true difference in means is not equal to 0
95 percent confidence interval:
 -6.06915183  0.02748516
sample estimates:
mean of x mean of y 
 23.81333  26.83417 
summary(fit)$coefficients[2,3]
[1] 2.055174
ttest$statistic
        t 
-2.055174 
t.test( s[["hf"]],s[["chow"]],var.equal = T)$statistic
       t 
2.055174 

Linear Models in Practice Exercises #1

You can make a design matrix \(X\) for a two group comparison either using model.matrix() or simply with:

X = cbind(rep(1,nx + ny),
rep(c(0,1),
c(nx, ny)))

For a comparison of two groups, where the first group has \(nx=5\) samples, and the second group has \(ny=7\) samples, what is the element in the 1st row and 1st column of \(X^{T}X\)?

nx<-5
ny<-7
X <- cbind(rep(1,nx + ny),
rep(c(0,1),
c(nx, ny)))
XtX<-(t(X)%*%X)
XtX[1,1]
[1] 12

Linear Models in Practice Exercises #2

What are all the other elements of \(X^{T}X\)?

XtX
     [,1] [,2]
[1,]   12    7
[2,]    7    7

Recall the LSE estimates: \[\hat{\beta}=(X^{T}X)^{-1}X^{T}Y\] Once you write down the matrices as we did before you can find the solution to estimate the parameters.

When we’re testing if a particular estimated parameter is statically significant we’re going to have to know how much it varies, and we’re going to have to compute its standard error. This is basically the t-test.

We have an estimate and its standard error such that: \[\frac{\text{signal}}{\text{noice}}=\frac{\hat{\beta}_i}{SE(\hat{\beta}_i)}\] \[SE(\hat{\beta}_{i})=\sqrt{s^{2}(X^{T}X)^{-1}_{ii}}\] where \(s^{2}\) is the sample variance.

LS0tCnRpdGxlOiAiTElORUFSIE1PREVMUyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKICBwZGZfZG9jdW1lbnQ6IGRlZmF1bHQKLS0tCgpMZXQgdXMgdGFsayBhIGxpdHRsZSBiaXQgYWJvdXQgbWF0cml4IG5vdGF0aW9uIGFuZCB3aHkgd2UgdXNlIGl0CgoxLiBNQVRSSVggTk9UQVRJT04KClN1cHBvc2UgeW91IGhhdmUgc29tZSBkYXRhIGFuZCB5b3UgaGF2ZSBhIGxpbmVhciBtb2RlbAokJFxzdW1fe2k9MX1ee059KHlfe2l9LVxiZXRhX3swfS1cYmV0YV97MX14X3tpMX0tXGJldGFfezJ9eF97aTJ9LVxiZXRhX3szfXhfe2kzfS1cYmV0YV97NH14X3tpNH0pXnsyfSQkCkl0IGhhcyBmb3VyIHZhcmlhYmxlcyAoJHhfe2lqfSQpIGFuZCBpdCdzIGEgbGl0dGxlIGJpdCBtb3JlIGNvbXBsaWNhdGVkIHRoYW4gdGhlIG9uZXMgd2Ugc2F3IGJlZm9yZS4gQW5kIHlvdSBoYXZlIGZvdXIgcGFyYW1ldGVycyAoJFxiZXRhX3tqfSQgZm9yIGV2ZXJ5ICRqPTEsLi4uLDQkKSBwbHVzIHRoZSBiYXNlIGxldmVsIHBhcmFtZXRlciAoJFxiZXRhX3swfSQpLiBBbmQgeW91IHdhbnQgdG8gZmluZCB0aGUgcGFyYW1ldGVycyB0aGF0IGZpdCB5b3VyIGRhdGEgYmVzdCwgc28gd2UgbWlnaHQgY29uc2lkZXIgbGVhc3Qgc3F1YXJlcy4KCihhKSBMaW5lYXIgTW9kZWxzIGFzIE1hdHJpeCBNdWx0aXBsaWNhdGlvbgoKU28gd2UgbG9vayBmb3IgdGhlIGJldGFzIHRoYXQgbWluaW1pemUgdGhpcyBlcXVhdGlvbiwgYnV0IGJlZm9yZSB3ZSBwcm9jZWVkIHRvIHRoZSBvcHRpbWl6YXRpb24gcHJvY2VzcyB3ZSBjYW4gd3JpdGUgdGhlIGFib3ZlIGVxdWF0aW9uIGluIG1hdHJpeCBub3RhdGlvbiBhcyBmb2xsb3dzOgoKZmlyc3QsIGxldCB1cyBkZWZpbmUgdGhlIGZvbGxvd2luZyBtYXRyaWNlcywKJCRcYmVnaW57YWxpZ259WD1cYmVnaW57cG1hdHJpeH0xXFx4X3tpMX1cXHhfe2kyfVxceF97aTN9XFx4X3tpNH1cZW5ke3BtYXRyaXh9ICYgJiBcdGV4dHthbmR9ICYgJiBcYmV0YT1cYmVnaW57cG1hdHJpeH1cYmV0YV97MH1cXCBcYmV0YV97MX1cXCBcYmV0YV97Mn1cXCBcYmV0YV97M31cXCBcYmV0YV97NH1cZW5ke3BtYXRyaXh9XFwgXGVuZHthbGlnbn0kJAp0aGVuIHdlIGhhdmUsCiQkKFktIFhcYmV0YSlee1R9KFktWFxiZXRhKSQkCndoZXJlICRZJCBpcyB0aGUgdmVjdG9yIHRoYXQgY29udGFpbnMgZWFjaCBvYnNlcnZhdGlvbiAkeV97aX0kIGZvciBlYWNoICRpPTEsLi4uLE4kLgoKTm90ZSB0aGF0IHRoaXMgZm9ybXVsYSBpcyBlcXVpdmFsZW50IHRvIHRoZSBmaXJzdCBvbmUsIGJ1dCBlYXNpZXIgdG8gd3JpdGUgZG93biBhbmQgd29yayB3aXRoLiBJdCBpcyBub3Qgb25seSBlYXNpZXIgdG8gd3JpdGUgZG93biBvbiBhIHBpZWNlIG9mIHBhcGVyLCBidXQgYWxzbyBmYXN0ZXIgYXQgbGVhc3Qgb24gUi4KCkhlcmUgaXMgYSBzaW11bGF0aW9uIGV4YW1wbGUgdGhhdCBpbGx1c3RyYXRlcyBob3cgcXVpY2sgUiBjYW4gd29yayB3aXRoIG1hdHJpeCBhbGdlYnJhIGluc3RlYWQgb2YgdXNpbmcgYSBtb3JlIGNvbXBsZXggZm9ybXVsYSB0byBjb21wdXRlIHRoZSBzdW0gb2Ygc3F1YXJlczoKYGBge3IgQ29tcHV0ZXJzIG9mdGVuIHByZWZlciBtYXRyaWNlc30KeTwtcm5vcm0oMWU2KQp4PC1jYmluZChyZXAoMSwxZTYpLCByZXAoMDoxLCBlYWNoPTVlNSkpCmJldGE8LWMoMSwxKQpzeXN0ZW0udGltZSh7c3VtKHkteCUqJWJldGEpXjJ9KQpzeXN0ZW0udGltZSh7c3VtKHNhcHBseShzZXFfYWxvbmcoeSksZnVuY3Rpb24oaSkgeVtpXS14W2ksMV0qYmV0YVsxXS14W2ksMl0qYmV0YVsyXSleMil9KQpgYGAKU28gaW5zdGVhZCBvZiB3cml0aW5nIGRvd24gZWFjaCBzaW5nbGUgbW9kZWwgZm9yIGVhY2ggZWxlbWVudCwgZm9yIGVhY2ggaW5kaXZpZHVhbCB3ZSBpbnN0ZWFkIHdyaXRlIHRoZXNlIG1hdHJpY2VzLgokJFxiZWdpbnthbGlnbn1cdW5kZXJicmFjZXtcYmVnaW57cG1hdHJpeH14X3sxMH0gJiB4X3sxMX1cXCB4X3syMH0gJiB4X3syMX1cXCBcdmRvdHMgJiBcdmRvdHMgXFwgIHhfe04wfSAmIHhfe04xfVxlbmR7cG1hdHJpeH19X3tYfSAgXHVuZGVyYnJhY2V7XGJlZ2lue3BtYXRyaXh9XGJldGFfezB9XFwgXGJldGFfezF9XGVuZHtwbWF0cml4fX1fe1xiZXRhfT1cYmVnaW57cG1hdHJpeH1cYmV0YV97MH14X3sxMH0rXGJldGFfezF9eF97MTF9XFwgXGJldGFfezB9eF97MjB9K1xiZXRhX3sxfXhfezIxfVxcIFx2ZG90cyBcXCBcYmV0YV97MH14X3tOMH0rXGJldGFfezF9eF97TjF9IFxlbmR7cG1hdHJpeH1cZW5ke2FsaWdufSQkClNvIHdoZW4gd2Ugc2VlICRYXGJldGEkIGluIG91ciBtb2RlbCB3ZSBhc3N1bWUgdGhhdCAkWCQgaXMgYSBtYXRyaXggd2l0aCBlbnRyaWVzIGZvciBlYWNoIGluZGl2aWR1YWwgb24gdGhlIHJvd3MsIGFuZCB0aGVuIHRoZSBjb2x1bW5zIHJlcHJlc2VudCB0aGUgZGlmZmVyZW50IGNvdmFyaWF0ZXMgb3IgdmFyaWFibGVzIHVzaW5nIGluIHRoZSBtb2RlbCwgb24gdGhlIG90aGVyIGhhbmQgJFxiZXRhJCBpcyBhbm90aGVyIGxpdHRsZSBtYXRyaXggdGhhdCBjb250YWlucyB0aGUgcGFyYW1ldGVycyBvZiB0aGUgbW9kZWwuIAoKSW5zdGVhZCBvZiB0aGUgZm9ybXVsYSB3aXRoIGFsbCB0aGUgaW5kaWNlcywgd2UgY2FuIGFjdHVhbGx5IHdyaXRlIHRoZXNlIG1hdHJpY2VzCgooYSkgU29tZSBTcGVjaWZpYyBMaW5lYXIgbW9kZWxzIChFeHByZXNzaW5nIGV4cGVyaW1lbnRhbCBkZXNpZ24gdXNpbmcgUiBmb3JtdWxhKQoKSW4gdGhpcyBtb2R1bGUgd2UnbGwgc2hvdyBob3cgdG8gdXNlIHRoZSB0d28gUiBiYXNlIGZ1bmN0aW9uczoKCiogJ2Zvcm11bGEnCgoqICdtb2RlbC5tYXRyaXgnCgppbiBvcmRlciB0byBwcm9kdWNlIGRlc2lnbiBtYXRyaWNlcyBmb3IgYSB2YXJpZXR5IG9mIGxpbmVhciBtb2RlbHMKCldlJ3JlIGdvaW5nIHRvIGJlIGJ1aWxkaW5nIG1hdHJpY2VzIGZpbGxlZCBieSB6ZXJvcyBhbmQgb25lcyB0aGF0IGdldCBtdWx0aXBsaWVkIGJ5IGJldGEgaW4gYSBsaW5lYXIgbW9kZWwuCmBgYHtyfQp4PC1jKDEsMSwyLDIpCmY8LWZvcm11bGEofngpICMgZS5nIGxtKHl+YmV0YTF4MStlcHNpbG9uKQpmCmBgYAoKVGhlIG1vZGVscyBmaXQgYnksIGUuZy4sIHRoZSBsbSBhbmQgZ2xtIGZ1bmN0aW9ucyBhcmUgc3BlY2lmaWVkIGluIGEgY29tcGFjdCBzeW1ib2xpYyBmb3JtLiAgVGhlIH4gb3BlcmF0b3IgaXMgYmFzaWMgaW4gdGhlIGZvcm1hdGlvbiBvZiBzdWNoIG1vZGVscy4gQW4gZXhwcmVzc2lvbiBvZiB0aGUgZm9ybSB5IH4gbW9kZWwgaXMgaW50ZXJwcmV0ZWQgYXMgYSBzcGVjaWZpY2F0aW9uIHRoYXQgdGhlIHJlc3BvbnNlIHkgaXMgbW9kZWxlZCBieSBhIGxpbmVhciBwcmVkaWN0b3Igc3BlY2lmaWVkIHN5bWJvbGljYWxseSBieSBtb2RlbC4gU3VjaCBhIG1vZGVsIGNvbnNpc3RzIG9mIGEgc2VyaWVzIG9mIHRlcm1zIHNlcGFyYXRlZCBieSArIG9wZXJhdG9ycy4KYGBge3J9Clg8LW1vZGVsLm1hdHJpeChmKSAjIGl0IGdpdmVzIHVzIGFuIGludGVyY2VwdCBmaWxsZWQgYnkgYSB2ZWN0b3Igb2Ygb25lcyBhbmQgd2UnbGwgaGF2ZSBhIGNvbHVtbiB4IHdoaWNoIGdpdmVzIHRoZSB2YXJpYWJsZSB4IGFzIGEgY29sdW1uClgKYGBgCmBgYHtyfQpjbGFzcyh4KQpjbGFzcyhYKQpgYGAKCgpNb2RlbC5tYXRyaXggd2lsbCBjcmVhdGUgYSBkZXNpZ24gbWF0cml4IHVzaW5nIHRoYXQgZm9ybXVsYSBpZiB5b3UgZG9uJ3QgcHJvdmlkZSBhbnkgZGF0YSwgaXQgd2lsbCB1c2UgdGhlIGVudmlyb25tZW50IG9mIHRoZSBvYmplY3QgZiBpbnRvIHRoZSBmb3JtdWxhCgpTbyBpZiB3ZSB1c2UgYSBmYWN0b3IgYW5kIGJ1aWxkIGEgbW9kZWwgbWF0cml4IHVzaW5nIHRoZSBmYWN0b3IgeCwgaXQgd291bGQgbG9vayBkaWZmZXJlbnQsCmBgYHtyfQp4PC1mYWN0b3IoYygxLDEsMiwyKSkKeApYPC1tb2RlbC5tYXRyaXgofngpClgKYGBgCmluc3RlYWQgb2YgaGF2aW5nIGEgY29sdW1uIHdpdGggJCgxLDEsMiwyKSQgdmVjdG9yIHdlJ2xsIGhhdmUgYSBjb2x1bW4gd2l0aCAkKDAsMCwxLDEpJCB2ZWN0b3IsIHRoYXQgdGFrZXMgdGhlIHZhbHVlIG9mIDAgd2hlbiAkeF97aWp9PTEkIGFuZCAxIHdoZW4gJHhfe2lqfT0yJCAoZm9yIGVhY2ggJGlcaW5cezEsLi4uLE5cfSQgYW5kICRqXGluXHsxLC4uLixwXH0kKQoKV2UgYWdhaW4gaGF2ZSBhbiBpbnRlcmNlcHQgZmlsbGVkIGJ5IGEgdmVjdG9yIG9mIG9uZXMgYW5kIGEgY29sdW1uIHgyIHdoaWNoIGdpdmVzIHRoZSB2YXJpYWJsZSAkeCQgcmVwcmVzZW50ZWQgYXMgYSBpbmRpY2F0b3IgdmFyaWFibGUuIAoKTm93IGxldCdzIGNvbnN0cnVjdCBhIGZhY3RvciAkeCQgd2hpY2ggaGFzIHRocmVlIGRpZmZlcmVudCBsZXZlbHM6CmBgYHtyfQp4PC1mYWN0b3IoYygxLDEsMiwyLDMsMykpCm1vZGVsLm1hdHJpeCh+eCkKYGBgCk9uZSBjYW4gYWN0dWFsbHkgZGVmaW5lIG1hdHJpY2VzIHdpdGggaW5kaWNhdG9yIHZhcmlhYmxlcyBhcyB2ZWN0b3JzIGRlZmluaW5nIG5vbi1udW1lcmljYWwgZW50cmllczoKCmBgYHtyfQp4PC1mYWN0b3IoYygxLDEsMSwxLDIsMiwyLDIpKQp5PC1mYWN0b3IoYygiYSIsImEiLCJiIiwiYSIsImIiLCJhIiwiYSIsImIiKSkgCm1vZGVsLm1hdHJpeCh+eCt5KQpgYGAKQXMgYmVmb3JlIHdlIGhhdmUgYW4gImludGVyY2VwdCIgYW5kIHR3byB2ZWN0b3JzIGV4cHJlc3NlZCBhcyBpbmRpY2F0b3IgdmFyaWFibGVzLiBJbiB2ZWN0b3IgIngyIiB2YXJpYWJsZSB0YWtlcyB2YWx1ZSBvZiAwIHdoZW4gJHhfe2lqfT0xJCBhbmQgMSBvdGhlcndpc2UuIExpa2V3aXNlLCBpbiB2ZWN0b3IgInliIiB2YXJpYWJsZSB0YWtlcyB0aGUgdmFsdWUgb2YgMCB3aGVuICR5X3tpan09JCJhIiBhbmQgMSBvdGhlcndpc2UuCgpBbHNvIHlvdSBjYW4gc3BlY2lmeSBhbiBpbnRlcmFjdGlvbiBiZXR3ZWVuIHRoZSB2YXJpYWJsZXMgdXNpbmcgIjoiLCBzbwpgYGB7cn0KbW9kZWwubWF0cml4KH54K3kreDp5KSAjdGhpcyBtb2RlbCBkZXNjcmliZXMgdGhlIGludGVyYWN0aW9uIGRlc2NyaWJlZCBiZWxvdwptb2RlbC5tYXRyaXgofngqeSkgI211bHRpcGxpY2F0aW9uLiAKYGBgClNvICJ4Mjp5YiIgdmVjdG9yIHdpbGwgdGFrZSB2YWx1ZSBvZiAxIGlmZiBib3RoICR4X3tpan09MiQgYW5kICR5X3tpan09JCJiIiBob2xkcywgYW5kIDAgb3RoZXJ3aXNlLgoKV2UgYWxzbyBjYW4gY3JlYXRlIGEgbWF0cml4IHdpdGggdGhlIG9wcG9zaXRlIGNvbmRpdGlvbiBmb3IgdGhlIGluZGljYXRvciB2YXJpYWJsZSAkeCQ6CmBgYHtyfQp4PC0gZmFjdG9yKGMoMSwxLDIsMikpCm1vZGVsLm1hdHJpeCh+eCkKeDwtcmVsZXZlbCh4LCAiMiIpCm1vZGVsLm1hdHJpeCh+eCkKeDwtZmFjdG9yKHgsbGV2ZWxzPWMoIjEiLCIyIikpCngKYGBgCgpTb21lIG90aGVyIG9wZXJhdGlvbnM6CmBgYHtyfQp6PC0xOjQKbW9kZWwubWF0cml4KH56KSAjej0oMSwyLDMsNCkKbW9kZWwubWF0cml4KH4wK3opICMgbm8gaW50ZXJjZXB0IHZlY3Rvcgptb2RlbC5tYXRyaXgofnorSSh6XjIpKSAjYWRkcyBhbm90aGVyIGNvbHVtbiB0aGF0IGlzIHRoZSBzcXVhcmUgb2YgegpgYGAKIAogTm93IHdlJ3JlIGdvaW5nIHRvIHNob3cgaG93IHRvIHBlcmZvcm0gbGluZWFyIG1vZGVscyBpbiBSLCBhbmQgd2UgYXJlIGdvaW5nIHRvIGRvIGEgc2ltcGxlIHR3byBncm91cCBjb21wYXJpc29uLiBXZSBuZWVkIGZpcnN0IGRvIGxvYWQgaW4gc29tZSBkYXRhIG9mIG1pY2Ugd2VpZ2h0cywgbWljZSB3aGljaCB3ZXJlIGFyZSBnaXZlbiB0d28gZGlldHMuIE9uZSB3YXMgYSBoaWdoLWZhdCBkaWV0IGFuZCBvbmUgd2FzIGEgY29udHJvbCBkaWV0LgpgYGB7cn0KI2luc3RhbGwucGFja2VnZXMoImRvd25sb2FkZXIiLCJnZ3Bsb3QyIikKI2xpYnJhcnkoZG93bmxvYWRlcixnZ3Bsb3QyKQp1cmw8LSJodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vZ2Vub21pY3NjbGFzcy9kYWdkYXRhL21hc3Rlci9pbnN0L2V4dGRhdGEvZmVtYWxlTWljZVdlaWdodHMuY3N2IgpmaWxlbmFtZTwtImZlbWFsZU1pY2VXZWlnaHRzLmNzdiIKaWYgKCFmaWxlLmV4aXN0cyhmaWxlbmFtZSkpZG93bmxvYWQodXJsLGZpbGVuYW1lKQpkYXQ8LXJlYWQuY3N2KGZpbGVuYW1lKQpwPC1nZ3Bsb3QoZGF0KQpwPC1wK2Flcyh4PWRhdCREaWV0LHk9ZGF0JEJvZHl3ZWlnaHQpCnA8LXArc2NhbGVfc2l6ZV9tYW51YWwodmFsdWVzPWMoMC44LDAuOCwwLjgsMC41KSkKcDwtcCtnZW9tX3BvaW50KCkrZ2VvbV9qaXR0ZXIod2lkdGg9MC4xKQpwPC1wK3hsYWIoIkRpZXQiKSt5bGFiKCJCb2R5IFdoZWlnaHQiKStnZ3RpdGxlKCJCb2R5IFdoZWlnaHQgb3ZlciBEaWV0IikKcApgYGAKImNob3ciIGlzIHRoZSBjb250cm9sIHNhbXBsZSBhbmQgImhmIiBpcyB0aGUgaGlnaC1mYXQgZGlldC4gSW4gZGF0YToKYGBge3J9CmRhdFsxMToxNCxdCmBgYApmaXJzdCBjb2x1bW4gaW5kaWNhdGVzIHdoZXRoZXIgYSBtb3VzZSB3YXMgZXhwb3NlZCB0byBhIGhpZ2gtZmF0IGRpZXQgb3IgYSBjb250cm9sbGVkIGRpZXQuCgpMb29raW5nIG9ubHkgdG8gdGhlIGNoYXJ0IHdlIGNhbiBzZWUgdGhhdCBtaWNlIHBvcHVsYXRpb24gd2hpY2ggd2VyZSBnaXZlbiB0aGUgY29udHJvbCBkaWV0IGhhdmUgc2xpZ2h0bHkgbG93ZXIgYm9keSB3ZWlnaHRzLCBvbiBhdmVyYWdlLCB0aGFuIHRoZSBtaWNlIHRoYXQgd2VyZSBnaXZlbiB0aGUgaGlnaC1mYXQgZGlldCwgYWx0aG91Z2ggdGhlcmUncyBvdmVybGFwIGJldHdlZW4gdGhlc2UgdHdvIGdyb3Vwcy4KCldlIHdhbnQgdG8gYW5hbHl6ZSB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZXNlIHR3byBncm91cHMgdXNpbmcgYSBsaW5lYXIgbW9kZWwuCgpGaXJzdCwgbGV0IHVzIGNvbnN0cnVjdCB0aGUgbWF0cml4ICRYJCB0aGF0IHdlIGhhdmUgc2VlbiBpbiB0aGUgbGluZWFyIG1vZGVsIGZvcm11bGEsIHNvIHdlIGNhbiBzZWUgd2hhdCBpcyBoYXBwZW5pbmcgaW50ZXJuYWxseSBhbmQgaG93IFIgaXMgdGFraW5nIHRoZSBkYXRhOgpgYGB7cn0KZGlldDwtZmFjdG9yKGRhdCREaWV0KQpsZXZlbHMoZGlldCkKWDwtbW9kZWwubWF0cml4KH5kaWV0LGRhdGE9ZGF0KQpYCmBgYApOb3csIHdlJ3JlIGdvaW5nIHRvIGp1c3QgcnVuIHRoZSBtb2RlbC4gCgpZb3UgZG9uJ3QgYWN0dWFsbHkgaGF2ZSB0byBzcGVjaWZ5IHRoZSAkWCQgbWF0cml4LiBXZSB1c2UgdGhlIGxtKHl+eCkgZnVuY3Rpb24gZm9yIGxpbmVhciBtb2RlbC4KCgpgYGB7cn0KZml0PC1sbShCb2R5d2VpZ2h0fkRpZXQsIGRhdGE9ZGF0KQpzdW1tYXJ5KGZpdCkKKGNvZWZzPC1jb2VmKGZpdCkpCmBgYApTbyB3ZSBoYXZlIHRoZSBpbnRlcmNlcHQgJFxoYXR7XGJldGF9X3swfT0yMy44MTMzMzMkIGFuZCB0aGUgZGlmZmVyZW5jZSBpbiBhdmVyYWdlIHdlaWdodCBiZXR3ZWVuIGhpZ2gtZmF0IGFuZCBjb250cm9sIGRpZXQgaXMgJFxoYXR7XGJldGF9XzE9My4wMjA4MzMkLgoKVG8gc2hvdyB0aGF0IG91ciBtYXRoZW1hdGljYWwgbW9kZWwgaXMgY29uc2lzdGVudCB3aXRoIHRoZXNlIHJlc3VsdHMsIHJlY2FsbCAKJCRcaGF0e1xiZXRhfT1cYmVnaW57cG1hdHJpeH1caGF0e1xiZXRhfV97MH1cXCBcaGF0e1xiZXRhX3sxfX1cZW5ke3BtYXRyaXh9PShYXntUfVgpXnstMX1YXntUfVkkJAp0aHVzLApgYGB7cn0KWTwtbWF0cml4KGRhdCRCb2R5d2VpZ2h0LG5jb2w9MSkKYmV0YS5oYXQ8LXNvbHZlKHQoWCklKiVYKSUqJSh0KFgpJSolWSkKYmV0YS5oYXQKYGBgCldlIGhhdmUgYW5vdGhlciB3YXkgdG8gbG9vayBhdCB0aGVzZSByZXN1bHRzIGZyb20gdGhpcyBsaW5lYXIgbW9kZWw6CgoqIFRvIGdldCB0aGUgY29lZmZpY2llbnRzIHdlIG5vdCBuZWVkIHRvIHJ1biBhIGxpbmVhciBtb2RlbC4gV2Ugb25seSBuZWVkIHRvIGxvb2sgYXQgdGhlIG1lYW5zIG9mIGVhY2ggZ3JvdXAuIAogICAqIFRoZSBpbnRlcmNlcHQgJFxoYXR7XGJldGF9X3swfSQgaXMgbm8gbW9yZSB0aGFuIHRoZSBzYW1wbGUgbWVhbiBvZiBjb250cm9sIGdyb3VwLCBhbmQKICAgICogJFxoYXR7XGJldGF9X3sxfSQgYXMgc2FpZCBiZWZvcmUgaXMgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgc2FtcGxlIG1lYW5zOiAgICAKCmBgYHtyfQpzPC1zcGxpdChkYXQkQm9keXdlaWdodCxkYXQkRGlldCkKbWVhbihzW1siY2hvdyJdXSkgIyBzcGxpdCBkaXZpZGVzIHRoZSBkYXRhIGluIHRoZSB2ZWN0b3IgeCBpbnRvIHRoZSBncm91cHMgZGVmaW5lZCBieSBmLiBUaGUgcmVwbGFjZW1lbnQgZm9ybXMgcmVwbGFjZSB2YWx1ZXMgY29ycmVzcG9uZGluZyB0byBzdWNoIGEgZGl2aXNpb24uIHVuc3BsaXQgcmV2ZXJzZXMgdGhlIGVmZmVjdCBvZiBzcGxpdC4KYGBgIApgYGB7cn0KbWVhbihzW1siaGYiXV0pLW1lYW4oc1tbImNob3ciXV0pCmBgYAoKKiBDb21wYXJpbmcgYSBzaW5nbGUgMi1ncm91cCB0byBhIHQtdGVzdDoKYGBge3IgVC12YWx1ZX0Kc3VtbWFyeShmaXQpJGNvZWZmaWNpZW50cwoodHRlc3Q8LXQudGVzdChzW1siY2hvdyJdXSwgc1tbImhmIl1dLHZhci5lcXVhbCA9IFQpKQpzdW1tYXJ5KGZpdCkkY29lZmZpY2llbnRzWzIsM10KdHRlc3Qkc3RhdGlzdGljCnQudGVzdCggc1tbImhmIl1dLHNbWyJjaG93Il1dLHZhci5lcXVhbCA9IFQpJHN0YXRpc3RpYwpgYGAKCgpMaW5lYXIgTW9kZWxzIGluIFByYWN0aWNlIEV4ZXJjaXNlcyAjMQoKWW91IGNhbiBtYWtlIGEgZGVzaWduIG1hdHJpeCAkWCQgZm9yIGEgdHdvIGdyb3VwIGNvbXBhcmlzb24gZWl0aGVyIHVzaW5nIG1vZGVsLm1hdHJpeCgpIG9yIHNpbXBseSB3aXRoOgpgYGB7cn0KWCA9IGNiaW5kKHJlcCgxLG54ICsgbnkpLApyZXAoYygwLDEpLApjKG54LCBueSkpKQpgYGAKRm9yIGEgY29tcGFyaXNvbiBvZiB0d28gZ3JvdXBzLCB3aGVyZSB0aGUgZmlyc3QgZ3JvdXAgaGFzICRueD01JCBzYW1wbGVzLCBhbmQgdGhlIHNlY29uZCBncm91cCBoYXMgJG55PTckIHNhbXBsZXMsIHdoYXQgaXMgdGhlIGVsZW1lbnQgaW4gdGhlIDFzdCByb3cgYW5kIDFzdCBjb2x1bW4gb2YgJFhee1R9WCQ/CgpgYGB7cn0Kbng8LTUKbnk8LTcKWCA8LSBjYmluZChyZXAoMSxueCArIG55KSwKcmVwKGMoMCwxKSwKYyhueCwgbnkpKSkKWHRYPC0odChYKSUqJVgpClh0WFsxLDFdCmBgYApMaW5lYXIgTW9kZWxzIGluIFByYWN0aWNlIEV4ZXJjaXNlcyAjMgoKV2hhdCBhcmUgYWxsIHRoZSBvdGhlciBlbGVtZW50cyBvZiAkWF57VH1YJD8KYGBge3J9Clh0WApgYGAKCiogRml0dGluZyBMaW5lYXIgTW9kZWxzIGFuZCBUZXN0aW5nCgpSZWNhbGwgdGhlIExTRSBlc3RpbWF0ZXM6CiQkXGhhdHtcYmV0YX09KFhee1R9WCleey0xfVhee1R9WSQkCk9uY2UgeW91IHdyaXRlIGRvd24gdGhlIG1hdHJpY2VzIGFzIHdlIGRpZCBiZWZvcmUgeW91IGNhbiBmaW5kIHRoZSBzb2x1dGlvbiB0byBlc3RpbWF0ZSB0aGUgcGFyYW1ldGVycy4KCldoZW4gd2UncmUgdGVzdGluZyBpZiBhIHBhcnRpY3VsYXIgZXN0aW1hdGVkIHBhcmFtZXRlciBpcyBzdGF0aWNhbGx5IHNpZ25pZmljYW50IHdlJ3JlIGdvaW5nIHRvIGhhdmUgdG8ga25vdyBob3cgbXVjaCBpdCB2YXJpZXMsIGFuZCB3ZSdyZSBnb2luZyB0byBoYXZlIHRvIGNvbXB1dGUgaXRzIHN0YW5kYXJkIGVycm9yLiBUaGlzIGlzIGJhc2ljYWxseSB0aGUgdC10ZXN0LgoKV2UgaGF2ZSBhbiBlc3RpbWF0ZSBhbmQgaXRzIHN0YW5kYXJkIGVycm9yIHN1Y2ggdGhhdDoKJCRcZnJhY3tcdGV4dHtzaWduYWx9fXtcdGV4dHtub2ljZX19PVxmcmFje1xoYXR7XGJldGF9X2l9e1NFKFxoYXR7XGJldGF9X2kpfSQkCiQkU0UoXGhhdHtcYmV0YX1fe2l9KT1cc3FydHtzXnsyfShYXntUfVgpXnstMX1fe2lpfX0kJAp3aGVyZSAkc157Mn0kIGlzIHRoZSBzYW1wbGUgdmFyaWFuY2UuCgoKCgoK