Hopfield Nets and Auto Associators/Lec.15

Hopfield Net

 

Hopfiled network는 위처럼 어떤 뉴런의 output이 동시에 어떤 뉴런에 영향을 주는 것을 이야기한다. 위의 네트워크는 각각의 퍼셉트론이 +1/-1의 output을 가지고있다. 매 시간 마다 뉴런은 "filed"라고 하는 를 받아서 그것의 부호가 현재 자기의 부호와 일치하면 반응이 없고 다르다면 'flip'을 해서 그 field와 부호를 일치시킨다. 이 관계는 아래와 같다.

예를들어

위의 관계에서 노란색 node가 -1, 검정색 node가 +1이고 빨간색 edge가 +1, 파란색 edge가 -1일때 위에 표시한것처럼 wy가 -1이되어 검정색 노드가 +에서 그 부호와 맞추기 위해 -가 된다.

이 과정을 반복하면

이런식으로 반복된다. 그렇다면 이러한게 영원히 반복될까? 결론부터 말하자면 아니다. 이를 증명해보자. 

이러한 네트워크에서 가 현재 field가 들어오기 전의 output이고 가 field가 들어와서 반응한 후의 output이라고 하자. 만약 라면 즉 , 부호가 안바뀌었다면 filp하지 않고 아래의 식을 얻을 수 있다.

그 반대의 경우에서는 라면 인 것이고 flip일 일어나면서 아래의 식을 얻을 수 있다.

그리고 이값은 만약 y-가 양수라면 y+는 음수이므로 음수*음수=양수, y+가 음수라면 y+는 음수여서 음수*음수 임으로 항상 양수이다. 따라서 field가 들어온후에서 들어오기전의 값을 뺀 것이 양수임으로 이는 flip을 한다면 항상 그 뉴런의 값이 증가한다는 것을 의미한다. 이는 가 flip할떄마다 증가한다는 것이다. 

이제 모든 노드에 대해서 살펴보자. 모든 노드를 더한 것을 D라고 하고 그 식은 아래와 같다.

그리고 이 노드들중 어느 하나가 flip을 했다고 하면 flip전과 후의 D의 차는 아래와 같다.

어차피 여기서 를 제외한 나머지 부분은 같기때문에 그 차가 0이고 flip된 부분만 보면 아래의 식을 얻을 수 있다.

그리고 이것은 위에서 보았듯이 flup할때는 항상 양수이다. 즉 flip을 할때마다 D의 값은 증가한다는 것이다. 하지만 D의 값은 그 범위가 정해져있는데 왜냐하면 D를 이루고 있는 w와 b는 항상 일정하기 떄문이다. 즉 D의 최대값은 아래의 경우이고

의 최솟값은 flip이 가장 적게 일어날 때인 아래의 경우이다.

결국 언젠가는 가 양수이기에 점점 에 다가가서 더이상 증가하지 못하고 그로 인해 flip을 할 수 없어질 것이다.

이 D의 음수를 네트워크의 에너지라고 하고 그 표현은 아래와 같다.

그리고 위에서 본것처럼 D는 계속 증가하기에 flip을 할 수록 hopfield network의 에너지를 점점 줄인다. 

 

Content-Aaddressable Memory

그렇다면 이 에너지는 갑자기 어디서부터 온 것 일까? 이는 물리학에서부터 왔다.

위와 같은 쌍극자(diapole)이 있다고 하자. 이 diapole은 local field에 맞추어서 변한다. 예를들어 diapole이 local field와 맞춰져있지 않으면 flip을 해서 맞추는 것이다. 그런데 이 local field는 모든 diapole에 대한 중간값이다. 그래서 하나의 diapole이 flip하면 이 local field가 바뀌어져 다른 diapole이 flip하게 된다. 그래서 이 전체 diapole의 값을 아래의 식으로 표현할 수 있다.

여기서 p는 i번째 diapole에 대한 벡터값이다. 위에 식에 따르면 diapole의 값은 J 즉 field에 의해 결정된다. 그리고 이 값에 반응하여 아래 처럼 diapole이 바뀌는 것이다.

