홉필드 네트워크 (Hopfield Network)

1. 머리말

현재의 디지털 컴퓨터는 계산하는 장치로서는 전혀 새로운 것이 아니다. 인간과 동물의 뇌와 신경시스템인 생물학적 컴퓨터는 수백만 년 전보다 훨씬 이전부터 존재했으며, 감각적인 정보를 처리하거나 동물들이 환경에 적응하는데 있어서 놀라운 효과를 발휘해 왔다. 얼굴을 인식하거나 노란 빛깔의 유자를 보고서 신 맛을 연상하는 것들은 곱셈이나 나눗셈과 같은 통상의 계산 범주를 훨씬 뛰어넘는 것이다. 이러한 생물학적 수행 능력의 효용성으로 말미암아 신경 시스템의 원리에 의거, 이와 유사한 능력을 수행할 수 있는 인공 신경망 장치들의 개발이 더욱 요구되고 있는 것이다.

홉필드 네트워크는 1982 년 미국 캘리포니아 공과대학의 물리학자인 존 홉필드 (John J.Hopfield) 에 의해 제안된 상호결합형 신경망 모델로서 연상기억이나 최적화 문제를 병렬적으로 푸는 데 많이 사용된다. 특히 연상기억에 있어서는 일정한 범용 패턴들을 연결강도로 저장하였다가 미지의 입력패턴이 주어질 때 이와 가장 유사한 패턴을 찾아낸다.

1982 년 홉필드에 의해 발표된 "Neural networks and physical systems with emergent collective computational abilities" 란 간결한 논문 [HOP82] 은 신경망 연구에 큰 영향을 끼쳤다. 그 첫 번째 이유는 홉필드가 상당히 유명한 대학 (Caltech Univ.) 및 연구 기관 (Bell Labs) 과 연관이 있는 당대의 저명한 물리학자였다는 점으로서 그의 신경망에 대한 관심과 발표된 연구 결과가 물리학계의 신경망 분야에 대한 인식을 고양시켰다. 두 번째 이유는 그가 연구에 있어 전자 장치 기술과의 연결을 피하고 물리학적 시스템과 신경망과의 밀접한 관계를 주장했기 때문이다.

과학계의 연구에 있어서 흔히 있는 일이지만 홉필드 혼자만이 이러한 생각을 한 것은 아니었다. 일본의 아마리 (Amari) 는 1972 년 신경망의 역동을 분석하는 데 있어서 일찌기 리야프노프 (Lyapunov) 함수를 강조했으며 [AMA72], 또한 많은 연구 그룹들이 신경망의 수렴 (convergence) 성질을 이해하려고 노력했다. 예를 들면 허멜 (Hummel) 과 쥬커 (Zucker) 는 1981 년에 "대칭연결 네트워크는 매우 중요하고도 특수한 경우이며, 그들의 행위는 에너지 함수에 의해 지배된다" 라는 요지의 기술적인 리포트를 하였으며 이에 관한 최종 리포트는 1983 년에 발표되었다 [HUM83].

홉필드 네트워크와 유사하면서도 두 가지 면에서 다른 모델은 마르 (David Marr) 와 포지오 (Poggio) 가 제안하였다 [MAR78]. 그러나 에너지 함수의 사용이 곧 신경망 행위를 분석하고 제어한다는 것을 여러 사람들에게 확신시킨 사람은 홉필드였다.

2. Hopfield Network

당대의 저명한 물리학자였던 Hopfield 는 물리학적 스핀 모델로부터 Hopfield network 를 착안하였으며 에너지 개념을 신경망에 처음으로 도입하였다. 그러나 Hopfield network 는 다음과 같은 2 가지의 중요한 제약을 가지고 있다.

첫 번째 제약 조건은 생물학적인 뉴런에서는 일반적으로 대칭성이 성립할 수 없기 때문에 매우 중대한 제약점이라고 할 수 있다. 두 번째 제약 조건은 각 뉴런들이 완전히 비동기적으로 작동한다는 가정하에서만 network 가 제대로 수행될 수 있다는 것으로, 만약 동기적으로 작동할 때에는 에너지가 안정된 상태에 도달하지 못할 수 있으며 무한 루프에 걸릴 수도 있다.

