경사하강법 (Steepest descent method, 最急降下法)

"경사하강법"이란 함수의 기울기로 최소값을 찾아내는 알고리즘으로,

뉴럴네트워크를 공부하면서 나오는 기초 알고리즘 중의 하나이다.

값을 찾기위한 경사하강법의 수식은 아래와 같다.

 

여기서

(nabla) 는 벡터공간에 대한 스칼라 장의 구배를 의미한다.

 

간편한 프로그래밍의 예를 들기위해 사용을 할 것은 2차함수이므로,

x항에 대한 편미분 항 이외는 무시 할 수 있다.

 

따라서 아래와 같이 간략하게 나타낼 수 있다.

 

여기서

는 학습계수로써,

값을 크게 할 수록 반복계산 횟수는 짧아지지만,

결과값에 최대한 근접하기 위해서 결과가 진동을 하게 된다.

 

이와는 반대로,

값을 작게 하면 결과는 좀 더 정확하게 나오지만,

값을 찾기까지의 시간이 더 오래걸린다.

 

따라서, 자기가 해결하고 싶은 상황에 따라서

값을 구하는 것을 많이 궁리 할 필요가 있다.

 

만약에 아래와 같은 2차 방정식이 있다고 가정하자.

 

위의 수식을 그래프로 표현하면 아래와 같이 나온다.

 

물론 그냥 눈으로 봐도 최소값이 무엇인 지는 쉽게 알 수 있는 문제이지만,

간단한 예를 들기 위해서 수식을 정했다.

 

이 식에 경사하강법을 적용하기 위해서, 수식에 대해서 편미분을 취해 주면 아래와 같이 된다.

 

따라서, 위의 값을 경사하강법 식에 적용하면 아래와 같은 수식으로 나타낼 수 있다.

 

이 식을 사용해서 평가함수가 최소가 되는 x의 값을 구하는 프로그램은 아래와 같다.

(소스는 c 언어로 작성했다.)

//
//  main.c
//  SteepestDescentMethod
//
//  Created by 초인로크 on 6/17/16.
//  Copyright © 2016 초인로크. All rights reserved.
//
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
double random_number(){
    
    return ((double)(rand()%RAND_MAX)/(double)RAND_MAX);
   
}
 
double function(double x){
    
    return (x + 4)*(x + 4);
    
}
 
int main(int argc, const char * argv[]) {
    
    srand((unsigned int)time(NULL));
    
    int i;
    double alpha = 0.1, x = 0.0;
    
    x = 50 - random_number() * 50;
    
    for(i=0;i<100;i++){
        
        x += -2 * alpha * (x + 4);
        printf("%d: The x:%lf, Results:%lf\n",i,x,function(x));
        
    }
    
    return 0;
    
}

입력값 x는 랜덤하게 결정해 주었으며,

값은 0.1을 이용하였다.

위의 소스를 실행하면 아래와 같은 결과를 확인 할 수 있다.

