- 2014 년 5 월 20 일
- 바실리스 브로 니 오티스
- . 코멘트가 없습니다
이 기사는 Dirichlet Process Mixture Models로 클러스터링에 대한 시리즈의 세 번째 파트입니다. 이전에는 Dirichlet Distribution을 기반으로 유한 혼합물 모델을 정의했으며이 특정 모델을 무한하게 만드는 방법에 대한 질문을 제기했습니다. 우리는 k 개의 군집이 무한대 인 경향이있을 때 모형의 한계를 취하는 아이디어에 대해 간단히 논의했지만 그러한 물체의 존재가 사소한 것이 아니라고 강조하면서 (즉, 실제로 어떻게 모형의 한계를 취하는가? "?). 다시 말해, 우리가 k를 무한대로 만들고자하는 이유는 이런 방식으로 데이터 내의 총 군집 수를 미리 정의 할 필요가없는 비모수 적 모델을 가지기 때문입니다.
업데이트 : Datumbox Machine Learning Framework는 이제 오픈 소스이며 무료로 제공됩니다. 다운로드. com.datumbox.framework.machinelearning.clustering 패키지를 확인하여 Java에서 Dirichlet Process Mixture Models의 구현을 확인하십시오.
비록 우리의 목표는 데이터 세트에서 클러스터링을 수행 할 수있는 모델을 구축하는 것이지만 그 전에 Dirichlet Processes에 대해 논의해야합니다. 우리는 엄격한 수학적 정의와 DP에 대한보다 직관적 인 설명을 제공하고 프로세스를 구성하는 방법을 논의 할 것입니다. 이러한 구성 / 표현은“실제”에서 Dirichlet Process의 발생을 찾는 방법으로 볼 수 있습니다.
이 블로그 게시물을 쉽게 찾을 수 있도록 연구 보고서를 조정하려고 했음에도 불구하고 모델을 사용하기 전에 필요한 수학적 도구와 분포를 정의하는 것이 여전히 중요합니다. Dirichlet Process 모델은 활발한 연구 주제이지만 통계 및 확률 적 프로세스를 사용하기 전에 이해해야합니다. 또 다른 문제는이 기사에서 볼 수 있듯이 Dirichlet Processes는 다양한 방법으로 표현 / 구성 될 수 있다는 것입니다. 결과적으로 몇몇 학술 논문은 완전히 다른 표기법 / 협약을 사용하고 다른 관점에서 문제를 조사합니다. 이 게시물에서는 가능한 한 간단하게 설명하고 동일한 표기법을 사용하려고합니다. Dirichlet Process Mixture Models의 정의와 실제로이를 사용하여 클러스터 분석을 수행하는 방법에 중점을 둔 다음 두 기사를 통해 상황이 더 명확 해지기를 바랍니다.
1. 디리클레 프로세스의 정의
Θ 공간의 디리클레 프로세스는 확률 적 프로세스입니다. 이것은 "Θ 공간에 대한 확률 분포"에 대한 확률 분포이며 그것에서 분리는 개별 배포판입니다. 보다 공식적으로 Dirichlet Distribution은 확률 측정에 대한 분포입니다. ㅏ 확률 측정 는 공간 Θ에서 [0,1]의 부분 집합의 함수이다. G는 DP 분포 랜덤 확률 측정치이며 
파티션의 경우 (A1,…ㅏn)의 공간 Θ 
.
그림 1 : 유한 파티션의 한계는 Dirichlet으로 배포됩니다.
DP에는 두 개의 매개 변수가 있습니다. 첫 번째는 기본 분포 G입니다.0 그것은 평균처럼 제공 
. 두 번째는 엄격하게 양수이고 역 분산과 같은 강도 매개 변수 α입니다. 
. 출력 분포 값의 반복 범위를 결정합니다. a의 값이 클수록 반복은 더 작아집니다. 값이 작을수록 출력 분포 값의 반복이 높아집니다. 마지막으로 Θ 공간은 DP를 정의하는 매개 변수 공간입니다. 또한 공간 Θ는 G의 정의 공간이기도합니다.0 이것은 G의 것과 동일합니다.
더 간단하고 더 직관적 인 방법 디리클레 프로세스를 설명하는 것은 다음과 같습니다. 유한 한 방식으로 분할 할 수있는 공간 Θ가 있다고 가정합니다 (A1,…,ㅏn) 및 확률을 할당하는 확률 분포 G입니다. G는 Θ에 대한 특정 확률 분포이지만 다른 것들도 많이 있습니다. Θ의 디리클레 프로세스는 정확히 이것을 모델링합니다. 그것은 공간 Θ에서 가능한 모든 확률 분포에 대한 분포입니다. Dirichlet 프로세스는 G로 매개 변수화됩니다.0 기본 기능 및 α 농도 매개 변수. 우리는 매개 변수 α와 G를 가진 DP에 따라 G가 분포되어 있다고 말할 수 있습니다.0 G가 Θ의 파티션에 할당 한 확률의 공동 분포가 디리클레 분포를 따르는 경우. 또는 G가 Θ의 유한 파티션에 할당하는 확률은 Dirichlet Distribution을 따릅니다.
그림 2 : Dirichlet 프로세스의 그래픽 모델
마지막으로 우리는 볼 수 있습니다 DP의 그래픽 모델. α는 스칼라 하이퍼 파라미터 G입니다.0 DP의 기본 분포, G는 DP에서 샘플링 된 Θ 매개 변수 공간에 대한 임의 분포, 매개 변수에 확률을 할당합니다.i 는 G 분포에서 도출 된 모수 벡터이며 Θ 공간의 요소입니다.
2. 후방 디리클레 프로세스
사후 디리클레 프로세스는 다음과 같이 논의되었습니다. 퍼거슨. Dirichlet Process에서 랜덤 확률 측정 G를 그려서 시작합니다. 
. G는 Θ에 대한 확률 분포이므로이 분포에서 표본을 추출하고 독립적으로 동일하게 분포 된 표본을 추출 할 수 있습니다.1,…, θn ~ G. Dirichlet Process의 추첨은 이산 분포이므로, 우리는 
어디에 
짧은 표기법이다 
다음과 같은 경우 1을 취하는 델타 함수입니다. 
다른 곳에서는 0입니다. 이것의 흥미로운 효과는 G가 이런 식으로 정의 되었기 때문에 동일한 값을 가진 다른 샘플이 양성일 가능성이 있다는 것입니다 
. 나중에 볼 수 있듯이, 이는 데이터 세트에 대한 군집 분석을 수행하는 데 사용할 수있는 군집 효과를 만듭니다.
위의 정의와 관찰을 사용하여 샘플 θ가 주어진 Dirichlet Process의 후부를 추정하려고합니다. 그럼에도 불구하고 우리는 그것을 알고 있기 때문에 와 
Bayes 규칙과 Dirichlet과 Multinomial 간의 Conjugacy를 사용하여 
와 
.
방정식 1 : 후방 디리클레 프로세스
이 속성은 매우 중요하며 다양한 DP 표현에 사용됩니다.
3. Dirichlet Process 표현
이전 세그먼트에서 우리는 Dirichlet Process를 정의하고 이론적 모델을 제시했습니다. 우리가 대답해야 할 중요한 질문 중 하나는 그러한 대상이 존재한다는 것을 어떻게 알 수 있으며 구성 및 대표 디리클레 프로세스.
존재의 첫 징후는 퍼거슨 콜 모고 로프 일관성 정리 (Kolgogorov Consistency Theorem)를 사용하여 디리클레 프로세스 (Dirichlet Process)를 정의하고 사후 디리클레 프로세스 (Postior Dirichlet Process)를 설명했습니다. 그의 연구를 계속하면서 블랙웰과 맥퀸 De Finetti의 정리를 사용하여 이러한 확률 확률 측정의 존재를 증명하고 Dirichlet Process의 특성을 만족시키는 Blackwell-MacQueen urn 체계를 도입했습니다. 1994 년 세스 후라 만 Stick-breaking 구조를 도입하여 DP를 구성하는 간단하고 직접적인 추가 방법을 제공했습니다. 마지막으로 또 다른 표현이 제공되었습니다 더스 Dirichlet Process를 구성하는 효과적인 방법으로 Chinese Restaurant Process를 소개했습니다.
Dirichlet Process의 다양한 표현은 수학적으로 동일하지만 다른 관점에서 문제를 검사하기 때문에 공식이 다릅니다. 아래에서 우리는 문헌에서 발견 된 가장 일반적인 표현을 제시하고 Dirichlet Process에 대한 추론 알고리즘을 구성하는 간단하고 계산적으로 효율적인 방법을 제공하는 Chinese Restaurant Process에 중점을 둡니다.
3.1 Blackwell-MacQueen 항아리 구성표
Blackwell-MacQueen 항아리 구성표를 사용하여 Dirichlet Process를 나타낼 수 있습니다. 블랙웰과 맥퀸. 그것은 교체없이 반대의 샘플링 모델로 볼 수있는 Pólya urn 방식을 기반으로합니다. Pólya urn 체계에서 우리는 색깔이있는 공을 포함하는 투명하지 않은 항아리가 있다고 가정하고 무작위로 공을 그립니다. 우리가 공을 그릴 때, 우리는 그 색깔을 관찰하고, 그것을 다시 항아리에 넣고, 같은 색깔의 공을 더 추가합니다. Dirichlet Process를 구성하기 위해 Blackwell과 MacQueen도 비슷한 방식을 사용합니다.
이 체계는 θ의 시퀀스를 생성합니다1, θ2,… 조건부 확률 
. 이 계획에서 우리는 G0 색상과 각 θ에 대한 분포입니다.n 항아리에 놓인 공의 색상을 나타냅니다. 그만큼 연산 다음과 같습니다 :
· 우리는 빈 항아리로 시작합니다.
· 확률에 비례하여 α 우리는 그립니다 
우리는 항아리에이 색깔의 공을 추가합니다.
· n-1에 비례하는 확률로 우리는 항아리에서 무작위 공을 그립니다. 우리는 그 색깔을 관찰하고 그것을 다시 항아리에 놓고 우리는 같은 색깔의 공을 항아리에 추가합니다.
이전에는 Dirichlet Process로 시작하여 Blackwell-MacQueen 구성표를 도출했습니다. 이제 Blackwell-MacQueen 구성표에서 반대로 시작하여 DP를 도출해 봅시다. θ부터i G에서 iid 방식으로 도출 된 경우 공동 분포는 유한 순열에 변하지 않으므로 교환 가능합니다. 결과적으로 de Finetti의 정리를 사용함으로써, 우리는 그것들을 iid로 만드는 조치에 대한 분포가 존재해야하며이 분포는 Dirichlet Process입니다. 결과적으로 우리는 Blackwell-MacQueen urn 방식이 DP를 나타내는 것이며이를 구축 할 수있는 구체적인 방법을 제공합니다. 나중에 볼 수 있듯이이 체계는 수학적으로 중국 식당 프로세스와 동일합니다.
3.2 스틱 파괴 구조
스틱 브레이킹 구조는 Dirichlet Process를 대표하는 대체 방법입니다. 세스 후라 만. 그것을 형성하는 건설적인 방법입니다 배포 및 사용 다음 비유: 우리는 길이가 1 인 스틱을 가지고 있다고 가정하고 β 위치에서 깰 수 있습니다.1 우리는 π를 할당합니다1 우리가 부러진 막대기 부분의 길이와 같습니다. 동일한 과정을 반복하여 π를 얻습니다.2, 파이3... 등; 이 체계가 정의 된 방식으로 인해 우리는 무한한 시간을 계속 할 수 있습니다.
위의 π를 기준으로k 로 모델링 할 수 있습니다 
어디 
이전 체계에서와 같이 θ는 기본 분포에 의해 직접 샘플링됩니다. 
. 결과적으로 G 분포는 π로 가중 된 델타 함수의 합으로 작성 될 수 있습니다.k 다음과 같은 확률 . 따라서 스틱 브레이킹 구조는 Dirichlet Process를 간단하고 직관적으로 구성 할 수있는 방법을 제공합니다.
3.3 중식 레스토랑 프로세스
중국 식당 프로세스는 더스, Dirichlet Process를 나타내는 또 다른 효과적인 방법이며 Blackwell-MacQueen urn 구성표에 직접 연결할 수 있습니다. 이 체계는 다음 비유: 우리는 테이블이 무한한 중국 식당이 있다고 가정합니다. 고객이 식당에 들어 오면 점유 한 테이블에 무작위로 앉거나 사용 가능한 첫 번째 빈 테이블에 앉습니다.
CRP는 양의 정수의 파티션 공간에 대한 분포를 정의합니다. 우리는 θ를 그려서 시작합니다1,… θn Blackwell-MacQueen 항아리 체계에서. 이전 세그먼트에서 논의했듯이, 클러스터링 효과가 나타날 것으로 예상되므로 고유 한 θ 값 k의 총 개수는 n보다 상당히 적습니다. 따라서 이것은 k 개의 군집에서 {1,2,…, n} 세트의 파티션을 정의합니다. 결과적으로 Blackwell-MacQueen urn 방식을 사용하면 {1,2,…, n} 세트의 무작위 파티션이 유도됩니다. 중국 식당 프로세스는 이로 인해 파티션을 통한 배포. 알고리즘은 다음과 같습니다.
· 우리는 빈 식당으로 시작합니다.
· 1st 고객은 항상 1에 앉아st 테이블
· n + 1th 고객은 2 가지 옵션이 있습니다 :
o 비어있는 첫 번째 테이블에 확률로 앉아 
o 가능성이있는 k 번째 점유 테이블 중 하나에 앉아 
어디에 
그 테이블에 앉아있는 사람들의 수
여기서 α는 DP의 분산 값이고 n은 주어진 시간에 식당의 총 고객 수입니다. 잠재 변수 zi i의 테이블 번호를 저장합니다th 고객이며 1에서 k까지의 값을 갖습니다.n 어디 kn n 명의 고객이 식당에있을 때 차지한 총 테이블 수입니다. 우리는 kn 항상 n보다 작거나 같고 평균적으로 
. 마지막으로 테이블 정렬의 가능성에 주목해야합니다. 
순열에 변하지 않습니다. 따라서 zi 같은 크기의 고객이있는 테이블의 확률이 동일하다는 것을 의미합니다.
중식당 프로세스는 Pólya urn 방식 및 Dirichlet Process와 밀접하게 연결되어 있습니다. CRP는 파티션을 통한 배포 n 포인트의 (테이블 할당) 잠재 변수 z의 공간에서 선행으로 사용할 수 있습니다i 어느 클러스터 할당을 결정합니다. CRP는 각 테이블 / 클러스터에 매개 변수를 지정하지 않는다는 점만 제외하고는 Pólya의 urn 체계와 동일합니다. 토고 CRP에서 Pólya의 항아리 체계까지 우리는 그립니다 모든 테이블 k = 1,2…에 대해 그리고 모든 x에 대해i 이것은 테이블 z로 그룹화됩니다.i 할당 
. 즉, 새로운 x에 할당i 테이블의 파라미터 θ 마지막으로 우리는 할당 할 수 없습니다 처음부터 무한 테이블까지 θ는, 누군가가 새로운 테이블에 앉을 때마다 새로운 θ를 할당 할 수 있습니다. 위의 모든 사항으로 인해 CRP는 데이터 세트에서 클러스터 분석을 수행하기 위해 계산 효율적인 알고리즘을 구축하는 데 도움이 될 수 있습니다.
이 포스트에서는 Dirichlet Process와이를 구성하는 몇 가지 방법에 대해 논의했습니다. 다음 기사에서 위의 아이디어를 사용할 것입니다. Dirichlet Process Mixture Model을 소개하고 Dirichlet Process를 구성하고 Cluster Analysis를 수행하기 위해 Chinese Restaurant Representation을 사용할 것입니다. 몇 가지 요점을 놓친 경우 다음 두 기사를 통해 문제가 명확 해지기 때문에 걱정하지 마십시오.
이 게시물이 재미 있었기를 바랍니다. 그렇다면 Facebook과 Twitter에서 공유하십시오. 🙂
