[데이터마이닝] Linear Regression and Regularization

Feature Selection via Shrinkage(Regularization)

Supervised learning에서는 class label prediction을 해야할 것이다. 이때, $\{a_1, a_2, \dots, a_p\}$와 같이 무수히 많은 attribute가 존재할텐데, 모든 attribute가 반드시 필요한 것은 아닐 것이다. 이러한 경우에 일부 attribute를 없애줘야 할 것이고, 우리는 이 과정을 feature selection이라고 한다. 그리고 어떠한 attribute가 필요하고 어떠한 attribute가 필요 없는지를 찾아내는 방법도 물론 존재한다. 흔히 domain knowledge나 attribute들의 조합 등을 통해서 target variable의 lable을 prediction 하곤 한다.

우리는 learning process를 소수의 feature만을 사용하는 쪽으로 편향시킬 수 있다. 그래서 우리는 이번에 shrinkage라는 것을 통해서 모든 attribute 대신의 소수의 attribute만을 사용하고자 한다. 여기서 핵심 아이디어는 최소로 만들고자하는 objective function을 사용하는 것이다. 이 objective function의 경우 2개의 term이 존재하는데, 하나는 error minimization에 관한 것이고 다른 하나는 0 쪽으로 parameter들을 shrink, 즉 parameter를 제거하는데 사용 될 것이다.

Linear Regression

먼저 linear regression이라는 것은 supervised learning에서 하나의 직선이 data의 흐름을 따라가도록 만드는 것이다. 우리는 다음과 같이 목적에 따라서 직선으로 data를 classification할 수도 있고 regression 할 수도 있다.
직선을 기준으로 서로 반대 방향으로 data를 분류하는 과정이 classification이다. 이는 supervised learning에서 data마다 ground truth label이 함께 존재하기 때문에 가능한 것이다. Regression의 경우에는 data가 어떻게든 분포가 되어 있을 것인데, 이 data의 흐름을 가장 잘 설명해주는 직선을 찾아야 한다. 그렇다면 이러한 직선은 어떻게 그리는 것일까? 가장 쉽게 직선을 그리는 방식은 다음과 같이 직선의 방정식을 이용하는 것이다.

여기서 $a,b$는 parameter, $x,y$는 data를 나타낸다. Data에 가장 적합한 직선을 찾기 위해서 parameter를 찾아야 하는데, 이때 ground truth와 model prediction의 error를 최소화하는 식으로 찾을 것이다. 어느 정도 적절한 직선을 그렸다고 할지라도 error는 존재하게 된다. 그래서 우선은 다음과 같이 error에 관한 term을 추가해주고자 한다.

각각의 $(x,y)$ 쌍에 대해서 위와 같은 prediction을 얻은 것이고, 추가한 error 혹은 noise는 Gaussian을 따르게 된다. 그래서 이를 종합해서 우리는 data에 가장 최적으로 들어맞는 직선을 찾아야 하고 다음과 같이 정리할 수 있다.

여기서 $w_i$가 기존의 $a$이고, $w_0$가 기존의 $b$에 대응된다. 그리고 최적의 직선을 찾아가는 과정에서 error를 최소화하기 위해서 error function을 정의하고 이를 최소화해야 한다. Error는 실제 $y_i$와 우리의 prediction $\hat{y}_i(=f(x))$를 이용해서 error function을 정의할 것이다.

Error function에 사용되는 $w=\{a,b\}$는 parameter들을 모아놓은 것이다. Prediction을 위해서 각 data sample을 function $f$에 대입하고, 그 결과를 실제 ground truth value와 비교하고 이를 모든 data에 대해서 summation 해준 결과를 error로 만들어 낸 것이다. 우리의 최종 목표는 이 error를 최소로 만드는 것이다. 개념적으로 어렵지 않고 직관적으로 data point로부터 직선까지의 거리들을 줄여보자는 것이다.

Ordinary Least Square(OLS)