0: The x:8.040129, Results:144.964707
1: The x:5.632103, Results:92.777413
2: The x:3.705683, Results:59.377544
3: The x:2.164546, Results:38.001628
4: The x:0.931637, Results:24.321042
5: The x:-0.054691, Results:15.565467
6: The x:-0.843752, Results:9.961899
7: The x:-1.475002, Results:6.375615
8: The x:-1.980002, Results:4.080394
9: The x:-2.384001, Results:2.611452
10: The x:-2.707201, Results:1.671329
11: The x:-2.965761, Results:1.069651
12: The x:-3.172609, Results:0.684576
13: The x:-3.338087, Results:0.438129
14: The x:-3.470470, Results:0.280403
15: The x:-3.576376, Results:0.179458
16: The x:-3.661100, Results:0.114853
17: The x:-3.728880, Results:0.073506
18: The x:-3.783104, Results:0.047044
19: The x:-3.826483, Results:0.030108
20: The x:-3.861187, Results:0.019269
21: The x:-3.888949, Results:0.012332
22: The x:-3.911160, Results:0.007893
23: The x:-3.928928, Results:0.005051
24: The x:-3.943142, Results:0.003233
25: The x:-3.954514, Results:0.002069
26: The x:-3.963611, Results:0.001324
27: The x:-3.970889, Results:0.000847
28: The x:-3.976711, Results:0.000542
29: The x:-3.981369, Results:0.000347
30: The x:-3.985095, Results:0.000222
31: The x:-3.988076, Results:0.000142
32: The x:-3.990461, Results:0.000091
33: The x:-3.992369, Results:0.000058
34: The x:-3.993895, Results:0.000037
35: The x:-3.995116, Results:0.000024
36: The x:-3.996093, Results:0.000015
37: The x:-3.996874, Results:0.000010
38: The x:-3.997499, Results:0.000006
39: The x:-3.997999, Results:0.000004
40: The x:-3.998400, Results:0.000003
41: The x:-3.998720, Results:0.000002
42: The x:-3.998976, Results:0.000001
43: The x:-3.999181, Results:0.000001
44: The x:-3.999344, Results:0.000000
45: The x:-3.999476, Results:0.000000
46: The x:-3.999580, Results:0.000000
47: The x:-3.999664, Results:0.000000
48: The x:-3.999731, Results:0.000000
49: The x:-3.999785, Results:0.000000
50: The x:-3.999828, Results:0.000000
51: The x:-3.999863, Results:0.000000
52: The x:-3.999890, Results:0.000000
53: The x:-3.999912, Results:0.000000
54: The x:-3.999930, Results:0.000000
55: The x:-3.999944, Results:0.000000
56: The x:-3.999955, Results:0.000000
57: The x:-3.999964, Results:0.000000
58: The x:-3.999971, Results:0.000000
59: The x:-3.999977, Results:0.000000
60: The x:-3.999982, Results:0.000000
61: The x:-3.999985, Results:0.000000
62: The x:-3.999988, Results:0.000000
63: The x:-3.999991, Results:0.000000
64: The x:-3.999992, Results:0.000000
65: The x:-3.999994, Results:0.000000
66: The x:-3.999995, Results:0.000000
67: The x:-3.999996, Results:0.000000
68: The x:-3.999997, Results:0.000000
69: The x:-3.999998, Results:0.000000
70: The x:-3.999998, Results:0.000000
71: The x:-3.999998, Results:0.000000
72: The x:-3.999999, Results:0.000000
73: The x:-3.999999, Results:0.000000
74: The x:-3.999999, Results:0.000000
75: The x:-3.999999, Results:0.000000
76: The x:-3.999999, Results:0.000000
77: The x:-4.000000, Results:0.000000
78: The x:-4.000000, Results:0.000000
79: The x:-4.000000, Results:0.000000
80: The x:-4.000000, Results:0.000000
81: The x:-4.000000, Results:0.000000
82: The x:-4.000000, Results:0.000000
83: The x:-4.000000, Results:0.000000
84: The x:-4.000000, Results:0.000000
85: The x:-4.000000, Results:0.000000
86: The x:-4.000000, Results:0.000000
87: The x:-4.000000, Results:0.000000
88: The x:-4.000000, Results:0.000000
89: The x:-4.000000, Results:0.000000
90: The x:-4.000000, Results:0.000000
91: The x:-4.000000, Results:0.000000
92: The x:-4.000000, Results:0.000000
93: The x:-4.000000, Results:0.000000
94: The x:-4.000000, Results:0.000000
95: The x:-4.000000, Results:0.000000
96: The x:-4.000000, Results:0.000000
97: The x:-4.000000, Results:0.000000
98: The x:-4.000000, Results:0.000000
99: The x:-4.000000, Results:0.000000
Program ended with exit code: 0

눈에서도 확인 할 수 있듯이 Results가 최소로 나오는 x값은 -4 가 되겠다.

위키피디아의 문헌을 붙여두니 설명을 더 보고싶은 분은 참고 하시길 바란다.

위키백과 - 경사 하강법

 

 

여기에 작성하는 모든 포스팅 들은 스스로의 지식의 정리와, 지식의 공유 차원에서 정리한 것입니다.

학교의 레포트나 과제등은, 본인 스스로가 공부를 해서 직접 제출 하도록 합시다.

 

이 글에 사용된 자료는 모두 블로그 주인장이 만든 것입니다.

다른 블로그, 사이트 등에 가져가는 일이 없도록 해 주시기 바랍니다.