선형회귀 알고리즘
기본적인 개념
회귀분석(Regression Analysis)
회귀분석은 D차원 벡터 독립 변수 x(수치형 설명변수)와 이에 대응하는 스칼라 종속 변수 y(연속형 숫자)간의 관계를 정량적으로 찾아내는 작업.
회귀분석에서는 결정론적 모형과 확률적 모형이 있다.
결정론적 모형(Deterministic Model)
독립 변수 x에 대해 대응하는 종속 변수 y와 가장 비슷한 값 y-hat을 출력하는 함수 f(x)를 찾는 과정
만약 독립 변수 x와 이에 대응하는 종속 변수 y간의 관계가 다음과 같은 선형 함수 f(x)이면 선형 회귀분석(linear regression analysis)이라고 한다.
위 식에서 w를 함수 f(x)의 계수(coefficient)이자 이 선형 회귀모형의 모수(parameter)라고 한다.
상수항 결합(Bais Augmentation)
상수항이 0이 아닌 회귀분석모형인 경우에는 수식을 간단하게 만들기 위해 상수항을 독립변수에 추가한다. 이를 상수항 결합(bias augmentation)이라고 한다.
OLS(Ordinary Least Squares)
가장 기본적인 결정론적 선형 회귀 방법으로 잔차제곱합(RSS: Residual Sum of Squares)를 최소화하는 가중치 벡터를 행렬 미분으로 구하는 방법.
우리가 사용하는 예측 모형은 다음과 같이 상수항이 결합된 선형 모형임.
이때 잔차 벡터(residual vector) e는
잔차 제곱합(RSS:residual sum of squares)은
이다. 잔차의 크기 즉, 잔차 제곱합을 가장 작게 하는 가중치 벡터를 구하기 위해 잔차 제곱합의 그레디언트(gradient) 벡터를 구하면 다음과 같다.
잔차의 최소가 되는 최적화 조건은 그래디언트 벡터가 0벡터이어야 하므로 다음식이 성립한다.
만약 X^T*X 행렬의 역행렬이 존재한다면 다음처럼 최적 가중치 벡터 w*를 구할 수 있다.
X^T*X 행렬의 역행렬이 존재하고 위에서 구한 값이 f(w)의 최고값이 아닌 최저값이 되려면 X^T*X가 양의 정부호(positive define) 행렬이어야 한다. 만약 X가 풀랭크가 아니면 즉, X의 각 행렬이 서로 독립이 아니면 X^T*X가 양의 정부호가 아니고 역행렬이 존재하지 않으므로 위와 같은 해를 구할 수 없다.
직교 방정식
여기에서 그래디언트가 0벡터가 되는 관계를 나타내는 다음 식을 직교 방정식(normal equation)이라고 한다.
직교 방정식을 인수 분해하면
즉, c_d가 모든 데이터의 d번째 차원의 원소로 이루어진 데이터 벡터(특징 행렬의 열벡터)라고 할 때 모든 차원 d(d=0, …, D)에 대해 c_d는 잔차 벡터 e와 수직을 이룬다.
또는
직교 방정식으로부터 다음과 같은 성질을 알 수 있다.
(1) 모형에 상수항이 있는 경우에 잔차 벡터의 원소의 합은 0이다. 즉, 잔차의 평균은 0이다.
(2) x 데이터의 평균값 x-bar에 대한 예측값은 y데이터의 평균값 y-bar이다.
1번 성질은 상수항 결합이 되어 있으면 X의 첫번째 열이 1-벡터라는 것을 이용하여 증명할 수 있다.
2번 성질은 다음처럼 증명한다.
경사 하강법
Gradient Descent (GD)는 여러 종류의 문제에서 최적의 해법을 찾을 수 있는 일반적인 최적화 알고리즘
임의의 점에서 그 점으로부터 감소하는 기울기를 구간을 찾아 이동하는 것을 반복함으로써 해를 구하는 방법.
비용 함수를 최소화하기 위해 반복해서 파라미터를 재조정하는 것이다. 한번에 MSE가 감소하는 방향으로 진행하여 알고리즘이 최솟값에 수렴할 때까지 점진적으로 향상
중요파라미터 : 스텝의 크기(α) ; 학습률(learning rate)을 하이퍼파라미터로 결정
문제 : 무작위 초기화 때문에 전역 최솟값(global minimuml 우리가 찾고자 하는 값)이 아니라 지역 최솟값(local minimum)에 수렴함.
하지만 선형 회귀를 위한 MSE 비용함수는 convex function;볼록 함수 이므로 경사하강법을 적용할 수 있다. (convex function의 최솟값, 즉 비용함수의 최솟값을 찾는 데에 수치해석적인 방법이 사용된다.)
배치 경사 하강법
배경 : 경사 하강법을 구현하려면 각 모델 θ에 대해 비용 함수의 그래디언트를 계산해야함. 다시 말해, θ가 조금 변경될 때 비용 함수가 얼마나 바뀌는지 계산해야한다. → computation 증가.
개념 : 경사 하강법 매 스탭마다 전체 훈련 세트(X)에 대해 계산함.
장점 : 경사 하강법은 특성 수에 민감하지 않아서 수십만 개의 특성에서 선형 회귀를 훈련시키면 정규방정식보다 경사 하강법이 훨씬 빠름.
단점 : 매우 큰 훈련세트에서는 아주 느림.
확률적 경사 하강법 (SGD; Stochastic Gradient Descent)
배경 : 배치 경사 하강법의 경우 매 스탭에서 전체 훈련 세트를 사용하다보니 훈련 세트가 커지면 매우 느림.
개념 : 매 스탭에서 딱 한 개의 샘플을 무작위로 선택하여 그 샘플에 대한 그래디언트를 계산함.
장점 : 매 반복에서 매우 적은 데이터만 처리하기 때문에 빠르다. 큰 훈련세트에서도 적용가능함.
비용 함수가 불규칙하면 지역 최솟값을 건너 뛸 수도 있기 때문에 전역 최솟값을 찾을 가능성이 높다. → 학습률을 점진적으로 감소시켜서 해결한다.
단점 : 무작위로 샘플을 선택하기 때문에 불안정함.
미니배치 경사 하강법
배경 : 각 스탭에서의 전체 데이터셋을 쓰고 싶지도 않고, 하나의 샘플만으로 그래디언트를 계산하기도 싫다!
개념 : 위 두 가지를 아우를 수 있게, 임의의 작은 샘플 세트에 대해 그래디언트를 계산함.
장점 : SGD보다 덜 불규칙하게 움직이기 때문에 최솟값에 더 가까이 도달
단점 : SGD보다 지역 최솟값에서 빠져나오기는 더 힘들다.
정리
선형회귀(Linear Regression)에서는 독립변수에 대해 이에 대응하는 종속변수를 예측할 수 있도록, 특성 가중치 합과 편향을 통해 예측을 만드는 과정이다. 그 과정에서 MSE, RMSE, RSS(OLS에서) 등의 손실함수를 최소화해야한다. 그 최소화하는 과정에서 직교방정식, 경사하강법 등이 사용된다. 손실함수를 최소화하는 과정에서 최적의 해를 구하고 경제적인 계산이 가능하도록 방법을 선택해야한다.
