Machine Learning (Linear Models, Logistic Regression, GD, SGD)

목차

1. 선형 모델 

2. Linear Regression

3. Linear Regression의 generalization

4. Logistic Regression

5. Gradient Decent / Stochastic Gradient Decent  

1. 선형 모델 Linear models

먼저 Linear model이 무엇인지 생각해보자. Linear model은 말 그대로 주어진 데이터들의 linear combination을 통해서 결과를 얻어내고자 하는 것이다. '$x = {x_1, x_2, ..., x_d}$'가 있을 때, '$s = w^Tx  = \sum_{n=1}^{N}w_nx_n$'의 linear combination을 통해서 어떤 signal '$s$'를 얻는다. 

 

이 '$s$'를 어떻게 사용하는지에 따라서 

1. classification: '$y = sign(s)$'

2. regression: '$y = s$'

3. logistic regression: '$y = \theta(s)$' ('$\theta$'는 sigmoid function: e.g., '$\theta(s) = \frac{1}{1+e^{-s}}$')

로 나뉠 수 있다. 

이 모든 경우에 우리의 목적은 주어진 데이터 '$D = \{ (x, y)_i | i = 1, 2, ..., M \}$'에 대해서 최적의 '$\hat{w}$'를 찾는 것이다. 

1. classification: Perceptron Learning Algorithm (PLA)

2. regression: '$w = (X^TX)^{-1}XY $'

3. logistic regression: Maximum Likelihood Estimation 혹은 Cross Entropy error measure를 통해서 구한다. 

먼저 학습의 두 가지 목적이 무엇인지 생각해보자. 

1. '$E_{OUT}(g) \simeq E_{IN}(g)$' 

2. '$E_{IN}(g) \simeq 0 $'

Linear model은 이 중에서 첫 번째 목적을 잘 만족시킨다. 즉 generalization property가 뛰어나다. 

수식을 이용해서 풀어보면, 

$$E_{out}(g) \le E_{in}(g) + \sqrt{\frac{8}{N} ln{\frac{4m_H(2N)}{\delta}}  }$$

이다. 

그런데 linear model의 경우 '$d_{VC} = d+1$'이고, '$m_H(N) \le N^{d+1} + 1$'이 되어서 위의 식은 다음과 같이 써진다. 

$$E_{out}(g) \le E_{in}(g) + \sqrt{\frac{8}{N} ln{\frac{4(2N^{d+1})}{\delta}}  }$$

generalization error에 해당하는 '$ \sqrt{\frac{8}{N} ln{\frac{4(2N^{d+1})}{\delta}}  } $'를 big O notation을 사용해서 써보면 다음과 같이 간략하게 표현된다. 

$$E_{out}(g) = E_{in}(g) + O(\sqrt{\frac{ d }{ N } \ln N })$$

즉 '$\sqrt{d}$'에 비례해서 generalization error가 커지고 (curse of dimensionality), '$\sqrt{\frac{\ln N}{N}}$'에 비례하므로, '$N$'이 커질 수록 '$E_{in}(g) \simeq E_{out}(g)$'가 될 것을 쉽게 예상할 수 있다. 

먼저 classification에 사용되는 PLA를 다시 한번 집고 넘어가자. 

상당히 간단한 알고리즘이고, 데이터가 linearly separable하다면, 항상 데이터를 나누는 solution을 찾을 수 있다. 즉 '$E_{in}(g) = 0$'가 되는 것이다. 문제는 데이터가 linearly separable하지 않은 경우이다. 

위의 그림과 같이 데이터가 나뉘지지 않을 경우엔 PLA는 제대로 동작하지 않는다. 그 결과 역시 매우 불안정하다. 만약 데이터가 나뉘질 수 없을 때 우리가 차선으로 선택할 수 있는 것은 가장 적은 수의 데이터가 잘못 분류되게 하는 분류기를 찾는 것이다. 하지만 이는 combinatorial optimization으로  NP-hard 문제이다. 

* combinatorial optimization: 주어진 데이터의 임의의 수에 대한 combination에 대해 각각 optimization을 해야 하는 경우. 

이를 아주 간단한 변형을 통해서 완화 시킬 수 있는데 이것이 바로 다음에 나오는 pocket  알고리즘이다. 

내부 내용은 PLA와 같다. 하지만 4번째 줄에 내용이 추가되었다. 즉 현재 상태에서 PLA를 통해 '$w$'를 찾는다. 그리고 해당 '$w$'가 전체 데이터에 대해서 얼마나 잘 동작하는지를 검사하고, 만약 이전 상태보다 더 잘 동작 할 때만 '$w$'를 update하는 것이다. 이를 통해서 PLA의 불안정한 동작을 조금이나마 해소할 수 있으나, 4번째 줄을 처리하는데 오랜 시간이 걸린다. ('$O(N)$')

두 알고리즘 (PLA와 pocket 알고리즘)의 동작을 보면 다음과 같다. 

