To laboratorium na temat Regresji grzbietowej (Ridge Regression - RR) i Lasso w R pochodzi ze stron 251-255 książki “Introduction to Statistical Learning with Applications in R” autorstwa Garetha Jamesa, Danieli Witten, Trevora Hastie i Roberta Tibshirani. Zostało ono ponownie zaimplementowane jesienią 2016 roku w formacie tidyverse przez Amelię McNamarę i R. Jordana Crousera w Smith College.

W tym tygodniu omówimy dwie alternatywne formy regresji liniowej zwane regresją grzbietową i regresją LASSO. Te dwie metody są przykładami metod regularyzacji lub zmniejszania, w których zachęca się do tego, aby parametry modelu były małe.

Regresja Grzbietowa i Lasso

Wykorzystamy pakiet glmnet w celu przeprowadzenia regresji ridge i lasso. Główną funkcją w tym pakiecie jest glmnet(), która może być użyta do dopasowania modeli regresji grzbietowej, modeli lasso i innych.

Funkcja ta ma nieco inną składnię niż inne funkcje dopasowujące modele, z którymi zetknęliśmy się do tej pory. W szczególności, musimy przekazać macierz \(x\) jak również wektor \(y\) i nie używamy składni \(y \sim x\).

Zanim przejdziemy dalej, upewnijmy się najpierw, że brakujące wartości zostały zostały usunięte z danych, jak opisano w poprzednim laboratorium.

Hitters = na.omit(Hitters)

W raporcie tym przeprowadzimy regresję grzbietową i lasso, aby przewidzieć Salary na danych Hitters.

Skonfigurujmy nasze dane:

x = model.matrix(Salary~., Hitters)[,-1] # przycinam pierwszą kolumnę
                                         # zostawiam predyktory
y = Hitters %>%
  select(Salary) %>%
  unlist() %>%
  as.numeric()

Funkcja model.matrix() jest szczególnie przydatna do tworzenia \(x\); nie tylko nie tylko tworzy macierz odpowiadającą 19 predyktorom, ale również automatycznie przekształca wszelkie zmienne jakościowe w zmienne dummy.

Ta ostatnia właściwość jest ważna, ponieważ glmnet() może przyjmować tylko numeryczne, ilościowe dane wejściowe.

Bias vs Variance

Wybór modelu w problemach uczenia nadzorowanego wiąże się z realizacją dwóch sprzecznych celów:

1.) Model powienien być dobrze dopasowany do danych uczących, aby uchwycić zależność pomiędzy danymi.

2.) Model powinien dobrze przybliżać nieznane dane (zapewniać mały błąd generalizacji).

Modele złożone dobdrze dopasowują się do danych wyjściowych, ale charakteryzują się dużą zmiennością wartości wyjściowych. Ryzykiem jest nadmierne dopasowanie = overfitting!

Modele prostsze są obciążone dużym błędem systematyczny (bias) i ich zastosowanie niesie ryzyko niewystarczającego dopasowania (underfitting)!

Składnikiem błędów generalizacji jest nieredukowalny błąd związany ze zmiennością danych.

Regularyzacja

Duża liczna zmiennych objaśniających (predyktorów): Metoda OLS nie daje jednoznacznego rozwiązania, gdy macierz XTX nie jest odwracalna (tzn. gdy zmienne objaśniające są liniowo zależne).

Taka sytuacja może mieć miejsce gdy zmiennych objaśniających jest tyle samo lub więcej niż obserwacji.

Duża wartość θi oznacza dużą wrażliwość funkcji regresji na drobne fluktuacje cechy!

Lepszym rozwiązaniem jest gorsze dopasowanie do danych uczących przy równoczesnym ograniczeniu parametrów świadczących o potencjalnie dużym błędzie generalizacji.

Regresja Grzbietowa

Wprowadzenie

Regresja grzbietowa (ang. Ridge regression) to technika regresji liniowej, która wprowadza regularyzację \(L_2\) do estymacji współczynników modelu. Regularyzacja \(L_2\) polega na dodaniu do funkcji celu kary proporcjonalnej do kwadratu wartości współczynników regresji.

Podstawową ideą regresji grzbietowej jest minimalizacja funkcji celu, która składa się z dwóch składników: błędu dopasowania (sumy kwadratów różnic pomiędzy rzeczywistymi wartościami odpowiedzi a przewidywanymi wartościami modelu) i kary regularyzacyjnej \(L_2\).

Wzór funkcji celu dla regresji grzbietowej można przedstawić jako: Minimize: RSS + \(\lambda \|\beta\|_2^2\), gdzie:

  • RSS to suma kwadratów różnic pomiędzy rzeczywistymi wartościami odpowiedzi a przewidywanymi wartościami modelu (błąd dopasowania),

  • \(\lambda\) (lambda) to parametr regularyzacji, który kontroluje siłę regularyzacji,

  • \(\|\beta\|_2^2\) to norma \(L_2\) współczynników regresji podniesiona do kwadratu.

Dodanie kary regularyzacyjnej \(L_2\) powoduje, że współczynniki regresji są skupione wokół zera, ale nie dokładnie równe zeru (chyba że \(\lambda\)=0).

Regresja grzbietowa zmniejsza wartości współczynników, ale nie powoduje, że stają się one równe zero. Im większa wartość \(\lambda\), tym bardziej są “sciskane” współczynniki regresji.

Regresja grzbietowa jest szczególnie przydatna, gdy mamy do czynienia z modelem, w którym występuje nadmierna wielowymiarowość lub wysokie korelacje między zmiennymi niezależnymi.

Poprzez zmniejszanie wartości współczynników, regresja grzbietowa może pomóc w redukcji wpływu mało istotnych cech, poprawić stabilność modelu i zmniejszyć ryzyko przeuczenia (overfitting).

Jednym ze sposobów kontroli złożoności modelu jest penalizacja jego wielkości. Na przykład, w problemie regresji liniowej:

\[ \min_{\beta \in \mathbb{R}^p} \sum_{i=1}^n (y_i - x_i^\top \beta)^2, \]

możemy kontrolować wielkość współczynników \(\beta\). Oczywiście wielkość \(\beta\) można zdefiniować na różne sposoby, np. norma-2: \(\|\beta\|_2\), norma-1: \(\|\beta\|_1\) czy norma-nieskończoność: \(\|\beta\|_{\infty}\). Regresja grzbietowa wiąże się z karą dwóch norm:

\[ \min_{\beta \in \mathbb{R}^p} \sum_{i=1}^n (y_i - x_i^\top \beta)^2 + \lambda \|\beta\|_2^2 \]

gdzie \(\lambda\) jest parametrem kontrolującym poziom regularyzacji. Zauważ, że \(X\) to macierz \(n\) na \(p\) wymiarów z wierszami: \(x_i^\top\), oraz \(Y\) to \(n\) na 1 wektor \(y_i\). Załóżmy, że \(X^\top X + \lambda I\) jest odwracalna, mamy dokładne rozwiązanie problemu regresji grzbietowej:

\[ \hat \beta_{ridge} = (X^\top X + \lambda I)^{-1}X^\top Y. \]

Przypomnijmy, że rozwiązaniem zwykłej regresji najmniejszych kwadratów jest (zakładając odwracalność macierzy \(X^\top X\)):

\[ \hat \beta_{ols} = (X^\top X)^{-1}X^\top Y. \]

Dwa fakty: kiedy \(\lambda \to 0\), \(\hat \beta_{ridge} \to \hat \beta_{ols}\); kiedy \(\lambda \to \infty\), \(\hat \beta_{ridge} \to 0\).

W szczególnych przypadkach \(X\) jest ortogonalna (tzn. kolumny \(X\) są ortogonalne), mamy:

\[ \hat \beta_{ridge} = \frac{\hat \beta_{ols}}{1 + \lambda}. \]

Widzimy więc, że estymator grzbietowy ma dodatkowo \(1/(1 + \lambda)\) tzw. “shrinkage factor”. W związku z tym na estymatorze grzbietowym występuje obciążliwość (bias).

Przykład

Funkcja glmnet() posiada argument alfa, który określa, jaki typ modelu jest dopasowywany.

Jeśli alfa = 0 to dopasowywany jest model regresji grzbietowej, a jeśli alfa = 1 to dopasowywany jest model lasso.

Najpierw dopasowujemy model regresji grzbietowej:

grid = 10^seq(10, -2, length = 100)
ridge_mod = glmnet(x, y, alpha = 0, lambda = grid)

Domyślnie funkcja glmnet() wykonuje regresję grzbietową dla automatycznie wybranego wybranego zakresu wartości \(\lambda\). Jednakże, tutaj wybraliśmy implementację funkcję w zakresie wartości od \(\lambda = 10^{10}\) do \(\lambda = 10^{-2}\), zasadniczo pokrywając pełen zakres scenariuszy od modelu zerowego zawierającego tylko przechwyt, do dopasowania najmniejszego kwadratu.

Jak widać, możemy również obliczyć dopasowanie modelu dla konkretnej wartości \(\lambda\), która nie jest jedną z oryginalnych wartości siatki.

Zauważ, że domyślnie funkcja glmnet() standaryzuje zmienne tak, by były w tej samej skali. Aby wyłączyć to domyślne ustawienie, użyj argumentu standardize = FALSE.

Z każdą wartością \(\lambda\) związany jest wektor współczynników regresji grzbietowej, przechowywany w macierzy, do której można uzyskać dostęp przez coef(). W tym przypadku jest to macierz \(20 \times 100\), z 20 wierszami (po jednym dla każdego predyktora, plus intercept) i 100 kolumnami (po jednej dla każdej wartości \(\lambda\)).

dim(coef(ridge_mod))
## [1]  20 100
plot(ridge_mod)    # wykres współczynników

Spodziewamy się, że oszacowania współczynników będą znacznie mniejsze, w sensie normy \(l_2\), gdy używana jest duża wartość \(\lambda\), w porównaniu z małą wartością \(\lambda\).

Oto współczynniki, gdy \(\lambda = 11498\), wraz z ich normą \(l_2\):

ridge_mod$lambda[50]  # Wyświetl 50-tą wartość lambdy
## [1] 11497.57
coef(ridge_mod)[,50] # Wyświetl współczynniki związane z 50-tą wartością lambdy
##   (Intercept)         AtBat          Hits         HmRun          Runs 
## 407.356050200   0.036957182   0.138180344   0.524629976   0.230701523 
##           RBI         Walks         Years        CAtBat         CHits 
##   0.239841459   0.289618741   1.107702929   0.003131815   0.011653637 
##        CHmRun         CRuns          CRBI        CWalks       LeagueN 
##   0.087545670   0.023379882   0.024138320   0.025015421   0.085028114 
##     DivisionW       PutOuts       Assists        Errors    NewLeagueN 
##  -6.215440973   0.016482577   0.002612988  -0.020502690   0.301433531
sqrt(sum(coef(ridge_mod)[-1,50]^2)) # Oblicz normę l2
## [1] 6.360612

Dla kontrastu, oto współczynniki, gdy \(\lambda = 705\), wraz z ich \(l_2\) normą. Zwróć uwagę na znacznie większą normę \(l_2\) współczynników związanych z tą mniejszą wartością \(\lambda\).

ridge_mod$lambda[60] # Wyświetl 60-tą wartość lambdy
## [1] 705.4802
coef(ridge_mod)[,60] # Wyświetl współczynniki powiązane z 60-tą wartość lambdy
##  (Intercept)        AtBat         Hits        HmRun         Runs          RBI 
##  54.32519950   0.11211115   0.65622409   1.17980910   0.93769713   0.84718546 
##        Walks        Years       CAtBat        CHits       CHmRun        CRuns 
##   1.31987948   2.59640425   0.01083413   0.04674557   0.33777318   0.09355528 
##         CRBI       CWalks      LeagueN    DivisionW      PutOuts      Assists 
##   0.09780402   0.07189612  13.68370191 -54.65877750   0.11852289   0.01606037 
##       Errors   NewLeagueN 
##  -0.70358655   8.61181213
sqrt(sum(coef(ridge_mod)[-1,60]^2)) # Oblicz normę l2
## [1] 57.11001

Funkcję predict() możemy wykorzystać do wielu celów. Na przykład, możemy uzyskać współczynniki regresji grzbietowej dla nowej wartości \(\lambda\), powiedzmy 50:

predict(ridge_mod, s = 50, type = "coefficients")[1:20,]
##   (Intercept)         AtBat          Hits         HmRun          Runs 
##  4.876610e+01 -3.580999e-01  1.969359e+00 -1.278248e+00  1.145892e+00 
##           RBI         Walks         Years        CAtBat         CHits 
##  8.038292e-01  2.716186e+00 -6.218319e+00  5.447837e-03  1.064895e-01 
##        CHmRun         CRuns          CRBI        CWalks       LeagueN 
##  6.244860e-01  2.214985e-01  2.186914e-01 -1.500245e-01  4.592589e+01 
##     DivisionW       PutOuts       Assists        Errors    NewLeagueN 
## -1.182011e+02  2.502322e-01  1.215665e-01 -3.278600e+00 -9.496680e+00

Podzielimy teraz próbki na zbiór treningowy i testowy w celu oszacować błąd testu regresji grzbietowej i lasso.

set.seed(1)

train = Hitters %>%
  sample_frac(0.5)

test = Hitters %>%
  setdiff(train)

x_train = model.matrix(Salary~., train)[,-1]
x_test = model.matrix(Salary~., test)[,-1]

y_train = train %>%
  select(Salary) %>%
  unlist() %>%
  as.numeric()

y_test = test %>%
  select(Salary) %>%
  unlist() %>%
  as.numeric()

Następnie dopasowujemy model regresji grzbietowej na zbiorze treningowym i oceniamy jego MSE na zbiorze testowym, używając \(\lambda = 4\). Zwróć uwagę na użycie funkcji predict(). Ponownie: tym razem otrzymujemy przewidywania dla zbioru testowego, zastępując type="coefficients" argumentem newx.

ridge_mod = glmnet(x_train, y_train, alpha=0, lambda = grid, thresh = 1e-12)
ridge_pred = predict(ridge_mod, s = 4, newx = x_test)
mean((ridge_pred - y_test)^2)
## [1] 139858.6

Testowe MSE wynosi 139858. Zauważ, że gdybyśmy zamiast tego dopasowali po prostu model tylko z wyrazem wolnym, przewidywalibyśmy każdą obserwację testową używając średniej z obserwacji zbioru treningowego. W takim przypadku moglibyśmy obliczyć MSE zestawu testowego w ten sposób:

mean((mean(y_train) - y_test)^2)
## [1] 224692.1

Moglibyśmy również uzyskać ten sam wynik, dopasowując model regresji grzbietowej z bardzo dużą wartością \(\lambda\). Zauważ, że 1e10 oznacza \(10^{10}\).

ridge_pred = predict(ridge_mod, s = 1e10, newx = x_test)
mean((ridge_pred - y_test)^2)
## [1] 224692.1

Tak więc dopasowanie modelu regresji grzbietowej z \(\lambda = 4\) prowadzi do znacznie niższego testu MSE niż dopasowanie modelu z samym przechwytem.

Sprawdzimy teraz, czy jest jakaś korzyść z wykonania regresji grzbietowej z \(\lambda = 4\) zamiast po prostu wykonać regresję najmniejszych kwadratów.

Przypomnijmy, że najmniejsza kwadratura to po prostu regresja grzbietowa z \(\lambda = 0\).

* Uwaga: Aby glmnet() dawał dokładne (exact) współczynniki najmniejszego kwadratu, gdy \(\lambda = 0\), używamy argumentu exact=T przy wywołaniu funkcji predict(). W przeciwnym razie, funkcja predict() będzie interpolować nad siatką wartości \(\lambda\) użytą w dopasowaniu modelu glmnet(), dając przybliżone wyniki. Nawet gdy użyjemy exact = T, pozostaje niewielka rozbieżność na trzecim miejscu po przecinku między wynikami glmnet(), gdy \(\lambda = 0\) i wyjściem z lm(); jest to spowodowane numerycznym przybliżeniem ze strony glmnet().

ridge_pred = predict(ridge_mod, s = 0, newx = x_test)
mean((ridge_pred - y_test)^2)
## [1] 174060
lm(Salary~., data = train)
## 
## Call:
## lm(formula = Salary ~ ., data = train)
## 
## Coefficients:
## (Intercept)        AtBat         Hits        HmRun         Runs          RBI  
##   2.398e+02   -1.639e-03   -2.179e+00    6.337e+00    7.139e-01    8.735e-01  
##       Walks        Years       CAtBat        CHits       CHmRun        CRuns  
##   3.594e+00   -1.309e+01   -7.136e-01    3.316e+00    3.407e+00   -5.671e-01  
##        CRBI       CWalks      LeagueN    DivisionW      PutOuts      Assists  
##  -7.525e-01    2.347e-01    1.322e+02   -1.346e+02    2.099e-01    6.229e-01  
##      Errors   NewLeagueN  
##  -4.616e+00   -8.330e+01
predict(ridge_mod, s = 0, type="coefficients")[1:20,]
##   (Intercept)         AtBat          Hits         HmRun          Runs 
##  239.89368111   -0.01946204   -2.07305757    6.44254692    0.64610179 
##           RBI         Walks         Years        CAtBat         CHits 
##    0.82179888    3.62448842  -13.28142313   -0.70314292    3.26064805 
##        CHmRun         CRuns          CRBI        CWalks       LeagueN 
##    3.33170237   -0.54000590   -0.72015101    0.22582579  131.41324242 
##     DivisionW       PutOuts       Assists        Errors    NewLeagueN 
## -134.76073238    0.20949301    0.61942855   -4.58545824  -82.35090554

