EM algorithm을 공부해보자. 이건 사실 내가 생각보다 어렵다고 생각하여 계속 미루고 미뤄왔던 내용이었다. 그런데 용기를 내서? 공부를 해보니 생각보다 어려운 내용은 아니더라.

EM algorithm은 Expectation Maximization Algorithm이다. 왜 Expectation Maximization이라고 하는지 그리고 이게 뭐하는 것인지에 대하여 이번 포스팅에서 알아보려고 한다. 

우선, 이게 뭐하는 것인지 알아보자. 아주 간단한 개념이다. 아래와 같이 두 개의 Gaussian distribution이 있다고 해보자.(Normal Distribution = Gaussian Distribution)

파란 점섬으로 된 거는 무시하고, 두 개의 normal distribution만 봐보자. 노란색 그래프 중간에 있는 저 빨간색 점. 저 data가 주어졌을 때, 저 data가 노란 그래프에 속할지 파란 그래프에 속할지 알 수 없다. 상식적으로 노란 그래프에 속할 확률이 크고 파란 그래프에 속할 확률은 작다. 이걸 알아내기 위해서 EM을 쓰는 것이다. 

이번 포스팅은 수학 말고 편하게 예를 통해서 알아보자. 우리가 동전이 두개가 있다. 하나는 약간 구부러진 동전(A)이고, 또 하나는 그냥 일반 동전이다(B). 그리고 나는 아래와 같은 data를 받았다.

각 round마다 10번씩 동전을 던지고 앞면(H)가 나온 경우와 뒷면(T)가 나온 경우를 기록한 data이다. 각 round마다 어떤 동전을 사용했는지는 모른다.(이것이 포인트다.) 이 상황에서 각 round가 어떤 동전을 통해서 수행된 것인지 알아보자. 우선 우리는 동전 A에서 head가 나올 확률(pA)을 0.6, 동전 B에서 head가 나올 확률(pB)를 0.5라고 initialize해주자.

pA = 0.6

pB = 0.5

이 상황에서 산수같은 수학을 한번 해보자. 각 round에 대하여 선택된 동전이 A라고 가정할 때, 그리고 B라고 가정할 때의 확률을 구해보자.

round2을 예시로 설명을 해보면, A를 선택했을 때를 가정하면(choiceA), pA = 0.6이고 round2에서 head = 9, tail = 1이었으므로

이렇게 된다. 그러면 이 말은 무엇인가? 0.00403 : 0.00098은 403:98 즉, H가 9가 나오고 T이 1개 나왔을 경우는 동전 A를 사용했을 확률(0.00403)이 동전 B를 사용했을 확률(0.00098)보다 4배정도 높다는 것이다.(참고로 이런 것을 normalization해준다고 한다.) 이 계산을 모든 round에 대해서 해주면 아래와 같다. (여기까지의 작업을 expectation step이라고 한다.)

그러면 이제 normalized pA, normalized pB 확률을 각 round의 H, T count에 곱해주자. 이렇게 하면 동전 A B에 대하여 expected count를 구할 수 있다.

자 이제 우리가 할 일은 마지막에 있는 sum값을 가지고 새로운 확률을 구해보는 것이다.

위의 결과를 보면, A를 던져서 head가 나올 확률이 0.6에서 0.71로 증가했다. B도 이번에 증가했네? 여기까지의 작업을 maximization step이라고 한다.

이제 다음에 해야할 일은, 이 새로운 확률을 가지고 똑같은 일을 똑같이 해주는 것이다. 최초에 pA = 0.6, pB = 0.5를 가지고 했었던 그 일을 계속 반복해준다. 이 작업을 반복해주면 pA와 pB 값이 특정 값에 fix된다고 한다. 그 때까지 반복해주면 된다.

아주 쉬운 포스팅이다. 그런데 이 쉬운 개념이 내가 얼마전에 어려워서 그냥 넘어갔던 forward-backward algorithm의 기본 개념이라고 한다. 다음 포스팅은 이 forward-backward algorithm이다.