여기서 보면 초반 동작은 비슷하다. (대충 300 iteration까지) 하지만 데이터가 linearly separable하지 않기 때문에 PLA는 성능이 들쭉 날쭉하지만, pocket algorithm은 '$E_{in}$'이 커지면 update하지 않으므로 안정된 성능을 보인다. 여기서 주의할 점은 한 iteration에 걸리는 시간은 pocket algorithm이 더 길다. 

위의 그림은 PLA를 1000번 수행했을 때와, pocket algorithm의 결과를 보여준다. 

2. Linear Regression

먼저 regression이란 단어가 무엇인지 생각해보자. regression은 back의 의미를 갖고 있는 re와 간다의 의미를 갖고 있는 gress가 합쳐진 단어이다. 즉 돌아간다 란 의미로, 주어진 데이터로부터 model로 돌아간다는 뜻을 갖고 있다. 즉 주어진 데이터가 특정 model로 부터 나왔다고 가정하고, 해당 model을 역으로 찾는 것을 뜻한다. 

우리의 가정은 다음과 같다. 

만약 학습 데이터 '$D = \{ (x, y)_i | i = 1, 2, ..., N \}$'가 주어졌다면, '$x_i$'와 '$y_i$'는 다음의 관계를 갖는다고 가정한다. 

$$y_i = f(x_i) + \epsilon$$

여기서 '$\epsilon$'은 특정 분포를 따르는 random variable로 가정을 하고, 이는 '$y = f(x)$' 대신에 '$y \sim p(y|x)$'를 가정한다는 것과 같다. 이를 그림으로 그려보면 다음과 같다. 

앞서 말했든 우리는 선형 모델을 가정하고 있고, 따라서 

$$g(x) = w^Tx$$

이다. 즉 우리의 목적은 주어진 데이터를 제일 잘 설명하는, 혹은 설정한 에러를 가정 최소로 하는, '$w$'를 찾는 것이다. 이 한 문장에서 알 수 있듯이 에러를 정의할 필요가 있다. 

가장 기본적인 Linear regression의 방법인 ordinary least square (OLS)는 다음의 에러 measure를 사용한다. 

$$E_{in}(g) = \frac{1}{N}\sum_{n=1}^{N}( g(x_n) -  y_n )^2$$

$$E_{out}(g) = E[(h(x) - y)^2]$$

물론 '$E_{out}(g)$'은 우리가 직접적으로 구할 수는 없다. 그런데 '$g(x) = w^Tx$'이므로, 

$$E_{in}(w) = \frac{1}{N} \sum_{n=1}^{N} (w^Tx_n - y_n)^2 $$

이고, 이를 matrix notation으로 써보면 

$$E_{in}(w) = \frac{1}{N} || Xw - Y ||^2 $$

이다. 여기서 '$X$'는 'x_n'들이 row 방향으로 밑으로 차곡차곡 싸여져있는 tall matrix이고, Y는 모든 Y가 역시 밑으로 싸여져 있는 column vector이고, '$w$'는 column vector이다. 여기서 주의할 점은 우리는 bias를 포함시킨 식을 위해서 각 '$x_n$'에 '$1$'을 추가하고, '$w \in R^{d+1}$'로 입력 데이터의 dimension 보다 1 큰 차원의 값을 갖는다. 

결국 위와 같이 정의된 에러를 최소로 하는 '$w$'를 찾는 것이 OLS의 목적이다. 

$$E_{in}(w) = \frac{1}{N} || Xw - Y ||^2 $$

를 잘 보면 우리가 찾고싶은 '$w$'에 대해서 미분 가능하고, convex function이므로 바로 답을 찾을 수 있다. 

먼저 다음-의 성질을 이용한다. 

$$ \nabla(x^TAx) = (A+A^T)x  $$

$$ \nabla(Ax) = A^T $$

$$ \nabla(x^TA) = A $$

$$ || A ||^2 = A^TA$$

그러면 다음과 같이 유도될 수 있다. 

$$ \nabla E_{in}(w) = \frac{1}{N} \nabla (w^TX^TXw - w^TX^TY - Y^TXw + Y^TY) $$

$$ = 2X^TXw - 2X^TY  $$

우리의 목적은 '$\nabla E_{in} =0 $'를 찾는 것이므로, 

$$ X^TXw = X^TY$$

를 얻을 수 있고, 만약 '$X^TX$'가 invertable하다면, 

$$ \hat{x} = (X^TX)^{-1}X^TY $$

를 얻을 수 있고, 이것이 OLS의 solution이다. ('$(X^TX)^{-1}X^T$'를 pseudo-inverse라 한다.)

이번엔 Hat matrix (projection matrix)를 사용해서 linear regression을 분석해보자. 

1. 주어진 '$D = \{ (x, y)_i | i = 1, 2, ..., N\}$'에서 '$w = (X^TX)^{-1}X^TY$'를 구했다. 

