Nowadays,I am learning about algorithm from ISLR with application in R. previously I was using Simple Linear Regression to predict the sales using single predictors. In this blog, we will use multiple predictors to predict the response. We will use Auto dataset from the MASS package and predict mp(Mile per Gallon) using multiple predictors in Dataset.

library(ISLR)
library(MASS)
library(corrplot) # We'll use corrplot later on in this example too.
library(dplyr)
library(ggplot2)
library(visreg) # This library will allow us to show multivariate graphs.
library(rgl)
library(knitr)
library(scatterplot3d)
data("Auto")
attach(Auto)
head(Auto)
str(Auto)
'data.frame':   392 obs. of  9 variables:
 $ mpg         : num  18 15 18 16 17 15 14 14 14 15 ...
 $ cylinders   : num  8 8 8 8 8 8 8 8 8 8 ...
 $ displacement: num  307 350 318 304 302 429 454 440 455 390 ...
 $ horsepower  : num  130 165 150 150 140 198 220 215 225 190 ...
 $ weight      : num  3504 3693 3436 3433 3449 ...
 $ acceleration: num  12 11.5 11 12 10.5 10 9 8.5 10 8.5 ...
 $ year        : num  70 70 70 70 70 70 70 70 70 70 ...
 $ origin      : num  1 1 1 1 1 1 1 1 1 1 ...
 $ name        : Factor w/ 304 levels "amc ambassador brougham",..: 49 36 231 14 161 141 54 223 241 2 ...
summary(Auto)
      mpg          cylinders      displacement     horsepower        weight    
 Min.   : 9.00   Min.   :3.000   Min.   : 68.0   Min.   : 46.0   Min.   :1613  
 1st Qu.:17.00   1st Qu.:4.000   1st Qu.:105.0   1st Qu.: 75.0   1st Qu.:2225  
 Median :22.75   Median :4.000   Median :151.0   Median : 93.5   Median :2804  
 Mean   :23.45   Mean   :5.472   Mean   :194.4   Mean   :104.5   Mean   :2978  
 3rd Qu.:29.00   3rd Qu.:8.000   3rd Qu.:275.8   3rd Qu.:126.0   3rd Qu.:3615  
 Max.   :46.60   Max.   :8.000   Max.   :455.0   Max.   :230.0   Max.   :5140  
                                                                               
  acceleration        year           origin                      name    
 Min.   : 8.00   Min.   :70.00   Min.   :1.000   amc matador       :  5  
 1st Qu.:13.78   1st Qu.:73.00   1st Qu.:1.000   ford pinto        :  5  
 Median :15.50   Median :76.00   Median :1.000   toyota corolla    :  5  
 Mean   :15.54   Mean   :75.98   Mean   :1.577   amc gremlin       :  4  
 3rd Qu.:17.02   3rd Qu.:79.00   3rd Qu.:2.000   amc hornet        :  4  
 Max.   :24.80   Max.   :82.00   Max.   :3.000   chevrolet chevette:  4  
                                                 (Other)           :365  

The Auto dataset has 392 observation with 9 columns. The columns are like mpg, cylinders, displacement, horsepower etc which are related to the cars. Each row is the data about the cars and name column can be used to identify. In multiple regression, we will use more than one predictors. Before applying the lm() to the dataset we need to drop name column which is a qualitative variable.

auto_df <- select(Auto,-name)

Lets look the dataset after excluding the Name column.

summary(auto_df)
      mpg          cylinders      displacement     horsepower        weight    
 Min.   : 9.00   Min.   :3.000   Min.   : 68.0   Min.   : 46.0   Min.   :1613  
 1st Qu.:17.00   1st Qu.:4.000   1st Qu.:105.0   1st Qu.: 75.0   1st Qu.:2225  
 Median :22.75   Median :4.000   Median :151.0   Median : 93.5   Median :2804  
 Mean   :23.45   Mean   :5.472   Mean   :194.4   Mean   :104.5   Mean   :2978  
 3rd Qu.:29.00   3rd Qu.:8.000   3rd Qu.:275.8   3rd Qu.:126.0   3rd Qu.:3615  
 Max.   :46.60   Max.   :8.000   Max.   :455.0   Max.   :230.0   Max.   :5140  
  acceleration        year           origin     
 Min.   : 8.00   Min.   :70.00   Min.   :1.000  
 1st Qu.:13.78   1st Qu.:73.00   1st Qu.:1.000  
 Median :15.50   Median :76.00   Median :1.000  
 Mean   :15.54   Mean   :75.98   Mean   :1.577  
 3rd Qu.:17.02   3rd Qu.:79.00   3rd Qu.:2.000  
 Max.   :24.80   Max.   :82.00   Max.   :3.000  

The auto_df dataframe contains 8 columns lets look the plot of the dataset.

# Plot matrix of all variables.
plot(auto_df, col="navy", main="Matrix Scatterplot")

The above matrix plot helps to see the relationship between two columns and pattern in the datasets. For example, horsepower and weight seem to have positive relationships. From the plot, mpg seems to have the same pattern with displacement, weight, and horsepower.

In this blog, we want to find the best model for predicting the mpg using different predictors in data. We will look upon residuals error, p-value for the performance of the model.