cross validation에 대해서 공부해보자. 이 방법은 data mining쪽에서 아주 많이 사용되는 model measurement의 일부이다. 우리가 하나의 model을 build했을 때 그것이 얼마나 좋은 model인지 알기 위해서는 한번의 test만으로는 불가능하다. 여러번 해봐야 된다. 그런데 dataset은 하나. 방법은 k로 나눠서 생각해보는 것이다. 

하나의 데이터를 위와 같이 10개(k=10)로 나누어서 그 중에 하나는 test set으로 사용하고 나머지 9개는 train set으로 사용하는 것이다. 위의 그림에서 보면 1 fold에서 data를 10개로 쪼개서 그 중 하나만(초록색) test set으로 사용하고 나머지 9개(노란색) dataset은 train set으로 사용한다는 것이다. 2-fold에서도 같은 방법으로 하되 첫번째 dataset이 아닌 두번째 dataset을 test set으로 하겠다는 것이다. 그렇게 k번 반복하는 것이다. 이렇게 하면 하나의 dataset을 가지고 k번의 test를 할 수 있다. 그러면 k개의 결과가 나오는데 그거 어떻게 평가할까?

이것이 이번 포스팅의 포인트이다. cross validation measurement에 대하여 설명해보도록 하자. 여기서 하나의 cross validation만 생각해보지 않고 여러 classifier 끼리의 measurement를 생각해보자. (덤으로 각 알고리즘의 평균/표준편차도 구했다)

자 만일 우리가 어떤 classification을 만드려고 하는데 algorithm 1, 2, 3을 써서 10 cross validation을 돌렸더니 위와 같은 Accuracy가 나왔다고 하자. 뭘 써야 할까? 위와 같은 경우에는 사실 굳이 뭐 해볼 필요도 없이 당연히 Algorithm2를 써야된다. 왜냐하면 평균도 가장 높고 분산도 algorithm3에 비해서 낮으니까. 그런데 이거를 어떻게 수학적으로 증명할 것인가? 그것을 알기 위해서 이전에 포스팅했던 confidence level을 이용한다. 본격적으로 confidence level을 통해 어떤 것이 더 좋은지 증명하기 전에 한 가지 내용만 추가해보자. 바로 null hypothesis에 대한 이야기이다.

Null hypothesis는 말 그대로 가정이다. 좋은 예가 있으니 예를 들어서 설명해보자. 가령 미국의 어린이들의 콜레스테롤 수치가 궁금하다. 미국인 전체의 콜레스테롤 수치가 평균:190, 표준편차:15 라고 해보자. 이 상태에서 100명의 어린이를 sampling하여 그 아이들의 콜레스테롤 수치를 측정했더니 그 평균이 198이었다. 이것의 Z값은 어떻게 되는가?

(단, s = 표준편차, x_bar = sample mean, u0 = real mean, n = sample size)

위와 같이 된다. t-value는 test-statistic이라고도 하며 sample에 대한 Z값이라고 생각하면 된다. 아무튼 t-value는 (198-190)/(15/sqrt(100)) = 5.33이 된다. 이 말은 무엇인가?

미국인 어린이의 콜레스테롤 수치를 190으로 기대했을 때, 100명의 sample mean을 봤더니 198이 평균이었다. 그리고 그 t-value가 5.33이라는 엄청 높은 숫자가 나왔다. 이 말은 우리가 선택한 100명의 어린이. 그 sample이 198이라는 평균을 나타낼 확률이 무지하게 작다는 것이다. 그 말은 무엇이냐? 아이들 콜레스테롤 평균을 190으로 가정했을 때, 특정 sample 100명을 실제로 계산해봤더니 198이라는 수치가 나올 확률은 극히 적다는 것이다. 거의 그럴 리가 없다는 것이다. 이 말은 미국인 어린이의 콜레스테롤 수치는 190보다는 높을 것이다라는 말로 귀결된다.

아래의 링크를 참고해보라.

https://www.ltcconline.net/greenl/courses/201/hyptest/hypmean.htm

자 이제 다시 본론으로 돌아가서 아래의 세 algorithm을 분석해보자.

(단, null hypothesis = 0)

