ML - 09 Regression

Basic Idea

이제 classifier를 벗어나 회귀문제를 다룬다. 여전히 dataset은 ${(x_i, y_i)}_{i=1}^N$ 이지만, $y_i$는 discrete한 class label이 아니라 continuous한 real number이다.

Loss function은 squared error를 사용한다. 즉, $\text{Loss} = (\text{guess} - \text{actual})^2$

Model

Classifier에서처럼 linear model을 사용한다.

\[h(x; \theta, \theta_0) = \theta^T x + \theta_0\]

마찬가지로 이것을 최적화 문제로 보고

\[J(\theta, \theta_0) = \frac{1}{n} \sum_{i=1}^n (\theta^T x + \theta_0 - y_i)^2\]

를 최소화하는 $\theta$와 $\theta_0$를 찾는다.

Ordinary Least Squares

다행히 이 문제는 Analytic solution이 존재한다.

\[W = \begin{bmatrix} x_1^{(1)} & x_2^{(1)} & \cdots & x_d^{(1)} \\ x_1^{(2)} & x_2^{(2)} & \cdots & x_d^{(2)} \\ \vdots & \vdots & \ddots & \vdots \\ x_1^{(n)} & x_2^{(n)} & \cdots & x_d^{(n)} \\ \end{bmatrix} \quad T = \begin{bmatrix} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(n)} \\ \end{bmatrix}\]

위처럼 dataset을 행렬로 정의하자. 평소와 다르게 dataset이 transpose된 형태임을 알 수 있다. 대부분의 textbook에서 위처럼 정의하고, 이후 $W\theta$로 표현하는데 편의가 있기에 위의 형태를 사용한다. 그러면 $J$를 아래처럼 손쉽게 표현할 수 있고 미분후 $0$으로 놓아 최적해를 구할 수 있다.

\[\begin{align*} J(\theta) &= \frac{1}{n} (W\theta - T)^T (W\theta - T) \\ \nabla J(\theta) &= \frac{2}{n} W^T (W\theta - T) = 0 \\ &\Rightarrow W^T W \theta = W^T T \\ &\Rightarrow \theta = (W^T W)^{-1} W^T T \end{align*}\]

$\nabla J(\theta)$ 유도

1. 미분연산자

$e = W\theta - T$라고 하자. 그러면 $J(\theta) = \frac{1}{n} e^T e$가 된다. $de^T e = e^T de$ 이므로

\[dJ = d\left( \frac{1}{n} e^T e \right) = \frac{1}{n} (de^T e + e^T de) = \frac{2}{n} e^T de\]

$e$는 $W\theta - T$이므로 $de = W d\theta$가 된다. 따라서

\[dJ = \frac{2}{n} e^T W d\theta\] \[dJ = (\nabla J)^T d\theta\]

이기에, gradient는 $\nabla J = \frac{2}{n} W^T e= \frac{2}{n} W^T (W\theta - T)$가 된다.

2. 행렬미분

잘 정리하면 미소 연산자 없이도 미분이 된다.

\[\begin{align*} J(\theta) &= \frac{1}{n} (W\theta - T)^T (W\theta - T) \\ &= \frac{1}{n} \left[ \theta^T W^T W \theta - 2 T^T W \theta + T^T T \right] \end{align*}\]

여기서 $W^TW$는 symmetric 하기에

\[\nabla_\theta (\theta^T W^T W \theta) = 2 W^T W \theta\]

가 되고 $T^T W \theta$는

\[\nabla_\theta (T^T W \theta) = W^T T\]

마지막으로 남은 항 $T^T T$는 $\theta$에 의존하지 않기에 미분하면 $0$이 된다.

따라서

\[\nabla J(\theta) = \frac{1}{n} (2 W^T W \theta - 2 W^T T) = \frac{2}{n} W^T (W\theta - T)\]

참고: 행렬 미분에서 $q(x) = x^T A x$의 gradient는 $\nabla_x q(x) = (A + A^T)x$가 된다. $A$가 symmetric 하기에 $2Ax$가 된다.

Regularization

먼저 아래의 질문을 답해보자.

1. $W^T W$가 invertible하지 않다면 어떻게 되는가?
2. overfitting이 발생할 수 있지 않은가?

위 문제들은 정규화를 통해 해결할 수 있다. 정확히는 ridge regression을 통해 해결하고자 한다.

L2 regularization term을 추가하여 아래와 같이 최적화 문제를 정의하자.

\[J(\theta) = \frac{1}{n} \sum_{i=1}n (\theta^T x + \theta_0 - y_i)^2 + \lambda \|\theta|^2\]

이렇게 잡으면, loss function은 0에 가까운 $\theta$를 선호하게 된다.

여기서 $\theta_0$는 전반적인 데이터의 평균을 맞추는 역할을 하기에 regularization term에서 제외한다.

Invertible 증명

미분 과정을 생략하면 최종적으로

\[\theta = (W^T W + \lambda I)^{-1} W^T T\]

가 된다. 즉, $W^T W + \lambda I$가 invertible해야 한다. $W^T W$는 positive semi-definite matrix이기에, 모든 eigenvalue가 0 이상이다. $\lambda I$는 positive definite matrix이기에, 모든 eigenvalue가 $\lambda$ 이상이다. 따라서 $\lambda>0$이라면 $W^T W + \lambda I$의 모든 eigenvalue는 0보다 크다. 즉, $W^T W + \lambda I$는 invertible하다.

Error Analysis

• Structural error: 모델이 데이터의 패턴을 표현할 수 없는 경우 발생하는 에러.
• Estimation error: 모델이 데이터의 패턴을 표현할 수 있지만, 학습 데이터가 부족하여 모델이 패턴을 제대로 학습하지 못하는 경우 발생하는 에러.

$\lambda$를 올릴 수록 structural error는 증가하지만 estimation error는 감소한다. 반대로 $\lambda$를 낮출 수록 structural error는 감소하지만 estimation error는 증가한다.

Time Complexity

한편 $\theta = (W^T W + \lambda I)^{-1} W^T T$의 계산은 $W^TW$ term에 의해 $O(d^3)$의 시간복잡도를 가진다.

Relation to Gradient Descent

위처럼 시간 복잡도가 높기에 gradient descent로 최적해를 구하는 방법도 있다. OLS는 convex이기에 gradient descent로 최적해가 보장죄기 때문이다.