Hopfield network 는 뉴런의 작용을 단지 임계값의 작용으로 보고 훈련에 의한 정보가 연결강도에 의해 표현된다는 간단한 이론에 기초하고 있으며, 연상기억 (associative memory) 이나 순회판매원 문제 (Traveling Salesman Problem) 와 같은 최적화 (optimization) 문제를 해결하는데 있어 매우 유용하다. 또한 Hopfield network 는 많은 수의 비동기적이고 국소적인 계산을 통하여 전역적 최적화 (global optimization) 를 이룰 수 있다는 것이 증명되었기 때문에 더욱 많은 관심을 끌었다.

Hopfield network 는 전역적, 지역적 최적화를 수행할 뿐만 아니라 연상 기억장치 (associative memory) 로서도 효과적으로 작동한다. 연상 기억장치는 순차적 컴퓨터에서 내용 주소 기억장치 (CAM: Content Address Memory) 라고도 하는데, 기억장치에 기억된 정보에 접근하기 위하여 주소를 사용하는 것이 아니라, 기억된 정보의 일부분을 이용하여 원하는 정보가 기억된 위치를 알아낸 후 그 위치에서 나머지 정보에 접근할 수 있는 기억장치이다.

Hopfield network 의 처리 유니트들은 <그림 1> 에서 보는 바와 같이 완전연결 (fully connected) 되어 있어서 각 유니트는 다른 모든 유니트들과 서로 직접적인 연결 경로를 갖는다. 이 연결선들에는 유니트들 상호간에 관련된 연결강도가 존재한다.

<그림 1> 완전 연결된 네트워크

Hopfield network 는 자신을 제외한 모든 유니트들간의 양방향으로 상호연결된 network 인데, 초기 버전에서 입출력은 이진수, 전달함수는 계단함수 (hard limiter) 를 사용하였으나 그 후 1986년에는 입출력이 아날로그인 버전이 발표되었다. <그림 2> 는 Hopfield network 의 기본 구조를 나타내는데 x₀, x₁, x₂ ... x_N-1 은 입력된 패턴이고 x₀', x₁', x₂' ... x_N-1' 은 network 가 수렴한 상태의 출력패턴이다. 그림에서 보는 바와 같이 각 유니트는 자신을 제외한 다른 모든 유니트들과 완전연결되어 있다.

<그림 2> 홉필드 네트워크

3. 연상 기억장치 (Associative Memory)

우리 인간은 과거의 시간과 새로운 사건을 서로 연관시키고 기억된 사건들을 통합함으로써 새로운 개념을 창조해내는 능력을 가지고 있다. 예를 들면, 심한 노이즈 (noise) 를 가진 불완전한 패턴이나 왜곡된 (distorted) 패턴이 제시되었을 때, 우리는 주어진 패턴이 무엇인지를 판단하여 본래의 완전한 형태를 유추해낼 수 있다. 이러한 연상기억 능력은 경험과 학습을 통하여 점차적으로 개선되는 것이다.

Hopfield network 의 동작의 예를 <그림 3> [LIP87] 에 나타내었다.

<그림 3> 내용 주소 기억장치 (CAM) 로서의 홉필드 네트워크의 동작 예
(a) 8 개의 대표패턴들  (b) 노이즈가 있는 '3' 의 입력에 대한 출력

120 개의 노드를 가진 Hopfield network 는 14,400 개의 연결강도를 이용하여 그림의 상단에 나타낸 것과 같이 8개의 대표패턴들을 회상할 수 있도록 훈련받는다. 이와같이 검고 흰 것으로 표현되는 숫자 패턴들은 각각 120 개의 화소를 가진다. 이 network 의 입력은 검은 경우에는 +1, 흰 경우에는 -1의 값을 가진다. 여기에 제시된 예와 같이 숫자 '3' 을 나타내는 패턴의 각 비트를 0.5 의 확률로 +1 과 -1 을 임의적으로 바꾸어서 노이즈가 첨가된 입력패턴은 network 가 반복 수행됨에 따라 출력이 점차로 대표패턴과 같이 되어 가다가 6번의 반복 수행 후 숫자 '3' 을 나타내는 패턴에 수렴하였다.

