몇일 전부터 쓰고 있던 포스팅인데 딴짓하고 그러느라 좀 늦었다. 이번에는 꼭 포스팅을 마무리하리라. 사실 딴짓이라기 보다는 포스팅을 하기 위해 사용해야할 수식들을 만들고 친구들 만나느라 우하하하.....

에헴.. 그러니까 예전에 다시 예제와 같이 설명하겠다는 Artificial Neural Network의 Backpropagation에 대해서 다시 한번 설명해보려고 한다. Backpropagation은 Artificial Neural Network를 training하기 위한 알고리즘으로 보면 된다. 조금 더 구체적으로 말하면 Artificial Neural Network의 Weight을 update하는데 사용된다고 보면 된다. 

우선 살짝 Artificial Neural Network에 대해서 복습하고 넘어갈까? Artificial Neural Network은 Input layer, Hidden layer, Output layer로 이루어져있는 network이다. 각각의 layer는 각각 다른 개수의 Neuron으로 이루어져있다. 하나의 Neuron을 보면 아래와 같이 생겼다.

무언가 input n개를 받고 그것을 각각의 weight에 곱하고 더해서 z를 구한다. 이 z값을 f(z)에 적용하여 output을 낸다. 이 때 f(z) 함수의 특성에 따라 output은 무조건 0과 1사이가 된다. 

지금까지 한 이야기들은 모두 이전 포스팅에도 했었던 내용이다. 사실 앞으로 쓸 내용도 모두 했던 얘기이다. 그렇지만 조금 더 숫자를 이용해서 구체적으로 쓰려고 하는 것이다. 예전에 이야기했던 것처럼 Artificial Neural Network은 한개의 Input layer 여러개의 Hidden layer 한개의 Output layer를 가지고 있다. 이번 포스팅에는 나는 아래와 같은 한개의 Input layer, 두개의 Hidden layer, 한개의 Output layer를 가지고 이야기를 해보려고 한다.

각각의 Weight을 모두 쓰려면 너무 시간이 걸리고 복잡해보이기만 할 것 같아서 위와 같이 몇개만 예시로 Weight 넘버링 해봤다. wN_{ij}는 Layer{N-1}에서의 i번째 Neuron과 Layer{N}의 j번째 Neuron 사이의 Weight을 표현한 것이다.

Backpropagation은 epoch를 계속 반복하면서 최적의 weight으로 update되는 과정이다. 따라서 제일 처음에는 weight은 random값으로 설정된다. 우리는 공부를 하고 있는 것이므로 아래와 같이 initialize되었다고 가정하고 생각해보련다.

자 여기서 Backpropagation을 시작해보자. Input layer는 3 dimension이기 때문에 세 개의 Input, Output layer는 2 dimension이기 때문에 두 개의 Output, bias는 Input layer를 제외한 나머지 모든 layer에 각각 하나씩 주기로 하고 그래서 3 dimension (4 - 1). 위와 같이 초기화시켜놓고 Backpropagation을 시작해보자.

이 식과 그 값을 앞으로 계속 사용할 것이다. 즉 Backpropagation을 하기 위해서는 우선 젤 먼저 feedforward를 할 이유가 있다는 것이다. (위의 식처럼 주어진 input과 weight을 가지고 output을 구하는 것을 feedforward라고 한다.) 위의 식에서 f(x)는 x에 대한 sigmoid function이다.

아무튼 위의 값을 가지고 Backpropagation을 시작해보자. Backpropagation의 목적은 Error를 최소한으로 하는 weight을 만드는데 목적이 있다. Error는 sum of squared error로 아래와 같이 구한다.

위의 식에서 y는 실제 값 y_hat은 우리가 feedforward 해서 나온 예측값이다. 즉 우리의 예측값과 실제값의 차이의 제곱의 합의 절반을 Error라고 정의하고 그것을 최소화하겠다는 것이다. (왜 절반이냐? 계산을 쉽게하기 위해서!! 미분하기 쉽기 위해서!! 제곱을 미분하면 2가 앞으로 튀어나올 것이고 서로 상쇄되서 없어지니까.)

우리가 정확히 구하고 싶은 것은 Error가 아니라 Error를 최소로 만드는 weight을 구하고 싶은 것이다. 따라서 우리는 Error를 weight으로 미분할 것이다. 각 층별로 우리는 w1 w2 w3을 가지고 있으니까 결국 우리는 아래의 값을 순서대로 구할 것이다.

de/dw3

de/dw2

de/dw1

de/dw3를 젤 먼저 구할 것이다. 그래서 BACKpropagation이다. 뒤에 것부터!! 뭐 그런의미이다. 

