아 이제 Ensemble을 공부해보도록 하자. 참 이거 포스팅 순서가 엉망 진창이다. 그런데 이해해주시길 바란다. 공부하느라 요즘 만신창이가 되어가고 있다. Ensemble이 무엇인지 부터 설명해보자. 

영어 단어 Ensemble은 여러 가지를 합친다는 의미이다. data mining에서 ensemble이라고 하면 여러가지 model을 합친다는 것이다. 조금 더 정교한 결과를 얻기 위해서 합치는 것이다. 가령 아래의 경우 하나의 model으로는 정교한 classifier를 찾을 수 없다.

자 그럼 여기서부터 Bagging부터 조금 자세하게 이야기해보도록 하자. Bagging은 Bootstrap Aggreggating의 준말이라고 한다. 여기서 중요한 것은 sampling을 한다는 것이다.(sampling을 할 때 sampled data는 최대한 random해야된다.) 전체의 data로 하는 것이 아니고 sampling된 data로 classifier를 돌린다는 것이다. 아래와 같이 간단하게 두가지 sample을 가지고 이야기해보자. (sampling된 data는 테두리선을 빨간색으로 해놨다)

# sample1

# sample2

# sample3

sample1과 sample2 sample3를 놓고 보자. 저렇게 sampling하고 classifier를 돌리면 당연히 다른 결과가 나올 수 밖에 없다. 이것을 대략 합쳐보자.

각 영역이 어떻게 분류가 되는지 각각의 model 별로 봐보자.

이것을 majority voting bagging이라고 한다. 왜 majority voting인지는 위의 table을 보면 쉽게 이해할 수 있을 것이다. 이제 이렇게 나온 결과를 각각의 model1, model2, model3과 비교해보자. 합친 것이 더 error rate이 적다.

흠.. 세보니까 model1과 ensemble error개수는 같네... -_- 그런데 model 개수를 조금 더 늘리고 데이터를 조금 더 분산시키고 하면 분명히 ensemble error가 더 적을 것이다. 참고로 각 영역을 정하는 방법은 majority voting말고도 probability를 기반으로 정할 수 있다. 여기서 이것에 대한 자세한 이야기는 안 하련다.(나도 모르므로)

그 다음 해야할 이야기는 Random Forest이다. Random Forest는 위와 비슷한 개념인데 Tree에 특별히 더 잘 적용되는 것이라고 보면 된다. 우선 tree 기반의 classifier 하나를 정하자. Decision Tree로 정해보자. 그리고 sampling을 한다. random forest는 모든 feature를 다 사용하지 않는다. 특정 feature만 골라서 사용한다. 몇 개를 고르냐? 그건 자유다.(select n features) 몇 개를 하든 상관없다. 이렇게 몇 개 골라진 feature를 가지고 data를 classifier로 돌린다.

random forest를 통해서 영향력 있는 feature를 골라줄 수 있다. 

위의 source code와 그 밑의 결과는 아래의 링크에서 capture해왔다.

http://blog.datadive.net/selecting-good-features-part-iii-random-forests/

위의 결과를 보면, 각 feature가 얼마나 영향력이 있는 feature인지 ranking을 알 수 있다.

자 마지막으로 Boosting이다. 아 이거 생각하면 아오 맥주먹고 스트레스 풀고 싶어지는 그런 느낌이 든다고 할까? 공부할 때 Bagging, Random Forest는 1시간 반만에 끝냈는데 Boosting만 4시간 걸렸다. 왜 그렇게 걸렸는지 Boosting 설명하면서 이야기 해보려고 한다.

-------------------------------------------------------------------------------------------

Boosting 관련 내용은 아래의 포스팅에서 더 잘 설명해두었다. 너무 허접해서 다시 했다. (2016.09.11)

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

-------------------------------------------------------------------------------------------

Boosting은 기본적으로 sampling을 하지 않는다. 기본적인 개념은 이렇다. weak learner로 strong learner를 만드는 것이다. weak learner가 뭐냐? 아주 simple한 classifier. 가령,

- 어른과 어린이를 구분할 때 키가 160 이상이면 어른 이하면 아이.

- 남자와 여자를 구분할 때, 머리카락 길이가 20센치 이상이면 여자 이하면 남자.

