[패턴인식]Chapter 7.1-2 Stochastic Methods

 

 

(김경환 교수님의 자료와 수업을 통해 제작되었습니다.)

7.1 Introduction

  low dimension에 대한 학습은 손으로 계산하거나, 접근이 쉽다. dimension이 높아질수록 손으로 계산하기가 어려워지고, 복잡해져 gradient descent로 solution region에 점점 다가가게 된다. 접근하는 방향에 있어서 랜덤성을 수용하는 것은 학습에 도움이 되고, 복잡한 모델이더라도 좋은 parameter를 갖도록 도와준다.

 

  이에 따라 두가지 해결 방법을 제시하는데, 첫 번째는 Boltzmann learning이고, 두 번째는 genetic algoritms이다. 이 장에서는 첫 번째의 방법에 집중하도록 한다. 이 방법은 grdient 방법으로 설명될 수 있는 점도 있지만,  복잡한 problem에 대해 유용한 점을 보인다. 계산 과정이 복잡하기 때문에 컴퓨터 없이는 잘 쓰이지 않을 것이라 한다.

 

7.2 Stochastic search

  물리적인 현상에서 나타나는 것과 같이 위와 같이 Energy를 쓰게 된다. $s_i$와 $s_j$는 +1,-1으로 두 가지 값을 가질 수 있게 된다. 자기장을 형성하는 magnet $s_i$와 $s_j$의 상호작용에 의해 에너지가 발생하고, 이에 상호작용의 정도 $w_{ij}$를 곱한 값을 모든 i와 j에 대해서 적용하여 더한 값이 전체 에너지 값을 갖게 된다. 실제 문제에서는 $w_ij$의 값이 물리문제에서의 상호작용의 정도를 나타내지 않고 일반화하여 classifer에 적용할 수 있다. 우리는 에너지를 안정적인 상태로 낮추는 것이 목적이 된다.

 

  E를 최소로 하는 값을 찾기 위해 모든 경우의 수에 대해 찾아본다면 N이 매우 작지 않은 경우를 제외하고 적용할 수 없을 것이다. 경우의 수는 $2^N$이 될 것이기 때문이다. 따라서 처음으로 사용할 수 있는 greedy algorithm은 $s_i$에 대해 +1, -1을 가질 때 각각에 대한 E를 비교하여 낮은 E값을 갖게 되는 것을 취한다. 이는 local minima에 대해 잡힐 수 있는 가능성이 높으므로 다른 방법을 이용한다.

 

  각 노드들은 위와 같이 연결되어 있는 것이다. 각 값들은 +1과 -1값을 가질 수 있게 되며 모든 노드들이 서로 연결되어 ㅇ있는 fully connected 상태이다. 위는 17개의 노드로 구성되어 있으며, 에너지를 가질 수 있는 모든 경우의 수는 $2^17$이다. visible과 hidden은 각각 10개, 7개 노드로 구성되어 있다.

 

[Simulated annealing]

  $s_i$의 값을 +1,-1 하나씩 바꿔가며 낮은 E 값을 갖는 것을 택하는 것은 local minima에 빠질 확률이 매우 높을 것이다. 이 문제를 해결하기 위한 방법으로 물리적인 annealing의 방법을 사용하게 되는데, 이 방법은 철을 연마하는 것 혹은 높은 온도에서부터 모양을 바꿔가며 항아리를 만드는 과정과 비슷하다. 처음에 온도가 높은 속에서는 물체가 모형을 변형하기 쉬워 전체적인 그림을 그릴 수 있게 되고, 온도가 낮아질수록 움직일 수 있는 변동성은 작아진다.

 

  이러한 부분이 에너지 측면으로는 좋아보이지 않을수도 있지만, local minima를 찾는데는 효율적이다. 무조건 낮은 에너지를 갖도록 하는 $s_i$상태를 찾고자 한다면 local minima에 빠질 확률이 높아질 것이기 때문이다. 따라서 $s_i$를 높은 온도 상태에서는 다음 상태의 E값이 조금 높더라도 이동할 수 있고, 낮은 온도에서는 최대한 낮은 에너지로만 움직이려는 방향성을 넣어 global minimum을 찾게 된다. 아래의 골프문제 같은 문제를 simulated annealing은 해결할 수 있다고 말한다.

  오른쪽과 같은 그림을 해결할 수 없을 것처럼 보이지만, 온도가 높을 때는 다음 상태의 에너지가 조금 높더라도, 최소점에서도 올라올 수 있는 가능성이 존재하기 때문에 움직이면서 온도가 낮아질수록 골프 hole에 도달할 수 있게 된다.

