'전공관련/Algorithm'에 해당되는 글 6건

영상을 이용하다 보면 조명에 의한 영향력을 제거 하고 싶은 경우가 꽤나 빈번하게 발생한다.

근사화에 대한 내용을 보다 보니 언젠가 쓸수도 있겠다 싶은 내용이 있어서 기록.

=============================================================

위 영상과 같은 경우는 조명이 다양하지 않고 한쪽 방향에서만 가해지는 단순한 형태이다.

영상의 형태에 대한 곡면의 방정식을 구하고 이 방정식의 파라미터를 근사화 하면 

조명에 의한 배경을 근사화 할 수 있다

이와같은 곡면에 대한 방정식은 일반적으로 아래와 같다.

임의의 좌표를 샘플링 해서 아래와 같이 방정식의 파라미터를 계산하는 과정이 필요하다.

앞의 x, y 로 구성된 행렬의 역핼렬을 구해 좌우변에 곱해주면 원하는 파라미터를 구할 수 있다.

이제 방정식이 완성 되었으니 식을 이용하여 좌표값을 대입하면 전체 영상에 대한 조명배경을 구할 수 있다.

배경을 구했으니 전경과의 차를 이용하여 원하는 내용만을 남길 수 있겠지. 

물론 실제 어플리케이션에서는 다른 다양한 작업들이 추가 되어야만 사용 가능 할 것이다.

이러한 배경제거를 이용하면 이진화 연산에도 도움을 얻을 수 있다.

원 영상을 일반적인 하나의 임계값으로 이진화 할 경우는 올바른 이진화가 안 될 가능성이 높다.

하나의 임계값을 통해 두개의 영역으로 나뉘는 경우는 일반적으로 별로 없기 때문이다.

아래의 영상과 같이 정보가 날아가는 경우를 확인 할 수 있다.

이런 경우 보다 깔끔한 이진화 결과를 얻을 수 있다.

위의 모든 내용이 출처에 보다 자세히 설명 되어 있음.

원본 그림을 제외한 나머지 영상은 확인을 위해 본인이 계산하여 얻은 결과물임.

원본 그림 출처 : http://darkpgmr.tistory.com/56

배깅과 부스팅이라는 용어를 들어 본 적 있을 것이다.

이 두 개념은 뭔가 유사한 개념 같으면서 또 다른 개념이라 정리가 필요하다.

둘다 학습 샘플을 한번 더 샘플링하여 사용해서 전체 시스템의 신뢰도를 높이는 기법중에 하나이다.

먼저 배깅 (Bagging)

이는 bootstrap aggregating 의 줄임말이라고 한다. 한줄로 잘 설명한 글이 있어서 인용.. ㅋ 

[ 주어진 데이터에 대해서 여러개의 붓스트랩 자료를 생성하고 각 붓스트랩 자료를 모델링 한 후 

결합하여 최종의 예측 모형을 산출하는 방법 ] (인용[1])

위 문장에서 얘기한 대로 전체 Data set 에서 동일한 크기의 random sampling 된 sub sample set을 만든다. 

생성된 sub sample set 마다 각각 학습모델을 만들어 준다. 이때 각 모델은 서로 다른 알고리즘을 적용 할 수도 있다.

각 서브모델에서 생성된 모델을 이용 하여 최종 모델을 생성하는데, 이때 최종 결과값을 도출 하는 방법은 

연속형일경우 평균값을, 범주형일때는 투표를 통해 최종 결과를 낼 수 있다.

그림 1. Bagging 의 system flow

다음은 부스팅(boosting)

일반적으로 부스팅은 약검출기(weak classifier) 들을 여러개 모아 강검출기(strong classifier)를 생성하는 방법을 말한다.

마찬가지로 잘 정리된 문장이 있어서 인용.

[부스팅은 잘못 분류된 개체들에 집중하여 새로운 분류규칙을 만드는 단계를 반복하는 방법] (인용[1])

전체 학습 샘플에 여러개의 weak classifier를 적용한다. 

각 weak classifier를 이용하여 학습모델을 만들고 그 모델을 이용하여 학습샘플을 평가한다.

평가된 결과에 따라 잘 맞춘 weak classifier는 가중치를 더하여주고

잘못 평가한 weak classifier의 가중치는 낮추어 준다.

(19.09.30. 수정. 잘 맞춘 weak classifier는 가중치를 낮추고 틀린 classifier는 가중치를 높여서 전체적으로 성능을 향상시키는 방향으로 업데이트 하는것이 맞음. )

이러한 일련의 과정을 특정 조건이 될때까지 반복하고, 반복이 끝나면 그 때 까지 누적된 

