Question 4

Generate a simulated two-class data set with 100 observations and two features in which there is a visible but non-linear separation between the two classes. Show that in this setting, a support vector machine with a polynomial kernel (with degree greater than 1) or a radial kernel will outperform a support vector classifier on the training data. Which technique performs best on the test data? Make plots and report training and test error rates in order to back up your assertions.

Generate data and plot:

set.seed(1)
transl <- 3
X <- matrix(rnorm(100 * 2), ncol = 2)
X[1:30, ] <- X[1:30, ] + transl
X[31:60, ] <- X[31:60, ] - transl
y <- c(rep(0, 60), rep(1, 40))
dat <- data.frame(x = X, y = as.factor(y))
plot(X, col = y + 1)

Split to training and test set:

train <- sample(100, 80)
dat.train <- dat[train, ]
dat.test <- dat[-train, ]

Fit with a support vector classifier and describe the model:

library(e1071)
svm.lin <- svm(y ~ ., data = dat.train, kernel = 'linear', scale = FALSE)
plot(svm.lin, data = dat.train)

summary(svm.lin)

Call:
svm(formula = y ~ ., data = dat.train, kernel = "linear", scale = FALSE)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  linear 
       cost:  1 
      gamma:  0.5 

Number of Support Vectors:  62

 ( 30 32 )


Number of Classes:  2 

Levels: 
 0 1

Calculate the training error of the support vector classifier:

table(predict = svm.lin$fitted, truth = dat.train$y)
       truth
predict  0  1
      0 50 30
      1  0  0

The error rate: \(\frac{33}{47 + 33} = 41.25%\).

The support vector classifier marks all training points as class zero, which means this model is useless on this training set.

Fit with polynomial kernel and calculate the training error rate:

svm.poly <- svm(y ~ ., data = dat.train, kernel = 'polynomial', scale = FALSE)
plot(svm.poly, data = dat.train)

table(predict = svm.poly$fitted, truth = dat.train$y)
       truth
predict  0  1
      0 50 30
      1  0  0

There are 2 correct prediction.

Fit with radial kernel and calculate the traing error rate:

svm.rad <- svm(y ~ ., data = dat.train, kernel = 'radial', scale = FALSE)
plot(svm.rad, data = dat.train)

table(predict = svm.rad$fitted, truth = dat.train$y)
       truth
predict  0  1
      0 49  0
      1  1 30

The error rate is \(\frac{1}{1 + 46 + 33} = 1.25%\), which much more less than the other 2 kernels.

Compare the test errors of the 3 kernels:

lin.pred <- predict(svm.lin, dat.test)
table(predict = lin.pred, truth = dat.test$y)
       truth
predict  0  1
      0 10 10
      1  0  0
poly.pred <- predict(svm.poly, dat.test)
table(predict = poly.pred, truth = dat.test$y)
       truth
predict  0  1
      0 10 10
      1  0  0
rad.pred <- predict(svm.rad, dat.test)
table(predict = rad.pred, truth = dat.test$y)
       truth
predict  0  1
      0 10  0
      1  0 10

The test error rate for linear, polynomial (with default degree: 3) and radial kernel are: 35%, 35% and 0.

Question 5

We have seen that we can fit an SVM with a non-linear kernel in order to perform classification using a non-linear decision boundary. We will now see that we can also obtain a non-linear decision boundary by performing logistic regression using non-linear transformations of the features.

  1. Generate a data set with n = 500 and p = 2, such that the observations belong to two classes with a quadratic decision boundary between them:
set.seed(1)
x1 <- runif(500) - 0.5
x2 <- runif(500) - 0.5
y <- as.integer(x1 ^ 2 - x2 ^ 2 > 0)

两类的分界线是 \(x_1^2 - x_2^2 = 0\),也就是 \(x = \pm y\),4个象限的角平分线,边界是直线而不是二次曲线。

  1. Plot the observations, colored according to their class labels. Your plot should display X 1 on the x-axis, and X 2 on the y-axis:
plot(x1[y == 0], x2[y == 0], col = "red", xlab = "X1", ylab = "X2")
points(x1[y == 1], x2[y == 1], col = "blue")

  1. Fit a logistic regression model to the data, using \(X_1\) and \(X_2\) as predictors.
dat <- data.frame(x1 = x1, x2 = x2, y = as.factor(y))
lr.fit <- glm(y ~ ., data = dat, family = 'binomial')
  1. Apply this model to the training data in order to obtain a predicted class label for each training observation. Plot the observations, colored according to the predicted class labels. The decision boundary should be linear.
lr.prob <- predict(lr.fit, newdata = dat, type = 'response')
lr.pred <- ifelse(lr.prob > 0.5, 1, 0)
plot(dat$x1, dat$x2, col = lr.pred + 2)

边界是线性的,但即使在训练集上,预测结果误差仍然非常大,表明线性逻辑回归不适于这个数据集。

  1. Now fit a logistic regression model to the data using non-linear functions of \(X_1\) and \(X_2\) as predictors (e.g. \(X_1^2\) , \(X_1 \times X_2\), \(log(X_2)\), and so forth).
lr.nl <- glm(y ~ poly(x1, 2) + poly(x2, 2), data = dat, family = 'binomial')
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
summary(lr.nl)

Call:
glm(formula = y ~ poly(x1, 2) + poly(x2, 2), family = "binomial", 
    data = dat)

Deviance Residuals: 
       Min          1Q      Median          3Q         Max  
-1.079e-03  -2.000e-08  -2.000e-08   2.000e-08   1.297e-03  

Coefficients:
              Estimate Std. Error z value Pr(>|z|)