- 좋은 컴퓨터와 나쁜 컴퓨터를 구분할 때, 크기가 크면 나쁜 컴퓨터 작으면 좋은 컴퓨터. 

누가 봐도 제대로 잘 동작할 것 같지 않은 저런 weak한 learner들을 말한다. 위와 같은 대충대충의 기준으로는 제대로된 machine learning이 이루어지지 않는다. 그런데 저런거 한 100개 가져다 놓으면 꽤나 잘 동작한다는 것이 boosting의 원리이다. 그거를 어떻게 구현하냐?? weight을 통해 구현한다.

weak learner1를 통해서 대충 data를 classify 해보자. 그러면 맞은 것이 있고, 틀린 것이 있을 것이다. boosting은 여러 개의 weak learner를 사용한다고 했으므로, weak learner2를 사용해서 또 data를 classify 하는 것이다. 그런데 이때 처음에 weak learner1을 돌렸을 때 틀렸던 data들에 대해서는 조금 더 높은 weight을 두고 weak learner1에서 맞았던 data들에 대해서는 조금 더 낮은 weight을 두는 것이다. 

무슨 말이여? 싶을 것이다. 예제를 보자.

(단, a < 0.1 and b > 0.1, 최초 weak learner1을 돌릴 때의 weight은 1/datasize(10) = 0.1로 같게 설정한다.)

위의 예제는 아래의 링크에서 확인 가능하다.

http://www.csie.ntu.edu.tw/~b92109/course/Machine%20Learning/AdaBoostExample.pdf

그러면 0.1보다 작은 값 a와 0.1보다 큰 값b는 어떻게 만들어줄까? 틀린 개수/전체 개수, 즉 error rate(e)을 구해서(3/10 = 0.3) 아래의 식에 적용시켜주면 된다.

위의 식을 구하는 방법도 있지만, 그냥 그 부분은 생략하려고 한다. 그런데 왜 이거 공부하는데 오래 걸렸냐? 바로 weight을 어떻게 classifier에 적용시키냐는 것이다. 이거를 설명해둔 책이나 blog가 전혀 없었다. 결국 답은 stack overflow 사이트에서 찾았다. 답은... 참 어이없게도... "알아서" 이다. 적당히 알아서 적용하라는거다. 예를 들어, count-base classifier algorithm을 사용한다면, 1을 세지 말고 1*weight을 세라는 것이다. 혹은 sampling을 할 때 weight이 큰 것이 더 sampling이 잘 되도록 한다던지. 즉 "알아서" 이다. "고작?" 이거 찾으려고 4시간 걸린거다...

아무튼 이번 포스팅 여기서 마치려고 한다. 다음 포스팅은 아마도 classifier evaluation & cross validation이 되지 않을까 싶다.

이번 포스팅에서는 Forward algorithm과 Viterbi algorithm을 공부할 차례다. 우선 Forward algorithm을 공부하고 Viterbi algorithm을 공부할 예정이다. 이 두 algorithm은 굉장히 비슷하므로 Forward algorithm 설명마친 후에는 거의 Viterbi algorithm은 설명할 것이 별로 없을 것이다. 아무튼 Forward algorithm 설명해보자.

Forward algorithm는 HMM에서 주어진 input sequence에 대한 probability를 구하는 것이다. 가령, 첫째 둘째 셋째날 외출한 사람의 수가 각각 10명 1명 4명일 경우의 확률은 아래의 확률을 모두 더한 것과 같을 것이다.

Possible output : Sunny, Rainy

우선 Forward algorithm를 사용하지 않고 일일이 한번 구하려면 어떻게 구해야되는지 알아보자. 지금부터는 그냥 단순 고등학교 수학문제가 되겠다. 우리가 필요한 확률들은 아래와 같이 정의되어 있다고 하자.

우선, output sequence가 sunny, rainy, sunny라고 가정하고 (probability = 1) 부분적으로 계산을 해보자.

여기서 sunny rainy sunny일 확률을 계산해서 곱해주자.

이와 같은 일을 우리는 각각의 possible output sequence에 대하여 해줘야 된다. 즉 위의 계산을 7번 더해줘야 된다.