위와 같이 de/dw3를 구하면 된다. w3는 4x2 matrix이니까 당연히 위와 같이 8개의 element를 구해야 한다. 여기서 질문!! 위의 식에서, 예를 들어 de/dw3_{11}를 보자. 이 식이 de_{total}/dOUT_{o1} * dOUT_{o1}/dOUT_{z1} * dOUT_{z1}/dw3_{11}와 같이 되는 것은 알겠지? 그런데 이것이 왜 그 다음 식으로 전개가 될까? 왜 ...

de_{total}/dOUT_{o1} = -(y1 - OUT_{o1})

dOUT_{o1}/dOUT_{z1} = OUT_{o1}(1-OUT_{o1})

dOUT_{z1}/dw3_{11} = H2_{o1}

이렇게 될까??? 위의 세 식이 저렇게 되는 이유를 알면 backpropagation은 거의 모두 이해했다고 보면 된다. de_{total}/dOUT_{o1}부터 차례대로 봐보자.

이기 때문에 이것을 OUT_{o1}로 미분을 하면 

이렇게 되는 것이다 y2에 대해서는 마찬가지로 OUT_{02}로 똑같이 해주면 된다.

dOUT_{o1}/dOUT_{z1}를 구해보자. 이거는 조금 더 복잡하다. 그렇지만 어렵지는 않다.

dOUT_{z1}/dw3_{11}는 굉장히 간단하다. OUT_{z1}을 젤 위의 식에서 

로 표현했기 때문에 이것을 w3_{11}로 미분하면 H2_{o1}이 나오는 것이다.

결국 de_{total}/dOUT_{o1}, dOUT_{o1}/dOUT_{z1}, dOUT_{z1}/dw3_{11}는 우리가 이미 feedforward를 통해 구해놓은 그 값을 짜맞춰서 구할 수 있게 된다는 뜻이다.

자 de_{total}/dOUT_{o1}, dOUT_{o1}/dOUT_{z1}를 미분하는 공식은 그냥 "외워"두자. 왜냐하면 앞으로도 계속 쓰이기 때문이다. 아래와 같이 공식화해보자.

위의 공식을 생각하며 de/dw2를 구해보자.

위와 같이 구할수 있다. 위의 값중에서 de_{total}/dH2_{o1}, de_{total}/dH2_{o2}, de_{total}/dH2_{o3}, de_{total}/dH2_{o4}는 아래와 같이 구할 수 있다.

이 식의 수식 전개는 모두 위에서 "외우"라고 했던 공식 세개를 통해서 이해가 가능할 것이고 추가로 설명해야할 내용이 있다면 왜 de_{total}/dH2_{o1} = de_{1}/dH2_{o1} + de_{2}/dH2_{o1} 이와 같이 되는가? 정도일 것 같다. 왜인지 생각해보자. H2_{o1}가 error에 영향을 주는 것은 e_{1}에도 영향을 주고 e_{2}에도 영향을 주기 때문이다. 즉 H2_{o1}의 변화량은 e_{1}과 e_{2} 모두에게 영향을 준다는 뜻이다. 그래서 두 개를 더한 것이다.

자 de/dw2 식 설명을 모두 끝냈으니까 실제로 값을 구해볼까나. 우선 de_{total}/dH2_{o1}, de_{total}/dH2_{o2}, de_{total}/dH2_{o3}, de_{total}/dH2_{o4}는 아래와 같은 값을 갖게 되기 때문에

이와 같은 값을 가지게 되고, de/dw2는 아래와 같이 계산이 된다.

이제 마지막으로 de/dw1을 구할 차례이다. 이거는 아래와 같이 구하면 된다.

de_{total}/dH1_{o1}, de_{total}/dH1_{o2}, de_{total}/dH1_{o3}, de_{total}/dH1_{o4}, de_{total}/dH1_{o5}는 아래와 같이 구한다. 여기서부터 조금 많이 복잡해진다. 종이하고 연필꺼내서 적어가면서 봐라. 눈으로는 이해하기 힘들것이다.

우선 H1_{o1}, H1_{o2}, H1_{o3}, H1_{o4}, H1_{o5}는 e1과 e2모두 영향을 주게 된다. 따라서 기본적으로 

de_{total}/dH1_{o1} = de_{1}/dH1_{o1} + de_{2}/dH1_{o1}

de_{total}/dH1_{o2} = de_{1}/dH1_{o2} + de_{2}/dH1_{o2}

de_{total}/dH1_{o3} = de_{1}/dH1_{o3} + de_{2}/dH1_{o3}