null hypothesis를 0으로 놨는데, 이는 각각의 algorithm의 차이를 0으로 가정했다는 뜻이고 그 말은 각각의 algorithm은 차이가 없다고 가정했다는 뜻이다. 그렇게 가정하고 계산을 했을 때 위의 t-statistic이 저렇게 나왔다. 이 값을 t-statistic table을 보면서 각각 분석해보자. 

A1 - A2 : 둘의 차이를 0으로 가정했다. 1-fold에서 10-fold까지 sample의 차이 평균을 구해보니 차이 평균은 -0.965였고 이것에 해당하는 t-statistic은 -2.4477이다. 위의 table에서 찾아보면 이 값은 0.05 - 0.02 사이에 존재한다. 이 말은 100% - (95% ~ 98%)의 확률이라는 것이다. 즉 우리가 선택한 이 sample은 오로지 2~5%에 해당하는 극히 드문 sample이라는 것이다. 따라서 우리가 예측한 null hypothesis "둘 차이는 0일 것이다"는 거짓으로 보는 것이 맞다. 둘 차이의 performance 차이는 명확하고 부호를 따져보면 A2가 훨씬 좋은 것으로 나타난다. 

A2 - A3 : 둘의 차이를 0으로 가정했다. 1-fold에서 10-fold까지 sample의 차이 평균을 구해보니 차이 평균은 0.0295였고, 이것에 해당하는 t-statistic은 0.7308이다. 이 0.7308을 t-statistic table에서 찾아보면 대략 0.5에서 0.4 즉!! 53%정도의 확률로 A2가 더 낫다는 것이다.

A2 - A3 : 생략 -_-

다음 포스팅은 EM algorithm에 대해서 이야기해보도록 하겠다. 아 이거 어려울 것 같은데...

이번에는 통계에 관한 이야기를 조금 해보려고 한다. 아무래도 통계를 전공한 사람은 아니다보니 뭔가 어설플 수도 있으나 이해해 주시라. 이번 포스팅에서 이야기할 내용은 confidence level이다. 

confidence level은 "얼마나 확신하냐?"이다. 예를 들어 내가 턱걸이를 몇 개 하는지 누군가에게 맞춰보라고 했다. 그 사람은 100% 확실한 정답을 말할 수 있을까? 있다!! "너? 한.. 0개에서 1000개 사이하겠지 뭐~" 당연한 이야기이다. 아마도 턱걸이 1000개 이상 할 수 있는 사람은 없을 것이므로, 0개에서 1000개 사이라고 대충 때려 이야기하면 100% 정답이다. 그런데 어떤 사람은 이렇게 이야기 할 수도 있다. "5개에서 10개 사이" 이 사람이 정답일 확률은 어떻게 될까? 아까 100% 보다는 확실히 작을 것이다. 한.. 60%라고 치자. 세번째 사람은 조금 더 디테일하게 이야기한다. "8개에서 9개 사이" 이 사람이 정답일 확률은 더 적겠지? 한 30%?

그렇다 Confidence level은 어떤 값 X가 N%의 확률로 a와 b 사이에 있을 확률을 의미한다. 이제 조금 더 현실적인 이야기를 해보자. 어떤 classifier에 대하여 0.95라는 accuracy가 측정되었다고 해보자. 이 classifier에 대하여 96%에 해당하는 confidence level을 구하라고 하면, 예를 들어 0.93 - 0.98이 될 것이다. 즉 classifier의 accuracy가 항상 0.95가 나오는 것은 아닐 것이다. 그렇지만 어떤 방법으로 계산을 했을 때, 이 classifier는 96%의 확률로 항상 accuracy 0.93에서 0.98을 나타낼 수 있다는 것이다. 다른 말로 말하면 accuracy가 0.93에서 0.98 사이에 나타나지 않을 확률은 4%밖에 안 된다는 것이다.

자 confidence level에 대해서는 이렇게 대략적으로 개념을 잡았으니, 이것을 구체적으로 어떻게 계산하는지부터 설명해보자. 계산법은 아주 간단하다. 

