library(tidyverse)      # for plotting and summarizing
library(moderndive)     # for nice model output
library(broom)          # for nice model output 
library(patchwork)      # for nicely organizing plots
library(openintro)      # for data
theme_set(theme_minimal()) # changes the theme of ggplots to theme_minimal, my personal favorite

GOAL:

By the end of these notes and activities, you should be able to perform the following tasks.

  • Have a high-level understanding of how linear model coefficients are estimated.
  • Use \(R^2\) to describe how well your response variable can be explained by the model.
  • Use \(\hat{\sigma}\) (also called \(s_e\) or residual standard error) to estimate how variable the predictions may be.

Model Fitting

Up until now, we have mostly been concerned with interpreting coefficients from linear models, but where do they come from?

The “best” coefficients are those that minimize the sum of the squared residuals. This is referred to as the least squares criterion. If you like mathematical equations, it can be written mathematically, as:

\[ \text{min}_{\bf{\beta}} \sum_{i=1}^n[y_i - (\beta_0 + \beta_1 x_{i1} + ... + \beta_p x_{ip})]^2 \]

In words, this means, find the \(\beta_0, \beta_1, ... , \beta_p\) that make the smallest sum of squared residuals. Calculus and linear algebra can be used to solve the minimization problem explicitly. We will not go through that in this class, but I encourage you to take Linear Algebra and Computational Linear Algebra if learning those details is of interest to you.

Instead let’s look at this in a picture. The graph on the left is the least squares solution. The one on the right is just another line I made up.

Below I compute the squared residuals (in the table) and the sum of the squared residuals (the result of the summarize()) for the best fit line (I have rounded the coefficients so this is not exact).

stats_best <- mpg %>% 
  mutate(fitted = 35.70 - 3.53*displ,
         resid = hwy - fitted,
         resid_squared = resid^2)

stats_best
stats_best %>% 
  summarize(rss_best = sum(resid_squared))

YOUR TURN!

  1. In the two graphs above, what do you notice about the size of the residuals, in general?

  2. How could we represent the squared residuals on the graph?

  3. Modify the code above to compute the sum of the squared residuals for the model from the graph on the right. How does that compare to the sum of the squared residuals from the least squares line?

  4. In the code below, try modifying the my_y_int and my_slope values, which are your intercept and slope for the line. When you run the code, the residual sum of squares (RSS) will be shown in the title. Play around with this for awhile. Are there any other lines you can fit that are very unlike the best fit line but still have small RSS?

my_y_int = 50 #put your y-intercept here
my_slope = -5 #put your slope here

rss <- mpg %>% 
  summarize(rss = sum((hwy - (my_y_int + my_slope*displ))^2)) %>% 
  pull(rss)

mpg %>% 
  ggplot(aes(x = displ, y = hwy)) +
  geom_abline(slope = my_slope, intercept = my_y_int, color = "blue", size = .5) +
  geom_segment(aes(xend = displ, 
                   yend = my_y_int + my_slope*displ), 
               color = "darkred") +
  geom_point(aes(x = displ, y = my_y_int + my_slope*displ), color = "blue") +
  geom_point() + 
  labs(title = bquote(RSS == .(rss)))

Let’s also take a little bit of time exploring this website.

Evaluation

  • Is our model accurate?
  • Does it predict new observations well?

Variance explained in response: \(R^2\)

Recall that one of our goals in building a model is to better explain the variation in our response variable, \(y\).

Let’s take a look at the mpg data again. First, let’s just look at a distribution of highway mpg, hwy.

ggplot(mpg) +
  geom_histogram(aes(x = hwy), bins = 30) +
  geom_vline(aes(xintercept = mean(hwy)), color = "darkred") +
  theme_minimal()

The standard deviation of hwy is 5.9546434 and the variance is 35.4577785. These are ways we’ve talked about measuring variation. We could also use the sum of the squared deviations from the mean, SST (total sum of squares):

mpg %>% 
  summarize(sst = sum((hwy - mean(hwy))^2))

Why do we like this measure?! It is going to give us a good way to compare to our fitted values after fitting a model.

Now, let’s fit the simple model that uses engine displacement, displ, to explain hwy.

lm_displ <- lm(hwy ~ displ,
               data=mpg)
tidy(lm_displ)

We can compare the variation in hwy after accounting for displ to the variation of hwy accounting for no variables. These are shown in the plots below.

We would like to know if there is less variation in hwy after using displ to help explain hwy. Or, once I know displ, can I predict hwy better? We can evaluate this by the sum of the squared residuals, RSS (yes, this is the same quantity that gets minimized when we find the “best” coefficient).

augment(lm_displ, data=mpg) %>% 
  summarize(rss = sum(.resid^2))

How does this compare to SST?

We define \(R^2\) as

\[ R^2 = 1 - \frac{RSS}{SST} = 1 - \frac{\sum(y_i - \hat{y}_i)^2}{\sum(y_i - \bar{y})^2}. \] It is the fraction of variation in \(y\) accounted for or explained by the model.

YOUR TURN!

  1. How small can \(R^2\) be? When will \(R^2\) be small?
  2. How large can \(R^2\) be? When will \(R^2\) be large?
  3. What are the units of \(R^2\)?