각 weak classifier의 가중치를 이용하여 최종 학습 모델을 만들게 된다.

그림 2. boosting의 system flow

위의 두 그림을 보면 전반적인 형태는 비슷하다.

전체 학습샘플을 일정 크기로 리샘플링 하고 각각의 학습 모델을 만들고, 그들을 이용하여 최종 학습모델을 만든다는점.

boosting의 가장 큰 특징은 다음단계의 weak classifier가 이전단계의 weak classifier의 영향을 받는다는 점이다.

이전의 classifier의 양상을 보고 보다 잘 맞출수 있는 방향으로 다음 단계를 진행하고 각 classifier의 weight를 업데이트 한다.

최종적으로 서로간에 영향을 받아 만들어진 여러 weak classifier와 서로다른 weight를 만들게 되고 이들을 통해 최종적으로

strong classifier를 생성하게 된다.

내가 생각할 때는 bagging과 boosting의 차이점은 각 weak classifier를 생성하는 과정까지가 큰 차이점이고

weight등의 개념은 voting의 문제로 얘들과 별개로 생각해야 할 거 같다..

좀더 공부하고.. 틀린내용 있으면 수정해야지... 

인용[1] : http://blog.naver.com/muzzincys/220201299384

논문을 보던중에 Ferns 라는 Local Descriptor 를 알게 되었다.

Fast Keypoint Recognition in Ten Lines of Code ( 2007, CVPR ) 이 논문에서 처음 나온 개념인 것 같다.

simple binary feature 로 연산속도도 꽤 빠르면서 성능도 잘 나오는 것 같다.

즐겨보는 다크프로그래머 님의 블로그에서 보다 자세히 설명 되어 있으니 참고하는것이 좋겠다.

http://darkpgmr.tistory.com/90

(사실 논문만으론 이해가 거의 되질 않아서 다크님 글 보고 이해한게 대부분.. 허류.. )

논문발표용으로 만든 발표자료 기록용으로 남겨둔다.

PCA에 대해 이해하기 위해 공부하며 정리한 글.

개인적인 이해이므로 정확하지 않을 가능성이 다분... 

우리말로 주성분분석이라 불리는 PCA 는 특징값의 차원을 낮추고 중요한 정보들은 보존하기 위한 방법으로

Feature Space를 변환하여 특징값을 중요도 순으로 구한뒤 이중 일부만을 선택함으로써 차원은 낮추며 정보손실은 최소화 하는 것을 기본 전제로 한다.

이해하기 쉽도록 2차원의 데이터를 가지고 시작.

PCA의 목적이 정보의 손실을 최소화 하면서 차원을 낮추는 것이라 하였으니 2차원의 데이터를 1차원으로 낮춰야 한다.

2차원의 데이터가 1차원으로 낮아지기 위해서는 projection 을 이용한다. 

2차원 상의 데이터를 임의의 한 축으로 projection 하면 2차원의 데이터가 1차원의 데이터로 선형변환 된다.

이때 우리가 알고싶은 것은 선형변환하기위한 무수히 많은 축들 중에서 어떤 축이 기존 특징의 정보를 가장 적게 손실하는가 가 된다.

아래의 그림에서 볼 수 있듯이 여러 축으로 projection이 가능하지만 그 결과는 모두 같지 않다.

두 projection 결과중 왼쪽의 것은 특징값이 일부 overlap 되면서 그만큼 특징값의 정보를 손실했다고 볼 수있다.

반면 오른쪽의 것은 왼쪽의 것에 비해 정보의 손실없이 차원이 낮아진 것을 볼 수있다.

위에서 볼 수 있듯이 정보의 손실이 가장 적은 축은 데이터의 분산이 가장 큰 방향의 벡터값이라고 할 수 있을 것이다.

분산이 가장 큰 방향을 찾기 위해서는 covariance(공분산) 과 eigenvector(고유벡터) 를 이용한다.

원 데이터의 covariance 를 구하고 이들의 eigenvalue에 해당하는 eigenvector를 찾아서 matrix를 구성하면 

이 matrix가 데이터를 projection 하는 변환행렬이 된다.

이때 eigenvalue 는 원 정보의 차원만큼 구할 수 있고 eigenvalue의 값이 클수록 원 정보의 대표적인 정보를 가지고 있는 

더 중요한 값이고 값이 작아질수록 덜중요한 혹은 노이즈 성분이 될 수 있다.

이러한 이유로 모든 eigenvector 를 이용하면 역변환을 통해 원본 정보를 그대로 복원이 가능하고, 중요하다고 판단되는 상위 일부의 정보만을 이용하면 정보의 손실을 최소화 하면서 차원을 줄일 수 있게 된다.

