Variance Reduction

Assume that we have two variables, X and Y that are related according to the hypothetical model \(Y = \beta_0 + \beta_1 X + e\). We collect a sample consisting of n paired observations of the form \((x_i,y_i)\). We then use the sample to create a fitted model of the form \(\hat Y = \hat \beta_0 + \hat \beta_1 X\).

Assume we wish to make a prediction about the value of \(Y\) for a new observation. Without considering the effect that \(X\) has on \(Y\), our best point estimate for the new value of \(Y\) would be \(\bar y\). To take into account the uncertainty that we know exists in our prediction, we could create a 95% prediction interval around our point prediction, \(\bar y\). Such an interval is shown in the plot on the left below. We will discuss how prediction intervals are formed in a later lesson.

If, however, we know the value of \(X\) in the new observation, then a better estimate for the value of \(Y\) would be given by \(E[Y | X = x]= \beta_0 + \beta_1 x\), which can be approximated using our fitted model. This gives us a point estimate of \(\hat y = \hat \beta_0 + \hat \beta_1 x\). Again, we know that there is some uncertainty in our prediction, so we might create a 95% prediction interval around the point prediction \(\hat y\). Such a prediction interval is shown in the plot on the right below.

Notice that the prediction interval in the plot on the right is considerably shorter than the one on the left. By taking into account the effect that \(X\) has on \(Y\), we are able to reduce the uncertainty, or variance, in our prediction. This allows us to make more precise predictions.

In this lesson, we will discuss a method of measuring the amount of variance reduction we obtain in using a regression model to explain a portion of the variation in \(Y\) through its relationship with \(X\).



SST, SSR, and SSE

We will use a quantity denoted by \(r^2\) to measure the proportion of the variance in our response variable \(Y\) that is explained by the relationship between \(Y\) and a predictor \(X\). Before we define \(r^2\), we first need to introduce some related quantities.

For a particular observation \(y_i\), notice that the quantity \(d_i = y_i - \bar y\) measures the amount by which the observation deviates from the sample mean. We will decompose this quantity into two pieces.

Notice that \(d_i = r_i + \hat e_i\).

We now sum the squares of each of these three quantities over all of the points in our sample.

SST = SSE + SSR

An important relationship between these three sums is given by the equation \(SST = SSE + SSR\).

To establish this result, we will need to make use of the following two identities:

The first identity is one of our two normal equations. The second identity can be derived from the two normal equations. Armed with these identities, we may procede with our proof that \(SST = SSE + SSR\) as follows:

\(\hspace{30pt} SST = \sum (y_i - \bar{y})^2\)

\(\hspace{30pt} SST = \sum [(\hat e_i + \hat y_i) - \bar{y}]^2\)

\(\hspace{30pt} SST = \sum [\hat e_i + (\hat y_i - \bar{y})]^2\)

\(\hspace{30pt} SST = \sum [\hat e_i^2 + 2\hat e_i (\hat y_i - \bar{y}) + ( \hat y_i - \bar y)^2]\)

\(\hspace{30pt} SST = \sum \hat e_i^2 + 2\sum \hat e_i (\hat y_i - \bar{y}) + \sum ( \hat y_i - \bar y)^2\)

\(\hspace{30pt} SST = SSE + 2 \sum( \hat e_i \hat y_i - \hat e_i\bar{y}) + SSR\)

\(\hspace{30pt} SST = SSE + 2 \sum \hat e_i \hat y_i - 2 \bar{y}\sum\hat e_i + SSR\)

\(\hspace{30pt} SST = SSE + 0 - 0 + SSR\)

\(\hspace{30pt} SST = SSE + SSR\)

r-Squared

Intuitive explanations of the meaning of the variables \(SST\), \(SSR\), and \(SSE\) are as follows:

Ideally, we would like for \(SSE\) to be close to 0 and for \(SSR\) to thus be close to \(SST\). We can measure the proportion of the variance in \(Y\) that is explained by our regression model using the following quantity:

\[r^2 = \frac{SSR}{SST}\]

Note that since \(0 \leq SSR \leq SST\), we get that \(0 \leq r^2 \leq 1\). The quantity \(r^2\) is a diagnostic tool that is commonly uses to measure the quality of the fit in a regression model.

Notice that since \(SST = SSR + SSE\), we can rewrite the formula for \(r^2\) as follows:

\[r^2 = \frac{SSR}{SST} = 1 - \frac{SSE}{SSR}\]

The \(r^2 = 1 - \frac{SSE}{SSR}\) formula for \(r^2\) is often the more useful of the two formulas, since we will have other reasons for calculating \(SSE\).

Residual Standard Error

Consider the hypothetical model \(Y = \beta_0 + \beta_1 X + e\). If we know the value of the variable \(X\), then the only uncertainty in the value of \(Y\) is due to the error term \(e\). We often assume that \(E[e]=0\). In that case, \(Var[e] = \sigma_e^2\) provides a measurement of the amount of error inherent in our model.

Since we do not generally have access to the hypothetical model, we cannot calulcate values of \(e\) exactly. However, we can construct a fitted model, \(Y = \hat\beta_0 + \hat\beta_1 X + \hat e\) and then use \(\hat e\) as an approximation of \(e\). As such, we should be able to use the observed residuals \(\hat e_i\) to find an approximation of \(\sigma_e^2\).

It can be shown that the following expression provides an unbiased estimate of \(\sigma_e^2\):

\[s^2 = \frac{SSE}{n-2} = \frac{1}{n-2} \sum_{i=1}^n \hat e_i^2\] The square root of this quantity is called the residual standard error (RSE). It approximates the standard deviation of the error term \(e\).

