최적화 문제 - 경사도 하강 (Gradient Descent) 알고리즘 & 샘플 코드 및 관련 확장

기계 학습 (machine learning) 의 회귀 분석 기본 적 인 사 고 는 훈련 집의 특징 (x) 을 수집 하여 특정한 함수 로 훈련 집 목표 치 (y) 를 적합 하 게 하 는 것 이다. 적합 한 방식 으로 샘플 (x) 의 목표 치 를 예측 / 평가 하고 자 한다.회귀 분석 이 더욱 엄밀 한 데이터 정의 [2]:

알 수 없 는 / 구 해 대기 변수 (벡터) 를 지정 합 니 다.
β

서로 독립 된 변수 (벡터) 기반
X

대응 변수 y 와 알 수 없 는 변수 \ 베타 와 독립 변수 x 의 함수 관 계 를 찾 고 싶 습 니 다.
Y≈f(X,β)

구체 적 인 응용 장면, 예 를 들 어 광고 시스템 의 온라인 트 래 픽 예측 (온라인 트 래 픽 분 배 를 통 해 계약 식 보 유량 표현 확보) 은 트 래 픽 예측 을 통 해 광고 시스템 수익 을 최적화 시 킬 수 있다. 대부분의 회귀 분석 에서 알 수 없 는 변수의 구 해 는 대부분 목표 함수 최적화 로 이 루어 졌 다.
min∑i=0n(yi−f(xi,β))
상기 수학 표현 식 에서 x i 는 제 i 개 견본 의 특징 값 (벡터) 을 나타 내 고 y i 는 대응 하 는 목표 값 을 나타 내 며 f 는 함수 (이 부분 은 일반적으로 선험 지식 에서 얻 을 수 있 으 며, 예 를 들 어 다항식) 를 나타 낸다. 만약 견본 공간 에서 모든 점 이 상기 수학 등식 을 최소 화 할 수 있다 면 (어떻게 정의 하여 최소 화 합 니까? 일반적으로 엔지니어 가 밸브 값 을 설정 합 니 다)공정 상 우 리 는 함수 f 와 \ beta 가 견본 공간 과 목표치 의 관 계 를 잘 묘사 했다 고 생각 합 니 다. 구 해 된 목표 함수 가 미 지 의 견본 을 잘 묘사 할 수 있 는 지 에 대해 본 고의 토론 범위 에 있 지 않 습 니 다. 관심 이 있 는 독 자 는 회귀 분석 에서 의 과 의합 문제 (overfitting) 를 검색 할 수 있 습 니 다. 본 블 로 그 는 경사 하강 (gradient descent) 을 통 해 어떻게 하 는 지 에 중심 을 두 고 토론 할 것 입 니 다.알고리즘 은 회귀 분석의 최적화 문제 와 관련 확장 알고리즘 을 해결 합 니 다. 회귀 분석 에 관 한 토론 은 본 편의 토론 을 넘 어 섰 습 니 다. 여기 서 간단하게 건 너 뛰 고 관심 이 있 는 독자 들 은 볼 수 있 습 니 다 [2].
이론 부분
우선 경사도 가 떨 어 지 는 기본 사상 을 살 펴 보 자. 여기 서 우 리 는 목표 함 수 를 다시 인용 하 자.
F(β)=min(∑i=0n(yi−f(xi,β)))
그 중에서 \ beta 는 알 수 없 는 변수 입 니 다. 우 리 는 F (돌출 함수 - convex function) 가 지정 한 도 메 인 에서 유도 할 수 있다 고 가정 합 니 다. 유도 할 수 없 는 함수 에 대한 최적화 해법 은 (차 계단 subgradient method) 을 볼 수 있 습 니 다. 만약 에 우리 가 \ beta 를 F (x) 1 단계 도체 의 방향 으로 변화 시 키 면 우 리 는 확보 할 수 있 습 니 다.
F(β(k))≤F(β(k−1))
이 를 위해 알 수 없 는 변 수 를 초기 화 할 수 있 습 니 다. \ beta 0. 알 수 없 는 변 수 를 업데이트 / 탐색 할 때마다 \ beta 를 따라 갑 니 다.
∂F∂β
1 단계 도체 의 마이너스 방향 이 일정한 걸음 길 이 를 바 꿉 니 다. (여기 서 우 리 는 r 를 상수 로 하 는 상황 을 먼저 토론 합 니 다. 만약 r 가 충분 하 다 면) 코드 실현 에서 우 리 는 목표 함수 의 1 단계 도 수 를 미리 계산 해 야 합 니 다.
β(k)=β(k−1)−r∗∂F∂βk−1
샘플 코드 부분