==============================================================================================

아직 PCA에 대한 이해도가 낮아 너무 개념적인 내용밖에 파악하지 못한 상태...

조금더 살펴 보는 걸로 하자.

K Mean Clustering 은 입력샘플을 K 개의 집단으로 군집화 하는 알고리즘 이다.

임의의 시작점을 k 개 만큼 정하고 입력샘플 각각을 시작점과 비교하여 

가장 가까운 점에 소속 시킨다.

입력 샘플이 모두 특점 집단에 소속 되였으면 각 소속에 해당하는 점들의 중심점을 

구한다.

이렇게 구한 중심점을 기준으로 다시 입력샘플과의 거리를 비교, 가장 가까운 

중심점에 다시 소속시킨다.

이렇게 반복하다 더이상 입력집단이 속한 소속이 변하지 않으면 

그때의 그룹들을 k개의 집단으로 군집화 되었다고 한다.

이려한 반복과정은 반드시 수렴하므로 무한루프에 빠질염려는 하지 않아도 되나

전역 최적해 가 아닌 지역 최적 해에 빠질 가능성이 있기때문에 

항상 유의해야 한다.

========================================================================

테스트 프로그램.

임의의 입력점을 생성.

입력받은 k 개만큼의 군집으로 군집화 한 결과.

중심점 으로 맞추기 귀찮아서 그냥 사각형의 왼쪽상단의 점으로 묶어버렸다.. 

코드 몇줄 차인데 보기 아름답진 않군.. 

출처 - http://blog.daum.net/hazzling/15669927 

히든 머커프 모델의 약자인 HMM 

이것은 예측 알고리즘이라 해야하나.. 

일단 공부하다 나온개념인데다 잘 설명되있는것 같아서 저장해둔다.

좀더 공부하고 내 정리된 내용으로 수정해야겠다.

=================================================================

MM과 HMM의 차이점은 상태(state)를 관측할 수 있는가에 달려있다.

날씨나 동전던지기와 같은 사건(event)에서는 쉽게 상태를 알 수 있지만, 그렇지 않는 사건들도 존재한다.

예를 들어,  아래와 같은 문제가 있다고 하자.

이와 같이 3개의 통(상태 1,2,3  -> N = 3)에는 빨간색, 파란색, 녹색 공들이 6개(M = 6)가 들어있는데, 하나의 통에 들어있는 서로다른 색의 공들은 같은 숫자로

들어있지 않다.

이 그림에서 나오는 화살표는 Markov Model에서 처럼 한 상태에서 다른 상태로 전이할 확률(transition probability)이다.

그런데, 각각의 상태에 도착하면 그 상태에서는 빨간, 파란, 녹색 공중 하나를 어떤 확률에 기반해서 뱉어낸다고 한다. 약간 crazy한 콜라 자판기를 생각해도 된다.

3개의 자판기에 빨간, 파란, 녹색 콜라캔이 위의 그림처럼 들어있고, 동전을 넣으면 어떤 확률에 의해서 지맘대로 토해내는 그런 자판기 말이다~

이렇게 어떤 확률에 의해서 콜라를 뱉어내는 자판기는 아래와 같이 generation process로 모델링 할 수 있다.

위 그림에서 ouput process가 바로 어떤 상태 q에서 어떤 ball  x 를 뱉어낼 확률이며 이는 조건부 확률 f(x | q)로 나태낼 수 있다.

그리고  1, 2, 3번 상태에 대한 전이 확률을 알고 있기 때문에 이 부분은 Markov Model을 이용해서 모델링할 수 있을 것이다.

자 그럼 이제 우리는 각 상태로의 전이 확률과 각 상태에서의 생성 확률을 모델링했다.  그렇다면 아래와 같은 문제를 생각해 볼 수 있을 것이다.

블랙박스에는 관측할 수 없는(unobservable) 3개의 상태들이 있고, Markov Process를 따른다. 각 상태에서는 위의 그림처럼 '빨간->파란->파란' 순서로 공들이

출력된다는 것을 관측했다(observed)

이러한 정보로 부터, 우리가 알고 싶은 것은 '과연 감춰진 state sequence는 무엇인가?'일 것이다.

음....  약간 거꾸로 생각해서 만약에 '빨간, 파란, 녹색' 공들 그 자체가 state이고 그들간의 전이 확률을 계산한다면 굳이 근본적인 상태들의 sequence를 알 필요가