광학적인 연상 기억장치는 미국의 휴즈 연구소의 버나드 소퍼 (Bernard H. Soffer) 등에 의해 실험된 것으로 <그림 4> 에 나타나 있다 [BEL86]. 제일 왼쪽의 영상은 본래의 영상이고 중간의 것은 반쪽을 가린 것이며, 제일 오른쪽의 것은 회상된 영상을 나타낸다. 출력된 영상은 반사 작용 등으로 인해 원본에 비해 덜 명확하나 상당한 근사도를 보인다.

<그림 4> 광학적인 연상기억의 예

Hopfield network 의 동작 원리를 살펴보면 다음과 같다. 입력백터 X 에 대해 출력백터 Y 를 계산하는 연상기억은 하나의 선형변환으로 볼 수 있으며 행렬 T 로써 나타낼 수 있다.

이와같은 X 와 Y 의 L 개의 쌍에 대한 변환 T 는 (식 2) 와 같이 주어진다.

(식 2)

여기서 M, N 은 각각 입력백터와 출력백터의 크기이며, L 은 저장된 패턴의 수를 나타낸다. 또 입력백터 X^t 에 대한 연상재현 (associative recall) 백터 Y^*t 는 (식 3) 으로 주어진다.

(식 3)

여기서 t 는 연상 재현코자 하는 특징 패턴을 나타낸다. 이때 입력백터 X 들이 상호직교하면 (X^s-1) X^t = 0 이므로 X^t 에 대한 연상재현은 Y^t 에 비례하게 된다. Hopfield network 에서는 이와같은 연상기억 기능을 신경망의 비선형 활성함수 (hard limiter) 및 피드백을 사용하여 향상시킨다.

N 개의 유니트로 구성되는 network 에서 시각 t 일 때 i 번째의 유니트가 다른 N-1 개의 유니트로부터 받은 신호의 총합 u_i(t) 를 (식 4) 로 나타낸다.

(식 4)

여기서 v_j(t) 는 유니트 j 의 출력으로 1 또는 0, θ_i 는 유니트 i 의 임계값, 그리고 w_ij 는 유니트간의 연결강도로 유니트 j 로부터 유니트 i 에의 전달효율을 나타낸다. 이때 (t+1)에서의 유니트 i 의 출력값 v_i(t + 1) 은 입력의 총합 u_i(t) 가 양의 값 (또는 0) 이면 1, 음의 값이면 0 으로 바뀐다. 이것은 뉴런이 다른 뉴런으로부터 신호총합이 임계값을 넘을 경우에 흥분하여 활성화되는 것을 모델화한 것이다.

Hopfield 는 이외에도 신경망의 행위가 어떤 양 (이를 에너지라 함) 을 감소시키는 방향으로 동작함을 발견하였다. 이 에너지를 사용하여 신경망의 동작을 살펴보면 신경망이 전체적으로 어떻게 변화하고 있으며, 전체로서 어떠한 정보처리 능력을 갖고 있는가를 한눈에 이해할 수 있다. Hopfield network 의 에너지 E는 (식 5) 와 같이 정의된다.

(식 5)

여기서 X_i, X_j 는 각각 유니트 i, j 의 출력값을 나타낸다. Hopfield network 의 반복연상은 각 유니트가 전체 에너지 E 를 최소화하는 데에 기여하도록 자신의 출력을 정하게 되는 과정이라 볼 수 있다.

여기서 주목할 것은 Hopfield network 에서는 학습을 하지 않는다는 것이다. 함수 E 의 모양이 연결강도 w_ij 와 정수 θ_i 에 의해 결정됨을 생각하면 지역 최소값의 분포는 이 신경망을 동작시키는 시점에서 결정된다. 그리고 어떤 초기상태에서 어떤 순서로 유니트가 동작하는가에 따라 어느 지역 최소값으로 가는가가 결정된다. 즉, <그림 5> 에서 에너지의 최소점은 A 로서, 에너지가 A에 도달했을 때 입력에 대응하는 정확한 연상 내용을 출력하게 되어 있다. 그러나 대표패턴들이 상호 직교하지 않거나 유니트의 수보다 많아 서로의 간섭이 생길 경우 B 와 같은 지역 최소점이 형성된다. 즉 초기 입력패턴이 왼쪽에 지정되면 에너지의 최소점은 결국 B 에 수렴하게 되어 A 와는 다른 내용을 연상하게 된다.

<그림 5> 홉필트 네트워크의 에너지 표면

