[머신러닝/딥러닝] 1. Linear Models for Regression

Linear Models for Regression

이번 시간에는 첫 시간인 만큼 수치를 예측하는 Regression(회귀) 위한 Linear model 활용법에 대해서 알아보도록 하자. 이번 글에서 다룰 내용은 아래와 같다.

1.Regression & Linear models : Regression과 Linear model에 대한 의미부터 한번 짚어본다.

2. Batch method
 : 전체 데이터을 훈련 데이터로 이용해 모델을 만드는 방법을 Batch method라 한다.
   Batch method 에서 최소자승법을 적용한 OLS(Ordinal Least Square)와 최대 Likelihood를 예측하는 방법에 대해서 알아본다.

3. Sequential method
 : Batch method와 상반되는 개념으로 데이터 실시간으로 쌓이고 있을때, 데이터를 모아뒀다가 학습하는 것이 아니라, 그때그때 학습하면서 모델을 update하는 sequential method에 대해서 알본다. 마찬가지로 재귀적으로 최소자승법을 적용 시키는 RLS(Recursive Least Square)에 대해서도 알아본다.

4. Regularization

 : 모델이 학습데이터에 너무 적중시키면 현실데이터를 만족시키지 못하는 경우가 생기는데(overfitting) 이런 문제를 해결하기 위한 정규화(Regularization)방법을 소개하고, 정규화된 회귀모델인 Ridge regression, Sparse regression(LASSO)에 대해서 알아본다.

Regression & Linear models

1. Linear model 이란?

우린 통상 그래프가 직선이면 Linear 모델이라 한다. 그러나 수학적으로 Linear 모델의 정의는 다르다.

x가 입력되면 y가 출력되는 system이 있다고 가정하자.즉, x1이 입력되면 y1, x2가 입력되면 y2가 출력된다. 그럼 x1 + x2를 입력하면 어떤 변수가 나올까? 

일반적인 system은 이 값을 예측할 수가 없다. 하지만 이 system이 linear 하다면 출력은 y1 + y2가 출력된다. 이것이 바로 수학적 linear의 정의이다. 즉, linear combination을 입력으로 넣으면 출력도 linear combination으로 출력되는 것이 linear model의 가장 큰 특징이다.

그럼 사실 f(x) = 2x + 1 과 같은 직선식도 수학적으로는 linear가 아니다.
※ f(1) = 3, f(2) = 5, f(1+2) = 7이기 때문에 엄밀히 말하면 위 식은 linear가 아니다.
진정한 linear system은 절편이 없는, 즉 원점을 지나는 직선 모델만 수학적 linear system이라 할 수 있다.

하지만 f(x) = 2x + 1과 같은 경우는 수학적 linear는 아니지만 linear처럼 풀기 쉬워서 non-linear로 구분하는 것이 아니라 affine linear system이라 한다.

2. Regression이란?

입력 X, 출력 y가 있을 때 X에서 y로 가는 길을 f(x)로 mapping하는 것을 Regression이라 한다. 다만 우리는 그 관계를 모르기 때문에 $\hat{f}$(x)를 구해서 $\hat{y}$을 추론(inference)하며, 이런 방법을 Inductive inference(귀납적 추론)라 부른다.

많은 사람들은 통상 Linear regression을 f(x) = wx + b 와 같은 식으로 알고있다. 하지만 정확한 표현은 위 식처럼 Basis function Φ(x)를 통해 x를 변형시킨 다음 weight를 적용한 affair linear model이다. 

※ 우리가 익히 아는 Linear regression의 Basis function은 Φ(x) = x 인 형태다.

  

이렇게 basis function 를 사용하면 비선형함수를 선형화, 즉 Linear technique를 적용할 수 있다. 

예를 들어 f(x) = w0 + w1X + w2X² + w3X³ 는 확실히 비선형식이다. 

그런데 이 식을 f = w0Φ0(x) + w1Φ1(x) + w2Φ(x) + w3Φ(x), Φi(x) = xⁱ 로 변형한다면 이 문제는 Φ에 대한 linear model이 된다. 

