파이썬 코딩으로 말하는 데이터 분석 - 6. 경사하강법

요즘 데이터분석과 관련하여  텐서플로우와 스파크(ML)등의 머신러닝 솔루션들이 굉장히 유행하고 있습니다. 물론 저것들이 삶을 편안하게 만들어주기도 하지만 대부분의 데이터 분석은 저런 거창한 것 말고 평균,편차 같은 기본적인 개념으로 부터 시작되고 있으며 이러한 개념을 조금씩 변경해가며 더 의미있는 가치를 찾기 위해 빠르게 적용해보는 과정을 거쳐야하는데  그러기 위해서는 

1. 직접 코딩해서 기본적인 데이터분석 유틸리티 함수들을 만들어봐야한다. 

2. SQL문을 잘 다루어야한다. 

3. 엑셀을 잘 다루어야 한다. 

이 3가지는 기본이라고 저는 생각합니다. 소규모 데이터를 가지고 이리저리 반복해서 돌려보는 과정은 매우 중요하며 이런 기본적인 것들도 못하면서 하둡,텐서플로우나 깔짝대고, 데이터 분석 한다 라고 칭할 수는 없겠지요. (이것은 논쟁의 여지가 있습니다.) 그래서 이것들 중 1번에 대하여  "밑바닥부터 시작하는 데이터과학" 등의 좋은책의 내용을 통해서 살펴보는 시간을 갖도록 하겠습니다. 

통계,확률,패턴인식 분야의 내용들의 수식은 외우기가 힘듭니다. 잘은 모르지만 외워도 금방 까먹어지는게 통계관련 공식인거 같습니다. (예를들어 정규분포,확률밀도라는 개념은 매우 쉽게 수긍이 가지만 , 그 식을 외우는건 좀 .;;) 또한 체득하고 나면 당연한거 아냐? 라고 느껴지는 알고리즘(수식) 인데 글로 설명하면 매우 산만해지는 학문인거 같습니다. 하지만  우리들은 소프트웨어 개발자이기 때문에 수많은 기술변화도 따라가야하는 운명에 있는데 쓸때 없이 공식 및 수학을 외우고 있을 수는 없지 않겠습니까? 

제가 초등학교 5학년때 만(10,000) 단위 암산을 했었는데요. 주산,암산을 배워보신분은 아시겠지만 그것이 가능한것은 기억의 매개로 주판을 이용한 것 입니다. 마찬가지로 우리 개발자들은 그 기억의 매개체로 코드를 이용하면 개념과 함정(예를들어 K-Means 를 통해 군집화하면 길이차를 가지고 구분짓는 것이기 때문에 문제가 생기는 도메인 또한 많다) 에 대한 이해가 더 오래갈 것이라 보며 덤으로 가져다 사용도 할 수 있을것입니다.

* 그 상상의 매개체로써의 언어로 "파이썬" 을 선택했으며 정말 좋은 언어라고 생각합니다.

순서 

1. 통계 - 카운팅,min,max,평균,중앙값,산포도,분산,편차,공분산,상관관계 

2. 가설과 추론 (베이지언 - 사후확률,우도) 

3. 군집화 (K-Means)

4. 연관 (Apriori)

5. 함수형으로 데이터 다루기 

6. 경사하강법

7. 회귀분석

8. 은닉 마코프법 (HMM) 

9. k-NN

10. DTW 

 * 참고로 "밑바닥부터 배우는 데이터과학" 서적은 numpy,scikit-learn 등의 외부라이브러리를 활용은 배제되었습니다.

경사하강법 (gradient descent)

말이 어렵지만 쉽게 생각하면 가장 적절한 1차 직선으로 조금씩 변화 (fitting)시켜가는 방식 중 하나이다.

필기식 동영상 강좌인 이찬우님의 동영상을 먼저 보면 좋을 거 같다. 글로 개념을 이해하는건 삽질이니깐;; 

혹시 저 동영상을 보고 이해했다면  아래 나의 설명글은 볼 필요가 없을것이고, 점프하여 바로 파이썬 코드를 살펴보자.

* 1차만 가능하다는 말은 아니고 이 글에서는 쉽게 1차식으로 설명한다. 

 데이터 포인터들을 나타내는 1차 직선의 방정식을 생각해보자. y = mx + b 가 될 텐데..저 무수한 점들 (빅데이터) 를 일반화 하는 직선의 방정식을 어떤식으로 풀어야할까?  m 과 b 의 값을 어떻게 알맞게 맞춰 (피팅) 갈 수 있을까? 최종 피팅되어  1차 방정식을 알게 된다면 이제 다른 데이터에 대한 예측도 가능 할 것이다. 

딥러닝(신경망) 에서 어떻게 초기,결과 데이터를 가지고 중간 파라미터들 (weight) 를 찾아 내는 것과 거의 동일한다.  혹시나 딥러닝을 하실거라면 경사하강법은 매우 중요한 기본기 이다.

