linear models

• introduction
• recent notes
  • regularization
  • the regression line (freedman ch 2)
  • multiple regression (freedman ch 4)
• advanced topics
  • BLUE
  • GLS
  • path models
  • simultaneous equations
  • binary variables
  • LR with non-linear basis functions
  • locally weighted LR (lowess)
  • kernel regression
  • gam
• sums interpretation
• geometry - J. 6
• likelihood calcs
  • normal equation
  • ridge regression

• Material from “Statistical Models Theory and Practice” - David Freedman

---

introduction

• $Y = X \beta + \epsilon$

  type of linear regression	X	Y
  simple	univariate	univariate
  multiple	multivariate	univariate
  multivariate	either	multivariate
  generalized	either	error not normal

• minimize: $L(\theta) = ||Y-X\beta||_2^2 \implies \hat{\theta} = (X^TX)^{-1} X^TY$

• 2 proofs

  1. set deriv and solve
  2. use projection matrix H to show HY is proj of Y onto R(X)
     1. the projection matrix maps the responses to the predictions: $\hat{y} = Hy$
  • define projection (hat) matrix $H = X(X^TX)^{-1} X^T$
    • show $||Y-X \theta||^2 \geq ||Y - HY||^2$
    • key idea: subtract and add HY
• interpretation
  • if feature correlated, weights aren’t stable / can’t be interpreted
  • curvature inverse $(X^TX)^{-1}$ - dictates stability
  • importance: weight * feature value
• LS doesn’t work when p » n because of colinearity of X columns
• assumptions
  • $\epsilon \sim N(X\beta,\sigma^2)$
  • homoscedasticity: $var(Y_i|X)​$ is the same for all i
    • opposite of heteroscedasticity
• multicollinearity - predictors highly correlated
  • variance inflation factor (VIF) - measure how much the variances of the estimated regression coefficients are inflated as compared to when the predictors are not linearly related
• normal linear regression
  • variance MLE $\hat{\sigma}^2 = \sum (y_i - \hat{\theta}^T x_i)^2 / n$
    • in unbiased estimator, we divide by n-p
  • LS has a distr. $N(\theta, \sigma^2(X^TX)^{-1})$
• linear regression model
  • when n is large, LS estimator ahs approx normal distr provided that X^TX /n is approx. PSD
• weighted LS: minimize $\sum [w_i (y_i - x_i^T \theta)]^2$
  • $\hat{\theta} = (X^TWX)^{-1} X^T W Y$
  • heteroscedastic normal lin reg model: erorrs ~ N(0, 1/w_i)
• leverage scores - measure how much each $x_i$ influences the LS fit
  • for data point i, $H_{ii}$ is the leverage score
• LAD (least absolute deviation) fit
  • MLE estimator when error is Laplacian

recent notes

regularization

• when $(X^T X)$ isn’t invertible can’t use normal equations and gradient descent is likely unstable
  • X is nxp, usually n » p and X almost always has rank p
  • problems when n < p
• intuitive way to fix this problem is to reduce p by getting rid of features
• a lot of papers assume your data is already zero-centered
  • conventionally don’t regularize the intercept term

1. ridge regression (L2)
   • if (X^T X) not invertible, add a small element to diagonal
   • then it becomes invertible
   • small lambda -> numerical solution is unstable
   • proof of why it’s invertible is difficult
   • argmin $\sum_i (y_i - \hat{y_i})^2+ \lambda \vert \vert \beta\vert \vert _2^2 $
   • equivalent to minimizing $\sum_i (y_i - \hat{y_i})^2$ s.t. $\sum_j \beta_j^2 \leq t$
   • solution is $\hat{\beta_\lambda} = (X^TX+\lambda I)^{-1} X^T y$
   • for small $\lambda$ numerical solution is unstable
   • When $X^TX=I$, $\beta {Ridge} = \frac{1}{1+\lambda} \beta{Least Squares}$
2. lasso regression (L1)
   • $\sum_i (y_i - \hat{y_i})^2+\lambda \vert \vert \beta\vert \vert _1 $
   • equivalent to minimizing $\sum_i (y_i - \hat{y_i})^2$ s.t. $\sum_j \vert \beta_j\vert \leq t$
   • “least absolute shrinkage and selection operator”
   • lasso - least absolute shrinkage and selection operator - L1
   • acts in a nonlinear manner on the outcome y
   • keep the same SSE loss function, but add constraint of L1 norm
   • doesn’t have closed form for Beta
   • because of the absolute value, gradient doesn’t exist
   • can use directional derivatives
   • best solver is LARS - least angle regression - if tuning parameter is chose well, will set lots of coordinates to 0 - convex functions / convex sets (like circle) are easier to solve - disadvantages
   • if p>n, lasso selects at most n variables
   • if pairwise correlations are very high, lasso only selects one variable
3. elastic net - hybrid of the other two
   • $\beta_{Naive ENet} = \sum_i (y_i - \hat{y_i})^2+\lambda_1 \vert \vert \beta\vert \vert _1 + \lambda_2 \vert \vert \beta\vert \vert _2^2$
   • l1 part generates sparse model
   • l2 part encourages grouping effect, stabilizes l1 regularization path
   • grouping effect - group of highly correlated features should all be selected - naive elastic net has too much shrinkage so we scale $\beta_{ENet} = (1+\lambda_2) \beta_{NaiveENet}$ - to solve, fix l2 and solve lasso

