Machine Learning:Multi Layer Perceptrons (Prof. Dr. Martin Riedmiller)

신경망 자료 중 잘 설명된 강의 자료가 있어서 번역하였다.

원본 출처 : http://ml.informatik.uni-freiburg.de/_media/documents/teaching/ss09/ml/mlps.pdf

Neural networks

• 단일 뉴런은 복잡한 문제에는 맞지 않다. (선형 문제는 가능하다.)
• 네트워크 문제를 수식으로 풀어내는 것은 너무 시간이 소요된다.
• 네트워크의 훈련은 일련의 데이터 세트로 가능해야 한다.
• 비선형 문제는 수식으로 풀어내야 하지만, 다중 차원 문제에서 부분해를 사용한 접근은 분명히 한계가 있다.
• 일련의 샘플 데이터 세트가 있다면 이런 문제에 대한 일반 모델을 구하는 것이 궁극적인 Neural networks의 목적이다.
• 기본 아이디어는 Multi Layer Perceptron (Werbos 1974, Rumelhart, McClelland, Hinton 1986) 에서 제안되었다. MLP는 Feed Forward Network라 불리기도 한다.

MLP에서 Neuron의 의미
일단 기본적인 Perceptron은 다음의 비연속 함수를 사용한다.

그러나 수학적인 이유로 아래 처럼 부드러운 분포를 가진 함수를 사용한다.

 는 논리 함수라 불린다. 논리 함수의 특성으로 다음을 꼽을 수 있다.

1. 
2. 
3. 연속이며 미분 가능하다.

Multi layer perceptrons

MLP는 논리 결과를 출력하는 노드들의 집합으로 이루어진 유한 비주기 그래프이다.

i번째 레이어 노드들의 출력은  i+1번째 레이어의 입력값으로 활용된다. 그림 처럼 많은 노드들을 조합하면 아주 복잡한 함수도 계산 가능하다.

MLP의 특징을 서술하면 다음과 같다.

1. 입력 연결이 없는 노드를 입력 뉴런이라 하며 입력 패턴이 n개이면 입력 뉴런 또한 n개이어야 한다.
2. 출력 연결이 없는 노드를 출력 뉴런이라 한다. MLP는 한개 이상의 출력 뉴런을 가질 수 있다.
   출력 뉴런의 수는 출력이 서술해야 할, 값의 형태에 달려 있다.
3. 출력/입력 뉴런이 아닌 모든 노드를 히든 뉴런이라 한다.
4. 그래프가 비주기이기 때문에, 모든 뉴런은 레이어로 분류할 수 있으며 입력 레이어를 첫번째 레이어로 삼는다.
5. 다음 레이어를 뛰어넘어 그 다음 레이어로 연결하는 선들을 Shortcut(지름길)이라 부른다.
6. 대부분의 MLP에서 현재 레이어의 모든 뉴런은 shortcut 없이 다음 레이어의 모든 뉴런과 연결되어 있다.
7. 모든 뉴런은 숫자로 표현 가능하다.
8. Succ(i) 은 i번째 레이어를 기준으로  i → j 이 존재하는 j번째 레이어의 모든 뉴런이다.
   (Successors : 후임자)
9. Pred(i)은 i번째 레이어를 기준으로 j → i가 존재하는 j번째 레이어의 모든 뉴런이다.
   (predecessor : 전임자)
10. 모든 연결은 실수로 이루어진 가중치를 가지고 있다. i → j 연결에서의 가중치(Weight)를  이라 한다.
11. 모든 히든 레이어와 출력 레이어의 입력으로 바이어스(bias) 가 있다. i 레이어의 바이어스 가중치를  이라 한다.

계산의 편의를 위해 다음의 변수를 정의한다.

1. 히든 뉴런과 출력 뉴런은  (Network input)이라 불리는 입력을 표현하는 변수를 가진다.
2. 모든 뉴런은 라 불리는 출력을 표현하는 변수를 가진다.

 입력이 존재할 때, MLP는 다음과 같이 표현된다.

1. 모든 입력에 상응하는 입력 뉴런이 존재함으로
   
2. i번째 레이어의 모든  히든, 출력 레이어
   이전 레이어에서  가 계산되어 존재함으로,  에서 와 는 다음과 같다.
   
   
   