(예를들어 어떤 방정식을 얻게 된다면 , 해당 사진이 고양이 인지에 대해  예측도 가능 할 것이다.) 

일단 아무 직선을 저 데이터 뭉치사이에 그려 넣고, 각 데이터포인터와 직선과의 최단거리를 구한다.그 최단거리의 제곱의 합을 비용이라고 부르자. 비용(오차) 이 클 수록 직선은 저 데이터들을 대표하는 직선이 아닐 것이다. 

즉 비용이 최소가 되도록  y = m*x + b 함수에서 m 와 b 의 값을 피팅시켜 나갈 것이다.

여기서 비용 함수는 아래와 같다.

N :  데이터 샘플들 갯수

Yi :  데이터 샘플중 i 번째의 y 값

MXi + B :  1차직선의방정식의 i 에서 y 값 

Error : 비용 (오차) 

위 함수에서의 미지수는 m 과 b 이다. 이 미지수를 조절해서 비용(Error) 값이 최소가 되도록 만들어 나간다.

서술해보면 실제데이터와 직선의 차의 제곱의 합의 평균이다. ㅡ.ㅡ;;  흠흠.  역시 수식이 깔끔하다;;;

아무튼 중요한것은 이 비용함수는 2차식이라는 것이고 , 아래와 같이 나타 낼 수 있게 된다.

초기 weight (여기서는 m 또는 b) 에서 경사를 하강시켜가면서 가장 최소의 값을 찾는 것이다. y축이 오차이기 때문에 y가 가장 낮을 수록 가장 적절한 값이기 때문이다. 

저 2차선은 비용함수인데 가장낮은 w (여기서는 m 또는 b) 는 무엇인가? 그렇다!!!!! 미분을 해서 0 이 나오는 값!! 즉  최소값이다.(고등학교때 배웠지 않은가? 극대,극소~) 

근데 어떻게 찾을까?  해답은 노가다다. 조금씩 변경해가면서 더 작으면 또 조금씩 이동하는것이다. 너무 작게 이동하면 평생 걸릴것이니. 적절히 점프해간다. (이건 과학이 아니라 예술(직감) 이라고들 한다..)

아래 그림에서 왔다리 갔다리 하는 모습을 확인 할 수 있을것이다. 이렇게 한스텝씩 쪼여간다. (물론 좀 더 현명하게 쪼이는 방법도 있긴한데 이 글의 범위를 벗어난다.) 

마지막으로 설명할 부분은 m 과 b 는 각각 따로 편미분을 통해서 최소값을 구하게 된다는 것이다. 당연히 기울기(m) 을 가장 적절하게 바꿔가면서 , 전반적인 높,낮이 (b) 를 바꿔야지 가장 최적의 직선이 될 것 아닌가~

위에 사진에서 W1 은 (m) ,  W2(b) 이며, 초기값 (W1, W2) 에서 변화량(알파) * 방향(도함수값)을 각각 더하고 빼가면서 최적값을 찾는다. 사진에서 알파는 러닝레이트(Learning rate) 로 , 저 값을 조절해서 스텝의 크기가 정해진다. 

단점은 위의 그림처럼 엄한데 가서 최소값을 찾을 수 도 있다는 것이다. 진정한 최소 값은 다른 곳에 있을 수도 있다.

코드로 말해요.

함수하나를 만들어보자. 실수 백터를 입력하면  요소의 제곱의 합을  리턴해 주는 함수이다. (비용함수라고 치자)

def sum_of_squares(v):
    return sum(v_i ** 2 for v_i in v)

위에서 v 는 아래 설명식에서의 t (1~N) 에서의 X 값과 같다) 물론 동일식은 아니다.

미분값을 구해보자.  

f 라는 함수에 대해 x 위치에서의 미분값 즉 기울기를 리턴한다. (위의 식에서의 x가 아니다. 헥깔리지 마시라) h 는 수학에서는 극한으로 가야겠지만 프로그래밍에서는 근사로 충분하기 때문에 적절히 작은수(0.00001 정도?) 를 넣어준다. 

이 미분값의 방향에 따라서 조금씩 스텝을 바꿔서 최소값으로 나아가게 된다.
(여기서 x 는 위의 해설에서 m 과 b 와 같다, 즉 여기서는 x 를 조절해서 최소의 기울기를 찾아나간다) 

def difference_quotient(f, x, h):
    return (f(x + h) - f(x)) / h

여러 변수중 하나의 변화율만 관찰하는 편도함수를 구해보자.  

def partial_difference_quotient(f, v, i, h):
    """ 함수 f의 i번째 편도함수가 v에서 가지는 값 """

    w = [v_j + (h if j == i else 0)      # h를 v의 i번째 변수에만 더해주자.
         for j, v_j in enumerate(v)]      # 즉 i 번째 변수만 변화할 경우 

    return (f(w) - f(v)) / h