\[s = \sqrt{\frac{SSE}{n-2}} = \sqrt{\frac{1}{n-2} \sum_{i=1}^n \hat e_i^2}\]

Using R to Calculate r-Squared and RSE

Let’s return to the Pearson data set. In the code chunk below, we load the data, create an OLS regression model, and then print a summary of that model.

myData <- read.table("father_son.txt", sep="\t", header=TRUE)
mod <- lm(sheight ~ fheight, myData)
summary(mod)

Call:
 Median      3Q     Max 
-8.8772 -1.5144 -0.0079  1.6285  8.9685 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) 33.88660    1.83235   18.49   <2e-16 ***
fheight      0.51409    0.02705   19.01   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.437 on 1076 degrees of freedom
Multiple R-squared:  0.2513,    Adjusted R-squared:  0.2506 
F-statistic: 361.2 on 1 and 1076 DF,  p-value: < 2.2e-16

We can see from the summary that:

r-Squared and Correlation

The value \(r^2\) is related to the sample correlation \(\rho_{X,Y} = \mathrm{corr}[X,Y]\). In fact, it can be shown that:

\[r^2 = \mathrm{corr}[X,Y]\]

To establish this result, we first need to derive an alternate form for the expression \(SSR\). Notice that:

\(\hspace{30pt} SSR = \sum\limits_{i=1}^n (\hat y_i - \bar y)^2\)

\(\hspace{30pt} SSR = \sum\limits_{i=1}^n \left[\left(\hat \beta_0 + \hat \beta_1 x_i \right) - \bar y\right]^2\)

\(\hspace{30pt} SSR = \sum\limits_{i=1}^n \left[\left(\bar y - \hat\beta_1\bar x \right) + \hat \beta_1 x_i - \bar y\right]^2\)

\(\hspace{30pt} SSR = \sum\limits_{i=1}^n \left( - \hat\beta_1\bar x + \hat \beta_1 x_i\right)^2\)

\(\hspace{30pt} SSR = \beta_1^2 \sum\limits_{i=1}^n \left( x_i - \bar x\right)^2\)

\(\hspace{30pt} SSR = \beta_1^2 SXX\)

\(\hspace{30pt} SSR = \left(\frac{SXY}{SXX} \right)^2 SXX\)

\(\hspace{30pt} SSR = \frac{\left(SXY \right)^2}{SXX}\)

Now, recall that \(r^2 = \frac{SSR}{SST}\). We will substitute the expression above in for \(SSR\), and then simplify.

\(\hspace{30pt} r^2 = \frac{SSR}{SST}\)

\(\hspace{30pt} r^2 = \frac{\left(SXY \right)^2}{SXX} \frac{1}{SST}\)

\(\hspace{30pt} r^2 = \frac{\left(SXY \right)^2}{SXX \cdot SST}\)

\(\hspace{30pt} r^2 = \frac{\left(SXY \right)^2}{SXX \cdot SST}\)

\(\hspace{30pt} r^2 = \frac{\left(\sum\limits_{i=1}^n (x_i - \bar x)(y_i - \bar y) \right)^2}{\sum\limits_{i=1}^n (x_i - \bar x)^2 \cdot \sum\limits_{i=1}^n (y_i - \bar y)^2}\)

\(\hspace{30pt} r^2 = \left(\frac{\sum\limits_{i=1}^n (x_i - \bar x)(y_i - \bar y) }{\sqrt{\sum\limits_{i=1}^n (x_i - \bar x)^2} \cdot \sqrt{\sum\limits_{i=1}^n (y_i - \bar y)^2}} \right)^2\)

\(\hspace{30pt} r^2 = \left( \frac{\mathrm{cov}[X,Y]}{s_X s_Y} \right)^2\)

\(\hspace{30pt} r^2 = \left( \mathrm{corr}[X,Y] \right)^2\)

This completes our proof.

Correlation Between \(Y\) and \(\hat Y\)

It can also be shown that the correlation between the fitted value \(\hat Y\) and the response \(Y\) is exactly the same as that between the predictor \(X\) and the response \(Y\). In other words:

\[\mathrm{corr}\left[\hat Y,Y \right] = \mathrm{corr}\left[X,Y\right]\]

The proof of this fact is left as an exercise.