3. 출력은  이다.

간단히 출력 값이 결정되는 과정을 일러스트레이션으로 나타내면 다음과 같다.

의사 코드

Require : pattern , MLP, enumeration of all neurons in topological order 

Ensure : calculate output of MLP 

 1: for all input neurons i do

 2:    
 3: end for

 4: for all hidden and output neurons i in topological order do
 5:    
 6:     
 7: end for
 8: for all output neurons i do
 9:     assemble  in output vector 
10: end for
11: return 


추가 논의

논리 함수를 사용하는 뉴런은 0과 1사이의 값만 출력할 수 있다. 만약 더 넓은 범위의 실수 값을 얻고 싶다면, 다음과 같은 함수도 고려할 만 하다.

1. tanh 함수.
   
2. 선형 함수
   

뉴런 출력을 계산하는 방식은 논리 함수와 비교할 때, 과 의 관계만 차이가 있고 다른 부분은 비슷하다.

함수는 각 뉴런의 국부적인 특성으로 정의하여도 관계 없다.

전형적인 신경망 위상 형태

1. 회귀 분석 목적: 출력 뉴런의 뉴런 함수는 선형 함수 이다. (함수에서 독립 변수와 종속 변수와의 관계가 1:1인 함수)
2. 분류 목적 : 출력 뉴런의 뉴런 함수는 논리/tanh 함수이다.
3. 모든 히든 뉴런은 논리 함수이다.
4. 레이어 형태
   "입력 레이어 - 첫번째 히든 레이어 - 두번째 히든 레이어 - ... - 출력 레이어"로 구성되며, i번째 레이어의 모든 뉴런의 i+1번째 레이어의 모든 뉴런과 연결된다. 또한 shortcut은 없다.

보조 정리

모든 Boolean 형태 함수는 한개의 히든 레이어 MLP로 구현 가능하다.

출력 범위가 정해져 있고 연속인 모든 함수는, 어느 정도의 오차를 감안한다면 한개의 히든 레이어를 가진 MLP로 구성가능하다.

증명 : Cybenko (1989). Idea : partition input space in small cells

MLP 훈련

훈련용 데이터 세트 와 MLP가 있다면 훈련을 통해 MLP의 가중치 값들을 적절하게 조합할 수 있다.
 는 회귀 분석일 경우 실수 이고 데이터 분류가 목적이면 0이거나 1이다.

MLP 훈련은 최소 제곱법(Least square method)에 따라 아래의 결과가 최소가 되는 의 집합을 찾는 문제로 귀결된다.



은 입력값 와 가중치 에 의해서 결정되는 전체 네트워크의 출력 값이다. 분석을 가능하게 하기 위해, 독립 변수 와 종속 번수 와의 관계는 연속이며 미분 가능한 경우만 살펴 볼 것이다.



을 만족하는 모든  는 극대 혹은 극소점으로 가장 작은 의 후보들이다. 극대/극소 값에서 극소값은 작은 r에 대하여



을 만족한다.

문제는 찾은 극소점이 최소점임을 보장할 수 없다는데 있다. 그러므로 MLP 훈련은 최적의 효과가 안나올 수도 있다. 이 문제를 Local minima problem (in BackPropagation)이라 부른다. 이 문제 해결을 위한 알고리즘은 최근 들어 발표되고 있으니 따로 찾아보는 것도 괜찮다.

극소점을 찾는 수치해석 방식을 보자. 극소점을 찾는 방법은 임의의 지점에서 시작하고 지점에서의 기울기가 0이 될때까지 반복적으로 찾아간다.



그러면 는 어떻게 결정되어야 할까?

아래의 그림과 같이 임의의 지점  에서의 기울기는 음수이다. 가 양수여야 한다.

아래 그림과 같은 경우는 기울기가 양수이다. 가 음수여야 한다.

아래 그림과 같은 경우 찾고자 하는 지점과 가까우므로 의 값이 작아야 정확한 값을 찾을 수 있다.

아래 그림의 경우,  충분히 커야 빠르게 수렴이 가능하다.

위의 경우를 종합하여 보면 최적의 식은 다음과 같다.

 인 을 학습율(Learning rate)이라 한다.