Multiple Linear regression uses multiple predictors. The equation for multiple linear regression looks like: \[Y=a+b*X1 + c*X2 \] where:

\(Y\) is Response or dependent variable \(a\) is intercept \(X1\) and \(X2\) are predictors or independent variable \(b\) and \(c\) are coefficeints for the b and c respectively

Before fitting the data to a model lets create a test and train set of the Data. Train set will be used to train or fit the model and test set will be used to check the performance of the model. We will split the data to train, test set using an 80:20 ratio.

require(caTools)
sample = sample.split(auto_df,SplitRatio = 0.80) # splits the data in the ratio mentioned in SplitRatio. After splitting marks these rows as logical TRUE and the the remaining are marked as logical FALSE
train1 =subset(auto_df,sample ==TRUE) # creates a training dataset named train1 with rows which are marked as TRUE
test1=subset(auto_df, sample==FALSE)

Lets look into the train and test data.

summary(train1)
      mpg         cylinders      displacement     horsepower        weight    
 Min.   : 9.0   Min.   :3.000   Min.   : 68.0   Min.   : 46.0   Min.   :1613  
 1st Qu.:17.0   1st Qu.:4.000   1st Qu.: 98.0   1st Qu.: 75.0   1st Qu.:2204  
 Median :23.0   Median :4.000   Median :140.5   Median : 92.0   Median :2782  
 Mean   :23.7   Mean   :5.466   Mean   :194.2   Mean   :104.2   Mean   :2959  
 3rd Qu.:30.0   3rd Qu.:8.000   3rd Qu.:302.0   3rd Qu.:130.0   3rd Qu.:3600  
 Max.   :46.6   Max.   :8.000   Max.   :455.0   Max.   :230.0   Max.   :5140  
  acceleration        year           origin     
 Min.   : 8.00   Min.   :70.00   Min.   :1.000  
 1st Qu.:13.62   1st Qu.:73.00   1st Qu.:1.000  
 Median :15.50   Median :76.00   Median :1.000  
 Mean   :15.51   Mean   :75.98   Mean   :1.582  
 3rd Qu.:17.00   3rd Qu.:79.00   3rd Qu.:2.000  
 Max.   :24.60   Max.   :82.00   Max.   :3.000  
summary(test1)
      mpg          cylinders     displacement     horsepower         weight    
 Min.   :10.00   Min.   :3.00   Min.   : 71.0   Min.   : 52.00   Min.   :1825  
 1st Qu.:17.50   1st Qu.:4.00   1st Qu.:115.2   1st Qu.: 80.25   1st Qu.:2302  
 Median :22.00   Median :5.50   Median :159.5   Median : 95.00   Median :2852  
 Mean   :22.69   Mean   :5.49   Mean   :195.2   Mean   :105.15   Mean   :3035  
 3rd Qu.:27.15   3rd Qu.:6.00   3rd Qu.:250.0   3rd Qu.:114.50   3rd Qu.:3641  
 Max.   :44.60   Max.   :8.00   Max.   :440.0   Max.   :215.00   Max.   :4955  
  acceleration        year           origin     
 Min.   : 8.50   Min.   :70.00   Min.   :1.000  
 1st Qu.:14.00   1st Qu.:73.00   1st Qu.:1.000  
 Median :15.50   Median :76.00   Median :1.000  
 Mean   :15.64   Mean   :75.99   Mean   :1.561  
 3rd Qu.:17.50   3rd Qu.:79.00   3rd Qu.:2.000  
 Max.   :24.80   Max.   :82.00   Max.   :3.000  

Fitting Models

Its time to fit the model and We will use Least Square method to fit our regression model.

fit1<- lm(mpg~., data = train1)
summary(fit1)

Call:
lm(formula = mpg ~ ., data = train1)

Residuals:
    Min      1Q  Median      3Q     Max 
-8.6093 -2.3503 -0.1876  1.9308 12.6934 

Coefficients:
               Estimate Std. Error t value Pr(>|t|)    
(Intercept)  -1.739e+01  5.457e+00  -3.186   0.0016 ** 
cylinders    -3.549e-01  3.948e-01  -0.899   0.3694    
displacement  1.731e-02  8.991e-03   1.925   0.0552 .  
horsepower   -2.754e-02  1.612e-02  -1.709   0.0886 .  
weight       -6.272e-03  7.873e-04  -7.967 3.88e-14 ***
acceleration  4.153e-02  1.166e-01   0.356   0.7221    
year          7.664e-01  6.072e-02  12.622  < 2e-16 ***
origin        1.397e+00  3.293e-01   4.244 2.97e-05 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3.441 on 286 degrees of freedom
Multiple R-squared:  0.8189,    Adjusted R-squared:  0.8145 
F-statistic: 184.8 on 7 and 286 DF,  p-value: < 2.2e-16

We have the results of the model . From the model output we found that:

The matrix scatterplot above shows that there is the high correlation between displacement,weight, and horsepower. When there are two or more variables strongly correlated it is called collinearity. Let us validate by using correlation plot.

cor = cor(test1[1:8])
corrplot(cor, method = "number")