de_{total}/dH1_{o4} = de_{1}/dH1_{o4} + de_{2}/dH1_{o4}

de_{total}/dH1_{o5} = de_{1}/dH1_{o5} + de_{2}/dH1_{o5}

위와 같이 나오고. e1과 e2는 각각 아래와 같이 OUT_{o1}과 OUT_{o2}로 표현이 가능하고 OUT_{o1}과 OUT_{o2}는 모두 H1_{o1}, H1_{o2}, H1_{o3}, H1_{o4}, H1_{o5}로 표현이 가능하다. 아래와 같이 말이다.

(위의 식이 복잡하여 일부러 g(x)라는 함수를 만들어놨다. g(x)는 sigmoid function 말하는 것이다. f(x)와 같다고 생각하고 보면 된다.)

복잡하다... 그래도 어쩌겠냐.. 해야지.. 아무튼 이것을 알고 

de_{total}/dH1_{o1} = de_{1}/dH1_{o1} + de_{2}/dH1_{o1}

de_{total}/dH1_{o2} = de_{1}/dH1_{o2} + de_{2}/dH1_{o2}

de_{total}/dH1_{o3} = de_{1}/dH1_{o3} + de_{2}/dH1_{o3}

de_{total}/dH1_{o4} = de_{1}/dH1_{o4} + de_{2}/dH1_{o4}

de_{total}/dH1_{o5} = de_{1}/dH1_{o5} + de_{2}/dH1_{o5}

이것을 구해보자.

고등학교 때 f(g(x))를 미분하면 f'(g(x)) * g'(x)라는 것을 배웠을 것이다. 그것을 이용해서 e_{1}과 e_{2}를 H1_{o1}, H1_{o2}, H1_{o3}, H1_{o4}, H1_{o5}로 각각 미분하면 위와 같이 되는 것이다. (나 혼자 미분하고 굿하고 장구치고 한거라.. 틀릴수도 있다. 하지만 원리는 위와 같이 구하는 것이 맞다)

g1, g2, g3, g4의 값과 그 미분값을 구해봤을 때 아래의 값이 나오고

이것을 대입해서 우리가 원하는 값을 구하면...

이렇게 나오게 된다. 그러면 우리는 이제 드디어 de/dw1, de/dw2, de/dw3를 모두 구하게 됐다!!! 이것을 가지고 최종적으로 w1, w2, w3을 update시켜보자. weight update는 아래와 같이 할 수 있다.

위의 공식에 따라서 weight을 update해보면 아래와 같이 update된다. (단, learning_rate은 0.1이라고 하면...)

지금까지 무지하게 많은 숫자와 공식들을 가지고 고생했다... 우와... 드디어 했다 아무튼... 참고로 말하자면 위의 식들 중 틀린 것이 있을 수도 있다. 그렇지만 원리는 제대로 설명했으니 '이 사람 실수했꾸먼?' 하고 봐주면서 읽기를 바란다. 

다음 포스팅은 뭘까? 잘 모르겠따. 이번 포스팅 역시 무지하게 오랜만에 한 포스팅인데.... 아무튼 언제가 될지 모를 다음 포스팅을 기다려주시길...

으아 오늘은 왜 이렇게 공부가 안 되냐? 조금 쉬어야 되는 때가 온 것인가? 잠깐 어딘가 떠나있어야 되나? 아 몰라 적어도 오늘 뭔가는 해야지. 오늘은 아주 쉬운 포스팅이 될 것이니 음악이나 하나 틀어두고 쉬엄쉬엄 읽어보시길 바란다.

data mining에서 하나의 model을 측정하는 방법은 여러가지가 있다. 대표적인 measurement가 accuracy인데, 이 accuracy는 biased data에서는 별로 효과적이지 못 하다고 이전 포스팅에서 이야기했었다. 그것을 해결하기 위해 F1 measurement, Recall, Precision을 계산해야 된다고 이야기한 것이 딱 이전 포스팅에 작성한 내용이다.

http://operatingsystems.tistory.com/entry/Data-Mining-Measuring-a-classification-model

위에 링크 남겨둔다.

이번 포스팅에서 할 이야기는 위의 내용과 비슷하나 조금 advanced된 이야기이다. Macro average와 micro average이다. 간단하게 아래와 같은 3-class confusion matrix가 있다고 해보자.

지금 BAC CON EXP 세 개의 class가 있으니까 하나하나 분리해보자.

마지막에 pooled matrix는 위의 세 개를 합친 것이다.

우선 macro average는 이렇게 구한다. 각각의 BAC CON EXP에 대한 recall, precision, f1을 구해서 평균을 내는 것이다.