Wygląda na to, że rzeczywiście poprawiamy się w stosunku do zwykłego najmniejszego kwadratu!

Uwaga: ogólnie, jeśli chcemy dopasować (niespenalizowany) model najmniejszych kwadratów, to powinniśmy użyć funkcji lm(), ponieważ ta funkcja dostarcza bardziej użytecznych wyjścia, takie jak błędy standardowe i wartości \(p\) dla współczynników.

Zamiast arbitralnie wybierać \(\lambda = 4\), lepiej byłoby użyć walidacji krzyżowej do wyboru parametru dostrojenia \(\lambda\). Możemy to zrobić używając wbudowanej funkcji walidacji krzyżowej, cv.glmnet(). Domyślnie funkcja ta wykonuje 10-krotną walidację krzyżową, choć można to zmienić używając argumentu argumentu folds. Zauważ, że najpierw ustawiamy losowe ziarno, aby nasze wyniki były powtarzalne, ponieważ wybór krotności walidacji krzyżowej jest losowy.

set.seed(1)
cv.out = cv.glmnet(x_train, y_train, alpha = 0) # Dopasuj model regresji grzbietowej na danych treningowych
bestlam = cv.out$lambda.min  # Wybierz lamdę, która minimalizuje treningowy MSE 
bestlam
## [1] 326.1406

Widzimy zatem, że wartość \(\lambda\), która powoduje najmniejszy błąd walidacji krzyżowej to 326. Możemy również wykreślić MSE jako funkcję \(\lambda\):

plot(cv.out) # Narysuj wykres treningowego MSE jako funkcję lambda

Jaki jest testowy MSE związany z tą wartością \(\lambda\)?

ridge_pred = predict(ridge_mod, s = bestlam, newx = x_test) # Użyj najlepszej lambdy do przewidywania danych testowych
mean((ridge_pred - y_test)^2) # Oblicz testowe MSE
## [1] 140056.2

Stanowi to dalszą poprawę w stosunku do testowego MSE, które uzyskaliśmy używając \(\lambda = 4\). Ostatecznie, ponownie wyznaczamy nasz model regresji grzbietowej na pełnym zestawie danych, używając wartości \(\lambda\) wybranej w walidacji krzyżowej, i sprawdzamy oszacowania współczynników.

out = glmnet(x, y, alpha = 0) # Dopasuj model regresji grzbietowej do pełnego zbioru danych
predict(out, type = "coefficients", s = bestlam)[1:20,] # Wyświetlanie współczynników przy użyciu lambda wybranego przez CV
##  (Intercept)        AtBat         Hits        HmRun         Runs          RBI 
##  15.44834992   0.07716945   0.85906253   0.60120338   1.06366687   0.87936073 
##        Walks        Years       CAtBat        CHits       CHmRun        CRuns 
##   1.62437580   1.35296285   0.01134998   0.05746377   0.40678422   0.11455696 
##         CRBI       CWalks      LeagueN    DivisionW      PutOuts      Assists 
##   0.12115916   0.05299953  22.08942756 -79.03490992   0.16618830   0.02941513 
##       Errors   NewLeagueN 
##  -1.36075645   9.12528397

Zgodnie z oczekiwaniami, żaden ze współczynników nie jest dokładnie zerowy - regresja grzbietowa nie dokonuje selekcji zmiennych!

Regresja Lasso

Wprowadzenie

Zamiast regularyzacji \(L_2\), LASSO używa penalizacji \(L_1\), to znaczy:

\[ \min_{\beta \in \mathbb{R}^p} \sum_{i=1}^n (y_i - x_i^\top \beta)^2 + \lambda \|\beta\|_1. \]

Ze względu na charakter normy \(L_1\), LASSO ma tendencję do dawania bardziej rzadkich rozwiązań niż regresja grzbietowa. Jest to typowo użyteczne w ustawieniach wielowymiarowych, gdy prawdziwy model jest w rzeczywistości niskowymiarowym osadzeniem.

Model regresji lasso został pierwotnie opracowany w 1989 roku. Jest to alternatywa dla klasycznego oszacowania metodą najmniejszych kwadratów, która unika wielu problemów z nadmiernym dopasowaniem (overfittingiem), gdy mamy dużą liczbę niezależnych zmiennych.

Regresja Lasso (Least Absolute Shrinkage and Selection Operator) to technika regresji liniowej stosowana do oszacowania współczynników modelu, która wprowadza regularyzację \(L_1\). Regularyzacja L1 polega na dodaniu do funkcji celu kary proporcjonalnej do wartości bezwzględnej współczynników regresji.

Regresja Lasso ma zdolność do jednoczesnego wykonania selekcji cech i regularyzacji, co oznacza, że może pomóc w identyfikacji najbardziej istotnych cech modelu, a także zmniejszyć wpływ mniej istotnych cech.

Podstawowym celem regresji Lasso jest minimalizacja funkcji celu, która składa się z dwóch składników: błędu dopasowania (sumy kwadratów różnic pomiędzy rzeczywistymi wartościami odpowiedzi a przewidywanymi wartościami modelu) i kary regularyzacyjnej \(L_1\).

Wzór funkcji celu dla regresji Lasso może być przedstawiony jako: Minimize: RSS + \(\lambda \|\beta\|_1\), gdzie:

  • RSS to suma kwadratów różnic pomiędzy rzeczywistymi wartościami odpowiedzi a przewidywanymi wartościami modelu (błąd dopasowania),

  • \(\lambda\) (lambda) to parametr regularyzacji, który kontroluje siłę regularyzacji, a \(\|\beta\|_1\) to norma \(L_1\) współczynników regresji.

Dodanie kary regularyzacyjnej \(L_1\) powoduje, że niektóre współczynniki regresji stają się równe zero, co prowadzi do selekcji cech. Im większa wartość \(\lambda\), tym większa jest tendencja do redukcji współczynników do zera, prowadząc do bardziej rzadkiego modelu z mniejszą liczbą cech.

Regresja Lasso jest przydatna w przypadkach, gdy mamy do czynienia z wieloma cechami, z których niektóre mogą być nieistotne. Może pomóc w identyfikacji istotnych cech, redukcji nadmiaru danych i zwiększeniu interpretowalności modelu.

Przykład

Zobaczyliśmy, że regresja grzbietowa z mądrym wyborem \(\lambda\) może przewyższać metodę najmniejszych kwadratów, jak również model zerowy na zbiorze danych Hitters.

Teraz zobaczmy, czy lasso może dać albo dokładniejszy, albo bardziej interpretowalny model niż regresja grzbietowa.

W celu dopasowania modelu lasso, po raz kolejny używamy funkcji glmnet(), jednak tym razem używamy argumentu alpha=1. Poza tą zmianą postępujemy tak samo jak w przypadku dopasowywania modelu regresji grzbietowej:

lasso_mod = glmnet(x_train, 
                   y_train, 
                   alpha = 1, 
                   lambda = grid) # Dopasuj model lasso do danych treningowych

plot(lasso_mod)    # Wykreśl współczynniki

Zauważmy, że na wykresie współczynników, w zależności od wyboru dostrojenia parametru, niektóre ze współczynników są dokładnie równe zeru. Teraz przeprowadzimy walidację krzyżową i obliczymy związany z nią błąd testu:

set.seed(1)
cv.out = cv.glmnet(x_train, y_train, alpha = 1) # Dopasuj model lasso do danych treningowych
plot(cv.out) # Narysuj wykres MSE dla próby uczącej jako funkcję lambda

bestlam = cv.out$lambda.min # Wybierz lamdę, która minimalizuje MSE w próbie uczącej
lasso_pred = predict(lasso_mod, s = bestlam, newx = x_test) # Użyj najlepszej lambdy do przewidywania danych testowych
mean((lasso_pred - y_test)^2) # Oblicz MSE w próbie testowej
## [1] 143273

Jest to znacznie niższe MSE zbioru testowego niż modelu zerowego i modelu najmniejszych kwadratów, i bardzo podobny do MSE testu regresji grzbietowej z \(\lambda\) wybranej przez walidację krzyżową.

Jednakże lasso ma istotną przewagę nad regresją grzbietową w tym, że wynikowe oszacowania współczynników są rzadkie. Tutaj widzimy, że 12 z 19 oszacowań współczynników jest dokładnie zerowych:

out = glmnet(x, y, alpha = 1, lambda = grid) # Dopasuj model lasso do pełnego zbioru danych
lasso_coef = predict(out, type = "coefficients", s = bestlam)[1:20,] # Wyświetlanie współczynników przy użyciu lambda wybranego przez CV
lasso_coef
##   (Intercept)         AtBat          Hits         HmRun          Runs 
##    1.27429897   -0.05490834    2.18012455    0.00000000    0.00000000 
##           RBI         Walks         Years        CAtBat         CHits 
##    0.00000000    2.29189433   -0.33767315    0.00000000    0.00000000 
##        CHmRun         CRuns          CRBI        CWalks       LeagueN 
##    0.02822467    0.21627609    0.41713051    0.00000000   20.28190194 
##     DivisionW       PutOuts       Assists        Errors    NewLeagueN 
## -116.16524424    0.23751978    0.00000000   -0.85604181    0.00000000

Wybierając tylko predyktory o niezerowych współczynnikach widzimy, że model lasso z \(\lambda\) wybranym przez walidację krzyżową zawiera tylko siedem zmiennych:

lasso_coef[lasso_coef != 0] # Wyświetlanie tylko niezerowych współczynników
##   (Intercept)         AtBat          Hits         Walks         Years 
##    1.27429897   -0.05490834    2.18012455    2.29189433   -0.33767315 
##        CHmRun         CRuns          CRBI       LeagueN     DivisionW 
##    0.02822467    0.21627609    0.41713051   20.28190194 -116.16524424 
##       PutOuts        Errors 
##    0.23751978   -0.85604181

Twoja kolej!

Teraz nadszedł czas na przetestowanie tych metod (regresja grzbietowa i lasso) oraz metod oceny (zestaw walidacyjny, walidacja krzyżowa) na innych zbiorach danych. Możesz pracować z zespołem nad tą częścią laboratorium.

Możesz użyć dowolnego zbioru danych zawartego w ISLR lub wybrać jeden z pakietów danych na Kaggle/Data World itp. (zmienna zależna musi być ciągła).

Pobierz zbiór danych i spróbuj określić optymalny zestaw parametrów, które należy użyć do jego modelowania! Aby zaliczyć to laboratorium, zamieść odpowiedzi na następujące pytania:

Zbiór danych

  • Który zbiór danych wybrałeś?

Wybrany datase: Statystyki dla dużej liczby amerykańskich szkół wyższych z wydania US News and World Report z 1995 roku.

# Wybrany datase:
# Statystyki dla dużej liczby amerykańskich szkół wyższych z wydania US News and World Report z 1995 roku.

data("College")
head(College)
##                              Private Apps Accept Enroll Top10perc Top25perc
## Abilene Christian University     Yes 1660   1232    721        23        52
## Adelphi University               Yes 2186   1924    512        16        29
## Adrian College                   Yes 1428   1097    336        22        50
## Agnes Scott College              Yes  417    349    137        60        89
## Alaska Pacific University        Yes  193    146     55        16        44
## Albertson College                Yes  587    479    158        38        62
##                              F.Undergrad P.Undergrad Outstate Room.Board Books
## Abilene Christian University        2885         537     7440       3300   450
## Adelphi University                  2683        1227    12280       6450   750
## Adrian College                      1036          99    11250       3750   400
## Agnes Scott College                  510          63    12960       5450   450
## Alaska Pacific University            249         869     7560       4120   800
## Albertson College                    678          41    13500       3335   500
##                              Personal PhD Terminal S.F.Ratio perc.alumni Expend
## Abilene Christian University     2200  70       78      18.1          12   7041
## Adelphi University               1500  29       30      12.2          16  10527
## Adrian College                   1165  53       66      12.9          30   8735
## Agnes Scott College               875  92       97       7.7          37  19016
## Alaska Pacific University        1500  76       72      11.9           2  10922
## Albertson College                 675  67       73       9.4          11   9727
##                              Grad.Rate
## Abilene Christian University        60
## Adelphi University                  56
## Adrian College                      54
## Agnes Scott College                 59
## Alaska Pacific University           15
## Albertson College                   55

Zmienna zależna

  • Jaka była Twoja zmienna zależna (tzn. co próbowałeś modelować)?

Wybrana zmienna objaśniana - Wskaźnik ukończenia studiów

y = College %>%
  select(Grad.Rate) %>%
  unlist() %>%
  as.numeric()

x = model.matrix(Grad.Rate~., College)[,-1]

Regresja grzbietowa, Lasso, OLS

  • Czy oczekiwałeś, że regresja grzbietowa będzie lepsza od lasso, czy odwrotnie? Jak wypada w stosunku do OLS? Pokaż odpowiednie raporty, miary dopasowania i krótko je omów (porównaj).

W pierwszej kolejnosci należy podzielić próbki na zbiór treningowy i testowy w celu oszacować błąd testu regresji grzbietowej i lasso oraz OLS.

# Zastosowany został stosunek próby treningowej do testowej 80/20
set.seed(1)

train = College %>%
  sample_frac(0.8) 

test = College %>%
  setdiff(train)

x_train = model.matrix(Grad.Rate~., train)[,-1]
x_test = model.matrix(Grad.Rate~., test)[,-1]

y_train = train %>%
  select(Grad.Rate) %>%
  unlist() %>%
  as.numeric()

y_test = test %>%
  select(Grad.Rate) %>%
  unlist() %>%
  as.numeric()

1. Regresja grzbietowa

W pierwszej kolejności przetestowana zostanie regresja grzbietowa (alfa=0)

grid = 10^seq(10, -2, length = 100)
ridge_mod = glmnet(x, y, alpha = 0, lambda = grid)
dim(coef(ridge_mod))
## [1]  18 100
plot(ridge_mod)

Następnie identyfikujemy wartość lambdy, która najbardziej minimalizuje błąd MSE

set.seed(1)
cv.out = cv.glmnet(x_train, y_train, alpha = 0) # dopasowanie modelu regresji grzbietowej na danych treningowych
bestlam = cv.out$lambda.min  # Wybierz lamdę, która minimalizuje treningowy MSE 
bestlam
## [1] 3.349577
plot(cv.out)

W kolejnym kroku wyznaczamy prognozę na bazie danych treningowych. Oszacowany został również błąd MSE oraz wartości współczynników w modelu.

ridge_pred = predict(ridge_mod, s = bestlam, newx = x_test) # Zastosowanie najlepiszej wartości lambdy
MSE_reg_g = mean((ridge_pred - y_test)^2) # MSE
print(paste("Wartość błędu MSE dla prognozy za pomocą regresji grzbietowej:",  MSE_reg_g))
## [1] "Wartość błędu MSE dla prognozy za pomocą regresji grzbietowej: 143.303113635089"
out = glmnet(x, y, alpha = 0) 
Reg_g_coef = predict(out, type = "coefficients", s = bestlam)[1:18,] # Współczynniki
Reg_g_coef 
##   (Intercept)    PrivateYes          Apps        Accept        Enroll 
## 35.4259636579  3.5360447063  0.0004891764  0.0003725834  0.0001803018 
##     Top10perc     Top25perc   F.Undergrad   P.Undergrad      Outstate 
##  0.0929335051  0.1061424028 -0.0001242029 -0.0013135925  0.0007248959 
##    Room.Board         Books      Personal           PhD      Terminal 
##  0.0017740362 -0.0022337145 -0.0018475835  0.0491413814 -0.0171970338 
##     S.F.Ratio   perc.alumni        Expend 
##  0.0425557858  0.2401109479 -0.0001708884

2. Model regresji Lasso

lasso_mod = glmnet(x_train, y_train, alpha = 1,lambda = grid) # Model lasso
plot(lasso_mod)  # Wykres współczynników
## Warning in regularize.values(x, y, ties, missing(ties), na.rm = na.rm):
## collapsing to unique 'x' values

Identyfikacja wartości lambdy, która najbardziej minimalizuje błąd MSE w modelu Lasso.

set.seed(1)
cv.out = cv.glmnet(x_train, y_train, alpha = 1) # Dopasowanie modelu Lasso
bestlam = cv.out$lambda.min # Najlepsza lambda
plot(cv.out) 

Ponownie wyznaczamy wartości prognozowane oraz liczymy błąd MSE. Następnie sprawdzamy współczynniki modelu.