없을 수도 있다. 하지만, 우리는 다음에 나올 공에 관심이 있는 것이 아니라 과연 어떤 근본적인 상태가 있었는지에 관심이 있기 때문에, 이런 가정은 필요없다.

아무튼 이 문제를 풀기 전에 우선, 전체적인 Notation을 정리하고 넘어갈 필요가 있다.

여기 기술된 notation은 HMM을 정의이며 문제를 풀기 위한 기본 절차라고 할 수 있다. 앞으로 만약 어떤 문제를 HMM으로 풀고자 한다면, 이와 같이 기본

notation을 정리하고 들어가면 편하겠다.

다음으로 정리할 것은 Markov Model과 generation process를 결합한 그림이다. 이 그림이야 말로, HMM의 핵심이라 할 수 있다.

 이 그림이 나타내는 것은 MM에서도 배웠지만, 일단 기본적으로 Markov Model을 따른다는 것이고, 추가적으로

 어떤 상태 q에서 x를 출력할 확률은 그 이전 상태와는 완전히 독립적이라는 가설이다.

 (conditional independency assumption)

 근데 왜 'Bayesian network' 이라는 말이 있을까? 이는 HMM도 '베이지안 네트웍' 모델링 기법에 그 기반을 두었기 때문인데, 좀더 상위 모델 개념이라고

 이해하고 넘어가자.

 지금까지, 해결하려고 하는 문제를 정의하고 모델링까지 했으니, 이제 진짜 우리가 풀려고 하는 문제를 다시 정의해 보자.

이 그림에서 initial state distribution은 그 첨자가 1 이다. 이는 반드시 HMM의 경우 start state가 존재해야 한다는 의미이다. 그 시작 상태에서 어떤 output을

출력할 확률 분포가 필요한 이유이다.

그러면, 위와 같이 좀더 보기 좋게 정리된 문제를 가지고 우리는 실제 어떤 문제를 풀어야 할까? 

아래 그림에 잘 정리가 되어 있다.

첫째, 관측된 output들이 sequence에 대한 확률이다. 이건 약간 Markov Model을 계산할 때와 비슷해 보인다.

        ==> 다른 점은 모델 파라미터 '람다'가 들어가 있는 것이다.

둘째, 관측된 output sequence를 가지고 가장 그럴 듯한 state sequence를 찾아내는 것이다.

        ==> 사실 진짜로 알고 싶은 것은 바로 이것이다.

셋째, 학습에 관련된 이슈인데, 이는 학습 데이터를 가지고 있는 상태에서 모델 파라미터 '람다'를 적절하게 결정해야 할 필요가 있기 때문에

        학습 알고리즘을 통해서 '람다'를 최적화 해야 한다.

지금부터 기술되는 것은 이 세가지 문제를 푸는 방법이다. 관심없는 분은 넘어가시길 바란다. 좀 복잡하니....

이제 첫번째 문제를 해결해 보자.

음... 먼가  Markov Model을 풀 때와 비슷해 보이지 않는가?  output sequence가 x1 ~ x8 일때 그에 대응하는 state sequence Q는 엄청나게 많다.

하지만, 확률로 표현하면, 전부 OR 이기 때문에 단순히 더하면 된다. summation 안에 들어가 있는 수식은 조건부 확률을 Bayesian Theorem에 의해서

뒤집은 결과이다. 이 수식을 어떻게 계산할까?  머리가 약간 아플 수도 있지만  하나의 Q = q1 ~ qT에 대해서만 생각해 보면,

아주 위쪽에서 그려진 Bayesian network representation을 이용해서 아래와 같이 풀어 쓸 수 있다. 그리고 이 결과를 계산하면 된다.

하지만,  이것도 Markov Model처럼 DP 기법(수학적 귀납법을 생각)을 사용하면, 아래와 같이 빠르게 계산할 수 있다.

즉, 시간 t 에서의 확률은  시간 t-1 에서의 확률을 알면,  t-1 에서 t 까지의 모든 path만 고려해면 된다는 이 엄청나게 깔끔하고 단순한 수식!!!

멋지다 @.@

아무튼 이 수식에 Forward Algorithm이라는 말이 들어간 것은 계산 순서가 1부터 t까지 순차적으로 계산하기 때문에 그런거고 별 의미는 없다.

다시한번 정리하면

 DP 기법에서 자주 나오는 notation인데, 다시 한번 숙지하고 넘어가자. DP는 아래와 같이 구성되어 있다.

1. initialization

    - 고등학교때 수열 문제 풀때, 초기 a1, a2 등등을 지정하고 가는 것 처럼 초기값 설정

