Linear Regression

1. Introduction

 

기계학습(machine learning)의 기본 목적은 주어진 데이터를 해석하여 미래에 발생할 일을 예측하고자 하는 것 이다. 예를 들어, 어떤 에어컨 판매 회사의 연도별 판매 대수를 아래의 그림 1의 왼쪽과 같이 알고 있다면, 앞으로의 판매량을 예측하는데 기계학습을 이용할 수 있다.

 

그림 1. (Left)2011~2020년의 에어컨 판매 대수와 (Right)선형 모델을 통한 미래 데이터의 예측

위 데이터로부터 향후의 에어컨 판매량을 예측할 수 있는 가장 쉬운 방법은 그림 1의 오른쪽과 같이 데이터에 잘 맞는 직선을 하나 정하는 것 임을 직관적으로 알 수 있다. 즉, 주어진 데이터를 가장 잘 설명하는 선형 모델(linear model)로 부터 값을 추정하는 방법이며 이 선형 모델을 정하는 것(흔히 linear model을 modeling한다고 표현한다)을 선형 회귀(linear regression)라고 한다.

 

2. Statistical Approach

 

일반적으로 선형 회귀에서는 잔차(residual)의 합을 최소화 하는 모델을 데이터를 가장 잘 설명하는 선형 모델로 정의하는데, 여기서 잔차란 그림 2의 green line으로 표시된 것으로 모델에 의한 추정 값(black point)과 실제 데이터의 값(red point)의 차이를 의미한다.

그림 2. 모델(blue line)에 의한 추정값(black point)과 실제 데이터의 값(red point)의 차이를 잔차(green line)으로 정의한다. 선형 회귀를 통해 이 잔차의 합을 최소화 하는 선형 모델을 구한다.

잔차를 최소화하는 선형 모델이 왜 데이터를 가장 잘 설명하는 모델이 되는지에 대해서 직관적으로는 이해되겠지만, 좀 더 정확히 그 의미를 알기 위해서는 확률 통계적 접근이 필요하며 이를 위해서는 먼저 아래와 같은 가정이 필요하다.

 

(가정)

 

모든 데이터(red point)는 '관측'되었다고 표현하며 데이터를 일종의 '관측치'로 가정한다. 모든 데이터는 독립적으로 관측되었으며 데이터가 관측될 확률을 표현하는 확률 분포는 평균이 추정값이고 표준편차가 $\sigma$라고 가정한다(independent identically distributed, i.i.d).

 

그림 3. 각 데이터에 대한 likelihood

 

모델이 정해졌을 때 데이터가 관측될 확률은 그림 3의 gray line으로 표현되어있으며 앞서 언급한 바와 같이 추정값이(black point) 평균이고 일정한 표준 편차를 가진 정규분포다. 따라서, 모델이 주어졌을 때 즉, $y=a*x+b$라는 직선이 정해졌을 때 그림 3의 관측치 $y_2$가 관측될 확률은 다음과 같다.

 

$$ P(y_2 | model) = \mathcal{N}(y_2; \hat{y}_2, \sigma^2) $$

 

따라서, 특정 데이터에서 이 확률을 높이는 것은 해당 데이터의 추정값과 측정값 사이의 잔차를 줄이는 것으로 해석될 수 있다. 반대로 잔차를 줄인다는 것은 주어진 모델에서 데이터가 관측될 확률을 최대화 한다는 것으로 이해할 수 있다.

 

3. Maximum Likelihood Estimation(MLE)

 

이렇게 모델이 주어졌을 때 데이터가 관측될 확률을 likelihood(우도, 가능도)라고 하며 전체 데이터에 대한 likelihood를 최대화 하는 모델을 데이터를 가장 잘 설명하는 모델로 정의한다. 이 기법을(likelihood를 최대화 하는 것)을 Maximum Likelihood Estimation(MLE)이라고 한다.

전체 데이터의 likelihood는 아래와 같이 joint probability distribution으로 나타낼 수 있다.

 

$$ P(y_0, y_1, \ ... \ , y_{10} | model) $$

 

모든 데이터가 독립적으로 관측되었다고 가정하였으므로 이를 다음과 같이 모든 likelihood들의 곱으로 표현할 수 있다.

 

$$ P(y_0, y_1, \ ... \ , y_{10} | model) = \prod_{i}{P(y_i | model)} = \prod_{i}{\eta*exp\Big{(}-\frac{(y_i-\hat{y}_i)^2}{2\sigma^2}\Big{)}} $$

 

위 식에 log를 취하면 다음과 같이 식을 바꿀 수 있고 이를 log likelihood라고 한다.

 

