Hopfield Nets and Boltzmann Machines/Lec.16

이제 전 강의에서 배웠던 모호한 것들을 명확히 이해해보자. 우선 몇가지 수기을 정리해보자. 먼저 Hebbian learning은

이다. 그리고 이떄 W를 매트리긋로 표현하면 다음과 같다.

간단히 증명해보자면

이 이유때문이다. 위는 하나의 패턴에 대한 w이고 여러개의 패턴에 대해서는

이기때문에 아래와 같다.

이제 이 W를 에너지식에 넣어보자. 에너지의 식은 이고 여기에 위의 W를 대입하면

이다. 여기서 는 어차피 y는 +1,-1로 이루어져있고 이 inner product는 각각의 element의 제곱의 합임으로 결국 element의 수와 같다. 이를 N이라고 두면

가 나온다. 여기서 첫쨰항은 을 weight로 사용한 에너지의 값이고 두번째 항은 위에서 정의한 full weight를 사용시의 에너지 이다. 그리고 이것은 element의 수에만 dependet하다. 그래서 계산을 위해서 앞으로 W를 그냥 으로 정의하려 한다.

이렇게 해도 문제 없는 것을 eigen vector의 관점에서 보자. eigen vector의 식은 이다. 여기서 w대신에 full weight와 우리가 아까 다시 정의한 w를 각각 넣어보면 과 이다. 따라서 이것은 eigen vector는 같고 eigen value만 다른 것을 의미한다. 그래서 다시 정의한 w를 사용해도 무방하다. 그리고 여기서 eigen vector가 모두 양수 또는 0이다. 

에너지식을 다시보면 이것은 quadratic이고 w가 양수이기에 오목한 모양을 가진다. 따라서 등고선은 아래의 모양을 가질 것이다.

그런데 우리가 선택하는 모든 element들은 +1 또는 -1이다. 따라서 위에서 정한 hyper cube에서 노란색의 꼭지점에서만 값을 가질 것이다. 그리고 전 강의에서 배운 symmetric한 성질때문에 하나의 패턴을 정하면 자동적으로 그 반대의 패턴도 저장될 것이다. 이것을 아래 3차원 hypercube에서 자세히 살펴보자.

여기서 노락색 두개의 패턴을 저장했더니 negative pattern도 역시 같지 저장되었다. 그리고 이 패턴을 ghost라고 한다. 여기서 만일 왼쪽 위의 노란색 패턴을 flip했다 생각해보자. 그러면

3개의 y중 하나가 -1로 바뀌어서 1,2,3중하나로 갈 것이다. 만일 1로 flip된다면 문제가 생기는게 1은 다른 하나의 패턴의 ghost이고 이렇게 되면 메모리가 corrupted된다. 그래서 서로 멀리 떨어트려 놓아야 하는 것이고 N개의 y가 다 다르면 가장 멀리 떨어진 것이라 생각할 수 있는데 symmetric때문에 N/2개가 다른 것이 가장 멀리 떨어져 있는 것이다. 

 

이제 네트워크가 evolve되는 과정을 살펴보자.

위는 hypercube이고 2개의 뉴런이 있는 네트워크의 경우이다. 검정색 화살표가 initial인데 evolve가 된다면 여기에 w가 곱해져서 1로 갈 것이다. 그리고 y=sign(wy)에 의하여 그 벡터에 가장 가까운 꼭지점으로 옮겨진다. 이렇게 flip이 되는데 만일 evolve가 되었는데 주황색 화살표처럼 같은 부분에 있으면 y=sign(wy)해도 같은 꼭지점으로 가지게 된다. 이렇게 되면 flip이 안되는 것이다. 그렇다면 언제 패턴이 저장이 되는 것일까? 주황색의 경우처럼 w를 곱해도 자기 자신으로 evolve됬을때 일것이다. 이럴떄는 아래의 식 처럼

가 W의 eigenvector일떄일 것이다. 물론 W의 eigenvalue는 양수이다.

 

이번에는 두개이상의 패턴을 저장해보자. 우선 주어진 것은 의 패턴이고 W는 모든 y에 대하여 인 W가 필요하다. 먼저 K개의 orthogonal pattern을 저장해보자. 위에서 말한 것 처럼 가장 간단한 방법은 eigen vector을 이용하는 것이다. 각각의 y가 W의 eigen vector면 된다. 즉 일 때 이면 되는 것이다. 여기서 만일 eigen value가 모두 1이라면 이것은 hebbian rule일 것이다. 그렇다면 이 W을 이용해 evolve를 해보자.