# -*- encoding: utf-8 -*-
import re
import sys
import numpy as np
import copy
import time

def timeConsumption(func):
    def func_wrapper(x):
        start_time = time.time()
        func(x)
        end_time = time.time()
        print "[Function-Time-Consumption] ", end_time - start_time
    return func_wrapper

def initialize(length=300):
    """
    """
    X = []
    Y = []
    mu, sigma = 0, 0.1
    V = 100
    # here we assume x is two-dimesion matrix 
    for i in np.random.random(length):
        a = i * V
        for j in np.random.random(length): 
            b = j * V
            X.append([a**2, b**2, a, b, 1, 1])

    # white noise
    noise = np.random.normal(mu, sigma, size=length * length)

    # a * x**2 + b * x + c
    function = lambda x: np.dot([3.0, -1.5, 3.5, -2, 4, 1.0], x)
    Y = [function(X[i]) + noise[i] for i in range(length * length)] 
    return X, Y

class GradientDescent(object):
    """
    """

    def __init__(self, X, Y, eplison=0.000001, gama=0.01, iter_num=10000):
        """
        """
        _d = X.shape[-1]

        # parameter initailization
        self.a = np.random.normal(0, 1, size=_d)

        self.X = X
        self.Y = Y
        self.eplison = eplison
        self.gama = (1.0 / max(Y)) * 1.0 / len(X)
        self.iter_num = iter_num

    def function(self, a, x):
        """
        Do we have prior knowledge about the function?
            - quadratic ?
            - exponential ?
            - linear ?
        """
        return np.dot(a, x)

    @timeConsumption
    def run(self):
        """
        """
        derative = []
        for i in range(len(self.a)):
            derative.append(np.mean([x[i] for x in self.X]))

        local_y = [self.function(self.a, x) for x in self.X]
        diff = np.mean(np.subtract(local_y, self.Y)) 
        while self.iter_num > 0:
            local_a = copy.copy(self.a)
            for i in range(len(local_a)):
                local_a[i] -= self.gama * derative[i] * diff
            local_y = [self.function(local_a, x) for x in self.X]
            diff = np.mean(np.subtract(local_y, self.Y))
            print diff
            self.a = local_a
            self.iter_num -= 1
            if abs(diff) < self.eplison: break
        print self.a

def main():
    """
    """
    X, Y = initialize()
    # time-consumption for length of 300 is 298.651947021, dependent on initialize value
    # instance = GradientDescent(np.array(X), np.array(Y))
    # instance.run()

    # time-consumption for length of 300 is 290.654798031
    instance = StochasticGradientDescent(np.array(X), np.array(Y))
    instance.run()

    # time-consumption for length of 300 is 287.527049065, dependent on initialize value
    # instance = MiniBatchGradientDescent(np.array(X), np.array(Y))
    # instance.run()


if __name__ == "__main__":
    reload(sys)
    sys.setdefaultencoding("utf-8")

    main()