그리고 위의 Hopfiled network에서와 같이 이 flipping은 언젠가 멈추게 된다. 이 시스템의 전체 에너지의 식은 아래와 같다.

그리고 이 시스템은 에너지가 감소하는 방향으로 나아간다.

즉 위의 경우 오른쪽으로 나아가며 에너지를 줄이는 방향으로 나아가는 것이다. 그리고 바닥을 찍고 멈춘다. 더이상 에너지를 줄일 수 없기 때문이다. 하지만 만약 여기서 조금의 변화가 생겨 이 diapole이 flip하게 되면 어떻게 될까? 왼쪽으로 다시 올라가며 원래 위치에 정확히 다시 돌아간다. 그리고 다른 diapole이 local minimum을 향하게 된다. 

 

이제 이를 Hopfield에 적용해보자. 우선 hopfield의 에너지는 아래와 같다.

위의 diapole과 매우 유사하다. 그리고 이 에너지가 local minimum일때까지 계속 진행된다. 위의 식에서 b는 weight에 뉴런하나를 추가하는 식으로 없에고 시그마의 조건을 j<i로 바꾸어서 절반의 상태만 보려고 한다. 어차피 이래도 에너지가 local minimum쪽으로 가려하는 것은 변함이 없다.

아래의 그림을 다시 살펴보자.

여기서 저 주황색 공은 역시 local minimum으로 떨어질 것이다. 하지만 이 네트워크에서는 또다른 의미를 가지고 있다. 각각의 minima는 저장된 패턴을 이야기한다. 즉 각각의 뉴런은 저 저장된 패턴쪽으로 다가갈수록 점점 패턴이 명확해지는 것이다. 이를 "Content Addressable Memory" 또는 "Associative Memory"라고 한다. 

 

그러면 진행과정을 살펴보자.

위의 그물같은게 energy contour라고 하면 네트워크는 이 에너지가 낮은 방향으로 진행될 것이다. 그리고 이 방향이 위로 올라갔다 내려갔다하는 것이 아닌 flipping할때마다 에너지가 낮아짐을 보였음으로 monotic하게 에너지가 낮아질 것이다. 

여기서 activation function에 따라 달라지는 것이 있는데 만일 threshold activation을 사용했다면 가능한 경우는 이고 따라서 모든 경우가 되지 않고 저 격자에서만 표시할 수 있을 것이다. 반면에 tanh를 사용한 경우 tanh가 [-1 1]의 범위를 가짐으로 에너지도 continuous해질 것이다. 

 

그렇다면 Energy conotur를 2 뉴런 네트워크에서 살펴보자. 먼저 에너지를 벡터형식으로 표현하면 가 된다. 절반인 이유는 위에서 i<j로 절반만 표현했기 떄문이다. 그렇다면 이 결과는 아래와 같다. 

여기서 대칭인 이유가 위의 벡터식에서 y에 -를 붙이면 이다. 따라서 이말은 y가 minimum이면 -y도 mimmum이라는 것이고 그래서 -부분과 +부분이 대칭으로 나온 것이다. 

 

Remember Specific Pattern

이제 실제로 특정 패턴을 기억시키는 과정을 보자. 만약 N개의 픽셀로 이루어져있으면 N개의 뉴런이 필요할 것이다. 그리고 Hopfield 네트워크로 이루어져있음으로 모든 뉴런은 각각 다른 모든 뉴런에 연결되어 있을 것이고 여기서는 weight들이 모두 symmetic하다고 한다. 

위에 energy contour에서 보았듯이 어떠한 패턴 P를 저장하면 -P 같이 저장된다. 에너지가 symmetric하기 때문이다. 또한