We can use the get_regression_summaries or glance to find the \(R^2\) value. It is called r_squared or r.squared, respectively.

get_regression_summaries(lm_displ)
glance(lm_displ)

\(R^2\) can be used to compare models with the same response variable and the same number of explanatory variables.

For example, let’s fit another model that uses city mpg, cty, to predict hwy. How does this model compare to the one with only displ?

mpg %>% 
  ggplot(aes(x = cty, y = hwy)) +
  geom_jitter() +
  theme_minimal()

lm_cty <- lm(hwy ~ cty, 
              data=mpg)
tidy(lm_cty)
glance(lm_cty)

IMPORTANT NOTE: We CANNOT use \(R^2\) to compare models with different numbers of explanatory variables. I will not go into details, but here is an example of adding five variable of “noise” to the model, that is 5 variables that are just a bunch of random numbers. What happens to the \(R^2\) value? Adding a new variable, even one that is complete nonsense will never decrease the \(R^2\) value.

set.seed(10) #makes results reproducible
lm_displ_noise <- lm(hwy ~ displ + 
                       rnorm(n = nrow(mpg)) +
                       rnorm(n = nrow(mpg)) +
                       rnorm(n = nrow(mpg)) +
                       rnorm(n = nrow(mpg)) +
                       rnorm(n = nrow(mpg)),
                     data=mpg)
glance(lm_displ_noise) %>% 
  select(r.squared)
glance(lm_displ) %>% 
  select(r.squared)

We can use the adjusted \(R^2\) to compare models with different numbers of variables. This can also be found in the output from glance or get_regression_summaries. Read more about adjusted \(R^2\) here.

Standard error of regression: \(\hat{\sigma}\)

The standard error of the regression, \(\hat{\sigma}\), is defined as

\[ \hat{\sigma} = \sqrt{\frac{\sum_{i=1}^n (y_i - \hat{y}_i)^2}{n-p}}. \]

This can be found in the glance output, called sigma. It is another statistic that describes how well the model fits, telling us approximately how far the predictions are from their actual values, on average.

YOUR TURN!

Use the hsb2 dataset from the openintro library to answer the following questions.

  1. First, look at a distribution of math. Compute the SST.

  2. Compute the \(R^2\) for the model that uses only ses to explain math. Describe what this means in the context of the data.

  3. Find \(\hat{\sigma}\) for this model. Interpret it in the context of the data.

  4. Compute the \(R^2\) for the model that uses only prog. So, does prog or ses explain more of the variation in math?

  5. Fit a model with both ses and prog. Use the adjusted \(R^2\) to decide if adding a second variable to the model seems useful.

  6. Now try adding an interaction effect. Use the adjusted \(R^2\) to decided if adding that is useful. Compare the plots you created in your most recent homework assignment of the fitted models with and without an interaction effect to help illustrate why you are seeing these results.

