Lecture 2 : Linear Regression and Gradient Descent (2)

CONTENTS

• Linear Regression with Mean Square Error (MSE)
• Gradient Descent Algorithms
  • ( Batch Gradient Descent / Stochastic Gradient Descent / Mini-batch Gradient Descent)

---

Batch Gradient Descent (BGD)

주어진 Training data에 Q개의 instance가 존재한다고 가정하자.

이때의 MSE(Mean square Error)를 구하면 다음과 같다.

P = E[d*X]  : cross correlation vector

R = E[X*X] : input correlation matrix

 

위의 MSE를 가지고 Gradient Descent 방식을 사용하여 최적의 weight vector W를 구하자.

 

위에 있는 grad(€) 는 모든 Q개의 instance들에 대한 error 정보를 포함하고 있다.

(모든 Q에 대한 MSE를 구한 것이기 때문에)  

 

Iteration 0 : weight vector W에 대한 초기값을 설정해준다. W0

Iteration 1 : 모든 instance들에 대한 MSE의 gradient값을 구해준 뒤 gradient descent로 W vector를 업데이트한다.

Iteration 2 : 다시 모든 instance들에 대한 MSE의 gradient값을 구해준 뒤 W vector를 업데이트한다.

...

...

...           :  MSE가 매우 작거나 0이 될 때까지 iteration을 반복해준다.

이때, input vector인 X와 desired output 값인 y는 supervised learning이기에 미리 주어진 dataset 값이기 때문에

 

P vector와 R matrix는 iteration을 반복해도 변하지 않는 constant 성분들을 갖는다. 이런 식으로 iteration을  반복

 

하다보면 MSE는 점점 감소할 것이다.

 

BGD의 문제점 : 정확한 gradient 값에 대한 정보는 처리하고자하는 모든 dataset이 주어진 경우에만 계산할 수 있다.

 

즉, 모든 input 값과 그에 대응되는 output값이 사전에 미리 정해진 경우에만 P 벡터와 R 행렬을 정확히 구하고,

 

gradient를 구해나갈 수 있다.

1. dataset이 미리 다 정해지지않고, 순차적으로 입력되는 경우, P와 R을 정확히 계산하는 것이 불가능하다.

 

2. input의 feature vector의 차원이 크다면, R과 P를 구하는데 computational burden이 생긴다. 

 

 

Stochastic Gradient Descent(SGD)

Dataset이 한번에 모두 주어지는 것이 아닌, stream 형태로 하나씩 입력되는 경우

 

To find a correct approximation, 즉 dataset 전체의 error에 대한 값들을 구하는 것이아닌, 그것들의 적절한

 

근사값을 찾는 과정을 위해서는, 적절한 시간동안의 interval과 평균을 내는 과정이 필요하다.

 

Then, How long should we examine the stream to get reliable estimations of R and P ?

(몇개의 데이터를 사용하면 R과 P의 근사값을 찾아낼 수 있을 것인가?)

 

iteration횟수 k 가 점점 커질수록, weight vector W의 평균은 우리가 찾고자하는 optimal weight

 

vector solution으로 근접해간다.

따라서 이를 사용하면 gradient를 계산하는 과정은 아래와 같은 방식으로 바뀌게 된다.

엡실론 = k번째 instance의 square error ( 실제값 - 예상값 )

 

=> k번째 하나의 instance에 대한 square error의 graident를 구한다. 

 

이렇게 구한 gradient를 사용하여 weight vector를 업데이트해준다.

 

k번째 instance의 에러에 대한 gradient값들로부터 이의 기대값을 구하면 전체 dataset에 대한 gradient로

 

수렴할 것이다.

Q개의 instance로 이루어진 dataset이 있다고 가정하자.

Iteration 0 : weight vector에 대한 초깃값 W0 을 설정해준다.

 

Iterateion 1 : 첫번째 instance X1에 대한 square error €1을 구하고 이의 gradient를 구해준다.

                  구해준 gradient를 사용하여 weight vector를 업데이트 해준다 W0 -> W1

Iteration 2: 두번째 instance X2에 대한 square error  €2을 구하고 이의 gradient를 구해준다.

                  구해준 gradient를 사용하여 weight vector를 업데이트 해준다 W1 -> W2

...

...

Iteration Q : 마지막 Q 번째 instance에 대한 square error를 구하고, gradient를 구해 W를 갱신. 

 

Q까지 반복을 끝냈다면, 원하는 수준의 error를 얻을 때 까지 Iteration 1 ~ Q를 반복해준다.

 

BGD vs SGD

BGD는 전체 dataset에 대한 정보를 이용하여 계산을 진행한다. 즉, global graient information을 사용하여 최적의

 

weight vector를 구해가기 때문에 computation effort is heavy.

 

SGD는 하나의 instance에 대한 정보만으로 계산을 진행한다. 즉, local gradient information을 사용하여 최적의 

 

weight vector를 구해가기 때문에 compuation effort는 적지만, 일반적으로 더 많은 iteration을 요구한다.

 

 

Mini-Batch Gradient Descent

BGD와 SGD의 적절한 타협점 => mini batch gradient descent이다.

 

사이즈 B의 미니 배치를 만들어서 이 배치들에 대한 gradient 정보를 사용하여 계산을 진행한다.

B=1이라면 개별 instance들에 대한 gradient만을 사용하는 SGD 방식이고, B = Q(instance 수)라면 모든

 

dataset에 대한 gradient를 사용하는 BGD 방식이다.

 

Iteration 0 : 초기 weight vector W0를 설정하고, 적절한 batch size B를 지정한다. (1보단 크고 Q보단 작게)

 

Iteration 1: B개의 Instance들의 square error값에 대한 gradient를 구하고 이들의 평균을 구한다.

               이 평균을 가지고 weight vector를 업데이트해준다 (W0 -> W1)

Iteration 2: 다음 B개의 Instance들의 square error의 gradient를 구하고 이들의 평균을 구한다.

               이 평균을 가지고 weight vector를 업데이트 해준다.

...

...

Repeat Iteration