모든 stable한 곳이 저장된 패턴이기에 여러개의 패턴을 저장하게 네트워크를 구성할 수 있다. 물론 이때 각각의 패턴은 positive pattern과 negative pattern을 지니고 있는 것이다. 패턴을 저장한다는 것은 두가지의 성질을 지니고 있는 것이다. 하나는 stable이고 하나는 stationary이다.  우리가 어떠한 패턴을 저장하는 네트워크를 만들려면 일때 우리가 원하는 패턴인 에서 local minimum을 가져야 한다. 이렇게 되면 모든 뉴런이 flip을 안하게되고 local field에 정렬된다. 이를 패턴이 stable하다고 한다. 그리고 우리는 패턴을 저장하려면 flip이 안되게 이여야 한다. flip이 되더라도 다시 돌아오게 된다. 이떄를 stationary 패턴이라고 한다. 그리고 우리는 우선 이를위해 Hebbian learning을 사용할 것이다. 이는 모든 weight가 두개의 뉴런의 곱인 형태이다.

패턴이 stationary일떄를 잠시 살펴보면 아래의 수식을 만들 수 있다.

이는 원래 의 부호에 따라 현재 뉴런의 값인 가 flip하든지 가만히 있든지 하는데 이 두 부호가 같으니 어떠한 뉴런도 flip하지 않을 것이라는 것이 보장된다.

그리고 이 Hebbian learning을 에너지 관점에서 보면

가 나오게 되고 이는 이 값이 네트워크에서 lowest possible energy라는 것이다. 

 

이제 4bit의 패턴을 저장한 결과를 살펴보자.

왼쪽이 패턴이 저장되어있는 모습이고 오른쪽은 그에대한 에너지 맵이다. 왼쪽의 패턴이 저장된 곳에 가장 낮은 에너지를 가짐을 볼 수 있다. 또한 왼쪽위에 negative pattern도 존재함을 볼 수 있다. 하지만 이것의 문제점은 복원할 때 어느 부분이 복원될지를 모른 다는 것이다. 

 

이제 여러개의 패턴을 저장하는 것을 살펴보자. 마찬가지로 hebbian learning을 사용함으로

의 식을 만족하고 여기서 {yp}는 저장된 패턴들의 set를 이야기한다.

그렇다면 얼마나 많은 패턴들을 저장할 수 있을까? 우선 식들을 다시 써보면 K번째 패턴을 N bit에 저장한것은 다음과 같고

hebbian learning에 의한 weight는 아래와 같다. 여기서 normalization을 위해 N으로 나누어 주었다.

여기서 어떤 패턴인 가 stable하려면 flip이 안되야 함으로 원래 뉴런과 계산된 뉴런의 부호가 같아야 한다. 부호가 같으면 곱해도 항상 양수임으로

이어야 한다. 이 w에 위에서 구한 normalized 된 식을 넣어주면 아래를 구할 수 있다.

이 식을 두개로 나누어 보면

이다. 첫번째 식은 p에서의 패턴이고 이는 위에서 한개의 패턴을 저장할때에서 보았듯이 항상 +1이다. 두번째 식은 모든 나머지 패턴들이고 이것은 첫번째항에 대한 noise가 된다. 이를 corsstalk term이라고 하며 statinoary가 안될려면 여기가 -1보다 작아 두 식을 더했을 때 음수가 나와야 하는 것이다. 즉

위의 조건인 crosstalk term이 -1보다 작을때는 패턴이 저장되지 못 할 것이다. 위의 crosstalk term을 라고 하자, 그러면 우리가 k개의 랜덤 패턴을 저장하려 할때, 패턴의 저장 성공 유무는 가 -1보다 떨어질 가능성에 달려있는 것이다. 만일 여기서 N과 K를 늘린다면 이 확률은 가우스 정규분포에 다가가게 된다.(평균은 0, 분산은 K/N). 그리고 이 분포에서 C가 -1보다 작을 확률은 아래와 같다.

이것은 0.4%의 이하로 stable 하지 않을 경우가 나오게 하려면 K<0.14N이어야 한다는 것이다. 만일 K>0.14N이 된다면 점점 커질수록 패턴을 저장할 확률이 낮아지며 결국은 아무것도 기억하지 못하는 경우가 나온다. 즉, hebbian learning으로 훈련되는 N개의 뉴런을 가진 네트워크는 낮은 확률의 에러를 가질려면 0.14N개의 패턴까지 기억할 수 있는 것이다. 

 