여기서는 output으로 가능한 경우의 수가 sunny 또는 rainy밖에 없고 input sequence 길이 역시 3밖에 안되기 때문에 8번 하는 것 정도는 금방 끝낼 수 있다. 그런데 실제로 실생활에서 사용될 때는 output 개수도 많을 것이고 input sequence는 더더욱 많을 것이다. 이는 N^V와 같은 형태로 계산 수가 늘어나기 때문에 효율상 상당히 안 좋다. 그러면 위와 같은 일을 우리는 어떻게 간단하게 해결할 수 있을까. Trellis를 이용하여 간단하게 만들면 된다. Trellis는 아래와 같은 모형을 Trellis라고 한다.

계산 결과는 결국 같다.(휴 다행이다. 한번에 끝내서) 어떤 사람들은 위의 두 풀이과정을 보고, 이거 뭐 딱히 다를게 있어? 라고 이야기 할 수도 있다. 그런데 컴퓨터 입장에서는 확실히 다르다. Forward algorithm을 사용할 경우에는 이전에 사용했었던 계산값을 다시 사용할 수가 있다. 그런데 일일이 같은 계산 8번 해줄 때는 그런 이득을 취할 수가 없다. 이런 것을 dynamic programming이라고 하나보다. 이것에 대한 정확한 개념은 독자들에게...

여기까지가 Forward algorithm이다. Viterbi algorithm은 간단하게 이야기만 하고 끝내려고 한다. Viterbi algorithm의 목적은 most likely possible output sequence를 구하는 것이다. Forward algorithm에서 다른 것은 각각의 state에서 합을 하지 말고 maximum을 취해서 가장 큰 값들만 다음 state로 넘어갈 수 있도록 하는 것이다.

o2 = 1일 때 보면, sunny일 확률도 o1=10 & sunny로부터 왔고 rainy일 확률도 o1=10 & sunny로부터 왔다. 따라서 o1까지는 sunny일 확률이 제일 높다.

o3 = 4일 때 보면, sunny일 확률도 o2=1 & rainy로부터 왔고, rainy일 확률도 o2=1 & rainy로부터 왔다. 따라서 o2까지는 sunny → rainy일 확률이 제일 높다.

마지막으로 final state에서 보면 rainy일 확률(0.020412)가 sunny일 확률(0.01134)보다 크다. 따라서 o3까지를 모두 종합해보면, observation sequence가 10, 1, 4일 경우에는 sunny → rainy → rainy 가 가장 높은 확률을 나타내게 된다. 

후, 요즘 12시 넘겨서 자는 경우 거의 없는데 오늘 12시 넘긴다. 12시 16분이다. 빨리 자야겠다. 다음 포스팅은 forward-backward algorithm이면 좋겠으나 아닐 수도 있다.

forward-backward algorithm 공부해보고 싶으신 분은 이거 한번 찾아보세요!! 저는 조금 쉬었다가 다음에 보려고요

http://www.cs.rochester.edu/u/james/CSC248/Lec11.pdf

이번 포스팅에서는 Markov Chain과 Hidden Markov Model에 대해서 이야기해보도록 하자. 우선 Markov Chain이다. Markov Chain은 일종의 Automata의 확장이라고 보면 된다. Automata의 확장인데 하나의 state에서 그 다음 state으로 갈 때 확률이 이용되는 automata라고 보면 될 것 같다. 이거는 예제로 보면 금방 이해가 갈 것이다.

우선 위의 그림과 함께 Markov Chain의 component를 설명해보자.

Q : component of Markov model e.g. q0, q1, ... qN

위의 그림에서의 동그라미 하나하나가 state이다. HOT 동그라미는 q1 state이고 COLD 동그라미는 q2 state이고 WARM 동그라미는 q3 state이다.

aij : state i에서 state j로 가는 확률이다. 예를 들어, HOT 다음에 또 HOT일 확률은 a11이고, HOT 다음에 WARM일 확률은 a13이다. 

q0, qF :  q0는 state 0, 즉 시작하는 start state을 의미하며, qF는 Final state, 즉 종료하는 final state을 의미한다.