2. induction

    -  a(n)과 a(n-1)의 관계를 수식으로 표현

    - 그래서 귀납법(induction)이다.

    - 그래서 deduction이 아니다.

3. termination

    - 계산하려고 하는 대상이 a(100) 인 경우, a(101)은 계산할 필요가 없다. 그래서 종료 조건이 반드시 필요하다.

    - 프로그램으로 작성한다고 생각하면 recursive call이 되겠는데, 여기에 종료 조건이 없으면 무한루프에 걸리니까...

다시 원래 문제로 돌아가서, '아니 그럼 forward algorithm'이 있으니 'backward'도 있겠네? 하시는 분도 계실 것이다. 그렇다!

backward 방향으로 계산하면 똑같다. 다만, 초기 상태까지 와 봐야, 그 중간에 저장된 확률 값들을 알 수 있다는 단점이 있다.

 아무튼, 자 ~ 이제 첫번째 문제는 해결된 셈이다.  이젠 어떤 output sequence가 주어져도 그 확률을 계산할 수 있다.

 다음으로, 두번째 문제를 풀어보자. 관측된 output sequence로부터 가장 그럴듯한 state sequence를 구하는 문제인데, 

 most probable  sequence decoding이라고도 한다. 즉, 아래와 같은 문제이다.

 위 수식에서  argmax 는 해당 확률 값을 최대로 하는 state sequence Q를 찾는다는 의미이다.

 이 문제를 해결하는 데, 가장 잘 알려진 알고리즘이 바로 Viterbi Algorithm이다. 이것도 DP 방법을 사용해서 문제를 해결하는데,

 관점은 지금까지와는 조금 다르게, path의 확률을 계산하는 데 초점이 맞춰져 있다.

 단순하게 생각하면 시간 t의 여러개의 상태에서 시간 t+1의 어떤 상태 q(j)로 오는 path는 상태의 숫자만큼 존재한다. 그런데, 여러개의

 path에서 어떤 path로 오는 것이 가장 그럴듯 한가? 라는 문제를 생각해 보면, 아래와 같이 두가지를 고려해야 한다.

 1. t의 어떤 상태에서 t+1의 상태 q(j)로의 전이 확률  : a(i,j)

 2. q(j)에서 관측된 output x(t+1)의 확률 : b(j, x(t+1))

 즉, 이 두가지 확률을 곱한 값이 최대가 되는 path를 선택하면 된다.

 이 문제를 DP 문제로 확대시켜서 수학적 귀납법으로 표현하면 아래와 같이 되는 것이다.

 위에서 path probability는 잘 알겠는데, 그럼 path node는 먼가?  이는 path probability에서 destination의 output 확률을 제거하고

 , 그 확률이 최대가 되는 이전 상태이다.  현재 어떤 output이 있는 지 고려하지 않고 계산한다.

음...?  그런데 여기서 path backtracking은 무엇인가?  HMM을 공부할때, 자주 하는 착각중에 하나는 바로

