우와 오랜만에 포스팅이다. 포스팅하면 좋은 것이... 할 때는 귀찮아도 나중에 오랫동안 생각 안해서 까먹고 있어도 되세길 거리가 있다는 것이 좋다. 그것도 내가 쓴 것이라 눈에 더 잘 들어온다는 장점도 있고. 아무튼!! 포스팅해보자.

오늘은 Self Organizing Map에 대해서 이야기하련다. SOM이라고 부른다. 우리가 기본적으로 Artificial Neural Network하면 Clustering보다는 Classification이 먼저 떠오른다. Artificial Neural Network를 이용해서도 Clustering을 할 수 있는데 그것이 SOM이다. SOM을 이용하면 high-dimension data를 low-dimension data로(1D, 2D, 또는 3D)표현할 수도 있는데 이는 포스팅을 읽으면 자연스렇게 알게 될 것이다.

우선 이해하기 쉽게 이렇게 설명해보자. 아래와 같이 농구골대가 여러개 있다고 해보자.

A선수는 슛을 쏠 때 슛이 길고 왼쪽으로 치우치는 경향이 있어서 보통 n1, n2골대에 공이 들어간다. 

반면, B선수는 슛이 짧고 오른쪽으로 치우치는 경향이 있어서 n15, n16 골대에 많이 들어간다. 

이제 A와 B선수 둘 중 아무나 랜덤으로 공을 던지고 우리는 누가 던졌는지 알아맞추기 놀이를 해보자. 한 사람이 10번 던졌는데 그 중 9번이 n1, n2 골대에 들어갔다. 누가 던졌을까? A가 던졌을 것이다. n1, n2는 A의 영역이니까. 

이런식으로 Clustering을 하는 것이다. 이제 조금더 이론적으로 이야기해보자. 우선 neuron을(농구골대) N개 만들어두자. 그리고 우리가 D개의 data가 있다고 해보자. 그 중에 sample로 몇개를(s개) 뽑아서 모든 neuron의 거리를 젤 것이다. 하나의 data에 대하여 모든 neuron간의 거리이다. (반대로 혼동하지 말자.) 그림으로 표현하면 아래와 같다.

data와 neuron 사이의 거리는 더 자세하게 말하면 data와 neuron의 weight 간의 거리이다. 각각의 neuron이 weight을 가지고 있는데 그 weight과 data간의 거리를 구한다는 말이다. 거리를 구하는 공식은 일반적으로 euclidean distance를 많이 쓰는데, 이 말은 data와 neuron의 weight은 같은 dimension을 가지고 있다는 뜻이다. 그렇다!! SOM에서 data와 neuron의 weight은 같은 dimension을 가져야 한다. 거리를 구해야 하기 때문이다. 하나의 데이터 d1과 모든 neuron의 weight 사이의 거리를 구하면 아래와 같이 나온다고 해보자. 우리는 그 중에서 제일 가까운 neuron만 update해줄 것이다. 이렇게 제일 가까운 neuron을 Best Matching Unit(BMU)라고 부른다.

BMU를 update 해주는 공식은 어디서 많이 본 공식이다. 이거는 Artificial Neural Network에서 각각의 weight이 update될 때 사용되는 공식이다. 

지금까지의 과정을 모든 sample S개에 대해서 반복을 하고 또 다시 Sample집단을 뽑아서 위의 과정을 계속 반복하는 것이 SOM이 training되는 방식이다.

여기에서 한 가지 이야기 안한 것이 있다면, neighbor에 대한 이야기이다. 하나의 data에 대하여 모든 neuron 간의 거리를 구하여 BMU를 구한 상황에서 BMU 하나만 update 시킨다고 했었는데, 사실 BMU의 neighbor들도 같이 update 해줘야 된다.

BMU의 neighbor은 말 그대로 neighbor이다. neuron이 아래와 같이 1차원으로 줄 지어져 있으면 neighbor은 양쪽 옆의 neuron들이고

neuron이 2차원으로 줄 지어져있으면 neighbor은 상하좌우 neuron들이다.

neighbor을 training시켜주는 공식은 위에서 설명한 update 공식과 같은데, 한가지 추가하자면 neighbor이니까 살짝 덜 update시키기 위해서 특정 공식을 아래와 같이 곱해준다.

