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 |