(Intercept)     -94.48    2963.78  -0.032    0.975
poly(x1, 2)1   3442.52  104411.28   0.033    0.974
poly(x1, 2)2  30110.74  858421.66   0.035    0.972
poly(x2, 2)1    162.82   26961.99   0.006    0.995
poly(x2, 2)2 -31383.76  895267.48  -0.035    0.972

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 6.9218e+02  on 499  degrees of freedom
Residual deviance: 4.2881e-06  on 495  degrees of freedom
AIC: 10

Number of Fisher Scoring iterations: 25
  1. Apply this model to the training data in order to obtain a predicted class label for each training observation. Plot the observations, colored according to the predicted class labels. The decision boundary should be obviously non-linear. If it is not, then repeat (a)-(e) until you come up with an example in which the predicted class labels are obviously non-linear.
lr.prob.nl <- predict(lr.nl, newdata = dat, type = 'response')
lr.pred.nl <- ifelse(lr.prob.nl > 0.5, 1, 0)
plot(dat$x1, dat$x2, col = lr.pred.nl + 2)

The predictions are much better than linear model.

  1. Fit a support vector classifier to the data with \(X_1\) and \(X_2\) as predictors. Obtain a class prediction for each training observation. Plot the observations, colored according to the predicted class labels.
svm.lin <- svm(y ~ ., data = dat, kernel = 'linear', cost = 0.01)
plot(svm.lin, dat)

  1. Fit a SVM using a non-linear kernel to the data. Obtain a class prediction for each training observation. Plot the observations, colored according to the predicted class labels.
svm.nl <- svm(y ~ ., data = dat, kernel = 'radial', gamma = 1)
plot(svm.nl, data = dat)

  1. Comment on your results.

线性逻辑回归处理非线性边界效果很差,SVM线性核使用小 cost 时效果尚可,非线性逻辑回归和SVM处理非线性边界效果都很好。

Question 6

At the end of Section 9.6.1, it is claimed that in the case of data that is just barely linearly separable, a support vector classifier with a small value of cost that misclassifies a couple of training observations may perform better on test data than one with a huge value of cost that does not misclassify any training observations. You will now investigate this claim.

6a

Generate two-class data with p = 2 in such a way that the classes are just barely linearly separable.

set.seed(1)
obs = 1000
x1 <- runif(obs, min = -4, max = 4)
x2 <- runif(obs, min = -1, max = 16)
y <- ifelse(x2 > x1 ^ 2, 0, 1)
dat <- data.frame(x1 = x1, x2 = x2, y = as.factor(y))
train <- sample(obs, obs/2)
dat.train <- dat[train, ]
dat.test <- dat[-train, ]
par(mfrow = c(1,2))
plot(dat.train$x1, dat.train$x2, col = as.integer(dat.train$y) + 1, main = 'training set')
plot(dat.test$x1, dat.test$x2, col = as.integer(dat.test$y) + 1, main = 'test set')

6b

Compute the cross-validation error rates for support vector classifiers with a range of cost values. How many training errors are misclassified for each value of cost considered, and how does this relate to the cross-validation errors obtained?

set.seed(1)
cost.grid <- c(0.001, 0.01, 0.1, 1, 5, 10, 100, 10000)
tune.out <- tune(svm, y ~., data = dat.train, kernel = 'linear', ranges = list(cost = cost.grid))

WARNING: reaching max number of iterations
summary(tune.out)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:
 cost
  0.1

- best performance: 0.24 

- Detailed performance results:
   cost error dispersion
1 1e-03 0.370 0.05517648
2 1e-02 0.248 0.05977736
3 1e-01 0.240 0.05416026
4 1e+00 0.244 0.05641119
5 5e+00 0.244 0.05641119
6 1e+01 0.244 0.05641119
7 1e+02 0.244 0.05641119
8 1e+04 0.270 0.06749486

Training errors of the models with different cost value:

err.rate.train <- rep(NA, length(cost.grid))
for (cost in cost.grid) {
  svm.fit <- svm(y ~ ., data = dat.train, kernel = 'linear', cost = cost)
  plot(svm.fit, data = dat.train)
  res <- table(prediction = predict(svm.fit, newdata = dat.train), truth = dat.train$y)
  err.rate.train[match(cost, cost.grid)] <- (res[2,1] + res[1,2]) / sum(res)
}

err.rate.train
[1] 0.370 0.240 0.246 0.246 0.244 0.244 0.244 0.244
paste('The cost', cost.grid[which.min(err.rate.train)], 'has the minimum training error:', min(err.rate.train))
[1] "The cost 0.01 has the minimum training error: 0.24"

最优结果与 cross-validation 结果不一致。 随着 cost 变大,training error 应该降低,但这里有升有降,原因尚不清楚。

6c

Generate an appropriate test data set, and compute the test errors corresponding to each of the values of cost considered. Which value of cost leads to the fewest test errors, and how does this compare to the values of cost that yield the fewest training errors and the fewest cross-validation errors?

err.rate.test <- rep(NA, length(cost.grid))
for (cost in cost.grid) {
  svm.fit <- svm(y ~ ., data = dat.train, kernel = 'linear', cost = cost)
  res <- table(prediction = predict(svm.fit, newdata = dat.test), truth = dat.test$y)
  err.rate.test[match(cost, cost.grid)] <- (res[2,1] + res[1,2]) / sum(res)
}
err.rate.test
[1] 0.384 0.232 0.230 0.230 0.232 0.232 0.232 0.232
paste('The cost', cost.grid[which.min(err.rate.test)], 'has the minimum test error:', min(err.rate.test))
[1] "The cost 0.1 has the minimum test error: 0.23"

最优结果与 cross-validation 结果一致,都是 cost = 0.1 时最优。

6d

Discuss your results.

