시뮬레이티드 어닐링과 볼쯔만 머신
신경망 이론과 응용(1) : 김대수, 하이테크 정보사, 1992, Page 211~223
|
|
백프로파게이션 네트워크 [RUM86] 나 홉필드 네트워크 [HOP82, HOP85] 는 신경망에 있어서 매우 중요한 학습 모델인데 이 모델들이 매우 중요한 공통적인 문제점은 지역 최소점 (local minima) 문제이다. 문제의 해결에 있어서 우리가 일반적으로 추구하는 것은 지역 최소점이 아닌 전역적 최소점 (global minima) 을 찾는 것이다. 이 장에서는 고체를 높은 온도에서 녹인 후에 지역 최소점에 빠지지 않도록 서서히 식히면서 에너지의 상태를 최소화시키는 시뮬레이티드 어닐링과 이 알고리즘을 바탕으로 한 병렬처리 시스템의 하나인 볼쯔만 머신에 대하여 살펴본다. 1984년 힌턴 (G. E. Hinton) [HIN84] 등에 의해 제안된 이 모델은 홉 필드 네트워크와는 달리 에너지가 증가하는 방향으로도 작은 확율이나마 상태의 전이를 허용함으로써 지역 최소점에 빠질 구슬이 가장 최소의 에너지를 가진 곳으로 이동할 수 있도록 하여 최소값을 구할 수 있도록 하였다.
금속의 담금질 (annealing) 이란 고체를 녹을 때까지 가열하고 난 후 그것을 완전한 격자 상태의 결정체가 될 때까지 식히는 물리적인 과정이다. 이런 과정 중에 그 고체의 자유 에너지 (free energy) 는 최소화된다. 오래 전부터의 경험에 의하면 고체화되는 과정에서 지역 최소점에 빠지지 않도록 하기 위해서는 조심스럽게 서서히 식혀야 한다.
조합 최적화 (combinatorial optimization) 문제에서도 이와 유사한 과정을 정의할 수 있다. 이 과정은 잠재적으로 매우 많은 해결방안 중에서 최소의 비용이 드는 해답을 구하는 문제로 공식화될 수 있다. 우리는 여기서 비용 함수 (cost function) 와 자유 에너지 사이의 관계, 그리고 해답과 물리적인 상태의 관계를 정립함으로써 물리적인 담금질 과정의 시뮬레이션에 의거한 조합 최적화 문제의 해결 방안을 소개할 수 있는데 이러한 방법이 바로 시뮬레이티드 어닐링 (Simulated Annealing) 이다.
시뮬레이티드 어닐링은 스코트 커크패이트릭 (Scott Kirkpatrick), 젤라트 (Gelatt) 와 베키 (Vecchi) [KIR83] 등에 의해 처음 제안된 방법으로 조합 최적화 문제와 관련하여 소개되었다 [KIR82, KIR83, KIR94]. 또한 1985 년에 체르니 (Cerney)[CER85] 에 의해 독립적으로 연구 발표되었다. 이러한 개념들은 고체의 물리적인 담금질과 아주 많은 경우의 수를 가진 조합 최적화 문제 사이의 밀접한 관계에 의거한다.
이 방법의 두드러진 특징은 폭넓은 응용 가능성과 최상에 가까운 해답을 얻을 수 있다는 점이다. 그러나 이 방법에도 상당히 큰 단점이 있다. 상당히 좋은 해답을 얻는데 걸리는 계산 시간이 엄청나게 길다는 점이다. 그러나 시뮬레이티드 어닐링 알고리즘의 구현시 필요한 엄청난 시간은 대규모 병렬처리 (massively parallel execution) 를 기반으로 하는 계산 모델을 사용함으로써 상당히 줄일 수 있는데 그러한 모델 중의 하나가 바로 볼쯔만 머신 (Bolzmann machine) 이다.
EUR100 [AAR89] 은 유럽의 100대 도시들을 연결하는
순회판매원 (TSP) 문제인데 상호 대칭적이고 2차 평면적인 유클리트 거리를 다룬다.
거리 행렬 (distance matrix) 의 요소들은 테이블에 주어진 지리학상의 좌표로 계산되어
진다.
<그림 1> [AAR89] 은 EUR100 문제의 해결을 위하여 수행된 시뮬레이티드
어닐링 최적화 과정의 단계적 발전도를 보여준다. <그림 1> 의 (a) 에서 보는
바와 같이 처음의 해답은 100개 도시의 임의적인 나열로서 콘트롤 변수인 c 의 값이
17.85 인 경우인데 최적의 값과는 거리가 멀다. 이 해답은 매우 혼란스럽고 또한 매우
큰 엔트로피 (entrophy) 를 가지며 총 여행거리는 무려 129.965 나 된다. <그림 1>
의
(b) 와 (c) 는 콘트롤 변수인 c 가 각각 4.46 과 1.28 로 총 여행거리가 각각 68.153
과
33.048 로 점차 줄어들고 있다. 마지막으로, 거의 최적인 해답은 <그림 1>
의
(d) 와 같이 얻어지는데 이때의 c 값은 0.06 이다. 이 경우 패턴이 겹치지 않고 엔트로피가
매우 작으며 총 여행 거리가 앞의 경우들보다 훨씬 적은 21,456 에 불과하다.
<그림1> 시뮬레이티드 어닐링 알고리즘의 4가지
EUR100
해답을 위한 단계적 발전도
이 문제의 경우 최소 여행 거리는 21,134 이고 이 경우의 여행 루트는 <그림 2> [AAR88b] 에 나타나 있는데 직선의 연결은 최적의 여행 경로를 나타낸다. CYBER-205 컴퓨터에서 최적의 여행 경로를 구하는데 59.5 CPU 초가 걸렸다.
<그림 2> EUR100 문제의 최적화 해답
볼쯔만 머신은 신경망과 시뮬레이티드 어닐링으로부터의 흥미로운 성질들을 결합시킨 모델인데 대규모 병렬처리를 이용하는 강력한 계산 장치이다. 볼쯔만 머신은 1984년 힌튼 (G. E. Hinton) 과 세즈노우스키 (T. J. Sejnowski) [HIN84] 에 도입되었다. 볼쯔만 머신은 커넥셔니스트 (connectionist) 모델로의 최신 접근 방법이다. 이것은 홉필드 모델 [HOP82, HOP85] 의 일반화로 여겨질 수 있는데 홉필드 네트워크의 동작 규칙을 확률적인 동작 규칙으로 확장시킨 것으로 생각될 수 있다. 홉필드 네트워크의 동작 규칙에서는 네트워크의 상태를 에너지를 감소시키는 방향으로만 변화시키지만, 볼쯔만 머신에서는 에너지가 증가하는 상태의 전이에 대해서도 작은 확률로나마 허용하는 동작규칙을 사용한다.
백프로퍼게이션
네트워크를 비롯한 여러 신경망 모델들이 지역 최소점 (local minima) 에 빠져서 전역적
최소점 (global minima) 을 구할 수 없는 경우도 있는데 비하여 볼쯔만 머신에서는
에너지가 증가하는 방향으로의 전이도 가능하므로 전역적 최소값을 구할 수 있다.
이것의 원리는 마치 <그림 3> [HIN86] 에서 보는 바와 같이 구슬이 두개의 지역 최소값을
가진 에너지 장벽으로 분리되어 있는 시스템에서 상자를 흔들어 어느 곳으로도 굴러갈
수 있도록 하는 것과 같은 원리인 것이다.
<그림3> 지역 최소값에서의 탈출
볼쯔만 머신은 신경망 모델의 하나로서 커넥셔니스트 모델들의 클라스에 속한다. 볼쯔만 머신은 유니트라고 불리는 단순한 게산 요소들로 이루어진 네트워크이다. 그 유니트들은 'on' 이나 'off' 의 2 가지 상태 중 하나를 가질 수 있다. 연결들은 개별 유니트들의 상태에 국부적인 제한을 가하는 실수값의 연결 강도를 가지고 있다.
홉필드 모델과 마찬가지로 볼쯔만 머신에서의 유니트들도 이진수의 상태를 가지며 연결은 쌍방향 (bidirectional) 이다. 볼쯔만 머신은 확률적인 상태전이 (state transition) 방법을 사용하는데 비하여 홉필드 모델은 확정적인 (deterministic) 상태전이 방법을 쓰는 것이 다르다. 또한 볼쯔만 머신은 학습시에 은닉 유니트를 쓸 수도 있다. 개별 유니트들의 상태를 그들 이웃들의 상태를 조정하기 위하여 시뮬레이티드 어닐링 알고리즘에 의한 확률적인 상태전이 메카니즘이 쓰인다.
우리가 볼쯔만 머신을 학습하는 중요한 이유는 다음과 같다. 우선 이 모델은 탐사, 표현 및 학습 등에 응용될 수 있는 일반적인 접근 방법을 제시해 준다 [HIN87]. 또한 이 모델은 엄밀한 수학적인 바탕을 통하여 네트워크의 수렴 성질을 제공하며 지도학습이건 자율학습이건 간에 간단한 학습 알고리즘들을 형성할 수 있게 해 준다. 마지막으로, 이 모델의 단순성으로 인하여 실리콘 칩에 넣는 하드웨어의 구현이 비교적 쉽다는 것이다.
볼쯔만 머신에서는 연결강도의 합 ui(t) 로 부터 다음 시각의 출력 vi(t+1) 을 결정하는 이론에 계단함수 (step function) 대신 확률에 의한 판정이론을 도입했다. 즉 유니트 I 의 다음 시각에서의 출력값 vi(t+1) 이 1 이 될 확률 P 는 (식 1) 에 의해 결정된다.
ui
= 
wijvj(t) + θI
i≠j
P[vi
(t+1) = 1] = f(ji(t) / T)
f(x)
= 1/2(1 + tanh(x/2) = 
(식
1)
<그림 4> 25 개의 유니트를 가진 볼쯔만 머신의 예
여기서 변수 (parameter) T 는 네트워크 온도라 부르며, T 의 값에 따라 함수 f(x/t) 의 형태는 <그림 5> 와 같이 변화한다. T 가 크면 f(x/T) 는 x 값의 차이에 둔감해지고, T 가 무한대에 접근할 때는 x 의 값에 관계없이 f(x/T) = 0.5 가 된다. 또 T 가 작으면 f(x/T) 는 x 값이 양수, 음수에 따라 민감해지고, T 가 0 에 접근할 때에는 f(x/T) 는 계단함수 1(x) 에 수렴한다. 이 때는 ui(t) 의 값이 양수일 경우는 확률 1.0으로 vi(t+1) = 1 이 되고, 음수일 경우는 확률 1.0 으로 vi(t+1) = 0 이 되고, 음수일 경우는 확률 1.0 으로 vi(t+1) = 0 이 된다. 이러한 성질을 잘 이용하면 네트워크의 상태를 항상 에너지 함수의 최고점에 수렴시킬 수 있는 가능성이 있다.
<그림 5> T에 의한 시그모이드 함수의 변화
일반적으로 온도 T 는 높은 온도에서 출발하여 낮추어 가다가 평행상태에 도달하면 평행상태가 깨지지 않도록 서서히 온도를 낮추어 최종적으로 0 의 극한에 도달한다. 이러한 것은 금속재료 등을 가열한 후 서서히 냉각시켜 내부의 결함을 없애는 방법과 유사하여 시뮬레이티드 어닐링 (simulated annealing) 이라 부른다. 여기에서 중요한 것은 온도 T 를 낮추어가는 방법이다. 온도를 너무 급속히 낮추면 평행상태를 이루어도 최소 에너지 상태에 도달할 확률이 적고, 너무 천천히 낮추면 최소 에너지에 도달할 확률은 커지지만 많은 반복을 필요로 하므로 시간이 많이 걸린다.
스튜어트 게만 (S. German) 과 도날드 게만 (D. German) [GEM84] 형제는 1984 년에 온도 T(t) 를 (식 1) 의 조건을 만족시키면서 낮추어가면 네트워크의 상태는 반드시 최소점에 수렴한다는 것을 증명하였다.
T(t) ≥ c/log(1 + t)
여기서 t 는 시간 발전 규칙의
적용횟수, C 는 정수이다.
(식 2) 에서 주어지는 확률이 vi(t+1)
= 1 의
상태로 상태전이한 경우의 네트워크 에너지의 변화를 살펴보자. 상태전이의 전후에서
변화하는 것은 유니트 i 뿐이므로 (식 3) 으로부터 전이 전후의 에너지 변화량은
(식 4) 와 같이 주어진다.
E(t+1)
- E(t) = -{vi(t+1) - vi(t)}{
wij(t) + θi} (식
3)
i≠j
=
-{vi(t+1) - vi(t)}ui(t)
E(t+1)
- E(t) = -{1 - vi(t)}ui(t) (식
4)
(식 4) 로부터 ui(t) 가 양수인 경우는 상태전이에 의해 에너지가 감소하거나 변화하지 않는다. 이와 반대로 ui(t) 가 음수인 경우에는 상태전이에 의해 에너지가 증가하거나 변화하지 않는다. 이러한 전이는 홉필드 네트워크에서는 금지되어 있지만 볼쯔만 머신에서는 작은 확률로 허용되어 상태가 에너지 함수의 최소점에 수렴하게 된다. 즉, 홉필드 네트워크에서의 상태는 에너지 함수의 지역 최소점을 나타내는 임의의 하나의 상태에 수렴하지만, 볼쯔만 머신에서는 상태전이에 확률을 도입함으로써 하나의 상태에 수렴하기보다는 네트워크의 각 상태가 각각 결정된 확률로 출현하는 평행상태에 수렴한다. 평행상태에서의 각 상태의 출현 확률은 그 때의 상태 에너지 값으로부터 볼쯔만 분포 (Boltzmann distribution) 에 의해 주어진다. 각 상태의 에너지 값을 정하는 에너지 함수는 유니트간 연결강도나 유니트의 임계값 등의 네트워크 변수들에 의해 결정되므로 이 변수들을 적당히 조절함으로써 원하는 평행상태를 실현할 수 있다. 이처럼 원하는 평형분포를 실현할 수 있도록 네트워크의 변수들을 조절하는 것이 볼쯔만 머신의 학습이다.
볼쯔만 머신의 모든 유니트들을 가시 (visible)
유니트들과 은닉 (hidden) 유니트들의 두개의 그룹으로 나누어 가시 유니트들의 상태의
평형 분포를 원하는 확률 분포로 일치하도록 학습한다.(<그림 6> 참조). 볼쯔만
머신의 학습 방법을 두가지로 나눌 수 있는데 한가지는 학습시에 제시되는 목표 분포를
그대로 따라서 학습하는 자기상기형 방법이다. 이것은 가시 유니트들을 통하여 학습
상태를 볼 수 있으며 학습 결과로 네트워크의 변수는 외부 환경의 확률적인 구조를
갖게 된다.
<그림 6> 볼쯔만 머신의 학습 방법
(a)
자기상기형 (b) 상호상기형
또 한가지는 가시 유니트들을 입력 유니트들과 출력 유니트들의 두개의 그룹으로 나누어 입력 유니트들의 상태를 고정했을 때의 출력 유니트들의 평형 분포를 원하는 확률 분포와 일치하도록 학습하는 상호상기형 방법이다. 상호상기형 방법의 학습결과는 입력 유니트들의 상태와 출력 유니트들 상태간의 조건부 확률을 학습하게 된다. 이것은 일종의 연상기억을 실현하는데 사용될 수 있다. 예를 들면 입력 유니트들을 '바나나' 를 나타내는 패턴으로 고정했을 경우에 출력 유니트들에 '노랗다' 나 '길쭉하다' 등에 대응하는 복수의 패턴이 확률적으로 나타나면 이것은 '바나나' 로부터 '노랗다' 나 '길쭉하다' 를 연상한 것이 된다.
볼쯔만 머신은 유니트들이 그들의 상태전이를 국부적으로 평가하기 때문에 병렬처리를 쉽게 해준다 [AAR86, AAR88a, BAN86]. 더군다나 볼쯔만 머신은 전체적인 구성을 분산 표현하기 때문에 전통적인 컴퓨터 아키텍처를 사용할 때 생길 수 있는 폰 노이만의 병목 현상 (bottleneck) 을 겪지 않는다.
볼쯔만 머신에서의 병렬처리 상태전이 방법에는 여러가지 접근법이 있는데 크게 나누자면 동기성 병렬처리 (synchronous parallelism) 와 비동기성 병렬처리 (asynchronous parallelism) 로 분류된다. 볼쯔만 머신은 최적화 문제 뿐만 아니라 패턴인식에 있어서 필수적인 패턴분류에도 매우 유용하다.
볼쯔만 머신의 장점중 대규모 병렬처리와 분산된 표현은 볼쯔만 머신의 또 다른 두드러진 특징들이다. 이러한 점들은 볼쯔만 머신이 개념적으로는 단순하지만 강력한 계산 모델임을 보여주며, 시뮬레이티드 어닐링 알고리즘을 이용한 병렬처리에 적합하므로 미래의 병렬 컴퓨터의 발전 가능성을 높여주고 있다.
볼쯔만 머신의 유용한 응용분야로는 VLSI 의 배치문제나 순회판매원 문제 (traveling salesman problem), 최적화 문제의 근사해를 구하는 경우 등에 특히 적합하다.
금속의 담금질에서 아이디어를
얻은 시뮬레이티드 어닐링과 그것을 이용하여 최적화 문제 등에 유용한 볼쯔만 머신에
대하여 논하였다.
1 절에서는 머리말을,
2 절에서는 시뮬레이티드 어닐링에 관한 특징과
연구 시기 등을 기술하였으며, 3 절에서는 시뮬레이티드
어닐링의 응용을 순회판매원의 경우를 들어서 설명하였다.
4
절에서는 신경망과 시뮬레이티드 어닐링의 흥미로운 성질을 융합한 볼쯔만 머신에
관하여 살펴 보았다. 볼쯔만 머신은 VLSI 배치 문제, 순회판매원 문제 등의 최적화
문제의 근사해를 구하는데 매우 유용한 모델이다. 볼쯔만 머신의 학습 방법들에 관해서는
5 절에서 기술하였으며, 볼쯔만 머신의 특징 및
응용 분야에 관해서는 6 절에서 기술하였다.
◈ 생각할 점 ◈
1. 지역 최소점 (local minima) 과 전역적 최소점 (global minima) 은 어떻게 다른가? 홉필드 네트워크에서는 불가능한 전역적 최소점이 볼쯔만 머신에서는 구현이 가능한 이유는 무엇인가?
2. 시뮬레이티드 어닐링이 어떻게 순회판매원 문제 해결에 쓰이는지 자세하게 기술하시오.
3. 시뮬레이티드 어닐링이 전역적 최소점으로 수렴하는 데는 무한정으로 변화하는 가설에 의거했기 때문에 실제적인 상황에서는 응용에 크게 도움이 안 된다는 주장이 있다. 이에 대한 견해는?
4. 볼쯔만 머신의 학습 방법은 어떤 것들이 있으며 그 특징들은 무엇인가?
5. 조합적인 최적화 문제 (combinatorial optimization problem) 란 어떤 것들이 있으며, 이런 문제들의 해결이 그토록 어려운 이유는 무엇인가?