[The Boltzmann factor]

  물리적으로 다시 생각해보면 magent이 pointing up이 되면, E가 양의 방향으로 증가하게 되고, -1이 되면 음의 방향으로 증가한다. 이에 따라 전체 E는 pointing up된 magnet의 수로 나타낼 수 있을 것이다. 가장 높은 N은 $_NC_N$이 될 것이고,  (모든 magnet이 up) 그 다음 높은 에너지에 해당하는 것은 $_NC_{N-1}(하나만 down)$이 될 것이다. 이는 에너지가 높아질수록 지수적으로 energy 조합의 개수가 줄어듦을 보여준다.

 

  또한, T가 높아질수록 가질 수 있는 에너지의 수가 많아질 것이고, 낮아짐에 따라 가질 수 있는 에너지의 수가 줄어들게 될 것이다. 위와 같은 문제를 weighted 문제로 끌고 오면 서로의 관계성을 나타내어야 하여 다른 문제가 되겠지만, 경향성은 위와 같이 될 것이라 한다.

  또한, $P(\gamma)$는 위의 경향성을 나타낸 식이고, Z(T)는 분자항을 더한 값이 된다. 이 때, $P(\gamma)$를 Boltzmann factor라 하며, 분모항인 Z(T)를 Partition function이라 한다. partition function은 $2^N$의 경우의 수를 갖게 될 것이므로 모든 T에 대해 계산을 하는 것은 시간이 오래 걸릴 것이다. 하지만, 분모항을 계산하지 않아도 분자항 만을 이용해도 된다.

 

[Simulated annealing algorithm]

  위에서 언급했던 두가지 내용, 물리적인 접근과 SA 방법은 general optimization problem을 해결하기 위한 방법이었다. $s_i(1)$의 상태는 랜덤하게 시작하고, T(1)은 높은, 변동성이 큰 상태로 알고리즘을 시작한다. 위에서 언급한 바와 같이 우리는 낮은 에너지를 찾아가는 과정이고, $E_a$를 $s_i$가 원래 +1이 었을때의 E, $E_b$를 -1로 해준 상태에서의 E라고 하여 다음 state가 될 두 후보를 정한다. 이에 낮은 에너지를 찾아가는 것이 목적이겠지만, 그 다음 stage가 조금 높더라도 다음의 확률로 높은 에너지가 되는 후보를 선택할 수 있다. 

  이 경우는 에너지가 낮은 곳을 찾아가려는 방향에서 위배되는 경우라고 생각할 수 있지만, local minima를 넘어가고 global minimum을 찾기 위한 과정이라고 말했다. 높은 온도에서는 위의 값이 커지게 되므로 확률적으로 다음 state가 에너지가 높더라도 넘어갈 수 있는 힘이 있고, 낮은 온도에서는 다음 state가 낮은 방향으로만 선정되어 $s_i$를 정하게 된다.

 

  위와 같이 두 후보 중에서 판별하여 선정하는 과정을 pooling이라고 하고, 온도를 점점 낮춰가며 알고리즘을  진행한다. 온도가 낮아짐에 따라 더 높은 state로 이전할 가능성이 줄어들고, 이는 greedy algorithm과 유사해져 간다. ($s_i$를 바꿔가며 낮은 state가 되는 값만을 선택하는 방법, 위에서 언급) 온도가 내려가는 정도를 천천히 하게 된다면 global minimum에 다가갈 확률이 높아지게 될 것이다.

 

  실제로 알고리즘을 진행할 때에는 다음 state의 후보가 되는 $s_i$의 상태, polled unit과 연결된 것에만 전체 에너지의 변화에 영향을 미치게 된다. 따라서, polled unit과 연결되지 않은 노드들에 대해서는 계산하지 않고 계산량을 줄인다. $N_i$를 i번째 노드와 연결된 노드를 말하고, fully connected되어있는 상태에서는 N-1개의 노드가 존재할 것이다. 이 상태에서 에너지는 i번째 노드와 상호작용하는 에너지로 하고, 이 값이 이전 state보다 작거나, 큰 경우에는 $e^{-(E_b-E_a)/T(k)}$의 확률로 다음 state를 정하게 된다. 

 

  이 다음 state가 큰 경우를 실제 코드를 구현함에 있어서는 $e^{-(E_b-E_a)/T(k)}$의 확률을 rand[0,1)의 함수를 이용하여 이 값보다 클 때 그 state로 넘어갈 수 있도록 한다. $e^{-(E_b-E_a)/T(k)}$이 값이 크다면, 에너지가 더 높더라도 넘어갈 수 있는 확률이 높다는 뜻이고, 이 값이 어떠한 값(0과 1사이)보다 커지는 경우도 많아질 것이다. 이러한 점을 종합하여 아래와 같은 알고리즘을 구성한다.

  polled unit은 하나씩 존재하기 때문에 sequential simulated annealing이라 부르기도 한다. 온도는 알고리즘이 진행됨에 따라 낮춰가야 하고, global minimum을 찾기 위해 최대한 천천히 온도를 감소시켜야 한다. 온도를 낮춰가며 진행하는 과정을 annealing schedule이라고 하며, 처음 시작하는 온도는 $E_a-E_b$값의 최대보다는 큰 값을 가져 exp의 지수부분이 1보다 작은 값을 갖기 원할 것이고, 마지막의 온도는 global minimum에서 빠져나가지 못하도록 충분히 낮은 온도로 선택되어야 할 것이다. 이 annealing은 최소 N/2번 반복하여 이루어져야할 것이고, 실제 문제에서는 더 많은 학습량을 가져야 한다.

  위의 문제에서 $s_i$를 바꿔가며 낮은 E를 찾아가는 모습이다.  노드의 개수는 N=6인 상태에서 $2^6=64$개의 조합으로 존재하고, T가 높을 때에는 state가 변하는 것이 많은 것을 볼 수 있는데, 이는 온도가 높을 수록 다음 state의 에너지가 높더라도 다음 상태로 넘어갈 수 있는 확률이 높기 때문이다. 학습이 진행되면서, 온도가 낮아질수록 다음 state로 넘어갈 확률이 낮아져 변화하는 정도가 작아지는 것을 볼 수 있는데, 중간에 global minimum에 도달 했다가 한번 다른 state로 넘어가는 모습을 볼 수 있다. 이는 아직 온도가 낮아지지 않아 다른 local minimum으로 넘어갈 수 있는 점을 보여준다. 결국 종료하는 시점에서는 global minimum을 찾은 것을 볼 수 있다.

 

  위에서 말한 annealing schedule에서 $T(k+1)=cT(k) with 0<c<1$로 감소되어야 하고, 온도를 천천히 감소시켜야 한다는 점에서 0.8<c<0.99를 많이 사용한다고 한다. 

 

  위 그림에서는 annealing schedule에서 가능한 온도 4가지를 선택하여 보여준 것이다. $P(\gamma)$는 그 state에 존재할 확률이고, 온도가 낮아짐에 따라 global minimum에 존재할 확률이 높아져 막대기가 높은 것을 볼 수 있다. 위에서 볼 수 있는 점은 어떠한 state로 갈 모든 확률이 음수 혹은 0이 아니라는 것이다. 하지만, 매우 작은 값을 갖기 때문에 다음 state로 변하지 않아야될 수 있는 경우가 많아진다. 즉, N이 커져 있는 복잡한 실제 문제에서 모든 경우의 수 ,$2^N$을 모두 조사하는, 시간적 부담이 큰 부분을 해소할 수 있다는 점에서 annealing을 진행하는 것이 장점이 된다. 

 

