본문 바로가기

Enginius/Machine Learning

Determinantal Point Process (DPP)

Determinantal Point Process란 무엇인가?


어떤 현상을 표현하는 샘플들이 있다고 하자. 그리고 우리는 한정된 수의 샘플현상을 최대한 잘 표현하고자 한다. 이 경우에 어떻게 샘플을 뽑아야 좋을까? 

이 경우 두 가지를 고려해야 할 것이다. 

1. 개별 샘플이 얼마나 현상을 잘 표현하는지를 고려하고, 

2. 각 샘플들끼리 최대한 덜 겹치게 

해야 한정된 수로 최적의 결과를 낼 수 있을 것이다. Determinantal Point Process는 이런 경우에 사용될 수 있는 개념이다. 


먼저 Point process는 다음과 같이 정의된다. 


Ground set Y에서 정의된 point process P는 Y에서의 point pattern에서 정의된 probability measure이다. 

예를 들어 continuous domain에서 정의된 Y라는 stream이 있을 때, 각 시간 t1, t2, t3에서 measure한 y1, y2, y3를 하나의 instance로 볼 수 있다. 이러한 {y1, y2, y3}에 대한 확률을 정의하는 것이 point process이다. 


현재 참고하고 있는 논문의 notation을 설명하겠다. 대부분의 경우 우리의 domain인 Ground set은 discrete라 가정할 것이고, WLOG, Y = {1, 2, ..., N}이라고 하겠다. 그리고 이러한 Y의 원소를 item이라고 하겠다. 


앞서 PP는 probability measure라고 했었다. DPP에서 확률은 다음과 같이 정의된다. 

For every '$A \subseteq Y$', 

$$P(A \subseteq Y) = det(K_A)$$


간단하다. 이제 우리는 어떤 set A가 주어졌을 때, '$K_A$'를 구하는 방법만 찾으면 된다. SVM이나 GP와 같은 kernel method를 본적이 있다면, 이 '$k_A$'가 A라는 데이터로 만든 kernel이라고 추측할 수 있을 것이다. 그리고 이는 반쯤은 맞는 말이다. 이에 대해서 좀 더 자세히 살펴보자. 


먼저 '$Prob = det(K_A)$'의 확률이다. 그래서 '$K_A$'는 PSD여야 한다. 

또한 복잡한, 혹은 직관적인, 유도를 통해서 '$K_A$'의 eigenvalue가 1보다 작아야 한다는 것을 유도할 수 있다. 즉 '$K_A$'의 eigenvalue는 0과 1 사이에 있어야한다. 

그리고 이 조건이 전부이다! 

DPP를 정의하기 위한 '$K$'의 조건은 eigenvalue가 0과 1사이에 있기만 하면 된다. 


우리는 이러한 '$K$'를 marginal kernel이라고 한다. 만약 '$A = \{ i\}$' 가 singleton이면 다음과 같은 성질을 같는다. 

$$P(i \in Y) = K_{ii}$$

'$K$'의 diagonal 성분은 Y의 개별 element가 포함될 확률을 나타낸다. 이 값이 1에 가까울 수록 해당 원소가 DPP에 의해 선택될 확률이 올라간다. 


만약 '$A =\{ i, j\}$'와 같이 두 개의 원소로 이뤄진 set이라면, 

$$P(i, j \in Y) = [K_{ii} K_{ij} ; K_{ji} K_{jj}]$$

$$ = K_{ii}K_{jj} - K_{ij}K_{ji}$$

$$ = P(i \in Y)P(j \in Y) - K^2_{ij}$$

와 같이 확률이 정의된다. 

직관적으로 생각하면 K의 off-diagonal 성분들은 두 원소 사이의 negative correlation을 나타낸다. 만약 이 값이 크다면 i와 j는 같이 뽑히지 않을 것이다. 


즉 이러한 성질을 통해서 우리는 정말 Uniform한 sampling을 할 수 있다.  

위 그림에서 오른쪽은 Poisson PP에서 뽑은 것이다. 자세한 것은 다른 포스팅 참조. 왼쪽은 DPP로 뽑은 것이다. 딱 봐도 왼쪽이 더 '균등하게' 뽑힌 것을 알 수 있다. 이 때 '$K_{ij}$'는 i와 j 사이의 거리에 반비례하는 함수이다. 



L-ensembles란 무엇인가?


우리는 앞서 DPP는 적절한 '$K$'만 정의하면 됨을 알았다. 그리고 이 '$K$'가 만족해야할 조건은 eigenvalue가 0~1이었다. 하지만 이 간단한 조건 하나 만족시키는 것이 생각보다 '귀찮다' (=어렵다의 공학적 표현). 


그래서 우리는 '$K$' 대신에 '$L$' 이라는 L-ensemble을 통해서 DPP를 정의한다. 개념은 아주 간단하다. 

$$P_L(Y = y) \propto det(L_y)$$

 

위 식에서와 같이 여기선 비례의 개념을 사용하기 때문에 L의 eigenvalue가 1보다 작을 필요가 없다.  


나는 수학을 못하므로 복잡한 증명은 건너뛰고 다음의 성질만 쓰겠다. 

L-ensemble은 DPP이고, marginal kernel은 다음과 같이 정의된다. 

$$K = L(L+I)^{-1} = I - (L+I)^{-1}$$


이로써 PSD만 만족하는 kernel function을 이용해서 L을 만들고, 이 L로 위의 방식과 같이 K를 만들고, DPP를 만들 수 있다! 이제 쓸 일만 남았다. 


k-DPP란 무엇인가? 

 

주어진 문제는 다음과 같다. N개의 데이터가 있다. 이 중에서 k개의 적절히 분포된 데이터를 고르고 싶다고 하자. 단순히 k개를 uniform하게 뽑는 것은 그리 좋은 방법이 아니다. 여튼 이런 경우에 사용될 수 있는 것이 k-DPP라 한다. 


어떤 Discrete set '$Y = \{ 1, 2, ..., N\}$' 에 정의된 k-DPP는 k의 cardinality를 같은 set '$y \subseteq Y$'의 확률이고, 다음과 같이 정의된다. 

$$P_L^k(Y) = \frac{det(L_Y)}{\sum_{|Y'| = k}det(L_{Y'})}$$


기존의 DPP와 비교해보면 유일한 다른점은 Y에 대한 제약과 normalization constant이다. 즉 우리가 관심있는 set의 cardinality를 k로 fix한 것이 전부이지만, 이 것은 매우 큰 implication을 갖는다. 


우리에게 주어진 문제를 푸는 것은 매우 간단하다.  걍 greedy하게 one-by-one으로 풀자. 

Since a k-DPP is just a DPP conditioned on size, we could sample a k-DPP by repeatedly sampling the corresponding DPP and rejecting the samples until we obtain one of size k. 


이렇게 하는 이유는 N의 점 중에서 k개의 좋은 selection을 하는 것 자체가 combinatorial 문제이기 때문에 NP-HARD이기 때문이다. 


간단한 예제로 이번 포스팅을 마무리 하겠다. 


코드


메인 함수


주요 사용 함수 (kdpp)


커널 함수

'Enginius > Machine Learning' 카테고리의 다른 글

Deep Learning이란 무엇일까?  (4) 2014.08.02
Sparse Kernel Methods  (0) 2014.07.31
Non-stationary Gaussian process regression  (0) 2014.07.25
ICML에 나온 Gaussian process  (0) 2014.07.23
Stochastic process and Gaussian process  (2) 2014.07.16