평균을 기준으로 플러스/마이너스 Zn*표준편차를 해주는 것이다. 이 식은 고등학교에서 많이 봤을 것이다. 정규분포 공부할 때 많이 봤을 것이다. 읭? 갑자기 왠 정규분포? 우선 정규분포 이야기를 빼고 위의 평균과 표준편차를 구하는 것에 집중하자. 하나하나씩 구해서 집어넣어보자.

그런데 저 평균을 구하기 위해서 조금 원론적인 이야기부터 해보자. 우선 sample erorr와 true error이다. 말 그대로 sample error는 sample로부터의 error rate이다. 전체 D개의 data에서 n개의 sample을 추출해서 각 N개에 대하여 옳고 그름을 따져보자.

가령 50개의 data에서 5개만 sample로 뽑아서 실제 값(h(x))과 예측된 값(f(x))을 비교했더니 5개 중에 2개 에러가 났다. sample error는 0.4가 되겠다. 그러면 true error는 무엇이냐? true error는 전체 data에서 하나를 random을 뽑았을 때 그것이 misclassify될 확률이다. 뭐 따지고 보면 sample error랑 개념이 비슷하다. 

그러면 우리한테 D개의 동전이 있다고해보자. 여기서 n개를 뽑아서 (n < D) 동전을 던져보자. 앞면이 나올 확률을 p라고 놨을 때, 우리가 기대할 수 있는 평균값은 아래와 같다.

가령 40번 던져서 0.6의 확률로 앞면이 나왔다면 24이라는 expected head count를 얻는데, 이 말은 40번 중에서 평균적으로 24번정도의 앞면을 갖게 된다는 이야기이다. 즉 이것에 평균이다. sample data에서 평균을 구하는 공식은 np가 된다. 분산과 표준편차 공식은 아래와 같다.

p를 그래프로 나타내면 아래와 같다.

여기서 중요한 것을 하나 말해보자. n이 충분히 커지면 위의 값들은 normal distribution(정규분포)의 평균/분산/표준편차와 거의거의 같아진다는 것이다. 즉 n이 충분히 커지면 그 p는 정규분포 형태의 모형을 띈다는 것이다. 그런데 n이 충분히 크다는 것을 어떻게 아냐?

위의 공식을 만족시키는 n에 대하여 정규분포를 이뤘다고 가정하고 평균/분산/표준편차를 sample의 평균/분산/표준편차로 간주하고 계산해도 된다는 것이다. 즉 n이 충분히 크면 sample들 역시 정규분포를 이루게 된다. 자 그러면 confidence level에 대하여 식을 치환해보자. 여기서 평균은 np가 아니라 그냥 p이다. 왜냐하면 각 sample의 평균이 np였고 지금 우리가 구하는 것은 sample들의 평균이므로 np를 n으로 나눠준다. 분산 역시 n으로 나눠줘야 하고 결국 표준편차는 sqrt(n)으로 나눠주게 되는 꼴이 된다. 따라서 아래와 같은 식이 나온다.

마지막으로 Zn은 confidence level table을 통해 확인하면 되는 값들이다.

98%의 confidence level을 구하고 싶으면 2.33을 곱해주면 된다.

자 마지막으로 예를 들어보자. 내 포스팅에 예가 없으면 섭하다.

1000개의 data에서 100개를 뽑아서 classifier를 돌렸더니 80개가 맞았다. 이것에 대한 95% confidence level을 구하면?

p = 0.8

standard deviation = sqrt(0.8*0.2)/10 = 0.04

95% confidence level N = 1.96

confidence level = 0.8 - 1.96*0.04 ~ 0.8 + 1.96*0.04 → 0.7216 ~ 0.8784

이렇게 된다. 후, 내가 아무래도 수학에 기초가 없다보니까 좀 맞나 싶은 내용들도 있을지도 모른다. 이번 포스팅을 할 때는 한글 블로그도 조금 참고했다. 정말 설명 잘 해놓은 블로그 많더라

http://math7.tistory.com/66

http://gongsin.com/bbs/board.php?bo_table=gongsin_column_bbs&wr_id=250458

http://dermabae.tistory.com/184

참고하시길 바라며, 다음 포스팅은 cross validation에 대해서 포스팅할 생각이다.