GRADIENT DESCENT

의사코드

앞서 이야기한 극소점 찾기의 의사코드이다.

Require : Mathematical function , learning rate 

Ensure : returned vector is close to local minimum of  

 1: choose an initial point 

 2: while  || not close to 0 do
 3:    

 4: end while
 5: return 

그러면, 아래와 같은 질문이 떠오른다.

1. 의 초기값은 어떤 값으로 정해야 하는가?
2. 은 어떤 값을 선택해야 하는가?
3. 위 알고리즘은 정말 최소점으로 수렴할까?

작은 을 선택한 경우, 알고리즘은 최소점으로 수렴한다.

아주 작은 을 선택한 경우, 알고리즘은 더 확실하게 수렴하지만, 아주 느리다.

적당히 큰 을 선택한 경우, 수렴한다.

큰 을 선택한 경우, 발산한다.

위에서 본 것처럼 의 선택은 알고리즘의 동작에 아주 결정적인 영향을 끼친다. 충분히 작은 만이 수렴함을 보장한다. 그러나 이 작을 경우 해을 구하는 시간이 아주 오래 걸린다.
대체적으로 수렴 여부는 의 크기에 달려 있다.
다음의 그림은 Flat spots and steep valleys 문제를 보여준다.

Flat spot인 은 우리가 관심을 가질 지역이 아니므로 빨리 벗어나야 하며, 기울기가 급격하게 변하는 에서는 의 값이 충분히 작아야 한다.

1차원 함수가 아닌 더 높은 차원에서는 단순 기울기의 크기만으로 을 결정할 수 없다. 크기가 크더라도 방향이 맞지 않다면, 수렴하는 값을 쉽게 찾을 수 없다. 이것을 zig-zagging problem이라고 한다.

결론적으로 단순한 Gradient descent만으로는 원하는 결과를 얻기가 쉽지 않다. 이러한 문제들을 극복하기 위해 몇개의 휴리스틱 방법들이 제안돼었다. 대표적인 몇개을 꼽아보면 다음과 같다.

• Momentum을 이용한 gradient descent 방식.
• 다차원에서 각 차원별 별도로 학습률을 지정하는 방식.
• 상황별 학습율 방식. (Adaptive learning rate)
• 편미분과 별개로 차분 길이을 계산하는 방식.

Momentum을 이용한 gradient descent 방식.

이 아이디어의 핵심은 차분의 변화량을 보다 부드럽게 만드는 것이다. 즉 현재의 차분에 이전 차분 값을 어느정도 반영하는 것이다.

1: choose an initial point 
2:  set   (step width)
3:  while  || not close to 0 do
4:   
5:   
6: end while
7: return 

 범위 안에서 임의로 정해지는 가 새로 추가된 변수이다.  = 0일 경우, 일반적인 Gradient descent이다.

이 방법의 장점으로는

• zig-zagging 이 줄어든다. (차분의 방향성이 급격히 변하지 않고 천천히 변화된다.)
• Flat spot지역에서 수렴이 가속된다.
• 편미분의 부호가 바뀌면 수렴이 감속된다.

반면 단점으로는 아래가 있다.

• 추가 변수 를 결정해야만 한다.
• 의도치 않은 다른 종류의 zig-zagging이 발생할 수 있다.

Super-SAB (Tollenare 1990)

각 차원변수에 대하여 별도로 학습율을 관리하며 상황에 맞게 변화 시킨다. 편미분식의 부호가 변화되면 학습율은 줄어들고, 부호가 계속 유지되면 학습율은 증가한다.

 1: choose an initial point 
 2: set initial learning rate 
 3: set former gradient 
 4:  while  || not close to 0 do
 5:    
 6:    for all dimensions i do
 7:         
 8:         
 9:     end for
10:    
11: end while
12: return 

 은 수동으로 결정되어야 할 추가 변수이다.  이면 일반적인 Gradient descent와 같다.
Super-SAB는 다음과 같은 장단점이 있다.
장점

• 차원별로 학습율을 따로 관리하여 zig-zagging 문제가 줄어든다.
• Flat spots 지역에서는 학습율은 커진다.
• 편미분의 부호가 바뀌면 학습을은 줄어든다.

단점