우리는 error function을 최소화시켜야 한다는 것은 이해가 됐다. 그렇다면 어떻게 최소화를 시키겠다는 것일까? 바로 Ordinary Least Squre(OLS)를 이용할 것이다. 위에서 정의한 error function $E(w)$를 최소로 만들었다면 최소로 만들어주는 optimal parameter $w^\ast$를 얻게 될 것이다. 총 $n$개의 observation이 주어지게 된다면 우리는 $n$개의 $(x_i,y_i)$ 쌍이 존재할 것이다. 각 sample $x_i$에는 attribute가 $p$개 존재할 것이고, 이에 대해서 다음과 같이 prediction $y_i$를 얻을 수 있다.

이를 vector form으로 나타내면 다음과 같다.

다시 이를 모든 $n$개의 observation에 대해서 정리하면 다음과 같다.

이제 우리가 원하는 optimal parameter를 얻기 위해서 ground truth와 model prediction 사이의 error를 최소로 만들어야 한다. $y, X$는 data이기 때문에 known이지만 model parameter $w$는 unknown이다. Unknown parameter를 추정해야 하는 과정에서 optimal parameter $\hat{w}$를 추정해야 하는 것이다.

그리고 여기서 Ordinary Least Square(OLS)가 쉽게 solution을 제공해준다. 이를 위해서 차근차근 설명해보도록 하겠다. 만약 $X$가 invertible하다면 다음과 같이 쉽게 optimal solution을 구할 수 있을 것이다.

그러나 현실에서 $X$는 invertible하지 않을 것이다. 아마도 $X$는 fat matrix이거나 slim matrix라서 underdetermined거나 overdetermined matrix일 것이다. 그렇기 때문에 양변에 $X$의 inverse를 곱해주는 것은 불가능하다. 그 대안으로 우리는 양변에 $X$의 transpose를 취해서 곱해줄 것이다.

이렇게 하는 이유는 $w$에 곱해진 $X^TX$가 square, symmetric matrix가 되어 $(X^TX)^{-1}$가 존재하게 되기 때문이다. 그래서 우리는 여기서 다음과 같이 양변에 $(X^TX)^{-1}$를 곱하면 된다.

이렇게해서 optimal parameter $\hat{w}$를 얻게 되었고, $X$가 invertible하지 않은 상황에서 사용한 이러한 trick을 pseudo-inverse라고 한다.

Ridge Regression and LASSO

OLS를 사용해서 error를 최소로 만들어 optimal solution $w$를 찾았다. Data에 적절한 직선을 찾는 과정을 OLS를 통해서 할 수 있었다. 이제 우리는 기존의 error에다가 penalty term을 더하고자 한다. Penalty term을 제외한 기존의 error term은 error를 최소화시키는 것이 목적이었다.

그렇다면 우리의 model을 편향시킬 수 있을까? Bias를 통해서 우리의 model을 원하는 방향으로 조절하고 싶은 것이다. 그리고 이를 penalty term 혹은 regularizer를 통해서 하고자 하는 것이다. 대표적으로 $L_1$ norm을 사용하는 LASSO와 $L_2$ norm을 사용하는 ridge regression을 비교해보고자 한다.

Ridge Regression

먼저 위의 식을 보면 model parameter의 제곱들이 더해진 것을 볼 수 있다. Ridge regression 방법에서는 우리의 objective function에 weight의 $L_2$ norm을 더하게 된다.

LASSO method

위의 식은 model paramter의 절대값들이 더해진 것을 볼 수 있다. LASSO method에서는 우리의 objective function에 weight의 $L_1$ norm을 더하게 된다.

위의 식들에서 본 것과 같이 기존 error term에 $L_2$ norm과 $L_1$ norm을 더한 이유는 때때로 model이 제대로 fitting하지 못하기 때문이다. 매우 이상적인 경우에서는 모든 것이 완벽해서 이러한 penalty term이 필요 없을 것이다. 하지만 대부분 outlier가 존재하고, data가 존재하지 않거나 충분하지 않을 것이다. 이러한 문제점들 때문에 bias가 model에 필요한 것이다.