Hopfield network 를 연상 기억장치로 사용할 때 두 가지 중요한 한계를 가지고 있다. 첫째는 저장되어 있는 패턴의 수와 정확히 회상될 (recall) 수 있는 수가 매우 제한적이라는 것이다. 즉, 너무 많은 패턴을 저장하고 있으면 수렴할 때 잘못된 패턴으로 도달할 수 있다. Hopfield network 는 대표 (exemplar) 패턴이 임의적으로 생성될 때 클래스의 수가 유니트의 수 (N) 나 입력요소 수의 0.15 배 이상일 때 문제가 되며, 일반적으로 클래스의 수가 0.15 N 이하일 때 잘 작동한다. 두 번째는 대표패턴이 다른 대표패턴과 유사하여 많은 비트들을 공유한다면 network 가 불안정해진다는 것이다. 즉 하나의 견본이 시각 0일 때 불안정하게 작용될 경우 network 는 다른 패턴으로 수렴하게 된다.

4. Hopfield network의 동작 알고리즘

[단계 1] 연결강도 w_ij를 결정한다.

for   

이 식에서는 w_ij 는 뉴런 j 로부터 뉴런 i로의 연결강도이고, x_i 는 s번째 패턴의 i번째 요소이며 +1 또는 -1의 값을 갖는다.

[단계 2] 알려지지 않은 입력패턴으로 초기화한다.

이 식에서 μ_i(0) 는 시각 0일 때 노드 i의 출력이고 또한 +1이나 -1의 값을 가질 수 있는 x_i 는 입력패턴의 i번째 요소이다.

[단계 3] 수렴할 때까지 계속 반복한다.

함수 f_h 는 hard limiting 비선형 함수이다. 이 과정은 노드 출력이 거의 변화가 없을 때까지 반복된다. 변화가 거의 없을 때 노드 출력은 알려지지 않은 입력패턴과 가장 잘 부합되는 대표패턴을 나타낸다.

[단계 4] 단계 2로 가서 수행한다.

5. 연상기억의 실험

홉필드 네트워크의 동작을 알아보기 위해 몇 개의 숫자를 이용한 문자인식을 실험하였다. 각 패턴의 크기는 10 × 10 으로 하였으며 기억패턴은 0, 1, 2, 3 의 4 가지 숫자를 사용하였다.

(1) 사용된 패턴

<그림 6> 패턴 그룹 1

<그림 7> 패턴 그룹 2

<그림 8> 패턴 그룹 3

(2) 결과 및 고찰

아래의 <그림 9> 와 <그림 10> 은 <그림 6> 의 패턴 2 에다 노이즈 (noise) 30 을 준 뒤 본래의 모양을 기억하는 것을 보인 것이다.

<그림 9> 동기적 갱신의 결과

<그림 10> 비동기적 갱신의 결과

동기적 갱신의 경우에는 주기가 2인 진동 현상이 나타나 기억이 불가능함을 볼 수 있다. 이에 반해 비동기적 갱신은 원래의 모양을 완벽하게 기억함을 보여준다. 따라서 홉필드 네트워크는 비동기적으로 동작되어야만 연상기억 장치로서의 기능을 수행할 수 있다.

(3) 각 패턴들에 대한 잡음 적응성 (Noise tolerance)

각 패턴들에 잡음을 5 씩 증가시키면서 원래의 패턴을 기억할 수 있는 한계, 즉 최대 잡음 적응성을 측정하였다.

<표 1> 패턴그룹 #1 을 사용했을 때의 패턴간의 유사도 및 잡음 적응성

패턴 1 과 패턴 2 의 '0' 노드수와 최대 잡음 적응성을 비교해 보았을 때 각각 48 일 때 31, 53 일 때 29 로서 '0' 노드수와 최대 잡음 적응성 사이에는 직선적인 함수 관계가 없으며, 에너지와 최대 잡음 적응성간에도 상관관계가 없는 것 같다.

<표 2> 패턴그룹 #2 를 사용했을 때의 패턴간의 유사도 및 잡음 적응성