2. '$D$' 중에서 input에 해당하는 '$X$'를 '$w$'를 이용해서 '$\hat{Y}$'를 구할 수 있다. ('$\hat{y} = Xw$')

3. '$\hat{Y} = X (X^TX)^{-1}X^TY $' 이다. '$X (X^TX)^{-1}X^T$'이 Hat matrix이다. 

4. 이를 살펴보면 '$Y$'를 '$\hat{Y}$'로 넘기는 과정이 '$X$'의 basis로 orthogonal projection 시키는 것임을 알 수 있다. 

 * '$X^T$'를 곱하고, 다시 '$X$'를 곱하면, '$X$'의 성분과 orthogonal 한 부분은 모두 상쇄된다. '$(X^TX)^{-1}$'는 normalization 부분이다. 

이를 그림으로 표현해보면 다음과 같다. 

귀찮아서 강의 slide를 그대로 따왔는데, 보게 되면 어떤 '$y$'에 대해서 '$\hat{y}$'는 '$X$'의 range space로 orthogonal projection 시킨 값임을 알 수 있다. 

 자 이제, 우리가 구한 hat matrix '$H = X(X^TX)^{-1}X^T$'의 성질에 대해서 알아보자. 

1. Idempotent: '$H^2 = H$' : 당연한 성질인 것이 어느 공간으로 projection 시키고 나면, 이미 그 공간에 있기 때문에 또 projection 시키면 당연히 그 공간에 있을 것이다. (이게 정의다.)

2. Symmetric: '$H^T = H$'

3. '$I-H$' 역시 hat matrix이다. 

4. '$trace(H) = trace(X(X^TX)^{-1}X^T) = trace(X^TX(X^TX)^{-1}) = trace(I) = d+1$' 즉 데이터의 dimension+1과 같다. +1이 되는 이유는 bias를 고려하기 위해서 각 input 데이터에 +1을 추가하기 때문이다. 의미를 살펴보면 주어진 '$H$'가 데이터를 '$X$'의 range space로 orthogonal projection을 시키는 것이고, 데이터들이 살고 있는 공간이 '$d+1$'이기 때문에 '$trace(H)$'는 projection 시키는 공간의 dimension이라고 할 수 있을 것이다. 여기서 주의할 점은 '$H \in R^{N \times N}$'이고 '$N$'은 학습 데이터의 수이다. 

3. Linear regression의 Generalization 

 사실 새로운 장으로 빼기엔 내용이 적긴 하지만 그만큼 어렵고, 중요한 내용이여서 이렇게 하였다. 앞서 이진 분류에 대해서는 '$d_{VC}$'를 이용해서 generalization bound를 계산한 적이 있다. 그렇다면 regression에 대해서도 이런 것이 가능할 것인가? 

 이를 위해서 몇 가지 설정을 할 필요가 있다. 

1. 우리가 얻은 데이터는 에러가 섞여 있다. 

$$y = f + \epsilon$$

 - 여기서 '$\epsilon \sim N(0, \sigma^2)$'  이고, '$\sigma^2$'는 인가되는 측정 오차의 예상 분산이다. 

2. 각각 데이터에 인가되는 에러는 독립적이다. 

이제 수학을 좀 해보자. 

먼저 in-sample error에 해당하는 '$E_{in}(w)$'를 '$H$'f를 사용해서 풀어보자. 

$$E_{in}(w) = \frac{1}{N} || Xw - Y ||^2 $$

$$ = \frac{1}{N} || X(X^TX)^{-1}X^TY - Y ||^2 = \frac{1}{N} || HY - Y ||^2 $$

그런데, '$HY = \hat{Y}$'로 '$X$'의 range space로 orthogonal projection 시킨 것이다. 

여기서 앞서한 가정을 살펴보자.

1. 우리는 입력과 출력이 linear한 관계에 있다고 가정하였다. 

2. 우리에게 들어온 출력 데이터는 에러가 들어가 있다. 

3. 즉 '$X$'의 range space에 속하지 않는 '$Y$'의 부분이 바로 에러 '$\epsilon$'이다. 

4. '$Y$'에서 '$R(X)$'에 속하는 부분을 '$f$', 나머지 부분을 '$\epsilon$'이라고 하자. 

5. 그러면'$Hf = f$'  이다. 

이와 같은 성질을 이용하면 '$HY - Y = H(f+\epsilon) - (f+\epsilon) = H\epsilon - \epsilon$' 이다. 

사실 이 부분이 상당히 흥미로운 부분이다. 

$$HY-Y = \hat{Y}-Y = H\epsilon - \epsilon = \hat{\epsilon} - \epsilon$$

즉 출력값은 '$Y$'를 넘기는 것이나, 에러에 해당하는 '$\epsilon$'을 넘기는 것이나 그 차이가 똑같다는 것으로, model이 에러와 signal을 구별하지 못한다는 것을 뜻한다. 

