Ch7.2 Stochastic Methods - Stochastic search

2020-2학기 서강대 김경환 교수님 강의 내용 및 패턴인식 교재를 바탕으로 본 글을 작성하였습니다.

 

7.2 Stochastic search

---

  이해를 돕기 위해 일반적인 2차 최적화 문제의 논의로부터 시작한다. 2차 최적화에 접근하는 해석학적 방법이 있지만, 큰 규모의 문제들에 잘 맞지 않는다. 여기서는 서로 다른 후보 솔루션들에 대한 탐색 방법에 초점을 위해 2차를 예시 든다. 

▶ suppose we have a large number of variables, where each variable can take one of two discrete values.

많은 변수 $s_i$, $i=1,2, ..., N$을 가지며, 각각의 변수는 binary(이산 -1 또는 1) 값 중 하나를 취할 수 있다고 가정하자. 그러면 최적화 문제는 아래와 같다. 

• The optimization problem is to find the values of the $s_i$ so as to minimize the cost or energy

 즉 아래 식 (1)의 비용 또는 에너지를 최소화하는 $s_i$의 값들을 구할 것.

$$ E = - \frac{1}{2} \sum^{N}_{i,j=1} w_{i,j}s_i s_j \tag{1}\label{1}$$

• $w_{i,j}$는 대칭이며, 양수 또는 음수를 가짐
• $w_{i,i} = 0$
• $s_i$와 독립적인, 즉 중요하지 않은 상수를 식 (1)인 $E$에 추가하기 위해 0으로 설정

이 최적화 문제는 노드들의 네트워크로 시각화될 수 있으며, 양방향 링크 또는 상호연결이 $w_{i,j}$들에 해당한다. 아래 [그림 2] 예시

[그림 2] Stochastic search

 

•  Imagine the network represents $N$ physical magnets. 

네트워크가 $N$개의 물리적 자석(magnet)들을 나타냄

•  The $w_{ij}$ are functions of the physical separations between the magnets.

$w_{i,j}$는 자석 간의 물리적 간격의 함수들임

• Each pair of magnets has an associated interaction energy which depends upon their state, separation and other physical properties:

자석 쌍들 각각은 그들의 상태, 간격 그리고 기타 물리적 속성에 종속되는 관련된 상호작용 에너지를 가진다.

$$E_{i,j} = -\frac{1}{2} w_{i,j} s_i s_j \tag{2}\label{2}$$ 

전체 시스템의 $E$ 식(1)는 주어진과 같이 식(2)의 상호작용 $E$의 모두의 합임

 최적화 작업은 가장 낮은 $E$를 가질 때인 가장 안정된 구성인 자석들의 상태의 구성을 찾는 것이다. 이 일반적 최적화 문제는 광범위한 어플리케이션에서 나타타며, 대부분의 경우 가중치들은 물리적 해석을 갖지 않는다. 단순히, 학습 방법들에 대해 응용에 관심을 둠

•  Except for very small problems or few connections, it is infeasible to solve directly for the $N$ values si that give the minimum energy. (e.g. the space has $2^N$ possible configurations.)

 매우 작은 문제 또는 소수의 연결을 제외하고는, 최소 $E$를 제공하는 $N$개 값을 갖는 $s_i$에 대해 직접 문제를 푸는 것은 사실상 불가능하다. 따라서 아래 "greedy search"알고리즘을 제안할 수 있다.

•  Greedy search <무모한 방법>
  

방법 : 각 node에 랜덤하게 상태를 할당하는 것에서 시작하여, 그 다음, 각 노드를 차례로 고려하고 $s_i=+1$ 상태에서의 에너지를 계산하고, 그런 다음 $s_i = -1$의 상태에서 계산하고, 그리고 더 낮은 에너지를 제공하는 것을 선정한다. (당연히, 이 판정은 0이 아닌 가중치 $w_{i,j}$로 node $i$에 연결된 node들에만 기반할 필요가 있음) 