경사도 하강 확장 부분
구체 적 인 프로젝트 가 실 현 될 때 훈련 데이터 가 너무 커서 메모리 에 전부 불 러 올 수 없 거나 훈련 량 이 많아 훈련 이 느 릴 수 있 습 니 다 (변수 업데이트 때마다 전체 데 이 터 를 한 번 씩 필요 로 합 니 다). 이때 우 리 는 경사도 가 떨 어 지 는 집중 변형 을 사용 할 수 있 습 니 다 [2]: - 대량 경사도 하락 (Batch Gradient Descent) - 랜 덤 경사도 하락 (Stochastic Gradient Descent)- 소량 경사도 하강 (Mini - Patch Gradient Descent)
상기 알고리즘 의 기본 사상 은 사다리 가 떨 어 지 는 것 과 비슷 하 다. 변 수 를 업데이트 할 때 모든 훈련 데이터 의 양 이 다 르 고 대량의 사다리 가 떨 어 지면 매번 에 의존 하 는 훈련 집합의 양 을 미리 설정 하고 무 작위 사다리 가 떨 어 지면 모든 훈련 데이터 가 한 번 씩 변 수 를 업데이트 한다.

class StochasticGradientDescent(GradientDescent):

    def __init__(self, X, Y, eplison=0.000001, gama=0.01, iter_num=300):
        super(StochasticGradientDescent, self).__init__(X, Y, eplison, gama, iter_num)

    @timeConsumption
    def run(self):
        derative = []
        for i in range(len(self.a)):
            derative.append(np.mean([x[i] for x in self.X]))

        LENGTH = len(self.X)
        i = np.random.randint(0, LENGTH, 1)
        local_y = self.function(self.a, self.X[i].reshape(-1))
        diff = local_y - self.Y[i]

        # https://en.wikipedia.org/wiki/Stochastic_gradient_descent
        learning_rate = self.gama
        den = self.iter_num
        while self.iter_num > 0:
            local_a = copy.copy(self.a)
            for i in range(len(local_a)):
                local_a[i] -= learning_rate * derative[i] * diff
            i = np.random.randint(0, LENGTH, 1)
            local_y = self.function(local_a, self.X[i].reshape(-1))
            diff = local_y - self.Y[i]
            self.a = local_a
            self.iter_num -= 1
            learning_rate = self.gama * self.iter_num / den


            _temp = [self.function(local_a, x) for x in self.X]
            _diff = np.mean(np.subtract(_temp, self.Y))
            print _diff
            if abs(_diff) < self.eplison: break

        # make sure result converge
        while abs(_diff) > self.eplison:
            local_a = copy.copy(self.a)
            for i in range(len(local_a)):
                local_a[i] -= self.gama * derative[i] * _diff
            local_y = [self.function(local_a, x) for x in self.X]
            _diff = np.mean(np.subtract(local_y, self.Y))
            print _diff
            self.a = local_a
        print self.a

class MiniBatchGradientDescent(GradientDescent):

    def __init__(self, X, Y, eplison=0.000001, gama=0.01, iter_num=300, batch=100):
        super(MiniBatchGradientDescent, self).__init__(X, Y, eplison, gama, iter_num)
        self.batch = int(0.1 * self.X.shape[0])

    @timeConsumption
    def run(self):
        derative = []
        for i in range(len(self.a)):
            derative.append(np.mean([x[i] for x in self.X]))

        LENGTH = len(self.X)
        local_a = copy.copy(self.a)
        learning_rate = self.gama
        den = self.iter_num
        _diff = 0
        while self.iter_num > 0:
            index = np.random.randint(0, LENGTH, self.batch)
            data = self.X[index]
            local_y = [self.function(local_a, x) for x in data]
            diff = np.mean(np.subtract(local_y, self.Y[index]))
            for i in range(len(local_a)):
                local_a[i] -= learning_rate * derative[i] * diff
            self.a = local_a
            self.iter_num -= 1
            learning_rate = self.gama * self.iter_num / den

            _temp = [self.function(local_a, x) for x in self.X]
            _diff = np.mean(np.subtract(_temp, self.Y))
            print _diff
            if abs(_diff) < self.eplison: break

        # without follow code, diff do not converge to minimize
        # make sure result converge
        while abs(_diff) > self.eplison:
            local_a = copy.copy(self.a)
            for i in range(len(local_a)):
                local_a[i] -= self.gama * derative[i] * _diff
            local_y = [self.function(local_a, x) for x in self.X]
            _diff = np.mean(np.subtract(local_y, self.Y))
            print _diff
            self.a = local_a
        print self.a