LASSO Optimization

LASSO를 자세하게 살펴보고자 한다.

위의 optimization problem은 사실상 다음의 optimization problem과 동일하다.

결국 위에서 추가된 constraint의 Lagrangian multiplier가 $L_1$ norm penalty term인 셈이다. 하고자 하는 바는 여전히 동일하지만, 이렇게 constrained optimization problem으로 형태를 바꾸게 되면 parameter에 특정 범위가 생기게 된다. 이렇게 함으로써 parameter에 제약을 주게 되고, 이렇게 만들어진 parameter space에서 optimal solution $w^\ast$는 정해진 범위 안에 존재하게 될 것이다. 이것이 constrained optimization이고 LASSO는 Lagrangian multiplier를 단지 이용해서 제약 범위를 penalty term으로 만든 것이다.

우리는 결국 $\{w_0, w_1, \dots, w_p\}$라는 coefficient를 찾아야 한다. 만약 어떠한 이유 때문에 이들을 찾기 어렵다면 penalty term을 사용해야 할 것이다. 즉, 만약 해결해야하는 문제가 너무 어렵다면, parameter space 전체를 탐색하지 말고 대신에 특정 범위만을 통해서 solution을 찾으면 된다.

Ridge Regression vs. LASSO

위와 같이 ridge regression에서 squared term은 sphere 혹은 circle을 정의하게 되고, 이는 optimal solution이 존재하는 constraint가 될 것이다. 반면, LASSO의 경우에는 좌측과 같이 diamond를 constraint로 정의하게 된다. 제약 조건이 없다고 생각하면 위에서 optimal solution $\hat{\beta}$가 contour(loss function) 중앙에 존재할 것이고, 만약 중앙에서 멀리 벗어나게 된다면 그만큼 error도 증가하게 될 것이다. 하지만 constraint 때문에 solution이 범위 밖에 존재해서는 안된다. 그래서 처음에는 무작위하게 constraint 안에 solution이 존재하게 된다. Constraint가 없다면 반복적으로 optimal solution을 향해서 parameter가 update 될 것이다. 그러나 constraint의 존재 때문에 계속해서 optimal solution을 찾아가던 도중에 boundary를 마주하게 될 것이다.

LASSO

LASSO의 특징으로는 diamond constraint의 boundary에 solution이 존재하게 되고, 이 중에서도 corner point에서 optimal solution을 찾아주게 된다. Corner point가 아닌 boundary에서 solution을 찾을 수도 있지만, optimization solver는 결국에는 corner point에서 optimal solution을 찾을 수 있도록 만들어 줄 것이다. 그렇게 되면 하나의 값은 반드시 0이 되어, 우리는 많고 많은 0을 얻게 되어 대부분의 0을 더하게 될 것이다. 이것이 의미하는 바는 비록 많은 attribute를 보고 있더라도, 대부분이 불필요해지게 되는 것이다. 그렇게 되면 LASSO를 통해서 대부분의 coefficient가 0이 되어 model prediction에서 대부분의 feature를 사용하지 않아도 되는 것이다. 이러한 과정이 feature selection이 되는 것이다.

Ridge Regression

LASSO랑 다르게 ridge regression은 덜 흥미로울 수 있다. Optimal solution을 찾아가는 과정에서 circle이라는 boundary를 만나게 되고, LASSO와 마찬가지로 boundary와 동시에 contour 위에서 optimal solution이 발견될 것이다. Ridge regression에서는 하나의 parameter를 찾게되면 나머지 parameter도 constraint 때문에 찾을 수가 있다. 이러한 과정에서 model complexity가 상당히 줄어들게 된다. 만약 sample의 부족으로 인하여 data mining algorithm을 돌리는데 제대로 들어맞지 않을 때마다 LASSO를 사용하게 되면 몇몇 attribute를 날려버리고 feature selection이나 dimension reduction 등을 하게 된다. 그러면 model은 훨씬 간단해질 것이고, model complexity는 자연스럽게 줄어들 것이다. $L_2$ norm도 마찬가지로 동일한 circle 위에서 찾기 때문에 자연스럽게 줄어들 것이다.

