Topics

References

  • Wasserman (20004), Chpters 9, 13

Maximum Likelihood

\[\mathcal{L}(\theta) = \prod_{i=1}^n f(X_i;\theta)\]

Example: Gaussian sample

mu = 1
sigma = 2
n = 100
x = rnorm(n, mu, sigma)  # sample
hist(x, freq=FALSE)  # show histogram
for(m in -1:3){
  # compare with Gaussians with differnt means
  curve(dnorm(x, m, sigma), add=TRUE, col=m+3)
}

m = seq(-1, 3, 0.1)  # grid 
s = seq(1, 3, 0.1)
L = matrix(0, length(m), length(s))
for(i in 1:length(s)){
  for(j in 1:length(m)){
    L[j,i] = prod(dnorm(x, m[j], s[i]))
  }
}
persp(m, s, L, ticktype="detailed", theta=30)

  • Log likelihood:

\[\mathcal{l}(\theta) = \log \mathcal{L}(\theta) = \sum_{i=1}^n \log f(X_i;\theta)\]

# 3D plot
persp(m, s, log(L), ticktype="detailed", theta=30, phi=30)

The surface of log likelihood is smoother than likelihood, which is convenient for parameter fitting.

# countour plot
contour(m, s, log(L), xlab="m", ylab="s")

Maximum likelihood estimator (MLE) \(\hat{\theta}\)

  • \(\theta\) that maximizes \(\mathcal{L}(\theta)\) or \(\mathcal{l}(\theta)\)

Example: \(\mbox{Bernoulli}(p)\)

\[f(x;p) = p^x(1-p)^{1-x}\]

  • for samples \(x_1,...,x_n\), let \(S = \sum_i x_i\), i.e. number of 1s

    • \(\mathcal{L}(p) = \prod_i p^{x_i}(1–p)^{1–x_i} = p^S(1–p)^{n–S}\)
    • \(\mathcal{l}(p) = S\log p + (n–S)\log(1–p)\)
  • let \(\frac{d\mathcal{l}(p)}{dp} = 0\)

    • \(\frac{S}{p} - \frac{n-S}{1–p} = 0\)
    • \((1-p)S - p(n-S) = S - pn = 0\)
  • MLE is \(\hat{p} = \frac{S}{n}\) … sample mean

Example: \(\mathcal{N}(\mu,\sigma^2)\)

\[f(x;\mu,\sigma^2)=\frac{1}{\sqrt{2\pi}\sigma} e^{–\frac{(x–\mu)^2}{2\sigma^2}}\]

  • let \(M=\frac{1}{n}\sum_i x_i\) and \(S=\frac{1}{n}\sum_i x_i^2\)

  • Likelihood:

\[\mathcal{L}(\mu,\sigma^2) = \prod_i \frac{1}{\sqrt{2\pi}\sigma} e^{–\frac{(x_i–\mu)^2}{2\sigma^2}} = (2\pi)^{-\frac{n}{2}}\sigma^{-n} e^{\sum_i\frac{-(x_i–\mu)^2}{2\sigma^2}}\\ = (2\pi)^{-\frac{n}{2}}\sigma^{-n} e^\frac{n(–S+2M\mu-\mu^2)}{2\sigma^2}\]

  • Log likelihood:

\[\mathcal{l}(\mu,\sigma^2) = -\frac{n}{2}\log(2\pi) -n\log\sigma +n\frac{–S+2M\mu-\mu^2}{2\sigma^2}\]

  • let \(\frac{\partial\mathcal{l}}{\partial\mu}=0\)

then \(n\frac{2M-2\mu}{2\sigma^2} = 0\),
i.e. \(\hat{\mu}=M\) … sample mean

  • let \(\frac{\partial\mathcal{l}}{\partial\sigma}=0\)

then \(-n\frac{1}{\sigma} - 2n\frac{–S^2+M^2}{2\sigma^3}=0\)
i.e. \(\sigma^2=S-M^2=\frac{1}{n}\sum_i (x_i-M)^2\) … sample variance

x = rnorm(10, 1, 1)
M = mean(x)
S = mean(x^2)
c(M, S-M^2)
[1] 1.1234711 0.8463601

Properties of MLE

  • For a large number of data \(n\rightarrow\infty\)
    • Consistent: \(\hat{\theta}\rightarrow\theta\)
    • Asymptotically normal: \(\hat{\theta}\sim\mathcal{N}(\theta,\frac{1}{n}\Sigma)\)
    • Efficient: smallest variance among all estimates
  • Can be biased with finite \(n\)
    • Unbiased estimate: \(E(\hat{\theta}) = \theta\)
    • bias\((\hat{\theta}) = E(\hat{\theta})–\theta\)

Regression

Pairs of data \((X_1,Y_1),...,(X_n,Y_n)\) sampled from \((X,Y)\) * \(X\): independent var., predictor var., covariate, regressor
* \(Y\): dependent var., outcome, response var.

Generative model: \[Y = r(X) + \epsilon \quad\mbox{ where } E(\epsilon)=0\]

Linear Regression

Linear model: \[Y = \beta_0 + \beta_1X + \epsilon\]

  • \(r(x) = \beta_0 + \beta_1x\)
  • \(E(\epsilon)=0\) and \(V(\epsilon)=\sigma^2\)

  • Least squares estimates \(\hat{\beta}_0\) and \(\hat{b}_1\)
    • parameters that minimize residual sums of squares:

\[\mbox{RSS} = \sum_i\epsilon_i^2 = \sum_i\{y_i – (\beta_0 + \beta_1x_i)\}^2\]

Let \(\bar(X)=\frac{1}{n}\sum_ix_i\) and \(\bar(Y)=\frac{1}{n}\sum_iy_i\)

  • Let \(\frac{\partial\mbox{RSS}}{\partial \beta_0}=0\)
    then \(\sum_i (y_i–\beta_0-\beta_1x_i) = \bar{Y}-\beta_1\bar{X}-\beta_0=0\)
    thus \(\beta_0=\bar{Y}-\beta_1\bar{X}\)

  • Let \(\frac{\partial\mbox{RSS}}{\partial \beta_1}=0\)
    then \(\sum_i \{(y_i–\bar{Y})-\beta_1(x_i-\bar{X})\}(x_i-\bar{X}) = 0\) i.e. \(\sum_i(x_i-\bar{X})(y_i–\bar{Y}) - \beta_1\sum_i(x_i-\bar{X})^2 = 0\)

\[\hat{\beta_1} = \frac{\sum_i(x_i–\bar{X})(y_i–\bar{Y})}{\sum_i(x_i–\bar{X})^2} = \frac{Cov(X,Y)}{Var(X)}\]

\[\hat{\beta}_0 = \bar{Y} – \hat{\beta}_1\bar{X}\]

n = 1000
b0 = 5
b1 = 2
eps = 1
x = runif(n, 0, 10)
y = b0 + b1*x + rnorm(n, 0, eps)
plot(x, y)  # plot sample points
xbar = mean(x)
ybar = mean(y)
b1hat = sum((x-xbar)*(y-ybar))/sum((x-xbar)^2)
b0hat = ybar - b1hat*xbar
c(b0hat, b1hat)
[1] 4.979394 1.994324
curve(b0hat+b1hat*x, add=TRUE)

MLE and LSE

  • Assumption: \(\epsilon \sim \mathcal{N}(0,\sigma^2)\)

  • Likelihood:

\[\mathcal{L}(\beta_0,\beta_1,\sigma) = \prod_i f(y_i;\beta_0+\beta_1x_i,\sigma^2)\\ = (2\pi)^{-\frac{n}{2}}\sigma^{-n} e^{–\sum_i\frac{(y_i – (\beta_0 + \beta_1x_i))^2}{2\sigma^2}}\]

  • Log likelihood:

\[\mathcal{l}(\beta_0,\beta_1,\sigma) = -\frac{n}{2}\log(2\pi) –n\log\sigma -\frac{1}{2\sigma^2}\sum_i\{y_i–(\beta_0+\beta_1x_i)\}^2\]

  • Maximizing log likelihood = minimizing RSS

Goodness of Regression Model

  • Sum of squares: Total SS = Explained SS + Residual SS
    • TSS = \(\sum_i\{y_i – \bar{Y}\}^2\)
    • ESS = \(\sum_i\{(\hat{\beta}_0 + \hat{\beta}_1 x_i) – \bar{Y}\}^2\)
    • RSS = \(\sum_i\{y_i - (\hat{\beta}_0+\hat{\beta}_1 x_i)\}^2\)
  • Coefficient of determination: \(R^2\) = 1–RSS/TSS = ESS/TSS
tss = sum((y-ybar)^2)
ess = sum(((b0hat+b1hat*x)-ybar)^2)
rss = sum((y-(b0hat+b1hat*x))^2)
r2 = ess/tss
c(tss, ess, rss, r2)
[1] 3.362383e+04 3.254664e+04 1.077196e+03 9.679633e-01

Data Frame

A data frame is a list made of vectors or matrices with the same length or rows, defined as data.frame class.