LS0tCnRpdGxlOiAiTW9kZWwgRml0dGluZyBhbmQgRXZhbHVhdGlvbiIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCi0tLQoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKSAgICAgICMgZm9yIHBsb3R0aW5nIGFuZCBzdW1tYXJpemluZwpsaWJyYXJ5KG1vZGVybmRpdmUpICAgICAjIGZvciBuaWNlIG1vZGVsIG91dHB1dApsaWJyYXJ5KGJyb29tKSAgICAgICAgICAjIGZvciBuaWNlIG1vZGVsIG91dHB1dCAKbGlicmFyeShwYXRjaHdvcmspICAgICAgIyBmb3IgbmljZWx5IG9yZ2FuaXppbmcgcGxvdHMKbGlicmFyeShvcGVuaW50cm8pICAgICAgIyBmb3IgZGF0YQp0aGVtZV9zZXQodGhlbWVfbWluaW1hbCgpKSAjIGNoYW5nZXMgdGhlIHRoZW1lIG9mIGdncGxvdHMgdG8gdGhlbWVfbWluaW1hbCwgbXkgcGVyc29uYWwgZmF2b3JpdGUKYGBgCgo8ZGl2IGNsYXNzPSJhbGVydCBhbGVydC1zdWNjZXNzIj4KICA8c3Ryb25nPkdPQUw6PC9zdHJvbmc+CgpCeSB0aGUgZW5kIG9mIHRoZXNlIG5vdGVzIGFuZCBhY3Rpdml0aWVzLCB5b3Ugc2hvdWxkIGJlIGFibGUgdG8gcGVyZm9ybSB0aGUgZm9sbG93aW5nIHRhc2tzLgoKKiBIYXZlIGEgaGlnaC1sZXZlbCB1bmRlcnN0YW5kaW5nIG9mIGhvdyBsaW5lYXIgbW9kZWwgY29lZmZpY2llbnRzIGFyZSBlc3RpbWF0ZWQuICAKKiBVc2UgJFJeMiQgdG8gZGVzY3JpYmUgaG93IHdlbGwgeW91ciByZXNwb25zZSB2YXJpYWJsZSBjYW4gYmUgZXhwbGFpbmVkIGJ5IHRoZSBtb2RlbC4gIAoqIFVzZSAkXGhhdHtcc2lnbWF9JCAoYWxzbyBjYWxsZWQgJHNfZSQgb3IgcmVzaWR1YWwgc3RhbmRhcmQgZXJyb3IpIHRvIGVzdGltYXRlIGhvdyB2YXJpYWJsZSB0aGUgcHJlZGljdGlvbnMgbWF5IGJlLiAKCjwvZGl2PgoKIyBNb2RlbCBGaXR0aW5nCgpVcCB1bnRpbCBub3csIHdlIGhhdmUgbW9zdGx5IGJlZW4gY29uY2VybmVkIHdpdGggaW50ZXJwcmV0aW5nIGNvZWZmaWNpZW50cyBmcm9tIGxpbmVhciBtb2RlbHMsIGJ1dCB3aGVyZSBkbyB0aGV5IGNvbWUgZnJvbT8KClRoZSAiYmVzdCIgY29lZmZpY2llbnRzIGFyZSB0aG9zZSB0aGF0IG1pbmltaXplIHRoZSBzdW0gb2YgdGhlIHNxdWFyZWQgcmVzaWR1YWxzLiBUaGlzIGlzIHJlZmVycmVkIHRvIGFzIHRoZSBsZWFzdCBzcXVhcmVzIGNyaXRlcmlvbi4gSWYgeW91IGxpa2UgbWF0aGVtYXRpY2FsIGVxdWF0aW9ucywgaXQgY2FuIGJlIHdyaXR0ZW4gbWF0aGVtYXRpY2FsbHksIGFzOgoKJCQKXHRleHR7bWlufV97XGJme1xiZXRhfX0gXHN1bV97aT0xfV5uW3lfaSAtIChcYmV0YV8wICsgXGJldGFfMSB4X3tpMX0gKyAuLi4gKyBcYmV0YV9wIHhfe2lwfSldXjIKJCQKCkluIHdvcmRzLCB0aGlzIG1lYW5zLCBmaW5kIHRoZSAkXGJldGFfMCwgXGJldGFfMSwgLi4uICwgXGJldGFfcCQgdGhhdCBtYWtlIHRoZSBzbWFsbGVzdCBzdW0gb2Ygc3F1YXJlZCByZXNpZHVhbHMuIENhbGN1bHVzIGFuZCBsaW5lYXIgYWxnZWJyYSBjYW4gYmUgdXNlZCB0byBzb2x2ZSB0aGUgbWluaW1pemF0aW9uIHByb2JsZW0gZXhwbGljaXRseS4gV2Ugd2lsbCBub3QgZ28gdGhyb3VnaCB0aGF0IGluIHRoaXMgY2xhc3MsIGJ1dCBJIGVuY291cmFnZSB5b3UgdG8gdGFrZSBMaW5lYXIgQWxnZWJyYSBhbmQgQ29tcHV0YXRpb25hbCBMaW5lYXIgQWxnZWJyYSBpZiBsZWFybmluZyB0aG9zZSBkZXRhaWxzIGlzIG9mIGludGVyZXN0IHRvIHlvdS4gCgpJbnN0ZWFkIGxldCdzIGxvb2sgYXQgdGhpcyBpbiBhIHBpY3R1cmUuIFRoZSBncmFwaCBvbiB0aGUgbGVmdCBpcyB0aGUgbGVhc3Qgc3F1YXJlcyBzb2x1dGlvbi4gVGhlIG9uZSBvbiB0aGUgcmlnaHQgaXMganVzdCBhbm90aGVyIGxpbmUgSSBtYWRlIHVwLiAKCmBgYHtyLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD00LCBlY2hvPUZBTFNFfQpsbV9kaXNwbCA8LSBsbShod3kgfiBkaXNwbCwKICAgICAgICAgICAgICAgZGF0YT1tcGcpCgpwMSA8LSBhdWdtZW50KGxtX2Rpc3BsLCBkYXRhID0gbXBnKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gZGlzcGwsIHkgPSBod3kpKSArCiAgZ2VvbV9saW5lKGFlcyh4ID0gZGlzcGwsIHkgPSAuZml0dGVkKSwgY29sb3IgPSAiYmx1ZSIsIHNpemUgPSAuNSkgKwogIGdlb21fc2VnbWVudChhZXMoeGVuZCA9IGRpc3BsLCAKICAgICAgICAgICAgICAgICAgIHllbmQgPSAzNS43MCAtIDMuNTMqZGlzcGwpLCAKICAgICAgICAgICAgICAgY29sb3IgPSAiZGFya3JlZCIpICsKICBnZW9tX3BvaW50KGFlcyh4ID0gZGlzcGwsIHkgPSAuZml0dGVkKSwgY29sb3IgPSAiYmx1ZSIpICsKICBnZW9tX3BvaW50KCkgKwogIHNjYWxlX3hfY29udGludW91cyhicmVha3MgPSAxOjgpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoYnJlYWtzID0gc2VxKDEwLDYwLDEwKSkgKwogIGxhYnModGl0bGUgPSAiQmVzdCBtb2RlbCIsIHN1YnRpdGxlID0gIkFjdHVhbCAoYmxhY2spLCBGaXR0ZWQgKGJsdWUpLCBhbmQgcmVzaWR1YWxzIChyZWQpIikKCnAyIDwtIG1wZyAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gZGlzcGwsIHkgPSBod3kpKSArCiAgZ2VvbV9hYmxpbmUoc2xvcGUgPSAuNSwgaW50ZXJjZXB0ID0gMTUsIGNvbG9yID0gImJsdWUiLCBzaXplID0gLjUpICsKICBnZW9tX3NlZ21lbnQoYWVzKHhlbmQgPSBkaXNwbCwgCiAgICAgICAgICAgICAgICAgICB5ZW5kID0gMTUgKyAuNSpkaXNwbCksIAogICAgICAgICAgICAgICBjb2xvciA9ICJkYXJrcmVkIikgKwogIGdlb21fcG9pbnQoYWVzKHggPSBkaXNwbCwgeSA9IDE1ICsgLjUqZGlzcGwpLCBjb2xvciA9ICJibHVlIikgKwogIGdlb21fcG9pbnQoKSArIAogIHNjYWxlX3hfY29udGludW91cyhicmVha3MgPSAxOjgpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoYnJlYWtzID0gc2VxKDEwLDYwLDEwKSkgKwogIGxhYnModGl0bGUgPSAiQW5vdGhlciBtb2RlbCIpCgpwMSArIHAyCmBgYAoKQmVsb3cgSSBjb21wdXRlIHRoZSBzcXVhcmVkIHJlc2lkdWFscyAoaW4gdGhlIHRhYmxlKSBhbmQgdGhlIHN1bSBvZiB0aGUgc3F1YXJlZCByZXNpZHVhbHMgKHRoZSByZXN1bHQgb2YgdGhlIGBzdW1tYXJpemUoKWApIGZvciB0aGUgYmVzdCBmaXQgbGluZSAoSSBoYXZlIHJvdW5kZWQgdGhlIGNvZWZmaWNpZW50cyBzbyB0aGlzIGlzIG5vdCBleGFjdCkuCgpgYGB7cn0Kc3RhdHNfYmVzdCA8LSBtcGcgJT4lIAogIG11dGF0ZShmaXR0ZWQgPSAzNS43MCAtIDMuNTMqZGlzcGwsCiAgICAgICAgIHJlc2lkID0gaHd5IC0gZml0dGVkLAogICAgICAgICByZXNpZF9zcXVhcmVkID0gcmVzaWReMikKCnN0YXRzX2Jlc3QKCnN0YXRzX2Jlc3QgJT4lIAogIHN1bW1hcml6ZShyc3NfYmVzdCA9IHN1bShyZXNpZF9zcXVhcmVkKSkKYGBgCgo8ZGl2IGNsYXNzPSJhbGVydCBhbGVydC1pbmZvIj4KICA8c3Ryb25nPllPVVIgVFVSTiE8L3N0cm9uZz4KICAKMS4gSW4gdGhlIHR3byBncmFwaHMgYWJvdmUsIHdoYXQgZG8geW91IG5vdGljZSBhYm91dCB0aGUgc2l6ZSBvZiB0aGUgcmVzaWR1YWxzLCBpbiBnZW5lcmFsPyAgCgoyLiBIb3cgY291bGQgd2UgcmVwcmVzZW50IHRoZSBzcXVhcmVkIHJlc2lkdWFscyBvbiB0aGUgZ3JhcGg/ICAKCjMuIE1vZGlmeSB0aGUgY29kZSBhYm92ZSB0byBjb21wdXRlIHRoZSBzdW0gb2YgdGhlIHNxdWFyZWQgcmVzaWR1YWxzIGZvciB0aGUgbW9kZWwgZnJvbSB0aGUgZ3JhcGggb24gdGhlIHJpZ2h0LiBIb3cgZG9lcyB0aGF0IGNvbXBhcmUgdG8gdGhlIHN1bSBvZiB0aGUgc3F1YXJlZCByZXNpZHVhbHMgZnJvbSB0aGUgbGVhc3Qgc3F1YXJlcyBsaW5lPwoKNC4gSW4gdGhlIGNvZGUgYmVsb3csIHRyeSBtb2RpZnlpbmcgdGhlIGBteV95X2ludGAgYW5kIGBteV9zbG9wZWAgdmFsdWVzLCB3aGljaCBhcmUgeW91ciBpbnRlcmNlcHQgYW5kIHNsb3BlIGZvciB0aGUgbGluZS4gV2hlbiB5b3UgcnVuIHRoZSBjb2RlLCB0aGUgcmVzaWR1YWwgc3VtIG9mIHNxdWFyZXMgKFJTUykgd2lsbCBiZSBzaG93biBpbiB0aGUgdGl0bGUuIFBsYXkgYXJvdW5kIHdpdGggdGhpcyBmb3IgYXdoaWxlLiBBcmUgdGhlcmUgYW55IG90aGVyIGxpbmVzIHlvdSBjYW4gZml0IHRoYXQgYXJlIHZlcnkgdW5saWtlIHRoZSBiZXN0IGZpdCBsaW5lIGJ1dCBzdGlsbCBoYXZlIHNtYWxsIFJTUz8KCjwvZGl2PgoKYGBge3J9Cm15X3lfaW50ID0gNTAgI3B1dCB5b3VyIHktaW50ZXJjZXB0IGhlcmUKbXlfc2xvcGUgPSAtNSAjcHV0IHlvdXIgc2xvcGUgaGVyZQoKcnNzIDwtIG1wZyAlPiUgCiAgc3VtbWFyaXplKHJzcyA9IHN1bSgoaHd5IC0gKG15X3lfaW50ICsgbXlfc2xvcGUqZGlzcGwpKV4yKSkgJT4lIAogIHB1bGwocnNzKQoKbXBnICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBkaXNwbCwgeSA9IGh3eSkpICsKICBnZW9tX2FibGluZShzbG9wZSA9IG15X3Nsb3BlLCBpbnRlcmNlcHQgPSBteV95X2ludCwgY29sb3IgPSAiYmx1ZSIsIHNpemUgPSAuNSkgKwogIGdlb21fc2VnbWVudChhZXMoeGVuZCA9IGRpc3BsLCAKICAgICAgICAgICAgICAgICAgIHllbmQgPSBteV95X2ludCArIG15X3Nsb3BlKmRpc3BsKSwgCiAgICAgICAgICAgICAgIGNvbG9yID0gImRhcmtyZWQiKSArCiAgZ2VvbV9wb2ludChhZXMoeCA9IGRpc3BsLCB5ID0gbXlfeV9pbnQgKyBteV9zbG9wZSpkaXNwbCksIGNvbG9yID0gImJsdWUiKSArCiAgZ2VvbV9wb2ludCgpICsgCiAgbGFicyh0aXRsZSA9IGJxdW90ZShSU1MgPT0gLihyc3MpKSkKYGBgCgpMZXQncyBhbHNvIHRha2UgYSBsaXR0bGUgYml0IG9mIHRpbWUgZXhwbG9yaW5nIFt0aGlzIHdlYnNpdGVdKGh0dHA6Ly9zZXRvc2EuaW8vZXYvb3JkaW5hcnktbGVhc3Qtc3F1YXJlcy1yZWdyZXNzaW9uLykuCgojIEV2YWx1YXRpb24KCiogSXMgb3VyIG1vZGVsIGFjY3VyYXRlPyAgCiogRG9lcyBpdCBwcmVkaWN0IG5ldyBvYnNlcnZhdGlvbnMgd2VsbD8gIAoKIyMgVmFyaWFuY2UgZXhwbGFpbmVkIGluIHJlc3BvbnNlOiAkUl4yJAoKUmVjYWxsIHRoYXQgb25lIG9mIG91ciBnb2FscyBpbiBidWlsZGluZyBhIG1vZGVsIGlzIHRvIGJldHRlciBleHBsYWluIHRoZSB2YXJpYXRpb24gaW4gb3VyIHJlc3BvbnNlIHZhcmlhYmxlLCAkeSQuIAoKTGV0J3MgdGFrZSBhIGxvb2sgYXQgdGhlIGBtcGdgIGRhdGEgYWdhaW4uIEZpcnN0LCBsZXQncyBqdXN0IGxvb2sgYXQgYSBkaXN0cmlidXRpb24gb2YgaGlnaHdheSBtcGcsIGBod3lgLgoKYGBge3J9CmdncGxvdChtcGcpICsKICBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IGh3eSksIGJpbnMgPSAzMCkgKwogIGdlb21fdmxpbmUoYWVzKHhpbnRlcmNlcHQgPSBtZWFuKGh3eSkpLCBjb2xvciA9ICJkYXJrcmVkIikgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKClRoZSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgYGh3eWAgaXMgYHIgc2QobXBnJGh3eSlgIGFuZCB0aGUgdmFyaWFuY2UgaXMgYHIgdmFyKG1wZyRod3kpYC4gVGhlc2UgYXJlIHdheXMgd2UndmUgdGFsa2VkIGFib3V0IG1lYXN1cmluZyB2YXJpYXRpb24uIFdlIGNvdWxkIGFsc28gdXNlIHRoZSBzdW0gb2YgdGhlIHNxdWFyZWQgZGV2aWF0aW9ucyBmcm9tIHRoZSBtZWFuLCBTU1QgKHRvdGFsIHN1bSBvZiBzcXVhcmVzKToKCmBgYHtyfQptcGcgJT4lIAogIHN1bW1hcml6ZShzc3QgPSBzdW0oKGh3eSAtIG1lYW4oaHd5KSleMikpCmBgYAoKV2h5IGRvIHdlIGxpa2UgdGhpcyBtZWFzdXJlPyEgSXQgaXMgZ29pbmcgdG8gZ2l2ZSB1cyBhIGdvb2Qgd2F5IHRvIGNvbXBhcmUgdG8gb3VyIGZpdHRlZCB2YWx1ZXMgYWZ0ZXIgZml0dGluZyBhIG1vZGVsLgoKTm93LCBsZXQncyBmaXQgdGhlIHNpbXBsZSBtb2RlbCB0aGF0IHVzZXMgZW5naW5lIGRpc3BsYWNlbWVudCwgYGRpc3BsYCwgdG8gZXhwbGFpbiBgaHd5YC4KCmBgYHtyfQpsbV9kaXNwbCA8LSBsbShod3kgfiBkaXNwbCwKICAgICAgICAgICAgICAgZGF0YT1tcGcpCnRpZHkobG1fZGlzcGwpCmBgYAoKV2UgY2FuIGNvbXBhcmUgdGhlIHZhcmlhdGlvbiBpbiBgaHd5YCBhZnRlciBhY2NvdW50aW5nIGZvciBgZGlzcGxgIHRvIHRoZSB2YXJpYXRpb24gb2YgYGh3eWAgYWNjb3VudGluZyBmb3Igbm8gdmFyaWFibGVzLiBUaGVzZSBhcmUgc2hvd24gaW4gdGhlIHBsb3RzIGJlbG93LgoKYGBge3IsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTQsIGVjaG89RkFMU0V9CmcxIDwtIGF1Z21lbnQobG1fZGlzcGwsIGRhdGE9bXBnKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gZGlzcGwsIHkgPSBod3kpKSArCiAgZ2VvbV9wb2ludCgpICsKICBnZW9tX2xpbmUoYWVzKHggPSBkaXNwbCwgeSA9IC5maXR0ZWQpLCBjb2xvciA9ICJkYXJrcmVkIikgKwogIGdlb21fc2VnbWVudChhZXMoeGVuZCA9IGRpc3BsLCAKICAgICAgICAgICAgICAgICAgIHllbmQgPSAzNS43MCAtIDMuNTMqZGlzcGwpLCAKICAgICAgICAgICAgICAgY29sb3IgPSAiZGFya3JlZCIpICsKICBsYWJzKHRpdGxlID0gIkJlc3QgTGluZSIpCgpnMiA8LSBtcGcgJT4lIAogIGdncGxvdChhZXMoeCA9IGRpc3BsLCB5ID0gaHd5KSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9obGluZShhZXMoeWludGVyY2VwdCA9IG1lYW4oaHd5KSksIGNvbG9yID0gImRhcmtyZWQiKSArCiAgZ2VvbV9zZWdtZW50KGFlcyh4ZW5kID0gZGlzcGwsIAogICAgICAgICAgICAgICAgICAgeWVuZCA9IG1lYW4oaHd5KSksIAogICAgICAgICAgICAgICBjb2xvciA9ICJkYXJrcmVkIikgKwogIGxhYnModGl0bGUgPSAiTWVhbiBvZiBod3kiKQoKZzEgKyBnMgpgYGAKCgpXZSB3b3VsZCBsaWtlIHRvIGtub3cgaWYgdGhlcmUgaXMgbGVzcyB2YXJpYXRpb24gaW4gYGh3eWAgIGFmdGVyIHVzaW5nIGBkaXNwbGAgdG8gaGVscCBleHBsYWluIGBod3lgLiBPciwgb25jZSBJIGtub3cgYGRpc3BsYCwgY2FuIEkgcHJlZGljdCBgaHd5YCBiZXR0ZXI/IFdlIGNhbiBldmFsdWF0ZSB0aGlzIGJ5IHRoZSBzdW0gb2YgdGhlIHNxdWFyZWQgcmVzaWR1YWxzLCBSU1MgKHllcywgdGhpcyBpcyB0aGUgc2FtZSBxdWFudGl0eSB0aGF0IGdldHMgbWluaW1pemVkIHdoZW4gd2UgZmluZCB0aGUgImJlc3QiIGNvZWZmaWNpZW50KS4KCgpgYGB7cn0KYXVnbWVudChsbV9kaXNwbCwgZGF0YT1tcGcpICU+JSAKICBzdW1tYXJpemUocnNzID0gc3VtKC5yZXNpZF4yKSkKYGBgCgpIb3cgZG9lcyB0aGlzIGNvbXBhcmUgdG8gU1NUPwoKV2UgZGVmaW5lICRSXjIkIGFzCgokJApSXjIgID0gMSAtIFxmcmFje1JTU317U1NUfSA9IDEgLSBcZnJhY3tcc3VtKHlfaSAtIFxoYXR7eX1faSleMn17XHN1bSh5X2kgLSBcYmFye3l9KV4yfS4KJCQKSXQgaXMgdGhlIGZyYWN0aW9uIG9mIHZhcmlhdGlvbiBpbiAkeSQgYWNjb3VudGVkIGZvciBvciBleHBsYWluZWQgYnkgdGhlIG1vZGVsLiAKCgo8ZGl2IGNsYXNzPSJhbGVydCBhbGVydC1pbmZvIj4KICA8c3Ryb25nPllPVVIgVFVSTiE8L3N0cm9uZz4KCjEuIEhvdyBzbWFsbCBjYW4gJFJeMiQgYmU/IFdoZW4gd2lsbCAkUl4yJCBiZSBzbWFsbD8gIAoyLiBIb3cgbGFyZ2UgY2FuICRSXjIkIGJlPyBXaGVuIHdpbGwgJFJeMiQgYmUgbGFyZ2U/ICAKMy4gV2hhdCBhcmUgdGhlIHVuaXRzIG9mICRSXjIkPwoKPC9kaXY+CgpXZSBjYW4gdXNlIHRoZSBgZ2V0X3JlZ3Jlc3Npb25fc3VtbWFyaWVzYCBvciBgZ2xhbmNlYCB0byBmaW5kIHRoZSAkUl4yJCB2YWx1ZS4gSXQgaXMgY2FsbGVkIGByX3NxdWFyZWRgIG9yIGByLnNxdWFyZWRgLCByZXNwZWN0aXZlbHkuIAoKYGBge3J9CmdldF9yZWdyZXNzaW9uX3N1bW1hcmllcyhsbV9kaXNwbCkKZ2xhbmNlKGxtX2Rpc3BsKQpgYGAKCiRSXjIkIGNhbiBiZSB1c2VkIHRvIGNvbXBhcmUgbW9kZWxzIHdpdGggdGhlIHNhbWUgcmVzcG9uc2UgdmFyaWFibGUgYW5kIHRoZSBzYW1lIG51bWJlciBvZiBleHBsYW5hdG9yeSB2YXJpYWJsZXMuCgpGb3IgZXhhbXBsZSwgbGV0J3MgZml0IGFub3RoZXIgbW9kZWwgdGhhdCB1c2VzIGNpdHkgbXBnLCAqY3R5KiwgdG8gcHJlZGljdCBgaHd5YC4gSG93IGRvZXMgdGhpcyBtb2RlbCBjb21wYXJlIHRvIHRoZSBvbmUgd2l0aCBvbmx5IGBkaXNwbGA/CgpgYGB7cn0KbXBnICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBjdHksIHkgPSBod3kpKSArCiAgZ2VvbV9qaXR0ZXIoKSArCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKCmBgYHtyfQpsbV9jdHkgPC0gbG0oaHd5IH4gY3R5LCAKICAgICAgICAgICAgICBkYXRhPW1wZykKdGlkeShsbV9jdHkpCmdsYW5jZShsbV9jdHkpCmBgYAoKKipJTVBPUlRBTlQgTk9URSoqOiBXZSBDQU5OT1QgdXNlICRSXjIkIHRvIGNvbXBhcmUgbW9kZWxzIHdpdGggZGlmZmVyZW50IG51bWJlcnMgb2YgZXhwbGFuYXRvcnkgdmFyaWFibGVzLiBJIHdpbGwgbm90IGdvIGludG8gZGV0YWlscywgYnV0IGhlcmUgaXMgYW4gZXhhbXBsZSBvZiBhZGRpbmcgZml2ZSB2YXJpYWJsZSBvZiAibm9pc2UiIHRvIHRoZSBtb2RlbCwgdGhhdCBpcyA1IHZhcmlhYmxlcyB0aGF0IGFyZSBqdXN0IGEgYnVuY2ggb2YgcmFuZG9tIG51bWJlcnMuIFdoYXQgaGFwcGVucyB0byB0aGUgJFJeMiQgdmFsdWU/IEFkZGluZyBhIG5ldyB2YXJpYWJsZSwgZXZlbiBvbmUgdGhhdCBpcyBjb21wbGV0ZSBub25zZW5zZSB3aWxsIG5ldmVyIGRlY3JlYXNlIHRoZSAkUl4yJCB2YWx1ZS4KCmBgYHtyfQpzZXQuc2VlZCgxMCkgI21ha2VzIHJlc3VsdHMgcmVwcm9kdWNpYmxlCmxtX2Rpc3BsX25vaXNlIDwtIGxtKGh3eSB+IGRpc3BsICsgCiAgICAgICAgICAgICAgICAgICAgICAgcm5vcm0obiA9IG5yb3cobXBnKSkgKwogICAgICAgICAgICAgICAgICAgICAgIHJub3JtKG4gPSBucm93KG1wZykpICsKICAgICAgICAgICAgICAgICAgICAgICBybm9ybShuID0gbnJvdyhtcGcpKSArCiAgICAgICAgICAgICAgICAgICAgICAgcm5vcm0obiA9IG5yb3cobXBnKSkgKwogICAgICAgICAgICAgICAgICAgICAgIHJub3JtKG4gPSBucm93KG1wZykpLAogICAgICAgICAgICAgICAgICAgICBkYXRhPW1wZykKZ2xhbmNlKGxtX2Rpc3BsX25vaXNlKSAlPiUgCiAgc2VsZWN0KHIuc3F1YXJlZCkKCmdsYW5jZShsbV9kaXNwbCkgJT4lIAogIHNlbGVjdChyLnNxdWFyZWQpCmBgYAoKCldlIGNhbiB1c2UgdGhlIGFkanVzdGVkICRSXjIkIHRvIGNvbXBhcmUgbW9kZWxzIHdpdGggZGlmZmVyZW50IG51bWJlcnMgb2YgdmFyaWFibGVzLiBUaGlzIGNhbiBhbHNvIGJlIGZvdW5kIGluIHRoZSBvdXRwdXQgZnJvbSBgZ2xhbmNlYCBvciBgZ2V0X3JlZ3Jlc3Npb25fc3VtbWFyaWVzYC4gUmVhZCBtb3JlIGFib3V0IGFkanVzdGVkICRSXjIkIFtoZXJlXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9Db2VmZmljaWVudF9vZl9kZXRlcm1pbmF0aW9uI0FkanVzdGVkX1IyKS4KCgojIyBTdGFuZGFyZCBlcnJvciBvZiByZWdyZXNzaW9uOiAkXGhhdHtcc2lnbWF9JAoKVGhlIHN0YW5kYXJkIGVycm9yIG9mIHRoZSByZWdyZXNzaW9uLCAkXGhhdHtcc2lnbWF9JCwgaXMgZGVmaW5lZCBhcwoKJCQKXGhhdHtcc2lnbWF9ID0gXHNxcnR7XGZyYWN7XHN1bV97aT0xfV5uICh5X2kgLSBcaGF0e3l9X2kpXjJ9e24tcH19LgokJAoKVGhpcyBjYW4gYmUgZm91bmQgaW4gdGhlIGBnbGFuY2VgIG91dHB1dCwgY2FsbGVkIGBzaWdtYWAuIEl0IGlzIGFub3RoZXIgc3RhdGlzdGljIHRoYXQgZGVzY3JpYmVzIGhvdyB3ZWxsIHRoZSBtb2RlbCBmaXRzLCB0ZWxsaW5nIHVzICphcHByb3hpbWF0ZWx5KiBob3cgZmFyIHRoZSBwcmVkaWN0aW9ucyBhcmUgZnJvbSB0aGVpciBhY3R1YWwgdmFsdWVzLCBvbiBhdmVyYWdlLiAKCgoKCjxkaXYgY2xhc3M9ImFsZXJ0IGFsZXJ0LWluZm8iPgogIDxzdHJvbmc+WU9VUiBUVVJOITwvc3Ryb25nPgoKVXNlIHRoZSBgaHNiMmAgZGF0YXNldCBmcm9tIHRoZSBgb3BlbmludHJvYCBsaWJyYXJ5IHRvIGFuc3dlciB0aGUgZm9sbG93aW5nIHF1ZXN0aW9ucy4KCjEuIEZpcnN0LCBsb29rIGF0IGEgZGlzdHJpYnV0aW9uIG9mIGBtYXRoYC4gQ29tcHV0ZSB0aGUgU1NULgoKMi4gQ29tcHV0ZSB0aGUgJFJeMiQgZm9yIHRoZSBtb2RlbCB0aGF0IHVzZXMgb25seSBgc2VzYCB0byBleHBsYWluIGBtYXRoYC4gRGVzY3JpYmUgd2hhdCB0aGlzIG1lYW5zIGluIHRoZSBjb250ZXh0IG9mIHRoZSBkYXRhLgoKMy4gRmluZCAkXGhhdHtcc2lnbWF9JCBmb3IgdGhpcyBtb2RlbC4gSW50ZXJwcmV0IGl0IGluIHRoZSBjb250ZXh0IG9mIHRoZSBkYXRhLgoKNC4gQ29tcHV0ZSB0aGUgJFJeMiQgZm9yIHRoZSBtb2RlbCB0aGF0IHVzZXMgb25seSBgcHJvZ2AuIFNvLCBkb2VzIGBwcm9nYCBvciBgc2VzYCBleHBsYWluIG1vcmUgb2YgdGhlIHZhcmlhdGlvbiBpbiBgbWF0aGA/Cgo1LiBGaXQgYSBtb2RlbCB3aXRoIGJvdGggYHNlc2AgYW5kIGBwcm9nYC4gVXNlIHRoZSBhZGp1c3RlZCAkUl4yJCB0byBkZWNpZGUgaWYgYWRkaW5nIGEgc2Vjb25kIHZhcmlhYmxlIHRvIHRoZSBtb2RlbCBzZWVtcyB1c2VmdWwuCgo2LiBOb3cgdHJ5IGFkZGluZyBhbiBpbnRlcmFjdGlvbiBlZmZlY3QuIFVzZSB0aGUgYWRqdXN0ZWQgJFJeMiQgdG8gZGVjaWRlZCBpZiBhZGRpbmcgdGhhdCBpcyB1c2VmdWwuIENvbXBhcmUgdGhlIHBsb3RzIHlvdSBjcmVhdGVkIGluIHlvdXIgbW9zdCByZWNlbnQgaG9tZXdvcmsgYXNzaWdubWVudCBvZiB0aGUgZml0dGVkIG1vZGVscyB3aXRoIGFuZCB3aXRob3V0IGFuIGludGVyYWN0aW9uIGVmZmVjdCB0byBoZWxwIGlsbHVzdHJhdGUgd2h5IHlvdSBhcmUgc2VlaW5nIHRoZXNlIHJlc3VsdHMuCgo8L2Rpdj4KCgoK