A. 다시 '$E_{in}(w)$'를 써보면

$$E_{in}(w) = \frac{1}{N} || (I-H)\epsilon ||^2 = \frac{1}{N} (\epsilon^T\epsilon + \epsilon^T H^TH\epsilon - 2\epsilon^TH\epsilon) = \frac{1}{N}(\epsilon^T\epsilon - \epsilon^TH\epsilon)$$

이다. 

B. 여기서 '$H$'는 '$X$'와 '$Y$'의 함수로, '$E_{in}$'을 general하게 구하기 위해서는 모든 가능한 학습 데이터 '$D$'에 대해서 평균을 내야 할 것이다. ('$E_D$'는 data로 평균, '$E_{in}$'은 in-sample error)

$$ E_D[E_{in}(w)] = \frac{1}{N} E_D[\epsilon^T\epsilon - \epsilon^TH\epsilon] $$

C. 먼저 '$E_D[\epsilon^T\epsilon]$'은 각 데이터에 인가된 에러가 독립적이므로 

$$ E_D[\epsilon^T\epsilon] = N\sigma^2 $$

이다. 

D. 두 번째 항인 '$E_D[\epsilon^TH\epsilon]$'은 각 '$\epsilon$'에 대한 quadratic form으로 쉽게 생각해서 모든 가능한 combination을 해당 '$H$'의 값을 곱해서 더한 것이라고 보면 된다. 그런데 '$\epsilon$'의 각 항이 독립적이므로, 그리고 평균이 0이므로, 이 값은 결국 '$H$'의 diagonal term과 '$\epsilon_i^2$'를 곱한 것의 합과 같다. 

$$ E_D[\epsilon^TH\epsilon] = trace(H)\sigma^2 = (d+1)\sigma^2$$

E. 그래서 정리해보면 

$$E_D[E_{in}(w)] = \frac{1}{N}(N\sigma^2 - (d+1)\sigma^2) = \sigma^2(1 - \frac{d+1}{N})$$

이 된다. 

*Out-sample Error '$E_{out}(w)$' 

비슷한 방법으로 '$E_{out}(w)$'을 구할 수 있다. 정확히는 아니고, 우리가 몇 가지 setting을 할 필요가 있다. 

1. Test data는 학습 데이터의 입력에 해당하는 '$X$'를 공유한다. 

2. 입력 '$X$'에 대응되는 출력 '$Y' = f(X) + \epsilon '$'는 '$\epsilon ' ~ N(0, \sigma^2)$' 이라는 새로운 노이즈가 인가되어있다. 

3. 이 상황에서 에러를 계산해보자. 

위에서 전개한 것과 거의 동일한 전개가 된다. 