패턴 2 가 원래의 패턴을 전혀 기억하지 못하는 것은 패턴 3 과 유사한 부분이 많았기 때문이다. 패턴 0 도 패턴 3 과의 유사도가 큼에도 불구하고 잡음 적응성이 큰 이유는 '0' 인 노드수가 서로 엇비슷하기 때문이다. 패턴 2 는 '0' 노드수 역시 패턴 3 에 비해 훨씬 적었기 때문에 패턴 3 에 흡수되어 버린 것이다.

<표 3> 패턴그룹 #3을 사용했을 때의 패턴간의 유사도 및 잡음 적응성

패턴 2 의 모양을 다르게 하여 패턴 3 과의 유사도를 38 에서 33 으로 줄이고 '0' 노드수를 48 에서 44 로 줄여 패턴 3 과의 차이를 더 크게 하였더니 본래의 모양을 기억해 내었다. 결론적으로 홉필드 네트워크는 기억패턴간의 유사도가 적을수록, 기억패턴의 '0' 노드수가 엇비슷할수록 보다 효과적인 기억 능력을 가짐을 알 수 있다.

6. 최적화 문제의 예 : 순회판매원 문제 (Traveling Salesman Problem)

최적화 (optimization) 문제란 여러 개의 제한 조건들을 만족시키면서 어떤 목적 함수를 최대화 또는 최소화시키는 것을 말한다. 이러한 문제들의 해결은 컴퓨터 과학, 통계학, 물리학, 공학 그리고 경영학 등에 있어서 매우 중요하며 많은 문제들이 NP-완전 (NP-complete) 문제로 귀착된다. 순회판매원 문제 (TSP: Traveling Salesman Problem) 도 대표적인 NP-완전 문제의 하나로서 순회판매원이 n 개의 도시를 단 한번씩만 방문하여 총 이동거리가 최소가 되는 경로를 찾는 문제이다.

이 문제는 매우 간단한 이론에 기초를 두고 있으면서도 도시의 수가 증가함에 따라 해결에 상당히 오랜 시간이 걸린다. 홉필드와 그의 동료 탱크 [HOP85] 는 연속적인 홉필드 네트워크를 이용하여 이 문제를 해결하려 했으며 적당한 (reasonable) 시간내에 외판원 문제의 해를 구했다.

그러나 불행하게도 실제적인 제한점은 존재한다. 홉필드 네트워크를 이용할 경우 성능이 썩 좋지는 않으며, 더구나 문제의 크기가 커질수록 성능이 더욱 떨어진다.

홉필드 네트워크로 이 문제를 설명하는데 있어서 가장 중요한 요점은 순방 (tour)을 표현하는 것이다. 순방은 0 과 1 로 표현되는 행렬이다. 10 개의 도시를 순방하는 행렬은 <그림 11> 로 표현될 수 있다.

<그림 11> 순회판매원 행렬

홉필드 네트워크는 행렬의 엔트리 숫자만큼의 처리 유니트를 필요로 한다. 그러므로 10 개 도시의 순회판매원 문제는 100 (10²) 개의 유니트를 필요로 한다. 만약 있을 수 있는 경우의 수를 모두 조사할 경우에는 대단히 많은 시간이 필요하게 된다. 가령 10 개 도시의 경우 9!/2 = 36,28,000/2 = 181,440 가지의 경우의 수가 있고, 30 개 도시일 경우에는 무려 4 × 10³⁰ 가지의 경우의 수가 존재한다. 그러므로 디지털 컴퓨터로 이 문제를 풀려고 할 경우 도시의 숫자가 커짐에 따라 경우의 수도 기하급수적으로 커지기 때문에 문제의 해결이 거의 불가능하다. 이 문제의 목표는 100 개의 유니트를 가진 네트워크가 수렴하여 순방을 나타내는 좋은 행렬값을 구하는 것이다.

순회판매원 문제에 있어서 두 번째 중요한 요소는 에너지 식이다. 에너지 함수는 다음의 문제들을 지키면서 만들어져야 한다.

위의 4 가지 조건들을 모두 만족하는 에너지 함수를 만들기는 매우 복잡하다. <그림 12> [DAY90] 는 순회판매원 문제의 해답을 보여 주는데 (a)에서 (c) 까지는 네트워크 처리의 중간 결과를 보여주고 (d) 는 네트워크의 최종상태를 나타낸다. (e) 도 네트워크 처리의 중간 결과를 보여주는데, 순회판매원이 순방할 루트를 보여 준다. (f) 는 최종적인 결과를 나타내는데 상당히 좋은 결과를 보여 준다.