단점 : usually gets caught in local minima or never converge.

 아쉽게도, greedy search는 시스템이 대개 local $E$ 최소들에 붙들리거나 결코 수렴하지 못하기 때문에(교재 computer 연습문제 1) 성공하지 못하므로, 다른 방법이 필요하다. 

 

▶ 7.2.1 Simulated annealing (모의 담금질?)

---

Annealing에 대한 사전적 정의 및 개념 설명

• in physics, the method for allowing a system such as many magnets or atoms in an alloy to find a low-energy configuration.
• the system is heated, thereby conferring randomness to each component (magnet).
• the process proceeds by gradually lowering the temperature of the system so as to allow the system to relax into a low- energy configuration.
• as the temperature is lowered, the system has increased probability of finding the optimum configuration.
• at moderately high temperatures the system slightly favors regions in the configuration space that are overall lower in energy, and hence are more likely to contain the global minimum.

 물리학에서 합금의 많은 자석 또는 원자 같은 시스템이 낮은 에너지 구성을 찾게 하는 방법은 "annealing"에 기반한다. 물리적 annealing시, 시스템은 가열되고, 그에 의해 각 요소(자석, magnet)에 randomness(랜덤성)을 부여한다. 결과로, 각 변수는 일시적으로 에너지 측면에서 불리한 값을 띠게 되고 전체 시스템은 높은 에너지를 갖는 구성들은 탐구한다. "annealing"은 시스템이 낮은 에너지 구성으로 이완될 수 있도록, 시스템의 온도를 점차적으로 낮추어, 궁긍적으로는 0을 향한 randomness가 없도록 진행한다. 이렇게 적당히 높은 온도에서 조차 전반적으로 에너지가 더 낮고, 그래서 global minimum을 포함할 가능성이 더 높은 구성 공간의 영역들을 시스템이 약간 선호하기 때문에 효과적이다. 온도가 더 낮아짐에 따라 시스템은 최적 구성을 찾을 확률을 증가시킨다. 이 방법은 아래 그림 오른쪽과 같이 golf course 지형 같은 경우도 있지만, 광범위한 에너지 함수에 성공적이다. 다행히, 우리가 고려할 학습에서의 문제들은 golf course 처럼 극단적인 케이스는 포함하지 않는다. (교재 내용 일부)

 

▶ 7.2.2 The Boltzmann factor (볼츠만 계수)

---

 기체의 분자나 고체의 자성체 원자 같이 어떤 온도 $T$에서 상호작용하는 수많은 물리적 요소의 통계적 특성은 철저하게 분석되어 왔다. 간단한 가정들에 의해 의존하는 주요 시스템은 다음과 같다. 시스템이 에너지 $E_\gamma$를 갖는, $\gamma$에 의해 indexing 되는 (binary) 구성에 있을 확률은

$$P(\gamma) = \frac{e^-{E_\gamma / T}}{Z(T)} \tag{3}\label{3}$$

으로 주어진다. 

  참고 : 볼츠만 계수에 대한 이해 (우회적)

 균일한 외부 자계에서 상호작용하지 않는, 즉 상호연결 가중치들이 없는 수많은 자석들로 구성된 시스템에서 만일, 한 자석이 위를 가리킨다면, 즉 $s_i=+1$이면, 전체 시스템에 작은 양(positive) 에너지를 기여한다. 만일 자석이 아래로 향하면, 즉 $s_i = -1$이면, 작은 음(negative) 에너지를 기여한다. 모두의 총 에너지는 따라서 위로 향한 전체 자석 수에 비례할 것이다. 시스템이 특정 총 에너지를 가질 확률은 그 에너지를 갖는 구성의 수와 관계가 있을 것이다.