# Recall

BAC = 9/(9+3) = 0.75

CON = 5/(5+4) = 0.55

EXP = 4/(4+2) = 0.66

# Precision

BAC = 9/(9+4) = 0.69

CON = 5/(5+4) = 0.55

EXP = 4/(4+1) = 0.80

BAC = (2 * 0.75 * 0.69) / (0.75 + 0.69) = 0.72

CON = (2 * 0.55 * 0.55) / (0.55 + 0.55) = 0.55

EXP = (2 * 0.66 * 0.80) / (0.66 + 0.80) = 0.72

별로 어렵지 않게 이해할 수 있는 부분이므로 더 이상의 설명은 생략하도록 하자. 그러면 Micro average를 구해보자. 이건 더 쉽다. pooled matrix를 이용하여 한꺼번에 한번만 구한다.

Recall = 18/(18+9) = 0.66

Precision = 18/(18+9) = 0.66

F1-measure = (2*0.66*0.66)/(0.66+0.66) = 0.66

micro-average에서는 Recall과 Precision이 같은 값을 갖게 된다. 따라서 F1역시 Recall, Precision과 같게 된다. Recall, Precision = a로 놓으면

F1-measure = 2*a*a/2a = a

자 끝이다-_-. 정말 간단한 포스팅 되겠다. 그런데 한 가지 이야기를 더 하고 끝내야 된다. macro-average와 micro-average의 특징을 이야기 해야된다.

Macro-average는 내 classifier가 모든 class에 대해 얼마나 (평균적으로) 잘 동작하는지 알고 싶을 때 사용한다. 위의 예제의 경우, BAC CON EXP각 class에 대하여 얼마나 평균적으로 고르게 잘 동작하고 있는지를 알고 싶을 때 사용한다. 그래서 평균을 구하는 것인가 싶다.

Micro-average는 이럴 때 사용한다. 위의 경우에는 우리가 하나의 confusion matrix를 가지고 각 class별로 3개로 나눴다. 따라서 각 3개의 confusion matrix에서 TF, FN, FP, TN의 합은 같을 수 밖에 없다. 그런데 만일 아래와 같이 각각의 class의 size가 다르면 어떻게 할까?

위의 경우는 BAC CON EXP가 각각 독립적으로 측정된 confusion matrix라서 각각의 size가 다를 수 있다. 이런 경우에는 각각의 confusion matrix를 pooled로 합치면, recall, precision, f1이 다를 수 있게 된다. 위의 경우의 micro-average를 precision, recall, f1에 대하여 구하면 아래와 같다.

Recall : 114/(114+10) = 0.92

Precision : 114/(114+22) = 0.84

F1 : (2*0.92*0.84)/(0.92+0.84) = 0.88

아주 쉬운 포스팅이다. 다음 포스팅은 뭐가 될지 솔직히 잘 모르겠지만 뭔가 올라오겠지?

이번 포스팅은 내가 이전에 공부하다가 몰라서 잠깐 미뤄뒀던 Forward-Backward algorithm이다. 알고 보면 그렇게 어려운 내용은 아니었던 것 같은데 왜 이렇게 오래걸렸을까? 아무래도 여러가지 probability를 표현하는 기호에 익숙하지 않았던 것, 그리고 Forward-Backward algorithm에 나오는 기본 전제를 간과해서. 아무래도 후자가 조금 큰 것 같다. 아무튼 Forward-Backward algorithm 설명해보도록 하자.

Forward-Backward algorithm를 구하기 위해서 필요한 data는 observation sequence와 initial transition probability matrix, initial emission probability matrix이다. initial transition probability matrix와 initial emission probability matrix는 기본적으로 HMM의 parameter에 해당한다. 왜 initial이라는 단어를 붙였냐면, 기본적으로 Forward-Backward algorithm는 HMM의 parameter를 training하기 위한 algorithm이기 때문이다. 자, observation sequence도 분명 필요한 data라는 것을 다시 한번 되세기자.

이전에 포스팅했던 Forward algorithm과 Viterbi algorithm에서 사용했던 예제를 다시 사용하여 이야기해보면,

# Observation sequence : 10 - 1 - 4

# HMM parameter

이렇게 두 개가 주어진 상태에서, Forward-Backward algorithm를 돌리는 것이다. Forward-Backward algorithm의 최종 목적은 HMM parameter를 training하는 것이다. 편의상 transition probability matrix를 A로 놓고 emission probability matrix는 B로 놓자.

Transition probability matrix = A

Emission probability matrix = B

