ordinary least squares

OLS

MSE 를 cost function 으로 가지는 선형 회귀 모델에 대한 closed form solution

다음과 같은 선형 회귀 모델에 대한 RSS 가 있다고 해보자.

$$\mathrm{RSS}(\mathbf{w})=\frac{1}{2}\sum _{n=1}^N{\left(y_n-{\mathbf{w}}^{\top }{\mathbf{x}}_n\right)}^2=\frac{1}{2}\Vert \mathbf{X}\mathbf{w}-\mathbf{y}{\Vert }_2^2=\frac{1}{2}(\mathbf{X}\mathbf{w}-\mathbf{y}{)}^{\top }(\mathbf{X}\mathbf{w}-\mathbf{y})$$

이를 미분해서 gradient 를 구하면 다음과 같다.

$${\nabla }_{\mathbf{w}}\mathrm{RSS}(\mathbf{w})={\mathbf{X}}^{\top }\mathbf{X}\mathbf{w}-{\mathbf{X}}^{\top }\mathbf{y}$$

이제 gradient 를 0 으로 설정하면 normal equations 이라고 알려진 다음과 같은 식을 얻는다:

$${\mathbf{X}}^{\top }\mathbf{X}\mathbf{w}={\mathbf{X}}^{\top }\mathbf{y}$$

최적의 솔루션은 $y-\mathrm{X}w$ 이 $\mathbf{X}$ 의 범위에 대해 normal (orthogonal) 한 것이다.

즉, $\hat{\mathbf{w}}$ 에 대한 solution OLS 는 아래와 같다.

$$\hat{\mathbf{w}}={\left({\mathbf{X}}^{\top }\mathbf{X}\right)}^{-1}{\mathbf{X}}^{\top }\mathbf{y}$$

이는 system of linear equations $\mathbf{A}\mathbf{w}=\mathbf{b}$ 에서 $\mathbf{A}=\left({\mathbf{X}}^{\top }\mathbf{X}\right)$ 와 $\mathbf{b}={\mathbf{X}}^{\top }\mathbf{y}$ 일때, $\mathbf{w}$ 을 찾는 것과 같다.

B) OLS 는 Unique Global Minimum 을 가지는가?

OLS 의 solution 이 unique 한지 확인하기 위해서는 parameter $\mathbf{w}$ 의 Hessian matrix 가 positive definite 한지 알아보면 된다

$$\mathbf{H}(\mathbf{w})=\frac{{\partial }^2}{\partial {\mathbf{x}}^2}\mathrm{RSS}(\mathbf{w})={\mathbf{X}}^{\top }\mathbf{X}$$

만약 $\mathbf{X}$ 가 full [rank](the rank of a matrix) 인 경우, $\mathbf{H}$ 는 positive definite 하다.

여기서 full rank 인 경우는 $\mathbf{X}:={\left[{\mathbf{x}}_1,\dots ,{\mathbf{x}}_N\right]}^{\top }\in {\mathbb{R}}^{N\times D}$ 의 rank 가 $D$ 를 만족한다는 의미이고, positive definite 는 $\mathbf{v}>0$ 에 대해 ${\mathbf{v}}^{\top }\left({\mathbf{X}}^{\top }\mathbf{X}\right)\mathbf{v}=(\mathbf{X}\mathbf{v}{)}^{\top }(\mathbf{X}\mathbf{v})=\Vert \mathbf{X}\mathbf{v}{\Vert }^2>0$ 를 만족한다는 의미이다.

C) Computing Issue

$N\gg D$ 인 경우 ${\left({\mathbf{X}}^{\top }\mathbf{X}\right)}^{-1}$ 를 QR decomposition 을 통해 좀 더 빠르게 계산하는 방법이 있다: $\mathbf{X}=\mathbf{QR},$ where ${\mathbf{Q}}^{\top }\mathbf{Q}=\mathbf{I}$

• OLS 는 the system of linear equations $\mathrm{X}w=y$ 을 푸는 것과 동일하다는 점을 고려했을 때 QR decomposition 을 이용하면 다음과 같이 계산할 수 있다

$$\begin{array}{rl}(\mathbf{QR})\mathbf{w}& =\mathbf{y}\\ {\mathbf{Q}}^{\top }\mathbf{QR}\mathbf{w}& ={\mathbf{Q}}^{\top }\mathbf{y}\\ \mathbf{w}& ={\mathbf{R}}^{-1}\left({\mathbf{Q}}^{\top }\mathbf{y}\right)\end{array}$$

이때, $\mathbf{R}$ 은 upper triangular 이므로, backsubstitution 을 이용하면 matrix inversion 없이 equation 을 풀 수 있다.

other approaches: conjugate gradient, GMRES (generalized minimal residual method)

• Important issue
  • model 을 fitting 하기 전에, input feature 를 z-score 형태로 만드는 것이: zero mean and unit variance.

D) Solving for Offset and Slope Separately

$p(y\mid \mathbf{x},\mathbf{\theta })=\mathcal{N}\left(y\mid w_0+{\mathbf{w}}^{\top }\mathbf{x},{\sigma }^2\right)$ 에서 $\left(w_0,\mathbf{w}\right)$ 를 동시에 계산하는 방법 ($\mathbf{X}$ 에 $1$ column vector 추가) 도 있지만, 따로 계산할 수 있다.

$$\hat{\mathbf{w}}={\left({\mathbf{X}}_c^T{\mathbf{X}}_c\right)}^{-1}{\mathbf{X}}_c^T{\mathbf{y}}_c={\left[\sum _{i=1}^N\left({\mathbf{x}}_n-\overline{\mathbf{x}}\right){\left({\mathbf{x}}_n-\overline{\mathbf{x}}\right)}^T\right]}^{-1}\left[\sum _{i=1}^N\left(y_n-\bar{y}\right)\left({\mathbf{x}}_n-\overline{\mathbf{x}}\right)\right]$$

• ${\mathbf{X}}_c$ 는 centered input matrix 로, 행이 ${\mathbf{x}}_n^c={\mathbf{x}}_n-\overline{\mathbf{x}}$ 으로 구성됨 (${\mathbf{y}}_c=\mathbf{y}-\overline{\mathbf{y}}$ 는 centered output)

$${\hat{w}}_0=\frac{1}{N}\sum _n{y}_n-\frac{1}{N}\sum _n{\mathbf{x}}_n^T\hat{\mathbf{w}}=\bar{y}-{\overline{\mathbf{x}}}^T\hat{\mathbf{w}}$$

• $\hat{\mathbf{w}}$ 를 centered data 에 대해 계산하고, $\bar{y}-{\overline{\mathbf{x}}}^T\hat{\mathbf{w}}$ 를 통해 bias $w_0$ 를 계산

E) 단점

${\mathbf{X}}^{\top }\mathbf{X}$ 가 invertible 하지 않는 경우, 즉 singular 인 경우는 잘 동작하지 않는다.

이런 경우는 대부분 $m<n$ ($\mathbf{X}$ 는 $m\times n$ matrix) 이거나 일부 feature 가 불필요하는 경우다.

F) Related

G) References