df = data.frame(id=1:3, value=diag(1, 3), note=c("low","hi","low"))
df
  id value.1 value.2 value.3 note
1  1       1       0       0  low
2  2       0       1       0   hi
3  3       0       0       1  low
  • Components can be accessed by [ ] or $.
df$id
[1] 1 2 3
df$value.1
[1] 1 0 0
df$note
[1] low hi  low
Levels: hi low

Built-in Datasets

R comes with many datasets convenient for testing.

  • To list built-in datasets
data()
  • For example:
summary(ChickWeight)
     weight           Time           Chick     Diet   
 Min.   : 35.0   Min.   : 0.00   13     : 12   1:220  
 1st Qu.: 63.0   1st Qu.: 4.00   9      : 12   2:120  
 Median :103.0   Median :10.00   20     : 12   3:120  
 Mean   :121.8   Mean   :10.72   10     : 12   4:118  
 3rd Qu.:163.8   3rd Qu.:16.00   17     : 12          
 Max.   :373.0   Max.   :21.00   19     : 12          
                                 (Other):506          
  • By attach() a data frame, its compnents are copied to your work space, unless a variable of the same name has already been defined.
attach(ChickWeight)
plot(Time, weight, col=Diet)

plot(Time[Diet==3], weight[Diet==3])

Try linear regression of weight by time.

x = Time
y = weight
plot(x, y)  # plot sample points
xbar = mean(x)
ybar = mean(y)
b1hat = sum((x-xbar)*(y-ybar))/sum((x-xbar)^2)
b0hat = ybar - b1hat*xbar
curve(b0hat+b1hat*x, add=TRUE)
title(sprintf("beta0=%5.2f, beta1=%5.2f", b0hat, b1hat))

tss = sum((y-ybar)^2)
ess = sum(((b0hat+b1hat*x)-ybar)^2)
rss = sum((y-(b0hat+b1hat*x))^2)
r2 = ess/tss
paste("tss=", tss, "ess=", ess, "rss=", rss)
[1] "tss= 2914555.92560554 ess= 2042343.74905088 rss= 872212.176554658"
paste("R^2=", r2, "Cor^2=", cor(x,y)^2)
[1] "R^2= 0.700739255372688 Cor^2= 0.700739255372688"

Multiple Regression

\(k\)-dimensional input \(X = (X_1,...,X_k)\)

\[Y = \beta_0 + \beta_1X_1 + ... + \beta_kX_k + \epsilon\]

\[Y = X \beta + \epsilon\]

\[X = \left(\begin{array}{ccc} X_{11} & \cdots & X_{1k} \\ \vdots & & \vdots\\ X_{n1} & \cdots & X_{nk} \end{array}\right)\]

\[Y =\left(\begin{array}{c} Y_{1} \\ \vdots \\ Y_{n} \end{array}\right)\]

\[\mbox{RSS} = \sum_i\epsilon_i^2 = \sum_i (Y_i – X_i \beta)^2 = ||Y – X\beta||^2\]

+ RSS is minimized by

\[\hat{\beta} = (X^TX)^{–1} X^TY\]

Example of multivariate data

pairs(state.x77)

attach(as.data.frame(state.x77))
plot(Area, Population)

lm() in R

R offers lm() for linear regression.

See how Life Expectancy varies with Income.
summary() gives a variety of information,

LifeIncome = lm(`Life Exp`~Income)
summary(LifeIncome)

Call:
lm(formula = `Life Exp` ~ Income)

Residuals:
     Min       1Q   Median       3Q      Max 
-2.96547 -0.76381 -0.03428  0.92876  2.32951 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 6.758e+01  1.328e+00  50.906   <2e-16 ***
Income      7.433e-04  2.965e-04   2.507   0.0156 *  
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.275 on 48 degrees of freedom
Multiple R-squared:  0.1158,    Adjusted R-squared:  0.09735 
F-statistic: 6.285 on 1 and 48 DF,  p-value: 0.01562

Store the coeficients in a vector.

beta = coefficients(LifeIncome)
beta
 (Intercept)       Income 
6.758132e+01 7.433343e-04 

We can predict the values for new inputs

income = seq(0, 10000, 500)
lifetime = predict(LifeIncome, data.frame(Income=income))
plot(income, lifetime)

abline() adds the fitted line to a plot.

plot(Income, `Life Exp`)
abline(LifeIncome)

Try linear regression between other variables…

LifeMurder = lm(`Life Exp`~Murder)
summary(LifeMurder)

Call:
lm(formula = `Life Exp` ~ Murder)

Residuals:
     Min       1Q   Median       3Q      Max 
-1.81690 -0.48139  0.09591  0.39769  2.38691 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) 72.97356    0.26997  270.30  < 2e-16 ***
Murder      -0.28395    0.03279   -8.66 2.26e-11 ***
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.8473 on 48 degrees of freedom
Multiple R-squared:  0.6097,    Adjusted R-squared:  0.6016 
F-statistic: 74.99 on 1 and 48 DF,  p-value: 2.26e-11

Multiple Regression by lm()

lm() can also be used for multiple regression.

LifeIM = lm(`Life Exp` ~ Income + Murder)
summary(LifeIM)

Call:
lm(formula = `Life Exp` ~ Income + Murder)

Residuals:
     Min       1Q   Median       3Q      Max 
-1.48301 -0.62099 -0.01714  0.47768  2.20831 

Coefficients:
              Estimate Std. Error t value Pr(>|t|)    
(Intercept) 71.2255815  0.9673952  73.626  < 2e-16 ***
Income       0.0003705  0.0001973   1.878   0.0666 .  
Murder      -0.2697594  0.0328408  -8.214 1.22e-10 ***
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.8259 on 47 degrees of freedom
Multiple R-squared:  0.637, Adjusted R-squared:  0.6215 
F-statistic: 41.23 on 2 and 47 DF,  p-value: 4.561e-11
beta2 = coefficients(LifeIM)

Please try regression with other variables or other data sets.

3D Plotting

Let us use “rgl” package for ineractive viewing.

Tools >Install Packages… menu to install it. You may also need the X Window installed (XQuartz, etc.).

library(rgl)
plot3d(Income, Murder, `Life Exp`)

You can draw a surface by persp3d().

plot3d(Income, Murder, `Life Exp`)
xr = range(Income)
xc = cbind(xr,xr)  # values at 4 corners
yr = range(Murder)
yc = rbind(yr,yr)  # values at 4 corners
z = beta2[1] + beta2[2]*xc + beta2[3]*yc # regression surface
persp3d(xr, yr, z, col='green', add=TRUE)

Polynomial Regression

X = seq(-5,5,0.1)
X2 = X**2
X3 = X**3
X4 = X**4
X5 = X**5
plot(X, X, type="l")
lines(X, X2, type="l")
lines(X, X3, type="l")
lines(X, X4, type="l")
lines(X, X5, type="l")

Example: sine wave

Y = sin(X)
plot(X, Y, type="l")

  • Example: Noisy sine wave
n = 50
x = runif(n, -5, 5)
sigma = 0.1
y = sin(x) + rnorm(n, 0, sigma)
plot(x, y, type="p", col="green")
curve(sin(x), add=TRUE)

x2 = x**2
x3 = x**3
x4 = x**4
x5 = x**5
poly3 = lm(y~x+x2+x3)
poly5 = lm(y~x+x2+x3+x4+x5)
coefficients(poly3)
(Intercept)           x          x2          x3 
 0.20649506  0.44711899 -0.02415746 -0.03556397 
coefficients(poly5)
  (Intercept)             x            x2            x3 
 0.1042882031  0.8719270771 -0.0207464605 -0.1154905502 
           x4            x5 
 0.0008189321  0.0030131912 

Predict the output

Y3 = predict(poly3,data.frame(x=X,x2=X2,x3=X3))
Y5 = predict(poly5,data.frame(x=X,x2=X2,x3=X3,x4=X4,x5=X5))
plot(x, y, col="green")
lines(X, Y, type="l",col="blue")
lines(X, Y3,col="orange")
lines(X, Y5,col="red")

Overfitting

As we increase the number of regressors, even noisy outcome can be precisely fit.
This can make the regression function deviated from the underlying function, and can increase the errors for new data not used for fitting.

Example: sine wave

ns = 20  # sample points
xs = runif(ns, -4, 4)
sigma = 0.2  # sampling noise
target = sin  # target function, e.g. sin()
ys = target(xs) + rnorm(ns, 0, sigma)
plot(xs, ys, type="p", col="green")
curve(target(x), add=TRUE, lwd=2, col="red")
# polynomial regression
np = 50
xp = seq(-4, 4, length.out=np)
for(k in 3:11){
  x = xs  # samples for fitting
  pm = lm(ys ~ poly(x, k, raw=TRUE))
  print( summary(pm))
  x = xp  # prediction
  yp = predict(pm, newdata=data.frame(poly(x, k, raw=TRUE)))
  #yp = predict(pm, data.frame(x=xp))
  lines(x, yp, type="l",col=gray(k/20))
}

Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
     Min       1Q   Median       3Q      Max 
-0.29131 -0.17449 -0.01542  0.10599  0.65599 