$$ log(P(y_0, y_1, \ ... \ , y_{10} | model)) = \sum_{i}{\Big{(}-\frac{(y_i-\hat{y}_i)^2}{2\sigma^2}\Big{)}} + \alpha $$

 

따라서 위 식을 최대화 하는 또는 $\sum_{i}{\frac{(y_i-\hat{y}_i)^2}{2}}$를 최소화 하는 $a$와 $b$가 likelihood를 최대화 하는 parameter이며 $\sum_{i}{\frac{(y_i-\hat{y}_i)^2}{2}}$를 Sum Squared Error(SSE)라고 한다.

SSE를 이용하여 다음과 같이 MLE에 의한 linear regression 문제를 정의할 수 있다.

 

$$ {a^*, b^*} = \underset{a,b}{argmin} \sum_{i}{\frac{(y_i-\hat{y}_i)^2}{2}} = \underset{a,b}{argmin} \sum_{i}{\frac{(y_i-(a*x_i + b))^2}{2}} $$

 

4. Gradient Descent

 

위 문제를 푸는($a^*, b^*$를 구하는) 대표적인 방법으로는 gradient descent가 있다. Gradient descent는 오차 함수(검은색 곡선)가 convex(오목함수)일 때, 그림 4와 같이 오차 함수의 기울기 반대 방향으로 parameter를 움직여 최적의 parameter를 찾는 방법이다. 

 

 

그림 4. Convex 형태의 오차함수에서 gradient descent를 통한 최적해 계산

 

주어진 문제에서는 parameter가 두개 이므로 다음과 같이 각각 오차에 대한 편미분을 계산하여 기울기의 반대 방향으로 점진적으로 값을 업데이트 한다. 

 

$$ a_{update} = a - \alpha*(\frac{\partial C}{\partial a}) = a - \alpha*\sum_i{(-x_i*(y_i-(ax_i+b)))}$$

$$ b_{update} = b - \alpha*(\frac{\partial C}{\partial b}) = b - \alpha*\sum_i{(-y_i+(ax_i+b))} $$

 

여기서 $\alpha$는 step size로 parameter를 한 번 update할 때 얼마나 움직일 지를 결정하는 값이다. 이 값이 너무 크면 minimum에 수렴하기가 어렵고(over shooting) 너무 작으면 수렴하기까지 시간이 오래걸리므로 적절한 수치를 정해줄 필요가 있다.

 

5. Least Squares

Gradient descent가 점진적인 update를 통해 해를 찾아가는 방법이라면 least squares는 square error를 최소화 하는 해를 직접적으로 구하는 방법이다. Least squares에는 해석적(analytic)방법과 대수적(algebraic)방법이 있는데, 해석적 방법은 이차식에서 함수값이 최소가 되는 점이 미분값이 0이되는 점 이라는 것을 이용하여 다음과 같이 $a,b$를 구한다.

$$ \sum_i{(-x_i*(y_i-(ax_i+b)))} = 0$$

$$ \sum_i{(-y_i+(ax_i+b))} = 0 $$

위 식을 정리하면 다음과 같은 행렬 형태로 나타낼 수 있으며, 역행렬을 통한 계산으로 $a,b$를 구할 수 있다.

$$ \begin{bmatrix} \sum_i{x_i^2} \ \sum_i{x_i} \\ \sum_i{x_i} \ \ \ \ \ 1 \ \ \ \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} \sum_i{x_i y_i} \\ \sum_i{y_i} \end{bmatrix} $$

대수적 방법은 앞서 설명한 모델 추정 문제를 다음과 같이 선형 연립 방정식으로 만들어 해를 구하는 방법이다. 

$$ \begin{bmatrix} x_0 \ 1 \\ x_1 \ 1 \\ \vdots \ \vdots \\ x_9 \ 1 \end{bmatrix}   \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_9 \end{bmatrix}$$

$$ A\textbf{x} = \textbf{b} $$

일반적으로 A가 square matrix가 아니므로 inverse 대신 pseudo inverse를 사용하여 다음과 같이 계산한다.

$$ \textbf{x} = pinv(A)\textbf{b} $$

$$ \textbf{x} = (A^T A)^{-1}A^T \textbf{b} $$

대수적 방법 역시 잔차를 줄이는 방법인데, 잔차의 제곱합을 $||A\textbf{x}-\textbf{b}||^2$로 정의하고 이를 $\textbf{x}$에 대하여 편미분 하여 0으로 두면 다음과 같은 식을 만족한다.

$$ -2A^T(\textbf{b}-A\textbf{x}) = 0 $$

따라서 잔차의 제곱합을 최소화 하는 $\textbf{x}$는 $(A^TA)^{-1}A^T\textbf{b}$가 된다.

 

 

Reference

[1] Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2013). An introduction to statistical learning : with applications in R. New York :Springer,