Feature Selection via Shrinkage

LASSO와 ridge regression은 가장 흔한 regression이라 자주 접할 일이 많을 것이다. LASSO($L_1$)는 많은 weight를 0으로 만드는 경향이 있고, 본질적으로 feature selection을 하게 된다. Ridge regression($L_2$)는 weight를 줄이지만 feature selection에는 치우치지 않는다. Solution이 circle의 boundary에 존재하게 되지만, 이들을 0으로 만들어준다는 보장을 하진 않는다. 그래도 나름 model을 stable하게 만들어준다.

그리고 $L_1$과 $L_2$ penalty들은 logistic regression, neural network, SVM 등과 같이 또 다른 learning method들과 함께 사용될 수 있다. 그리고 이들 모두 variance를 줄여줌으로써 overfitting을 막을 수 있다. Variance라는 것은 complexity와 같은 의미이고, 만약 $L_1$과 $L_2$를 동시에 사용해도 되는지 궁금하다면 그 대답은 yes일 것이다. 이 둘을 함께 사용하는 elastic net이 존재한다. 이외에도 group lasso, fused lasso 등의 많은 변형들이 존재한다.

Dimensionality Reduction

LASSO는 feature selection을 수행하고 이는 제거된 feature에 수직인 하위 차원 sub space에 feature space를 투영하는 것과 같다. Feature selection을 보면 2개의 feature가 존재하지만 LASSO를 사용했을 때 하나의 feature가 불필요해진다면, 모든 것을 해당 axis로 투영시켜야 한다. 어떠한 attribute가 있던지 간에 해당 attribute는 0이 되어 필요 없어지게 된다.

Dimensionality reduction의 경우에는 간단한 feature selection 보다 더 나아가게 된다. Dimensionality reduction은 새로운 dimension을 만드는 것을 허락해준다. Feature selection은 기존의 attribute로부터 어떠한 것을 제거하고 어떠한 것을 남길지가 핵심이었다. 반면, dimensionality reduction은 새로운 axis를 만들어 내어 기존의 attribute를 무시하고 새로운 axis를 통해서 data를 보는 것이다.

Dimensionality reduction은 feature selection보다 더 큰 개념으로, feature selection을 할 수도 있고 새로운 dimension을 만들어낼 수도 있다. 위와 같이 얼굴 image들이 있다고 했을 때, 주어진 image로부터 모든 pixel을 사용해서 얼굴을 설명할 수 있다. Eigenface를 이용해서 얼굴을 나타내면 우측과 같은데, 얼핏 보기에 사람 얼굴 같지만 완벽하지 않다. 이 중 20개의 얼굴만을 이용해서 attribute를 구성할 수가 있고, 이러한 개념은 꽤 이상해보이지만, eigenface가 발전한 이유이기도 하다.
총 20개의 얼굴을 attribute로 이용하여 각각의 feature들을 통해서 하나의 얼굴을 설명하는 구조이다. $\alpha$는 coefficient, coordinate이고, eigenface는 axis, basis인 셈이다. 그래서 각 attribute인 얼굴들과 $\alpha$의 linear combination을 통해서 완전한 얼굴을 설명하고 있는 것이다.

Comments

몇몇 model에서 우리는 $L_1$ regularization과 같이 feature selection을 learning process에 합칠 수가 있다. 그리고 dimensionality reduction은 때때로 더 정확한 model을 만들 수 있지만, 종종 lower comprehensibility를 가지곤 한다. Dimensionality reduction은 새로운 axis를 만들어 내지만, 왜 만드는지는 알 수가 없다. 이러한 문제점이 dimensionality reduction에는 존재하는 것이다.