the regression line (freedman ch 2)

• regression line
  • goes through $(\bar{x}, \bar{y})$
  • slope: $r s_y / s_x$
  • intercept: $\bar{y} - slope \cdot \bar{x}$
  • basically fits graph of averages (minimizes MSE)
• SD line
  • same except slope: $sign(r) s_y / s_x$
  • intercept changes accordingly
• for regression, MSE = $(1-r^2) Var(Y)$

multiple regression (freedman ch 4)

• assumptions
  1. assume $n > p$ and X has full rank (rank p - columns are linearly independent)
  2. $\epsilon_i$ are iid, mean 0, variance $\sigma^2$
  3. $\epsilon$ independent of $X$
     • $e_i$ still orthogonal to $X$
• OLS is conditionally unbiased
  • $E[\hat{\theta} | X] = \theta$
• $Cov(\hat{\theta}|X) = \sigma^2 (X^TX)^{-1}$
  • $\hat{\sigma^2} = \frac{1}{n-p} \sum_i e_i^2$
    • this is unbiased - just dividing by n is too small since we have minimized $e_i$ so their variance is lower than var of $\epsilon_i$
• random errors $\epsilon$
• residuals $e$
• $H = X(X^TX)^{-1} X^T$
  1. e = (I-H)Y = $(I-H) \epsilon$
  2. H is symmetric
  3. $H^2 = H, (I-H)^2 = I-H$
  4. HX = X
  5. $e \perp X$
• basically H projects Y int R(X)
• $E[\hat{\sigma^2}|X] = \sigma^2$
• random errs don’t need to be normal
• variance
  • $var(Y) = var(X \hat{\theta}) + var(e)$
    • $var(X \hat{\theta})$ is the explained variance
    • fraction of variance explained: $R^2 = var(X \hat{\theta}) / var(Y)$
    • like summing squares by projecting
  • if there is no intercept in a regression eq, $R^2 = ||\hat{Y}||^2 / ||Y||^2$

advanced topics

BLUE

• drop assumption: $\epsilon$ independent of $X$
  • instead: $E[\epsilon|X]=0, cov[\epsilon|X] = \sigma^2 I$
  • can rewrite: $E[\epsilon]=0, cov[\epsilon] = \sigma^2 I$ fixing X
• Gauss-markov thm - assume linear model and assumption above: when X is fixed, OLS estimator is BLUE = best linear unbiased estimator
  • has smallest variance.
  • prove this

GLS

• GLMs roughly solve the problem where outcomes are non-Gaussian
  • mean is related to $w^tx$ through a link function (ex. logistic reg assumes sigmoid)
  • also assume different prob distr on Y (ex. logistic reg assumes Bernoulli)
• generalized least squares regression model: instead of above assumption, use $E[\epsilon|X]=0, cov[\epsilon|X] = G, : G \in S^K_{++}$
  • covariance formula changes: $cov(\hat{\theta}_{OLS}|X) = (X^TX)^{-1} X^TGX(X^TX)^{-1}$
  • estimator is the same, but is no longer BLUE - can correct for this: $(G^{-1/2}Y) = (G^{-1/2}X)\theta + (G^{-1/2}\epsilon)$
• feasible GLS=Aitken estimator - use $\hat{G}$
• examples
  • simple
  • iteratively reweighted
• 3 assumptions can break down:
  1. if $E[\epsilon|X] \neq 0$ - GLS estimator is biased
  2. else if $cov(\epsilon|X) \neq G$ - GLS unbiased, but covariance formula breaks down
  3. if G from data, but violates estimation procedure, estimator will be misealding estimate of cov

path models

• path model - graphical way to represent a regression equation
• making causal inferences by regression requires a response schedule

simultaneous equations

• simultaneous-equation models - use instrumental variables / two-stage least squares
  • these techniques avoid simultaneity bias = endogeneity bias

binary variables

• indicator variables take on the value 0 or 1
  • dummy coding - matrix is singular so we drop the last indicator variable - called reference class / baseline class
  • effect coding
    • one vector is all -1s
    • B_0 should be weighted average of the class averages
  • orthogonal coding