From the correlation, we can see that there is a strong relation between cylinders, displacement,horsepower, and weight. The mpg is also strongly correlated to cylinders, and weight. This situation is called collinearity.The problem of collinearity in the response is that it is difficult to find the individual effect on response. We should drop use only one of the collinear variables.

As the cylinders don’t show any significant relation in the first model with mpg we will exclude cylinders. Out of displacement, horsepower, and weight, the output of the first model shows that weight and mpg have a highly significant relation. We will use weight out of the other collinear variables in the next model.

fit2 <- lm(mpg~weight+year+origin,data = train1)
summary(fit2)

Call:
lm(formula = mpg ~ weight + year + origin, data = train1)

Residuals:
    Min      1Q  Median      3Q     Max 
-8.4916 -2.3379 -0.1141  1.7380 12.9231 

Coefficients:
              Estimate Std. Error t value Pr(>|t|)    
(Intercept) -1.948e+01  4.742e+00  -4.109 5.18e-05 ***
weight      -6.202e-03  3.026e-04 -20.495  < 2e-16 ***
year         7.866e-01  5.756e-02  13.668  < 2e-16 ***
origin       1.105e+00  3.064e-01   3.607 0.000364 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3.457 on 290 degrees of freedom
Multiple R-squared:  0.8148,    Adjusted R-squared:  0.8128 
F-statistic: 425.2 on 3 and 290 DF,  p-value: < 2.2e-16

In this model, we find all predictors p-value is highly significant. After excluding the collinear variable the F- statistic improved from 184.8 to 425.2 which is a great improvement. But there is no improvement on RSE and adjusted R squared value. Let’s plot the residuals:

plot(fit2, which =1)

This plot shows some of the outliers lying far away from the middle of the graph.

We will try a different type of transformation on both predictors and the response value and see how the performance of model changes. In the next model, we will use the natural log to the mpg using log() and see the change in performance of the model.

fit3 <- lm(log(mpg)~weight+year+origin,data = train1)
summary(fit3)

Call:
lm(formula = log(mpg) ~ weight + year + origin, data = train1)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.42966 -0.07392  0.00231  0.06847  0.37197 

Coefficients:
              Estimate Std. Error t value Pr(>|t|)    
(Intercept)  1.486e+00  1.687e-01   8.806  < 2e-16 ***
weight      -2.961e-04  1.077e-05 -27.491  < 2e-16 ***
year         3.220e-02  2.048e-03  15.722  < 2e-16 ***
origin       3.170e-02  1.090e-02   2.907  0.00392 ** 
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.123 on 290 degrees of freedom
Multiple R-squared:  0.8734,    Adjusted R-squared:  0.8721 
F-statistic: 666.8 on 3 and 290 DF,  p-value: < 2.2e-16
plot(fit3, which =1)

After some changes in the model, the performance of the model is increased. The Adjusted R-squared raised to 0.8721 and F-statistic is increased to 668.8. The p-value of the predictors is significant.

Let’s make a certain change in this model. We will use the natural log to the weight and mpg.

fit4 <- lm(log(mpg)~log(weight)+year+origin,data = auto_df)
summary(fit4)

Call:
lm(formula = log(mpg) ~ log(weight) + year + origin, data = auto_df)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.40429 -0.06527  0.00074  0.06386  0.39896 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)  7.776372   0.283133  27.465   <2e-16 ***
log(weight) -0.904177   0.027317 -33.099   <2e-16 ***
year         0.032789   0.001682  19.493   <2e-16 ***
origin       0.017207   0.009289   1.852   0.0647 .  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1174 on 388 degrees of freedom
Multiple R-squared:  0.8818,    Adjusted R-squared:  0.8809 
F-statistic: 964.7 on 3 and 388 DF,  p-value: < 2.2e-16
plot(fit4,which = 1)

In this model, the F-statistics and Adjusted R-squared are improved. Most of the predictor’s p-value is significant.The origin predictor seems to have weak p-value which means that origin doesn’t have strong relationships with the mpg while the presence of other predictors. So, we will exclude the origin and make a new model.

fit5 <- lm(log(mpg)~log(weight)+year,data = auto_df)
summary(fit5)

Call:
lm(formula = log(mpg) ~ log(weight) + year, data = auto_df)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.40595 -0.06360  0.00169  0.06379  0.39270 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)  8.039451   0.245703   32.72   <2e-16 ***
log(weight) -0.934085   0.022104  -42.26   <2e-16 ***
year         0.032817   0.001687   19.45   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1177 on 389 degrees of freedom
Multiple R-squared:  0.8807,    Adjusted R-squared:  0.8801 
F-statistic:  1436 on 2 and 389 DF,  p-value: < 2.2e-16
plot(fit5,which = 1)

The output of this model shows that the F-statistics is increased to 1436 and the Adjusted R-squared is also increased.The predictor has highly significant p values. This model is better than previous models.

The final regression equation for our model is:

\[ log(mpg) = 8.0395 + log(weight)* -.9341 + year * .0328 \]

Accuracy

We will use the test data to check the accuracy of our final model.