线性 kernel 拟合非线性边界时,cost 较小时 training error 和 test error 都比较小,但如果 cost 太小,由于 margin 过宽导致失去分类作用,见 cost = 0.001 时的模型图。

总体来说,这种情况下无论如何调整 cost 错误率都比较高,所以当使用不同 cost 后错误率无明显变化一直很高,可能是 kernel 选择不当导致的。

Question 7

In this problem, you will use support vector approaches in order to predict whether a given car gets high or low gas mileage based on the Auto data set.

7a

Create a binary variable that takes on a 1 for cars with gas mileage above the median, and a 0 for cars with gas mileage below the median.

library(ISLR)
mileage.median <- median(Auto$mpg)
Auto$mb <- ifelse(Auto$mpg > mileage.median, 1, 0)

7b

Fit a support vector classifier to the data with various values of cost, in order to predict whether a car gets high or low gas mileage. Report the cross-validation errors associated with different values of this parameter. Comment on your results.

cost.grid <- c(0.001, 0.1, 1, 100)
set.seed(1)
tune.res <- tune(svm, mb ~ . - mpg, data = Auto, kernel = 'linear', ranges = list(cost = cost.grid))
summary(tune.res)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:
 cost
    1

- best performance: 0.09129186 

- Detailed performance results:
   cost      error dispersion
1 1e-03 0.10861464 0.02815681
2 1e-01 0.10078133 0.04430714
3 1e+00 0.09129186 0.03486337
4 1e+02 0.11413712 0.03453277

cost = 1 has the lowest error rate.

7c

Now repeat (b), this time using SVMs with radial and polynomial basis kernels, with different values of gamma and degree and cost. Comment on your results.