위 개념으로 Linear technique를 적용하면 Neural networks도 affair linear model을 다시 입력으로 받는 Φ함수를 활용한 Linear model으로 볼 수 있다. (adaptive 한 basis function을 가지는 linear model)

항상 pair의 정보를 가지고 특정한 방식으로 처리하는 Kernel regression도 마찬가지로  Linear model화 할 수 있다. (자세한 내용은 추후에 다룬다.)    

※ 참고) 사람 / 책에 따라 x, y를 지칭하는 말을 다르게 혼용해서 쓰는데 알아두면 다른 강의를 들을 때도 유용하니 기억하도록 하자.

• X : input, independent variable(독립변수), predictor, regressor, covariate
• y : output, dependent variable(종속변수), response

2-1) Linear Regression

Linear regression은 Linear model의 입력과 출력인 x와 y가 Φ의 affine function일 것이라 가정하는 것이고, Real number의 벡터인 W를 구하는 문제다.

2-2) Polynomial Regression

Polynomial Regression은 Linear model의 basis function이 Φi(x) = xⁱ인 형태다.

i에 따라 점점 고차원의 함수가 되는데, 위 그림처럼 i가 높을수록 Training error는 0에 근접한다. 하지만 실제 데이터 패턴인 ground truth와는 거리가 멀기 때문에 현실적으로 쓸 수가 없다. 이런 경우를 overfitting 됐다고 한다. 그렇기 때문에 Generalization을 통해서 모델을 단순화 시켜 위 그림처럼 2nd order polynomial 모델을 만들어야 한다. 

2nd order polynomial 모델은 어느정도 오차는 있지만 ground truth를 잘 표현한다. 즉, bias는 좀 높아졌지만 variance를 낮춰서 overfitting을 피했다고 할 수 있다. 

※ overfitting 된 모델을 일반화(Generalization)시키기 위한 방법중 하나로 정규화(Regularization)하는 방법에 대해서는 잠시 뒤 자세히 다룬다.

Batch method

Batch method는 모든 데이터를 훈련 데이터로 해서 모델을 만드는 방법이다. Batch method를 활용해 모델을 추정하기 위한 최소자승법(OLS)와 Maximum likelihood 추정법에 대해서 알아보도록 하자.

1. Least Squares Method

위 식은 linear regression을 표현하는 affine function이이고, W와 Φ(X)의 원소는 모두 실수라고 가정한다.
※ W와 Φ(x)의 갯수가 M이 아니라 M+1인 것은 M개의 기울기와 1개의 절편이 있기 떄문
※ 여기서 우리는 basis function을 알고 있다고 가정한다. 참고로 우리가 잘 알고있는 1차 선형식의 basis function Φ(x) = x

Least Squares Method는 단어에서 유추할 수 있듯, 뭔가를 최소화 하는 방법이고, 이 원리를 linear regression에 적용시키면 「오차를 최소화」시키는 위의 식을 목적으로 한다. 그래서 위 식을 목적함수라고도 부른다.