• the highest-energy configuration : $\left(\begin{array}{l}N \\ N\end{array}\right)=1$
• the next-to-highest energy configurations : $\left(\begin{array}{l}N \\ 1\end{array}\right)=N$
• the next-lower-energy configurations : $\left(\begin{array}{l}N \\ 2\end{array}\right)=N(N-1) / 2$

모든 자석이 위로 향하는 최고 에너지 구성을 고려하면 $\left(\begin{array}{l}N \\ N\end{array}\right)=1$개 밖에 없다. 그 다음으로 높은 에너지는 단 하나의 자석이 아래로 향한 경우로 $\left(\begin{array}{l}N \\ 1\end{array}\right)=N$개가 있다. 그 다음으로 높은 에너지 구성은 두 개의 자석이 아래로 향하는 경우로, $\left(\begin{array}{l}N \\ 2\end{array}\right)=N(N-1) / 2$개의 구성이 있다. 이처럼 상태 수는 에너지가 증가합에 따라 지수 함수적으로 하락항믈 보여줄 수 있다. 자석들의 통계적 독립성 때문에, 큰 $N$에 대해 에너지 $E$에 있는 상태를 찾을 확률도 지수 함수적으로 줄어든다. (연습문제 2), 

• the exponential form of the Boltzmann factor is due to the exponential decrease in the number of accessible configurations with increasing energy
• $T$ in the Boltzmann factor : $e^\frac{E_\gamma}{T}$

• at high $T$, the probability is distributed roughly evenly among all configurations.

$$
e^{-E_{\gamma} / T} \approx e^{0}=1 \tag{4}\label{4}
$$

• at low $T$, it is concentrated at the lowest-energy configurations.

• in the case of magnets are interconnected by weights, the situation is a bit more complicated.

 그러면 위 식(3)의 Boltzmann 계수의 지수 함수적 형태는 에너지가 증가함에 따른 접근 가능한 구성 수의 지수 함수적 감소에 기인한다. 게다가, 높은 온도에서는, 대략적으로 가용한 에너지가 더 많으며, 따라서 더 높은 에너지 상태의 확률이 증가된다. 이는 Boltzmann 계수의 $T$에 대한 확률의 종속성을 정성적으로 묘사하고 있다. 높은 $T$에서는 확률이 모든 구성 간에 대략적으로 균등하게 분포되나, 낮은 $T$에서는 가장 낮은 에너지 구성에 집중된다.

 simulated annealing algorithm (algorithm 1 in p355)

[simulated annealing algorithm]

1. network 전체에 걸쳐 random하게 된 node의 state(상태, {0 또는 1})로 설정, 초기에는 높은 온도 "$T(1)$"을 설정
2. 하나의 node $i$를 random하게 선정해보자. 만일 "$s_i=+1$"라 하고, 이 구성에서의 시스템 에너지 $E_{a}$를 계산
3. 새로운 후보 상태 $s_i=-1$에 대해 $E_{b}$ 계산
4. 만일 $E_b \lt E_{a}$ 라면, 새로운 후보 상태를 받아들인다.
5. 그러나,  $E_b \gt E_{a}$, 이 변화를 아래의 확률로 받아들인다.
6. $e^{-\Delta \mathbf{E}_{ab}/T}$ , where $\Delta \mathbf{E_{ab}}=\mathbf{E}_b - \mathbf{E}_a$

 5, 6번째 의미는 에너지 측면에서 덜 유리한 상태를 가끔식 수용하는 것은 anneling algorithm의 핵심 요소임, 단순한 경사 강하와 탐욕스런 방식에 비해 탁월하다고 한다. (즉, 시스템이 원치 않는 local 에너지 상태에 빠진 경우, 뛰쳐 나오는 것을 가능하게 함) 

 위의 Algorithm 1에 대한 추가 설명은 다음 자료를 참고하자.

[강의자료 일부]