predictions<-predict(fit5, test1)
mse <- mean((test1$mpg - predictions)^2)
print(mse)
[1] 435.6201
sigma(fit5)/mean(test1$mpg)
[1] 0.005167033
test1$predicted<- predict(fit5,test1)
actuals_preds <- data.frame(test1$mpg,test1$predicted)
names(actuals_preds)<- c("mpg","predicted")
correlation_accuracy <- cor(actuals_preds)
correlation_accuracy
                mpg predicted
mpg       1.0000000 0.9228438
predicted 0.9228438 1.0000000

The correlation of the models shows that the accuracy is around 92 %.Lets check the true mpg and predicted mpg for the test data.

head(actuals_preds)

Wow! what happened?We used log to the response value in our model which predicted the response with a log. If we use log to the original mpg we can relate this result.

actuals_preds$log_mpg <- log(actuals_preds$mpg)
head(actuals_preds)

Finally

In this blog, we used Multiple Linear Regression methods to find the mpg of the car. We had 8 columns out of which 4 were collinear to each other. we got the best model with only two predictors. \[ log(mpg) = 8.0395 + log(weight)* -.9341 + year * .0328 \]

Reference:

LS0tCnRpdGxlOiAiTXVsdGlwbGUgTGluZWFyIFJlZ3Jlc3Npb24iCmF1dGhvcjogIkRpd2FzaCBTaHJlc3RoYSIKZGF0ZTogIjIwMTgvMDgvMTIiCm91dHB1dDogCiAgaHRtbF9ub3RlYm9vazoKICAgIHRoZW1lOiB5ZXRpCi0tLQo8Y2VudGVyPjxpbWcgc3JjID0gImh0dHBzOi8vbWFkaHVyZXNoa3VtYXIuZmlsZXMud29yZHByZXNzLmNvbS8yMDE1LzA3L2NhcnRvb25fZ3VpZGVfcmVncmVzc2lvbi5wbmciPjwvY2VudGVyPgoKTm93YWRheXMsSSBhbSBsZWFybmluZyBhYm91dCBhbGdvcml0aG0gZnJvbSBJU0xSIHdpdGggYXBwbGljYXRpb24gaW4gUi4gcHJldmlvdXNseSBJIHdhcyB1c2luZyBTaW1wbGUgTGluZWFyIFJlZ3Jlc3Npb24gdG8gcHJlZGljdCB0aGUgc2FsZXMgdXNpbmcgc2luZ2xlIHByZWRpY3RvcnMuIEluIHRoaXMgYmxvZywgd2Ugd2lsbCB1c2UgbXVsdGlwbGUgcHJlZGljdG9ycyB0byBwcmVkaWN0IHRoZSByZXNwb25zZS4gV2Ugd2lsbCB1c2UgQXV0byBkYXRhc2V0IGZyb20gdGhlIE1BU1MgcGFja2FnZSBhbmQgcHJlZGljdCBtcChNaWxlIHBlciBHYWxsb24pIHVzaW5nIG11bHRpcGxlIHByZWRpY3RvcnMgaW4gRGF0YXNldC4KYGBge3IgZmlnLmhlaWdodD0xNCwgZmlnLndpZHRoPTE0LCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KElTTFIpCmxpYnJhcnkoTUFTUykKbGlicmFyeShjb3JycGxvdCkgCmxpYnJhcnkoZHBseXIpCmBgYAoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KZGF0YSgiQXV0byIpCmF0dGFjaChBdXRvKQoKaGVhZChBdXRvKQpgYGAKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0Kc3RyKEF1dG8pCmBgYAoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0Kc3VtbWFyeShBdXRvKQpgYGAKVGhlIEF1dG8gZGF0YXNldCBoYXMgMzkyIG9ic2VydmF0aW9uIHdpdGggOSBjb2x1bW5zLiBUaGUgY29sdW1ucyBhcmUgbGlrZSBtcGcsIGN5bGluZGVycywgZGlzcGxhY2VtZW50LCBob3JzZXBvd2VyIGV0YyB3aGljaCBhcmUgcmVsYXRlZCB0byB0aGUgY2Fycy4gRWFjaCByb3cgaXMgdGhlIGRhdGEgYWJvdXQgdGhlIGNhcnMgYW5kIG5hbWUgY29sdW1uIGNhbiBiZSB1c2VkIHRvIGlkZW50aWZ5LiBJbiBtdWx0aXBsZSByZWdyZXNzaW9uLCB3ZSB3aWxsIHVzZSBtb3JlIHRoYW4gb25lIHByZWRpY3RvcnMuIEJlZm9yZSBhcHBseWluZyB0aGUgbG0oKSB0byB0aGUgZGF0YXNldCB3ZSBuZWVkIHRvIGRyb3AgbmFtZSBjb2x1bW4gd2hpY2ggaXMgYSBxdWFsaXRhdGl2ZSB2YXJpYWJsZS4KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KCmF1dG9fZGYgPC0gc2VsZWN0KEF1dG8sLW5hbWUpCmBgYApMZXRzIGxvb2sgdGhlIGRhdGFzZXQgYWZ0ZXIgZXhjbHVkaW5nIHRoZSBOYW1lIGNvbHVtbi4KCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CnN1bW1hcnkoYXV0b19kZikKYGBgClRoZSBhdXRvX2RmIGRhdGFmcmFtZSBjb250YWlucyA4IGNvbHVtbnMgbGV0cyBsb29rIHRoZSBwbG90IG9mIHRoZSBkYXRhc2V0LgoKYGBge3IgZmlnLmhlaWdodD0xMCwgZmlnLndpZHRoPTEwLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQojIFBsb3QgbWF0cml4IG9mIGFsbCB2YXJpYWJsZXMuCnBsb3QoYXV0b19kZiwgY29sPSJuYXZ5IiwgbWFpbj0iTWF0cml4IFNjYXR0ZXJwbG90IikKCmBgYApUaGUgYWJvdmUgbWF0cml4IHBsb3QgaGVscHMgdG8gc2VlIHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiB0d28gY29sdW1ucyBhbmQgcGF0dGVybiBpbiB0aGUgZGF0YXNldHMuIEZvciBleGFtcGxlLCBob3JzZXBvd2VyIGFuZCB3ZWlnaHQgc2VlbSB0byBoYXZlIHBvc2l0aXZlIHJlbGF0aW9uc2hpcHMuCkZyb20gdGhlIHBsb3QsIG1wZyBzZWVtcyB0byBoYXZlIHRoZSBzYW1lIHBhdHRlcm4gd2l0aCBkaXNwbGFjZW1lbnQsIHdlaWdodCwgYW5kIGhvcnNlcG93ZXIuCgpJbiB0aGlzIGJsb2csIHdlIHdhbnQgdG8gZmluZCB0aGUgYmVzdCBtb2RlbCBmb3IgcHJlZGljdGluZyB0aGUgbXBnIHVzaW5nIGRpZmZlcmVudCBwcmVkaWN0b3JzIGluIGRhdGEuIFdlIHdpbGwgbG9vayB1cG9uIHJlc2lkdWFscyBlcnJvciwgcC12YWx1ZSBmb3IgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSBtb2RlbC4KCk11bHRpcGxlIExpbmVhciByZWdyZXNzaW9uIHVzZXMgbXVsdGlwbGUgcHJlZGljdG9ycy4gVGhlIGVxdWF0aW9uIGZvciBtdWx0aXBsZSBsaW5lYXIgcmVncmVzc2lvbiBsb29rcyBsaWtlOgokJFk9YStiKlgxICsgYypYMiAkJAp3aGVyZToKCiokWSQgaXMgUmVzcG9uc2Ugb3IgZGVwZW5kZW50IHZhcmlhYmxlCiokYSQgaXMgaW50ZXJjZXB0CiokWDEkIGFuZCAkWDIkIGFyZSBwcmVkaWN0b3JzIG9yIGluZGVwZW5kZW50IHZhcmlhYmxlCiokYiQgYW5kICRjJCBhcmUgY29lZmZpY2VpbnRzIGZvciB0aGUgYiBhbmQgYyByZXNwZWN0aXZlbHkKCkJlZm9yZSBmaXR0aW5nIHRoZSBkYXRhIHRvIGEgbW9kZWwgbGV0cyBjcmVhdGUgYSB0ZXN0IGFuZCB0cmFpbiBzZXQgb2YgdGhlIERhdGEuIFRyYWluIHNldCB3aWxsIGJlIHVzZWQgdG8gdHJhaW4gb3IgZml0IHRoZSBtb2RlbCBhbmQgdGVzdCBzZXQgd2lsbCBiZSB1c2VkIHRvIGNoZWNrIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgbW9kZWwuIFdlIHdpbGwgc3BsaXQgdGhlIGRhdGEgdG8gdHJhaW4sIHRlc3Qgc2V0IHVzaW5nIGFuIDgwOjIwIHJhdGlvLgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpyZXF1aXJlKGNhVG9vbHMpCnNhbXBsZSA9IHNhbXBsZS5zcGxpdChhdXRvX2RmLFNwbGl0UmF0aW8gPSAwLjgwKSAKdHJhaW4xID1zdWJzZXQoYXV0b19kZixzYW1wbGUgPT1UUlVFKSAjIGNyZWF0ZXMgYSB0cmFpbmluZyBkYXRhc2V0IG5hbWVkIHRyYWluMSB3aXRoIHJvd3Mgd2hpY2ggYXJlIG1hcmtlZCBhcyBUUlVFCnRlc3QxPXN1YnNldChhdXRvX2RmLCBzYW1wbGU9PUZBTFNFKQpgYGAKTGV0cyBsb29rIGludG8gdGhlIHRyYWluIGFuZCB0ZXN0IGRhdGEuCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CnN1bW1hcnkodHJhaW4xKQoKYGBgCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CnN1bW1hcnkodGVzdDEpCmBgYAoKCgojIyBGaXR0aW5nIE1vZGVscwoKSXRzIHRpbWUgdG8gZml0IHRoZSBtb2RlbCBhbmQgV2Ugd2lsbCB1c2UgTGVhc3QgU3F1YXJlIG1ldGhvZCB0byBmaXQgb3VyIHJlZ3Jlc3Npb24gbW9kZWwuCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CiNmaXR0aW5nIGxpbmVhciBtb2RlbCBhbmQgcnVuIHN1bW1hcnkgb2YgdGhlIGZpdApmaXQxPC0gbG0obXBnfi4sIGRhdGEgPSB0cmFpbjEpCnN1bW1hcnkoZml0MSkKYGBgCldlIGhhdmUgdGhlIHJlc3VsdHMgb2YgdGhlIG1vZGVsIC4KRnJvbSB0aGUgbW9kZWwgb3V0cHV0IHdlIGZvdW5kIHRoYXQ6CgoqIFRoZSBwIHZhbHVlIG9mICBjeWxpbmRlcnMgYW5kIGFjY2VsZXJhdGlvbiBzaG93cyB0aGF0IHRoZXJlIGlzIG5vIHNpZ25pZmljYW50IHJlbGF0aW9uIHdpdGggbXBnLgoqIFRoZSBSU0UgaXMgMy40NDEgd2hlcmUgcC12YWx1ZSBpcyB2ZXJ5IHNtYWxsLgoKVGhlIG1hdHJpeCBzY2F0dGVycGxvdCBhYm92ZSBzaG93cyB0aGF0IHRoZXJlIGlzIHRoZSBoaWdoIGNvcnJlbGF0aW9uIGJldHdlZW4gZGlzcGxhY2VtZW50LHdlaWdodCwgYW5kIGhvcnNlcG93ZXIuIFdoZW4gdGhlcmUgYXJlIHR3byBvciBtb3JlIHZhcmlhYmxlcyBzdHJvbmdseSBjb3JyZWxhdGVkIGl0IGlzIGNhbGxlZCBjb2xsaW5lYXJpdHkuIExldCB1cyB2YWxpZGF0ZSBieSB1c2luZyBjb3JyZWxhdGlvbiBwbG90LgpgYGB7ciBmaWcuaGVpZ2h0PTEwLCBmaWcud2lkdGg9MTAsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIHBhZ2VkLnByaW50PVRSVUV9CiMgUGxvdCBhIGNvcnJlbGF0aW9uIGdyYXBoCmNvciA9IGNvcih0ZXN0MVsxOjhdKQpjb3JycGxvdChjb3IsIG1ldGhvZCA9ICJudW1iZXIiKQpgYGAKRnJvbSB0aGUgY29ycmVsYXRpb24sIHdlIGNhbiBzZWUgdGhhdCB0aGVyZSBpcyBhIHN0cm9uZyByZWxhdGlvbiBiZXR3ZWVuIGN5bGluZGVycywgZGlzcGxhY2VtZW50LGhvcnNlcG93ZXIsIGFuZCB3ZWlnaHQuIFRoZSBtcGcgaXMgYWxzbyBzdHJvbmdseSBjb3JyZWxhdGVkIHRvIGN5bGluZGVycywgYW5kIHdlaWdodC4gVGhpcyBzaXR1YXRpb24gaXMgY2FsbGVkIGNvbGxpbmVhcml0eS5UaGUgcHJvYmxlbSBvZiBjb2xsaW5lYXJpdHkgaW4gdGhlIHJlc3BvbnNlIGlzIHRoYXQgaXQgaXMgZGlmZmljdWx0IHRvIGZpbmQgdGhlIGluZGl2aWR1YWwgZWZmZWN0IG9uIHJlc3BvbnNlLiBXZSBzaG91bGQgZHJvcCB1c2Ugb25seSBvbmUgb2YgdGhlIGNvbGxpbmVhciB2YXJpYWJsZXMuCgpBcyB0aGUgY3lsaW5kZXJzIGRvbid0IHNob3cgYW55IHNpZ25pZmljYW50IHJlbGF0aW9uIGluIHRoZSBmaXJzdCBtb2RlbCB3aXRoIG1wZyB3ZSB3aWxsIGV4Y2x1ZGUgY3lsaW5kZXJzLiBPdXQgb2YgZGlzcGxhY2VtZW50LCBob3JzZXBvd2VyLCBhbmQgd2VpZ2h0LCB0aGUgb3V0cHV0IG9mIHRoZSBmaXJzdCBtb2RlbCBzaG93cyB0aGF0IHdlaWdodCBhbmQgbXBnIGhhdmUgYSBoaWdobHkgc2lnbmlmaWNhbnQgcmVsYXRpb24uIFdlIHdpbGwgdXNlIHdlaWdodCBvdXQgb2YgdGhlIG90aGVyIGNvbGxpbmVhciB2YXJpYWJsZXMgaW4gdGhlIG5leHQgbW9kZWwuCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmZpdDIgPC0gbG0obXBnfndlaWdodCt5ZWFyK29yaWdpbixkYXRhID0gdHJhaW4xKQpzdW1tYXJ5KGZpdDIpCmBgYApJbiB0aGlzIG1vZGVsLCB3ZSBmaW5kIGFsbCBwcmVkaWN0b3JzIHAtdmFsdWUgaXMgaGlnaGx5IHNpZ25pZmljYW50LiBBZnRlciBleGNsdWRpbmcgdGhlIGNvbGxpbmVhciB2YXJpYWJsZSB0aGUgRi0gc3RhdGlzdGljIGltcHJvdmVkIGZyb20gMTg0LjggdG8gNDI1LjIgd2hpY2ggaXMgYSBncmVhdCBpbXByb3ZlbWVudC4gQnV0IHRoZXJlIGlzIG5vIGltcHJvdmVtZW50IG9uIFJTRSBhbmQgYWRqdXN0ZWQgUiBzcXVhcmVkIHZhbHVlLgpMZXQncyBwbG90IHRoZSByZXNpZHVhbHM6CgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQojIyBwbG90dGluZyByZXNpZHVhbHMgcGxvdApwbG90KGZpdDIsIHdoaWNoID0xKQpgYGAKVGhpcyBwbG90IHNob3dzIHNvbWUgb2YgdGhlIG91dGxpZXJzIGx5aW5nIGZhciBhd2F5IGZyb20gdGhlIG1pZGRsZSBvZiB0aGUgZ3JhcGguCgpXZSB3aWxsIHRyeSBhIGRpZmZlcmVudCB0eXBlIG9mIHRyYW5zZm9ybWF0aW9uIG9uIGJvdGggcHJlZGljdG9ycyBhbmQgdGhlIHJlc3BvbnNlIHZhbHVlIGFuZCBzZWUgaG93IHRoZSBwZXJmb3JtYW5jZSBvZiBtb2RlbCBjaGFuZ2VzLiBJbiB0aGUgbmV4dCBtb2RlbCwgd2Ugd2lsbCB1c2UgdGhlIG5hdHVyYWwgbG9nIHRvIHRoZSBtcGcgdXNpbmcgbG9nKCkgYW5kIHNlZSB0aGUgY2hhbmdlIGluIHBlcmZvcm1hbmNlIG9mIHRoZSBtb2RlbC4KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KZml0MyA8LSBsbShsb2cobXBnKX53ZWlnaHQreWVhcitvcmlnaW4sZGF0YSA9IHRyYWluMSkKc3VtbWFyeShmaXQzKQpwbG90KGZpdDMsIHdoaWNoID0xKQpgYGAKQWZ0ZXIgc29tZSBjaGFuZ2VzIGluIHRoZSBtb2RlbCwgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSBtb2RlbCBpcyBpbmNyZWFzZWQuIFRoZSAgQWRqdXN0ZWQgUi1zcXVhcmVkIHJhaXNlZCB0byAwLjg3MjEgYW5kIEYtc3RhdGlzdGljIGlzIGluY3JlYXNlZCB0byA2NjguOC4gVGhlIHAtdmFsdWUgb2YgdGhlIHByZWRpY3RvcnMgaXMgc2lnbmlmaWNhbnQuCgpMZXQncyBtYWtlIGEgY2VydGFpbiBjaGFuZ2UgaW4gdGhpcyBtb2RlbC4gV2Ugd2lsbCB1c2UgdGhlIG5hdHVyYWwgbG9nIHRvIHRoZSB3ZWlnaHQgYW5kIG1wZy4KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KZml0NCA8LSBsbShsb2cobXBnKX5sb2cod2VpZ2h0KSt5ZWFyK29yaWdpbixkYXRhID0gYXV0b19kZikKc3VtbWFyeShmaXQ0KQpwbG90KGZpdDQsd2hpY2ggPSAxKQpgYGAKSW4gdGhpcyBtb2RlbCwgdGhlIEYtc3RhdGlzdGljcyBhbmQgQWRqdXN0ZWQgUi1zcXVhcmVkIGFyZSBpbXByb3ZlZC4gTW9zdCBvZiB0aGUgcHJlZGljdG9yJ3MgcC12YWx1ZSBpcyBzaWduaWZpY2FudC5UaGUgb3JpZ2luIHByZWRpY3RvciBzZWVtcyB0byBoYXZlIHdlYWsgcC12YWx1ZSB3aGljaCBtZWFucyB0aGF0IG9yaWdpbiBkb2Vzbid0IGhhdmUgc3Ryb25nIHJlbGF0aW9uc2hpcHMgd2l0aCB0aGUgbXBnIHdoaWxlIHRoZSBwcmVzZW5jZSBvZiBvdGhlciBwcmVkaWN0b3JzLiBTbywgd2Ugd2lsbCBleGNsdWRlIHRoZSBvcmlnaW4gYW5kIG1ha2UgYSBuZXcgbW9kZWwuCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmZpdDUgPC0gbG0obG9nKG1wZyl+bG9nKHdlaWdodCkreWVhcixkYXRhID0gYXV0b19kZikKc3VtbWFyeShmaXQ1KQpwbG90KGZpdDUsd2hpY2ggPSAxKQoKYGBgClRoZSBvdXRwdXQgb2YgdGhpcyBtb2RlbCBzaG93cyB0aGF0IHRoZSBGLXN0YXRpc3RpY3MgaXMgaW5jcmVhc2VkIHRvIDE0MzYgYW5kIHRoZSBBZGp1c3RlZCBSLXNxdWFyZWQgaXMgYWxzbyBpbmNyZWFzZWQuVGhlIHByZWRpY3RvciBoYXMgaGlnaGx5IHNpZ25pZmljYW50IHAgdmFsdWVzLiBUaGlzIG1vZGVsIGlzIGJldHRlciB0aGFuIHByZXZpb3VzIG1vZGVscy4KClRoZSBmaW5hbCByZWdyZXNzaW9uIGVxdWF0aW9uIGZvciBvdXIgbW9kZWwgaXM6CgokJCBsb2cobXBnKSA9IDguMDM5NSArIGxvZyh3ZWlnaHQpKiAtLjkzNDEgKyB5ZWFyICogLjAzMjggJCQgIAoKIyMgQWNjdXJhY3kKCldlIHdpbGwgdXNlIHRoZSB0ZXN0IGRhdGEgdG8gY2hlY2sgdGhlIGFjY3VyYWN5IG9mIG91ciBmaW5hbCBtb2RlbC4KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KcHJlZGljdGlvbnM8LXByZWRpY3QoZml0NSwgdGVzdDEpCm1zZSA8LSBtZWFuKCh0ZXN0MSRtcGcgLSBwcmVkaWN0aW9ucyleMikKcHJpbnQobXNlKQpzaWdtYShmaXQ1KS9tZWFuKHRlc3QxJG1wZykKYGBgCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQp0ZXN0MSRwcmVkaWN0ZWQ8LSBwcmVkaWN0KGZpdDUsdGVzdDEpCmFjdHVhbHNfcHJlZHMgPC0gZGF0YS5mcmFtZSh0ZXN0MSRtcGcsdGVzdDEkcHJlZGljdGVkKQpuYW1lcyhhY3R1YWxzX3ByZWRzKTwtIGMoIm1wZyIsInByZWRpY3RlZCIpCmNvcnJlbGF0aW9uX2FjY3VyYWN5IDwtIGNvcihhY3R1YWxzX3ByZWRzKQpjb3JyZWxhdGlvbl9hY2N1cmFjeQpgYGAKVGhlIGNvcnJlbGF0aW9uIG9mIHRoZSBtb2RlbHMgc2hvd3MgdGhhdCB0aGUgYWNjdXJhY3kgaXMgYXJvdW5kIDkyICUuTGV0cyBjaGVjayB0aGUgdHJ1ZSBtcGcgYW5kIHByZWRpY3RlZCBtcGcgZm9yIHRoZSB0ZXN0IGRhdGEuCgpgYGB7cn0KaGVhZChhY3R1YWxzX3ByZWRzKQoKYGBgCldvdyEgd2hhdCBoYXBwZW5lZD9XZSB1c2VkIGxvZyB0byB0aGUgcmVzcG9uc2UgdmFsdWUgaW4gb3VyIG1vZGVsIHdoaWNoIHByZWRpY3RlZCB0aGUgcmVzcG9uc2Ugd2l0aCBhIGxvZy4gSWYgd2UgdXNlICBsb2cgdG8gdGhlIG9yaWdpbmFsIG1wZyB3ZSBjYW4gcmVsYXRlIHRoaXMgcmVzdWx0LgoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KYWN0dWFsc19wcmVkcyRsb2dfbXBnIDwtIGxvZyhhY3R1YWxzX3ByZWRzJG1wZykKaGVhZChhY3R1YWxzX3ByZWRzKQpgYGAKCiMjIEZpbmFsbHkKPGNlbnRlcj4gPGltZyBzcmM9Imh0dHBzOi8vaS5pbWdmbGlwLmNvbS9zeTUwMS5qcGciPjwvY2VudGVyPgoKSW4gdGhpcyBibG9nLCB3ZSB1c2VkIE11bHRpcGxlIExpbmVhciBSZWdyZXNzaW9uIG1ldGhvZHMgdG8gZmluZCB0aGUgbXBnIG9mIHRoZSBjYXIuIFdlIGhhZCA4IGNvbHVtbnMgb3V0IG9mIHdoaWNoIDQgd2VyZSBjb2xsaW5lYXIgdG8gZWFjaCBvdGhlci4gd2UgZ290IHRoZSBiZXN0IG1vZGVsIHdpdGggb25seSB0d28gcHJlZGljdG9ycy4gCiQkIGxvZyhtcGcpID0gOC4wMzk1ICsgbG9nKHdlaWdodCkqIC0uOTM0MSArIHllYXIgKiAuMDMyOCAkJAoKIyMgUmVmZXJlbmNlOgoKKiAgW0lTTFIgQ2hhcHRlcjNdKGh0dHA6Ly93d3ctYmNmLnVzYy5lZHUvfmdhcmV0aC9JU0wvKQoqICBbUnB1Yl0oaHR0cHM6Ly9ycHVicy5jb20vRmVsaXBlUmVnby9NdWx0aXBsZUxpbmVhclJlZ3Jlc3Npb25JblJGaXJzdFN0ZXBzKQoqICBbTWFjaGluZUxlYXJuaW5nUGx1c10oaHR0cHM6Ly93d3cubWFjaGluZWxlYXJuaW5ncGx1cy5jb20vbWFjaGluZS1sZWFybmluZy9jb21wbGV0ZS1pbnRyb2R1Y3Rpb24tbGluZWFyLXJlZ3Jlc3Npb24tci8p