01 - Linear Regression - lec. 1,2,3

ucla | CS M146 | 2023-04-07T12:06

---

Table of Contents

• Definitions
• Lecture
  • Linear Regression Properties
    • Hypothesis function - linear w.r.t. weights @import url(‘https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css’)$\theta$
    • Loss Function - Least Squares Loss
  • Convex Functions - Optimization
    • Optimization Visual
  • Loss Optimization (Gradient Decent, Normal Equation)
  • Gradient Descent
    • Scaling - SGD, GD, MBGD
    • Full Batch Gradient Descent (GD)
    • Stochastic Gradient Descent (SGD)
    • Mini-batch Gradient Descent (MBGD)
  • Vectorization
  • Normal Equation
  • Linear Regression Recipe
• Discussion - Least Squares Gradient
• Resources

Definitions

• hypothesis function

  $h_{\theta }(\overrightarrow{x})\in \mathcal{H}$

  A function that maps inputs to outputs using input features (${\overrightarrow{x}}^{(i)}$) and labels ($y^{(i)}$) and belongs to a “hypothesis class ($\mathcal{H}$)” (a set of similar functions) by using arbitrary weights $\overrightarrow{\theta }$

  E.g. Linear regression hypothesis function:

  $h_{\theta }(\overrightarrow{x})={\theta }_0+{\theta }_1{x}_1+\dots +{\theta }_d{x}_d=\overrightarrow{{\theta }^T}\overrightarrow{x}$

• convex function

  • A real-valued function is convex if the line segment joining any two points lies above the function

Lecture

• Recall from lec. 1, an ML model takes features and labels aas inputs and returns a hypothesis function.

Linear Regression Properties

Hypothesis function - linear w.r.t. weights @import url(‘https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css’)$\theta$

• Parametrized

$h_{\overrightarrow{\theta }}(\overrightarrow{x})={\theta }_0+{\theta }_1{x}_1+\dots +{\theta }_d{x}_d\overrightarrow{x}\theta \in R^{d+1}$

• Vectorized ($x_0=1$)

$h_{\overrightarrow{\theta }}(\overrightarrow{x})=\sum _{j=0}^d{\theta }_j{x}_j={\overrightarrow{\theta }}^T\overrightarrow{x}$

• ${\theta }_0$ is the bias parameter and ${\theta }_{1:d}$ are the weights

• Visualized with a graph for multiple dimensions

Loss Function - Least Squares Loss

• Intuitively, sps. $d=1,{\theta }_0=0⟹x\in \text{R},\overrightarrow{\theta }=[0,{\theta }_1]$

$J(\overrightarrow{\theta })=\frac{1}{2n}\sum _{i=1}^n(h_{\overrightarrow{\theta }}({\overrightarrow{x}}^{(i)})-y^{(i)}{)}^2$

Convex Functions - Optimization

• a function is convex iff for all $t\in [0,1]$ and $x_1,x_2\in X$, the line through 2 point of the function lies above the function itself

  $f(t{x}_1+(1-t)x_2)\le tf(x_1)+(1-t)f(x_2)$

• strictly convex - the inequality is strict, no flat surface in the function
• Least squares is convex and differentiable w.r.t. $\theta$ → convex functions have a unique optima (minima)

Optimization Visual

Blue is a minima, gradient outward to red

Loss Optimization (Gradient Decent, Normal Equation)

• Given loss function $J(\overrightarrow{\theta })$ we want to find $\underset{\overrightarrow{\theta }}{min}J(\overrightarrow{\theta })$

• choose initial values of $\overrightarrow{\theta }$ and select new until we reach a minima (chaotic - location of minima depends heavily on the values of parameters chosen)
• convex functions have a unique minima
• normalized los function

Gradient Descent

• given an initial parameters $\overrightarrow{\theta }$, we can recursively update theta by moving against (down) the gradient by some step size called the learning rate $\alpha$:

${\theta }_j\leftarrow {\theta }_j-\alpha \cdot \frac{\partial }{\partial {\theta }_j}J(\overrightarrow{\theta })\text{simultaneous per }j$

• PROOF: indexed partial of least squares

• convergence - when gradient is close to 0: $

  \vec\theta_{new}-\vec\theta_{old}

  _2\lt \epsilon$

  • L2 Norm $

    \vec v

    _2$ - calculates distance (magnitude) of vector from origin

  $

  \vec v

  2=\sqrt{\sum_i v_i^2}=\sqrt{v_1^2+v_2^2+…+v^2{

  v

  }}$

Scaling - SGD, GD, MBGD

• Mean squared error

$J(\overrightarrow{\theta })=\frac{1}{n}\sum _{i=1}^n\ell ({\overrightarrow{x}}^{(i)},y^{(i)},\overrightarrow{\theta })$

• $\ell ({\overrightarrow{x}}^{(i)},y^{(i)},\overrightarrow{\theta })$ is the least squared error of $h_{\overrightarrow{\theta }}(\overrightarrow{x})$ for features and labels

Full Batch Gradient Descent (GD)

$\overrightarrow{\theta }\leftarrow \overrightarrow{\theta }-\alpha \frac{1}{n}\sum _{=1}^n(h_{\overrightarrow{\theta }}({\overrightarrow{x}}^{(i)})-y^{(i)}){\overrightarrow{x}}^{(i)}$

• computing average gradient over $n$ training instances (simultaneously) is $O(n)$* time (slow)
• SEE: quantum computing for finding GD for each example simultaneously
• *is actually $O(n\cdot d)$ but generally $n\gg d$
• finding the true loss relative to the population (dataset)

Stochastic Gradient Descent (SGD)

• computes gradient for every example, relative to the example - iterated over examples in batches → calculating per example loss

$\overrightarrow{\theta }\leftarrow \overrightarrow{\theta }-\alpha {\mathrm{\nabla }}_{\overrightarrow{\theta }}\ell ({\overrightarrow{x}}^{(i)},y^{(i)},\overrightarrow{\theta })$

$\overrightarrow{\theta }\leftarrow \overrightarrow{\theta }-\alpha (h_{\overrightarrow{\theta }}({\overrightarrow{x}}^{(i)})-y^{(i)}){\overrightarrow{x}}^{(i)}$

• GD vs SGD comparison (visual)
• pros: memory efficient, computationally cheap, implicit regularization (see further)
• cons: high noise, does not exploit GPUs to fullest

Mini-batch Gradient Descent (MBGD)

• sample a batch of $B$ points $D_B$ at random from full dataset $D$ (w/o replacement)

$\overrightarrow{\theta }\leftarrow \overrightarrow{\theta }-\alpha \frac{1}{B}\sum _{({\overrightarrow{x}}^{(i)},y^{(i)})\in D_B}{\mathrm{\nabla }}_{\overrightarrow{\theta }}\ell ({\overrightarrow{x}}^{(i)},y^{(i)},\overrightarrow{\theta })$

• $B=1⟹\text{SGD}$
• $B=n⟹\text{GD}$

• comparison visual

Vectorization

• compact equations, faster code - see discussion

Normal Equation

• finding the optimal $\overrightarrow{\theta }$ (weights/parameters) analytically s.t. $\frac{\partial }{\partial \overrightarrow{\theta }}J(\overrightarrow{\theta })$

• Optimized Normal Equation

$\overrightarrow{\theta }=(X^{T}X{)}^{-1}{X}^T\overrightarrow{y}$

• if $X$ is not invertible, try pseudo-inverse (np.linalg.pinv(X)), remove linearly dependent features, remove extra features s.t. $d\le n$
• normalized loss function

Linear Regression Recipe

Loss gradient

Discussion - Least Squares Gradient

Resources

---

📌

**SUMMARY
**