lasso_pred = predict(lasso_mod, s = bestlam, newx = x_test) # Predykcja z najlepszą lambdą
MSE_reg_l = mean((lasso_pred - y_test)^2) # MSE dla Lasso
print(paste("Wartość błędu MSE dla prognozy za pomocą regresji Lasso:",  MSE_reg_l))
## [1] "Wartość błędu MSE dla prognozy za pomocą regresji Lasso: 150.170305331426"
out = glmnet(x, y, alpha = 1, lambda = grid) # Dopasuj model lasso do pełnego zbioru danych
lasso_coef = predict(out, type = "coefficients", s = bestlam)[1:18,] # Wszystkie współczynniki
lasso_coef
##   (Intercept)    PrivateYes          Apps        Accept        Enroll 
##  3.601812e+01  1.696896e+00  5.109904e-04  0.000000e+00  0.000000e+00 
##     Top10perc     Top25perc   F.Undergrad   P.Undergrad      Outstate 
##  1.668854e-02  1.437067e-01  0.000000e+00 -1.248776e-03  8.922760e-04 
##    Room.Board         Books      Personal           PhD      Terminal 
##  1.452065e-03  0.000000e+00 -1.539697e-03  0.000000e+00  0.000000e+00 
##     S.F.Ratio   perc.alumni        Expend 
##  0.000000e+00  2.523755e-01 -5.372494e-06

Tym razem 7 współczynników zostało wyzerowane

lasso_coef_2 = lasso_coef[lasso_coef != 0] # Wyświetlanie tylko niezerowych współczynników
lasso_coef_2
##   (Intercept)    PrivateYes          Apps     Top10perc     Top25perc 
##  3.601812e+01  1.696896e+00  5.109904e-04  1.668854e-02  1.437067e-01 
##   P.Undergrad      Outstate    Room.Board      Personal   perc.alumni 
## -1.248776e-03  8.922760e-04  1.452065e-03 -1.539697e-03  2.523755e-01 
##        Expend 
## -5.372494e-06

Finalnie pozostaje 11 istotnych współczynników w modelu

3. Klasyczny model OLS

x_train <- as.data.frame(x_train)  # Konwersja macierzy na ramkę danych
y_train <- as.data.frame(y_train) 
train_data <- cbind(y_train, x_train)

ols_mod <- lm(y_train ~ ., data = train_data)  # OLS: wszystkie zmienne objaśniające
summary(ols_mod)  # Wyświetlenie szczegółów modelu
## 
## Call:
## lm(formula = y_train ~ ., data = train_data)
## 
## Residuals:
##     Min      1Q  Median      3Q     Max 
## -51.834  -6.962  -0.523   7.188  54.344 
## 
## Coefficients:
##               Estimate Std. Error t value Pr(>|t|)    
## (Intercept) 30.3348289  5.5530915   5.463 6.86e-08 ***
## PrivateYes   3.9113363  1.9446868   2.011 0.044738 *  
## Apps         0.0010006  0.0005299   1.888 0.059489 .  
## Accept      -0.0004933  0.0010687  -0.462 0.644525    
## Enroll       0.0030146  0.0027903   1.080 0.280416    
## Top10perc    0.0804254  0.0812505   0.990 0.322646    
## Top25perc    0.0817411  0.0613172   1.333 0.183006    
## F.Undergrad -0.0004387  0.0004752  -0.923 0.356260    
## P.Undergrad -0.0016990  0.0004353  -3.903 0.000106 ***
## Outstate     0.0008562  0.0002601   3.292 0.001053 ** 
## Room.Board   0.0022091  0.0006675   3.309 0.000991 ***
## Books       -0.0023413  0.0032875  -0.712 0.476637    
## Personal    -0.0015716  0.0008594  -1.829 0.067947 .  
## PhD          0.0678093  0.0642605   1.055 0.291744    
## Terminal    -0.0252143  0.0708814  -0.356 0.722170    
## S.F.Ratio    0.1375400  0.1806895   0.761 0.446838    
## perc.alumni  0.3113216  0.0558734   5.572 3.80e-08 ***
## Expend      -0.0003238  0.0001660  -1.950 0.051627 .  
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 12.97 on 604 degrees of freedom
## Multiple R-squared:  0.4598, Adjusted R-squared:  0.4446 
## F-statistic: 30.24 on 17 and 604 DF,  p-value: < 2.2e-16
summary(ols_mod)$coefficients
##                  Estimate   Std. Error    t value     Pr(>|t|)
## (Intercept) 30.3348289190 5.5530914628  5.4626921 6.862151e-08
## PrivateYes   3.9113363224 1.9446868419  2.0112937 4.473820e-02
## Apps         0.0010005716 0.0005299303  1.8881194 5.948895e-02
## Accept      -0.0004933097 0.0010686657 -0.4616127 6.445253e-01
## Enroll       0.0030145501 0.0027903341  1.0803545 2.804155e-01
## Top10perc    0.0804254087 0.0812504950  0.9898452 3.226462e-01
## Top25perc    0.0817410923 0.0613171903  1.3330861 1.830061e-01
## F.Undergrad -0.0004386809 0.0004751626 -0.9232225 3.562599e-01
## P.Undergrad -0.0016989840 0.0004353336 -3.9027175 1.058208e-04
## Outstate     0.0008561899 0.0002600847  3.2919656 1.052934e-03
## Room.Board   0.0022090732 0.0006675431  3.3092591 9.910922e-04
## Books       -0.0023412591 0.0032875211 -0.7121655 4.766373e-01
## Personal    -0.0015715846 0.0008594283 -1.8286396 6.794660e-02
## PhD          0.0678093163 0.0642605140  1.0552252 2.917442e-01
## Terminal    -0.0252143361 0.0708813729 -0.3557258 7.221701e-01
## S.F.Ratio    0.1375400010 0.1806895325  0.7611952 4.468376e-01
## perc.alumni  0.3113216154 0.0558734003  5.5719110 3.798553e-08
## Expend      -0.0003237719 0.0001660288 -1.9500945 5.162711e-02

W kolejnym kroku sekwencyjnie usuwamy nieistotne zmienne objaśniające

# Usuwanie niestotnych zmiennych
stepwise_mod <- step(ols_mod, direction = "backward")
## Start:  AIC=3205.7
## y_train ~ PrivateYes + Apps + Accept + Enroll + Top10perc + Top25perc + 
##     F.Undergrad + P.Undergrad + Outstate + Room.Board + Books + 
##     Personal + PhD + Terminal + S.F.Ratio + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## - Terminal     1      21.3 101634 3203.8
## - Accept       1      35.8 101649 3203.9
## - Books        1      85.3 101698 3204.2
## - S.F.Ratio    1      97.5 101710 3204.3
## - F.Undergrad  1     143.4 101756 3204.6
## - Top10perc    1     164.8 101778 3204.7
## - PhD          1     187.3 101800 3204.8
## - Enroll       1     196.4 101809 3204.9
## - Top25perc    1     299.0 101912 3205.5
## <none>                     101613 3205.7
## - Personal     1     562.6 102175 3207.1
## - Apps         1     599.8 102213 3207.4
## - Expend       1     639.8 102253 3207.6
## - PrivateYes   1     680.6 102293 3207.9
## - Outstate     1    1823.2 103436 3214.8
## - Room.Board   1    1842.4 103455 3214.9
## - P.Undergrad  1    2562.4 104175 3219.2
## - perc.alumni  1    5223.0 106836 3234.9
## 
## Step:  AIC=3203.83
## y_train ~ PrivateYes + Apps + Accept + Enroll + Top10perc + Top25perc + 
##     F.Undergrad + P.Undergrad + Outstate + Room.Board + Books + 
##     Personal + PhD + S.F.Ratio + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## - Accept       1      35.0 101669 3202.0
## - S.F.Ratio    1      98.4 101733 3202.4
## - Books        1     100.1 101734 3202.4
## - F.Undergrad  1     152.3 101787 3202.8
## - Top10perc    1     183.9 101818 3203.0
## - Enroll       1     200.1 101834 3203.1
## - PhD          1     225.5 101860 3203.2
## - Top25perc    1     283.0 101917 3203.6
## <none>                     101634 3203.8
## - Personal     1     553.4 102188 3205.2
## - Apps         1     600.8 102235 3205.5
## - Expend       1     657.8 102292 3205.8
## - PrivateYes   1     710.5 102345 3206.2
## - Outstate     1    1802.2 103436 3212.8
## - Room.Board   1    1821.1 103455 3212.9
## - P.Undergrad  1    2557.1 104191 3217.3
## - perc.alumni  1    5201.9 106836 3232.9
## 
## Step:  AIC=3202.05
## y_train ~ PrivateYes + Apps + Enroll + Top10perc + Top25perc + 
##     F.Undergrad + P.Undergrad + Outstate + Room.Board + Books + 
##     Personal + PhD + S.F.Ratio + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## - Books        1      95.7 101765 3200.6
## - S.F.Ratio    1     103.4 101773 3200.7
## - F.Undergrad  1     144.1 101813 3200.9
## - Enroll       1     165.8 101835 3201.1
## - PhD          1     209.9 101879 3201.3
## - Top25perc    1     259.8 101929 3201.6
## - Top10perc    1     282.8 101952 3201.8
## <none>                     101669 3202.0
## - Personal     1     542.0 102211 3203.4
## - Expend       1     629.6 102299 3203.9
## - PrivateYes   1     686.0 102355 3204.2
## - Apps         1    1314.0 102983 3208.0
## - Outstate     1    1772.2 103441 3210.8
## - Room.Board   1    1829.8 103499 3211.1
## - P.Undergrad  1    2522.5 104192 3215.3
## - perc.alumni  1    5312.2 106981 3231.7
## 
## Step:  AIC=3200.63
## y_train ~ PrivateYes + Apps + Enroll + Top10perc + Top25perc + 
##     F.Undergrad + P.Undergrad + Outstate + Room.Board + Personal + 
##     PhD + S.F.Ratio + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## - S.F.Ratio    1      99.2 101864 3199.2
## - F.Undergrad  1     141.3 101906 3199.5
## - Enroll       1     160.6 101926 3199.6
## - Top25perc    1     245.6 102011 3200.1
## - PhD          1     250.3 102015 3200.2
## - Top10perc    1     275.9 102041 3200.3
## <none>                     101765 3200.6
## - Personal     1     630.4 102395 3202.5
## - Expend       1     663.7 102429 3202.7
## - PrivateYes   1     685.8 102451 3202.8
## - Apps         1    1315.4 103080 3206.6
## - Room.Board   1    1754.1 103519 3209.3
## - Outstate     1    1778.5 103543 3209.4
## - P.Undergrad  1    2538.9 104304 3214.0
## - perc.alumni  1    5438.3 107203 3231.0
## 
## Step:  AIC=3199.24
## y_train ~ PrivateYes + Apps + Enroll + Top10perc + Top25perc + 
##     F.Undergrad + P.Undergrad + Outstate + Room.Board + Personal + 
##     PhD + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## - F.Undergrad  1     136.8 102001 3198.1
## - Enroll       1     163.1 102027 3198.2
## - Top25perc    1     238.7 102103 3198.7
## - PhD          1     262.6 102127 3198.8
## - Top10perc    1     275.1 102139 3198.9
## <none>                     101864 3199.2
## - PrivateYes   1     623.5 102488 3201.0
## - Personal     1     683.3 102547 3201.4
## - Expend       1    1012.9 102877 3203.4
## - Apps         1    1347.7 103212 3205.4
## - Outstate     1    1732.8 103597 3207.7
## - Room.Board   1    1740.8 103605 3207.8
## - P.Undergrad  1    2534.2 104398 3212.5
## - perc.alumni  1    5358.4 107223 3229.1
## 
## Step:  AIC=3198.07
## y_train ~ PrivateYes + Apps + Enroll + Top10perc + Top25perc + 
##     P.Undergrad + Outstate + Room.Board + Personal + PhD + perc.alumni + 
##     Expend
## 
##               Df Sum of Sq    RSS    AIC
## - Enroll       1      29.3 102030 3196.3
## - Top25perc    1     232.9 102234 3197.5
## - PhD          1     253.8 102255 3197.6
## - Top10perc    1     268.8 102270 3197.7
## <none>                     102001 3198.1
## - Personal     1     747.8 102749 3200.6
## - PrivateYes   1     762.5 102763 3200.7
## - Expend       1     988.4 102989 3202.1
## - Apps         1    1292.2 103293 3203.9
## - Room.Board   1    1721.7 103723 3206.5
## - Outstate     1    1776.4 103777 3206.8
## - P.Undergrad  1    2972.5 104973 3213.9
## - perc.alumni  1    5502.9 107504 3228.8
## 
## Step:  AIC=3196.25
## y_train ~ PrivateYes + Apps + Top10perc + Top25perc + P.Undergrad + 
##     Outstate + Room.Board + Personal + PhD + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## - Top25perc    1     241.7 102272 3195.7
## - Top10perc    1     263.9 102294 3195.9
## - PhD          1     268.1 102298 3195.9
## <none>                     102030 3196.3
## - Personal     1     724.9 102755 3198.7
## - PrivateYes   1     733.5 102764 3198.7
## - Expend       1    1026.2 103056 3200.5
## - Room.Board   1    1694.4 103725 3204.5
## - Outstate     1    1792.6 103823 3205.1
## - P.Undergrad  1    3004.2 105034 3212.3
## - Apps         1    4005.6 106036 3218.2
## - perc.alumni  1    5529.0 107559 3227.1
## 
## Step:  AIC=3195.72
## y_train ~ PrivateYes + Apps + Top10perc + P.Undergrad + Outstate + 
##     Room.Board + Personal + PhD + perc.alumni + Expend
## 
##               Df Sum of Sq    RSS    AIC
## <none>                     102272 3195.7
## - PhD          1     370.6 102643 3196.0
## - PrivateYes   1     719.4 102991 3198.1
## - Personal     1     736.3 103008 3198.2
## - Expend       1    1308.2 103580 3201.6
## - Room.Board   1    1725.5 103997 3204.1
## - Outstate     1    1820.9 104093 3204.7
## - Top10perc    1    2118.2 104390 3206.5
## - P.Undergrad  1    2981.6 105254 3211.6
## - Apps         1    4216.9 106489 3218.9
## - perc.alumni  1    5735.5 108007 3227.7
# Predykcja na danych testowych
x_test <- as.data.frame(x_test)  # Konwersja macierzy testowej na ramkę danych
ols_pred <- predict(stepwise_mod, newdata = x_test)
summary(stepwise_mod)$coefficients
##                  Estimate   Std. Error   t value     Pr(>|t|)
## (Intercept) 33.3222467245 3.4747006252  9.589962 2.201419e-20
## PrivateYes   3.7740985934 1.8204574735  2.073159 3.857600e-02
## Apps         0.0008993941 0.0001791899  5.019223 6.814264e-07
## Top10perc    0.1647836641 0.0463218480  3.557364 4.036245e-04
## P.Undergrad -0.0017216581 0.0004079227 -4.220550 2.807359e-05
## Outstate     0.0008331982 0.0002526161  3.298278 1.029290e-03
## Room.Board   0.0020796857 0.0006477270  3.210744 1.393386e-03
## Personal    -0.0017470704 0.0008329927 -2.097342 3.637366e-02
## PhD          0.0636885579 0.0428038725  1.487916 1.372890e-01
## perc.alumni  0.3207703658 0.0547984130  5.853643 7.851020e-09
## Expend      -0.0004122359 0.0001474575 -2.795626 5.342737e-03
OLS_coef=stepwise_mod$coefficients

Jak widać, finalnie również pozostało 11 istotnych zmiennych objaśniających. Następnie liczymy błąd MSE.

MSE_ols= mean((ols_pred - y_test)^2) # MSE dla OLS
print(paste("Wartość błędu MSE dla prognozy za pomocą OLS:",  MSE_ols))
## [1] "Wartość błędu MSE dla prognozy za pomocą OLS: 147.770118442805"
plot(stepwise_mod)

Wyniki

Na końcu należy porównać uzyskane wyniki za pomocą wyznaczonych miar błędu MSE.

data.frame(Model=c("Regresja grzbietowa", "Regresja Lasso", "Klasyczny OLS"),MSE=c(MSE_reg_g,MSE_reg_l,MSE_ols))
##                 Model      MSE
## 1 Regresja grzbietowa 143.3031
## 2      Regresja Lasso 150.1703
## 3       Klasyczny OLS 147.7701

Na podstawie wskzanych wartości można powiedzieć, że najlepszy rezultat prognozy uzyskano za pomocą regresji grzbietowej. Należy jednak dodać, że w tym przypadku zostały uwzględnione wszystkie predyktory, co może skutkować overfittingiem. Na drugim miejscu znalazła się klasyczna metoda najmniejszych kwadratów, natomiast wynik nie odbiega znacznie od regresji Lasso. Dodatkowo w metodzie OLS nie zostały zweryfikowane wszelkie testy związane z klasycznymi założeniami KNMK, które prawdopodbnie nie zostały całkowicie spełnione.

Predyktory

  • Które predyktory okazały się ważne w ostatecznym modelu (modelach)?
