Page cover image

#3: Linear Regression, Regularization, Bias-Variance

  • 4 min

#3: Linear Regression, Regularization, Bias-Variance content

Created
Topics
 

Linear Regression

Model Composition

pp-dimensional Input Vector x=[x1,x2,...,xp]x=[x_1,x_2,...,x_p]
Learnable Parameter Vector βT=[β0,β1,…,βp]\beta^{T}=\left[\beta_{0}, \beta_{1}, \ldots, \beta_{p}\right]
Target Function ff: assumed linear
Hypothesis Function gg: any linear function of parameters β\beta
g(x)=β0+∑i=1pβixig(x)=\beta_{0}+\sum_{i=1}^{p} \beta_{i} x_{i}

Loss Function (Error Metric)

Measures the discrepancy between the model prediction and the actual value on the training set

Residual Sum of Squares

Loss⁡(β)=RSS⁡(β)=∑i=1N(yi−gβ(xi))2=∑i=1N(yi−(β0+∑j=1pβjxji))2=∑i=1N(yi−β0−∑j=1pβjxji)2\begin{aligned}\operatorname{Loss}(\beta)=\operatorname{RSS}(\beta) &=\sum_{i=1}^{N}\left(y^{i}-g_{\beta}\left(x^{i}\right)\right)^{2} \\&=\sum_{i=1}^{N}\left(y^{i}-\left(\beta_{0}+\sum_{j=1}^{p} \beta_{j} x_{j}^{i}\right)\right)^{2} \\&=\sum_{i=1}^{N}\left(y^{i}-\beta_{0}-\sum_{j=1}^{p} \beta_{j} x_{j}^{i}\right)^{2}\end{aligned}

Training

🎯
Adjust β\beta to minimize loss
  1. Matrix Representation of the Hypothesis
    Subsume intercept/bias β0β_0 into the parameter vector ββ: βT=[β0,β1,…,βp]\beta^{T}=\left[\beta_{0}, \beta_{1}, \ldots, \beta_{p}\right]Augment input vector XX by 1: X=[1,x1,x2,…,xp]X=\left[1, x_{1}, x_{2}, \ldots, x_{p}\right]
    ⇒y=gβ(X)=X⋅β\Rightarrow y=g_{\beta}(X)=X \cdot \beta
  1. Compute the derivatives of RSS(β)RSS(\beta) and set it to zeroLoss⁡(β)=RSS(β)=(y−Xβ)T(y−Xβ)δRSSδβ=−2XT(y−Xβ)=0\operatorname{Loss}(\beta)=R S S(\beta)=(\mathbf{y}-\mathbf{X} \beta)^{T}(\mathbf{y}-\mathbf{X} \beta) \\ \frac{\delta R S S}{\delta \beta}=-2 \mathbf{X}^{T}(\mathbf{y}-\mathbf{X} \beta)=0
  1. Solve β\beta for the closed form solutionβ^=(XTX)−1XTy\hat{\beta}=\left(\mathbf{X}^{T} \mathbf{X}\right)^{-1} \mathbf{X}^{T} \mathbf{y}

Making Prediction

For a new observation x0x_0, its prediction can be computed as
y^0=[1x0]⋅β^=[1x0]⋅(XTX)−1XTy\begin{aligned}\hat{y}_{0} &=\left[1 x_{0}\right] \cdot \hat{\beta} \\&=\left[1 x_{0}\right] \cdot\left(\mathbf{X}^{T} \mathbf{X}\right)^{-1} \mathbf{X}^{T} \mathbf{y}\end{aligned}

Model Analysis

Significance of a Single Parameter

σ2\sigma^2 = variance of the observations assumed uncorrelated with constant variance
σ^2=1N−P−1∑i=1N(yi−y^i)2\hat{\sigma}^{2}=\frac{1}{N-P-1} \sum_{i=1}^{N}\left(y^{i}-\hat{y}^{i}\right)^{2}
For any variable βj\beta_{j} define the Z-score as zj=β^jσ^vjz_{j}=\frac{\hat{\beta}{j}}{\hat{\sigma} \sqrt{v{j}}}
  • vjv_{j} is the jth j^{\text {th }} diagonal element of (XTX)−1\left(X^{T} X\right)^{-1}
Result: smaller zjz_{j} → less important βj\beta_j

Significance of a Group of Coefficiants

F-statistics: measures the change in residual
F=(RSS0−RSS1)/(p1−p0)RSS1/(N−p1−1)F=\frac{\left(R S S_{0}-R S S_{1}\right) /\left(p_{1}-p_{0}\right)}{R S S_{1} /\left(N-p_{1}-1\right)}
  • RSS1R S S_{1} = residual sum of squares of the bigger model with p1+1p_{1}+1 parameters
  • RSS0R S S_{0} = residual sum of squares for the nested smaller model p0+1p_{0}+1

Regularization (Shrinkage Methods)

🎯
机器学习 = 训练集DD上的LossLoss 最小化问题 ⇒ F∗F^*容易过拟合
为对抗过拟合,向损失函数中加入描述模型复杂程度的正则项 Ω(F)\Omega(F)
Regularized Loss Function = Loss Function + Penalty Term

LpL_p Penalty =λ w=\lambda \> w

  • λλ = Regularization parameter
  • ww = weight associated with the variables
    • generally considered to be the LpL_p-norms

Usage

  • Help adjust complexity of hypothesis space
  • Balance fitness and generalizability

Ridge Regression

Implementation of L2L_2 Regularization
  • Penalty = squared magnitude (L2L_2-norm) of coefficients

Usage

  • Shrink the coefficients but greater than 0
  • Confine hypothesis space ⇒ make it smaller than the space of all linear functions
  • Output non-sparse