Coefficients:
                         Estimate Std. Error t value
(Intercept)             -0.181688   0.091932  -1.976
poly(x, k, raw = TRUE)1  0.701614   0.064937  10.804
poly(x, k, raw = TRUE)2  0.014968   0.011724   1.277
poly(x, k, raw = TRUE)3 -0.065701   0.005964 -11.017
                        Pr(>|t|)    
(Intercept)               0.0656 .  
poly(x, k, raw = TRUE)1 9.26e-09 ***
poly(x, k, raw = TRUE)2   0.2199    
poly(x, k, raw = TRUE)3 7.02e-09 ***
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.254 on 16 degrees of freedom
Multiple R-squared:  0.8973,    Adjusted R-squared:  0.878 
F-statistic: 46.59 on 3 and 16 DF,  p-value: 3.945e-08


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
     Min       1Q   Median       3Q      Max 
-0.29654 -0.16850 -0.03514  0.12371  0.63332 

Coefficients:
                          Estimate Std. Error t value
(Intercept)             -0.2015699  0.1250754  -1.612
poly(x, k, raw = TRUE)1  0.6984913  0.0681521  10.249
poly(x, k, raw = TRUE)2  0.0265492  0.0490652   0.541
poly(x, k, raw = TRUE)3 -0.0655553  0.0061761 -10.614
poly(x, k, raw = TRUE)4 -0.0008186  0.0033614  -0.244
                        Pr(>|t|)    
(Intercept)                0.128    
poly(x, k, raw = TRUE)1 3.61e-08 ***
poly(x, k, raw = TRUE)2    0.596    
poly(x, k, raw = TRUE)3 2.27e-08 ***
poly(x, k, raw = TRUE)4    0.811    
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2618 on 15 degrees of freedom
Multiple R-squared:  0.8977,    Adjusted R-squared:  0.8704 
F-statistic:  32.9 on 4 and 15 DF,  p-value: 2.903e-07


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
    Min      1Q  Median      3Q     Max 
-0.2368 -0.1508  0.0139  0.1205  0.3242 

Coefficients:
                         Estimate Std. Error t value
(Intercept)             -0.173092   0.097029  -1.784
poly(x, k, raw = TRUE)1  0.958092   0.093992  10.193
poly(x, k, raw = TRUE)2  0.042573   0.038219   1.114
poly(x, k, raw = TRUE)3 -0.143754   0.023932  -6.007
poly(x, k, raw = TRUE)4 -0.002053   0.002624  -0.783
poly(x, k, raw = TRUE)5  0.004475   0.001342   3.335
                        Pr(>|t|)    
(Intercept)              0.09612 .  
poly(x, k, raw = TRUE)1 7.36e-08 ***
poly(x, k, raw = TRUE)2  0.28406    
poly(x, k, raw = TRUE)3 3.22e-05 ***
poly(x, k, raw = TRUE)4  0.44689    
poly(x, k, raw = TRUE)5  0.00491 ** 
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2023 on 14 degrees of freedom
Multiple R-squared:  0.943, Adjusted R-squared:  0.9226 
F-statistic:  46.3 on 5 and 14 DF,  p-value: 3.233e-08


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
     Min       1Q   Median       3Q      Max 
-0.26657 -0.12466  0.02248  0.09091  0.35059 

Coefficients:
                          Estimate Std. Error t value
(Intercept)             -0.0572615  0.1085473  -0.528
poly(x, k, raw = TRUE)1  0.9689429  0.0867066  11.175
poly(x, k, raw = TRUE)2 -0.0986055  0.0830182  -1.188
poly(x, k, raw = TRUE)3 -0.1493887  0.0222311  -6.720
poly(x, k, raw = TRUE)4  0.0249399  0.0145790   1.711
poly(x, k, raw = TRUE)5  0.0048394  0.0012504   3.870
poly(x, k, raw = TRUE)6 -0.0012723  0.0006776  -1.877
                        Pr(>|t|)    
(Intercept)              0.60672    
poly(x, k, raw = TRUE)1 4.89e-08 ***
poly(x, k, raw = TRUE)2  0.25618    
poly(x, k, raw = TRUE)3 1.43e-05 ***
poly(x, k, raw = TRUE)4  0.11088    
poly(x, k, raw = TRUE)5  0.00193 ** 
poly(x, k, raw = TRUE)6  0.08307 .  
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1862 on 13 degrees of freedom
Multiple R-squared:  0.9551,    Adjusted R-squared:  0.9344 
F-statistic: 46.13 on 6 and 13 DF,  p-value: 5.084e-08


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
     Min       1Q   Median       3Q      Max 
-0.26978 -0.12330  0.02373  0.11564  0.33937 

Coefficients:
                          Estimate Std. Error t value
(Intercept)             -0.0536803  0.1124704  -0.477
poly(x, k, raw = TRUE)1  0.9255077  0.1364300   6.784
poly(x, k, raw = TRUE)2 -0.1101458  0.0900251  -1.224
poly(x, k, raw = TRUE)3 -0.1234700  0.0655560  -1.883
poly(x, k, raw = TRUE)4  0.0273701  0.0161256   1.697
poly(x, k, raw = TRUE)5  0.0010497  0.0090703   0.116
poly(x, k, raw = TRUE)6 -0.0013921  0.0007555  -1.843
poly(x, k, raw = TRUE)7  0.0001553  0.0003679   0.422
                        Pr(>|t|)    
(Intercept)               0.6417    
poly(x, k, raw = TRUE)1 1.95e-05 ***
poly(x, k, raw = TRUE)2   0.2446    
poly(x, k, raw = TRUE)3   0.0841 .  
poly(x, k, raw = TRUE)4   0.1154    
poly(x, k, raw = TRUE)5   0.9098    
poly(x, k, raw = TRUE)6   0.0902 .  
poly(x, k, raw = TRUE)7   0.6804    
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1924 on 12 degrees of freedom
Multiple R-squared:  0.9558,    Adjusted R-squared:   0.93 
F-statistic: 37.07 on 7 and 12 DF,  p-value: 3.378e-07


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
     Min       1Q   Median       3Q      Max 
-0.23466 -0.14559  0.00039  0.10458  0.31720 

Coefficients:
                          Estimate Std. Error t value
(Intercept)             -0.1190007  0.1386773  -0.858
poly(x, k, raw = TRUE)1  0.9445997  0.1401779   6.739
poly(x, k, raw = TRUE)2  0.0276791  0.1900057   0.146
poly(x, k, raw = TRUE)3 -0.1237675  0.0664381  -1.863
poly(x, k, raw = TRUE)4 -0.0207701  0.0604652  -0.344
poly(x, k, raw = TRUE)5  0.0004303  0.0092226   0.047
poly(x, k, raw = TRUE)6  0.0040351  0.0066076   0.611
poly(x, k, raw = TRUE)7  0.0001975  0.0003763   0.525
poly(x, k, raw = TRUE)8 -0.0001908  0.0002307  -0.827
                        Pr(>|t|)    
(Intercept)               0.4091    
poly(x, k, raw = TRUE)1 3.21e-05 ***
poly(x, k, raw = TRUE)2   0.8868    
poly(x, k, raw = TRUE)3   0.0894 .  
poly(x, k, raw = TRUE)4   0.7377    
poly(x, k, raw = TRUE)5   0.9636    
poly(x, k, raw = TRUE)6   0.5538    
poly(x, k, raw = TRUE)7   0.6102    
poly(x, k, raw = TRUE)8   0.4258    
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.195 on 11 degrees of freedom
Multiple R-squared:  0.9584,    Adjusted R-squared:  0.9281 
F-statistic: 31.66 on 8 and 11 DF,  p-value: 1.58e-06


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
     Min       1Q   Median       3Q      Max 
-0.22217 -0.09489  0.02552  0.07952  0.30819 

Coefficients:
                          Estimate Std. Error t value
(Intercept)             -0.1077859  0.1324799  -0.814
poly(x, k, raw = TRUE)1  0.7698886  0.1801226   4.274
poly(x, k, raw = TRUE)2  0.0093877  0.1816439   0.052
poly(x, k, raw = TRUE)3  0.0644109  0.1446390   0.445
poly(x, k, raw = TRUE)4 -0.0133295  0.0578929  -0.230
poly(x, k, raw = TRUE)5 -0.0509017  0.0365424  -1.393
poly(x, k, raw = TRUE)6  0.0030614  0.0063373   0.483
poly(x, k, raw = TRUE)7  0.0052422  0.0035041   1.496
poly(x, k, raw = TRUE)8 -0.0001507  0.0002218  -0.680
poly(x, k, raw = TRUE)9 -0.0001625  0.0001122  -1.447
                        Pr(>|t|)   