위 공식은 각자 찾아보는 것으로 하자. 위 공식을 통해서 neighbor들이 살짝 덜 update된다는 것만 알면 된다. 폭탄이 터지면 그 주변부의 피해가 덜 하다는 것과 비슷한 논리다.

이 포스팅 시작할 때 SOM의 장점 중 하나가 high dimension data를 low dimension data로 변환해주는 것이라고 했다. 이제 이 말이 무슨 말인지 알 것이다. 정확히 말하면 변환해주는 것이 아니라, 각각의 data가 어떤 neuron과 가장 가까운지를 영역상으로 counting해준 것 뿐이다. low dimension에서의 low의 의미는 neuron들이 1D로 배열되어있으면 1D로(low), 2D로 배열되어있으면 2D로(low) counting 해준다는 것이다.

위의 사진에서 보면 몇몇 neuron들이 다른 neuron들보다 높게 솟아있다. 주어진 input data(high dimension)을 각각의 neuron과 거리를 비교하고 제일 가까운 neuron를 찾아서 그 neuron을 한칸 한칸 쌓아 올리는 것이다. 이런 의미에서의 high to low dimension transformation이다.

Clustering에서 중요한 것 중에 하나가 Visualization이다. SOM을 visualization하는 여러가지 방법이 있는데, 그 중에서 가장 많이 쓰이는 것이 u-matrix이다. unified distance matrix의 약자이다. u-matrix는 neighbor neuron들간의 거리를(정확히 말하면 각 neuron의 weight들 간의 거리) 측정하여 서로 거리가 멀면 밝은 색깔로, 서로 거리가 가까우면 어두운 색깔로 나타내는 것이다. 

위의 그림에서 우리는 3개의 cluster를 찾을 수 있다. 왼쪽 하단에 빨간 동그라미 하나, 오른쪽 하단에 초록 네모 하나 그리고 완전 오른쪽 하단에 파란 다이아 하나. 이렇게 3개이다. 그런데 왼쪽 상단부분이 아주 밝은 것을 볼 수 있다. 그 부분의 neuron들이 거리가 길다는 것이다. 따라서 이상적으로는 아래와 같이 clustering되면 아주 좋겠다.

실제로 c1과 c2영역에 data가 있어서 그렇게 나눠지면 아주 이상적인 clustering이 된다. cluster들 사이의 길이가 크고, 각각의 cluster 내부의 data는 똘똘 뭉쳐있으니까. 그런데 실제로 c1과 c2영역에는 data가 없다. 그래서 c3영역에 일정 페턴을 가지고 뭉친것이다. 그 일정 페턴이라는 것이... 빨간동그라미는 왼쪽 하단, 초록네모는 오른쪽하단 전체, 파란다이아는 오른쪽 하단끝이라는 것이다. 결국 초록네모와 파란다이아의 영역이 겹치기 때문에 좋은 clustering은 아니라는 뜻이다.

별로 어렵지도 않은 내용이었는데 제대로 이해하는데 쪼금 걸렸다. 아무튼 여기까지가 SOM 설명이다. 다음 포스팅은 Convolutional neural network나 Bayesian network가 됐으면 하는데 그게 언제가 될까...

흠.. Boosting 부분에서 포스팅 내용이 너무 허접하다고 판단되어... 다시 포스팅을 하긴 했는데 아예 새로운 글에다가 했다.

http://operatingsystems.tistory.com/entry/Adaptive-Boosting-Algorithm

여기다 포스팅 해두었으니 잘 보시길!!

Adaptive Boosting Algorithm이다. 우선 이 알고리즘 설명하기 전에 내가 왜 Boosting을 다시 하냐면... Boosting 공부했던거 되세기기 위해서 예전에 써둔거 다시 읽어봤는데 뭔가 많이 부족하고 맘에 안들어서 다시하려고 그런다.

그런데 문제는 이 포스팅 정확하지 않을 수도 있다는 것이다. 그러니까 내가 쓴 것이 맞는지 틀리는지는 있는지 없는지 모르는 독자분들이 잘 판단해주세요ㅋㅋ 

이전 포스팅에서 디테일이 많이 생략되어있드라. 그 디테일을 이번 포스팅에서 살려보려고 한다.

우선 Boosting의 기본 개념을 다시 한번 되세기자. 쉽게 말해서 Weak learner 여러개를 합쳐서 트레이닝한 것이 Strong learner 하나보다 좋다는 것이다. 초등학교 축구 선수 100명이 박지성 한명보다 낫다는 것이다.