<그림 12> 순회판매원 문제

홉필드 네트워크는 10 개 이하의 도시를 대상으로 해야 하고, 그 이상일 경우에 국부적인 최적값을 얻게 되는 문제점을 내포하고 있다.

7. 장점과 제한점

연상 기억장치로 쓰이거나 최적화 문제 해결에 있어서의 응용 문제들은 네트워크가 최소의 에너지를 가지게 되는 안정된 상태일 때 해결된다. 이러한 접근 방법은 이 모델이 처음 제안되었을 당시에는 매우 파격적인 것으로 여겨졌다.

홉필드는 네트워크의 응용 분야에 있어서는 불행하게도 네트워크의 성능이 많이 제한되어 있다. 연상기억은 제한된 용량과 제한된 연상 능력을 보여 주고 있다. 외판원 문제의 최적화 문제도 몇 개의 제한된 해답을 제시하고 있으며 10 개 이상 도시의 경우 잘 작동하지 않는다. 그럼에도 불구하고 홉필드 네트워크는 신경망에 의해 해결 가능한 문제들에 매우 밝은 희망을 주고 있다. 그러나 실세계의 문제들을 다루는 데는 보다 성능이 월등한 네트워크가 필요하다.

홉필드는 홉필드 네트워크를 신호 분해 (Signal decomposition) 와 선형 프로그래밍 (Linear Programming) 과 같은 최적화 문제를 푸는데 사용하였다. 작업 스케쥴링 (Job scheduling) 최적화 문제는 홉필드 모델과 유사한 푸우 (Foo) 와 다케우치 (Takefuji) 모델 [FOO88] 에 의해 제한적인 영역에서 해결되었지만 일반적인 해결책은 아니다. 홉필드 네트워크의 광학적 구현은 파랏 (Farhat) 등에 구현되었다 [FAR85].

홉필드 네트워크의 비동기적인 연결강도 변화는 매우 독특한 성질이며, 신경세포가 비동기적인 갱신을 함에 비추어서 생물학적인 시스템 연구에 매우 밀접한 관련이 있다. 홉필드 네트워크와 그 유형의 네트워크들은 음성처리, 데이터베이스 검색, 영상처리 그리고 패턴분류 등에도 응용될 수 있다.

홉필드 네트워크를 이용하여 최적화 문제를 해결하려 할 때 문제점 중의 하나는 최적값에 대한 보장이다. 우리는 네트워크가 안정된 상태에서 얻는 값이 근사값이 아니라 최적값인지를 구분할 수 없다. 홉필드 네트워크의 가장 일반적인 장점은 그것의 근본적인 병렬처리 구조에 있다. 그러므로 하드웨어 수행이 매우 빠를 것이나 네트워크의 크기나 속도 및 응용 분야에 따라 달라진다.

8. 결어

이 장에서는 1982 년 홉필드에 의해 제안된 상호결합형 신경망 모델인 홉필드 네트워크를 살펴 보았다. 홉필드 네트워크는 연상기억이나 최적화 문제 등의 해결에 적합한 모델이다.

1 절에서는 홉필드 네트워크의 생성 배경을 비롯한 일반적인 기술을 하였으며, 2 절에서는 홉필드 네트워크의 두가지 중요한 제한점을 살펴보고, 완전연결된 네트워크의 구조를 고찰하였다.

3 절에서는 연상 기억장치와 관련된 설명과 더불어 숫자에 대한 실험과 광학적인 실험을 살펴 보았고, 수식을 통하여 홉필드 네트워크의 동작 원리를 설명하였으며, 연상 기억장치로서의 홉필드 네트워크의 두가지 중요한 한계점을 설명하였다.

4 절에서는 홉필드 네트워크의 동작 알고리즘을 서술하였고, 5 절에서는 홉필드 네트워크의 동작을 확인하기 위해 몇 개의 숫자에 대한 연상기억 능력을 실험하였으며, 그 결과에 대해 간략히 분석하였다.

6 절에서는 최적화 문제의 한가지 예인 '순회판매원 문제' 를 홉필드 네트워크를 이용하여 푸는 과정을 살펴 보았으며, 7 절에서는 홉필드 네트워크의 장점과 제한점들을 기술하였다.