(Intercept)              0.43482   
poly(x, k, raw = TRUE)1  0.00163 **
poly(x, k, raw = TRUE)2  0.95980   
poly(x, k, raw = TRUE)3  0.66557   
poly(x, k, raw = TRUE)4  0.82254   
poly(x, k, raw = TRUE)5  0.19382   
poly(x, k, raw = TRUE)6  0.63944   
poly(x, k, raw = TRUE)7  0.16552   
poly(x, k, raw = TRUE)8  0.51224   
poly(x, k, raw = TRUE)9  0.17843   
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1859 on 10 degrees of freedom
Multiple R-squared:  0.9656,    Adjusted R-squared:  0.9346 
F-statistic: 31.18 on 9 and 10 DF,  p-value: 3.724e-06


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
      Min        1Q    Median        3Q       Max 
-0.194427 -0.111667  0.008215  0.101650  0.280957 

Coefficients:
                           Estimate Std. Error t value
(Intercept)              -1.840e-01  1.490e-01  -1.235
poly(x, k, raw = TRUE)1   8.169e-01  1.838e-01   4.445
poly(x, k, raw = TRUE)2   2.300e-01  2.719e-01   0.846
poly(x, k, raw = TRUE)3   3.898e-02  1.453e-01   0.268
poly(x, k, raw = TRUE)4  -1.348e-01  1.260e-01  -1.070
poly(x, k, raw = TRUE)5  -4.561e-02  3.656e-02  -1.248
poly(x, k, raw = TRUE)6   2.725e-02  2.320e-02   1.174
poly(x, k, raw = TRUE)7   4.786e-03  3.500e-03   1.367
poly(x, k, raw = TRUE)8  -2.129e-03  1.840e-03  -1.157
poly(x, k, raw = TRUE)9  -1.492e-04  1.120e-04  -1.333
poly(x, k, raw = TRUE)10  5.650e-05  5.217e-05   1.083
                         Pr(>|t|)   
(Intercept)               0.24820   
poly(x, k, raw = TRUE)1   0.00161 **
poly(x, k, raw = TRUE)2   0.41951   
poly(x, k, raw = TRUE)3   0.79456   
poly(x, k, raw = TRUE)4   0.31253   
poly(x, k, raw = TRUE)5   0.24362   
poly(x, k, raw = TRUE)6   0.27035   
poly(x, k, raw = TRUE)7   0.20466   
poly(x, k, raw = TRUE)8   0.27701   
poly(x, k, raw = TRUE)9   0.21527   
poly(x, k, raw = TRUE)10  0.30698   
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1843 on 9 degrees of freedom
Multiple R-squared:  0.9696,    Adjusted R-squared:  0.9357 
F-statistic: 28.66 on 10 and 9 DF,  p-value: 1.287e-05


Call:
lm(formula = ys ~ poly(x, k, raw = TRUE))

Residuals:
      Min        1Q    Median        3Q       Max 
-0.194733 -0.097289 -0.001349  0.103516  0.276502 

Coefficients:
                           Estimate Std. Error t value
(Intercept)              -1.857e-01  1.551e-01  -1.198
poly(x, k, raw = TRUE)1   9.504e-01  3.055e-01   3.111
poly(x, k, raw = TRUE)2   2.081e-01  2.856e-01   0.729
poly(x, k, raw = TRUE)3  -1.601e-01  3.863e-01  -0.415
poly(x, k, raw = TRUE)4  -1.213e-01  1.333e-01  -0.910
poly(x, k, raw = TRUE)5   3.255e-02  1.446e-01   0.225
poly(x, k, raw = TRUE)6   2.416e-02  2.476e-02   0.976
poly(x, k, raw = TRUE)7  -7.646e-03  2.249e-02  -0.340
poly(x, k, raw = TRUE)8  -1.843e-03  1.981e-03  -0.930
poly(x, k, raw = TRUE)9   7.157e-04  1.549e-03   0.462
poly(x, k, raw = TRUE)10  4.756e-05  5.658e-05   0.841
poly(x, k, raw = TRUE)11 -2.188e-05  3.907e-05  -0.560
                         Pr(>|t|)  
(Intercept)                0.2654  
poly(x, k, raw = TRUE)1    0.0144 *
poly(x, k, raw = TRUE)2    0.4870  
poly(x, k, raw = TRUE)3    0.6894  
poly(x, k, raw = TRUE)4    0.3894  
poly(x, k, raw = TRUE)5    0.8276  
poly(x, k, raw = TRUE)6    0.3577  
poly(x, k, raw = TRUE)7    0.7427  
poly(x, k, raw = TRUE)8    0.3795  
poly(x, k, raw = TRUE)9    0.6563  
poly(x, k, raw = TRUE)10   0.4250  
poly(x, k, raw = TRUE)11   0.5907  
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1918 on 8 degrees of freedom
Multiple R-squared:  0.9707,    Adjusted R-squared:  0.9304 
F-statistic:  24.1 on 11 and 8 DF,  p-value: 6.286e-05

Excercise

1. Maximum Likelihood

  1. For a sample \(x_1,...,x_n\) from Poisson(\(\lambda\)), derive the MLE of \(\lambda\).

  2. Sample \(n\) (e.g. 100) data from a normal distribution and make MLEs of the mean \(\hat{\mu}\) and the variance \(\hat{\sigma^2}\).

Repeat it \(m\) (e.g., 1000) times and see the distributions of the MLEs \(P(\hat{\mu})\) and \(P(\hat{\sigma^2})\), e.g., histogram, mean, and variance.
See how the distributions change with the sample size \(n\).

2. Linear Regression

  1. Take a dataset from R and try linear regression
  1. Check the goodness of fit by \(R^2\) and compare that with correlation

3. Multiple Regression

Take a dateset with three or more components.
Make different multiple regression models and compare \(R^2\) to see which model describes the relationship better.

4. Take a function of your interest and apply polynomial regression

  1. Visulalize the sample points, target function, and the regression functions with different orders of the polynomial
  1. Compare the average squared difference of the regression function from
    a: the sample data used for fitting
    b: the target function
    c: newly sampled data not used for fitting

for different orders \(k\), sample size \(ns\), and the noise level \(\sigma\).