• 차분 길이는 여전히 편미분에 종속적이다.

RProp (Riedmiller & Braun, 1993)

각 차원에 맞게 차분 길이을 사용하는 방식으로, 편미분의 부호가 바뀌면 차분길이는 줄어들고 부호가 바뀌지 않는다면 차분길이는 늘어난다.


 1: choose an initial point 
 2: set initial learning rate 
 3: set former gradient 
 4:  while  || not close to 0 do
 5:    
 6:    for all dimensions i do
 7:         
 8:         
 9:     end for
10:    
11: end while
12: return 

 은 수동으로 결정되어야 할 추가 변수이다. MLPs의 경우, 경험적으로 , 초기  = 0.1 이 좋은 값이라고 알려져 있다.
Rprop는 앞서 언급한 모든 알고리즘의 단점을 보완한다.

그외 학습 방식이 아니고 해를 직접 구하는 방식의 알고리즘이 몇개 더 있다.
테일러 시리즈를 이용한 수치해석적 방법인 Newton 방법, Quickprop(Fahlmann, 1988), Line search 방법이 있고 해를 직접 구하기 때문에 보다 정확하지만 느리고 경우에 따라서는 불안정한 해를 낼 수도 있다.
(원본에서는 자세히 설명하고 있지만 여기서는 제외하겠다. 관심이 있다면 별도로 공부하길 바란다.)

Back to MLP Training

다시 MLP로 돌아가 에러 함수를 살펴보자.

위의 함수는 각 변수 에 따라 값이 변하고 위의 값이 최소인 각 레이어별 를 구하는 것이 최종 목적이다.



라 두면,



이고,



이다. 즉 전체 에러에 대한 편미분은 각 항을 각각 편미분 한 후, 더해도 상관없다.

 는 입력 에 따른 출력 값이다.


각 에러 항은

  

이고, 각 출력에 대한 편미분은 다음과 같다.



각 뉴런의 출력 는 각 뉴런의 입력 에 종속적이므로 체인룰을 적용하면,



이고

 이므로

1.   선형 출력 함수일 경우  이므로
   
   
2. 논리 출력 함수일 경우
   
   
3. tanh 함수일 경우
   
   

이 문서의 관심사는 각 레이어별 를 구하는 것이다.  인접한 두 레이어를 각각 j, i 레이어라 가정하면 j레이어의 각 뉴런은 다음 i번째 레이어의 각 뉴런으로 다음과 같은 구조를 가진다.



우리의 관심사인 다음 식은 체인룰에 따라 분해가 가능하고



 이므로



i가 출력 뉴런이라면 위에서



는 이미 계산 하였다. 바이어스의 경우






이다.

결론적으로 출력 뉴런의 경우 우리가 원하는 모든 계산이 가능해지고 점진적으로 역계산 하면(Backpropagation) 나머지 뉴런에 대하여서도 계산이 가능하다.

위와 같은 MLP를 가정해보자.

위의 식으로 모든 미지의 항에 대한 계산이 가능해진다. 위의 식을 해석 할때, neuron2 와 neuron 3의 출력 함수가 다름에 주의를 기울여야 한다.
neuron2는 logical 출력이고 neuron3는 regression 출력이다.

각 뉴런의 [미분(출력 / 입력)]을 계산 할때  두 뉴런이 아래와 같이 다르게 계산되는 것을 유의하여야 한다.






의사 코드

1: choose an initial weight vector 
2: initialize minimization approach
3: while error did not converge do
4:    for all  do
5:       apply  to network and calculate the network output
6:       calculate  for all weights
7:    end for
8:    calculate for all weights summing over all training patterns
9:    perform one update step of the minimization approach
10: end while


수학적으로 접근 가능한 최선의 모든 알고리즘이 완성되었다.
인공 신경망 알고리즘의 수학적 의미는 비선형 방정식의 최적해를 구하는 것이다. 단 앞서 언급한 local minima 문제를 고려하면 그 해가 항상 정답이지는 않다.
그러나 주어진 문제에서 극소값을 구하는 방식이므로 차선으로 사용 가능하다. 훈련 데이터 세트의 최소 자승법은 제곱 항이 있는 비선형이고 반드시 극소값이 존재한다. 즉 차선은 항상 존재한다.