list(Reg_g_coef, lasso_coef_2, OLS_coef)
## [[1]]
##   (Intercept)    PrivateYes          Apps        Accept        Enroll 
## 35.4259636579  3.5360447063  0.0004891764  0.0003725834  0.0001803018 
##     Top10perc     Top25perc   F.Undergrad   P.Undergrad      Outstate 
##  0.0929335051  0.1061424028 -0.0001242029 -0.0013135925  0.0007248959 
##    Room.Board         Books      Personal           PhD      Terminal 
##  0.0017740362 -0.0022337145 -0.0018475835  0.0491413814 -0.0171970338 
##     S.F.Ratio   perc.alumni        Expend 
##  0.0425557858  0.2401109479 -0.0001708884 
## 
## [[2]]
##   (Intercept)    PrivateYes          Apps     Top10perc     Top25perc 
##  3.601812e+01  1.696896e+00  5.109904e-04  1.668854e-02  1.437067e-01 
##   P.Undergrad      Outstate    Room.Board      Personal   perc.alumni 
## -1.248776e-03  8.922760e-04  1.452065e-03 -1.539697e-03  2.523755e-01 
##        Expend 
## -5.372494e-06 
## 
## [[3]]
##   (Intercept)    PrivateYes          Apps     Top10perc   P.Undergrad 
## 33.3222467245  3.7740985934  0.0008993941  0.1647836641 -0.0017216581 
##      Outstate    Room.Board      Personal           PhD   perc.alumni 
##  0.0008331982  0.0020796857 -0.0017470704  0.0636885579  0.3207703658 
##        Expend 
## -0.0004122359

W modeli regresji grzbietowej nie została odrzucona żadna zmienna. W przypadku modelu regresji Lasso oraz OLS, zostało po 11 istotnych zmiennych. Oba modele różnią się wyłącznie 2 zmiennymi (Top25perc oraz PhD).