'그럼 처음 상태에서 다음 상태로 가는 path 중에서 path probability가 가장 높은 path를 선택해고, 선택된 그 상태에서 다음으로의 path들을

 계속해서 선택해 나간다면 최종적으로 가장 그럴듯한 path가 나오는 게 아닌가?' 이다.

 답은 '아니다' 이다. 이 방법은 그냥 단순히 local search를 하는 것 뿐이고, viterbi algorithm은 global search를 하는 알고리즘이다. global search는

 모든 가능한 path를 전부 계산하기 때문에 너무 시간이 오래 걸린다. local search는 그냥 단순하게 현재 눈앞에 가장 이득인 놈을 선택해서 탐색하는 방법으로

 greedy search라고도 한다. '탐욕스런 탐색'이라니~ 정말 이름 잘 지었다!!  사설이지만, 우리의 인생의 방향을 선택할때도 가끔 이러지 않을까?

 아무튼, viterbi algorithm은 가장 optimal한 path를 선택해야 하기 때문에 끝까지 가본 이후, 마지막 상태부터 거꾸로  back tracking을 하면서

 가장 확률이 높게 나오는 이전 state를 선택해 가면서 처음 상태로 되돌아 가야 최종적인 결과가 나오는 알고리즘이다.

 그래서 path backtracking 공식이 있는 것이고...  위 그림에서 화살표가 거꾸로 되어 있는 이유도 이것 때문이다. ^^

 자 이제 여기까지 왔으면, HMM으로 모델링 된 어떤 문제에서 output sequence를 알면 대응되는 state sequence를 계산할 수 있겠다.

 대단하지 않은가?

 이제 마직막으로 세번째 '모델 학습'에 관련된 문제만 해결하면 되는데, 그러기 전에 우선 NLP에서는 어떤 응용이 있는 지 먼저 살펴보고 넘어 가자.

 NLP 분야에서 HMM이 쓰이는 대표적인 모듈은 POS(Part-of-Speech) Tagger이다. 즉, 아래와 같은 문제이다.

 [출처] 부산대학교  한국어 정보처리 연구실 - 품사태거 - 정성원 

 한국어 형태소 분석기는 어떤 어절에 대해 가능한 모든 형태소 분석 결과를 출력해 준다. 하지만, 우리가 필요한 것은 이중에서 진짜로 문맥에 맞는 형태소 분석

 결과이기 때문에, 이 문제도 HMM으로 모델링해서 해결할 수 있다.

 어절을 output , 형태소 조합을 state라고 한다면 HMM에 쉽게 대응해 볼 수 있을 것이다.

 태거를 HMM으로 모델링한다면, output과 state는 얼마나 될까?  일단 state는 그렇게 많지 않다. 형태소 분석기 내부에는 하나의 어절에 대해 구성 가능한

 형태소 결합 규칙을 기술해 두는데, 이 규칙의 수가 state의 수가 될 수 있다. 하지만, output의 숫자는 엄청나게 많다. 따라서, 일반적으로 태거를 구현할때는

 형태소 분석단계에서 최대한 분석의 수를 줄인 이후에 태거에서 HMM 기법을 통해 가장 적합한 품사를 결정한다. 즉, 중의성이 있는 어절들에 대해서만

 가능한 형태소 분석 결과를 출력하고, 그렇지 않은 경우는 고려하지 않는다.

 어쨌든, 이러한 품사 태거를 만들기 위해서는 대용량의 품사태깅된 학습 말뭉치가 필요한데, 이 말뭉치는 보통 아래와 같이 생겼다.

 나는 학교에 간다   -->   나/대명사+는/조사  학교/보통명사+에/조사  가다/동사+ㄴ다/종결어미

 하늘을 나는 새를 보았다 -->  하늘/보통명사+을/조사  날다/동사+ㄴ/관형형어미  새/보통명사+를/조사 보다/동사+았/선어말어미+다/종결어미

 .....

 우리는 이러한 학습 말뭉치를 가지고  상태전이확률(품사간 전이 확률, 편의상), 생성확률(어휘 생성 확률)을 계산할 수 있다.

 다시 본론으로 돌아가서, 세번째 문제는 모델의 파라미터를 학습 데이터로부터 최적화하는 것인데, 품사 태거를 학습시키는 문제에 적용해 보면 확률 데이터를 좀더

 정교한 방식으로 계산해서 얻겠다는 의미도 될 수 있다. 어떤 품사에서 출력되는 output의 숫자는 엄청나게 많아서 학습시킬 때 언제나, 데이터 부족 문제

 (data sparseness problem)가 생기는 것은 피할 수 없다. 즉, 관측된 데이터만으로는 관측되지 않은 확률 값을 계산하는 데 심각한 문제가 있다는 의미이다.

 이러한 문제를 해결하기 위해서 보통 우리가 하는 일은 "모델을 잘 만든다" 이다.

 조금 우습지만 이게 정답이다. 잘 만들어진 모델이 있으면, 잘 모르는 확률도 해당 모델을 기반으로 해서 좀 더 그럴듯하게 근사값을 계산할 수 있다.

 아주 대표적인 예가 있는 데, 바로 '정규분포(standard distribution)'이다. '학교 성적, 인구 분포 등등의 현상은 대부분 정규분포에 근사한다' 라는 게 우리의 가설이고

 이를 모델링한 것이 바로 정규분포이다. 따라서, 우리는 모든 사람을 일일히 호구조사하지 않아도 대충 몇살부터 몇살까지 몇명이 있는 지 근사값을 계산할 수

 있는 것이다. 그러니, 잘 모르면 모델을 잘 만들면 된다. 사설이지만, 가장 완벽한 모델은 무엇일까? 음... 바로 수학이다!!  한치의 오차도 없는 완벽한 모델 ^^

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

[여기서 잠깐]

Q) 위와 같은 품사 태깅된 말뭉치가 있는 경우에도 파라미터 '람다'를, 좀더 정확히 말하면 state transition 파라미터를, 학습시켜야 하나?