임으로 W에 어떤 패턴을 곱하면 결국 다시 자기 자신이 나오게 된다. 하지만 이것의 의미는 모든 패턴이 stable하다는 것이고 모든 것을 기억함으로 recover을 어떤 것을 하기 애매해진다. 그럼으로 compeltely useless network라고 할 수 있다. 

이것은 W의 eigen value가 다 같기에 생기는 일이다. 만일 eigen value가 다 다르다면 어떻게 될까? 

위의 결과가 나오게 된다. evolve하면 자기자신으로 무조건 가는 것이 아니다. 다른 어딘가로 보낼 수 있는 것이다. 그리고 이는 전부다 stable한 것은 아니라는 것을 보인다. 이것이 우리가 원하는 결과이다. 

Non-orthogonal일때를 보면

이렇게 evolve때마다 서로다른 패턴이 나오게 되면서 모든것이 stable하지 않게 된다. 그리고 eigen value가 다르게 아노는데 어느 부분이 분명 다른 value보다 클 것이다. 이렇게 한 value가 크게 되면 

이렇게 하나의 패턴으로 결국 모이게 된다. 

 

Optimization

이제 energy function을 보자. 에너지의 식은 아래와 같다.

그리고 이 값은 target pattern에 대해서는 maximally low해야하고 그 이외의 pattern에 대해서는 maximally high해야 한다. 그래야지 그 이외의 패턴들이 unstable해져서 target pattern으로 evolve하게 된다. 그러면 그냥 total energy of target pettern을 줄이면 되지 않을까? 하는데 이렇게 되면 아래의 문제가 생긴다.

모든 값들이 내려가게 되서 우리가 원하지 않는 target이 아닌 패턴도 minimize된다. 이렇게 되면 optimize가 된게 아니다. 따라서 우리는 target이 아닌 패턴은 maximize해야한다. 즉 아래의 update과정을 거치는 것이다.

target y의 에너지는 더해주고 target이 아닌 곳은 빼주면 결과적으로 원하는 부분만 minimize되는 것이다. 이기에 gradient descent같은 방법을 이용하면 아래의 식을 얻을 수 있다.

이것을 하나하나 뜯어보면 첫번째 summation은

target pattern을 minimize하고 두번쨰 summation은

그 이외의 모든 것을 maximize한다. 하지만 이것은 현실적으로 계산할 양이 너무 많다. 그래서 valley만 올리는 방법을 택한다.

valley를 올리면 결국은 target쪽이 내려가게 될것이다. 그렇다면 이 valley를 어떻게 알아낼까? 이것은 evolve해보면 된다. 랜덤한 어떤 것을 evolve하면 이것은 valley쪽으로 갈것이다. 이것을 계속 반복하면 모든 valley를 알 수 있는 것이다. 하지만 이방법 역시 비효율적이다. target과 멀리있는 valley는 사실 그리 중요하지 않기 때문이다. 그래서 target 근처의 valley를 찾을 것이다.

이는 target에서 evolve를 해서 얻어낼 수 있다.

그리고 이것에 관한 update식은 아래와 같다.

하지만 이것의 문제는 아래처럼

여러개의 target이 하나의 valley를 공유할때 문제이다. 이렇게 되면 오히려 잘 update된 것을 망칠 수 있게 된다. 그래서 이를 해결하기 위해 valley도 아닌 그냥 target 근처의 neighborhood를 올ㄹ리기로 한다.

즉 target pattern으로 부터 시작해서 few step만 간뒤 그 부분을 올리는 것이다. 이렇게하면 모든 문제를 해결 할 수 있다. 좀더 효율적으로 하기 위해 여기에 SGD의 개념을 추가하면 더 좋다. 

 

결국 optimize를 위해서는 W를 initialize한 뒤에 target pattern중 하나 샘플을 정한다. 그리고 그것을 몇 step evolve시킨다. 그리고 그것에 따라 아래처럼 update한다.

 

 

 

 

 

 

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

출처 : www.youtube.com/watch?v=ZnB8MMjg1mA&list=PLp-0K3kfddPwz13VqV1PaMXF6V6dYdEsj&index=22