• additive effects assume that each predictor’s effect on the response does not depend on the value of the other predictor (as long as the other one was fixed
  • assume they have the same slope
• interaction effects allow the effect of one predictor on the response to depend on the values of other predictors.
  • $y_i = β_0 + β_1x_{i1} + β_2x_{i2} + β_3x_{i1}x_{i2} + ε_i$

LR with non-linear basis functions

• can have nonlinear basis functions (ex. polynomial regression)
• radial basis function - ex. kernel function (Gaussian RBF)
  • $exp(-(x-r)^2 / (2 \lambda ^2))$
• non-parametric algorithm - don’t get any parameters theta; must keep data

locally weighted LR (lowess)

• recompute model for each target point
• instead of minimizing SSE, we minimize SSE weighted by each observation’s closeness to the sample we want to query

kernel regression

• nonparametric method

• $\operatorname{E}(Y

  X=x) = \int y f(y

  x) dy = \int y \frac{f(x,y)}{f(x)} dy$

  Using the [[kernel density estimation]] for the joint distribution ‘‘f(x,y)’’ and ‘‘f(x)’’ with a kernel ‘’’'’K’’’’’,

  $\hat{f}(x,y) = \frac{1}{n}\sum_{i=1}^{n} K_h\left(x-x_i\right) K_h\left(y-y_i\right)$ $\hat{f}(x) = \frac{1}{n} \sum_{i=1}^{n} K_h\left(x-x_i\right)$

  we get

  $\begin{align} \operatorname{\hat E}(Y

  X=x) &= \int \frac{y \sum_{i=1}^{n} K_h\left(x-x_i\right) K_h\left(y-y_i\right)}{\sum_{j=1}^{n} K_h\left(x-x_j\right)} dy,\ &= \frac{\sum_{i=1}^{n} K_h\left(x-x_i\right) \int y \, K_h\left(y-y_i\right) dy}{\sum_{j=1}^{n} K_h\left(x-x_j\right)},\ &= \frac{\sum_{i=1}^{n} K_h\left(x-x_i\right) y_i}{\sum_{j=1}^{n} K_h\left(x-x_j\right)},\end{align}$

gam

• generalized additive models: assume mean output is sum of functions of individual variables (no interactions)
  • learn individual functions using splines

sums interpretation

• SST - total sum of squares - measure of total variation in response variable
  • $\sum(y_i-\bar{y})^2$
• SSR - regression sum of squares - measure of variation explained by predictors
  • $\sum(\hat{y_i}-\bar{y})^2$
• SSE - measure of variation not explained by predictors
  • $\sum(y_i-\hat{y_i})^2$
• SST = SSR + SSE
• $R^2 = \frac{SSR}{SST}$ - coefficient of determination
  • measures the proportion of variation in Y that is explained by the predictor

geometry - J. 6

• LMS = least mean squares (p-dimensional geometries)

  • 
  • $y_n = \theta^T x_n + \epsilon_n$
  • $\theta^{(t+1)}=\theta^{(t)} + \alpha (y_n - \theta^{(t)T} x_n) x_n$

    • converges if $0 < \alpha < 2/

      x_n

      ^2$

    • 
    • 
  • if N=p and all $x^{(i)}$ are lin. indepedent, then there exists exact solution $\theta$

• solving requires finding orthogonal projection of y on column space of X (n-dimensional geometries)

  • 
  1. 3 Pfs
     1. geometry - $y-X\theta^*$ must be orthogonal to columns of X: $X^T(y-X\theta)=0$
     2. minimize least square cost function and differentiate
     3. show HY projects Y onto col(X)
  • either of these approaches yield the normal eqns: $X^TX \theta^* = X^Ty$

• SGD

  • SGD converges to normal eqn

• convergence analysis: requires $0 < \rho < 2/\lambda_{max} [X^TX]$

  • algebraic analysis: expand $\theta^{(t+1)}$ and take $t \to \infty$
  • geometric convergence analysis: consider contours of loss function

• weighted least squares: $J(\theta)=\frac{1}{2}\sum_n w_n (y_n - \theta^T x_n)^2$

  • yields $X^T WX \theta^* = X^T Wy$

• probabilistic interpretation

  • $p(y|x, \theta) = \frac{1}{(2\pi\sigma^2)^{N/2}} exp \left( \frac{-1}{2\sigma^2} \sum_{n=1}^N (y_n - \theta^T x_n)^2 \right)$
  • $l(\theta; x,y) = - \frac{1}{2\sigma^2} \sum_{n=1}^N (y_n - \theta^T x_n)^2$
    • log-likelihood is equivalent to least-squares cost function

likelihood calcs

normal equation

• $L(\theta) = \frac{1}{2} \sum_{i=1}^n (\hat{y}_i-y_i)^2$
• $L(\theta) = 1/2 (X \theta - y)^T (X \theta -y)$
• $L(\theta) = 1/2 (\theta^T X^T - y^T) (X \theta -y)$
• $L(\theta) = 1/2 (\theta^T X^T X \theta - 2 \theta^T X^T y +y^T y)$
• $0=\frac{\partial L}{\partial \theta} = 2X^TX\theta - 2X^T y$
• $\theta = (X^TX)^{-1} X^Ty$

ridge regression

• $L(\theta) = \sum_{i=1}^n (\hat{y}_i-y_i)^2+ \lambda \vert \vert \theta\vert \vert _2^2$
• $L(\theta) = (X \theta - y)^T (X \theta -y)+ \lambda \theta^T \theta$
• $L(\theta) = \theta^T X^T X \theta - 2 \theta^T X^T y +y^T y + \lambda \theta^T \theta$
• $0=\frac{\partial L}{\partial \theta} = 2X^TX\theta - 2X^T y+2\lambda \theta$
• $\theta = (X^TX+\lambda I)^{-1} X^T y$