LS0tDQp0aXRsZTogJ05pZWtsYXN5Y3puZSBtZXRvZHkgc3RhdHlzdHlraScNCnN1YnRpdGxlOiAnUmVndWxhcnl6YWNqYScNCmRhdGU6ICJgciBTeXMuRGF0ZSgpYCINCmF1dGhvcjogIk1hdGV1c3ogU3Vyb3dpZWMiDQpvdXRwdXQ6DQogIGh0bWxfZG9jdW1lbnQ6IA0KICAgIHRoZW1lOiBjZXJ1bGVhbg0KICAgIGhpZ2hsaWdodDogdGV4dG1hdGUNCiAgICBmb250c2l6ZTogMTBwdA0KICAgIHRvYzogeWVzDQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgdG9jX2Zsb2F0Og0KICAgICAgY29sbGFwc2VkOiBubw0KICAgIGRmX3ByaW50OiBkZWZhdWx0DQogICAgdG9jX2RlcHRoOiA1DQplZGl0b3Jfb3B0aW9uczogDQogIG1hcmtkb3duOiANCiAgICB3cmFwOiA3Mg0KLS0tDQoNCg0KYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIGVjaG89RkFMU0V9DQpsaWJyYXJ5KElTTFIpDQpsaWJyYXJ5KGdsbW5ldCkNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KHRpZHlyKQ0KYGBgDQoNClRvIGxhYm9yYXRvcml1bSBuYSB0ZW1hdCBSZWdyZXNqaSBncnpiaWV0b3dlaiAoUmlkZ2UgUmVncmVzc2lvbiAtIFJSKSBpIExhc3NvIHcgUiBwb2Nob2R6aSB6ZSBzdHJvbiAyNTEtMjU1IGtzacSFxbxraSAiSW50cm9kdWN0aW9uIHRvIFN0YXRpc3RpY2FsIExlYXJuaW5nIHdpdGggQXBwbGljYXRpb25zIGluIFIiIGF1dG9yc3R3YSBHYXJldGhhIEphbWVzYSwgRGFuaWVsaSBXaXR0ZW4sIFRyZXZvcmEgSGFzdGllIGkgUm9iZXJ0YSBUaWJzaGlyYW5pLiBab3N0YcWCbyBvbm8gcG9ub3duaWUgemFpbXBsZW1lbnRvd2FuZSBqZXNpZW5pxIUgMjAxNiByb2t1IHcgZm9ybWFjaWUgYHRpZHl2ZXJzZWAgcHJ6ZXogQW1lbGnEmSBNY05hbWFyxJkgaSBSLiBKb3JkYW5hIENyb3VzZXJhIHcgU21pdGggQ29sbGVnZS4NCg0KVyB0eW0gdHlnb2RuaXUgb23Ds3dpbXkgZHdpZSBhbHRlcm5hdHl3bmUgZm9ybXkgcmVncmVzamkgbGluaW93ZWogendhbmUgKipyZWdyZXNqxIUgZ3J6YmlldG93xIUqKiBpICoqcmVncmVzasSFIExBU1NPKiouIFRlIGR3aWUgbWV0b2R5IHPEhSBwcnp5a8WCYWRhbWkgbWV0b2QgKipyZWd1bGFyeXphY2ppKiogbHViICoqem1uaWVqc3phbmlhKiosIHcga3TDs3J5Y2ggemFjaMSZY2Egc2nEmSBkbyB0ZWdvLCBhYnkgcGFyYW1ldHJ5IG1vZGVsdSBiecWCeSBtYcWCZS4gDQoNCg0KIyBSZWdyZXNqYSBHcnpiaWV0b3dhIGkgTGFzc28NCg0KDQpXeWtvcnp5c3RhbXkgcGFraWV0IGBnbG1uZXRgIHcgY2VsdSBwcnplcHJvd2FkemVuaWEgcmVncmVzamkgcmlkZ2UgaSBsYXNzby4gR8WCw7N3bsSFIGZ1bmtjasSFIHcgdHltIHBha2llY2llIGplc3QgYGdsbW5ldCgpYCwga3TDs3JhIG1vxbxlIGJ5xIcgdcW8eXRhIGRvIGRvcGFzb3dhbmlhIG1vZGVsaSByZWdyZXNqaSBncnpiaWV0b3dlaiwgbW9kZWxpIGxhc3NvIGkgaW5ueWNoLg0KDQpGdW5rY2phIHRhIG1hIG5pZWNvIGlubsSFIHNrxYJhZG5pxJkgbmnFvCBpbm5lIGZ1bmtjamUgZG9wYXNvd3VqxIVjZSBtb2RlbGUsIHoga3TDs3J5bWkgemV0a27EmWxpxZtteSBzacSZIGRvIHRlaiBwb3J5LiBXIHN6Y3plZ8OzbG5vxZtjaSwgbXVzaW15IHByemVrYXphxIcgbWFjaWVyeiAkeCQgamFrIHLDs3duaWXFvCB3ZWt0b3IgJHkkIGkgbmllIHXFvHl3YW15IHNrxYJhZG5pICR5IFxzaW0geCQuDQoNClphbmltIHByemVqZHppZW15IGRhbGVqLCB1cGV3bmlqbXkgc2nEmSBuYWpwaWVydywgxbxlIGJyYWt1asSFY2Ugd2FydG/Fm2NpIHpvc3RhxYJ5IHpvc3RhxYJ5IHVzdW5pxJl0ZSB6IGRhbnljaCwgamFrIG9waXNhbm8gdyBwb3ByemVkbmltIGxhYm9yYXRvcml1bS4NCg0KDQpgYGB7cn0NCkhpdHRlcnMgPSBuYS5vbWl0KEhpdHRlcnMpDQpgYGANCg0KVyByYXBvcmNpZSB0eW0gcHJ6ZXByb3dhZHppbXkgcmVncmVzasSZIGdyemJpZXRvd8SFIGkgbGFzc28sIGFieSBwcnpld2lkemllxIcgYFNhbGFyeWAgbmEgZGFueWNoIGBIaXR0ZXJzYC4NCg0KU2tvbmZpZ3VydWpteSBuYXN6ZSBkYW5lOg0KDQoNCmBgYHtyfQ0KeCA9IG1vZGVsLm1hdHJpeChTYWxhcnl+LiwgSGl0dGVycylbLC0xXSAjIHByenljaW5hbSBwaWVyd3N6xIUga29sdW1uxJkNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB6b3N0YXdpYW0gcHJlZHlrdG9yeQ0KeSA9IEhpdHRlcnMgJT4lDQogIHNlbGVjdChTYWxhcnkpICU+JQ0KICB1bmxpc3QoKSAlPiUNCiAgYXMubnVtZXJpYygpDQpgYGANCg0KRnVua2NqYSBgbW9kZWwubWF0cml4KClgIGplc3Qgc3pjemVnw7NsbmllIHByenlkYXRuYSBkbyB0d29yemVuaWEgJHgkOyBuaWUgdHlsa28gbmllIHR5bGtvIHR3b3J6eSBtYWNpZXJ6IG9kcG93aWFkYWrEhWPEhSAxOSBwcmVkeWt0b3JvbSwgYWxlIHLDs3duaWXFvCBhdXRvbWF0eWN6bmllIHByemVrc3p0YcWCY2Egd3N6ZWxraWUgem1pZW5uZSBqYWtvxZtjaW93ZSB3IHptaWVubmUgZHVtbXkuDQoNClRhIG9zdGF0bmlhIHfFgmHFm2Npd2/Fm8SHIGplc3Qgd2HFvG5hLCBwb25pZXdhxbwgYGdsbW5ldCgpYCBtb8W8ZSBwcnp5am1vd2HEhyB0eWxrbyBudW1lcnljem5lLCBpbG/Fm2Npb3dlIGRhbmUgd2VqxZtjaW93ZS4NCg0KIyMgQmlhcyB2cyBWYXJpYW5jZQ0KDQpXeWLDs3IgbW9kZWx1IHcgcHJvYmxlbWFjaCB1Y3plbmlhIG5hZHpvcm93YW5lZ28gd2nEhcW8ZSBzacSZIHogcmVhbGl6YWNqxIUgZHfDs2NoIHNwcnplY3pueWNoIGNlbMOzdzoNCg0KMS4pIE1vZGVsIHBvd2llbmllbiBiecSHIGRvYnJ6ZSBkb3Bhc293YW55IGRvIGRhbnljaCB1Y3rEhWN5Y2gsIGFieSB1Y2h3eWNpxIcgemFsZcW8bm/Fm8SHIHBvbWnEmWR6eSBkYW55bWkuDQoNCjIuKSBNb2RlbCBwb3dpbmllbiBkb2JyemUgcHJ6eWJsacW8YcSHIG5pZXpuYW5lIGRhbmUgKHphcGV3bmlhxIcgbWHFgnkgYsWCxIVkIGdlbmVyYWxpemFjamkpLg0KDQpNb2RlbGUgesWCb8W8b25lIGRvYmRyemUgZG9wYXNvd3VqxIUgc2nEmSBkbyBkYW55Y2ggd3lqxZtjaW93eWNoLCBhbGUgY2hhcmFrdGVyeXp1asSFIHNpxJkgZHXFvMSFIHptaWVubm/Fm2NpxIUgd2FydG/Fm2NpIHd5asWbY2lvd3ljaC4gUnl6eWtpZW0gamVzdCBuYWRtaWVybmUgZG9wYXNvd2FuaWUgPSBvdmVyZml0dGluZyENCg0KTW9kZWxlIHByb3N0c3plIHPEhSBvYmNpxIXFvG9uZSBkdcW8eW0gYsWCxJlkZW0gc3lzdGVtYXR5Y3pueSAoYmlhcykgaSBpY2ggemFzdG9zb3dhbmllIG5pZXNpZSByeXp5a28gbmlld3lzdGFyY3phasSFY2VnbyBkb3Bhc293YW5pYSAodW5kZXJmaXR0aW5nKSENCg0KU2vFgmFkbmlraWVtIGLFgsSZZMOzdyBnZW5lcmFsaXphY2ppIGplc3QgbmllcmVkdWtvd2FsbnkgYsWCxIVkIHp3acSFemFueSB6ZSB6bWllbm5vxZtjacSFIGRhbnljaC4NCg0KIyMgUmVndWxhcnl6YWNqYQ0KDQpEdcW8YSBsaWN6bmEgem1pZW5ueWNoIG9iamHFm25pYWrEhWN5Y2ggKHByZWR5a3RvcsOzdyk6IE1ldG9kYSBPTFMgbmllIGRhamUgamVkbm96bmFjem5lZ28gcm96d2nEhXphbmlhLCBnZHkgbWFjaWVyeiBYVFggbmllIGplc3Qgb2R3cmFjYWxuYSAodHpuLiBnZHkgem1pZW5uZSBvYmphxZtuaWFqxIVjZSBzxIUgbGluaW93byB6YWxlxbxuZSkuIA0KDQpUYWthIHN5dHVhY2phIG1vxbxlIG1pZcSHIG1pZWpzY2UgZ2R5IHptaWVubnljaCBvYmphxZtuaWFqxIVjeWNoIGplc3QgdHlsZSBzYW1vIGx1YiB3acSZY2VqIG5pxbwgb2JzZXJ3YWNqaS4NCg0KRHXFvGEgd2FydG/Fm8SHIM64aSBvem5hY3phIGR1xbzEhSB3cmHFvGxpd2/Fm8SHIGZ1bmtjamkgcmVncmVzamkgbmEgZHJvYm5lIGZsdWt0dWFjamUgY2VjaHkhDQoNCkxlcHN6eW0gcm96d2nEhXphbmllbSBqZXN0IGdvcnN6ZSBkb3Bhc293YW5pZSBkbyBkYW55Y2ggdWN6xIVjeWNoIHByenkgcsOzd25vY3plc255bSBvZ3JhbmljemVuaXUgcGFyYW1ldHLDs3cgxZt3aWFkY3rEhWN5Y2ggbyBwb3RlbmNqYWxuaWUgZHXFvHltIGLFgsSZZHppZSBnZW5lcmFsaXphY2ppLg0KDQoNCiMjIFJlZ3Jlc2phIEdyemJpZXRvd2ENCg0KIyMjIFdwcm93YWR6ZW5pZSANCg0KUmVncmVzamEgZ3J6YmlldG93YSAoYW5nLiBSaWRnZSByZWdyZXNzaW9uKSB0byB0ZWNobmlrYSByZWdyZXNqaSBsaW5pb3dlaiwga3TDs3JhIHdwcm93YWR6YSByZWd1bGFyeXphY2rEmSAkTF8yJCBkbyBlc3R5bWFjamkgd3Nww7PFgmN6eW5uaWvDs3cgbW9kZWx1LiBSZWd1bGFyeXphY2phICRMXzIkIHBvbGVnYSBuYSBkb2Rhbml1IGRvIGZ1bmtjamkgY2VsdSBrYXJ5IHByb3BvcmNqb25hbG5laiBkbyBrd2FkcmF0dSB3YXJ0b8WbY2kgd3Nww7PFgmN6eW5uaWvDs3cgcmVncmVzamkuDQoNClBvZHN0YXdvd8SFIGlkZcSFIHJlZ3Jlc2ppIGdyemJpZXRvd2VqIGplc3QgbWluaW1hbGl6YWNqYSBmdW5rY2ppIGNlbHUsIGt0w7NyYSBza8WCYWRhIHNpxJkgeiBkd8OzY2ggc2vFgmFkbmlrw7N3OiBixYLEmWR1IGRvcGFzb3dhbmlhIChzdW15IGt3YWRyYXTDs3cgcsOzxbxuaWMgcG9tacSZZHp5IHJ6ZWN6eXdpc3R5bWkgd2FydG/Fm2NpYW1pIG9kcG93aWVkemkgYSBwcnpld2lkeXdhbnltaSB3YXJ0b8WbY2lhbWkgbW9kZWx1KSBpIGthcnkgcmVndWxhcnl6YWN5am5laiAkTF8yJC4gDQoNCld6w7NyIGZ1bmtjamkgY2VsdSBkbGEgcmVncmVzamkgZ3J6YmlldG93ZWogbW/FvG5hIHByemVkc3Rhd2nEhyBqYWtvOiBNaW5pbWl6ZTogUlNTICsgJFxsYW1iZGEgXHxcYmV0YVx8XzJeMiQsIGdkemllOg0KDQotIFJTUyB0byBzdW1hIGt3YWRyYXTDs3cgcsOzxbxuaWMgcG9tacSZZHp5IHJ6ZWN6eXdpc3R5bWkgd2FydG/Fm2NpYW1pIG9kcG93aWVkemkgYSBwcnpld2lkeXdhbnltaSB3YXJ0b8WbY2lhbWkgbW9kZWx1IChixYLEhWQgZG9wYXNvd2FuaWEpLA0KDQotICRcbGFtYmRhJCAobGFtYmRhKSB0byBwYXJhbWV0ciByZWd1bGFyeXphY2ppLCBrdMOzcnkga29udHJvbHVqZSBzacWCxJkgcmVndWxhcnl6YWNqaSwNCg0KLSAkXHxcYmV0YVx8XzJeMiQgdG8gbm9ybWEgJExfMiQgd3Nww7PFgmN6eW5uaWvDs3cgcmVncmVzamkgcG9kbmllc2lvbmEgZG8ga3dhZHJhdHUuDQoNCkRvZGFuaWUga2FyeSByZWd1bGFyeXphY3lqbmVqICRMXzIkIHBvd29kdWplLCDFvGUgd3Nww7PFgmN6eW5uaWtpIHJlZ3Jlc2ppIHPEhSBza3VwaW9uZSB3b2vDs8WCIHplcmEsIGFsZSBuaWUgZG9rxYJhZG5pZSByw7N3bmUgemVydSAoY2h5YmEgxbxlICRcbGFtYmRhJD0wKS4gDQoNClJlZ3Jlc2phIGdyemJpZXRvd2Egem1uaWVqc3phIHdhcnRvxZtjaSB3c3DDs8WCY3p5bm5pa8OzdywgYWxlIG5pZSBwb3dvZHVqZSwgxbxlIHN0YWrEhSBzacSZIG9uZSByw7N3bmUgemVyby4gSW0gd2nEmWtzemEgd2FydG/Fm8SHICRcbGFtYmRhJCwgdHltIGJhcmR6aWVqIHPEhSAic2Npc2thbmUiIHdzcMOzxYJjenlubmlraSByZWdyZXNqaS4NCg0KUmVncmVzamEgZ3J6YmlldG93YSBqZXN0IHN6Y3plZ8OzbG5pZSBwcnp5ZGF0bmEsIGdkeSBtYW15IGRvIGN6eW5pZW5pYSB6IG1vZGVsZW0sIHcga3TDs3J5bSB3eXN0xJlwdWplIG5hZG1pZXJuYSB3aWVsb3d5bWlhcm93b8WbxIcgbHViIHd5c29raWUga29yZWxhY2plIG1pxJlkenkgem1pZW5ueW1pIG5pZXphbGXFvG55bWkuIA0KDQpQb3ByemV6IHptbmllanN6YW5pZSB3YXJ0b8WbY2kgd3Nww7PFgmN6eW5uaWvDs3csIHJlZ3Jlc2phIGdyemJpZXRvd2EgbW/FvGUgcG9tw7NjIHcgcmVkdWtjamkgd3DFgnl3dSBtYcWCbyBpc3RvdG55Y2ggY2VjaCwgcG9wcmF3acSHIHN0YWJpbG5vxZvEhyBtb2RlbHUgaSB6bW5pZWpzennEhyByeXp5a28gcHJ6ZXVjemVuaWEgKCoqb3ZlcmZpdHRpbmcqKikuDQoNCkplZG55bSB6ZSBzcG9zb2LDs3cga29udHJvbGkgesWCb8W8b25vxZtjaSBtb2RlbHUgamVzdCBwZW5hbGl6YWNqYSBqZWdvIHdpZWxrb8WbY2kuIE5hIHByenlrxYJhZCwgdyBwcm9ibGVtaWUgcmVncmVzamkgbGluaW93ZWo6DQoNCiQkDQpcbWluX3tcYmV0YSBcaW4gXG1hdGhiYntSfV5wfSBcc3VtX3tpPTF9Xm4gKHlfaSAtIHhfaV5cdG9wIFxiZXRhKV4yLA0KJCQNCg0KbW/FvGVteSBrb250cm9sb3dhxIcgd2llbGtvxZvEhyB3c3DDs8WCY3p5bm5pa8OzdyAkXGJldGEkLiBPY3p5d2nFm2NpZSB3aWVsa2/Fm8SHICRcYmV0YSQgbW/FvG5hIHpkZWZpbmlvd2HEhyBuYSByw7PFvG5lIHNwb3NvYnksIG5wLiBub3JtYS0yOiAkXHxcYmV0YVx8XzIkLCBub3JtYS0xOiAkXHxcYmV0YVx8XzEkIGN6eSBub3JtYS1uaWVza2/FhGN6b25vxZvEhzogJFx8XGJldGFcfF97XGluZnR5fSQuIA0KUmVncmVzamEgZ3J6YmlldG93YSB3acSFxbxlIHNpxJkgeiBrYXLEhSBkd8OzY2ggbm9ybToNCg0KJCQNClxtaW5fe1xiZXRhIFxpbiBcbWF0aGJie1J9XnB9IFxzdW1fe2k9MX1ebiAoeV9pIC0geF9pXlx0b3AgXGJldGEpXjIgKyBcbGFtYmRhIFx8XGJldGFcfF8yXjINCiQkDQoNCmdkemllICRcbGFtYmRhJCBqZXN0IHBhcmFtZXRyZW0ga29udHJvbHVqxIVjeW0gcG96aW9tIHJlZ3VsYXJ5emFjamkuIFphdXdhxbwsIMW8ZSAkWCQgdG8gbWFjaWVyeiAkbiQgbmEgJHAkIHd5bWlhcsOzdyB6IHdpZXJzemFtaTogJHhfaV5cdG9wJCwgb3JheiAkWSQgdG8gJG4kIG5hIDEgd2VrdG9yICR5X2kkLiBaYcWCw7PFvG15LCDFvGUgJFheXHRvcCBYICsgXGxhbWJkYSBJJCBqZXN0IG9kd3JhY2FsbmEsIG1hbXkgZG9rxYJhZG5lIHJvendpxIV6YW5pZSBwcm9ibGVtdSByZWdyZXNqaSBncnpiaWV0b3dlajoNCg0KJCQNClxoYXQgXGJldGFfe3JpZGdlfSA9IChYXlx0b3AgWCArIFxsYW1iZGEgSSleey0xfVheXHRvcCBZLg0KJCQNCg0KUHJ6eXBvbW5pam15LCDFvGUgcm96d2nEhXphbmllbSB6d3lrxYJlaiByZWdyZXNqaSBuYWptbmllanN6eWNoIGt3YWRyYXTDs3cgamVzdCAoemFrxYJhZGFqxIVjIG9kd3JhY2Fsbm/Fm8SHIG1hY2llcnp5ICRYXlx0b3AgWCQpOg0KDQokJA0KXGhhdCBcYmV0YV97b2xzfSA9IChYXlx0b3AgWCleey0xfVheXHRvcCBZLg0KJCQNCg0KRHdhIGZha3R5OiBraWVkeSAkXGxhbWJkYSBcdG8gMCQsICRcaGF0IFxiZXRhX3tyaWRnZX0gXHRvIFxoYXQgXGJldGFfe29sc30kOyBraWVkeSAkXGxhbWJkYSBcdG8gXGluZnR5JCwgJFxoYXQgXGJldGFfe3JpZGdlfSBcdG8gMCQuDQoNClcgc3pjemVnw7NsbnljaCBwcnp5cGFka2FjaCAkWCQgamVzdCBvcnRvZ29uYWxuYSAodHpuLiBrb2x1bW55ICRYJCBzxIUgb3J0b2dvbmFsbmUpLCBtYW15Og0KDQokJA0KXGhhdCBcYmV0YV97cmlkZ2V9ID0gXGZyYWN7XGhhdCBcYmV0YV97b2xzfX17MSArIFxsYW1iZGF9Lg0KJCQNCg0KV2lkemlteSB3acSZYywgxbxlIGVzdHltYXRvciBncnpiaWV0b3d5IG1hIGRvZGF0a293byAkMS8oMSArIFxsYW1iZGEpJCB0encuICJzaHJpbmthZ2UgZmFjdG9yIi4gVyB6d2nEhXprdSB6IHR5bSBuYSBlc3R5bWF0b3J6ZSBncnpiaWV0b3d5bSB3eXN0xJlwdWplIG9iY2nEhcW8bGl3b8WbxIcgKGJpYXMpLg0KDQojIyMgUHJ6eWvFgmFkDQoNCkZ1bmtjamEgYGdsbW5ldCgpYCBwb3NpYWRhIGFyZ3VtZW50IGFsZmEsIGt0w7NyeSBva3JlxZtsYSwgamFraSB0eXAgbW9kZWx1IGplc3QgZG9wYXNvd3l3YW55Lg0KDQpKZcWbbGkgYGFsZmEgPSAwYCB0byBkb3Bhc293eXdhbnkgamVzdCBtb2RlbCByZWdyZXNqaSBncnpiaWV0b3dlaiwgYSBqZcWbbGkgYGFsZmEgPSAxYCB0byBkb3Bhc293eXdhbnkgamVzdCBtb2RlbCBsYXNzby4gDQoNCk5hanBpZXJ3IGRvcGFzb3d1amVteSBtb2RlbCByZWdyZXNqaSBncnpiaWV0b3dlajoNCg0KDQpgYGB7cn0NCmdyaWQgPSAxMF5zZXEoMTAsIC0yLCBsZW5ndGggPSAxMDApDQpyaWRnZV9tb2QgPSBnbG1uZXQoeCwgeSwgYWxwaGEgPSAwLCBsYW1iZGEgPSBncmlkKQ0KYGBgDQoNCkRvbXnFm2xuaWUgZnVua2NqYSBgZ2xtbmV0KClgIHd5a29udWplIHJlZ3Jlc2rEmSBncnpiaWV0b3fEhSBkbGEgYXV0b21hdHljem5pZSB3eWJyYW5lZ28gd3licmFuZWdvIHpha3Jlc3Ugd2FydG/Fm2NpICRcbGFtYmRhJC4gSmVkbmFrxbxlLCB0dXRhaiB3eWJyYWxpxZtteSBpbXBsZW1lbnRhY2rEmSBmdW5rY2rEmSB3IHpha3Jlc2llIHdhcnRvxZtjaSBvZCAkXGxhbWJkYSA9IDEwXnsxMH0kIGRvICRcbGFtYmRhID0gMTBeey0yfSQsIHphc2Fkbmljem8gcG9rcnl3YWrEhWMgcGXFgmVuIHpha3JlcyBzY2VuYXJpdXN6eSBvZCBtb2RlbHUgemVyb3dlZ28gemF3aWVyYWrEhWNlZ28gdHlsa28gcHJ6ZWNod3l0LCBkbyBkb3Bhc293YW5pYSBuYWptbmllanN6ZWdvIGt3YWRyYXR1LiANCg0KSmFrIHdpZGHEhywgbW/FvGVteSByw7N3bmllxbwgb2JsaWN6ecSHIGRvcGFzb3dhbmllIG1vZGVsdSBkbGEga29ua3JldG5laiB3YXJ0b8WbY2kgJFxsYW1iZGEkLCBrdMOzcmEgbmllIGplc3QgamVkbsSFIHogb3J5Z2luYWxueWNoIHdhcnRvxZtjaSBzaWF0a2kuIA0KDQpaYXV3YcW8LCDFvGUgZG9tecWbbG5pZSBmdW5rY2phIGBnbG1uZXQoKWAgc3RhbmRhcnl6dWplIHptaWVubmUgdGFrLCBieSBiecWCeSB3IHRlaiBzYW1laiBza2FsaS4gQWJ5IHd5xYLEhWN6ecSHIHRvIGRvbXnFm2xuZSB1c3Rhd2llbmllLCB1xbx5aiBhcmd1bWVudHUgYHN0YW5kYXJkaXplID0gRkFMU0VgLg0KDQpaIGthxbxkxIUgd2FydG/Fm2NpxIUgJFxsYW1iZGEkIHp3acSFemFueSBqZXN0IHdla3RvciB3c3DDs8WCY3p5bm5pa8OzdyByZWdyZXNqaSBncnpiaWV0b3dlaiwgcHJ6ZWNob3d5d2FueSB3IG1hY2llcnp5LCBkbyBrdMOzcmVqIG1vxbxuYSB1enlza2HEhyBkb3N0xJlwIHByemV6IGBjb2VmKClgLiBXIHR5bSBwcnp5cGFka3UgamVzdCB0byBtYWNpZXJ6ICQyMCBcdGltZXMgMTAwJCwgeiAyMCB3aWVyc3phbWkgKHBvIGplZG55bSBkbGEga2HFvGRlZ28gcHJlZHlrdG9yYSwgcGx1cyBpbnRlcmNlcHQpIGkgMTAwIGtvbHVtbmFtaSAocG8gamVkbmVqIGRsYSBrYcW8ZGVqIHdhcnRvxZtjaSAkXGxhbWJkYSQpLg0KDQoNCmBgYHtyfQ0KZGltKGNvZWYocmlkZ2VfbW9kKSkNCnBsb3QocmlkZ2VfbW9kKSAgICAjIHd5a3JlcyB3c3DDs8WCY3p5bm5pa8Ozdw0KYGBgDQoNClNwb2R6aWV3YW15IHNpxJksIMW8ZSBvc3phY293YW5pYSB3c3DDs8WCY3p5bm5pa8OzdyBixJlkxIUgem5hY3puaWUgbW5pZWpzemUsIHcgc2Vuc2llIG5vcm15ICRsXzIkLCBnZHkgdcW8eXdhbmEgamVzdCBkdcW8YSB3YXJ0b8WbxIcgJFxsYW1iZGEkLCB3IHBvcsOzd25hbml1IHogbWHFgsSFIHdhcnRvxZtjacSFICRcbGFtYmRhJC4NCg0KT3RvIHdzcMOzxYJjenlubmlraSwgZ2R5ICRcbGFtYmRhID0gMTE0OTgkLCB3cmF6IHogaWNoIG5vcm3EhSAkbF8yJDoNCg0KDQpgYGB7cn0NCnJpZGdlX21vZCRsYW1iZGFbNTBdICAjIFd5xZt3aWV0bCA1MC10xIUgd2FydG/Fm8SHIGxhbWJkeQ0KY29lZihyaWRnZV9tb2QpWyw1MF0gIyBXecWbd2lldGwgd3Nww7PFgmN6eW5uaWtpIHp3acSFemFuZSB6IDUwLXTEhSB3YXJ0b8WbY2nEhSBsYW1iZHkNCnNxcnQoc3VtKGNvZWYocmlkZ2VfbW9kKVstMSw1MF1eMikpICMgT2JsaWN6IG5vcm3EmSBsMg0KYGBgDQoNCkRsYSBrb250cmFzdHUsIG90byB3c3DDs8WCY3p5bm5pa2ksIGdkeSAkXGxhbWJkYSA9IDcwNSQsIHdyYXogeiBpY2ggJGxfMiQgbm9ybcSFLiBad3LDs8SHIHV3YWfEmSBuYSB6bmFjem5pZSB3acSZa3N6xIUgbm9ybcSZICRsXzIkIHdzcMOzxYJjenlubmlrw7N3IHp3acSFemFueWNoIHogdMSFIG1uaWVqc3rEhSB3YXJ0b8WbY2nEhSAkXGxhbWJkYSQuDQoNCg0KYGBge3J9DQpyaWRnZV9tb2QkbGFtYmRhWzYwXSAjIFd5xZt3aWV0bCA2MC10xIUgd2FydG/Fm8SHIGxhbWJkeQ0KY29lZihyaWRnZV9tb2QpWyw2MF0gIyBXecWbd2lldGwgd3Nww7PFgmN6eW5uaWtpIHBvd2nEhXphbmUgeiA2MC10xIUgd2FydG/Fm8SHIGxhbWJkeQ0Kc3FydChzdW0oY29lZihyaWRnZV9tb2QpWy0xLDYwXV4yKSkgIyBPYmxpY3ogbm9ybcSZIGwyDQpgYGANCg0KRnVua2NqxJkgYHByZWRpY3QoKWAgbW/FvGVteSB3eWtvcnp5c3RhxIcgZG8gd2llbHUgY2Vsw7N3LiBOYSBwcnp5a8WCYWQsIG1vxbxlbXkgdXp5c2thxIcgd3Nww7PFgmN6eW5uaWtpIHJlZ3Jlc2ppIGdyemJpZXRvd2VqIGRsYSBub3dlaiB3YXJ0b8WbY2kgJFxsYW1iZGEkLCBwb3dpZWR6bXkgNTA6DQoNCg0KYGBge3J9DQpwcmVkaWN0KHJpZGdlX21vZCwgcyA9IDUwLCB0eXBlID0gImNvZWZmaWNpZW50cyIpWzE6MjAsXQ0KYGBgDQoNClBvZHppZWxpbXkgdGVyYXogcHLDs2JraSBuYSB6YmnDs3IgdHJlbmluZ293eSBpIHRlc3Rvd3kgdyBjZWx1IG9zemFjb3dhxIcgYsWCxIVkIHRlc3R1IHJlZ3Jlc2ppIGdyemJpZXRvd2VqIGkgbGFzc28uDQoNCg0KYGBge3J9DQpzZXQuc2VlZCgxKQ0KDQp0cmFpbiA9IEhpdHRlcnMgJT4lDQogIHNhbXBsZV9mcmFjKDAuNSkNCg0KdGVzdCA9IEhpdHRlcnMgJT4lDQogIHNldGRpZmYodHJhaW4pDQoNCnhfdHJhaW4gPSBtb2RlbC5tYXRyaXgoU2FsYXJ5fi4sIHRyYWluKVssLTFdDQp4X3Rlc3QgPSBtb2RlbC5tYXRyaXgoU2FsYXJ5fi4sIHRlc3QpWywtMV0NCg0KeV90cmFpbiA9IHRyYWluICU+JQ0KICBzZWxlY3QoU2FsYXJ5KSAlPiUNCiAgdW5saXN0KCkgJT4lDQogIGFzLm51bWVyaWMoKQ0KDQp5X3Rlc3QgPSB0ZXN0ICU+JQ0KICBzZWxlY3QoU2FsYXJ5KSAlPiUNCiAgdW5saXN0KCkgJT4lDQogIGFzLm51bWVyaWMoKQ0KYGBgDQoNCk5hc3TEmXBuaWUgZG9wYXNvd3VqZW15IG1vZGVsIHJlZ3Jlc2ppIGdyemJpZXRvd2VqIG5hIHpiaW9yemUgdHJlbmluZ293eW0gaSBvY2VuaWFteSBqZWdvIE1TRSBuYSB6YmlvcnplIHRlc3Rvd3ltLCB1xbx5d2FqxIVjICRcbGFtYmRhID0gNCQuIFp3csOzxIcgdXdhZ8SZIG5hIHXFvHljaWUgZnVua2NqaSBgcHJlZGljdCgpYC4gUG9ub3duaWU6IHR5bSByYXplbSBvdHJ6eW11amVteSBwcnpld2lkeXdhbmlhIGRsYSB6YmlvcnUgdGVzdG93ZWdvLCB6YXN0xJlwdWrEhWMgYHR5cGU9ImNvZWZmaWNpZW50cyJgIGFyZ3VtZW50ZW0gYG5ld3hgLg0KDQoNCmBgYHtyfQ0KcmlkZ2VfbW9kID0gZ2xtbmV0KHhfdHJhaW4sIHlfdHJhaW4sIGFscGhhPTAsIGxhbWJkYSA9IGdyaWQsIHRocmVzaCA9IDFlLTEyKQ0KcmlkZ2VfcHJlZCA9IHByZWRpY3QocmlkZ2VfbW9kLCBzID0gNCwgbmV3eCA9IHhfdGVzdCkNCm1lYW4oKHJpZGdlX3ByZWQgLSB5X3Rlc3QpXjIpDQpgYGANCg0KVGVzdG93ZSBNU0Ugd3lub3NpIDEzOTg1OC4gWmF1d2HFvCwgxbxlIGdkeWJ5xZtteSB6YW1pYXN0IHRlZ28gZG9wYXNvd2FsaSBwbyBwcm9zdHUgbW9kZWwgdHlsa28geiB3eXJhemVtIHdvbG55bSwgcHJ6ZXdpZHl3YWxpYnnFm215IGthxbxkxIUgb2JzZXJ3YWNqxJkgdGVzdG93xIUgdcW8eXdhasSFYyDFm3JlZG5pZWogeiBvYnNlcndhY2ppIHpiaW9ydSB0cmVuaW5nb3dlZ28uIFcgdGFraW0gcHJ6eXBhZGt1IG1vZ2xpYnnFm215IG9ibGljennEhyBNU0UgemVzdGF3dSB0ZXN0b3dlZ28gdyB0ZW4gc3Bvc8OzYjoNCg0KDQpgYGB7cn0NCm1lYW4oKG1lYW4oeV90cmFpbikgLSB5X3Rlc3QpXjIpDQpgYGANCg0KTW9nbGliecWbbXkgcsOzd25pZcW8IHV6eXNrYcSHIHRlbiBzYW0gd3luaWssIGRvcGFzb3d1asSFYyBtb2RlbCByZWdyZXNqaSBncnpiaWV0b3dlaiB6IGJhcmR6byBkdcW8xIUgd2FydG/Fm2NpxIUgJFxsYW1iZGEkLiBaYXV3YcW8LCDFvGUgYDFlMTBgIG96bmFjemEgJDEwXnsxMH0kLg0KDQoNCmBgYHtyfQ0KcmlkZ2VfcHJlZCA9IHByZWRpY3QocmlkZ2VfbW9kLCBzID0gMWUxMCwgbmV3eCA9IHhfdGVzdCkNCm1lYW4oKHJpZGdlX3ByZWQgLSB5X3Rlc3QpXjIpDQpgYGANCg0KVGFrIHdpxJljIGRvcGFzb3dhbmllIG1vZGVsdSByZWdyZXNqaSBncnpiaWV0b3dlaiB6ICRcbGFtYmRhID0gNCQgcHJvd2FkemkgZG8gem5hY3puaWUgbmnFvHN6ZWdvIHRlc3R1IE1TRSBuacW8IGRvcGFzb3dhbmllIG1vZGVsdSB6IHNhbXltIHByemVjaHd5dGVtLiANCg0KU3ByYXdkemlteSB0ZXJheiwgY3p5IGplc3QgamFrYcWbIGtvcnp5xZvEhyB6IHd5a29uYW5pYSByZWdyZXNqaSBncnpiaWV0b3dlaiB6ICRcbGFtYmRhID0gNCQgemFtaWFzdCBwbyBwcm9zdHUgd3lrb25hxIcgcmVncmVzasSZIG5ham1uaWVqc3p5Y2gga3dhZHJhdMOzdy4NCg0KUHJ6eXBvbW5pam15LCDFvGUgbmFqbW5pZWpzemEga3dhZHJhdHVyYSB0byBwbyBwcm9zdHUgcmVncmVzamEgZ3J6YmlldG93YSB6ICRcbGFtYmRhID0gMCQuDQoNCg0KXCogVXdhZ2E6IEFieSBgZ2xtbmV0KClgIGRhd2HFgiAqKmRva8WCYWRuZSAoZXhhY3QpKiogd3Nww7PFgmN6eW5uaWtpIG5ham1uaWVqc3plZ28ga3dhZHJhdHUsIGdkeSAkXGxhbWJkYSA9IDAkLCB1xbx5d2FteSBhcmd1bWVudHUgYGV4YWN0PVRgIHByenkgd3l3b8WCYW5pdSBmdW5rY2ppIGBwcmVkaWN0KClgLiBXIHByemVjaXdueW0gcmF6aWUsIGZ1bmtjamEgYHByZWRpY3QoKWAgYsSZZHppZSBpbnRlcnBvbG93YcSHIG5hZCBzaWF0a8SFIHdhcnRvxZtjaSAkXGxhbWJkYSQgdcW8eXTEhSB3IGRvcGFzb3dhbml1IG1vZGVsdSBgZ2xtbmV0KClgLCBkYWrEhWMgcHJ6eWJsacW8b25lIHd5bmlraS4gTmF3ZXQgZ2R5IHXFvHlqZW15IGBleGFjdCA9IFRgLCBwb3pvc3RhamUgbmlld2llbGthIHJvemJpZcW8bm/Fm8SHIG5hIHRyemVjaW0gbWllanNjdSBwbyBwcnplY2lua3UgbWnEmWR6eSB3eW5pa2FtaSBgZ2xtbmV0KClgLCBnZHkgJFxsYW1iZGEgPSAwJCBpIHd5asWbY2llbSB6IGBsbSgpYDsgamVzdCB0byBzcG93b2Rvd2FuZSBudW1lcnljem55bSBwcnp5YmxpxbxlbmllbSB6ZSBzdHJvbnkgYGdsbW5ldCgpYC4NCg0KDQpgYGB7cn0NCnJpZGdlX3ByZWQgPSBwcmVkaWN0KHJpZGdlX21vZCwgcyA9IDAsIG5ld3ggPSB4X3Rlc3QpDQptZWFuKChyaWRnZV9wcmVkIC0geV90ZXN0KV4yKQ0KDQpsbShTYWxhcnl+LiwgZGF0YSA9IHRyYWluKQ0KcHJlZGljdChyaWRnZV9tb2QsIHMgPSAwLCB0eXBlPSJjb2VmZmljaWVudHMiKVsxOjIwLF0NCmBgYA0KDQpXeWdsxIVkYSBuYSB0bywgxbxlIHJ6ZWN6eXdpxZtjaWUgcG9wcmF3aWFteSBzacSZIHcgc3Rvc3Vua3UgZG8gend5a8WCZWdvIG5ham1uaWVqc3plZ28ga3dhZHJhdHUhIA0KDQpVd2FnYTogb2fDs2xuaWUsIGplxZtsaSBjaGNlbXkgZG9wYXNvd2HEhyAobmllc3BlbmFsaXpvd2FueSkgbW9kZWwgbmFqbW5pZWpzenljaCBrd2FkcmF0w7N3LCB0byBwb3dpbm5pxZtteSB1xbx5xIcgZnVua2NqaSBgbG0oKWAsIHBvbmlld2HFvCB0YSBmdW5rY2phIGRvc3RhcmN6YSBiYXJkemllaiB1xbx5dGVjem55Y2ggd3lqxZtjaWEsIHRha2llIGphayBixYLEmWR5IHN0YW5kYXJkb3dlIGkgd2FydG/Fm2NpICRwJCBkbGEgd3Nww7PFgmN6eW5uaWvDs3cuDQoNClphbWlhc3QgYXJiaXRyYWxuaWUgd3liaWVyYcSHICRcbGFtYmRhID0gNCQsIGxlcGllaiBiecWCb2J5IHXFvHnEhyB3YWxpZGFjamkga3J6ecW8b3dlaiBkbyB3eWJvcnUgcGFyYW1ldHJ1IGRvc3Ryb2plbmlhICRcbGFtYmRhJC4gTW/FvGVteSB0byB6cm9iacSHIHXFvHl3YWrEhWMgd2J1ZG93YW5laiBmdW5rY2ppIHdhbGlkYWNqaSBrcnp5xbxvd2VqLCBgY3YuZ2xtbmV0KClgLiBEb215xZtsbmllIGZ1bmtjamEgdGEgd3lrb251amUgMTAta3JvdG7EhSB3YWxpZGFjasSZIGtyennFvG93xIUsIGNob8SHIG1vxbxuYSB0byB6bWllbmnEhyB1xbx5d2FqxIVjIGFyZ3VtZW50dSBhcmd1bWVudHUgYGZvbGRzYC4gWmF1d2HFvCwgxbxlIG5hanBpZXJ3IHVzdGF3aWFteSBsb3Nvd2Ugemlhcm5vLCBhYnkgbmFzemUgd3luaWtpIGJ5xYJ5IHBvd3RhcnphbG5lLCBwb25pZXdhxbwgd3liw7NyIGtyb3Rub8WbY2kgd2FsaWRhY2ppIGtyennFvG93ZWogamVzdCBsb3Nvd3kuDQoNCg0KYGBge3J9DQpzZXQuc2VlZCgxKQ0KY3Yub3V0ID0gY3YuZ2xtbmV0KHhfdHJhaW4sIHlfdHJhaW4sIGFscGhhID0gMCkgIyBEb3Bhc3VqIG1vZGVsIHJlZ3Jlc2ppIGdyemJpZXRvd2VqIG5hIGRhbnljaCB0cmVuaW5nb3d5Y2gNCmJlc3RsYW0gPSBjdi5vdXQkbGFtYmRhLm1pbiAgIyBXeWJpZXJ6IGxhbWTEmSwga3TDs3JhIG1pbmltYWxpenVqZSB0cmVuaW5nb3d5IE1TRSANCmJlc3RsYW0NCmBgYA0KDQpXaWR6aW15IHphdGVtLCDFvGUgd2FydG/Fm8SHICRcbGFtYmRhJCwga3TDs3JhIHBvd29kdWplIG5ham1uaWVqc3p5IGLFgsSFZCB3YWxpZGFjamkga3J6ecW8b3dlaiB0byAzMjYuIE1vxbxlbXkgcsOzd25pZcW8IHd5a3JlxZtsacSHIE1TRSBqYWtvIGZ1bmtjasSZICRcbGFtYmRhJDoNCg0KDQpgYGB7cn0NCnBsb3QoY3Yub3V0KSAjIE5hcnlzdWogd3lrcmVzIHRyZW5pbmdvd2VnbyBNU0UgamFrbyBmdW5rY2rEmSBsYW1iZGENCmBgYA0KDQpKYWtpIGplc3QgdGVzdG93eSBNU0UgendpxIV6YW55IHogdMSFIHdhcnRvxZtjacSFICRcbGFtYmRhJD8NCg0KDQpgYGB7cn0NCnJpZGdlX3ByZWQgPSBwcmVkaWN0KHJpZGdlX21vZCwgcyA9IGJlc3RsYW0sIG5ld3ggPSB4X3Rlc3QpICMgVcW8eWogbmFqbGVwc3plaiBsYW1iZHkgZG8gcHJ6ZXdpZHl3YW5pYSBkYW55Y2ggdGVzdG93eWNoDQptZWFuKChyaWRnZV9wcmVkIC0geV90ZXN0KV4yKSAjIE9ibGljeiB0ZXN0b3dlIE1TRQ0KYGBgDQoNClN0YW5vd2kgdG8gZGFsc3rEhSBwb3ByYXfEmSB3IHN0b3N1bmt1IGRvIHRlc3Rvd2VnbyBNU0UsIGt0w7NyZSB1enlza2FsacWbbXkgdcW8eXdhasSFYyAkXGxhbWJkYSA9IDQkLiBPc3RhdGVjem5pZSwgcG9ub3duaWUgd3l6bmFjemFteSBuYXN6IG1vZGVsIHJlZ3Jlc2ppIGdyemJpZXRvd2VqIG5hIHBlxYJueW0gemVzdGF3aWUgZGFueWNoLCB1xbx5d2FqxIVjIHdhcnRvxZtjaSAkXGxhbWJkYSQgd3licmFuZWogdyB3YWxpZGFjamkga3J6ecW8b3dlaiwgaSBzcHJhd2R6YW15IG9zemFjb3dhbmlhIHdzcMOzxYJjenlubmlrw7N3Lg0KDQoNCmBgYHtyfQ0Kb3V0ID0gZ2xtbmV0KHgsIHksIGFscGhhID0gMCkgIyBEb3Bhc3VqIG1vZGVsIHJlZ3Jlc2ppIGdyemJpZXRvd2VqIGRvIHBlxYJuZWdvIHpiaW9ydSBkYW55Y2gNCnByZWRpY3Qob3V0LCB0eXBlID0gImNvZWZmaWNpZW50cyIsIHMgPSBiZXN0bGFtKVsxOjIwLF0gIyBXecWbd2lldGxhbmllIHdzcMOzxYJjenlubmlrw7N3IHByenkgdcW8eWNpdSBsYW1iZGEgd3licmFuZWdvIHByemV6IENWDQpgYGANCg0KWmdvZG5pZSB6IG9jemVraXdhbmlhbWksIMW8YWRlbiB6ZSB3c3DDs8WCY3p5bm5pa8OzdyBuaWUgamVzdCBkb2vFgmFkbmllIHplcm93eSAtIHJlZ3Jlc2phIGdyemJpZXRvd2EgbmllIGRva29udWplIHNlbGVrY2ppIHptaWVubnljaCENCg0KIyMgUmVncmVzamEgTGFzc28NCg0KIyMjIFdwcm93YWR6ZW5pZQ0KDQpaYW1pYXN0IHJlZ3VsYXJ5emFjamkgJExfMiQsIExBU1NPIHXFvHl3YSBwZW5hbGl6YWNqaSAkTF8xJCwgdG8gem5hY3p5Og0KDQokJA0KXG1pbl97XGJldGEgXGluIFxtYXRoYmJ7Un1ecH0gXHN1bV97aT0xfV5uICh5X2kgLSB4X2leXHRvcCBcYmV0YSleMiArIFxsYW1iZGEgXHxcYmV0YVx8XzEuIA0KJCQNCg0KWmUgd3pnbMSZZHUgbmEgY2hhcmFrdGVyIG5vcm15ICRMXzEkLCBMQVNTTyBtYSB0ZW5kZW5jasSZIGRvIGRhd2FuaWEgYmFyZHppZWogcnphZGtpY2ggcm96d2nEhXphxYQgbmnFvCByZWdyZXNqYSBncnpiaWV0b3dhLiBKZXN0IHRvIHR5cG93byB1xbx5dGVjem5lIHcgdXN0YXdpZW5pYWNoIHdpZWxvd3ltaWFyb3d5Y2gsIGdkeSBwcmF3ZHppd3kgbW9kZWwgamVzdCB3IHJ6ZWN6eXdpc3RvxZtjaSBuaXNrb3d5bWlhcm93eW0gb3NhZHplbmllbS4NCg0KTW9kZWwgcmVncmVzamkgbGFzc28gem9zdGHFgiBwaWVyd290bmllIG9wcmFjb3dhbnkgdyAxOTg5IHJva3UuIEplc3QgdG8gYWx0ZXJuYXR5d2EgZGxhIGtsYXN5Y3puZWdvIG9zemFjb3dhbmlhIG1ldG9kxIUgbmFqbW5pZWpzenljaCBrd2FkcmF0w7N3LCBrdMOzcmEgdW5pa2Egd2llbHUgcHJvYmxlbcOzdyB6IG5hZG1pZXJueW0gZG9wYXNvd2FuaWVtICgqKm92ZXJmaXR0aW5naWVtKiopLCBnZHkgbWFteSBkdcW8xIUgbGljemLEmSBuaWV6YWxlxbxueWNoIHptaWVubnljaC4gDQoNClJlZ3Jlc2phIExhc3NvIChMZWFzdCBBYnNvbHV0ZSBTaHJpbmthZ2UgYW5kIFNlbGVjdGlvbiBPcGVyYXRvcikgdG8gdGVjaG5pa2EgcmVncmVzamkgbGluaW93ZWogc3Rvc293YW5hIGRvIG9zemFjb3dhbmlhIHdzcMOzxYJjenlubmlrw7N3IG1vZGVsdSwga3TDs3JhIHdwcm93YWR6YSByZWd1bGFyeXphY2rEmSAkTF8xJC4gUmVndWxhcnl6YWNqYSBMMSBwb2xlZ2EgbmEgZG9kYW5pdSBkbyBmdW5rY2ppIGNlbHUga2FyeSBwcm9wb3Jjam9uYWxuZWogZG8gd2FydG/Fm2NpIGJlend6Z2zEmWRuZWogd3Nww7PFgmN6eW5uaWvDs3cgcmVncmVzamkuDQoNClJlZ3Jlc2phIExhc3NvIG1hIHpkb2xub8WbxIcgZG8gamVkbm9jemVzbmVnbyB3eWtvbmFuaWEgc2VsZWtjamkgY2VjaCBpIHJlZ3VsYXJ5emFjamksIGNvIG96bmFjemEsIMW8ZSBtb8W8ZSBwb23Ds2MgdyBpZGVudHlmaWthY2ppIG5hamJhcmR6aWVqIGlzdG90bnljaCBjZWNoIG1vZGVsdSwgYSB0YWvFvGUgem1uaWVqc3p5xIcgd3DFgnl3IG1uaWVqIGlzdG90bnljaCBjZWNoLg0KDQpQb2RzdGF3b3d5bSBjZWxlbSByZWdyZXNqaSBMYXNzbyBqZXN0IG1pbmltYWxpemFjamEgZnVua2NqaSBjZWx1LCBrdMOzcmEgc2vFgmFkYSBzacSZIHogZHfDs2NoIHNrxYJhZG5pa8OzdzogYsWCxJlkdSBkb3Bhc293YW5pYSAoc3VteSBrd2FkcmF0w7N3IHLDs8W8bmljIHBvbWnEmWR6eSByemVjenl3aXN0eW1pIHdhcnRvxZtjaWFtaSBvZHBvd2llZHppIGEgcHJ6ZXdpZHl3YW55bWkgd2FydG/Fm2NpYW1pIG1vZGVsdSkgaSBrYXJ5IHJlZ3VsYXJ5emFjeWpuZWogJExfMSQuIA0KDQpXesOzciBmdW5rY2ppIGNlbHUgZGxhIHJlZ3Jlc2ppIExhc3NvIG1vxbxlIGJ5xIcgcHJ6ZWRzdGF3aW9ueSBqYWtvOiBNaW5pbWl6ZTogUlNTICsgJFxsYW1iZGEgXHxcYmV0YVx8XzEkLCBnZHppZToNCg0KLSBSU1MgdG8gc3VtYSBrd2FkcmF0w7N3IHLDs8W8bmljIHBvbWnEmWR6eSByemVjenl3aXN0eW1pIHdhcnRvxZtjaWFtaSBvZHBvd2llZHppIGEgcHJ6ZXdpZHl3YW55bWkgd2FydG/Fm2NpYW1pIG1vZGVsdSAoYsWCxIVkIGRvcGFzb3dhbmlhKSwNCg0KLSAkXGxhbWJkYSQgKGxhbWJkYSkgdG8gcGFyYW1ldHIgcmVndWxhcnl6YWNqaSwga3TDs3J5IGtvbnRyb2x1amUgc2nFgsSZIHJlZ3VsYXJ5emFjamksIGEgJFx8XGJldGFcfF8xJCB0byBub3JtYSAkTF8xJCB3c3DDs8WCY3p5bm5pa8OzdyByZWdyZXNqaS4NCg0KRG9kYW5pZSBrYXJ5IHJlZ3VsYXJ5emFjeWpuZWogJExfMSQgcG93b2R1amUsIMW8ZSBuaWVrdMOzcmUgd3Nww7PFgmN6eW5uaWtpIHJlZ3Jlc2ppIHN0YWrEhSBzacSZIHLDs3duZSB6ZXJvLCBjbyBwcm93YWR6aSBkbyBzZWxla2NqaSBjZWNoLiBJbSB3acSZa3N6YSB3YXJ0b8WbxIcgJFxsYW1iZGEkLCB0eW0gd2nEmWtzemEgamVzdCB0ZW5kZW5jamEgZG8gcmVkdWtjamkgd3Nww7PFgmN6eW5uaWvDs3cgZG8gemVyYSwgcHJvd2FkesSFYyBkbyBiYXJkemllaiByemFka2llZ28gbW9kZWx1IHogbW5pZWpzesSFIGxpY3pixIUgY2VjaC4NCg0KUmVncmVzamEgTGFzc28gamVzdCBwcnp5ZGF0bmEgdyBwcnp5cGFka2FjaCwgZ2R5IG1hbXkgZG8gY3p5bmllbmlhIHogd2llbG9tYSBjZWNoYW1pLCB6IGt0w7NyeWNoIG5pZWt0w7NyZSBtb2fEhSBiecSHIG5pZWlzdG90bmUuIE1vxbxlIHBvbcOzYyB3IGlkZW50eWZpa2FjamkgaXN0b3RueWNoIGNlY2gsIHJlZHVrY2ppIG5hZG1pYXJ1IGRhbnljaCBpIHp3acSZa3N6ZW5pdSBpbnRlcnByZXRvd2Fsbm/Fm2NpIG1vZGVsdS4NCg0KDQojIyMgUHJ6eWvFgmFkDQoNClpvYmFjenlsacWbbXksIMW8ZSByZWdyZXNqYSBncnpiaWV0b3dhIHogbcSFZHJ5bSB3eWJvcmVtICRcbGFtYmRhJCBtb8W8ZSBwcnpld3nFvHN6YcSHIG1ldG9kxJkgbmFqbW5pZWpzenljaCBrd2FkcmF0w7N3LCBqYWsgcsOzd25pZcW8IG1vZGVsIHplcm93eSBuYSB6YmlvcnplIGRhbnljaCBIaXR0ZXJzLiANCg0KVGVyYXogem9iYWN6bXksIGN6eSBsYXNzbyBtb8W8ZSBkYcSHIGFsYm8gZG9rxYJhZG5pZWpzenksIGFsYm8gYmFyZHppZWogaW50ZXJwcmV0b3dhbG55IG1vZGVsIG5pxbwgcmVncmVzamEgZ3J6YmlldG93YS4gDQoNClcgY2VsdSBkb3Bhc293YW5pYSBtb2RlbHUgbGFzc28sIHBvIHJheiBrb2xlam55IHXFvHl3YW15IGZ1bmtjamkgYGdsbW5ldCgpYCwgamVkbmFrIHR5bSByYXplbSB1xbx5d2FteSBhcmd1bWVudHUgYGFscGhhPTFgLiBQb3phIHTEhSB6bWlhbsSFIHBvc3TEmXB1amVteSB0YWsgc2FtbyBqYWsgdyBwcnp5cGFka3UgZG9wYXNvd3l3YW5pYSBtb2RlbHUgcmVncmVzamkgZ3J6YmlldG93ZWo6DQoNCg0KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0NCmxhc3NvX21vZCA9IGdsbW5ldCh4X3RyYWluLCANCiAgICAgICAgICAgICAgICAgICB5X3RyYWluLCANCiAgICAgICAgICAgICAgICAgICBhbHBoYSA9IDEsIA0KICAgICAgICAgICAgICAgICAgIGxhbWJkYSA9IGdyaWQpICMgRG9wYXN1aiBtb2RlbCBsYXNzbyBkbyBkYW55Y2ggdHJlbmluZ293eWNoDQoNCnBsb3QobGFzc29fbW9kKSAgICAjIFd5a3JlxZtsIHdzcMOzxYJjenlubmlraQ0KYGBgDQoNClphdXdhxbxteSwgxbxlIG5hIHd5a3Jlc2llIHdzcMOzxYJjenlubmlrw7N3LCB3IHphbGXFvG5vxZtjaSBvZCB3eWJvcnUgZG9zdHJvamVuaWEgcGFyYW1ldHJ1LCBuaWVrdMOzcmUgemUgd3Nww7PFgmN6eW5uaWvDs3cgc8SFIGRva8WCYWRuaWUgcsOzd25lIHplcnUuIFRlcmF6IHByemVwcm93YWR6aW15IHdhbGlkYWNqxJkga3J6ecW8b3fEhSBpIG9ibGljenlteSB6d2nEhXphbnkgeiBuacSFIGLFgsSFZCB0ZXN0dToNCg0KDQpgYGB7cn0NCnNldC5zZWVkKDEpDQpjdi5vdXQgPSBjdi5nbG1uZXQoeF90cmFpbiwgeV90cmFpbiwgYWxwaGEgPSAxKSAjIERvcGFzdWogbW9kZWwgbGFzc28gZG8gZGFueWNoIHRyZW5pbmdvd3ljaA0KcGxvdChjdi5vdXQpICMgTmFyeXN1aiB3eWtyZXMgTVNFIGRsYSBwcsOzYnkgdWN6xIVjZWogamFrbyBmdW5rY2rEmSBsYW1iZGENCmJlc3RsYW0gPSBjdi5vdXQkbGFtYmRhLm1pbiAjIFd5YmllcnogbGFtZMSZLCBrdMOzcmEgbWluaW1hbGl6dWplIE1TRSB3IHByw7NiaWUgdWN6xIVjZWoNCmxhc3NvX3ByZWQgPSBwcmVkaWN0KGxhc3NvX21vZCwgcyA9IGJlc3RsYW0sIG5ld3ggPSB4X3Rlc3QpICMgVcW8eWogbmFqbGVwc3plaiBsYW1iZHkgZG8gcHJ6ZXdpZHl3YW5pYSBkYW55Y2ggdGVzdG93eWNoDQptZWFuKChsYXNzb19wcmVkIC0geV90ZXN0KV4yKSAjIE9ibGljeiBNU0UgdyBwcsOzYmllIHRlc3Rvd2VqDQpgYGANCg0KSmVzdCB0byB6bmFjem5pZSBuacW8c3plIE1TRSB6YmlvcnUgdGVzdG93ZWdvIG5pxbwgbW9kZWx1IHplcm93ZWdvIGkgbW9kZWx1IG5ham1uaWVqc3p5Y2gga3dhZHJhdMOzdywgaSBiYXJkem8gcG9kb2JueSBkbyBNU0UgdGVzdHUgcmVncmVzamkgZ3J6YmlldG93ZWogeiAkXGxhbWJkYSQgd3licmFuZWogcHJ6ZXogd2FsaWRhY2rEmSBrcnp5xbxvd8SFLg0KDQpKZWRuYWvFvGUgbGFzc28gbWEgaXN0b3RuxIUgcHJ6ZXdhZ8SZIG5hZCByZWdyZXNqxIUgZ3J6YmlldG93xIUgdyB0eW0sIMW8ZSB3eW5pa293ZSBvc3phY293YW5pYSB3c3DDs8WCY3p5bm5pa8OzdyBzxIUgcnphZGtpZS4gVHV0YWogd2lkemlteSwgxbxlIDEyIHogMTkgb3N6YWNvd2HFhCB3c3DDs8WCY3p5bm5pa8OzdyBqZXN0IGRva8WCYWRuaWUgemVyb3d5Y2g6DQoNCg0KYGBge3J9DQpvdXQgPSBnbG1uZXQoeCwgeSwgYWxwaGEgPSAxLCBsYW1iZGEgPSBncmlkKSAjIERvcGFzdWogbW9kZWwgbGFzc28gZG8gcGXFgm5lZ28gemJpb3J1IGRhbnljaA0KbGFzc29fY29lZiA9IHByZWRpY3Qob3V0LCB0eXBlID0gImNvZWZmaWNpZW50cyIsIHMgPSBiZXN0bGFtKVsxOjIwLF0gIyBXecWbd2lldGxhbmllIHdzcMOzxYJjenlubmlrw7N3IHByenkgdcW8eWNpdSBsYW1iZGEgd3licmFuZWdvIHByemV6IENWDQpsYXNzb19jb2VmDQpgYGANCg0KV3liaWVyYWrEhWMgdHlsa28gcHJlZHlrdG9yeSBvIG5pZXplcm93eWNoIHdzcMOzxYJjenlubmlrYWNoIHdpZHppbXksIMW8ZSBtb2RlbCBsYXNzbyB6ICRcbGFtYmRhJCB3eWJyYW55bSBwcnpleiB3YWxpZGFjasSZIGtyennFvG93xIUgemF3aWVyYSB0eWxrbyBzaWVkZW0gem1pZW5ueWNoOg0KDQoNCmBgYHtyfQ0KbGFzc29fY29lZltsYXNzb19jb2VmICE9IDBdICMgV3nFm3dpZXRsYW5pZSB0eWxrbyBuaWV6ZXJvd3ljaCB3c3DDs8WCY3p5bm5pa8Ozdw0KYGBgDQoNCg0KIyBUd29qYSBrb2xlaiENCg0KVGVyYXogbmFkc3plZMWCIGN6YXMgbmEgcHJ6ZXRlc3Rvd2FuaWUgdHljaCBtZXRvZCAocmVncmVzamEgZ3J6YmlldG93YSBpIGxhc3NvKSBvcmF6IG1ldG9kIG9jZW55ICh6ZXN0YXcgd2FsaWRhY3lqbnksIHdhbGlkYWNqYSBrcnp5xbxvd2EpIG5hIGlubnljaCB6YmlvcmFjaCBkYW55Y2guIE1vxbxlc3ogcHJhY293YcSHIHogemVzcG/FgmVtIG5hZCB0xIUgY3rEmcWbY2nEhSBsYWJvcmF0b3JpdW0uDQoNCk1vxbxlc3ogdcW8ecSHIGRvd29sbmVnbyB6YmlvcnUgZGFueWNoIHphd2FydGVnbyB3ICoqSVNMUioqIGx1YiB3eWJyYcSHIGplZGVuIHogcGFraWV0w7N3IGRhbnljaCBuYSBLYWdnbGUvRGF0YSBXb3JsZCBpdHAuICh6bWllbm5hIHphbGXFvG5hIG11c2kgYnnEhyBjacSFZ8WCYSkuIA0KDQpQb2JpZXJ6IHpiacOzciBkYW55Y2ggaSBzcHLDs2J1aiBva3JlxZtsacSHIG9wdHltYWxueSB6ZXN0YXcgcGFyYW1ldHLDs3csIGt0w7NyZSBuYWxlxbx5IHXFvHnEhyBkbyBqZWdvIG1vZGVsb3dhbmlhIQ0KQWJ5IHphbGljennEhyB0byBsYWJvcmF0b3JpdW0sIHphbWllxZvEhyBvZHBvd2llZHppIG5hIG5hc3TEmXB1asSFY2UgcHl0YW5pYToNCg0KIyMgWmJpw7NyIGRhbnljaA0KDQotIEt0w7NyeSB6YmnDs3IgZGFueWNoIHd5YnJhxYJlxZs/DQogDQpXeWJyYW55IGRhdGFzZToNClN0YXR5c3R5a2kgZGxhIGR1xbxlaiBsaWN6YnkgYW1lcnlrYcWEc2tpY2ggc3prw7PFgiB3ecW8c3p5Y2ggeiB3eWRhbmlhIFVTIE5ld3MgYW5kIFdvcmxkIFJlcG9ydCB6IDE5OTUgcm9rdS4NCg0KDQpgYGB7cn0NCiMgV3licmFueSBkYXRhc2U6DQojIFN0YXR5c3R5a2kgZGxhIGR1xbxlaiBsaWN6YnkgYW1lcnlrYcWEc2tpY2ggc3prw7PFgiB3ecW8c3p5Y2ggeiB3eWRhbmlhIFVTIE5ld3MgYW5kIFdvcmxkIFJlcG9ydCB6IDE5OTUgcm9rdS4NCg0KZGF0YSgiQ29sbGVnZSIpDQpoZWFkKENvbGxlZ2UpDQoNCmBgYA0KDQojIyBabWllbm5hIHphbGXFvG5hDQotIEpha2EgYnnFgmEgVHdvamEgem1pZW5uYSB6YWxlxbxuYSAodHpuLiBjbyBwcsOzYm93YcWCZcWbIG1vZGVsb3dhxIcpPw0KDQpXeWJyYW5hIHptaWVubmEgb2JqYcWbbmlhbmEgLSBXc2thxbpuaWsgdWtvxYRjemVuaWEgc3R1ZGnDs3cNCg0KYGBge3J9DQoNCnkgPSBDb2xsZWdlICU+JQ0KICBzZWxlY3QoR3JhZC5SYXRlKSAlPiUNCiAgdW5saXN0KCkgJT4lDQogIGFzLm51bWVyaWMoKQ0KDQp4ID0gbW9kZWwubWF0cml4KEdyYWQuUmF0ZX4uLCBDb2xsZWdlKVssLTFdDQoNCg0KYGBgDQoNCiMjIFJlZ3Jlc2phIGdyemJpZXRvd2EsIExhc3NvLCBPTFMNCi0gQ3p5IG9jemVraXdhxYJlxZssIMW8ZSByZWdyZXNqYSBncnpiaWV0b3dhIGLEmWR6aWUgbGVwc3phIG9kIGxhc3NvLCBjenkgb2R3cm90bmllPyBKYWsgd3lwYWRhIHcgc3Rvc3Vua3UgZG8gT0xTPyBQb2thxbwgb2Rwb3dpZWRuaWUgcmFwb3J0eSwgbWlhcnkgZG9wYXNvd2FuaWEgaSBrcsOzdGtvIGplIG9tw7N3IChwb3LDs3duYWopLg0KIA0KIFcgcGllcndzemVqIGtvbGVqbm9zY2kgbmFsZcW8eSBwb2R6aWVsacSHIHByw7Nia2kgbmEgemJpw7NyIHRyZW5pbmdvd3kgaSB0ZXN0b3d5IHcgY2VsdSBvc3phY293YcSHIGLFgsSFZCB0ZXN0dSByZWdyZXNqaSBncnpiaWV0b3dlaiBpIGxhc3NvIG9yYXogT0xTLg0KIA0KYGBge3J9DQojIFphc3Rvc293YW55IHpvc3RhxYIgc3Rvc3VuZWsgcHLDs2J5IHRyZW5pbmdvd2VqIGRvIHRlc3Rvd2VqIDgwLzIwDQpzZXQuc2VlZCgxKQ0KDQp0cmFpbiA9IENvbGxlZ2UgJT4lDQogIHNhbXBsZV9mcmFjKDAuOCkgDQoNCnRlc3QgPSBDb2xsZWdlICU+JQ0KICBzZXRkaWZmKHRyYWluKQ0KDQp4X3RyYWluID0gbW9kZWwubWF0cml4KEdyYWQuUmF0ZX4uLCB0cmFpbilbLC0xXQ0KeF90ZXN0ID0gbW9kZWwubWF0cml4KEdyYWQuUmF0ZX4uLCB0ZXN0KVssLTFdDQoNCnlfdHJhaW4gPSB0cmFpbiAlPiUNCiAgc2VsZWN0KEdyYWQuUmF0ZSkgJT4lDQogIHVubGlzdCgpICU+JQ0KICBhcy5udW1lcmljKCkNCg0KeV90ZXN0ID0gdGVzdCAlPiUNCiAgc2VsZWN0KEdyYWQuUmF0ZSkgJT4lDQogIHVubGlzdCgpICU+JQ0KICBhcy5udW1lcmljKCkNCg0KYGBgDQogDQojIyMgMS4gUmVncmVzamEgZ3J6YmlldG93YQ0KDQpXIHBpZXJ3c3plaiBrb2xlam5vxZtjaSBwcnpldGVzdG93YW5hIHpvc3RhbmllIHJlZ3Jlc2phIGdyemJpZXRvd2EgKGFsZmE9MCkNCiANCmBgYHtyfQ0KDQpncmlkID0gMTBec2VxKDEwLCAtMiwgbGVuZ3RoID0gMTAwKQ0KcmlkZ2VfbW9kID0gZ2xtbmV0KHgsIHksIGFscGhhID0gMCwgbGFtYmRhID0gZ3JpZCkNCmRpbShjb2VmKHJpZGdlX21vZCkpDQpwbG90KHJpZGdlX21vZCkNCmBgYA0KDQpOYXN0xJlwbmllIGlkZW50eWZpa3VqZW15IHdhcnRvxZvEhyBsYW1iZHksIGt0w7NyYSBuYWpiYXJkemllaiBtaW5pbWFsaXp1amUgYsWCxIVkIE1TRQ0KDQpgYGB7cn0NCnNldC5zZWVkKDEpDQpjdi5vdXQgPSBjdi5nbG1uZXQoeF90cmFpbiwgeV90cmFpbiwgYWxwaGEgPSAwKSAjIGRvcGFzb3dhbmllIG1vZGVsdSByZWdyZXNqaSBncnpiaWV0b3dlaiBuYSBkYW55Y2ggdHJlbmluZ293eWNoDQpiZXN0bGFtID0gY3Yub3V0JGxhbWJkYS5taW4gICMgV3liaWVyeiBsYW1kxJksIGt0w7NyYSBtaW5pbWFsaXp1amUgdHJlbmluZ293eSBNU0UgDQpiZXN0bGFtDQpwbG90KGN2Lm91dCkNCg0KYGBgDQogDQogVyBrb2xlam55bSBrcm9rdSB3eXpuYWN6YW15IHByb2dub3rEmSBuYSBiYXppZSBkYW55Y2ggdHJlbmluZ293eWNoLg0KIE9zemFjb3dhbnkgem9zdGHFgiByw7N3bmllxbwgYsWCxIVkIE1TRSBvcmF6IHdhcnRvxZtjaSB3c3DDs8WCY3p5bm5pa8OzdyB3IG1vZGVsdS4NCiANCmBgYHtyfQ0KcmlkZ2VfcHJlZCA9IHByZWRpY3QocmlkZ2VfbW9kLCBzID0gYmVzdGxhbSwgbmV3eCA9IHhfdGVzdCkgIyBaYXN0b3Nvd2FuaWUgbmFqbGVwaXN6ZWogd2FydG/Fm2NpIGxhbWJkeQ0KTVNFX3JlZ19nID0gbWVhbigocmlkZ2VfcHJlZCAtIHlfdGVzdCleMikgIyBNU0UNCnByaW50KHBhc3RlKCJXYXJ0b8WbxIcgYsWCxJlkdSBNU0UgZGxhIHByb2dub3p5IHphIHBvbW9jxIUgcmVncmVzamkgZ3J6YmlldG93ZWo6IiwgIE1TRV9yZWdfZykpDQoNCm91dCA9IGdsbW5ldCh4LCB5LCBhbHBoYSA9IDApIA0KUmVnX2dfY29lZiA9IHByZWRpY3Qob3V0LCB0eXBlID0gImNvZWZmaWNpZW50cyIsIHMgPSBiZXN0bGFtKVsxOjE4LF0gIyBXc3DDs8WCY3p5bm5pa2kNClJlZ19nX2NvZWYgDQpgYGANCiANCiMjIyAyLiBNb2RlbCByZWdyZXNqaSBMYXNzbw0KIA0KYGBge3J9DQpsYXNzb19tb2QgPSBnbG1uZXQoeF90cmFpbiwgeV90cmFpbiwgYWxwaGEgPSAxLGxhbWJkYSA9IGdyaWQpICMgTW9kZWwgbGFzc28NCnBsb3QobGFzc29fbW9kKSAgIyBXeWtyZXMgd3Nww7PFgmN6eW5uaWvDs3cNCg0KYGBgDQoNCklkZW50eWZpa2FjamEgd2FydG/Fm2NpIGxhbWJkeSwga3TDs3JhIG5hamJhcmR6aWVqIG1pbmltYWxpenVqZSBixYLEhWQgTVNFIHcgbW9kZWx1IExhc3NvLg0KDQpgYGB7cn0NCnNldC5zZWVkKDEpDQpjdi5vdXQgPSBjdi5nbG1uZXQoeF90cmFpbiwgeV90cmFpbiwgYWxwaGEgPSAxKSAjIERvcGFzb3dhbmllIG1vZGVsdSBMYXNzbw0KYmVzdGxhbSA9IGN2Lm91dCRsYW1iZGEubWluICMgTmFqbGVwc3phIGxhbWJkYQ0KcGxvdChjdi5vdXQpIA0KDQpgYGANCg0KUG9ub3duaWUgd3l6bmFjemFteSB3YXJ0b8WbY2kgcHJvZ25vem93YW5lIG9yYXogbGljenlteSBixYLEhWQgTVNFLg0KTmFzdMSZcG5pZSBzcHJhd2R6YW15IHdzcMOzxYJjenlubmlraSBtb2RlbHUuDQoNCmBgYHtyfQ0KbGFzc29fcHJlZCA9IHByZWRpY3QobGFzc29fbW9kLCBzID0gYmVzdGxhbSwgbmV3eCA9IHhfdGVzdCkgIyBQcmVkeWtjamEgeiBuYWpsZXBzesSFIGxhbWJkxIUNCk1TRV9yZWdfbCA9IG1lYW4oKGxhc3NvX3ByZWQgLSB5X3Rlc3QpXjIpICMgTVNFIGRsYSBMYXNzbw0KcHJpbnQocGFzdGUoIldhcnRvxZvEhyBixYLEmWR1IE1TRSBkbGEgcHJvZ25venkgemEgcG9tb2PEhSByZWdyZXNqaSBMYXNzbzoiLCAgTVNFX3JlZ19sKSkNCg0Kb3V0ID0gZ2xtbmV0KHgsIHksIGFscGhhID0gMSwgbGFtYmRhID0gZ3JpZCkgIyBEb3Bhc3VqIG1vZGVsIGxhc3NvIGRvIHBlxYJuZWdvIHpiaW9ydSBkYW55Y2gNCmxhc3NvX2NvZWYgPSBwcmVkaWN0KG91dCwgdHlwZSA9ICJjb2VmZmljaWVudHMiLCBzID0gYmVzdGxhbSlbMToxOCxdICMgV3N6eXN0a2llIHdzcMOzxYJjenlubmlraQ0KbGFzc29fY29lZg0KDQpgYGANCg0KVHltIHJhemVtIDcgd3Nww7PFgmN6eW5uaWvDs3cgem9zdGHFgm8gd3l6ZXJvd2FuZQ0KDQpgYGB7cn0NCmxhc3NvX2NvZWZfMiA9IGxhc3NvX2NvZWZbbGFzc29fY29lZiAhPSAwXSAjIFd5xZt3aWV0bGFuaWUgdHlsa28gbmllemVyb3d5Y2ggd3Nww7PFgmN6eW5uaWvDs3cNCmxhc3NvX2NvZWZfMg0KYGBgDQpGaW5hbG5pZSBwb3pvc3RhamUgMTEgaXN0b3RueWNoIHdzcMOzxYJjenlubmlrw7N3IHcgbW9kZWx1DQoNCiMjIyAzLiBLbGFzeWN6bnkgbW9kZWwgT0xTDQoNCmBgYHtyfQ0KeF90cmFpbiA8LSBhcy5kYXRhLmZyYW1lKHhfdHJhaW4pICAjIEtvbndlcnNqYSBtYWNpZXJ6eSBuYSByYW1rxJkgZGFueWNoDQp5X3RyYWluIDwtIGFzLmRhdGEuZnJhbWUoeV90cmFpbikgDQp0cmFpbl9kYXRhIDwtIGNiaW5kKHlfdHJhaW4sIHhfdHJhaW4pDQoNCm9sc19tb2QgPC0gbG0oeV90cmFpbiB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhKSAgIyBPTFM6IHdzenlzdGtpZSB6bWllbm5lIG9iamHFm25pYWrEhWNlDQpzdW1tYXJ5KG9sc19tb2QpICAjIFd5xZt3aWV0bGVuaWUgc3pjemVnw7PFgsOzdyBtb2RlbHUNCnN1bW1hcnkob2xzX21vZCkkY29lZmZpY2llbnRzDQpgYGANClcga29sZWpueW0ga3Jva3Ugc2Vrd2VuY3lqbmllIHVzdXdhbXkgbmllaXN0b3RuZSB6bWllbm5lIG9iamHFm25pYWrEhWNlDQoNCmBgYHtyfQ0KIyBVc3V3YW5pZSBuaWVzdG90bnljaCB6bWllbm55Y2gNCnN0ZXB3aXNlX21vZCA8LSBzdGVwKG9sc19tb2QsIGRpcmVjdGlvbiA9ICJiYWNrd2FyZCIpDQoNCiMgUHJlZHlrY2phIG5hIGRhbnljaCB0ZXN0b3d5Y2gNCnhfdGVzdCA8LSBhcy5kYXRhLmZyYW1lKHhfdGVzdCkgICMgS29ud2Vyc2phIG1hY2llcnp5IHRlc3Rvd2VqIG5hIHJhbWvEmSBkYW55Y2gNCm9sc19wcmVkIDwtIHByZWRpY3Qoc3RlcHdpc2VfbW9kLCBuZXdkYXRhID0geF90ZXN0KQ0Kc3VtbWFyeShzdGVwd2lzZV9tb2QpJGNvZWZmaWNpZW50cw0KT0xTX2NvZWY9c3RlcHdpc2VfbW9kJGNvZWZmaWNpZW50cw0KYGBgDQoNCkphayB3aWRhxIcsIGZpbmFsbmllIHLDs3duaWXFvCBwb3pvc3RhxYJvIDExIGlzdG90bnljaCB6bWllbm55Y2ggb2JqYcWbbmlhasSFY3ljaC4NCk5hc3TEmXBuaWUgbGljenlteSBixYLEhWQgTVNFLg0KDQpgYGB7cn0NCk1TRV9vbHM9IG1lYW4oKG9sc19wcmVkIC0geV90ZXN0KV4yKSAjIE1TRSBkbGEgT0xTDQpwcmludChwYXN0ZSgiV2FydG/Fm8SHIGLFgsSZZHUgTVNFIGRsYSBwcm9nbm96eSB6YSBwb21vY8SFIE9MUzoiLCAgTVNFX29scykpDQoNCnBsb3Qoc3RlcHdpc2VfbW9kKQ0KYGBgDQoNCiMjIyBXeW5pa2kNCg0KTmEga2/FhGN1IG5hbGXFvHkgcG9yw7N3bmHEhyB1enlza2FuZSB3eW5pa2kgemEgcG9tb2PEhSB3eXpuYWN6b255Y2ggbWlhciBixYLEmWR1IE1TRS4NCg0KYGBge3J9DQpkYXRhLmZyYW1lKE1vZGVsPWMoIlJlZ3Jlc2phIGdyemJpZXRvd2EiLCAiUmVncmVzamEgTGFzc28iLCAiS2xhc3ljem55IE9MUyIpLE1TRT1jKE1TRV9yZWdfZyxNU0VfcmVnX2wsTVNFX29scykpDQpgYGANCg0KTmEgcG9kc3Rhd2llIHdza3phbnljaCB3YXJ0b8WbY2kgbW/FvG5hIHBvd2llZHppZcSHLCDFvGUgbmFqbGVwc3p5IHJlenVsdGF0IHByb2dub3p5IHV6eXNrYW5vIHphIHBvbW9jxIUgcmVncmVzamkgZ3J6YmlldG93ZWouDQpOYWxlxbx5IGplZG5hayBkb2RhxIcsIMW8ZSB3IHR5bSBwcnp5cGFka3Ugem9zdGHFgnkgdXd6Z2zEmWRuaW9uZSB3c3p5c3RraWUgcHJlZHlrdG9yeSwgY28gbW/FvGUgc2t1dGtvd2HEhyBvdmVyZml0dGluZ2llbS4NCk5hIGRydWdpbSBtaWVqc2N1IHpuYWxhesWCYSBzacSZIGtsYXN5Y3puYSBtZXRvZGEgbmFqbW5pZWpzenljaCBrd2FkcmF0w7N3LCBuYXRvbWlhc3Qgd3luaWsgbmllIG9kYmllZ2Egem5hY3puaWUgb2QgcmVncmVzamkgTGFzc28uDQpEb2RhdGtvd28gdyBtZXRvZHppZSBPTFMgbmllIHpvc3RhxYJ5IHp3ZXJ5Zmlrb3dhbmUgd3N6ZWxraWUgdGVzdHkgendpxIV6YW5lIHoga2xhc3ljem55bWkgemHFgm/FvGVuaWFtaSBLTk1LLCBrdMOzcmUgcHJhd2RvcG9kYm5pZSBuaWUgem9zdGHFgnkgY2HFgmtvd2ljaWUgc3BlxYJuaW9uZS4NCg0KIyMgUHJlZHlrdG9yeQ0KIC0gS3TDs3JlIHByZWR5a3Rvcnkgb2themHFgnkgc2nEmSB3YcW8bmUgdyBvc3RhdGVjem55bSBtb2RlbHUgKG1vZGVsYWNoKT8NCiANCmBgYHtyfQ0KbGlzdChSZWdfZ19jb2VmLCBsYXNzb19jb2VmXzIsIE9MU19jb2VmKQ0KYGBgDQogDQogVyBtb2RlbGkgcmVncmVzamkgZ3J6YmlldG93ZWogbmllIHpvc3RhxYJhIG9kcnp1Y29uYSDFvGFkbmEgem1pZW5uYS4NCiBXIHByenlwYWRrdSBtb2RlbHUgcmVncmVzamkgTGFzc28gb3JheiBPTFMsIHpvc3RhxYJvIHBvIDExIGlzdG90bnljaCB6bWllbm55Y2guDQogT2JhIG1vZGVsZSByw7PFvG5pxIUgc2nEmSB3ecWCxIVjem5pZSAyIHptaWVubnltaSAoVG9wMjVwZXJjIG9yYXogUGhEKS4NCiANCiANCiANCiANCiANCiA=