LS0tCnRpdGxlOiAiNi4gUmVncmVzc2lvbiBhbmQgTWF4aW11bSBMaWtlbGlob29kIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgojIFRvcGljcwoKKiBNYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGUgKE1MRSkKKiBMaW5lYXIgcmVncmVzc2lvbgoqIExlYXN0IHNxdWFyZXMgZXN0aW1hdGUgKExTRSkKKiBEYXRhIGZyYW1lIGluIFIKKiBNdWx0aXBsZSByZWdyZXNzaW9uCiogT3ZlcmZpdHRpbmcKCiMjIyMgUmVmZXJlbmNlcwoKKiBXYXNzZXJtYW4gKDIwMDA0KSwgQ2hwdGVycyA5LCAxMwoKIyBNYXhpbXVtIExpa2VsaWhvb2QKCiogUGFyYW1ldHJpYyBtb2RlbCAkXG1hdGhjYWx7Rn0gPSBce2YoeDtcdGhldGEpOyBcdGhldGFcaW5cVGhldGFcfSQKCiogQW4gaW5kZXBlbmRlbnQgc2FtcGxlICRYXzEsLi4uLFhfbiQKCiogTGlrZWxpaG9vZDogcHJvYmFiaWxpdHkgb2Ygb2JzZXJ2aW5nIHRoZSBzYW1wbGUgYXMgYSBmdW5jdGlvbiBvZiBwYXJhbWV0ZXIKCiQkXG1hdGhjYWx7TH0oXHRoZXRhKSA9IFxwcm9kX3tpPTF9Xm4gZihYX2k7XHRoZXRhKSQkCgojIyMgRXhhbXBsZTogR2F1c3NpYW4gc2FtcGxlCgpgYGB7cn0KbXUgPSAxCnNpZ21hID0gMgpuID0gMTAwCnggPSBybm9ybShuLCBtdSwgc2lnbWEpICAjIHNhbXBsZQpoaXN0KHgsIGZyZXE9RkFMU0UpICAjIHNob3cgaGlzdG9ncmFtCmZvcihtIGluIC0xOjMpewogICMgY29tcGFyZSB3aXRoIEdhdXNzaWFucyB3aXRoIGRpZmZlcm50IG1lYW5zCiAgY3VydmUoZG5vcm0oeCwgbSwgc2lnbWEpLCBhZGQ9VFJVRSwgY29sPW0rMykKfQpgYGAKCmBgYHtyfQptID0gc2VxKC0xLCAzLCAwLjEpICAjIGdyaWQgCnMgPSBzZXEoMSwgMywgMC4xKQpMID0gbWF0cml4KDAsIGxlbmd0aChtKSwgbGVuZ3RoKHMpKQpmb3IoaSBpbiAxOmxlbmd0aChzKSl7CiAgZm9yKGogaW4gMTpsZW5ndGgobSkpewogICAgTFtqLGldID0gcHJvZChkbm9ybSh4LCBtW2pdLCBzW2ldKSkKICB9Cn0KcGVyc3AobSwgcywgTCwgdGlja3R5cGU9ImRldGFpbGVkIiwgdGhldGE9MzApCmBgYAoKKiBMb2cgbGlrZWxpaG9vZDogIAoKJCRcbWF0aGNhbHtsfShcdGhldGEpID0gXGxvZyBcbWF0aGNhbHtMfShcdGhldGEpID0gXHN1bV97aT0xfV5uIFxsb2cgZihYX2k7XHRoZXRhKSQkCgpgYGB7cn0KIyAzRCBwbG90CnBlcnNwKG0sIHMsIGxvZyhMKSwgdGlja3R5cGU9ImRldGFpbGVkIiwgdGhldGE9MzAsIHBoaT0zMCkKYGBgCgpUaGUgc3VyZmFjZSBvZiBsb2cgbGlrZWxpaG9vZCBpcyBzbW9vdGhlciB0aGFuIGxpa2VsaWhvb2QsIHdoaWNoIGlzIGNvbnZlbmllbnQgZm9yIHBhcmFtZXRlciBmaXR0aW5nLgoKYGBge3J9CiMgY291bnRvdXIgcGxvdApjb250b3VyKG0sIHMsIGxvZyhMKSwgeGxhYj0ibSIsIHlsYWI9InMiKQpgYGAKCk1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0b3IgKE1MRSkgJFxoYXR7XHRoZXRhfSQKCiogJFx0aGV0YSQgdGhhdCBtYXhpbWl6ZXMgJFxtYXRoY2Fse0x9KFx0aGV0YSkkIG9yICRcbWF0aGNhbHtsfShcdGhldGEpJAoKIyMjIEV4YW1wbGU6ICRcbWJveHtCZXJub3VsbGl9KHApJAoKJCRmKHg7cCkgPSBwXngoMS1wKV57MS14fSQkCgoqIGZvciBzYW1wbGVzICR4XzEsLi4uLHhfbiQsIGxldCAkUyA9IFxzdW1faSB4X2kkLCBpLmUuIG51bWJlciBvZiAxcyAgCgogICAgKyAkXG1hdGhjYWx7TH0ocCkgPSBccHJvZF9pIHBee3hfaX0oMeKAk3ApXnsx4oCTeF9pfSA9IHBeUygx4oCTcClee27igJNTfSQgIAogICAgKyAkXG1hdGhjYWx7bH0ocCkgPSBTXGxvZyBwICsgKG7igJNTKVxsb2coMeKAk3ApJAoKKiBsZXQgJFxmcmFje2RcbWF0aGNhbHtsfShwKX17ZHB9ID0gMCQgIAoKICAgICsgJFxmcmFje1N9e3B9IC0gXGZyYWN7bi1TfXsx4oCTcH0gPSAwJCAgCiAgICArICQoMS1wKVMgLSBwKG4tUykgPSBTIC0gcG4gPSAwJAoKKiBNTEUgaXMgJFxoYXR7cH0gPSBcZnJhY3tTfXtufSQgLi4uIHNhbXBsZSBtZWFuCgojIyMgRXhhbXBsZTogJFxtYXRoY2Fse059KFxtdSxcc2lnbWFeMikkCgokJGYoeDtcbXUsXHNpZ21hXjIpPVxmcmFjezF9e1xzcXJ0ezJccGl9XHNpZ21hfSBlXnvigJNcZnJhY3soeOKAk1xtdSleMn17MlxzaWdtYV4yfX0kJAoKKiBsZXQgJE09XGZyYWN7MX17bn1cc3VtX2kgeF9pJCBhbmQgJFM9XGZyYWN7MX17bn1cc3VtX2kgeF9pXjIkCgoqIExpa2VsaWhvb2Q6CgokJFxtYXRoY2Fse0x9KFxtdSxcc2lnbWFeMikKICA9IFxwcm9kX2kgXGZyYWN7MX17XHNxcnR7MlxwaX1cc2lnbWF9IGVee+KAk1xmcmFjeyh4X2nigJNcbXUpXjJ9ezJcc2lnbWFeMn19CiAgPSAoMlxwaSleey1cZnJhY3tufXsyfX1cc2lnbWFeey1ufSBlXntcc3VtX2lcZnJhY3stKHhfaeKAk1xtdSleMn17MlxzaWdtYV4yfX1cXAogID0gKDJccGkpXnstXGZyYWN7bn17Mn19XHNpZ21hXnstbn0gZV5cZnJhY3tuKOKAk1MrMk1cbXUtXG11XjIpfXsyXHNpZ21hXjJ9JCQKCiogTG9nIGxpa2VsaWhvb2Q6IAoKJCRcbWF0aGNhbHtsfShcbXUsXHNpZ21hXjIpCiAgPSAtXGZyYWN7bn17Mn1cbG9nKDJccGkpIC1uXGxvZ1xzaWdtYSArblxmcmFje+KAk1MrMk1cbXUtXG11XjJ9ezJcc2lnbWFeMn0kJAoKKiBsZXQgJFxmcmFje1xwYXJ0aWFsXG1hdGhjYWx7bH19e1xwYXJ0aWFsXG11fT0wJCAgCgp0aGVuICRuXGZyYWN7Mk0tMlxtdX17MlxzaWdtYV4yfSA9IDAkLCAgCmkuZS4gJFxoYXR7XG11fT1NJCAuLi4gc2FtcGxlIG1lYW4KCiogbGV0ICRcZnJhY3tccGFydGlhbFxtYXRoY2Fse2x9fXtccGFydGlhbFxzaWdtYX09MCQgIAoKdGhlbiAkLW5cZnJhY3sxfXtcc2lnbWF9IC0gMm5cZnJhY3vigJNTXjIrTV4yfXsyXHNpZ21hXjN9PTAkICAKaS5lLiAkXHNpZ21hXjI9Uy1NXjI9XGZyYWN7MX17bn1cc3VtX2kgKHhfaS1NKV4yJCAuLi4gc2FtcGxlIHZhcmlhbmNlCgpgYGB7cn0KeCA9IHJub3JtKDEwLCAxLCAxKQpNID0gbWVhbih4KQpTID0gbWVhbih4XjIpCmMoTSwgUy1NXjIpCmBgYAoKIyMgUHJvcGVydGllcyBvZiBNTEUKCiogRm9yIGEgbGFyZ2UgbnVtYmVyIG9mIGRhdGEgJG5ccmlnaHRhcnJvd1xpbmZ0eSQKICAgICsgQ29uc2lzdGVudDogJFxoYXR7XHRoZXRhfVxyaWdodGFycm93XHRoZXRhJAogICAgKyBBc3ltcHRvdGljYWxseSBub3JtYWw6ICRcaGF0e1x0aGV0YX1cc2ltXG1hdGhjYWx7Tn0oXHRoZXRhLFxmcmFjezF9e259XFNpZ21hKSQKICAgICsgRWZmaWNpZW50OiBzbWFsbGVzdCB2YXJpYW5jZSBhbW9uZyBhbGwgZXN0aW1hdGVzCgoqIENhbiBiZSBiaWFzZWQgd2l0aCBmaW5pdGUgJG4kCiAgICArIFVuYmlhc2VkIGVzdGltYXRlOiAkRShcaGF0e1x0aGV0YX0pID0gXHRoZXRhJAogICAgKyBiaWFzJChcaGF0e1x0aGV0YX0pID0gRShcaGF0e1x0aGV0YX0p4oCTXHRoZXRhJAoKIyBSZWdyZXNzaW9uCgpQYWlycyBvZiBkYXRhICQoWF8xLFlfMSksLi4uLChYX24sWV9uKSQgc2FtcGxlZCBmcm9tICQoWCxZKSQKKiAkWCQ6IGluZGVwZW5kZW50IHZhci4sIHByZWRpY3RvciB2YXIuLCBjb3ZhcmlhdGUsIHJlZ3Jlc3NvciAgCiogJFkkOiBkZXBlbmRlbnQgdmFyLiwgb3V0Y29tZSwgcmVzcG9uc2UgdmFyLiAgCgpHZW5lcmF0aXZlIG1vZGVsOgokJFkgPSByKFgpICsgXGVwc2lsb24gXHF1YWRcbWJveHsgd2hlcmUgfSBFKFxlcHNpbG9uKT0wJCQKCiogcmVncmVzc2lvbiBmdW5jdGlvbjogJHIoeCkgPSBFKFl8WD14KSQKCiMjIExpbmVhciBSZWdyZXNzaW9uCgpMaW5lYXIgbW9kZWw6CiQkWSA9IFxiZXRhXzAgKyBcYmV0YV8xWCArIFxlcHNpbG9uJCQKCiogJHIoeCkgPSBcYmV0YV8wICsgXGJldGFfMXgkCiogJEUoXGVwc2lsb24pPTAkIGFuZCAkVihcZXBzaWxvbik9XHNpZ21hXjIkCgoqIExlYXN0IHNxdWFyZXMgZXN0aW1hdGVzICRcaGF0e1xiZXRhfV8wJCBhbmQgJFxoYXR7Yn1fMSQgIAogICAgKyBwYXJhbWV0ZXJzIHRoYXQgbWluaW1pemUgcmVzaWR1YWwgc3VtcyBvZiBzcXVhcmVzOgoKJCRcbWJveHtSU1N9ID0gXHN1bV9pXGVwc2lsb25faV4yID0gXHN1bV9pXHt5X2kg4oCTIChcYmV0YV8wICsgXGJldGFfMXhfaSlcfV4yJCQgIAoKTGV0ICRcYmFyKFgpPVxmcmFjezF9e259XHN1bV9peF9pJCBhbmQgJFxiYXIoWSk9XGZyYWN7MX17bn1cc3VtX2l5X2kkCgoqIExldCAkXGZyYWN7XHBhcnRpYWxcbWJveHtSU1N9fXtccGFydGlhbCBcYmV0YV8wfT0wJCAgCnRoZW4gJFxzdW1faSAoeV9p4oCTXGJldGFfMC1cYmV0YV8xeF9pKSA9IFxiYXJ7WX0tXGJldGFfMVxiYXJ7WH0tXGJldGFfMD0wJCAgCnRodXMgJFxiZXRhXzA9XGJhcntZfS1cYmV0YV8xXGJhcntYfSQKCiogTGV0ICRcZnJhY3tccGFydGlhbFxtYm94e1JTU319e1xwYXJ0aWFsIFxiZXRhXzF9PTAkICAKdGhlbiAkXHN1bV9pIFx7KHlfaeKAk1xiYXJ7WX0pLVxiZXRhXzEoeF9pLVxiYXJ7WH0pXH0oeF9pLVxiYXJ7WH0pID0gMCQKaS5lLiAkXHN1bV9pKHhfaS1cYmFye1h9KSh5X2nigJNcYmFye1l9KSAtIFxiZXRhXzFcc3VtX2koeF9pLVxiYXJ7WH0pXjIgPSAwJAoKJCRcaGF0e1xiZXRhXzF9ID0gXGZyYWN7XHN1bV9pKHhfaeKAk1xiYXJ7WH0pKHlfaeKAk1xiYXJ7WX0pfXtcc3VtX2koeF9p4oCTXGJhcntYfSleMn0gPSBcZnJhY3tDb3YoWCxZKX17VmFyKFgpfSQkCgokJFxoYXR7XGJldGF9XzAgPSBcYmFye1l9IOKAkyBcaGF0e1xiZXRhfV8xXGJhcntYfSQkCgpgYGB7cn0KbiA9IDEwMDAKYjAgPSA1CmIxID0gMgplcHMgPSAxCnggPSBydW5pZihuLCAwLCAxMCkKeSA9IGIwICsgYjEqeCArIHJub3JtKG4sIDAsIGVwcykKcGxvdCh4LCB5KSAgIyBwbG90IHNhbXBsZSBwb2ludHMKeGJhciA9IG1lYW4oeCkKeWJhciA9IG1lYW4oeSkKYjFoYXQgPSBzdW0oKHgteGJhcikqKHkteWJhcikpL3N1bSgoeC14YmFyKV4yKQpiMGhhdCA9IHliYXIgLSBiMWhhdCp4YmFyCmMoYjBoYXQsIGIxaGF0KQpjdXJ2ZShiMGhhdCtiMWhhdCp4LCBhZGQ9VFJVRSkKYGBgCgojIyBNTEUgYW5kIExTRQoKKiBBc3N1bXB0aW9uOiAkXGVwc2lsb24gXHNpbSBcbWF0aGNhbHtOfSgwLFxzaWdtYV4yKSQKCiogTGlrZWxpaG9vZDogCgokJFxtYXRoY2Fse0x9KFxiZXRhXzAsXGJldGFfMSxcc2lnbWEpID0gXHByb2RfaSBmKHlfaTtcYmV0YV8wK1xiZXRhXzF4X2ksXHNpZ21hXjIpXFwKICA9ICgyXHBpKV57LVxmcmFje259ezJ9fVxzaWdtYV57LW59IGVee+KAk1xzdW1faVxmcmFjeyh5X2kg4oCTIChcYmV0YV8wICsgXGJldGFfMXhfaSkpXjJ9ezJcc2lnbWFeMn19JCQKCiogTG9nIGxpa2VsaWhvb2Q6CgokJFxtYXRoY2Fse2x9KFxiZXRhXzAsXGJldGFfMSxcc2lnbWEpID0gLVxmcmFje259ezJ9XGxvZygyXHBpKSDigJNuXGxvZ1xzaWdtYSAtXGZyYWN7MX17MlxzaWdtYV4yfVxzdW1faVx7eV9p4oCTKFxiZXRhXzArXGJldGFfMXhfaSlcfV4yJCQKCiogTWF4aW1pemluZyBsb2cgbGlrZWxpaG9vZCA9IG1pbmltaXppbmcgUlNTCgojIyBHb29kbmVzcyBvZiBSZWdyZXNzaW9uIE1vZGVsCgoqIFN1bSBvZiBzcXVhcmVzOiBUb3RhbCBTUyA9IEV4cGxhaW5lZCBTUyArIFJlc2lkdWFsIFNTCiAgICArIFRTUyA9ICRcc3VtX2lce3lfaSDigJMgXGJhcntZfVx9XjIkCiAgICArIEVTUyA9ICRcc3VtX2lceyhcaGF0e1xiZXRhfV8wICsgXGhhdHtcYmV0YX1fMSB4X2kpIOKAkyBcYmFye1l9XH1eMiQKICAgICsgUlNTID0gJFxzdW1faVx7eV9pIC0gKFxoYXR7XGJldGF9XzArXGhhdHtcYmV0YX1fMSB4X2kpXH1eMiQKCiogQ29lZmZpY2llbnQgb2YgZGV0ZXJtaW5hdGlvbjogJFJeMiQgPSAx4oCTUlNTL1RTUyA9IEVTUy9UU1MKCmBgYHtyfQp0c3MgPSBzdW0oKHkteWJhcileMikKZXNzID0gc3VtKCgoYjBoYXQrYjFoYXQqeCkteWJhcileMikKcnNzID0gc3VtKCh5LShiMGhhdCtiMWhhdCp4KSleMikKcjIgPSBlc3MvdHNzCmModHNzLCBlc3MsIHJzcywgcjIpCmBgYAoKIyMgRGF0YSBGcmFtZQoKQSBkYXRhIGZyYW1lIGlzIGEgbGlzdCBtYWRlIG9mIHZlY3RvcnMgb3IgbWF0cmljZXMgd2l0aCB0aGUgc2FtZSBsZW5ndGggb3Igcm93cywgZGVmaW5lZCBhcyBgZGF0YS5mcmFtZWAgY2xhc3MuCgpgYGB7cn0KZGYgPSBkYXRhLmZyYW1lKGlkPTE6MywgdmFsdWU9ZGlhZygxLCAzKSwgbm90ZT1jKCJsb3ciLCJoaSIsImxvdyIpKQpkZgpgYGAKCiogQ29tcG9uZW50cyBjYW4gYmUgYWNjZXNzZWQgYnkgYFsgXWAgb3IgYCRgLgoKYGBge3J9CmRmJGlkCmRmJHZhbHVlLjEKZGYkbm90ZQpgYGAKCiMjIEJ1aWx0LWluIERhdGFzZXRzCgpSIGNvbWVzIHdpdGggbWFueSBkYXRhc2V0cyBjb252ZW5pZW50IGZvciB0ZXN0aW5nLgoKKiBUbyBsaXN0IGJ1aWx0LWluIGRhdGFzZXRzCmBgYHtyfQpkYXRhKCkKYGBgCgoqIEZvciBleGFtcGxlOgpgYGB7cn0Kc3VtbWFyeShDaGlja1dlaWdodCkKYGBgCgoqIEJ5IGBhdHRhY2goKWAgYSBkYXRhIGZyYW1lLCBpdHMgY29tcG5lbnRzIGFyZSBjb3BpZWQgdG8geW91ciB3b3JrIHNwYWNlLCB1bmxlc3MgYSB2YXJpYWJsZSBvZiB0aGUgc2FtZSBuYW1lIGhhcyBhbHJlYWR5IGJlZW4gZGVmaW5lZC4KCmBgYHtyfQphdHRhY2goQ2hpY2tXZWlnaHQpCnBsb3QoVGltZSwgd2VpZ2h0LCBjb2w9RGlldCkKYGBgCgpgYGB7cn0KcGxvdChUaW1lW0RpZXQ9PTNdLCB3ZWlnaHRbRGlldD09M10pCmBgYAoKVHJ5IGxpbmVhciByZWdyZXNzaW9uIG9mIHdlaWdodCBieSB0aW1lLgoKYGBge3J9CnggPSBUaW1lCnkgPSB3ZWlnaHQKcGxvdCh4LCB5KSAgIyBwbG90IHNhbXBsZSBwb2ludHMKeGJhciA9IG1lYW4oeCkKeWJhciA9IG1lYW4oeSkKYjFoYXQgPSBzdW0oKHgteGJhcikqKHkteWJhcikpL3N1bSgoeC14YmFyKV4yKQpiMGhhdCA9IHliYXIgLSBiMWhhdCp4YmFyCmN1cnZlKGIwaGF0K2IxaGF0KngsIGFkZD1UUlVFKQp0aXRsZShzcHJpbnRmKCJiZXRhMD0lNS4yZiwgYmV0YTE9JTUuMmYiLCBiMGhhdCwgYjFoYXQpKQpgYGAKCmBgYHtyfQp0c3MgPSBzdW0oKHkteWJhcileMikKZXNzID0gc3VtKCgoYjBoYXQrYjFoYXQqeCkteWJhcileMikKcnNzID0gc3VtKCh5LShiMGhhdCtiMWhhdCp4KSleMikKcjIgPSBlc3MvdHNzCnBhc3RlKCJ0c3M9IiwgdHNzLCAiZXNzPSIsIGVzcywgInJzcz0iLCByc3MpCnBhc3RlKCJSXjI9IiwgcjIsICJDb3JeMj0iLCBjb3IoeCx5KV4yKQpgYGAKCiMgTXVsdGlwbGUgUmVncmVzc2lvbgoKJGskLWRpbWVuc2lvbmFsIGlucHV0ICRYID0gKFhfMSwuLi4sWF9rKSQKCiQkWSA9IFxiZXRhXzAgKyBcYmV0YV8xWF8xICsgLi4uICsgXGJldGFfa1hfayArIFxlcHNpbG9uJCQKCiogQnkgc2V0dGluZyAkWF8xPTEkLCAKJFxiZXRhID1cbGVmdChcYmVnaW57YXJyYXl9e2N9XGJldGFfMVxcIFx2ZG90c1xcIFxiZXRhX2sgXGVuZHthcnJheX1ccmlnaHQpJCwgd2UgaGF2ZSBhIHZlY3RvciBub3RhdGlvbgoKJCRZID0gWCBcYmV0YSArIFxlcHNpbG9uJCQgICAgIAoKKiAkaSQtdGggaW5wdXQgJFhfaSA9IChYX3tpMX0sLi4uLFhfe2lrfSkkICAKICAgICogaW5wdXQgZGF0YSBtYXRyaXggCgokJFggPSBcbGVmdChcYmVnaW57YXJyYXl9e2NjY30KICAgIFhfezExfSAmIFxjZG90cyAmIFhfezFrfSBcXAogICAgXHZkb3RzICYgJiBcdmRvdHNcXAogICAgWF97bjF9ICYgXGNkb3RzICYgWF97bmt9ClxlbmR7YXJyYXl9XHJpZ2h0KSQkCgoqICRpJC10aCBvdXRwdXQgJFlfaSQgIAogICAgKyBvdXRwdXQgZGF0YSB2ZWN0b3IgCgokJFkgPVxsZWZ0KFxiZWdpbnthcnJheX17Y30KICAgIFlfezF9IFxcCiAgICBcdmRvdHMgXFwKICAgIFlfe259ClxlbmR7YXJyYXl9XHJpZ2h0KSQkCgoqIExlYXN0IHNxdWFyZSBzb2x1dGlvbgoKJCRcbWJveHtSU1N9ID0gXHN1bV9pXGVwc2lsb25faV4yID0gXHN1bV9pIChZX2kg4oCTIFhfaSBcYmV0YSleMiA9IHx8WSDigJMgWFxiZXRhfHxeMiQkCgogICAgKyBSU1MgaXMgbWluaW1pemVkIGJ5CgokJFxoYXR7XGJldGF9ID0gKFheVFgpXnvigJMxfSBYXlRZJCQKCiMjIEV4YW1wbGUgb2YgbXVsdGl2YXJpYXRlIGRhdGEKCmBgYHtyIHN0YXRlc30KcGFpcnMoc3RhdGUueDc3KQpgYGAKCmBgYHtyfQphdHRhY2goYXMuZGF0YS5mcmFtZShzdGF0ZS54NzcpKQpwbG90KEFyZWEsIFBvcHVsYXRpb24pCmBgYAoKIyMgYGxtKClgIGluIFIKClIgb2ZmZXJzIGBsbSgpYCBmb3IgbGluZWFyIHJlZ3Jlc3Npb24uICAKClNlZSBob3cgTGlmZSBFeHBlY3RhbmN5IHZhcmllcyB3aXRoIEluY29tZS4gIApgc3VtbWFyeSgpYCBnaXZlcyBhIHZhcmlldHkgb2YgaW5mb3JtYXRpb24sIAoKYGBge3IgbGluZWFyfQpMaWZlSW5jb21lID0gbG0oYExpZmUgRXhwYH5JbmNvbWUpCnN1bW1hcnkoTGlmZUluY29tZSkKYGBgCgpTdG9yZSB0aGUgY29lZmljaWVudHMgaW4gYSB2ZWN0b3IuCgpgYGB7cn0KYmV0YSA9IGNvZWZmaWNpZW50cyhMaWZlSW5jb21lKQpiZXRhCmBgYAoKV2UgY2FuIHByZWRpY3QgdGhlIHZhbHVlcyBmb3IgbmV3IGlucHV0cwoKYGBge3J9CmluY29tZSA9IHNlcSgwLCAxMDAwMCwgNTAwKQpsaWZldGltZSA9IHByZWRpY3QoTGlmZUluY29tZSwgZGF0YS5mcmFtZShJbmNvbWU9aW5jb21lKSkKcGxvdChpbmNvbWUsIGxpZmV0aW1lKQpgYGAKCmBhYmxpbmUoKWAgYWRkcyB0aGUgZml0dGVkIGxpbmUgdG8gYSBwbG90LgoKYGBge3J9CnBsb3QoSW5jb21lLCBgTGlmZSBFeHBgKQphYmxpbmUoTGlmZUluY29tZSkKYGBgCgpUcnkgbGluZWFyIHJlZ3Jlc3Npb24gYmV0d2VlbiBvdGhlciB2YXJpYWJsZXMuLi4KCmBgYHtyfQpMaWZlTXVyZGVyID0gbG0oYExpZmUgRXhwYH5NdXJkZXIpCnN1bW1hcnkoTGlmZU11cmRlcikKYGBgCgojIyMgTXVsdGlwbGUgUmVncmVzc2lvbiBieSBgbG0oKWAKCmBsbSgpYCBjYW4gYWxzbyBiZSB1c2VkIGZvciBtdWx0aXBsZSByZWdyZXNzaW9uLgoKYGBge3J9CkxpZmVJTSA9IGxtKGBMaWZlIEV4cGAgfiBJbmNvbWUgKyBNdXJkZXIpCnN1bW1hcnkoTGlmZUlNKQpiZXRhMiA9IGNvZWZmaWNpZW50cyhMaWZlSU0pCmBgYAoKUGxlYXNlIHRyeSByZWdyZXNzaW9uIHdpdGggb3RoZXIgdmFyaWFibGVzIG9yIG90aGVyIGRhdGEgc2V0cy4KCiMjIDNEIFBsb3R0aW5nCgpMZXQgdXMgdXNlICJyZ2wiIHBhY2thZ2UgZm9yIGluZXJhY3RpdmUgdmlld2luZy4KClRvb2xzID5JbnN0YWxsIFBhY2thZ2VzLi4uIG1lbnUgdG8gaW5zdGFsbCBpdC4gWW91IG1heSBhbHNvIG5lZWQgdGhlIFggV2luZG93IGluc3RhbGxlZCAoWFF1YXJ0eiwgZXRjLikuCgpgYGB7cn0KbGlicmFyeShyZ2wpCnBsb3QzZChJbmNvbWUsIE11cmRlciwgYExpZmUgRXhwYCkKYGBgCgpZb3UgY2FuIGRyYXcgYSBzdXJmYWNlIGJ5IHBlcnNwM2QoKS4KCmBgYHtyfQpwbG90M2QoSW5jb21lLCBNdXJkZXIsIGBMaWZlIEV4cGApCnhyID0gcmFuZ2UoSW5jb21lKQp4YyA9IGNiaW5kKHhyLHhyKSAgIyB2YWx1ZXMgYXQgNCBjb3JuZXJzCnlyID0gcmFuZ2UoTXVyZGVyKQp5YyA9IHJiaW5kKHlyLHlyKSAgIyB2YWx1ZXMgYXQgNCBjb3JuZXJzCnogPSBiZXRhMlsxXSArIGJldGEyWzJdKnhjICsgYmV0YTJbM10qeWMgIyByZWdyZXNzaW9uIHN1cmZhY2UKcGVyc3AzZCh4ciwgeXIsIHosIGNvbD0nZ3JlZW4nLCBhZGQ9VFJVRSkKYGBgCgojIyBQb2x5bm9taWFsIFJlZ3Jlc3Npb24KCmBgYHtyfQpYID0gc2VxKC01LDUsMC4xKQpYMiA9IFgqKjIKWDMgPSBYKiozClg0ID0gWCoqNApYNSA9IFgqKjUKcGxvdChYLCBYLCB0eXBlPSJsIikKbGluZXMoWCwgWDIsIHR5cGU9ImwiKQpsaW5lcyhYLCBYMywgdHlwZT0ibCIpCmxpbmVzKFgsIFg0LCB0eXBlPSJsIikKbGluZXMoWCwgWDUsIHR5cGU9ImwiKQpgYGAKCiMjIEV4YW1wbGU6IHNpbmUgd2F2ZQoKYGBge3J9ClkgPSBzaW4oWCkKcGxvdChYLCBZLCB0eXBlPSJsIikKYGBgCgoqIEV4YW1wbGU6IE5vaXN5IHNpbmUgd2F2ZQoKYGBge3J9Cm4gPSA1MAp4ID0gcnVuaWYobiwgLTUsIDUpCnNpZ21hID0gMC4xCnkgPSBzaW4oeCkgKyBybm9ybShuLCAwLCBzaWdtYSkKcGxvdCh4LCB5LCB0eXBlPSJwIiwgY29sPSJncmVlbiIpCmN1cnZlKHNpbih4KSwgYWRkPVRSVUUpCmBgYAoKCmBgYHtyfQp4MiA9IHgqKjIKeDMgPSB4KiozCng0ID0geCoqNAp4NSA9IHgqKjUKcG9seTMgPSBsbSh5fngreDIreDMpCnBvbHk1ID0gbG0oeX54K3gyK3gzK3g0K3g1KQpjb2VmZmljaWVudHMocG9seTMpCmNvZWZmaWNpZW50cyhwb2x5NSkKYGBgCgpQcmVkaWN0IHRoZSBvdXRwdXQKCmBgYHtyfQpZMyA9IHByZWRpY3QocG9seTMsZGF0YS5mcmFtZSh4PVgseDI9WDIseDM9WDMpKQpZNSA9IHByZWRpY3QocG9seTUsZGF0YS5mcmFtZSh4PVgseDI9WDIseDM9WDMseDQ9WDQseDU9WDUpKQpwbG90KHgsIHksIGNvbD0iZ3JlZW4iKQpsaW5lcyhYLCBZLCB0eXBlPSJsIixjb2w9ImJsdWUiKQpsaW5lcyhYLCBZMyxjb2w9Im9yYW5nZSIpCmxpbmVzKFgsIFk1LGNvbD0icmVkIikKYGBgCgojIyBPdmVyZml0dGluZwoKQXMgd2UgaW5jcmVhc2UgdGhlIG51bWJlciBvZiByZWdyZXNzb3JzLCBldmVuIG5vaXN5IG91dGNvbWUgY2FuIGJlIHByZWNpc2VseSBmaXQuICAKVGhpcyBjYW4gbWFrZSB0aGUgcmVncmVzc2lvbiBmdW5jdGlvbiBkZXZpYXRlZCBmcm9tIHRoZSB1bmRlcmx5aW5nIGZ1bmN0aW9uLCBhbmQgY2FuIGluY3JlYXNlIHRoZSBlcnJvcnMgZm9yIG5ldyBkYXRhIG5vdCB1c2VkIGZvciBmaXR0aW5nLgoKIyMgRXhhbXBsZTogc2luZSB3YXZlCgpgYGB7cn0KbnMgPSAyMCAgIyBzYW1wbGUgcG9pbnRzCnhzID0gcnVuaWYobnMsIC00LCA0KQpzaWdtYSA9IDAuMiAgIyBzYW1wbGluZyBub2lzZQp0YXJnZXQgPSBzaW4gICMgdGFyZ2V0IGZ1bmN0aW9uLCBlLmcuIHNpbigpCnlzID0gdGFyZ2V0KHhzKSArIHJub3JtKG5zLCAwLCBzaWdtYSkKcGxvdCh4cywgeXMsIHR5cGU9InAiLCBjb2w9ImdyZWVuIikKY3VydmUodGFyZ2V0KHgpLCBhZGQ9VFJVRSwgbHdkPTIsIGNvbD0icmVkIikKIyBwb2x5bm9taWFsIHJlZ3Jlc3Npb24KbnAgPSA1MAp4cCA9IHNlcSgtNCwgNCwgbGVuZ3RoLm91dD1ucCkKZm9yKGsgaW4gMzoxMSl7CiAgeCA9IHhzICAjIHNhbXBsZXMgZm9yIGZpdHRpbmcKICBwbSA9IGxtKHlzIH4gcG9seSh4LCBrLCByYXc9VFJVRSkpCiAgcHJpbnQoIHN1bW1hcnkocG0pKQogIHggPSB4cCAgIyBwcmVkaWN0aW9uCiAgeXAgPSBwcmVkaWN0KHBtLCBuZXdkYXRhPWRhdGEuZnJhbWUocG9seSh4LCBrLCByYXc9VFJVRSkpKQogICN5cCA9IHByZWRpY3QocG0sIGRhdGEuZnJhbWUoeD14cCkpCiAgbGluZXMoeCwgeXAsIHR5cGU9ImwiLGNvbD1ncmF5KGsvMjApKQp9CmBgYAoKIyBFeGNlcmNpc2UKCiMjIDEuIE1heGltdW0gTGlrZWxpaG9vZAoKMSkgRm9yIGEgc2FtcGxlICR4XzEsLi4uLHhfbiQgZnJvbSBQb2lzc29uKCRcbGFtYmRhJCksIGRlcml2ZSB0aGUgTUxFIG9mICRcbGFtYmRhJC4KCgoKMikgU2FtcGxlICRuJCAoZS5nLiAxMDApIGRhdGEgZnJvbSBhIG5vcm1hbCBkaXN0cmlidXRpb24gYW5kIG1ha2UgTUxFcyBvZiB0aGUgbWVhbiAkXGhhdHtcbXV9JCBhbmQgdGhlIHZhcmlhbmNlICRcaGF0e1xzaWdtYV4yfSQuICAKYGBge3J9CgpgYGAKClJlcGVhdCBpdCAkbSQgKGUuZy4sIDEwMDApIHRpbWVzIGFuZCBzZWUgdGhlIGRpc3RyaWJ1dGlvbnMgb2YgdGhlIE1MRXMgJFAoXGhhdHtcbXV9KSQgYW5kICRQKFxoYXR7XHNpZ21hXjJ9KSQsIGUuZy4sIGhpc3RvZ3JhbSwgbWVhbiwgYW5kIHZhcmlhbmNlLiAgClNlZSBob3cgdGhlIGRpc3RyaWJ1dGlvbnMgY2hhbmdlIHdpdGggdGhlIHNhbXBsZSBzaXplICRuJC4KCmBgYHtyfQoKYGBgCgojIyAyLiBMaW5lYXIgUmVncmVzc2lvbgoKMSkgVGFrZSBhIGRhdGFzZXQgZnJvbSBSIGFuZCB0cnkgbGluZWFyIHJlZ3Jlc3Npb24KCmBgYHtyfQoKYGBgCgoyKSBDaGVjayB0aGUgZ29vZG5lc3Mgb2YgZml0IGJ5ICRSXjIkIGFuZCBjb21wYXJlIHRoYXQgd2l0aCBjb3JyZWxhdGlvbgoKYGBge3J9CgpgYGAKCiMjIDMuIE11bHRpcGxlIFJlZ3Jlc3Npb24KClRha2UgYSBkYXRlc2V0IHdpdGggdGhyZWUgb3IgbW9yZSBjb21wb25lbnRzLiAgCk1ha2UgZGlmZmVyZW50IG11bHRpcGxlIHJlZ3Jlc3Npb24gbW9kZWxzIGFuZCBjb21wYXJlICRSXjIkIHRvIHNlZSB3aGljaCBtb2RlbCBkZXNjcmliZXMgdGhlIHJlbGF0aW9uc2hpcCBiZXR0ZXIuCgpgYGB7cn0KCmBgYAoKIyMgNC4gVGFrZSBhIGZ1bmN0aW9uIG9mIHlvdXIgaW50ZXJlc3QgYW5kIGFwcGx5IHBvbHlub21pYWwgcmVncmVzc2lvbgoKMSkgVmlzdWxhbGl6ZSB0aGUgc2FtcGxlIHBvaW50cywgdGFyZ2V0IGZ1bmN0aW9uLCBhbmQgdGhlIHJlZ3Jlc3Npb24gZnVuY3Rpb25zIHdpdGggZGlmZmVyZW50IG9yZGVycyBvZiB0aGUgcG9seW5vbWlhbAoKYGBge3J9CgpgYGAKCjIpIENvbXBhcmUgdGhlIGF2ZXJhZ2Ugc3F1YXJlZCBkaWZmZXJlbmNlIG9mIHRoZSByZWdyZXNzaW9uIGZ1bmN0aW9uIGZyb20gICAKYTogdGhlIHNhbXBsZSBkYXRhIHVzZWQgZm9yIGZpdHRpbmcgIApiOiB0aGUgdGFyZ2V0IGZ1bmN0aW9uICAKYzogbmV3bHkgc2FtcGxlZCBkYXRhIG5vdCB1c2VkIGZvciBmaXR0aW5nCgpmb3IgZGlmZmVyZW50IG9yZGVycyAkayQsIHNhbXBsZSBzaXplICRucyQsIGFuZCB0aGUgbm9pc2UgbGV2ZWwgJFxzaWdtYSQuCgpgYGB7cn0KCmBgYAo=