SP24) Linear Regression II

자자 파라미터 LR에서 $\theta$를 구할 때는 오타를 최소화하는 방향으로 구한다는 것도 알았음! 그럼 계산을 해줘야 하는데.. 지난 포스트의 솔루션 구하는 식을 한 번 볼까요? $X^\topX$ 이런 항이 있지 않습니까,,, 이게 적당히 feature 수가 적은 데이터셋이면 그냥 바로 계산해버리면 되긴 하지만 real-world 데이터의 크기는 굉장히 크기 때문에, 손진희 교수님이 쓰신 표현을 빌리자면 "prohibitively expensive"라고 하더이다.. 이런 계산은 안하느니만 못한 거죠ㅜㅡㅜ 그래서 일단 파라미터를 무작위로 초기화 시켜두고, 최적의 파라미터를 찾아가도록 하는 최적화 알고리즘을 사용하는데 그 중 하나가 바로 gradient descent, 경사하강법입니다. 이거랑 같이, regularization을 하는데 이 두 개를 복습해보겠움

 

Gradient Descent

말했다시피, 원래 파라미터를 찾으려면 closed-form solution을 이용해 직접 계산하는 게 가능하기야 한데.. 비용이 너무 크니까 이 방법을 쓰는 거구요, 이런 느낌입니다:

1. $\theta$ 초기화
2. 손실함수 $J(\theta)$에 대입해서 값 evaluation => minimum이 맞는지 확인!
3. 아니면 파라미터 업데이트
4. converge/minimum 될 때까지 반복~

어때 쉽지

식은 이렇습니다.

\begin{equation}\label{eq1}
\theta^{(\tau+1)} =  \theta^{(\tau)} - \rho(\tau)\nabla J(\theta)
\tag{1.a}
\end{equation}

 

여기서 "$-$"로 업데이트 해주는 이유는, 목적함수가 convex, 즉 아래로 볼록한 함수라는 가정으로 그렇게 써준 거라고 교수님이 그러시더라구요? concave면 +로 바꿔주면 된대영

\begin{equation}\label{eq2}
\begin{split}
\theta^{(\tau+1)} & =  \theta^{(\tau)} - \rho(\tau)\nabla J(\theta) \\
& = \theta^{(\tau)} + \rho(\tau)\dfrac{1}{n}\sum_{i=1}^n(y_i-\theta^{(\tau)\top}x_i)x_i
\end{split}
\tag{1.b}
\end{equation}

뒤에 붙는 항은 gradient의.. 평균? gradient의 추정이라고 하는군요~.~

이렇게 하면, 원래 파라미터 추정의 복잡도가 $O(np^2)$이었는데 이걸 $O(np)$로 줄일 수 있대요! ㄱㅇㄷ

 

Stochastic gradient descent도 있는데, 이건 이런 식입니다.

\begin{equation}\label{eq3}
\begin{split}
\theta^{(\tau+1)} & =  \theta^{(\tau)} - \rho(\tau)\nabla J(\theta)
& = \theta^{(\tau)} + \rho(\tau)(y_i-\theta^{(\tau)\top}x_i)x_i && \text{where } i \text{ is a random number.}
\end{split}
\tag{1.c}
\end{equation}

gradient의 평균 대신 일종의 "noisy estimate"을 쓰는 거예요. 일반적으로 gradient descent 하면 아래와 같은 2차원 곡선..에서 쉽게 설명하긴 하지만

손진희 교수님 수업자료

그치만 현실은...

Andrew Ng 교수님 수업자료

왕복잡 어질어질

무튼 그렇다,, 

이 알고리즘의 장점은 시간복잡도가 무려 $O(p)$라는 것인데요! 그것은 평균을 내지 않고 random estimate을 사용하기 때문입니다. 그만큼 일반적인 경사하강법에 비해 noise에 취약하다는 단점이 있어요.

 

Regularization

이건 지난번에 다룬 식인데요,

\begin{equation}\label{eq4}
\mathbf{w}^*_{\text{ridge}} = \arg\min_{\mathbf{w}} \sum_{j=1}^N \left( t(\mathbf{x}_j) - \sum_{i=0}^k w_i h_i(\mathbf{x}_j) \right)^2 + \lambda\sum_{i=1}^kw_i^2
\tag{2.a}
\end{equation}

 

뒤에 보면 $\lambda$가 들어간 항이 하나 더 붙죠? 이게 regularizer입니다! 왜 하냐면, 파라미터를 찾는 과정에서 파라미터 값이 너무 클 때 overfitting/underfitting 등이 발생할 수 있는데, 거기에 패널티를 주는 느낌이래요

그나저나 손진희 교수님 수업에서 overfitting 언급 너무 많이 하심ㅋㅋ

여기서 $\lambda$는 하이퍼파라미터라고 해서, 우리가 찾는 파라미터 대신 learning rate처럼 우리가 결정해주어야 하는 '초'매개변수를 의미해요. (비로소 깨닫는 하이퍼파라미터의 의미...)

이건 a.k.a ...라며 교수님이 소개하신 것들임

• L2-regularizer
• Tikhonov regularization
• Weight decay
• Support vector machine (SVM) with hinge loss

어 근데 중요한 거. $\ref{eq4}$에 추가된 항은 $i=1$부터인데 원래 식에는 $i=0$부터 시작하지?! 싶겠지만 그것은 $h_0((\mathbf{x}_j))=1$이라서 (bias) penalize 안 한다고 합니다. 네에 뭐 그런가보오~

 

그럼 weight를 어떻게 구해주냐면,

\begin{equation}\label{eq5}
\mathbf{w}^*_{\text{ridge}}  = \arg\min_{\mathbf{w}} (\mathbf{H}\mathbf{w}-\mathbf{t})^\top(\mathbf{H}\mathbf{w}-\mathbf{t}) + \lambda\mathbf{w}^\top I_{0+k}\mathbf{w}
\tag{2.b}
\end{equation}

아오 이건 또 뭐야 $I_{0+K}$?? 이건 $(k+1)\times(k+1)$ identity 행렬인데 이제 $I_{11}=I_{k+1, k+1}=0$인,, 그렇다고 하네욤

그래서 최종적으로는, 

 

\begin{equation}\label{eq6}
\mathbf{w}^*_{\text{ridge}}  = (\mathbf{H}^\top \mathbf{H}+\lambda I_{0+k})^{-1}\mathbf{H}^\top\mathbf{t}
\tag{2.c}
\end{equation}

우웩..

 

regularizer가 있는 경우와 없는 경우를 비교해 보면,

• $\lambda\rightarrow0$: regularizing 안 된 거나 다름 없음
• $\lambda\rightarrow\infty$ weight가 전부 0..

정말 penalize네요 ㅇㅅㅇ

 

근데 왜 ridge?

우왕 신기

 

이거 말고도, $\lambda|w_i|^2$을 더해주는 LASSO regularizer도 있다고 합니다. 근데 당연히 미분가능하지도 않고 closed-form solution이 없대요~ 이 외에도, 굳이 제곱을 고집하지 않고 지수를 바꿔주면서 regularizer를 다양하게 변형할 수 있나봅니다.

아님 L0-norm regularizer도 있는데 음 이게 왜 NP-hard지? 일단 정의는 [number of] "nonzero elements in a vector"로 하는 거 같은데 이럼 exhaustive search가 필요한 것도 알겠고.. 근데 어떻게 써먹는 건지 이해가 안 가네욤

 

 

일단 LR 드뎌 끝