어떤 현상을 표현하는 샘플들이 있다고 하자. 그리고 우리는 한정된 수의 샘플로 현상을 최대한 잘 표현하고자 한다. 이 경우에 어떻게 샘플을 뽑아야 좋을까?
이 경우 두 가지를 고려해야 할 것이다.
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에 의해 선택될 확률이 올라간다.
기존의 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이기 때문이다.