우선 weak learner의 error rate을 구하는 방법부터 알아보자. Weak learner h(x)는 아래와 같이 error rate을 구한다.

뭔가 어렵다 error rate 구하는 방법을 예제로 알아보자. 이거 헷깔린다 잘 봐둬라.

h1(x<thr)값은 x<thr라는 조건이 참이면 1 거짓이면 -1이다. 단순하다. 그래서 Weak learner이다. 그렇게 구한 값을 y와 비교한다. I(h1(x) != y)는 h1(x) != y라는 조건이 참이면 1 거짓이면 0이다. 이렇게 한 후에 d1이랑 곱해준다. d1은 weight1이라고 보면 된다. 젤 처음의 weight은 항상 1/데이터개수 이기 때문에 0.1로 초기화되는 것이다. error rate은 d1*I(h1(x) != y)의 합이기 때문에 우리는 0.3이라는 error를 가지게 된다. 또 다른 예제를 봐보자.

여기서는 x>thr이다. 부등호 방향이 바뀌었다. 그 외에는 구하는 방법은 같으니 한번 연습장에 해보시길 바란다.

여기서 thr은 무엇이냐면, threshold이다. 그 값을 정하는 기준은 error rate을 제일 작게 하는 threshold를 선택하는 것이다. 즉, threshold 0.5부터 8.5까지 error rate을 구해서 error rate이 젤 작은 threshold를 구하는 것이다. 첫번째 예제에서는 그 threshold가 2.5였고, 두번째 예제에서는 5.5였던 것이다.

이렇게 error rate을 구한 후에는 그 weak learner를 평가해야 한다. 평가치는 a(t)로 나타낸다. t번째의 weak learner의 평가치라고 보면 된다.

그래서 지금까지 한 것을 정리하면 각각의 t번째의 weak learner는 각각 error rate와 a값을 가지고 있었다. 이 값을 가지고 우리는 weight을 update 해줄 것이다. update해줄 때 중요한 원리는 t-1 weak learner에서 틀렸던 것들에 대해서 t weak learner에서는 더 큰 weight을 두고 맞았던 것들에 대해서는 더 작은 weight을 둔다는 것이다. 우리도 시험볼 때 평소에 자주 틀리는 것들에 대해서 중점적으로 더 공부하고 평소에 잘 맞는 것들에 대해서는 감만 유지하는 식으로 준비하는 것과 비슷하다. 그래서 weight을 update하는 식은 h(x)가 맞았는지 틀렸는지에 따라 두가지 경우로 나뉠 수 있다. 아래와 같이 나타낼 수 있다.

(위의 식에서 d는 weight을 의미한다는 점 참고)

예측이 맞을 때는 exp(-a)이고 틀릴 때는 exp(a)이다. 틀리면 커지게 마련이고 맞으면 작아지게 마련이다. 위의 식에서 Zt는 우선 그런게 있다고 치자. 그냥 주어진 값이라고 알아두고 저거 어떻게 구하는지는 조금 있다가 설명하려고 한다.

지금까지 한 것들이 weight(d1, d2, ...)이 한번 update될 때까지의 전체적인 과정이다. 그러면 실제로 아래의 예제를 통해서 training을 해보자.

위의 경우에서는 d3까지만(weight3) 구했다. 왜냐?? d3까지만 구해도 되니까... 왜냐?? 최종적으로 여러개의 weak learner들을 하나로 합치는 공식이 아래와 같은데

이 공식을 이용해서 첫번째 iteration, 두번째 iteration에서의 맞고 틀리고를 구해보면 둘다 세 개씩 틀린다. 그런데 세번째 iteration은 다 맞는다. 그래서 "오 잘됐군ㅋ" 하고 세번째 iteration에서 멈추는 것이다.

참 생각보다 그렇게 어려운 포스팅은 아니라고 생각하는데 왜 이렇게 오래 걸렸는지 잘 모르겠다. 하루 걸렸다. 뭐 쉬엄쉬엄해서 그런 것도 있긴 한데.. 

아무튼 이번 포스팅은 여기서 마치려고 한다. 다음 포스팅은 뭐가 될까? 몇 가지 생각해두고 있는 것이 Hadoop, Mahout, Spark 관련된 것일 수도 있고 또 다른 것이 될 수도 있고.. 아 배고파 점심 먹으러 가야지...