LS0tDQp0aXRsZTogIkxlc3NvbiAwOCAtIHItU3F1YXJlZCINCmF1dGhvcjogIlJvYmJpZSBCZWFuZSINCm91dHB1dDoNCiAgaHRtbF9ub3RlYm9vazoNCiAgICB0aGVtZTogZmxhdGx5DQogICAgdG9jOiB0cnVlDQogICAgdG9jX2RlcHRoOiAyDQotLS0NCg0KDQpgYGB7ciBlY2hvPUZBTFNFLCByZXN1bHRzPSdoaWRlJywgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0NCiNyZXF1aXJlKGdyaWRFeHRyYSkNCmBgYA0KDQoNCiMgVmFyaWFuY2UgUmVkdWN0aW9uDQoNCkFzc3VtZSB0aGF0IHdlIGhhdmUgdHdvIHZhcmlhYmxlcywgYFhgIGFuZCBgWWAgdGhhdCBhcmUgcmVsYXRlZCBhY2NvcmRpbmcgdG8gdGhlIGh5cG90aGV0aWNhbCBtb2RlbCAkWSA9IFxiZXRhXzAgKyBcYmV0YV8xIFggKyBlJC4gV2UgY29sbGVjdCBhIHNhbXBsZSBjb25zaXN0aW5nIG9mIGBuYCBwYWlyZWQgb2JzZXJ2YXRpb25zIG9mIHRoZSBmb3JtICQoeF9pLHlfaSkkLiBXZSB0aGVuIHVzZSB0aGUgc2FtcGxlIHRvIGNyZWF0ZSBhIGZpdHRlZCBtb2RlbCBvZiB0aGUgZm9ybSAkXGhhdCBZID0gXGhhdCBcYmV0YV8wICsgXGhhdCBcYmV0YV8xIFgkLg0KDQpBc3N1bWUgd2Ugd2lzaCB0byBtYWtlIGEgcHJlZGljdGlvbiBhYm91dCB0aGUgdmFsdWUgb2YgJFkkIGZvciBhIG5ldyBvYnNlcnZhdGlvbi4gV2l0aG91dCBjb25zaWRlcmluZyB0aGUgZWZmZWN0IHRoYXQgJFgkIGhhcyBvbiAkWSQsIG91ciBiZXN0IHBvaW50IGVzdGltYXRlIGZvciB0aGUgbmV3IHZhbHVlIG9mICRZJCB3b3VsZCBiZSAkXGJhciB5JC4gVG8gdGFrZSBpbnRvIGFjY291bnQgdGhlIHVuY2VydGFpbnR5IHRoYXQgd2Uga25vdyBleGlzdHMgaW4gb3VyIHByZWRpY3Rpb24sIHdlIGNvdWxkIGNyZWF0ZSBhIDk1JSBwcmVkaWN0aW9uIGludGVydmFsIGFyb3VuZCBvdXIgcG9pbnQgcHJlZGljdGlvbiwgJFxiYXIgeSQuIFN1Y2ggYW4gaW50ZXJ2YWwgaXMgc2hvd24gaW4gdGhlIHBsb3Qgb24gdGhlIGxlZnQgYmVsb3cuIFdlIHdpbGwgZGlzY3VzcyBob3cgcHJlZGljdGlvbiBpbnRlcnZhbHMgYXJlIGZvcm1lZCBpbiBhIGxhdGVyIGxlc3Nvbi4gICANCg0KSWYsIGhvd2V2ZXIsIHdlIGtub3cgdGhlIHZhbHVlIG9mICRYJCBpbiB0aGUgbmV3IG9ic2VydmF0aW9uLCB0aGVuIGEgYmV0dGVyIGVzdGltYXRlIGZvciB0aGUgdmFsdWUgb2YgJFkkIHdvdWxkIGJlIGdpdmVuIGJ5ICRFW1kgfCBYID0geF09IFxiZXRhXzAgKyBcYmV0YV8xIHgkLCB3aGljaCBjYW4gYmUgYXBwcm94aW1hdGVkIHVzaW5nIG91ciBmaXR0ZWQgbW9kZWwuIFRoaXMgZ2l2ZXMgdXMgYSBwb2ludCBlc3RpbWF0ZSBvZiAkXGhhdCB5ID0gXGhhdCBcYmV0YV8wICsgXGhhdCBcYmV0YV8xIHgkLiBBZ2Fpbiwgd2Uga25vdyB0aGF0IHRoZXJlIGlzIHNvbWUgdW5jZXJ0YWludHkgaW4gb3VyIHByZWRpY3Rpb24sIHNvIHdlIG1pZ2h0IGNyZWF0ZSBhIDk1JSBwcmVkaWN0aW9uIGludGVydmFsIGFyb3VuZCB0aGUgcG9pbnQgcHJlZGljdGlvbiAkXGhhdCB5JC4gU3VjaCBhIHByZWRpY3Rpb24gaW50ZXJ2YWwgaXMgc2hvd24gaW4gdGhlIHBsb3Qgb24gdGhlIHJpZ2h0IGJlbG93LiANCg0KTm90aWNlIHRoYXQgdGhlIHByZWRpY3Rpb24gaW50ZXJ2YWwgaW4gdGhlIHBsb3Qgb24gdGhlIHJpZ2h0IGlzIGNvbnNpZGVyYWJseSBzaG9ydGVyIHRoYW4gdGhlIG9uZSBvbiB0aGUgbGVmdC4gQnkgdGFraW5nIGludG8gYWNjb3VudCB0aGUgZWZmZWN0IHRoYXQgJFgkIGhhcyBvbiAkWSQsIHdlIGFyZSBhYmxlIHRvIHJlZHVjZSB0aGUgdW5jZXJ0YWludHksIG9yIHZhcmlhbmNlLCBpbiBvdXIgcHJlZGljdGlvbi4gVGhpcyBhbGxvd3MgdXMgdG8gbWFrZSBtb3JlIHByZWNpc2UgcHJlZGljdGlvbnMuIA0KDQpJbiB0aGlzIGxlc3Nvbiwgd2Ugd2lsbCBkaXNjdXNzIGEgbWV0aG9kIG9mIG1lYXN1cmluZyB0aGUgYW1vdW50IG9mIHZhcmlhbmNlIHJlZHVjdGlvbiB3ZSBvYnRhaW4gaW4gdXNpbmcgYSByZWdyZXNzaW9uIG1vZGVsIHRvIGV4cGxhaW4gYSBwb3J0aW9uIG9mIHRoZSB2YXJpYXRpb24gaW4gJFkkIHRocm91Z2ggaXRzIHJlbGF0aW9uc2hpcCB3aXRoICRYJC4gDQoNCjxiciAvPg0KPGJyIC8+DQoNCg0KYGBge3IsIGVjaG89RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQoNCnNldC5zZWVkKDMpDQp4IDwtIHJ1bmlmKDIwLCA1LDEwKQ0KeSA8LSAxLjIgKyAwLjMgKiB4ICsgcm5vcm0oMjAsIDAsIDAuMSkNCnogPC0gMCAqIHggDQoNCiMgQ3JlYXRlIGZpcnN0IG1vZGVsDQpvbmVzIDwtIDAqMToyMCArIDENCm1vZDEgPC0gbG0oeSB+IG9uZXMpDQpwcmVkMSA8LSBwcmVkaWN0KG1vZDEsIG5ld2RhdGEgPSBkYXRhLmZyYW1lKG9uZXM9YygxKSksIGludGVydmFsPSdwcmVkaWN0aW9uJywgbGV2ZWw9MC45NSkNCg0KDQojIENyZWF0ZSBzZWNvbmQgbW9kZWwNCm1vZDIgPC0gbG0oeSB+IHgpDQpwcmVkMiA8LSBwcmVkaWN0KG1vZDIsIG5ld2RhdGEgPSBkYXRhLmZyYW1lKHg9Yyg2LjUpKSwgaW50ZXJ2YWw9J3ByZWRpY3Rpb24nLCBsZXZlbD0wLjk1KQ0KDQojeWhhdCA8LSBzdW0obW9kMSRjb2VmZmljaWVudHMgKiBjKDEsNi41KSkNCg0KIyBEaXNwbGF5IHBsb3RzDQpwYXIobWZyb3c9YygxLDIpKQ0KDQpwbG90KHkgfiB6LCB4YXh0PSduJywgeGxhYj0iIiwgeWxpbT1jKDIuNSw0LjUpLCBwY2g9MTksIGNvbD1yZ2IoMCwwLDEsMC44KSwgDQogICAgIG1haW49Ijk1JSBQcmVkaWN0aW9uIEludCBmb3IgWSAiKQ0KYWJsaW5lKGg9bWVhbih5KSwgbHR5PTIsIGNvbD0icmVkIikNCnNlZ21lbnRzKDAuMjUscHJlZDFbMl0sMC4yNSxwcmVkMVszXSwgbHdkPTQsIGNvbD0iRGFyayBPcmFuZ2UiKQ0KDQpwbG90KHkgfiB4LCB5bGltPWMoMi41LDQuNSksIHBjaD0xOSwgY29sPXJnYigwLDAsMSwwLjgpLA0KICAgICBtYWluPSI5NSUgUHJlZGljdGlvbiBJbnQgZm9yIFksIFxuIEdpdmVuIHRoYXQgWD02LjUiKQ0KYWJsaW5lKGg9cHJlZDJbMV0sIGx0eT0yLCBjb2w9InJlZCIpDQpzZWdtZW50cyg2LjUscHJlZDJbMl0sNi41LHByZWQyWzNdLCBsd2Q9NCwgY29sPSJEYXJrIE9yYW5nZSIpDQoNCg0KYGBgDQoNCg0KIyBTU1QsIFNTUiwgYW5kIFNTRQ0KDQpXZSB3aWxsIHVzZSBhIHF1YW50aXR5IGRlbm90ZWQgYnkgJHJeMiQgdG8gbWVhc3VyZSB0aGUgcHJvcG9ydGlvbiBvZiB0aGUgdmFyaWFuY2UgaW4gb3VyIHJlc3BvbnNlIHZhcmlhYmxlICRZJCB0aGF0IGlzIGV4cGxhaW5lZCBieSB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gJFkkIGFuZCBhIHByZWRpY3RvciAkWCQuIEJlZm9yZSB3ZSBkZWZpbmUgJHJeMiQsIHdlIGZpcnN0IG5lZWQgdG8gaW50cm9kdWNlIHNvbWUgcmVsYXRlZCBxdWFudGl0aWVzLiANCg0KRm9yIGEgcGFydGljdWxhciBvYnNlcnZhdGlvbiAkeV9pJCwgbm90aWNlIHRoYXQgdGhlIHF1YW50aXR5ICRkX2kgPSB5X2kgLSBcYmFyIHkkIG1lYXN1cmVzIHRoZSBhbW91bnQgYnkgd2hpY2ggdGhlIG9ic2VydmF0aW9uIGRldmlhdGVzIGZyb20gdGhlIHNhbXBsZSBtZWFuLiBXZSB3aWxsIGRlY29tcG9zZSB0aGlzIHF1YW50aXR5IGludG8gdHdvIHBpZWNlcy4gDQoNCiogTGV0ICRyX2kgPSBcaGF0IHlfaSAtIFxiYXIgeSQuIFRoZSBxdWFudGl0eSAkcl9pJCBpcyB0aGUgcG9ydGlvbiBvZiB0aGUgZGV2aWF0b24gJGRfaSQgdGhhdCBpcyBleHBsYWluZWQgYnkgdGhlIHJlZ3Jlc3Npb24gbW9kZWwuIFlvdSB3b3VsZCBleHBlY3QgdGhlICR5JCB2YWx1ZSB0byB2YXJ5IGZyb20gJFxiYXIgeSQgYnkgdGhpcyBhbW91bnQgYXMgYSByZXN1bHQgb2YgdGhlIGVmZmVjdCBvZiAkeCQuDQoNCiogTGV0ICRcaGF0IGVfaSA9IHlfaSAtIFxoYXQgeV9pJC4gVGhpcyBpcyB0aGUgcmVzaWR1YWwgYXNzb2NpYXRlZCB3aXRoICR5X2kkLiBJdCBjYW4gYmUgdGhvdWdodCBhcyB0aGUgcG9ydGlvbiBvZiB0aGUgb3ZlcmFsbCBkZXZpYXRpb24gJGRfaSQgdGhhdCBpcyBsZWZ0IHVuZXhwbGFpbmVkIGJ5IG91ciBtb2RlbC4gDQoNCk5vdGljZSB0aGF0ICRkX2kgPSByX2kgKyBcaGF0IGVfaSQuDQoNCmBgYHtyLCBlY2hvPUZBTFNFfQ0KeWhhdDggPC0gc3VtKG1vZDIkY29lZmZpY2llbnRzKmMoMSx4WzldKSkNCnBsb3QoeVs5XSB+IHhbOV0sIHhsaW09Yyg3LjUsOC40KSwgIHlsaW09YygzLjQsMy43NSksIHBjaD0xOSwgY2V4PTIsIGNvbD0iYmx1ZSIsIHhsYWI9IiIsIHlsYWI9IiIpDQoNCmFibGluZShtb2QyJGNvZWZmaWNpZW50cykNCmFibGluZShoPW1lYW4oeSksIGx0eT0yLCBjb2w9InJlZCIpDQoNCmQgPSAwLjENCnNlZ21lbnRzKHhbOV0gLSBkLG1lYW4oeSkseFs5XSAtIGQseVs5XSwgbHdkPTMsIGNvbD0iZGVlcHNreWJsdWUzIikNCnNlZ21lbnRzKHhbOV0gLSBkLHlbOV0seFs5XSx5WzldLCBsdHk9MiwgbHdkPTIsIGNvbD0iZGVlcHNreWJsdWUzIikNCg0Kc2VnbWVudHMoeFs5XSArIGQsbWVhbih5KSx4WzldICsgZCx5aGF0OCwgbHdkPTMsIGNvbD0iRGFyayBPcmFuZ2UiKQ0Kc2VnbWVudHMoeFs5XSArIGQseWhhdDgseFs5XSArIGQseVs5XSwgbHdkPTMsIGNvbD0iR3JlZW40IikNCg0Kc2VnbWVudHMoeFs5XSx5aGF0OCx4WzldICsgZCx5aGF0OCwgbHR5PTIsIGx3ZD0yLCBjb2w9IkRhcmsgT3JhbmdlIikNCnNlZ21lbnRzKHhbOV0seVs5XSx4WzldICsgZCx5WzldLCBsdHk9MiwgbHdkPTIsIGNvbD0iR3JlZW40IikNCg0KdGV4dCg3LjY5LDMuNjMsIGV4cHJlc3Npb24oZFtpXSA9PSB5W2ldIC0gYmFyKHkpKSwgY2V4PTEuNSwgY29sPSJkZWVwc2t5Ymx1ZTMiKSANCnRleHQoOC4wOCwzLjY1LCBleHByZXNzaW9uKHlbaV0gLSBoYXQoeSlbaV0gPT0gaGF0KGUpW2ldKSwgY2V4PTEuNSwgY29sPSJHcmVlbjQiKSANCnRleHQoOC4wOCwzLjUsIGV4cHJlc3Npb24oaGF0KHkpW2ldIC0gYmFyKHkpID09IHJbaV0pLCBjZXg9MS41LCBjb2w9IkRhcmsgT3JhbmdlIikgDQoNCnBvaW50cyh4WzldLHlbOV0sIHBjaD0xOSwgY2V4PTIsIGNvbD0iYmx1ZSIpDQpwb2ludHMoeFs5XSx5aGF0OCwgcGNoPTE5LCBjZXg9MikNCmBgYA0KDQpXZSBub3cgc3VtIHRoZSBzcXVhcmVzIG9mIGVhY2ggb2YgdGhlc2UgdGhyZWUgcXVhbnRpdGllcyBvdmVyIGFsbCBvZiB0aGUgcG9pbnRzIGluIG91ciBzYW1wbGUuDQoNCiogTGV0ICRTU1QgPSBcc3VtIGRfaV4yICA9IFxzdW0gKHlfaSAtIFxiYXIgeSleMiQNCg0KKiBMZXQgJFNTUiA9IFxzdW0gcl9pXjIgID0gXHN1bSAoIFxoYXQgeV9pIC0gXGJhciB5KV4yJA0KDQoqIExldCAkU1NFID0gXHN1bSBcaGF0IGVfaV4yICA9IFxzdW0gKCB5X2kgLSBcaGF0IHlfaSleMiQNCg0KDQojIFNTVCA9IFNTRSArIFNTUg0KDQpBbiBpbXBvcnRhbnQgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlc2UgdGhyZWUgc3VtcyBpcyBnaXZlbiBieSB0aGUgZXF1YXRpb24gJFNTVCA9IFNTRSArIFNTUiQuIA0KDQpUbyBlc3RhYmxpc2ggdGhpcyByZXN1bHQsIHdlIHdpbGwgbmVlZCB0byBtYWtlIHVzZSBvZiB0aGUgZm9sbG93aW5nIHR3byBpZGVudGl0aWVzOg0KDQoqICRcc3VtIFxoYXQgZV9pID0gMCQNCg0KKiAkXHN1bSBcaGF0IGVfaSBcaGF0IHlfaSA9IDAkDQoNClRoZSBmaXJzdCBpZGVudGl0eSBpcyBvbmUgb2Ygb3VyIHR3byBub3JtYWwgZXF1YXRpb25zLiBUaGUgc2Vjb25kIGlkZW50aXR5IGNhbiBiZSBkZXJpdmVkIGZyb20gdGhlIHR3byBub3JtYWwgZXF1YXRpb25zLiBBcm1lZCB3aXRoIHRoZXNlIGlkZW50aXRpZXMsIHdlIG1heSBwcm9jZWRlIHdpdGggb3VyIHByb29mIHRoYXQgJFNTVCA9IFNTRSArIFNTUiQgYXMgZm9sbG93czoNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSAoeV9pIC0gXGJhcnt5fSleMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSBbKFxoYXQgZV9pICsgXGhhdCB5X2kpIC0gXGJhcnt5fV1eMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSBbXGhhdCBlX2kgKyAoXGhhdCB5X2kgLSBcYmFye3l9KV1eMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSBbXGhhdCBlX2leMiArIDJcaGF0IGVfaSAoXGhhdCB5X2kgLSBcYmFye3l9KSArICggXGhhdCB5X2kgLSBcYmFyIHkpXjJdJA0KDQokXGhzcGFjZXszMHB0fSBTU1QgPSBcc3VtIFxoYXQgZV9pXjIgKyAyXHN1bSBcaGF0IGVfaSAoXGhhdCB5X2kgLSBcYmFye3l9KSArIFxzdW0gKCBcaGF0IHlfaSAtIFxiYXIgeSleMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gU1NFICsgMiBcc3VtKCBcaGF0IGVfaSBcaGF0IHlfaSAtICBcaGF0IGVfaVxiYXJ7eX0pICsgU1NSJA0KDQokXGhzcGFjZXszMHB0fSBTU1QgPSBTU0UgKyAyIFxzdW0gXGhhdCBlX2kgXGhhdCB5X2kgLSAgMiBcYmFye3l9XHN1bVxoYXQgZV9pICsgU1NSJA0KDQokXGhzcGFjZXszMHB0fSBTU1QgPSBTU0UgKyAwIC0gMCArIFNTUiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gU1NFICsgU1NSJA0KDQoNCiMgci1TcXVhcmVkDQoNCkludHVpdGl2ZSBleHBsYW5hdGlvbnMgb2YgdGhlIG1lYW5pbmcgb2YgdGhlIHZhcmlhYmxlcyAkU1NUJCwgJFNTUiQsIGFuZCAkU1NFJCBhcmUgYXMgZm9sbG93czoNCg0KKiAkU1NUJCBpcyBhIG1lYXN1cmUgb2YgdGhlIGFtb3VudCBvZiB2YXJpYXRpb24gaW4gdGhlIHJlc3BvbnNlIHZhcmlhYmxlICRZJC4gDQoNCiogJFNTUiQgaXMgYSBtZWFzdXJlIG9mIHRoZSB2YXJpYXRpb24gaW4gJFkkIHRoYXQgaXMgZXhwbGFpbmVkIGJ5IHRoZSByZWdyZXNzaW9uIG1vZGVsLiANCg0KKiAkU1NFJCBpcyBhIG1lYXN1cmUgb2YgdGhlIHZhcmlhdGlvbiBpbiAkWSQgdGhhdCBpcyBsZWZ0IHVuZXhwbGFpbmVkIGJ5IG91ciBtb2RlbC4gDQoNCklkZWFsbHksIHdlIHdvdWxkIGxpa2UgZm9yICRTU0UkIHRvIGJlIGNsb3NlIHRvIDAgYW5kIGZvciAkU1NSJCB0byB0aHVzIGJlIGNsb3NlIHRvICRTU1QkLiBXZSBjYW4gbWVhc3VyZSB0aGUgcHJvcG9ydGlvbiBvZiB0aGUgdmFyaWFuY2UgaW4gJFkkIHRoYXQgaXMgZXhwbGFpbmVkIGJ5IG91ciByZWdyZXNzaW9uIG1vZGVsIHVzaW5nIHRoZSBmb2xsb3dpbmcgcXVhbnRpdHk6DQoNCiQkcl4yID0gXGZyYWN7U1NSfXtTU1R9JCQgDQoNCk5vdGUgdGhhdCBzaW5jZSAkMCBcbGVxIFNTUiBcbGVxIFNTVCQsIHdlIGdldCB0aGF0ICQwIFxsZXEgcl4yIFxsZXEgMSQuIFRoZSBxdWFudGl0eSAkcl4yJCBpcyBhIGRpYWdub3N0aWMgdG9vbCB0aGF0IGlzIGNvbW1vbmx5IHVzZXMgdG8gbWVhc3VyZSB0aGUgcXVhbGl0eSBvZiB0aGUgZml0IGluIGEgcmVncmVzc2lvbiBtb2RlbC4gDQoNCk5vdGljZSB0aGF0IHNpbmNlICRTU1QgPSBTU1IgKyBTU0UkLCB3ZSBjYW4gcmV3cml0ZSB0aGUgZm9ybXVsYSBmb3IgJHJeMiQgYXMgZm9sbG93czoNCg0KDQokJHJeMiA9IFxmcmFje1NTUn17U1NUfSA9IDEgLSBcZnJhY3tTU0V9e1NTUn0kJCANCg0KVGhlICRyXjIgPSAxIC0gXGZyYWN7U1NFfXtTU1J9JCBmb3JtdWxhIGZvciAkcl4yJCBpcyBvZnRlbiB0aGUgbW9yZSB1c2VmdWwgb2YgdGhlIHR3byBmb3JtdWxhcywgc2luY2Ugd2Ugd2lsbCBoYXZlIG90aGVyIHJlYXNvbnMgZm9yIGNhbGN1bGF0aW5nICRTU0UkLiANCg0KDQojIFJlc2lkdWFsIFN0YW5kYXJkIEVycm9yDQoNCkNvbnNpZGVyIHRoZSBoeXBvdGhldGljYWwgbW9kZWwgJFkgPSBcYmV0YV8wICsgXGJldGFfMSBYICsgZSQuIElmIHdlIGtub3cgdGhlIHZhbHVlIG9mIHRoZSB2YXJpYWJsZSAkWCQsIHRoZW4gdGhlIG9ubHkgdW5jZXJ0YWludHkgaW4gdGhlIHZhbHVlIG9mICRZJCBpcyBkdWUgdG8gdGhlIGVycm9yIHRlcm0gJGUkLiBXZSBvZnRlbiBhc3N1bWUgdGhhdCAkRVtlXT0wJC4gSW4gdGhhdCBjYXNlLCAkVmFyW2VdID0gXHNpZ21hX2VeMiQgcHJvdmlkZXMgYSBtZWFzdXJlbWVudCBvZiB0aGUgYW1vdW50IG9mIGVycm9yIGluaGVyZW50IGluIG91ciBtb2RlbC4gDQoNClNpbmNlIHdlIGRvIG5vdCBnZW5lcmFsbHkgaGF2ZSBhY2Nlc3MgdG8gdGhlIGh5cG90aGV0aWNhbCBtb2RlbCwgd2UgY2Fubm90IGNhbHVsY2F0ZSB2YWx1ZXMgb2YgJGUkIGV4YWN0bHkuIEhvd2V2ZXIsIHdlIGNhbiBjb25zdHJ1Y3QgYSBmaXR0ZWQgbW9kZWwsICRZID0gXGhhdFxiZXRhXzAgKyBcaGF0XGJldGFfMSBYICsgXGhhdCBlJCBhbmQgdGhlbiB1c2UgJFxoYXQgZSQgYXMgYW4gYXBwcm94aW1hdGlvbiBvZiAkZSQuIEFzIHN1Y2gsIHdlIHNob3VsZCBiZSBhYmxlIHRvIHVzZSB0aGUgb2JzZXJ2ZWQgcmVzaWR1YWxzICRcaGF0IGVfaSQgdG8gZmluZCBhbiAgYXBwcm94aW1hdGlvbiBvZiAkXHNpZ21hX2VeMiQuIA0KDQpJdCBjYW4gYmUgc2hvd24gdGhhdCB0aGUgZm9sbG93aW5nIGV4cHJlc3Npb24gcHJvdmlkZXMgYW4gdW5iaWFzZWQgZXN0aW1hdGUgb2YgJFxzaWdtYV9lXjIkOg0KDQokJHNeMiA9IFxmcmFje1NTRX17bi0yfSA9IFxmcmFjezF9e24tMn0gXHN1bV97aT0xfV5uIFxoYXQgZV9pXjIkJA0KVGhlIHNxdWFyZSByb290IG9mIHRoaXMgcXVhbnRpdHkgaXMgY2FsbGVkIHRoZSAqKnJlc2lkdWFsIHN0YW5kYXJkIGVycm9yKiogKFJTRSkuIEl0IGFwcHJveGltYXRlcyB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIHRoZSBlcnJvciB0ZXJtICRlJC4gDQoNCiQkcyA9IFxzcXJ0e1xmcmFje1NTRX17bi0yfX0gPSBcc3FydHtcZnJhY3sxfXtuLTJ9IFxzdW1fe2k9MX1ebiBcaGF0IGVfaV4yfSQkDQoNCiMgVXNpbmcgUiB0byBDYWxjdWxhdGUgci1TcXVhcmVkIGFuZCBSU0UNCg0KTGV0J3MgcmV0dXJuIHRvIHRoZSBQZWFyc29uIGRhdGEgc2V0LiBJbiB0aGUgY29kZSBjaHVuayBiZWxvdywgd2UgbG9hZCB0aGUgZGF0YSwgY3JlYXRlIGFuIE9MUyByZWdyZXNzaW9uIG1vZGVsLCBhbmQgdGhlbiBwcmludCBhIHN1bW1hcnkgb2YgdGhhdCBtb2RlbC4gDQoNCmBgYHtyfQ0KbXlEYXRhIDwtIHJlYWQudGFibGUoImZhdGhlcl9zb24udHh0Iiwgc2VwPSJcdCIsIGhlYWRlcj1UUlVFKQ0KbW9kIDwtIGxtKHNoZWlnaHQgfiBmaGVpZ2h0LCBteURhdGEpDQpzdW1tYXJ5KG1vZCkNCmBgYA0KDQpXZSBjYW4gc2VlIGZyb20gdGhlIHN1bW1hcnkgdGhhdDoNCg0KKiAkcl4yID0gMC4yNTEzJA0KDQoqICRzID0gMi40MzckDQoNCiMgci1TcXVhcmVkIGFuZCBDb3JyZWxhdGlvbg0KDQpUaGUgdmFsdWUgJHJeMiQgaXMgcmVsYXRlZCB0byB0aGUgc2FtcGxlIGNvcnJlbGF0aW9uICRccmhvX3tYLFl9ID0gXG1hdGhybXtjb3JyfVtYLFldJC4gSW4gZmFjdCwgaXQgY2FuIGJlIHNob3duIHRoYXQ6DQoNCiQkcl4yID0gXG1hdGhybXtjb3JyfVtYLFldJCQNCg0KVG8gZXN0YWJsaXNoIHRoaXMgcmVzdWx0LCB3ZSBmaXJzdCBuZWVkIHRvIGRlcml2ZSBhbiBhbHRlcm5hdGUgZm9ybSBmb3IgdGhlIGV4cHJlc3Npb24gJFNTUiQuIE5vdGljZSB0aGF0Og0KDQokXGhzcGFjZXszMHB0fSBTU1IgPSBcc3VtXGxpbWl0c197aT0xfV5uIChcaGF0IHlfaSAtIFxiYXIgeSleMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NSID0gXHN1bVxsaW1pdHNfe2k9MX1ebiBcbGVmdFtcbGVmdChcaGF0IFxiZXRhXzAgKyBcaGF0IFxiZXRhXzEgeF9pIFxyaWdodCkgLSBcYmFyIHlccmlnaHRdXjIkDQoNCiRcaHNwYWNlezMwcHR9IFNTUiA9IFxzdW1cbGltaXRzX3tpPTF9Xm4gXGxlZnRbXGxlZnQoXGJhciB5IC0gXGhhdFxiZXRhXzFcYmFyIHggXHJpZ2h0KSArIFxoYXQgXGJldGFfMSB4X2kgIC0gXGJhciB5XHJpZ2h0XV4yJA0KDQokXGhzcGFjZXszMHB0fSBTU1IgPSBcc3VtXGxpbWl0c197aT0xfV5uIFxsZWZ0KCAtIFxoYXRcYmV0YV8xXGJhciB4ICArIFxoYXQgXGJldGFfMSB4X2lccmlnaHQpXjIkDQoNCiRcaHNwYWNlezMwcHR9IFNTUiA9IFxiZXRhXzFeMiBcc3VtXGxpbWl0c197aT0xfV5uIFxsZWZ0KCB4X2kgLSBcYmFyIHhccmlnaHQpXjIkDQoNCiRcaHNwYWNlezMwcHR9IFNTUiA9IFxiZXRhXzFeMiBTWFgkDQoNCiRcaHNwYWNlezMwcHR9IFNTUiA9IFxsZWZ0KFxmcmFje1NYWX17U1hYfSBccmlnaHQpXjIgU1hYJA0KDQokXGhzcGFjZXszMHB0fSBTU1IgPSBcZnJhY3tcbGVmdChTWFkgXHJpZ2h0KV4yfXtTWFh9JA0KDQoNCk5vdywgcmVjYWxsIHRoYXQgJHJeMiA9IFxmcmFje1NTUn17U1NUfSQuIFdlIHdpbGwgc3Vic3RpdHV0ZSB0aGUgZXhwcmVzc2lvbiBhYm92ZSBpbiBmb3IgJFNTUiQsIGFuZCB0aGVuIHNpbXBsaWZ5LiANCg0KJFxoc3BhY2V7MzBwdH0gcl4yID0gXGZyYWN7U1NSfXtTU1R9JA0KDQokXGhzcGFjZXszMHB0fSByXjIgPSBcZnJhY3tcbGVmdChTWFkgXHJpZ2h0KV4yfXtTWFh9IFxmcmFjezF9e1NTVH0kDQoNCiRcaHNwYWNlezMwcHR9IHJeMiA9IFxmcmFje1xsZWZ0KFNYWSBccmlnaHQpXjJ9e1NYWCBcY2RvdCBTU1R9JA0KDQokXGhzcGFjZXszMHB0fSByXjIgPSBcZnJhY3tcbGVmdChTWFkgXHJpZ2h0KV4yfXtTWFggXGNkb3QgU1NUfSQNCg0KJFxoc3BhY2V7MzBwdH0gcl4yID0gXGZyYWN7XGxlZnQoXHN1bVxsaW1pdHNfe2k9MX1ebiAoeF9pIC0gXGJhciB4KSh5X2kgLSBcYmFyIHkpIFxyaWdodCleMn17XHN1bVxsaW1pdHNfe2k9MX1ebiAoeF9pIC0gXGJhciB4KV4yIFxjZG90IFxzdW1cbGltaXRzX3tpPTF9Xm4gKHlfaSAtIFxiYXIgeSleMn0kDQoNCiRcaHNwYWNlezMwcHR9IHJeMiA9IFxsZWZ0KFxmcmFje1xzdW1cbGltaXRzX3tpPTF9Xm4gKHhfaSAtIFxiYXIgeCkoeV9pIC0gXGJhciB5KSB9e1xzcXJ0e1xzdW1cbGltaXRzX3tpPTF9Xm4gKHhfaSAtIFxiYXIgeCleMn0gXGNkb3QgXHNxcnR7XHN1bVxsaW1pdHNfe2k9MX1ebiAoeV9pIC0gXGJhciB5KV4yfX0gXHJpZ2h0KV4yJA0KDQokXGhzcGFjZXszMHB0fSByXjIgPSBcbGVmdCggXGZyYWN7XG1hdGhybXtjb3Z9W1gsWV19e3NfWCBzX1l9ICBccmlnaHQpXjIkDQoNCiRcaHNwYWNlezMwcHR9IHJeMiA9IFxsZWZ0KCBcbWF0aHJte2NvcnJ9W1gsWV0gIFxyaWdodCleMiQNCg0KVGhpcyBjb21wbGV0ZXMgb3VyIHByb29mLiANCg0KIyBDb3JyZWxhdGlvbiBCZXR3ZWVuICRZJCBhbmQgJFxoYXQgWSQNCg0KSXQgY2FuIGFsc28gYmUgc2hvd24gdGhhdCB0aGUgY29ycmVsYXRpb24gYmV0d2VlbiB0aGUgZml0dGVkIHZhbHVlICRcaGF0IFkkIGFuZCB0aGUgcmVzcG9uc2UgJFkkIGlzIGV4YWN0bHkgdGhlIHNhbWUgYXMgdGhhdCBiZXR3ZWVuIHRoZSBwcmVkaWN0b3IgJFgkIGFuZCB0aGUgcmVzcG9uc2UgJFkkLiBJbiBvdGhlciB3b3JkczoNCg0KJCRcbWF0aHJte2NvcnJ9XGxlZnRbXGhhdCBZLFkgXHJpZ2h0XSA9IFxtYXRocm17Y29ycn1cbGVmdFtYLFlccmlnaHRdJCQNCg0KVGhlIHByb29mIG9mIHRoaXMgZmFjdCBpcyBsZWZ0IGFzIGFuIGV4ZXJjaXNlLiANCg0KDQoNCg0KDQoNCg0KDQo=