Dirichlet Process (DP)

Posted 2013.07.05 12:50

Dirichlet Process (DP)는 매우 복잡스러운 수학의 결과가 우리의 직관과 맞을 수 있다는 것을 보여주는 좋은 예라 할 수 있겠다. 


 DP는 그 이름에서 알 수 있듯이 Dirichlet distribution을 따르는 random process이다. Random process라 함은 시간에 따라 특정 분포를 따르는 Random variable들의 sequence라 생각할 수 있다. 나 개인적으로는 특정한 Probability allocation function을 갖는 Sample space에서 임의로 random variable들을 뽑는다는 개념을 좋아한다. 물론 RP에 시간에 따른 함수를 추가할 수 있기 때문에 정확한 정의는 아니다. 


 각설하고 DP는 unsupervised clustering에 많이 사용된다. 특히나 우리가 cluster하고 싶은 cluster의 수를 모를 때! 사용될 수 있는 장점이 있다. 유도 과정은 매우 복잡하니 생략을 하겠다. (사실 나도 따라갈 수만 있고 유도는 못하겠다..)


 DP를 이해하기 위해서는 Dirichlet distribution에 대해서 알아야 한다. Dirichlet distribution은 simplex에 대한 분포를 갖는다. n차원의 simplex의 정의는 모두 양수이고 sum이 1인 n차원의 벡터를 의미한다. 이러한 벡터는 multinomial distribution의 parameter로 쓰일 수 있다. (각 n개의 공이 뽑힐 확률로 이해될 수 있다.) 그래서 Dirichlet distribution을 따라다니는 수식어가 바로 distribution over distribution이다. 거창하게 들리지만 사실 multinomial distribution의 파라미터로 쓰일 수 있다는 말이다. 


 이러한 DP가 중요해지는 이유는 multinomial distribution이 대부분의 mixture model의 기본이기 때문이다. 다시 말해서 우리가 임의로 설정한 basis distribution의 weight를 Dirichlet random variable로 놓을 수 있다는 말이다. 하지만 이 경우에는 Dirichlet distribution의 dimension이 고정되어 있어서 cluster의 수를 모르는 경우에 사용되기가 힘들다. 

 

 그래서 아래 논문에서는 Dirichlet process란 것을 제안했고, 이는 내부적으로 Dirichlet distribution의 dimension을 바꿀 수 있게 되어있다. 이는 Chinese restaurant process라고도 불린다. 원탁 테이블을 갖는 중국집에 사람이 계속 들어올 때 사람이 cluster하고자 하는 개별 data이고, 테이블을 cluster하고자 하는 묶음이 된다. 


 각설하고 식을 써보면 다음과 같다. 

이게 정말 잘 동작하는지 시뮬레이션을 통해서 결과를 확인해보자. Likelihood는 각 cluster의 center를 mean으로 하는 multivariate Gaussian 분포를 따른다고 가정하였다. 간단하게 하기 위해서 분산은 모두 상수로 하였다. 

 


 실험 결과는 다음과 같다. (왼쪽이 임의로 만든 데이터, 오른쪽이 DP-GMM으로 구한 cluster)



 위의 동영상이 좀 깨지긴 하지만 처음에 cluster의 수를 제대로 몰라도 결국 비슷하게 찾아가는 것을 알 수 있다. 


 DP prior 부분에 $\alpha$ 가 들어가는데 이 변수가 중요하다. 결론부터 말하자면 이 값이 클 수록 새로운 cluster가 많이 생긴다. 작으면 작을 수록 새로운 cluster가 잘 생기지 않는다. (오히려 잘 준다.)


실험에 사용된 매트랩 코드 

1. demo_dp_gmm


2. demo_make_video_dp_gmm


+ Hyper-parameter alpha를 구하는 부분 추가

 위의 논문에 보면 alpha에 대한 conditional distribution이 나온다. 이식을 Gibbs sampling을 통해서 풀 수 있다. 

 Conditional distribution은 다음과 같다. 

 





   

  1. 수진

    | 2014.01.12 20:59 | PERMALINK | EDIT | REPLY |

    DP 동작 원리에 대해서
    데이터 특성이 어떻게 반영되는지가 궁금했는데,
    class specific-liklihood가 계산되어 반영되는군요~

    도움 많이 되었습니다!!

    코드 중간에
    % j-번째 class가 총 몇개가 할당되었는지 구한다.
    n_j = sum(find(dp.class==j));
    -> n_j = length(find(dp.class==j));

    로 변경되어야 할 것 같습니다~
    데이터 갯수를 return해주는 것이 아니라
    윗줄은 데이터의 index를 sum하는 것이더라구요 :)

    p.s alpha는 지금보다 적당히 하향조정하면 잘 작동합니다

  2. samchoi7@gmail.com

    | 2014.01.12 22:34 | PERMALINK | EDIT | REPLY |

    아 그렇군요! 감사합니다. ㅎㅎ
    alpha는 문제가 좀 있는거같아요.. 실제로 저 posterior로 sample을 하면 잘 안될 때가 많아요.. DP가 재밌는 알고리즘인 것은 확실한 것 같아요.

Write your message and submit
« PREV : 1 : ··· : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 87 : 88 : ··· : 142 : NEXT »