• ⓐ $\mathbf{E}_b \lt \mathbf{E}_a$인 경우, 당연히 받아들일 수 밖에 없음 ($\mathbf{E}$가 적을 수록 좋음)
• ⓑ $\mathbf{E}_a \lt \mathbf{E}_b$인 경우, $\epsilon-greedy$ 하게 $s_i$의 state 변경을 확률적으로 받아들임
• ⓒ $T$는 진행횟수(시간)에 따라서 감소하므로, $s_i$의 상태 변경에 대한 확률은 더 작아지게 될 것이다. 즉, local에서 빠져나올 확률은 더 적어질 것이다. (하지만, 우리의 믿음은 다음을 가정을 하므로 "시간이 지날수록 점차 원하는 global에 접근" 이를 받아들이도록 한다.)

• several aspects of the algorithm that must be considered

 알고리즘에 몇 가지 주의해서 고려해야 할 측면이 있다. - 특히, "시작 온도", "온도 감소 속도", "마지막 온도", "정지 기준"

• starting temperature (시작 온도)
  

1. $T(k)$ : the cooling schedule (냉각 스케줄)
2. we demand $T(1)$ to be sufficiently high that all configurations have roughly equal probability. 

 모든 구성이 대략 같은 확률을 갖도록 $T(1)$이 충분히 높을 것을 요구, 구체적으로는 임의의 구성들 간의 최대 에너지 차이보다 온도가 더 클 것을 요구함 ($\Delta \mathbf{E}_{ab} \lt\lt T$), 높은 $T$는 랜덤한 초기 구성이 최적으로부터 멀리 떨어져 있을 수 있기 때문에, 필요하게 될 수도 있는 어떠한 구성으로든 시스템이 이동할 수 있게 함

• the rate of temperature decreasing (온도 감소 속도)

1. the decrease must be both gradual and slow enough that the system can move to any part of the state space before being trapped in an unacceptable local minimum.
2. $T(k+1) = cT(k), 0.8 \lt c \lt 0.99$

 local minima에 갇히기 전에 상태 공간의 어떠한 부분으로도 시스템이 이동할 수 있기에 충분하게, 점진적이고 느려야 한다. global optima는 많아야 이 단계 수만큼 임의의 구성과 다를 수 있기 때문에, 최소한 $N/2$회 허용해야함

• the final temperature (정지 기준, 마지막 온도로 결정)

1. it must be low enough that there is negligible probability that if the system is in a global minimum will move out.

최종 온도는 시스템이 global minima에 있다면 거기서 빠져 나올 확률이 무시할 정도가 되도록 충분히 낮아야 함

 다음의 예제는 "simulated annealing algorithm" 을 적용한 사례로, $T$가 낮아짐에 따라, global minima에 "가까운" 상태들만이 시험된다.

▶ 7.2.3 Deterministic simulated annealing (결정론적 모의 담금질)

• stochastic simulated annealing is slow because of the discrete nature of the search through the space of all configurations.
• a faster, alternative method is to allow each node to take on analog values during search;

 탐색하는 동안 각 노드가 continious(analog) 값을 취하게 허용하는 것이고, 마지막에는 최적화 문제가 요구하는 대로 그 값들은 $s_i = \pm 1$이 되도록 강제로 만들어 주는 것이다.

 특정 $node_i$에 가해진 힘을 $l_i$로 식 (5)라고 하자. 

 $$l_i = \sum_j \omega_{ij}s_j \tag{5}\label{5}$$

 갱신된 값은 $tanh(), T, l_i$을 활용하면 식 (6)과 같음

$$s_i = f(l_i, T) = tanh[l_i/T] \tag{6}\label{6}$$

 위 방법을 사용하면 아래 그림가 같이 에너지 $E$의 편미분은 각 변수에서 선형적이다. 따라서 어떤 축에든 평행한 모든 "단면(cut)"에는 local minima가 없다. 특히, 최적화 문제에서 요구하듯이, 모든 $i$에 대해 극 값 $s_i = \pm 1$에서 발생함을 알 수 있다.

 

 

Reference

---

• pattern classification by richard o. duda