Linear Regression with Gradient Descent

Formalisms:

Given data $X=\{x^{(1)},\dots ,x^{(n)}\}$ corresponding to labels $\mathbf{y}=\{y^{(1)},\dots ,y^{(n)}\}$, find $h:{\mathbb{R}}^d\to \mathbb{R}$, where $h\in H\text{ (i.e. the set of all hypothesis)}$ performs best according with the evaluation criteria.

$$h(\mathbf{x})=\sum _{j=1}^d{\theta }_j{\mathbf{x}}_j+{\theta }_0{\mathbf{x}}_0={\theta }^{\top }\mathbf{x},\text{ where x0 = 1}$$

And then we can define the Cost Function as:

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

where we minimize $J(\theta )$ to find the model parameters $\theta$.

Gradient Descent

• initialize $\theta$
• Repeat until convergence

$${\theta }_j\leftarrow {\theta }_j-\alpha \frac{\partial }{\partial {\theta }_j}J(\theta )$$

For linear regression:

$$\begin{array}{rl}\frac{\partial }{\partial {\theta }_j}J(\theta )& =\frac{\partial }{\partial {\theta }_j}\frac{1}{2n}\sum _{i=1}^n(h_{\theta }(x^{(i)})-y^{(i)}{)}^2\\ & =\frac{\partial }{\partial {\theta }_j}\frac{1}{2n}\sum _{i=1}^n(h_{\theta }(x^{(i)})-y^{(i)}{)}^2\to \text{consider it as }(u^2{)}^{\prime }=2\times u\times u^{\prime }\\ & =\frac{1}{n}\sum _{i=1}^n(h_{\theta }(x^{(i)})-y^{(i)})\times \frac{\partial }{\partial {\theta }_j}(h_{\theta }(x^{(i)})-y^{(i)})\\ & =\frac{1}{n}\sum _{i=1}^n(\sum _{k=0}^d{h}_{\theta }(x^{(i)})-y^{(i)})\times \frac{\partial }{\partial {\theta }_j}(\sum _{k=0}^d{\theta }_k{x}_k^{(i)}-y^{(i)})\\ & =\frac{1}{n}\sum _{i=1}^n(\sum _{k=0}^d{h}_{\theta }(x^{(i)})-y^{(i)})(x_j^{(i)})\end{array}$$

• Assume convergence when $||{\theta }_{new}-{\theta }_{old}|{|}_2<ϵ$

page 53.