$$\mathbf{E}_{D, \epsilon'}[E_{test}(w)] = \mathbf{E}_{D, \epsilon'}[\frac{1}{N} || Xw - Y' ||^2]$$

여기서 주의할 점은 '$Y$' 대신에 '$Y'$'이 들어갔다는 것이다. 

그래서 아깐 '$HY-Y$' 였던 부분이 '$HY-Y'$'으로 변하고, 다시 '$H\epsilon - \epsilon'$'으로 변하게 된다. 그래서 

$$ \mathbf{E}_{D, \epsilon'}[E_{test}(w)] = \frac{1}{N} \mathbf{E}_{D, \epsilon'}[ || H\epsilon - \epsilon' || ]  $$

으로 변하고, 

$$ = \frac{1}{N} \mathbf{E}_{D, \epsilon'}[ \epsilon^TH^TH\epsilon - \epsilon^TH\epsilon' - \epsilon'^TH\epsilon' + \epsilon'^T\epsilon'  ]  $$

$$ = \frac{1}{N} ((d+1)\sigma^2 + N\sigma^2) ]  $$

를 구할 수 있다. 

비교해보면

$$ \mathbf{E}_D[E_{in}] = \sigma^2(1 - \frac{d+1}{N} ) $$

$$ \mathbf{E}_D[E_{out}] = \sigma^2(1 + \frac{d+1}{N} ) $$

으로 비슷하면서 다른 값이 나온다. 

잘 살펴보면 '$E_{in}$'의 경우 우리가 가정한 measurement noise의 정도인 '$\sigma^2$'보다 약간 더 좋은 결과가 나오고, '$E_{out}$'의 경우는 '$\sigma^2$' 보다 약간 더 안좋은 결과가 나온다. 그리고 '$N$'이 커질 수록 그 정도가 줄어든다. 이렇게 되는 이유는 우리의 데이터가 노이즈인 '$\epsilon$'과 실제 출력 '$f$'를 구별할 수 없기 때문이다. 

이를 big O notation으로 써보면 '$O(\frac{d}{N})$'인데, 앞서 살펴본 linear classifier의 경우 '$O(\sqrt{\frac{d}{N} \ln( \frac{N}{\delta} ) } )$' 이었던 것을 생각해볼 때 '$O(\frac{d}{N})$'은 몬가 일반적인 generalization bound와 관련된 값이라 추측해볼 수도 있겠다. 

위에 그림은 앞서 살펴본 '$E_{in}(w)$'와 '$E_{out}(w)$'를 N에 대한 함수로 그려본 것이다. 데이터가 d+1부터 시작하는 것은 아마도 '$X^TX$'가 full rank가 되어서 invertable하게 하기 위해서인 것 같다. 

각 에러를 다시 한번 써보면,  

$$ E_{in}(w) = \sigma^2(1 - \frac{d+1}{N}) $$

$$ E_{out}(w) = \sigma^2(1 + \frac{d+1}{N}) $$

이고, expected generalization error는 '$O(\frac{2(d+1)}{N})$' 이다.    

4. Logistic Regression 

 우리는 지금까지 Linear regression에 대해서 알아보았다. 즉 주어진 입력과 출력이 있을 때 이 둘 사이를 매핑하는 적절한 선형 함수를 찾는 것이 목적이었다. 그래서 가장 간단한 OLS에 대해서 알아봤고, 이렇게 구한 값에 대한 '$E_{in}$', '$E_{out}$', 그리고 expected generalization error를 어떻게 구하는지에 대해서도 알아봤다. 

 이제 다시 은행원으로 돌아가보자. 어떤 사람이 들어왔을 때 이 사람에게 대출을 해줄지 말지를 정할 때 perceptron을 사용하게 될 경우, 우리는 일종의 기준을 정해서 그 기준을 넘으면 허가, 넘지 못하면 불허를 하는 것과 같다. 일종의 원칙 주의자?!? 모 여튼, 세상에 유도리가 있어야하지 않겠는가? 

 예를 들면 당신이 승진을 해서 더 이상 카운터에 대충 업무를 안봐도 된다고 치자. 그리고 이제는 개인 고객을 상담하고, 자산 운용을 해주는 자리에 까지 올랐다. 당신이 하는 일은 고객이 파산을 할지 안할지를 알려주는 일이라고 하자. 만약 이전의 perceptron을 쓰게되면, 당신이 할 수 있는 말이라곤, "파산입니다." "아닙니다" 밖에 없을 것이다. 

 하지만 만약 어떻게서든 간에 우리가 "당신은 67.93%로 파산을 할 것 같으니 조심하세요."라고 말을 할 수 있다면, 좀 더 있어보이지 않겠는가? 바로 이것을 할 수 있게 해주는 것이 logistic regression이다! 즉 어떤 결과 그 자체를 알려주는 것이 아니라 event에 대한 확률을 알려주는 것이다. 

위의 그림이 그 차이를 알려준다. x축이 가지고 있는 재산이라고 할 때, (b)에 있는 것 처럼 자산의 양에 따라 파산의 확률을 알려줄 수 있는 어떤 함수를 구하는 것이 그 목적이다. 

자 이를 이제 수학적으로 표현해보자. 이해를 돕기 위해 지금까지 봐왔던 linear classification, linear regression과 비교해서 보겠다. 

1. Linear classification

$$ h(x) = sign(w^Tx) $$

2. Linear regression

$$ h(x) = w^Tx $$

3. Logistic regression

$$ h(x) = \theta(w^Tx) $$

'$\theta(s)$'는 0~1 사이 값을 반환하는 sigmoid함수. (값이 작으면 0에 가까운, 크면 1에 가까운 값을 반환한다.)

 여러 종류의 sigmoid 함수가 사용될 수 있겠지만, 가장 대표적으로 사용되는 것은 다음 함수이고, 모양은 위와 같다. 

$$ \theta(s) = \frac{1}{1 + e^{-s}} $$

 이 함수의 재밌는 특성은 

$$ 1 - \theta(s) = \theta(-s)$$

 이다. 뒤에서 학습 알고리즘을 유도하는 과정에서 이 특성은 아주 중요하게 사용될 것이다. 

자 개인적인 생각으로는 logistic regression에서 중요하게 생각해야 할 부분은 바로 확률이다. 더 이상 어떤 결과를 0또는 1로 생각하는 것이 아니라 0~1 사이에 있는 확률로 나타내겠다는 것이다. 

$$p(y|x) = \theta(w^Tx)$$

라는 개념을 잡고 시작하는 것이 좋다. 

윤성로 교수님께서 그려주신 logistic regression의 BIG PICTURE는 다음과 같다. 

얼핏 봐서는 복잡해보이는 그림이지만, 이 그림 하나에 logistic regression의 많은 것이 담겨 있다. 감히 모든 것이라고 말하고 싶지만, 내가 모든 것을 알고 있는 것이 아니여서 그러진 못하겠다. 

 일단 그림의 왼족부터 오른쪽으로 보면 

1. 왼쪽: 우리가 가지고 있는 학습 데이터 (x축이 입력, y축이 binary한 출력) 이 공간에서 일종의 linear regression을 해서 signal '$s = w^Tx$'를 얻는다. 

2. 중간: 이렇게 얻은 signal '$s$'를 sigmoid function을 통해서 0~1 사이 값으로 바꾼다. 이렇게 바뀐 값은 확률이 된다. 

3. 오른쪽: 우리가 현재 가지고 있는 '$w$'를 통해 얻은 '$s$'를 통해 얻은 확률과 '$y_n$', deterministic한 확률(?), 과의 차이를 보여준다. 즉 붉은색으로 나타낸 것이 현재 데이터의 출력이고, 초록색으로 나타낸 것이 sigmoid를 거쳐서 나온 확률이다. 이 값이 비슷하게 만드는 것이 우리의 목적이다. 

다시 정리해보자면, 어떤 입력 '$x$'가 들어왔을 때, 해당 입력에 대한 확률은 '$f(x) =\theta(w^Tx)$'로 주어진다. 주의할 점은 

'$y = +1$'에 대해선 '$p(y|x) = f(x)$'이고, '$y = -1$'에 대해선 '$p(y|x) = 1-f(x)$'가 된다는 것이다. 그런데 앞에서 '$1-\theta(s) = \theta(-s)$'

이므로 이를 다음과 같이 한번에 나타낼 수 있다. 

$$ p(y|x) = \theta(yw^Tx) $$

위의 식을 likelihood라고 보고, 모든 데이터들 간에 independence를 가자어한다면, 전체 데이터에 대한 likelihood는 다음과 같이 표현된다. 

$$ p(Y|X) = \prod_{n = 1}^{N} p(y_n|x_n) = \prod_{n = 1}^{N}\theta(y_nw^Tx_n) $$

이제 위치의 식을 최대로 하는 '$w$'를 찾으면 된다. 

위의 식은 곱의 꼴이므로 우리가 해석(?)하는데 좋지 않아서 우리는 '$-\frac{1}{N} \log( \cdot )$'를 일종의 wrapper 함수로 해서 이를 minimize하는 꼴로 바꿀 것이다. 즉 

$$ -\frac{1}{N}\log p(Y|X) = \frac{1}{N}\sum_{n = 1}^{N} \log \frac{1}{p(y_n|x_n)} = \frac{1}{N}\sum_{n = 1}^{N} \log \frac{1}{\theta(y_nw^Tx_n)}$$

이렇게 표현할 경우 간단하게 Likelihood를 유도할 수 있다. 하지만 위의 식을 indicating function을 통해서 '$y_n$'이 '$+1$'일 때와 '$-1$'일 때로 나눠서 표현해보면 다음과 같다. 

$$ \frac{1}{N} \sum_{n = 1}^{N} \log \frac{1}{\theta(y_nw^Tx_n)} = \frac{1}{N} \sum_{n = 1}^{N}  \{ [y_n=+1]\log \frac{1}{\theta(w^Tx_n)} + [y_n=-1]\frac{1}{1-\theta(x^Tx_n)}  \}$$

위 식에서 주의할 점은 '$\theta(w^Tx_n)$' 안에 '$y_n$'이 없다는 점이다. 위의 식은 앞으로 나올 cross entropy와 같은 모양이다. (정확히는 두 Bernoulli distribution 사이의 KL divergence)

여튼 다시 간단한 모양의 Likelihood를 우리의 error measure로 사용할 수 있다. 

$$ E_{in}(w) = \frac{1}{N} \sum_{n = 1}^{N} \log \frac{1}{p(y_n|x_n)} = \frac{1}{N} \sum_{n = 1}^{N} \log (1+e^{-y_nw^Tx_n}) $$

또한 위의 식으로부터 pointwise error measure를 유추할 수 있다. 

$$ e(\theta(w^Tx_n), y_n) = \log (1 + e^{-y_nw^Tx_n})  $$

즉 개별 점에서 위의 값을 줄이는 것이 목적인데, 재밌는 것은 '$y_nw^Tx_n$'을 키우게 되면, 위의 값이 줄어들게 된다. 참고로 '$y_nw^Tx_n$'을 키우는 것은 PLA에서도 하는 것이다. 결국 PLA나 logistic regression이나 비슷한 목적함수를 가지고 있다. 

Cross entropy based derivation

 

 앞서 우리는 Maximum Likelihood를 통해서 logistic regression을 풀었었다. 이번엔 같은 문제를 cross entropy를 이용해서 풀어보도록 하겠다. 

먼저 cross entropy란 두 개의 pmf 사이의 거리를 의미한다. 만약 두 pmf가 '$Bern(p)$'와 '$Bern(q)$'라면, 이 둘 사이의 cross entropy는 

$$ p\log \frac{1}{q} + (1-p)\log \frac{1}{1-q}$$

로 정의된다. 이 때 '$\log$'는 '$\log_{2}$'를 의미한다. 

그렇다면 '$p(y|x)$'를 indicating function을 이용해서 다시 써보면 다음과 같다. 

$$ p(y|x) = [y = +1]\theta(w^Tx) + [y = -1](1-\theta(w^Tx)) = \theta(w^Tx)^{[y = +1]} + (1-\theta(w^Tx))^{ [y = -1]} $$

 위의 식을 cross entropy 식과 비교해보면 '$[y = +1]$' 부분이 '$p$'에 해당하고, '$\theta(w^Tx)$' 부분이 '$q$'에 해당한다. 즉 실제 학습 데이터의 분포와 우리가 logistic regression을 통해 얻은 확률 분포 사이의 cross entropy가 likelihood와 같은 것이다. 

 

이를 이용해서 joint likelihood를 써보면 다음과 같다. 

$$ \prod_{n=1}^{N} p(y_n|x_n) =  \theta(w^Tx)^{[y = +1]} + (1-\theta(w^Tx))^{[y = -1]}  $$

앞에서 Likelihood를 계산할 때 '$-\log$'를 붙인 것과 같이 이번에도 Negative Log Likelihood (NLL)을 구해보면 다음과 같다. (주의할 점은 '$\frac{1}{N}$'은 이번엔 없다.) 

$$ NLL = \sum_{n=1}^{N} [y_n=+1]\log \theta(w^Tx_n) + [y_n=-1]\log (1-\theta(w^Tx_n)) $$

 위의 식을 cross-entropy error function이라고 한다. 

이 식이 많이 사용되는 이유는 '$w$'에 대해서 convex이기 때문이다. 즉 local minima에 빠질 염려가 없다. 

자 이제 logistic regression을 실제로 어떻게 구현하는지 알아보자. 사실 우리는 이미 다 알고 있다. Likelihood를 최대로 하는 '$w$'를 찾으면 된다. '$NLL$'은 다음과 같고, 

$$ E_{in}(w) = NLL = \frac{1}{N} \sum_{n=1}^{N} \log  (1 + e^{-y_nw^Tx_n})  $$

이를 '$w$'로 미분하면 다음과 같다. 

$$ \nabla_{w} E_{in}(w) = \frac{1}{N} \sum_{n=1}^{N} \frac{-y_nx_n e^{-y_nw^Tx_n}}{1 + e^{-y_nw^Tx_n}} = -\frac{1}{N} \sum_{n=1}^{N} y_nx_n \frac{1}{1+e^{y_nw^Tx_n}} = -\frac{1}{N} \sum_{n=1}^{N} y_nx_n \theta(-y_nw^Tx_n) $$ 

그리고 다음과 같이 gradient decent 방식을 사용하면 '$E_{in}(w)$'를 최소로 하는 '$\hat{w}$'를 구할 수 있다. 

$$ w \leftarrow w - \alpha \nabla_{w} E_{in}(w) $$

부호에 -가 붙은 이유는 '$\nabla_w E_{in}(w)$'는 '$E_{in}(w)$'를 키워주는 방향이기 때문이다. 

5. Gradient Decent / Stochastic Gradient Decent 

 Gradient decent 알고리즘은 간단하다. 어떤 목적 함수가 있을 때 이를 해당 파라미터로 미분해서 maximum을 찾을 땐 더해주고, minimum을 찾을 땐 빼주면 된다. 이게 왜 등장하게 되었는지에 대해서 약간의 수학적 전개를 해보자. 

우리가 만약 '$t$' step에서 weight '$w(t)$'를 update하고 싶다고 하자. 그러면 다음과 같이 쓸 수 있을 것이다. 

$$ w(t+1) \leftarrow w(t) + \eta \hat{\nu}$$

여기서 '$\eta$'는 step size이고, '$\nu$'는 방향에 해당하는 unit vector이다. 

만약 위의 문제와 같이 '$E_{in}(w)$'를 최소로 하는 '$w$'를 찾고 싶다고 하자. 그러면 '$E_{in}(w)$'를 '$w(t)$'에서 1차 Taylor 전개를 할 수 있다. 

$$ E_{in}(w(t)+x) \simeq E_{in}(w(t)) + \nabla E_{in}(w(t))^T x $$

그렇다면 '$w(t+1)$'로 이동시켰을 때 '$E_{in}(w)$'가 줄어들면 될 것이다. 

$$ \Delta E_{in} = E_{in}(w(t+1)) - E_{in}(w(t)) = E_{in}(w(t) + \eta \hat{\nu}) - E_{in}(w(t)) =  \eta \nabla E_{in}(w(t))^T \nu $$

즉 '$E_{in}$'의 변화량은 '$w(t)$'에서 '$E_{in}$'의 gradient이다. 그리고 '$\nu$'가 unit vector 이므로, 

$$ \eta \nabla E_{in}(w(t))^T \nu \ge -||  \nabla E_{in}(w(t)) || $$

이다. 당연한거다. 어떤 vector와 특정 unit vector의 내적은 해당 vector의 크기의 -1 곱한 것 보다는 크다. 그리고 이 값을 가장 줄이는, 그러니까 '$=$'를 만족하는 조건이 '$\nu$'와 '$\nabla E_{in} $' 이 반대 방향에 있는 것이다. 즉 가장 많이 줄이는 (=steepest) 방향은 다음과 같이 주어진다. 

$$ \nu = -\frac{\nabla E_{in}(w)}{|| \nabla E_{in}(w) ||}$$

사실 당연한 소리를 식을 써서 한 것 같다. 물론 이 때 learning rate에 해당하는 '$\eta$'는 매우 중요한 값 중 하나고, 이를 고정시킬 수도 있고 back tracking이라는 방법을 통해서 이 값을 찾을 수도 있다. (자세한 것은 Boyd 교수의 convex optimization 참조) 그리고 이 값을 어떻게 설정하느냐에 따라 다음 두 알고리즘이 있다. 

위의 알고리즘에선 '$\eta$'를 고정시켰다고 해서 Fixed learning-rate라는 말이 붙는다.. 굳이.. 

위 알고리즘은 '$\nabla E_{in}$'을 normalize하지 않는다. 사실 정확히 말하면 normalize한 후에 learning rate '$\eta$'에 다시 '$|| \nabla E_{in}||$'이 들어가서 결국 상쇄되는 것이다. 좀 더 rule of thumb을 쓰기가 쉽다는 장점이 있다..? 

Least mean square (LMS) rule 

 만약 cost function '$E_{in}$'이 mean square error 라면 (에러 제곱의 평균)

$$ w \leftarrow w - \eta \nabla E_{in}(w) = w +  \eta (y - w^Tx) x $$

와 같이 learning rule이 결정된다. 

여기서 '$y - w^Tx$'부분이 error에 해당하고, '$x$'는 해당 input에 해당한다. 

당연한게 

$$ \frac{\partial}{\partial w} (y - w^Tx)^2 = -2(y-w^Tx)x $$ 

이기 때문이다. 

의미를 살펴보면 조금 재밌는데, 어떤 input '$x$'와 output '$y$'가 있을 때, 현재 model에 이 값이 얼마나 잘 fit 되어있는지 (혹은 얼마나 에러가 있는지) 에 대한 term과 그 때의 input의 값을 곱한 것을 '$w$'에 더해주면 에러를 줄이게 된다. 

한국말론 최소자승법이라고 하며, 결국 에러의 제곱의 합 (혹은 평균) 을 우리의 error measure로 하겠다는 것이다. 장점은 제곱이 들어가서 몬가 식이 깔끔해지고, 단점으로는 outlier에 약하다. 

Stochastic gradient decent (SGD)는 이름은 엄청 거창하지만, 사실 내용은 아무 것도 없다 (라고 개인적으론 생각한다. 그냥 online version? 하지만 단정적으로 말하기엔 내가 아는게 너무 없어서 조심스럽긴하다..). 여튼 원래 error measure가 다음과 같이 주어졌을 때, 

$$ E_{in}(w) = \sum_{n = 1}^{N} e(x_n, y_n) $$

한번 update할 때 마다 '$O(N)$'의 연산량이 필요하다. ('$N$' 개의 학습 데이터에 대해서 모두 계산을 해야 할테니..)

그래서 이걸 랜덤으로 골라서 한번에 하나씩 하자는 거다. 

*Epoch와 iteration은 다르다. Epoch는 모든 데이터를 한번씩 다 보는 것을 의미한다고 한다. 즉 원래 gradient decent의 경우 epoch로 표현될 수 있다. 이 단어를 처음 본건 Restricted Boltzmann Machine 학습을 Contrastive Divergence로 할 때였는데, Batch version의 학습이었기 때문에 여기서도 epoch라고 썼던 것 같다. 당시엔 iteration과 같은 뜻인줄 알았는데 아닌 것 같다. 여튼 모든 데이터를 한번에 보는 batch GD는 epoch, online version은 SGD는 iteration을 쓰는 것이 옳은 것 같다. 

이게 왜 동작을 하냐면... '$n$'이 '$\{ 1, 2, ..., N \}$'에서 uniform하게 뽑히기 때문에 expected weight change는 다음과 같다. 

$$ = -\eta \frac{1}{N} \sum_{n = 1}^{N} \Delta e_n(w) $$

그리고 위의 식은 원래 Batch gradient decent와 같다. 

SGD의 동작은 위와 같다. 일반적으로 SGD는 GD보다 iteration의 수는 더 크지만, 한번 iteration에 걸리는 시간이 훨씬 짧기 때문에 전체 시간은 더 적게 걸릴 수 있다. 문젠 '$E_{in}$'이 monotonic하게 줄지 않는다는데 있다. 그래서 종료 조건을 설정하는 것이 어렵다.