그러면 우선 probability 수학식보다는 머리 속으로 직관적으로 말해보자.

우선 A에서 분자 부분을(expected number of transition from state i to state j) 먼저 설명해보자. 기호 말고 예시로 생각을 해보자.

위와 같이 observation sequence가 time 1, 2, 3에 각각 10 1 4로 주어졌고, state의 가능한 값들은 sunny, rainy라고 해보자. 우리가 구하고자 하는 Aij는 가령, sunny에서 rainy로 넘어가는 확률이다. 이것을 어떻게 구할까? 

time 1 → time 2만 놓고 생각해보자. sunny → rainy가 될 확률은

sunny → rainy로 기대되는 횟수를 sunny → rainy와 sunny → sunny로 기대되는 횟수로 나누는 것이다. 그러면 time 1 → time 2에 sunny → rainy로 넘어가는 확률은 어떻게 구할까?

여기서 forward probability와 backward probability를 사용한다. 

forward probability : start state(time 0)에서 time 1까지 observation sequence가 10일 확률

backward probability : time 2에서 final state(time 3)까지 observation sequence가 1 - 4일 확률

forward probability는 이전 포스팅에서 자세하게 설명했으므로 여기서는 생략하자. backward probability 어떻게 구하는지는 마지막에 살짝 link만 남겨놓겠다. 여기서는 우선 무시하고 backward probability가 의미하는 확률을 제대로 정의하고만 넘어가자.

time = 2에서 rainy일 backward probability를 구한다고 하면,

backward probability는 start state와 time = 1은 고려하지 않고(가정하고), time = 2부터만 고려한 probability가 된다. 따라서 time = 1까지의 확률은 1이라고 가정하고 time = 2부터의 확률을 계산하는 것이다. time = 2부터 observation sequence가 1 - 4로 주어질 확률이 backward probability이다.

여기서 잠깐, 왜 backward이냐? 이건 아래에 backward probability를 구하는 링크를 따라가서 공부해보면 알 수 있다. 젤 뒤에 final state부터 차례차례 거슬러올라가는 식으로 계산이 되기 때문이다. forward algorithm을 뒤집어 놓은 거라고 생각하면 된다. 그래서 backward이다.

자 그럼 다시 time 1 → time 2에 sunny → rainy로 넘어가는 확률에 대해서 생각해보자. 

즉 time 1 → time 2에 sunny → rainy로 넘어가는 확률은 위의 그림에서 forward probability, backward probability 그리고 p(sunny→rainy) * p(1|sunny)를 모두 곱한 확률이 되겠다. 우리는 이 확률을 간단하게 기호를 사용해서 나타내려고 한다.

A에서 분자 부분은(expected number of transition from state i to state j) 위의 확률이 모든 time에 대하여 나타날 확률을 모두 더한 것이다. 따라서

이렇게 된다. A에서 분모부분은 어떻게 될까? state i에서의 모든 transition을 모든 t에 대하여 해주면 되는 부분이므로 최종적으로 우리가 원하는 식은 아래와 같게 된다.

자, 지금까지 절반했다. 나머지 절반은 emission probability를 구하는 식이다. 

위의 두번째 b가 emission probability를 구하는 식이다. 위의 식에서 분모부분은 어떻게 구할까? 특정 time t에 state j에 있을 확률을 구한 후 그것을 모든 t에 대하여 더해주면 되겠다. 가령 time = 2에 sunny에 있을 확률을 그림으로 나타내면 아래와 같다.

즉 time = 2에 sunny에 있을 확률은

이렇게 되고 이것을 state j, time t에 대하여 일반화시키면 아래와 같이 된다.

이것을 모든 t에 대하여 sum을 한 것이 우리가 원하는 emission probability의 분모부분이다.

그러면 분자부분은 무엇인가? 분자 부분은 state j에 있고 Vk를 관찰할 확률이므로, 단순히 observation probability matrix를 확인해서 곱해주면 될 것 같다.(이상하게 이부분은 책에 명시되어 있지 않아서 내가 스스로 생각한 부분이다.) 이것을 수식으로 나타내면 아래와 같다.

내 블로그에 예시가 없으면 섭하다. 그런데 이번에는 적당한 예시를 못 찾았다.ㅠㅠ 예시를 만들수는 있으나 그래도 검토까지 해서 맞는지 전부 확인하고 올리는 것이 기본인데, 아직 적당한 예시를 못 찾았다. 그래서 일단 예시는 skip하고 여기서 포스팅 마무리하려고 한다. 

다음에 적절한 예시를 찾으면 수정하는 것으로 하자.