Model

β^ridge =argmin⁡β∑i=1N(yi−β0−∑j=1pxji⋅βj)2 subject to ∑j=1pβj2≤s\hat{\beta}^{\text {ridge }}=\operatorname{argmin}_{\beta} \sum_{i=1}^{N}\left(y^{i}-\beta_{0}-\sum_{j=1}^{p} x_{j}^{i} \cdot \beta_{j}\right)^{2} \\ \text { subject to } \sum_{j=1}^{p} \beta_{j}^{2} \leq s
  • Minimize ∑i=1N(yi−β0−∑j=1pxji⋅βj)2\sum_{i=1}^{N}\left(y^{i}-\beta_{0}-\sum_{j=1}^{p} x_{j}^{i} \cdot \beta_{j}\right)^{2}
  • Subject to constraint ∑j=1pβj2≤s\sum_{j=1}^{p} \beta_{j}^{2} \leq s
Rewritten as Lagrangian Multiplier
β^ridge =argmin⁡β[∑i=1N(yi−β0−∑j=1pxji⋅βj)2+λ∑j=1pβj2]\hat{\beta}^{\text {ridge }}=\operatorname{argmin}_{\beta}\left[\sum_{i=1}^{N}\left(y^{i}-\beta_{0}-\sum_{j=1}^{p} x_{j}^{i} \cdot \beta_{j}\right)^{2}+\lambda \sum_{j=1}^{p} \beta_{j}^{2}\right]

Loss Function

RSS(λ)=(y−Xβ)T(y−Xβ)+λβTβR S S(\lambda)=(\mathbf{y}-\mathbf{X} \beta)^{T}(\mathbf{y}-\mathbf{X} \beta)+\lambda \beta^{T} \beta

Closed Form Solution

β^ridge =(XTX+λI)−1XTy\hat{\beta}^{\text {ridge }}=\left(\mathbf{X}^{T} \mathbf{X}+\lambda \mathbf{I}\right)^{-1} \mathbf{X}^{T} \mathbf{y}

LASSO (Least Absolute Shrinkage and Selection Operator) Regression

Implementation of L1L_1 Regularization
  • Penalty = absolute value (L1L_1-norm) of coefficients

Usage

  • Penalize insignificant coefficients to zero
    ⇒ feature-selection method to remove useless coefficients
  • Prefers sparsity: less terms ⇒ better
    • With a lot of parameters, only some of them have predictive power
  • Output is sparse: some coefficients are left out

Model

β^lasso =argmin⁡β∑i=1N(yi−β0−∑j=1pxji⋅βj)2subject to∑j=1p∣βj∣≤t\hat{\beta}^{\text {lasso }}=\operatorname{argmin}{\beta} \sum{i=1}^{N}\left(y^{i}-\beta_{0}-\sum_{j=1}^{p} x_{j}^{i} \cdot \beta_{j}\right)^{2} \\\text{subject to} \sum_{j=1}^{p}\left|\beta_{j}\right| \leq t
  • Shrinkage Factor s=t∑j=1p∣βj∣s=\frac{t}{\sum_{j=1}^{p}\left|\beta_{j}\right|}

Bias-Variance Analysis

Purpose

express EoutE_{out} in a way that helps choosing the hypothesis space
  • How well H\mathscr{H} can approximate ff
  • How well we can zoom in on a good hypothesis h∈Hh\in \mathscr{H}
  • A theoretical process: Ex\mathbb{E}_x is not accessible in practice

Formula

Given:
  • gD=g^D= Dependence of gg on DD
  • Ex={E}_x= expectation over xx based on the distribution onX\mathscr{X}
  • ED[gD(x)]=\mathbb{E}_D[g^D(x)]= Average hypothesis over multiple draws of DD
 
notion image

Example

Given:
🚫 H1\mathscr{H}_1: High bias | Low Variance
✅ H2\mathscr{H}_2: Low bias | High Variance
Which one is better?
notion image
notion image
 
💡
Match the model complexity to the data resources NOT the target complexity ⇒ better generalizability Stick to the simplest answer!! (Occam's Razor)
 

Multi-Class Classification

💡
Use kk Logistic Regression models to classify kk classes

Likelihood for a Single Sample (Softmax Function)

P(yi=k∣xi)=eak∑j=1Keajak=wkT⋅xi,w∈RP×KP\left(y^{i}=k \mid x^{i}\right)=\frac{e^{a_{k}}}{\sum_{j=1}^{K} e^{a_{j}}} \quad a_{k}=\mathbf{w}_{k}^{T} \cdot x^{i} , \mathbf{w} \in \mathfrak{R}^{P \times K}
The softmax function is a function that turns a vector of KK real values into a vector of KK real values that sum to 1.

Likelihood of the Data

P(Y∣X)=∏i=1NP(yi∣xi)=∏i=1N∏j=1KP(yi=j∣xi)yji\begin{gathered}P(Y \mid X)=\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}\right)=\prod_{i=1}^{N} \prod_{j=1}^{K} P\left(y^{i}=j \mid x^{i}\right)^{y_{j}^{i}} \end{gathered}

Loss Function (Cross-Entropy Loss)

Lw=−log⁡[∏i=1NP(yi∣xi)]=−∑i=1N∑j=1Kyji⋅log⁡eak∑j=1Keaj\mathscr{L}_{w}=-\log \left[\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}\right)\right]=-\sum_{i=1}^{N} \sum_{j=1}^{K} y_{j}^{i} \cdot \log \frac{e^{a_{k}}}{\sum_{j=1}^{K} e^{a_{j}}}
  • yjiy_j^i value of output to the j-th xix_i