참고로 ||W|| 표기는 norm을 의미하며 각 원소의 제곱근을 의미한다.
||W||2는 2-norm이라 하며 w1, ... wn의 2제곱근이다.
(2-norm은 유클리디언(Euclidean) 거리를 의미하기 때문에 유클리디언-norm이라고도 한다. 

그럼 위 목적함수의 우측항을 norm의 정의에 따라 정리하면 아래와 같다.
(ex. 전치행렬과 행렬을 곱하면 모든 원소간의 곱 행렬이 된다. norm은 제곱근이기 때문에 제곱해주면 square root(√)가 사라짐.)

이제 위 식을 W에 대해 미분 해서 0인 지점(기울기가 0인지점 = 최소지점)을 찾으면 된다. 

위 행렬의 미분을 수행하기 위해 잠깐 선형대수학을 떠올려보자.

위 공식을 이용해서 미분을 수행하면

 - y^Ty 는 상수항으로 사라지고,

 - W^TΦy 와 y^TΦ^TW 는 각각 Φy로,

 - W^TΦΦ^TW 는 2ΦΦ^TW로 미분된다. 

미분값이 0인 지점을 찾기 때문에 양변을 2로 나눠주고 정리하면 아래와 같다.

위 식을 W에 대해 정리하면, 결국 우리가 구하고자 하는 파라미터 행렬 W는 아래와 같이 Φ(design matrix)의 pseudo inverse matrix와 y의 곱으로 구할 수 있다.

※ pseudo inverse matrix
AX = Y라는 식에서 A를 구하기 위해 X의 역행렬이 필요하다. 이 때 X가 역행렬을 가질 수 없을때 역행렬과 유사한 성질을 가질 수 있도록 만든 행렬을 pseudo-inverse matrix라 한다.

2. Maximum Likelihood View of OLS

머신러닝이란 학문을 공부하다 보면 Probability distribution(확률분포)이란 단어와 자주 마주치게 된다. 그만큼 보기보다 머신러닝 알고리즘은 통계학에 기반한 것들이 많고, 자연스럽게 Maximum likelihood estimation(최우추정법)이란 단어도 자주 마주칠 것이다. 물론 앞서 AI, 데이터마이닝 수업에서도 많이 설명했지만, 다시 한번 기초를 다진다는 느낌으로 알아보자.

이번에 알아볼 것은 통계학 관점에서 linear regression의 파라미터를 추정하는 것이다. 결론부터 말하면 앞서 matrix 연산으로 구한 OLS의 결과나, maximum likelihood를 구한 결과나 의미하는 것이 같다. 분석을 시작하기 전에 간단한 통계 리뷰를 해보자자.

• E[X] : expectation, 기대값
  ex. 예를 들어 사건을 '시험'이라고 하자.
  그리고 그 확률은 X = {100점 : 1/8, 70점 : 1/2, 50점 : 1/4, 0점 : 1/4} 라고 하자.
  그럼 E[x] 즉, 시험을 쳤을 때 예상되는 점수는 몇 점 일까?
  이 때 예상 점수는 E[x] = 100x1/8 + 80x1/2 + ... + 0x1/4 = 60점이다.
  즉, E[x]는 확률로 이루어진 weighted sum이라 할 수 있다. (확률이 동일하다면 평균과 같음)

• P(x1) : prior, 사전확률
  ex. 위 예제를 응용하면, x1을 100점이 나올 사건이라 한다면 그 확률은 1/8이다.
  이처럼 사전에 알고 있는 확률을 prior 라 한다.
  또 다른 예제로 어떤 주머니 X = {흰공10개, 빨간공50개} 라면,
  흰공을 꺼낼 사전확률은 1/6이라 할 수 있다.

• P(y | X) : posterior, 사후확률
  x라는 사건이 일어났을 때, y일 조건부 확률(conditional probabilities)을 posterior라 한다.
  만약 P(y=알람 | X=화재) 는 화재가 났을 때 알람이 울릴 확률이다.
  참고로 P(X=화재)는 화재가 일어날 prior다.

• P(X | y) : likelihood, evidence, 가능성
  y라는 결과가 X로 부터 왔을 조건부 확률이다.
  X로부터 y를 '예측(predict)' 한다고 하는 반면 y로부터 X를 '추론(inference)'한다고 한다.
  즉, 대부분의 추론 문제는 likelihood를 찾는 것이다.
  ※ 어떻게 원인, 결과로 두느냐에 따라 posterior과 likelihood는 바뀔 수 있다.
  ex. linear regression은 데이터(X, y)로부터 Φ, w가 결과로 나오기 때문에
  오히려 P(y' | Φ, w) 가 y'을 추론하는 likelihood이다.

여기까지 정리하고, 이제 linear regression문제를 통계학 관점에서 바라보자.

앞서 정의한 linear regression model에 Gaussian분포(정규분포)를 갖는 noise ε가 있다고 가정하자. 그럼 자연스럽게 y의 분포도 Gaussian, regression 모델이 Φ, w를 학습했을 때 y를 잘 적중시킬 확률도 Gaussian분포를 갖는다.

Gaussian분포의 확률밀도 함수는 위와 같은데,

이 식을 예측값 y의 분포로 적용하면 위와 같다.

사실 위 식으로도 likelihood P(y|Φ, w)를 최대로 하는 것은 오차를 최소화 하는 것, 즉 OLS의 원리와 같다는 것을 알아챘지만 끝까지 한번 풀어보자.
※ 확률밀도함수에서 오차가 작아질수록 exponential term이 커진다. 그리고 오차가 0이면 P(y|x) = 1으로 계산된다.

 likelihood P(y| Φ, w)를 최대화하기 위한 목적함수 J를 정의해보자. 

• 통계학에서 likelihood 는 모든 사건 확률의 곱으로 계산 할 수 있다.(maximum 문제)

• 계산의 편의를 위해 로그를 취하면 로그확률의 합과 같다. (minimum 문제로 전환)

• P(y| Φ, w)가 Gaussian 분포를 따름으로 Gaussian 확률밀도 함수를 대입하고 로그를 취한다.

• minimize 할 수 없는 상수항을 소거시키면, squared error 최소화 문제로 전환된다.

결론적으로, likelihood를 최대화 하는 것은 squared error를 최소화 하는 OLS의 목적과 완벽히 같다.

Sequential Methods

샘플이 실시간으로 들어온다고 했을 때 샘플을 모아뒀다가 한번에 학습하는 것이 아니라, 실시간으로 학습하는 것을 Sequential Method라 하며, 실시간으로 모델이 튜닝된다고 해서  On-line Learning이라고도 한다. (추후에 또 나오겠지만 batch size = 1인 경우 on-line learning이라고 한다.)

Sequential method도 OLS와 마찬가지로 MSE(mean of squared Error)를 최소화(LMS, Least Mean Squares) 시키는데, 차이점은 모든 샘플이 준비된 상태가 아니라 실시간으로 샘플 xn이 주어진다는 것이다.

그래서 sequential method에서는 모든 샘플을 대상으로 한 MSE를 알 수 없기 때문에, 샘플이 주어진 순간의 Instantaneous squared error를 최소화 한다. 즉, 샘플이 1개 들어올 때 마다 오차를 파악해서 w를 조금 튜닝하고, 샘플이 많이 들어올 수록 w는 optimal solution으로 수렴하게 된다.

위 식을 보면 새로운 샘플 xn이 들어왔을 때 이미 튜닝된 w로 gradient를 파악하고, gradient의 일부(η)를 이용해 기존의 w를 update 하는 것을 확인할 수 있다. 여기서 update 시킬 gradient의 크기를 결정하는 η를 learning rate라 한다. (0 < η)
※ 이 알고리즘을 Gradient decent 알고리즘이라 한다. 추후에 더 자세히 다루도록 한다.

learning rate 역시 모델의 성능과 학습속도를 결정하는 중요한 하이퍼파라미터다. 
※ learning rate가 너무 작으면 학습속도가 너무 오래걸리거나 local optima에 빠질 수 있고, 너무 크면 optimal solution을 찾지 못 할 수도 있다.

그래서 learning rate η를 0~1사이의 값으로 고정하는 것이 아니라, adaptive하게 조정하는 방법이 많이 알려져 있다.(ex. ADAM, Adagrad, RMSprop 등) 그 중 Recursive least square에 대해서 알아보자. (Gauss, 1950)
※ RLS는 계산량이 많아 다른 최적화 함수를 활용하는 것이 일반적이다. 다만, adaptive learning rate의 기초에 해당하니 원리를 알아두도록 하자.

RLS를 적용하기에 앞서, 먼저 입력된 샘플에 대한 가중치는 낮게, 최근에 들어온 샘플의 가중치를 높게 하기 위한 forgetting factor λ 를 설정하자.

위 목적함수를 보면 λ가 0과 1사이의 값을 갖기 때문에 i=1일때 오차에 대한 가중치가 가장 낮고, i가 n에 가까워질 수록 오차에 대한 가중치를 높게 가져가는 것을 확인할 수 있다.

위 식을 최소화 하기 위해 wn으로 편미분한뒤 Pn과 rn으로 치환하면 아래와 같이 표현할 수 있다.

하지만 우리는 on-line learning을 가정하기 때문에 n개의 샘플을 요구하는 Pn의 역함수를 구할 수 없다. 그래서 현재 샘플 Φn이 입력되기 전까지 학습된 모델 Pn-1을 알고 있다고 가정한다. 

 RLS의 핵심 아이디어는 바로 matrix inversion lemma를 적용해 Pn을 Pn-1로 표현하는 것이다. 이렇게 하면 n번째 모델을 구하기 위해 n-1번째 모델을 호출하는 방식으로, 즉 재귀적(Recursive)으로 n번째 모델을 구할 수 있게 된다.

※ matrix inversion lemma : 셔먼-모리슨-우드버리 공식의 특수한 경우
   (A+BCD)^-1 = A^-1 - A^-1B(C^-1 + DA^-1B)^-1DA^-1

(위 전개식의 3번째 줄이 matrix inversion lemma가 적용된 것인데, 굳이 matrix inversion lemma를 이해하려하진 하진 말자. 복잡한 matrix연산의 inverse matrix를 쉽게 구하는 방법 정도로 이해)

위 식을 w에 대해 풀면 아래와 같이 정리할 수 있다.

위 식에서 Φ는 이미 알고있고, yn은 관측되는 값이고, Pn-1과 wn-1은 이미 이전에 구해놓은 값을 재귀적으로 호출된다. 즉, Pn-1만 잘 기억하고 있으면 이미 지나간 샘플들(x1...xn-1)의 오차합(MSE)를 몰라도 wn을 update할 수 있다.

가만히 살펴보면 앞서 설명한 gradient decent 형태를 매우 닮아있는 것을 알 수 있다. 다만 RLS는 learning rate의 역할을 하는 Gain항이 Pn-1과 forgetting factor λ에 의해 매번 adaptive하게 변경된 다는 것이다. 즉, 데이터가 들어올 때마다 Gain(~learning rate)이 바뀐다. 이 방법(RLS)은 앞서 설명한 gradient decent보다 계산량은 좀 많지만 더욱 빨리 optimal weight로 converge할 수 있는 특징을 가진다.

Regularization

Overfitting(과적합)의 원인으로는 다양한 원인이 있을 수 있는데, 공통적인 이유는 모델의 복잡도가 매우 높다는 것이다. 그 대표적인 예가 위 그림처럼 polynomial regression에서 차수를 높게 가져가는 경우이다. 

또 다른 경우로는 X와 Y를 mapping 하는데, X ∈ {X1, X2, ..., Xk}와 같이 feature가 너무 많은 경우도 있다. 물론 이 경우 상관성이 없는 feature의 weight는 작게 튜닝되고 training set에서는 분명 성능이 좋게 나온다. 하지만 새로운 일반적인 데이터는 잘 예측하지 못하는 overfitting문제가 분명 발생한다. 

※ 실제로 대부분의 초심자는 많은 feature를 학습시킬수록 성능이 좋을 것이라 기대하고 차원의 저주에서 빠져나오지 못한다. a.k.a 多多益善(다다익선)

이런 overfitting을 방지하기 위해서는 학습된 모델이 실제 환경에서 일반적으로 쓰일 수 있도록 Generalization(일반화) 시켜줘야한다. 모델을 일반화 시키기 위해서는 모델의 파라미터 weight가 튜닝될 때 과적합 되지 않도록 규제(regularize)시켜줄 필요가 있다. 이 방법을 바로 Regularization(정규화)라고 한다.

정규화의 컨셉은 loss를 최소화 해야하는 상황에 위와 같이 제약조건을 추가로 주는 것이다. 위 식에 의하면  loss와 함께 모델의 복잡도 R(f)도 함께 최소화해야하는 숙제가 주어진 것이다. 위 식의 λR(f )가 바로 regularization term이고, λ를 어떻게 설정하느냐에 따라 정규화의 강도가 달라짐으로 중요한 하이퍼파라미터라 할 수 있다. (λ가 클수록 모델을 더 간단하게 만들고자 하는 노력을 하는 셈이다.)

출처 : Early Stopping in polynomial regression (The Start up, Michael Larionov, PhD, 2019)

하지만 애석하게도 모델의 복잡도 R(f)를 정의하는 것은 쉬운 것이 아니다. 그나마 가장 쉽게 정의할 수 있는 방법은 위와 같이 모델의 복잡도를 증가 시키면서 학습된 weight의 추세를 보는 것인데, 그 결과를 위 예제에서 확인할 수 있다.

위 예제의 3가지 케이스에서 튜닝된 weight를 보면 polynomial degree가 높아지면 높아질 수록 weight의 절대값도 기하급수적으로 높아지는 것을 확인할 수 있다. 여기서 착안해서 weight들의 norm을 활용해 모델의 복잡도를 규제하고자한 방법들이 위와 같이 여럿 있으며, 가장 대표적인 방법인 ridge regression과 LASSO에 대해서 알아보도록 하자.

1. Ridge Regression

Ridge Regression은 weight의 절대적인 크기를 측정하기 위해 2-norm 제곱승을 모델의 복잡도 함수 R(f)로 사용한다. 이 정의를 통해 앞서 제안한 목적함수는 아래와 같이 변경된다.

그리고 위 목적함수에 CLS를 풀듯 w로 편미분하고 그 값을 0으로 설정하면 w의 최소값을 구할 수 있다. 먼저 위 식을 풀기 쉽게 norm항을 제거하면,

와 같이 정리 될 수 있고, 위 식을 미분하면,

위와 같이 W를 구할 수 있다. 

w의 2-norm에 제약을 주면서 w1, w2를 튜닝하는 것을 그래프에 투영시키면 위와 같다. 만약 정규화 없이 OLS로 튜닝한다면 minimize cost를 찾을 것이다. 하지만 위 그래프의 원 영역에 들어와야한다는 제약조건이 있기 때문에, minimize cost에서 cost를 더 허용할 수 밖에 없다. 적절한 cost를 허용하면서 영역을 확장하다 보면 제약조건영역에 닿게 되는데, 그때의 w1과 w2는 minimum cost를 만족하는 w1, w2보다 확연히 줄어있는 것을 확인할 수 있다. 즉, w1, w2의 크기를 규제한 결과를 얻을 수 있다.

※ w의 2-norm의 제곱승을 규제한다는 것은 w1-w2 plane에서 원의 내부로 표현된다.

※ 만약 λ를 극한으로 크게 준다면(strong regularization) 원이 점점 작아지고, 그 원에 들어가기 위한 w1, w2 추정값은 점점 작아진다. 즉, 오차최소화의 목적을 버리고 모델의 단순화에 올인하게 되고, w1=0, w2=0인 함수, 즉 직선으로 된 함수를 도출하게 된다.

Lasso

앞서 복잡도 함수 R(f)를 w의 2-norm 제곱승으로 정의한 Ridge regression의 원리를 보았다.

이 복잡도 함수를 더 직관적이고 쉽게 하는 방법이 있는데 바로 1-norm을 사용하는 것이다. 

1-norm을 사용한다는 것은 w1과 w2의 절대값을 최소화 한다는 의미며, R(f)를 1-norm으로 했을 때 Lasso regression이라 한다. 아래는 Lasso의 목적함수다. (파라미터 w를 Θ로 표기, basis function Φ(X) = X로 표기한 건 별로 신경쓰지 않아도 된다.)

LASSO를 도식화 하면 Ridge와는 또 다른 양상을 보인다. 마찬가지로 OLS의 결과에 cost를 허용하다보면 적절히 작은 weight를 찾긴 하지만 특정 조건에서는 weight가 0이되는 지점을 만나게 된다. 

(a) LASSO,  (b) Ridge

실제로 위 그래프는 λ의 감소에 따른 regularization path이다.(좌측으로 갈수록 λ가 큼)

우측의 Ridge regression의 경우 λ를 극한으로 크게 줬을 때 weight=0으로 수렴하는데,

좌측의 LASSO의 경우 λ가 충분히 큰 값을 갖는 특정 시점에서 weight=0으로 수렴하면서, feature로써 역할을 하지 못하는 것을 확인할 수 있다.

이렇게 LASSO는 정규화된 회귀(regression) 모델로 활용 가능함과 동시에, 무의미한 feature를 삭제하는 역할 즉, 유의미한 feature를 찾아내는 feature selection 방법으로도 활용할 수 있다.

그럼 이제 다시 본론으로 돌아와서 LASSO의 목적함수를 풀어보자.

이제 이걸 Θ에 대해 편미분 해야하는데 1-norm값을 미분하는 것은 일반적인 방법으로는 불가능하다. 왜냐하면 1-norm을 그래프로 표현하면 위 그림과 같이 사각형을 그린다. 그런데 사각형의 꼭지점에서는 무수히 많은 기울기가 측정되기 때문에 미분 할 수가 없다. 그래서 coordinate descent와 sub-differentials를 적용해 우회해서 풀어보도록 한다.
※ w의 1-norm = w1 + w2 = Constant 를 그리면 위 그림과 같이 w1 + w2합이 일정한 사각형을 그린다.

coordinate descent는 어떤 특정 하나의 coordinate에 대해서 각각 optimizing하는 방법이다. 예를 들어 Θ가 w1, w2로 이루어져있다면, w1을 고정시킨다음 w2를 optimize, w2를 고정시켜놓고 w1을 optimize 하는 문제로 분할하는 방법이다.

먼저 LASSO의 목적함수를 전개하자. 이 때 coordinate descent를 적용하기 위해 아래의 새로운 definition을 적용한다.

• Θ = [Θ1, Θ2, ... ΘD]

• Θ-d = [Θ1, Θ2, ... Θd-1, Θd+1, ... ΘD] : Θd가 빠진 Θ 벡터

• X-d,n = [X1, X2, ... Xd-1, Xd+1, ... XD] : Θd에 대응하는Xd가 빠진 X벡터

coordinate descent는 위 정의에 따라 나머지 파라미터를 상수취급하고 Θd에 대한 식으로 목적함수를 표현한다. 그럼 이 식을 Θd로 편미분해보자.

위 식은 모든 원소가 아닌 Θd로 편미분해 gradient를 구한 결과이다. Θd를 제외한 다른항은 모두 상수라 할 수 있으니 보기 쉽게 3개의 항으로 분리하면 남은 숙제는 3번째 항에 있는 λδ|Θd|를 푸는 것이다. 위에서 언급한대로 δ|Θd|를 정석으로 푸는것은 불가능하니 sub-gradient(=sub-differential)로 나눠서 풀어보자.

|Θd|과 같은 절대값 함수는 위와 같이 그려지고, 3가지 경우로 나눠서 sub-gradient를 구할 수 있다. 위 원리를 LASSO의 목적함수에 대입하면 아래와 같다.
※ x=0일 때 미분하면 -1~1의 값을 가질 수 있다.

그리고 목적함수의 목표는 δJ = 0 으로 만드는 Θ의 추정값을 찾는 것이기 때문에 아래와 같이 정리할 수 있다.

위 식에 의하면 Θ의 추정값이 -λ~λ 사이에서는 0의 값을 가지고,

β 가 -λ보다 작으면 크게, (더 작은 값을 가지지 않게)

β가 λ보다 크면 작게, (더 큰값 을 가지지 않게) 하는 성질을 가졌다.

이렇게 threshold가 범위로 주어지고 범위 밖에서는 수축하는 기법을 soft-thresholidng이라한다.

만약 원점을 지나는 직선이 있을때, threshold를 범위로 준 다음에 그 범위에서 0을 갖게 하고, 나머지 구역에서는 원래 값을 갖게 하면 hard-thresholding이라 한다.

반면, soft-thresholding은
범위보다 작을 때(-) 더 큰값을 갖도록, 즉 (-)방향의 크기가 작게,
범위보다 클 때(+) 더 작은 값을 갖도록, 즉 (+)방향의 크기가 작게 수축시키는 역할을 한다.

즉, 우리가 구할 Θ의 추정값도 λ에 의해 soft-thresholding 된다고 할 수 있다.

위에서 정의한 β를 확인해보면 실제 y값과 예측된y의 차이, 즉 오차항을 포함하고 있다. 이 정의를 해석하면 λ가 클수록 threshold 구역에 오차를 많이 허용하는 것을 알 수 있고, 이 때 Θ는 0으로 추정된다. 이러한 원리 때문에 LASSO는 feature x가 특정 오차를 허용했을 때 x의 파라미터를 소거시킬 수 있어 변수선택법으로도 많이 활용된다.