[Deterministic simulated annealing]

  위에서 $s_i$값이 +1 혹은 -1로 가질 수 있던 부분에서 -1과 +1 사이에서 연속적인 값을 갖도록 하기 위한 방법이 Deterministic simulated annaling이다. 여기서는 $s_i$상태를 온도에도 영향을 받는 state라고 하고, 노드$i$에 가해진 힘을 $l_i$라 설정하면, $s_i$는 다음과 같이 $s_i$를 갱신한다.

  온도가 높아질수록 큰 랜덤성을 갖게 되어 다른 노드에 영향을 받는 정도가 작아지고, $s_i$는 1이 되기 어려워진다. 

  각 온도 T=0.01, 0.1, 1, 5에 대해서 그래프를 나타내었고, 노드 i가 받는 힘 $l_i$에 대해 나타내었다. 온도가 크면 랜덤성이 크며 노드 i에 큰 힘이 주어지더라도 $s_i$는 쉽게 1이 되려하지 않는 모습을 보인다. 하지만 온도가 낮을 때에는 랜덤성이 아주 작고, 작은 힘이 주어지더라도 $s_i=1$에 쉽게 다가가는 모습을 볼 수 있다.

  이렇게 연속적인 경우에 에너지 단면을 보게 되면, 각 편미분은 각 변수에 대해 linear하다. 따라서 어떤 축이든 축에 평행한 모든 단면에는 local minima가 존재하지 않는다. stable한 에너지의 local minima가 없다는 것이다. 그림에서 보면 전체 에너지는 $s_1, s_2, s_3$으로 이루어진 3차원이나 각 $s_3$에 대해 2차원 평면으로 그렸다. $s_i <->-s_i$의 대칭성을 갖고 있기 때문에 그래프도 대칭을 갖고 있는 것을 볼 수 있으며, (-1,1,-1)과 (1,-1,1)에서 최소가 발생하는 것을 볼 수 있다.

 

  이 탐색 방법은 노드에 가해진 힘의 mean에 영향을 받기 때문에 mean-field annealing이라고도 불린다. $l_i$를 구함에 있어서 노드 i에 대한 힘만 주어지고, i와의 상호작용은 고려하지 않는다. 그 이유는 온도가 낮아짐에 따라  $s_i$에 대한 simultaeneous equations를 deterministically하게 풀어낼 수 있기 때문이다. 

  알고리즘은 $l_i$와 $s_i$를 구하고, $s_i$를 구해가며 convergence cirterion met 혹은 $k=k_max$일 때 종료한다.

  이 과정은 앞의 stochastic annealing과 거의 유사한 solution을 제공하게 되고, 데이터가 많은 실제 문제들에서 훨씬 빠르게 적용될 수 있다고 한다. 위에서 구한 E를 다른 함수, $w_{ijk} s_i s_j s_k$의 sum의 최소를 찾는 것으로 바꿀 수도 있다고 한다.

---

Reference

• pattern classification by richard o. duda