A) Linguist's Guide to Statistics [참고 : http://blog.daum.net/hazzling/16884279]

    여기에 보면 아래와 같은 내용이 나온다.

   즉, "underlying state sequence는 unknown이고 오직 signal sequence 즉, output sequence만 학습데이터로 가지고 있는 경우에만

    state transition probability parameter를 Baum-Welch reestimation 알고리즘 등을 이용해서 추정한다"

   따라서, '그럴 필요 없다'가 정답이다. 다만,  품사조합(state)들 간의 transition 데이터가 좀 부족하면 보정작업등을 해서

   학습 데이터의 부족문제를 약간 해결할 수 있을 것이다.

   아래에서 언급되는 내용은 우리가 오직 output sequence만을 학습 데이터로 가지고 있는 경우에 어떻게 state transition에 관한

   정보를 끄집어 낼 것인가에 대한 것이다.

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

 아무튼, 우리는 관측된 데이터만 가지고 모든 상태전이확률, 생성확률을 잘 구할 수 있도록 모델을 구해야 하며, 이것이 지금부터 언급될 내용이다.

 보통 HMM의 파라미터 '람다'라 하면 아래 3가지를 의미한다.

 1. 상태전이확률  : A

 2. 생성확률 : B

 3. 초기확률 : py

 따라서,  람다 = ( A, B, py )  이렇게 표현하고  실제 우리가 관측한 데이터를 X 라고 한다면,

 우리가 만들려고 하는 어떤 모델은 '람다'를 조건으로 할때, 관측 데이터 X를 가장 잘 표현해야 한다. 이런 종류의 문제는 Likelihood 를 최대한 높여야 한다고

 보통 얘기하는데, 잠깐 Likelihood에 대해서 알고 넘어가자.

 예를 들어서, 동전던지기 사건에서 앞면이 나올 확률 p를 동전던지기 사건 모델의 파라미터라고 하고, 1000번 던저 나온 결과값 즉, 관측 데이터를 우리가 가지고

 있다고 하자. 1000번의 550번은 앞면, 450번은 뒷면이 나왔다. 자~ 그럼 어떻게 하면 확률 p를 가장 잘 결정할까? 일단 p = 0 으로 해보자.

 엥?  만약 그렇다면 관측한 데이터와 완전히 동떨어진다. 그럼 p = 1 로 하면?  역시 마찬가지다. p = 0.5 로 해도 관측된 데이터와는 조금 미스매치다.

 그래서 관측데이터를 가장 잘 표현할 수 있도록 조금씩 p값을 앞뒤로 조정해 나가면 p = ( 550 ) / ( 1000 ) = 0.55 로 결정된다. 이런 조정 작업이 바로

 모델 파라미터 학습이라고 하고, 여기서 사용된 개념이 바로 'Likelihood를 최대로 해서 모델 파라미터를 결정한다'는 것이다.

 그런데, 관측데이터에 너무 지나치게 모델 파라미터를 학습시키면 어떨까? 사실 동전을 많이 던지면 p 는 0.5에 접근한다. 실험을 적게하면 Likelihood로

 계산한 모델 파라미터 p는 0.1일 수도 있다. 이것이 보통 우리가 얘기하는 overfitting 되었다는 것이고, 거꾸로 생각하면 학습 데이터가 부족하다는 것이다.  

 (data sparseness problem)

 기계학습의 아주 기초적인 개념이 사실 고등학교때 배운 동전던지기 확률 모델에 거의 다 들어있다는 것을 요새 새삼 깨닫게 된다 @.@

 다시 파라미터 학습 문제로 돌아가면, 결국 Likelihood를 최대화하도록 람다를 학습시켜야 하는데 이를 수식으로 풀어내면 위의 그림과 같다.

 P( X | 람다 ) 는 3가지 문제 중에서 첫번째 문제를 해결할 때, 위의 수식처럼 summation 형태로 바꿀 수 있는데, P( Q | 람다 ) 는 state transition이

 숨겨져 있어서 구하기 어렵다. 따라서, estimation을 해야 한다. 그럼 어떤 방법을 사용해야 할까? 

 일반적으로 이런 문제에서는 EM(Expected Maximization) 알고리즘을 사용한다. EM도 결국 Likelihood를 최대화 하도록 파라미터를 학습시키는

 방법론이라고 할 수 있는 데, 좀더 잘 정리되어 있다는 점이 다를 뿐이다.

 ( 위에서 기술된 Baum-Welch reestimation은 EM 프레임웍을 HMM에 최적화시킨 알고리즘이다. )

 EM 알고리즘 참조 ==> http://blog.daum.net/hazzling/17067790

 잘 이해하기 힘든 그림이다.  이것 말고, 다른 문서를 참고하자.

 Linguist's Guide to Statistics [참고 : http://blog.daum.net/hazzling/16884279]

 여기에 있는 HMM chapter를 보면

 output sequence  =  o1, o2, .... , oT

 이런 관측 데이터가 있을 때,

 time (t)의 상태가 si 이고

 time(t+1)의 상태가 sj 일 조건부 확률을 아래와 같이 정의할 수 있는데,

 이 확률 값은  forward, backward probability의 조합으로도 표현할 수 있다.  

 그리고,

 가장 아래 부분은 관측렬이 아래와 같고

 output sequence  =  o1, o2, .... , oT

 time ( t ) 일때 상태가 si 일 확률은 

 partition 이론으로 부터, summation으로 풀어쓸 수 있고

 이 풀어쓴 결과가

 결국

 위 그림의 마지막 라인과 같다는 것을 알려준다.

 이것으로 부터 아래와 같은 4가지 fact를 추출할 수 있다.

 0) time 1 에서 상태 si 로 시작할 확률값

 1) si --> sj 로 transition하는 횟수의 평균값

 2) si 로부터 어떤 다른 상태로의 transition 횟수의 평균값

 3) si 에서 어떤 시그널(output)을 뱉을 평균 횟수

 그리고, 위에서 나온 fact를 이용해서,

 초기 py 값 :  time 1 에서 각각의 상태 si로 시작할 확률값

 pij   :  ( time 1 ~ T-1  사이에서 si -> sj transition 평균값 )  /   (  time 1 ~ T-1 사이에서 si 로 시작하는 transition 평균값 )

          이것이 바로  si --> sj  전이 확률의 평균값(기대값)

 aij   :  ( time 1 ~ T 사이에서 상태 si가  signal(j)를 출력할 평균값 ) / ( time 1 ~ T 사이에서 si 로 시작하는 transition 평균값 )

  이와 같이 모델 lamda를 계산할 수 있다.

  우리가 만약 어떤 m개의 관측 데이터를 가지고 있다고 하자.

  o11  o21  o31 ....  oT1

  o12 o22  o32 ....  oT2

  .........

  o1m o2m  o3m ....  oTm

  BW 알고리즘은 이것으로 부터 transition proability를 추정해 내는 알고리즘이라 할 수 있는데,

  그럼 우선 어떤 것을 먼저 설정해 줘야 할까?

  일단, number of state ( N ) 값과 number of observation ( M ) 값을 설정해야 한다.

  M 값은 관측 데이터로 부터 자연스럽게 설정되고

  N 값은 미리 알고 있다고 가정하자 ( 문제의 종류에 따라 다르다.)

  초기 시작 상태에서의 emission probability py는 그냥 대충 설정해 주면 된다. 합이 1이 되도록....

  마지막으로, transition probability aij, emission proability pij 도 랜덤하게 설정해 둔다.

  이 상태의 모델이 바로 lamda(0)

  자 이제 이러한 상태에서, 위의 그림에 나온 공식을 사용해서 계속 parameter를 최적화하는 작업을 진행해야 한다.

  위의 공식을 뜯어보면, 결국 최종적으로 forward, backward probability(variable)을 알아야 계산 가능하다는 것을 알 수 있다.

  그렇다면, forward, backward 확률은 어떤 순서로 계산하는가?

  forward는 기본적으로 time 1에서 먼저 계산하고 그 다음 time 2, 그리고 그 결과를 이용해서 time3 ...

  이런 식으로 해서 최종적으로 time T 까지 계산한다.

  backward는 forward와는 반대로 time T 부터 계산하고 거꾸로 time 1 까지 가면서 계산한다.

  ( 물론, time T에서는 초기값은 확률 합이 1이 되도록 임의로 설정해 둔다)

  이러한 과정을 통해서 alpha(t), beta(t) 값을 전부 어떤 테이블에 저장해 두고 사용한다.

  아래 그림을 보자.

  [reter to] http://nlp.korea.ac.kr/~kshan/resources/AlgorithmsForHMM.ppt

 초기에 initial guessing을 통해서 설정된 전이확률 및 생성확률을 가지고

 alpha, beta를 계산하고

 이를 이용해서 다시  아래를 계산한다.

  그러면 전이확률 및 생성확률, 초기확률이 변화할 것이다.

   또, 변화된 모델에서 alpha, beta를 구한다.

   이 과정을 아래 그림과 같이 반복한다.

   [refer to]  http://www.facweb.iitkgp.ernet.in/~sudeshna/courses/ml08/hmmkanungo2.pdf 

  아... 이제 무한루프에서 탈출한 기분 ^^

  그런데 이러한 BW 추정에도 단점이 있다.

  [reter to] http://nlp.korea.ac.kr/~kshan/resources/AlgorithmsForHMM.ppt