i 번째 변수에 대한 편 변화율을 계산한다. 즉 i번째 편도함수는 , i 번째 변수를 제외한 다른 모든 입력변수를 고정시켜서 계산한다. 

def estimate_gradient(f, v, h=0.00001):
    return [partial_difference_quotient(f, v, i, h)
            for i, _ in enumerate(v)]

모든 변수에 대한 편 변화율을 구한다. (여기서 v는 해설 예에서 m,b 이다.) 

Gradient 적용하기 

아래의 sum_of_squares_gradient 는 이미 정의된 도함수이다.  (x^2  ->  2x 로 미분)

# 8.3. 경사 적용하기

def step(v, direction, step_size):
    """ move step_size in the direction from v"""

    return [v_i + step_size * direction_i
            for v_i, direction_i in zip(v, direction)]


def sum_of_squares_gradient(v):
    return [2 * v_i for v_i in v]

#임의의 시작점을 선택 
v = [random.randint(-10,10) for i in range(3)]
tolerance = 0.0000001

while True:
    #print v, sum_of_squares(v)
    gradient = sum_of_squares_gradient(v) # v 에서의 경사기울기(gradient)를 구한다.
    next_v = step(v, gradient, -0.01)     # 그 기울기의 반대방향으로 이동
    if distance(next_v, v) < tolerance:   # 만약 기준내로 이동하였다면 멈춤. 
        break
    v = next_v                            # 그렇지 않다면 다시 이동.

적절한 이동 거리 정하기

너무 많이 이동하면 발산될 위험이 있고, 너무 적게 이동하면 계산시간이 너무 오래 걸린다.

적절한 거리를 미리 정해두고 가장 합리적인 값을 선택한다.

step_sizes = [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]

def safe(f):
    """define a new function that wraps f and return it"""
    def safe_f(*args, **kwargs):
        try:
            return f(*args, **kwargs)
        except:
            return float('inf')         # this means "infinity" in Python
    return safe_f

종합하기

def minimize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):
    """use gradient descent to find theta that minimizes target function"""

    step_sizes = [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]

    theta = theta_0                           # set theta to initial value
    target_fn = safe(target_fn)               # safe version of target_fn
    value = target_fn(theta)                  # value we're minimizing

    while True:
        gradient = gradient_fn(theta)
        next_thetas = [step(theta, gradient, -step_size)
                       for step_size in step_sizes]

        # choose the one that minimizes the error function
        next_theta = min(next_thetas, key=target_fn)
        next_value = target_fn(next_theta)

        # stop if we're "converging"
        if abs(value - next_value) < tolerance:
            return theta
        else:
            theta, value = next_theta, next_value

SGD  (Stochastic gradient descent) 

앞의 minimize_batch 를 이용하면 반복문을 돌 때마다 데이터 전체에 대해 gradient 값을 계산해야 하기 때문에 계산시간이 오래걸린다. 그런데 대부분의 오류 함수는 더 할 수 있는 속성을 갖고 있다. 즉 데이터 전체에 대한 오류값이 각각 데이터 포인트에 대한 오류값의 합과 같다. 이럴 때는 한 번 반복문을 돌 때마다 데이터 포인트 한 개에 대한 gradient 를 계산해야하는 SGD 를 사용할 수 있다.

def in_random_order(data):
    """generator that returns the elements of data in random order"""
    indexes = [i for i, _ in enumerate(data)]  # create a list of indexes
    random.shuffle(indexes)                    # shuffle them
    for i in indexes:                          # return the data in that order
        yield data[i]


def minimize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):

    data = zip(x, y)
    theta = theta_0                             # initial guess
    alpha = alpha_0                             # initial step size
    min_theta, min_value = None, float("inf")   # the minimum so far
    iterations_with_no_improvement = 0

    # if we ever go 100 iterations with no improvement, stop
    while iterations_with_no_improvement < 100:
        value = sum( target_fn(x_i, y_i, theta) for x_i, y_i in data )

        if value < min_value:
            # if we've found a new minimum, remember it
            # and go back to the original step size
            min_theta, min_value = theta, value
            iterations_with_no_improvement = 0
            alpha = alpha_0
        else:
            # otherwise we're not improving, so try shrinking the step size
            iterations_with_no_improvement += 1
            alpha *= 0.9

        # and take a gradient step for each of the data points
        for x_i, y_i in in_random_order(data):
            gradient_i = gradient_fn(x_i, y_i, theta)
            theta = vector_subtract(theta, scalar_multiply(alpha, gradient_i))

    return min_theta

완전한 소스는 아래에 있다.

https://github.com/insightbook/Data-Science-from-Scratch/blob/master/code/ch08_gradient_descent.py

---

레퍼런스 :

밑바닥부터 시작하는 데이터 과학