위의 Markov Chain에서 두가지 가정이 있다. 첫번째 가정은 하나의 state에서 다음 state로 가는 probability는 오로지 이전의 상태에 의해서 결정된다는 것이다. 즉 a13은 HOT에서 WARM으로 가는 확률인데 이 확률은 오로지 state1과 state3 사이에서만 결정되지 state1이 어떤 probability로 state1이 되었는지는 중요하지 않다는 이야기이다.

두번째 가정은 하나의 state에서 다음 state로 뻗어나가는 probability의 합은 1이라는 것이다. 당연한 이야기이다. 한 state에서 무조건 다음 state로 어떻게든 어디로든 갈 것이기 때문에 당연히 probability의 합은 1이다.

Markov Chain은 별로 안어렵다. 그래서 예제 하나만 더 보고 끝내도록 하자. 위의 그림에서 HOT HOT HOT WARM이 input으로 왔을 때 그 probability는 어떻게 구하는가? 아주 쉽다.

a01 a11 a11 a13을 전부 곱한 값이 될 것이다. 아주 쉽다.

자 두번째 공부할 것은 Hidden Markov Model이다. 우리가 살면서 주어진 input을 통해 output을 예측해야 되는 경우는 굉장히 많다. 사람들이 밖에 돌아다니는 빈도를 보고 비오는 날씨인지 날씨가 좋은지를 예측할 수도 있고, 사람들이 어떤 물건을 많이 사는지 적게 사는지를 관찰하여 그 물건의 품질을 결정할 수도 있고, 어떤 사람이 말을 얼마나 많이 하느냐에 따라 그 사람의 기분을 측정할 수도 있다. 이런식으로 우리가 관찰한 것들을 기반으로 우리가 볼 수 없는 무언가를 찾아내는 것, 숨겨진 그것을 찾아내는 것(hidden)을 model로 만들어 둔 것이 Hidden Markov Model(HMM)이다. 따라서 HMM에는 한 가지의 component가 더 들어간다. 

Q, A, q0, qF까지는 Markov Chain과 같고, 여기에 O(e.g. o1, o2, o3, ..., oT) observatoin 순서가(sequence of observation) 들어간다. sequence of observation 즉, 첫번째 날 두번째 날 세번째 날에 각각 사람을 10명 1명 4명 봤을 때, 첫번째 두번째 세번째 날의 날씨는?? 여기서 o1 o2 o3는 각각 10명 1명 4명이고, 이것을 가지고 예측된 날씨는 가령, Sunny Rainy Windy 등등이 되겠지. 즉 10명 1명 4명이라는 input sequence를 가지고 Sunny State인지 Rainy State인지 Windy State인지를 예측하는 것이 되겠다.

그 다음에 또 하나 언급할 component는 observation probability이다. 특정 state i에서 각각의 o1, o2, o3, ..., oT가 관측될 probability를 의미한다. 가령, Sunny state에서(Sunny한 날씨에) 밖에 사람이 10명이 관측될 확률, 1명이 관측될 확률, 4명이 관측될 확률을 의미한다. i state에 ot가 관측될 probability를 의미할 경우 기호로는 bi(ot)로 쓴다.

이것을 통해서 우리가 할 수 있는 것은 무엇일까? 보통 HMM을 통해서 우리는 다음의 세 가지 문제를 풀려고 한다.

Problem 1 : 주어진 input sequence으로 가능한 모든 output sequence 각각의 probability는?

Problem 2 : 주어진 ipnut sequence에 대해서 가장 그럴듯한 (highest probability) output sequence는?

Problem 3 : Learning!! 즉, Observation에 대한 probability(B)와 transition probability의 확률(A)를 learning하는 것!!

이 문제를 푸는 algorithm이 있는데, 각각의 문제가 아래의 algorithm을 통해 풀 수 있다.

Forward algorithm → Problem 1

Viterbi algorithm → Problem 2

Forward-Backward algorithm (Baum-Welch Algorithm) → Problem 3

다음 포스팅에는 Forward algorithm과 Viterbi algorithm을 같이 설명해보자. 둘다 비슷한 점이 있기 때문이다. 흠 그런데 Forward-Backward algorithm.. 요거 요거 이해가 어렵다. 당분간 skip 하도록 하자.