LS0tCnRpdGxlOiAiQXBwbGllZCBFeGVyY2lzZXMgb2YgQ2hhcHRlciA5IgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgojIFF1ZXN0aW9uIDQKCkdlbmVyYXRlIGEgc2ltdWxhdGVkIHR3by1jbGFzcyBkYXRhIHNldCB3aXRoIDEwMCBvYnNlcnZhdGlvbnMgYW5kIHR3byBmZWF0dXJlcyBpbiB3aGljaCB0aGVyZSBpcyBhIHZpc2libGUgYnV0IG5vbi1saW5lYXIgc2VwYXJhdGlvbiBiZXR3ZWVuIHRoZSB0d28gY2xhc3Nlcy4gU2hvdyB0aGF0IGluIHRoaXMgc2V0dGluZywgYSBzdXBwb3J0IHZlY3RvciBtYWNoaW5lIHdpdGggYSBwb2x5bm9taWFsIGtlcm5lbCAod2l0aCBkZWdyZWUgZ3JlYXRlciB0aGFuIDEpIG9yIGEgcmFkaWFsIGtlcm5lbCB3aWxsIG91dHBlcmZvcm0gYSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIG9uIHRoZSB0cmFpbmluZyBkYXRhLiBXaGljaCB0ZWNobmlxdWUgcGVyZm9ybXMgYmVzdCBvbiB0aGUgdGVzdCBkYXRhPyBNYWtlIHBsb3RzIGFuZCByZXBvcnQgdHJhaW5pbmcgYW5kIHRlc3QgZXJyb3IgcmF0ZXMgaW4gb3JkZXIgdG8gYmFjayB1cCB5b3VyIGFzc2VydGlvbnMuCgpHZW5lcmF0ZSBkYXRhIGFuZCBwbG90OgpgYGB7cn0Kc2V0LnNlZWQoMSkKdHJhbnNsIDwtIDMKWCA8LSBtYXRyaXgocm5vcm0oMTAwICogMiksIG5jb2wgPSAyKQpYWzE6MzAsIF0gPC0gWFsxOjMwLCBdICsgdHJhbnNsClhbMzE6NjAsIF0gPC0gWFszMTo2MCwgXSAtIHRyYW5zbAp5IDwtIGMocmVwKDAsIDYwKSwgcmVwKDEsIDQwKSkKZGF0IDwtIGRhdGEuZnJhbWUoeCA9IFgsIHkgPSBhcy5mYWN0b3IoeSkpCnBsb3QoWCwgY29sID0geSArIDEpCmBgYAoKU3BsaXQgdG8gdHJhaW5pbmcgYW5kIHRlc3Qgc2V0OgpgYGB7cn0KdHJhaW4gPC0gc2FtcGxlKDEwMCwgODApCmRhdC50cmFpbiA8LSBkYXRbdHJhaW4sIF0KZGF0LnRlc3QgPC0gZGF0Wy10cmFpbiwgXQpgYGAKCkZpdCB3aXRoIGEgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciBhbmQgZGVzY3JpYmUgdGhlIG1vZGVsOgpgYGB7cn0KbGlicmFyeShlMTA3MSkKc3ZtLmxpbiA8LSBzdm0oeSB+IC4sIGRhdGEgPSBkYXQudHJhaW4sIGtlcm5lbCA9ICdsaW5lYXInLCBzY2FsZSA9IEZBTFNFKQpwbG90KHN2bS5saW4sIGRhdGEgPSBkYXQudHJhaW4pCnN1bW1hcnkoc3ZtLmxpbikKYGBgCgpDYWxjdWxhdGUgdGhlIHRyYWluaW5nIGVycm9yIG9mIHRoZSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyOgpgYGB7cn0KdGFibGUocHJlZGljdCA9IHN2bS5saW4kZml0dGVkLCB0cnV0aCA9IGRhdC50cmFpbiR5KQpgYGAKClRoZSBlcnJvciByYXRlOiAkXGZyYWN7MzN9ezQ3ICsgMzN9ID0gNDEuMjUlJC4KClRoZSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIG1hcmtzIGFsbCB0cmFpbmluZyBwb2ludHMgYXMgY2xhc3MgKnplcm8qLCB3aGljaCBtZWFucyB0aGlzIG1vZGVsIGlzIHVzZWxlc3Mgb24gdGhpcyB0cmFpbmluZyBzZXQuCgpGaXQgd2l0aCBwb2x5bm9taWFsIGtlcm5lbCBhbmQgY2FsY3VsYXRlIHRoZSB0cmFpbmluZyBlcnJvciByYXRlOgpgYGB7cn0Kc3ZtLnBvbHkgPC0gc3ZtKHkgfiAuLCBkYXRhID0gZGF0LnRyYWluLCBrZXJuZWwgPSAncG9seW5vbWlhbCcsIHNjYWxlID0gRkFMU0UpCnBsb3Qoc3ZtLnBvbHksIGRhdGEgPSBkYXQudHJhaW4pCnRhYmxlKHByZWRpY3QgPSBzdm0ucG9seSRmaXR0ZWQsIHRydXRoID0gZGF0LnRyYWluJHkpCmBgYAoKVGhlcmUgYXJlIDIgY29ycmVjdCBwcmVkaWN0aW9uLgoKRml0IHdpdGggcmFkaWFsIGtlcm5lbCBhbmQgY2FsY3VsYXRlIHRoZSB0cmFpbmcgZXJyb3IgcmF0ZToKYGBge3J9CnN2bS5yYWQgPC0gc3ZtKHkgfiAuLCBkYXRhID0gZGF0LnRyYWluLCBrZXJuZWwgPSAncmFkaWFsJywgc2NhbGUgPSBGQUxTRSkKcGxvdChzdm0ucmFkLCBkYXRhID0gZGF0LnRyYWluKQp0YWJsZShwcmVkaWN0ID0gc3ZtLnJhZCRmaXR0ZWQsIHRydXRoID0gZGF0LnRyYWluJHkpCmBgYAoKVGhlIGVycm9yIHJhdGUgaXMgJFxmcmFjezF9ezEgKyA0NiArIDMzfSA9IDEuMjUlJCwgd2hpY2ggbXVjaCBtb3JlIGxlc3MgdGhhbiB0aGUgb3RoZXIgMiBrZXJuZWxzLgoKQ29tcGFyZSB0aGUgdGVzdCBlcnJvcnMgb2YgdGhlIDMga2VybmVsczoKYGBge3J9Cmxpbi5wcmVkIDwtIHByZWRpY3Qoc3ZtLmxpbiwgZGF0LnRlc3QpCnRhYmxlKHByZWRpY3QgPSBsaW4ucHJlZCwgdHJ1dGggPSBkYXQudGVzdCR5KQpwb2x5LnByZWQgPC0gcHJlZGljdChzdm0ucG9seSwgZGF0LnRlc3QpCnRhYmxlKHByZWRpY3QgPSBwb2x5LnByZWQsIHRydXRoID0gZGF0LnRlc3QkeSkKcmFkLnByZWQgPC0gcHJlZGljdChzdm0ucmFkLCBkYXQudGVzdCkKdGFibGUocHJlZGljdCA9IHJhZC5wcmVkLCB0cnV0aCA9IGRhdC50ZXN0JHkpCmBgYAoKVGhlIHRlc3QgZXJyb3IgcmF0ZSBmb3IgbGluZWFyLCBwb2x5bm9taWFsICh3aXRoIGRlZmF1bHQgZGVncmVlOiAzKSBhbmQgcmFkaWFsIGtlcm5lbCBhcmU6IDM1JSwgMzUlIGFuZCAwLgoKIyBRdWVzdGlvbiA1CgpXZSBoYXZlIHNlZW4gdGhhdCB3ZSBjYW4gZml0IGFuIFNWTSB3aXRoIGEgbm9uLWxpbmVhciBrZXJuZWwgaW4gb3JkZXIgdG8gcGVyZm9ybSBjbGFzc2lmaWNhdGlvbiB1c2luZyBhIG5vbi1saW5lYXIgZGVjaXNpb24gYm91bmRhcnkuIFdlIHdpbGwgbm93IHNlZSB0aGF0IHdlIGNhbiBhbHNvIG9idGFpbiBhIG5vbi1saW5lYXIgZGVjaXNpb24gYm91bmRhcnkgYnkgcGVyZm9ybWluZyBsb2dpc3RpYyByZWdyZXNzaW9uIHVzaW5nIG5vbi1saW5lYXIgdHJhbnNmb3JtYXRpb25zIG9mIHRoZSBmZWF0dXJlcy4KCihhKSBHZW5lcmF0ZSBhIGRhdGEgc2V0IHdpdGggbiA9IDUwMCBhbmQgcCA9IDIsIHN1Y2ggdGhhdCB0aGUgb2JzZXJ2YXRpb25zIGJlbG9uZyB0byB0d28gY2xhc3NlcyB3aXRoIGEgcXVhZHJhdGljIGRlY2lzaW9uIGJvdW5kYXJ5IGJldHdlZW4gdGhlbToKYGBge3J9CnNldC5zZWVkKDEpCngxIDwtIHJ1bmlmKDUwMCkgLSAwLjUKeDIgPC0gcnVuaWYoNTAwKSAtIDAuNQp5IDwtIGFzLmludGVnZXIoeDEgXiAyIC0geDIgXiAyID4gMCkKYGBgCgrkuKTnsbvnmoTliIbnlYznur/mmK8gJHhfMV4yIC0geF8yXjIgPSAwJO+8jOS5n+WwseaYryAkeCA9IFxwbSB5JO+8jDTkuKrosaHpmZDnmoTop5LlubPliIbnur/vvIzovrnnlYzmmK/nm7Tnur/ogIzkuI3mmK/kuozmrKHmm7Lnur/jgIIKCihiKSBQbG90IHRoZSBvYnNlcnZhdGlvbnMsIGNvbG9yZWQgYWNjb3JkaW5nIHRvIHRoZWlyIGNsYXNzIGxhYmVscy4gWW91ciBwbG90IHNob3VsZCBkaXNwbGF5IFggMSBvbiB0aGUgeC1heGlzLCBhbmQgWCAyIG9uIHRoZSB5LWF4aXM6CmBgYHtyfQpwbG90KHgxW3kgPT0gMF0sIHgyW3kgPT0gMF0sIGNvbCA9ICJyZWQiLCB4bGFiID0gIlgxIiwgeWxhYiA9ICJYMiIpCnBvaW50cyh4MVt5ID09IDFdLCB4Mlt5ID09IDFdLCBjb2wgPSAiYmx1ZSIpCmBgYAoKKGMpIEZpdCBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgdG8gdGhlIGRhdGEsIHVzaW5nICRYXzEkIGFuZCAkWF8yJCBhcyBwcmVkaWN0b3JzLgoKYGBge3J9CmRhdCA8LSBkYXRhLmZyYW1lKHgxID0geDEsIHgyID0geDIsIHkgPSBhcy5mYWN0b3IoeSkpCmxyLmZpdCA8LSBnbG0oeSB+IC4sIGRhdGEgPSBkYXQsIGZhbWlseSA9ICdiaW5vbWlhbCcpCmBgYAoKKGQpIEFwcGx5IHRoaXMgbW9kZWwgdG8gdGhlICp0cmFpbmluZyBkYXRhKiBpbiBvcmRlciB0byBvYnRhaW4gYSBwcmVkaWN0ZWQgY2xhc3MgbGFiZWwgZm9yIGVhY2ggdHJhaW5pbmcgb2JzZXJ2YXRpb24uIFBsb3QgdGhlIG9ic2VydmF0aW9ucywgY29sb3JlZCBhY2NvcmRpbmcgdG8gdGhlIHByZWRpY3RlZCBjbGFzcyBsYWJlbHMuIFRoZSBkZWNpc2lvbiBib3VuZGFyeSBzaG91bGQgYmUgbGluZWFyLgoKYGBge3J9CmxyLnByb2IgPC0gcHJlZGljdChsci5maXQsIG5ld2RhdGEgPSBkYXQsIHR5cGUgPSAncmVzcG9uc2UnKQpsci5wcmVkIDwtIGlmZWxzZShsci5wcm9iID4gMC41LCAxLCAwKQpwbG90KGRhdCR4MSwgZGF0JHgyLCBjb2wgPSBsci5wcmVkICsgMikKYGBgCgrovrnnlYzmmK/nur/mgKfnmoTvvIzkvYbljbPkvb/lnKjorq3nu4Ppm4bkuIrvvIzpooTmtYvnu5Pmnpzor6/lt67ku43nhLbpnZ7luLjlpKfvvIzooajmmI7nur/mgKfpgLvovpHlm57lvZLkuI3pgILkuo7ov5nkuKrmlbDmja7pm4bjgIIKCihlKSBOb3cg76yBdCBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgdG8gdGhlIGRhdGEgdXNpbmcgbm9uLWxpbmVhciBmdW5jdGlvbnMgb2YgJFhfMSQgYW5kICRYXzIkIGFzIHByZWRpY3RvcnMgKGUuZy4gJFhfMV4yJCAsICRYXzEgXHRpbWVzIFhfMiQsICRsb2coWF8yKSQsIGFuZCBzbyBmb3J0aCkuCgpgYGB7cn0KbHIubmwgPC0gZ2xtKHkgfiBwb2x5KHgxLCAyKSArIHBvbHkoeDIsIDIpLCBkYXRhID0gZGF0LCBmYW1pbHkgPSAnYmlub21pYWwnKQpzdW1tYXJ5KGxyLm5sKQpgYGAKCihmKSBBcHBseSB0aGlzIG1vZGVsIHRvIHRoZSB0cmFpbmluZyBkYXRhIGluIG9yZGVyIHRvIG9idGFpbiBhIHByZWRpY3RlZCBjbGFzcyBsYWJlbCBmb3IgZWFjaCB0cmFpbmluZyBvYnNlcnZhdGlvbi4gUGxvdCB0aGUgb2JzZXJ2YXRpb25zLCBjb2xvcmVkIGFjY29yZGluZyB0byB0aGUgcHJlZGljdGVkIGNsYXNzIGxhYmVscy4gVGhlIGRlY2lzaW9uIGJvdW5kYXJ5IHNob3VsZCBiZSBvYnZpb3VzbHkgbm9uLWxpbmVhci4gSWYgaXQgaXMgbm90LCB0aGVuIHJlcGVhdCAoYSktKGUpIHVudGlsIHlvdSBjb21lIHVwIHdpdGggYW4gZXhhbXBsZSBpbiB3aGljaCB0aGUgcHJlZGljdGVkIGNsYXNzIGxhYmVscyBhcmUgb2J2aW91c2x5IG5vbi1saW5lYXIuCgpgYGB7cn0KbHIucHJvYi5ubCA8LSBwcmVkaWN0KGxyLm5sLCBuZXdkYXRhID0gZGF0LCB0eXBlID0gJ3Jlc3BvbnNlJykKbHIucHJlZC5ubCA8LSBpZmVsc2UobHIucHJvYi5ubCA+IDAuNSwgMSwgMCkKcGxvdChkYXQkeDEsIGRhdCR4MiwgY29sID0gbHIucHJlZC5ubCArIDIpCmBgYAoKVGhlIHByZWRpY3Rpb25zIGFyZSBtdWNoIGJldHRlciB0aGFuIGxpbmVhciBtb2RlbC4KCihnKSBGaXQgYSBzdXBwb3J0IHZlY3RvciBjbGFzc2nvrIFlciB0byB0aGUgZGF0YSB3aXRoICRYXzEkIGFuZCAkWF8yJCBhcyBwcmVkaWN0b3JzLiBPYnRhaW4gYSBjbGFzcyBwcmVkaWN0aW9uIGZvciBlYWNoIHRyYWluaW5nIG9ic2VydmF0aW9uLiBQbG90IHRoZSBvYnNlcnZhdGlvbnMsIGNvbG9yZWQgYWNjb3JkaW5nIHRvIHRoZSBwcmVkaWN0ZWQgY2xhc3MgbGFiZWxzLgoKYGBge3J9CnN2bS5saW4gPC0gc3ZtKHkgfiAuLCBkYXRhID0gZGF0LCBrZXJuZWwgPSAnbGluZWFyJywgY29zdCA9IDAuMDEpCnBsb3Qoc3ZtLmxpbiwgZGF0KQpgYGAKCgooaCkgRml0IGEgU1ZNIHVzaW5nIGEgbm9uLWxpbmVhciBrZXJuZWwgdG8gdGhlIGRhdGEuIE9idGFpbiBhIGNsYXNzIHByZWRpY3Rpb24gZm9yIGVhY2ggdHJhaW5pbmcgb2JzZXJ2YXRpb24uIFBsb3QgdGhlIG9ic2VydmF0aW9ucywgY29sb3JlZCBhY2NvcmRpbmcgdG8gdGhlIHByZWRpY3RlZCBjbGFzcyBsYWJlbHMuCgpgYGB7cn0Kc3ZtLm5sIDwtIHN2bSh5IH4gLiwgZGF0YSA9IGRhdCwga2VybmVsID0gJ3JhZGlhbCcsIGdhbW1hID0gMSkKcGxvdChzdm0ubmwsIGRhdGEgPSBkYXQpCmBgYAoKKGkpIENvbW1lbnQgb24geW91ciByZXN1bHRzLgoK57q/5oCn6YC76L6R5Zue5b2S5aSE55CG6Z2e57q/5oCn6L6555WM5pWI5p6c5b6I5beu77yMU1ZN57q/5oCn5qC45L2/55So5bCPIGNvc3Qg5pe25pWI5p6c5bCa5Y+v77yM6Z2e57q/5oCn6YC76L6R5Zue5b2S5ZKMU1ZN5aSE55CG6Z2e57q/5oCn6L6555WM5pWI5p6c6YO95b6I5aW944CCCgojIFF1ZXN0aW9uIDYKCkF0IHRoZSBlbmQgb2YgU2VjdGlvbiA5LjYuMSwgaXQgaXMgY2xhaW1lZCB0aGF0IGluIHRoZSBjYXNlIG9mIGRhdGEgdGhhdCBpcyBqdXN0IGJhcmVseSBsaW5lYXJseSBzZXBhcmFibGUsIGEgc3VwcG9ydCB2ZWN0b3IgY2xhc3Np76yBZXIgd2l0aCBhIHNtYWxsIHZhbHVlIG9mIGNvc3QgdGhhdCBtaXNjbGFzc2nvrIFlcyBhIGNvdXBsZSBvZiB0cmFpbmluZyBvYnNlcnZhdGlvbnMgbWF5IHBlcmZvcm0gYmV0dGVyIG9uIHRlc3QgZGF0YSB0aGFuIG9uZSB3aXRoIGEgaHVnZSB2YWx1ZSBvZiBjb3N0IHRoYXQgZG9lcyBub3QgbWlzY2xhc3NpZnkgYW55IHRyYWluaW5nIG9ic2VydmF0aW9ucy4gWW91IHdpbGwgbm93IGludmVzdGlnYXRlIHRoaXMgY2xhaW0uCgojIyA2YQoKR2VuZXJhdGUgdHdvLWNsYXNzIGRhdGEgd2l0aCBwID0gMiBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIGNsYXNzZXMgYXJlIGp1c3QgYmFyZWx5IGxpbmVhcmx5IHNlcGFyYWJsZS4KCmBgYHtyfQpzZXQuc2VlZCgxKQpvYnMgPSAxMDAwCngxIDwtIHJ1bmlmKG9icywgbWluID0gLTQsIG1heCA9IDQpCngyIDwtIHJ1bmlmKG9icywgbWluID0gLTEsIG1heCA9IDE2KQp5IDwtIGlmZWxzZSh4MiA+IHgxIF4gMiwgMCwgMSkKZGF0IDwtIGRhdGEuZnJhbWUoeDEgPSB4MSwgeDIgPSB4MiwgeSA9IGFzLmZhY3Rvcih5KSkKdHJhaW4gPC0gc2FtcGxlKG9icywgb2JzLzIpCmRhdC50cmFpbiA8LSBkYXRbdHJhaW4sIF0KZGF0LnRlc3QgPC0gZGF0Wy10cmFpbiwgXQpwYXIobWZyb3cgPSBjKDEsMikpCnBsb3QoZGF0LnRyYWluJHgxLCBkYXQudHJhaW4keDIsIGNvbCA9IGFzLmludGVnZXIoZGF0LnRyYWluJHkpICsgMSwgbWFpbiA9ICd0cmFpbmluZyBzZXQnKQpwbG90KGRhdC50ZXN0JHgxLCBkYXQudGVzdCR4MiwgY29sID0gYXMuaW50ZWdlcihkYXQudGVzdCR5KSArIDEsIG1haW4gPSAndGVzdCBzZXQnKQpgYGAKCiMjIDZiCgpDb21wdXRlIHRoZSBjcm9zcy12YWxpZGF0aW9uIGVycm9yIHJhdGVzIGZvciBzdXBwb3J0IHZlY3RvciBjbGFzc2nvrIFlcnMgd2l0aCBhIHJhbmdlIG9mIGNvc3QgdmFsdWVzLiBIb3cgbWFueSB0cmFpbmluZyBlcnJvcnMgYXJlIG1pc2NsYXNzae+sgWVkIGZvciBlYWNoIHZhbHVlIG9mIGNvc3QgY29uc2lkZXJlZCwgYW5kIGhvdyBkb2VzIHRoaXMgcmVsYXRlIHRvIHRoZSBjcm9zcy12YWxpZGF0aW9uIGVycm9ycyBvYnRhaW5lZD8KCmBgYHtyfQpzZXQuc2VlZCgxKQpjb3N0LmdyaWQgPC0gYygwLjAwMSwgMC4wMSwgMC4xLCAxLCA1LCAxMCwgMTAwLCAxMDAwMCkKdHVuZS5vdXQgPC0gdHVuZShzdm0sIHkgfi4sIGRhdGEgPSBkYXQudHJhaW4sIGtlcm5lbCA9ICdsaW5lYXInLCByYW5nZXMgPSBsaXN0KGNvc3QgPSBjb3N0LmdyaWQpKQpzdW1tYXJ5KHR1bmUub3V0KQpgYGAKClRyYWluaW5nIGVycm9ycyBvZiB0aGUgbW9kZWxzIHdpdGggZGlmZmVyZW50ICpjb3N0KiB2YWx1ZToKYGBge3J9CmVyci5yYXRlLnRyYWluIDwtIHJlcChOQSwgbGVuZ3RoKGNvc3QuZ3JpZCkpCmZvciAoY29zdCBpbiBjb3N0LmdyaWQpIHsKICBzdm0uZml0IDwtIHN2bSh5IH4gLiwgZGF0YSA9IGRhdC50cmFpbiwga2VybmVsID0gJ2xpbmVhcicsIGNvc3QgPSBjb3N0KQogIHBsb3Qoc3ZtLmZpdCwgZGF0YSA9IGRhdC50cmFpbikKICByZXMgPC0gdGFibGUocHJlZGljdGlvbiA9IHByZWRpY3Qoc3ZtLmZpdCwgbmV3ZGF0YSA9IGRhdC50cmFpbiksIHRydXRoID0gZGF0LnRyYWluJHkpCiAgZXJyLnJhdGUudHJhaW5bbWF0Y2goY29zdCwgY29zdC5ncmlkKV0gPC0gKHJlc1syLDFdICsgcmVzWzEsMl0pIC8gc3VtKHJlcykKfQplcnIucmF0ZS50cmFpbgpwYXN0ZSgnVGhlIGNvc3QnLCBjb3N0LmdyaWRbd2hpY2gubWluKGVyci5yYXRlLnRyYWluKV0sICdoYXMgdGhlIG1pbmltdW0gdHJhaW5pbmcgZXJyb3I6JywgbWluKGVyci5yYXRlLnRyYWluKSkKYGBgCgrmnIDkvJjnu5PmnpzkuI4gY3Jvc3MtdmFsaWRhdGlvbiDnu5PmnpzkuI3kuIDoh7TjgIIK6ZqP552AICpjb3N0KiDlj5jlpKfvvIx0cmFpbmluZyBlcnJvciDlupTor6XpmY3kvY7vvIzkvYbov5nph4zmnInljYfmnInpmY3vvIzljp/lm6DlsJrkuI3muIXmpZrjgIIKCiMjIDZjCgpHZW5lcmF0ZSBhbiBhcHByb3ByaWF0ZSB0ZXN0IGRhdGEgc2V0LCBhbmQgY29tcHV0ZSB0aGUgdGVzdCBlcnJvcnMgY29ycmVzcG9uZGluZyB0byBlYWNoIG9mIHRoZSB2YWx1ZXMgb2YgY29zdCBjb25zaWRlcmVkLiBXaGljaCB2YWx1ZSBvZiBjb3N0IGxlYWRzIHRvIHRoZSBmZXdlc3QgdGVzdCBlcnJvcnMsIGFuZCBob3cgZG9lcyB0aGlzIGNvbXBhcmUgdG8gdGhlIHZhbHVlcyBvZiBjb3N0IHRoYXQgeWllbGQgdGhlIGZld2VzdCB0cmFpbmluZyBlcnJvcnMgYW5kIHRoZSBmZXdlc3QgY3Jvc3MtdmFsaWRhdGlvbiBlcnJvcnM/CgpgYGB7cn0KZXJyLnJhdGUudGVzdCA8LSByZXAoTkEsIGxlbmd0aChjb3N0LmdyaWQpKQpmb3IgKGNvc3QgaW4gY29zdC5ncmlkKSB7CiAgc3ZtLmZpdCA8LSBzdm0oeSB+IC4sIGRhdGEgPSBkYXQudHJhaW4sIGtlcm5lbCA9ICdsaW5lYXInLCBjb3N0ID0gY29zdCkKICByZXMgPC0gdGFibGUocHJlZGljdGlvbiA9IHByZWRpY3Qoc3ZtLmZpdCwgbmV3ZGF0YSA9IGRhdC50ZXN0KSwgdHJ1dGggPSBkYXQudGVzdCR5KQogIGVyci5yYXRlLnRlc3RbbWF0Y2goY29zdCwgY29zdC5ncmlkKV0gPC0gKHJlc1syLDFdICsgcmVzWzEsMl0pIC8gc3VtKHJlcykKfQplcnIucmF0ZS50ZXN0CnBhc3RlKCdUaGUgY29zdCcsIGNvc3QuZ3JpZFt3aGljaC5taW4oZXJyLnJhdGUudGVzdCldLCAnaGFzIHRoZSBtaW5pbXVtIHRlc3QgZXJyb3I6JywgbWluKGVyci5yYXRlLnRlc3QpKQpgYGAKCuacgOS8mOe7k+aenOS4jiBjcm9zcy12YWxpZGF0aW9uIOe7k+aenOS4gOiHtO+8jOmDveaYryBjb3N0ID0gMC4xIOaXtuacgOS8mOOAggoKIyMgNmQKCkRpc2N1c3MgeW91ciByZXN1bHRzLgoK57q/5oCnIGtlcm5lbCDmi5/lkIjpnZ7nur/mgKfovrnnlYzml7bvvIxjb3N0IOi+g+Wwj+aXtiB0cmFpbmluZyBlcnJvciDlkowgdGVzdCBlcnJvciDpg73mr5TovoPlsI/vvIzkvYblpoLmnpwgY29zdCDlpKrlsI/vvIznlLHkuo4gbWFyZ2luIOi/h+WuveWvvOiHtOWkseWOu+WIhuexu+S9nOeUqO+8jOingSBgY29zdCA9IDAuMDAxYCDml7bnmoTmqKHlnovlm77jgIIKCuaAu+S9k+adpeivtO+8jOi/meenjeaDheWGteS4i+aXoOiuuuWmguS9leiwg+aVtCBjb3N0IOmUmeivr+eOh+mDveavlOi+g+mrmO+8jOaJgOS7peW9k+S9v+eUqOS4jeWQjCBjb3N0IOWQjumUmeivr+eOh+aXoOaYjuaYvuWPmOWMluS4gOebtOW+iOmrmO+8jOWPr+iDveaYryBrZXJuZWwg6YCJ5oup5LiN5b2T5a+86Ie055qE44CCCgojIFF1ZXN0aW9uIDcKCkluIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgdXNlIHN1cHBvcnQgdmVjdG9yIGFwcHJvYWNoZXMgaW4gb3JkZXIgdG8gcHJlZGljdCB3aGV0aGVyIGEgZ2l2ZW4gY2FyIGdldHMgaGlnaCBvciBsb3cgZ2FzIG1pbGVhZ2UgYmFzZWQgb24gdGhlIEF1dG8gZGF0YSBzZXQuCgojIyA3YQoKQ3JlYXRlIGEgYmluYXJ5IHZhcmlhYmxlIHRoYXQgdGFrZXMgb24gYSAxIGZvciBjYXJzIHdpdGggZ2FzIG1pbGVhZ2UgYWJvdmUgdGhlIG1lZGlhbiwgYW5kIGEgMCBmb3IgY2FycyB3aXRoIGdhcyBtaWxlYWdlIGJlbG93IHRoZSBtZWRpYW4uCgpgYGB7cn0KbGlicmFyeShJU0xSKQptaWxlYWdlLm1lZGlhbiA8LSBtZWRpYW4oQXV0byRtcGcpCkF1dG8kbWIgPC0gaWZlbHNlKEF1dG8kbXBnID4gbWlsZWFnZS5tZWRpYW4sIDEsIDApCmBgYAoKIyMgN2IKCkZpdCBhIHN1cHBvcnQgdmVjdG9yIGNsYXNzae+sgWVyIHRvIHRoZSBkYXRhIHdpdGggdmFyaW91cyB2YWx1ZXMgb2YgY29zdCwgaW4gb3JkZXIgdG8gcHJlZGljdCB3aGV0aGVyIGEgY2FyIGdldHMgaGlnaCBvciBsb3cgZ2FzIG1pbGVhZ2UuClJlcG9ydCB0aGUgY3Jvc3MtdmFsaWRhdGlvbiBlcnJvcnMgYXNzb2NpYXRlZCB3aXRoIGRpZmZlcmVudCB2YWx1ZXMgb2YgdGhpcyBwYXJhbWV0ZXIuCkNvbW1lbnQgb24geW91ciByZXN1bHRzLgoKYGBge3J9CmNvc3QuZ3JpZCA8LSBjKDAuMDAxLCAwLjEsIDEsIDEwMCkKc2V0LnNlZWQoMSkKdHVuZS5yZXMgPC0gdHVuZShzdm0sIG1iIH4gLiAtIG1wZywgZGF0YSA9IEF1dG8sIGtlcm5lbCA9ICdsaW5lYXInLCByYW5nZXMgPSBsaXN0KGNvc3QgPSBjb3N0LmdyaWQpKQpzdW1tYXJ5KHR1bmUucmVzKQpgYGAKCmBjb3N0ID0gMWAgaGFzIHRoZSBsb3dlc3QgZXJyb3IgcmF0ZS4KCiMjIDdjCgpOb3cgcmVwZWF0IChiKSwgdGhpcyB0aW1lIHVzaW5nIFNWTXMgd2l0aCByYWRpYWwgYW5kIHBvbHlub21pYWwgYmFzaXMga2VybmVscywgd2l0aCBkae+sgGVyZW50IHZhbHVlcyBvZiAqZ2FtbWEqIGFuZCAqZGVncmVlKiBhbmQgKmNvc3QqLiBDb21tZW50IG9uIHlvdXIgcmVzdWx0cy4KCmBgYHtyfQoKYGBgCgo=