이제 이 패턴들의 관계를 파악해보자. 각각의 패턴은 0또는 1로 이루어져있기때문에 hypercube로 나타낼 수 있다. 간단히 3차원의 cube로 나타내보자.

빨간점에 패턴이 저장되면 symmetric하기때문에 파란점에도 negative pattern이 저장될 것이다. 그렇다면 새로운 패턴을 여기에 저장하려면 어떻게 해야할까? 이 두패턴에 가장 멀리 떨어진 곳에 저장을 해야할것이다. 그래야지 flipping할때 충동일 안일어나면서 다른패턴과 안섞일 것이다. 이때 N개의 비트로 이루어져있다면 이것과 가장 멀리떨어진것은 한패턴과 N/2개가 다를 때일 것이다. N개 비트 다 다를때는 원래 패턴의 negative pattern이기때문에 symmetirc을 고려했기 때문이다. 

그렇다면 이 때의 두 패턴을 곱하면 어떤것이나올까? N개의 비트중 N/2개는 +1, 나머지 N/2개는 -1이기에 합이 0이 나오고 이기때문에 이 두개의 패턴은 orthogonal하다고 할 수 있다. 이것은 N이 짝수일때의 경우이고 홀수라면 즉 이고 L이 홀수라면 이때는 아까와 다르게 홀수여서 N/2를 생각할 필요가 없어지고 개의 orthogonal한 패턴이 만들어 질 것이다. 하지만 실제로는 다르다.

 

그렇다면 2개의 orthogonal 4-bit pattern을 보자.

[1,1,-1,-1]과 [1,1,1,1]은 4/2개의 비트가 다르고 곱하면 0이됨으로 orthogonal이다. 그리고 이것에대한 에너지를 보면 어떤것을 복원할지 애매하다. 모든 저장된 패턴이 local minima여서 어디로 갈지 모르는 것이다. 

하지만 non orthogonal일때를 보자.

오히려 이때 어떤것을 recall할지 명확하게 보인다. 따라서 각 비트끼리 maximally distant가 아닐때 오히려 더 복원하기 쉬운 것이다. 이번에는 3개의 패턴을 보자. 아래는 orthogonal일때이다.

여기서 다시 복원한다면 랜덤하게 아무거나 나올 것이다. 하지만 non-orthogonal하다면

비교적 명확히 보인다. 3개의 패턴중 하나는 명확히 복원할 수 있는 것이다. 여기서는 좌하단과 좌상단 패턴은 flip하다보면 결국 중앙의 패턴으로 복원될 것이다. 

이번에는 6비트짜리를 살펴보자.

패턴이 완벽하게 stationary하고 stable하다 하지만 몇개의 fake 메모리들이 보인다.

이거는 2개의 orthogonal 패턴인데 stationary하고 stable하다. 하지만 중간에 fake memory가 보이는데 초록색부분으로 빠지게 되면 그 주변이 같은 에너지여서 다른 부분으로 빠질 수 가 없다. non orthogonal일때는

위에 경우보다는 fake memory가 덜 생긴 것을 볼 수 있다. 

 

이렇게 실제로는 0.14N보다 많은 패턴들을 저장할 수 있고 많은 의도하지 않은 패턴들이 나타나는 것을 볼 수 있다. 이런 의도하지 않은 패턴은 어디서 나온 것일까? 이것은 hebbian rule에서 어쩔 수 없이 나온 것이다. hebbian rule에서 weight들이 각 뉴런들의 filed에 대한 곱의 평균인데 이것들이 다시 패턴으로 저장되서 나오는 것이다.

 

결론을 이야기하자면 K>0.14N개의 패턴을 저장할 수 있다. 그리고 이러한 패턴들중 적어도 하나는 stable and stationary해 올바르게 복원이 가능하다. 또한 non-orthogonal이 더 기억하기 쉽다. 

 

 

 

 

 

 

이 자료는 제가 강의들은 것을 바탕으로 복습겸 정리한 것입니다. 틀린부분이있으면 지적해주세요!

출처 : www.youtube.com/watch?v=3Cp_pjPRmt8&list=PLp-0K3kfddPwz13VqV1PaMXF6V6dYdEsj&index=21&t=2672s