[Paper] Determinantal Point Process

“Determinantal point processes for machine learning”이란 논문에 대한 리뷰입니다.

원문은 링크에서 확인할 수 있습니다.

기존의 모델에 대한 논문의 경우에는 간결하게 어떤 구조인지, 어떤 포인트가 새로운 것이며 핵심인지 한번에 요약하는 방식으로 접근했다면, 본 논문은 보다 수학적으로 Determinantal Point Process(DPP)를 다루기 때문에 파트별로 내용을 요약하고, 수식전개가 생략된 부분들은 직접 풀어보면서 정리하였습니다.

다만 내용이 방대하여서 생략된 부분들이 있으며 원문에서 전달하고자 하는 내용을 훼손시키지 않기 위해 그대로 인용하며 의미를 정리하는 방식으로 진행됩니다.

1. Introduction

해당 논문에서 다루는 내용은 크게 다음과 같습니다.

probabilistic model of global, negative correlation
algorithm for sampling, marginalization, conditioning and inference task

point process라는 점에서 inference task보단 sampling algorithm을 중심으로 다루도록 하겠습니다.

1.1 Diversity

논문에서 다음과 같이 정의합니다.

DPP is a distribution over subsets of a fixed ground set, for instance, sets of search results selected from a large database

중요한 점은, ground set에 속한 데이터들이 negative correlation을 가지도록 모델링을 하고 싶었고 그 결과가 DPP인 것입니다.

• 이 때의 negative correlation은 kernel matrix로 정의되며 kernel matrix는 다음과 같이 정리됩니다.

  kernel matrix defines a global measure of similarity between pairs of items

2. Determinantal Point Process

2.1 Definition

point process란

point process $\mathcal{P}$ on a ground set $\mathcal{Y}$ is a probability measure over “point patterns” of $\mathcal{Y}$

여기서 point pattern은 finite subset of $\mathcal{Y} = \lbrace 1,2,…,N \rbrace $라고 하며 일종의 items

DPP란

point process is called  DPP if when $\mathrm{Y}$ is a random subset drawn according to $\mathcal{P}$, for every subset of $\mathrm{Y}$, $\mathcal{P}(A\subseteq \mathrm{Y}) = \det(K_{A})$

• K는 (N,N) matrix indexed by the element of ground set
• $K_{A}$는 그 중에서 indexed by the element of A

즉 어떤 subset이 뽑힐 확률은 subset으로 구성한 유사도 행렬의 $\det$값으로 정의하는 것이 DPP이며 앞서 말한 kernel matrix가 바로 K가 되는 것입니다.

marginal kernel, K란

• cardinality가 1인 set에 대해서 접근할 경우 $\det(K_{i}) = K_{ii}$로 정의됩니다. 즉,

  diagonal of marginal kernel K give the marginal probabilities of inclusion of individual elements of $ \mathcal{Y}$

marginal probability라는 말의 의미는 어떤 item이 subset에 포함되는 경우가 $2^{N-1}$ 정도 있는데 이것들에 대한 marginalization을 말하는 것으로 생각할 수 있다고 생각합니다.

특히 DPP를 probability measure로 정의하기 때문에 다음과 같은 필수 조건이 있습니다.

• K는 positive semidefinite하다.
• 단, marginal probability이기 때문에 normalization은 필수적이지 않다. disjoint한 element에 대한 measure가 아니라 어떤 fininte subset의 subset에 대한 measure이기 때문에 이렇게 얘기하는 것같습니다.

2.2 L-ensembles

기존의 marginal kernel은 subset의 marginal probability로 정의하는 반면 atomic probability로 정의하는 것이 L-ensemble

• 이 때 사용하는 행렬 L은 sysmetric matrix L indexed by the elements of $\mathcal{Y}$로  정의

L-ensemble이란

$\mathcal{P}(\mathrm{Y}=Y) \propto \det(L_{Y})$

Thorem 2.1

For any $A \subseteq \mathcal{Y}$,
$ \sum_{A\subseteq \mathrm{Y} \subseteq \mathcal{Y}} \det(L_{Y}) = \det(L+I_{\bar{A}}) $

증명 process는 다음과 같습니다.

1. 어떤 subset A의 한 element i에 대해서 ground set $\mathcal{Y}$를 2개로 partition을 할 수 있습니다.
   $ L+I_{\bar{A}} = \begin{bmatrix} L_{ii}+1 & L_{i\bar{i}} \\ L_{\bar{i}i} & L_{\mathcal{Y}-\lbrace i\rbrace + I_{\mathcal{Y}-\lbrace i\rbrace-A}} \end{bmatrix} $

2. (1,1)의 element로 인해서 $\det$값을 계산할 때 multilinearity를 이용한다면 $\det$ 값은 다음과 같습니다
   $ \det(L+I_{\bar{A}}) = \begin{vmatrix} L_{ii} & L_{i\bar{i}} \\ L_{\bar{i}i} & L_{\mathcal{Y}-\lbrace i\rbrace + I_{\mathcal{Y}-\lbrace i\rbrace-A}} \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ L_{\bar{i}i} & L_{\mathcal{Y}-\lbrace i\rbrace + I_{\mathcal{Y}-\lbrace i\rbrace-A}} \end{vmatrix} $
   • 이 때 첫번째 항은 A에 i가 포함된 경우를, 두번째 항은 애초에 ground set에 i가 없었기 때문에 어떤 A든 i가 배제된 경우의 $\det$값입니다.
3. 앞의 식의 의미를 따라 식으로 정리하면 다음과 같습니다.

$ \det(L+I_{\bar{A}}) = \sum_{A\cup \lbrace i\rbrace \subseteq \mathcal{Y} } \det(L_{Y}) + \sum_{A \subseteq \mathcal{Y} - \lbrace i\rbrace } \det(L_{Y}) = \sum_{A\subseteq \mathrm{Y} \subseteq \mathcal{Y}} \det(L_{Y}) $

---

이를 통해서 단순히 비례관계로 정의된 L-ensemble을 등호관계로 정리할 수 있습니다.

앞서 정리 2.1을 $A=\varnothing$에 적용하게 된다면
$ \det(L+I_{\bar{A}}) = \det(L+I_{\bar{\varnothing}}) = \det(L+I) = \sum_{\varnothing \subseteq \mathcal{Y}} \det(L_{Y}) $ 이 때 마지막 항의 의미는 곧 모든 subset에 대한 summation이기에 이를 normalization term으로 사용한다면 다음과 같은 식을 얻게 됩니다.

$\mathcal{P}(\mathrm{Y}=Y) = {\det(L_{Y})\over \det(L+I)}$

Thorem 2.2

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

여기서 marginal kernel과 L-ensemble과의 접점이 확인되어 L-ensemble또한 DPP라는 것을 알 수 있습니다.

증명 process는 다음과 같습니다.

1. marginal kernel로 정의한 DPP처럼 marginal probability는 다음과 같습니다.
   $\mathcal{P}(A\subseteq \mathrm{Y}) = {\sum_{A\subseteq \mathrm{Y} \subseteq \mathcal{Y}} \det(L_{Y}) \over \sum_{\mathrm{Y} \subseteq \mathcal{Y}} \det(L_{Y})}= {\det(L+I_{\bar{A}}) \over \det(L+I)}$

2. $ {\det(L+I_{\bar{A}}) \over \det(L+I)} = \det((L+I_{\bar{A}})(L+I)^{-1}) $

3. $= \det(L(L+I)^{-1}+ I_{\bar{A}}(L+I)^{-1})$

4. $= \det(I_{\bar{A}}(L+I)_{-1}+ I - (L+I)^{-1})$

5. $= \det(I+ (I_{\bar{A}}-I)(L+I)^{-1})$

6. $= \det(I- I_{A}(L+I)^{-1})$ and Let $(L+I)^{-1} = I-K$

7. $= \det (I- I_{A}(I-K))$

8. $= \det (I- I_{A} +I_{A}K)$

9. $= \det(I_{\bar{A}}+I_{A}K) = \begin{vmatrix} I_{\bar{A} \times \bar{A}} & 0 \\ 0 & K_{A}\end{vmatrix} = det(K_A)$

---

앞서 marginal kernel과 L-ensemble간의 관계가 규명되었고, L-ensemble이 sysmmetric이라는 점을 이용해서 eigendecomposition을 진행하면

$\begin{aligned} L &= \sum_{n=1}^{N} \lambda_{n}v_{n}v_{n}^{T} \\ K &= \sum_{n=1}^{N} {\lambda_{n}\over \lambda_{n}+1}v_{n}v_{n}^{T} \end{aligned}$

이 됩니다.

중요한 점을 정리하자면 다음과 같습니다.

• 우선 K의 eigenvalue들이 ${\lambda_{n}\over \lambda_{n}+1}$라는 점은 결국 각 element가 뽑힐 marginal probability는 L-ensemble의 eigenvalue와 연관이 있다고 생각합니다.
• L-ensemble은 proportion으로 정의되어 있었고, 이와 관련하여 normalization이 된 형태로 깔끔히 정리되기 때문에 L-ensemble을 sysmmetric하게 정의한다면 DPP에 대한 marginal kernel은 쉽게 구할 수 있게 됩니다.
• 반대로 marginal kernel을 구했다고 하더라도 모든 marginal kernel이 L-ensemble이 되는 것은 아닌데 이는 해당식의 inverse가 존재해야한다는 문제가 생기기 때문입니다.
• 이것이 가능하다는 제한 조건을 두는 것은 결국 empty set에 nonzero probability를 강제한다는 것이라는 내용이 있었지만 real data에선 자연스럽기 때문에 그리 큰 문제는 아니라고 합니다.
• 이후의 내용에선 L-ensemble로 접근한다고 합니다.

2.2.1 Geometry

그렇다면 L matrix를 $ B: D*N$ and $D<=N, L = B^T\times B$로 정의한다면 L은 positive semidefinite하게 됩니다.

이로 인해 $\mathcal{P}(\mathrm{Y}=Y) \propto \det(L_{Y})=Vol^{2}(\lbrace B_{i}\rbrace)$ 즉 matrix B을 구성하는 벡터로 구분되는 공간의 부피로 생각할 수 있고, 두 벡터 간의 sin값이 중요해집니다. 그 결과 두 벡터의 cosine similarity가 증가한다면 sin값은 작아져 결국 확률값도 줄어들게 됩니다. 이러한 성질이 바로 앞서 언급한 negative correltation입니다.

2.3 Properties

Cardinality

각 element마다 marginal probability가 각 eigenvalue가 되니, $\mathrm{Y}$의 cardinality는 Bernoulli trial을 따르게 되어서 cardinality의 기대값은 $\sum_{n=1}^N{\lambda_{n} \over \lambda_n +1}$이 됩니다.

• 즉 각 element의 등장할 확률이 높다면 cardinality의 expectation이 증가하게 됩니다.
• 혹은 반대로 cardinality가 정해져 있는 경우는 Section 5에서 다루게 됩니다.

2.4 Inference

Inference 과정에서 N이 증가할수록 the number of $\mathrm{Y}$는 exponential하게 증가해서 empirical practicality of computation and algorithm을 다루는 것이 2.4절에서 다루는 내용입니다.

2.4.1 Normalization

power set을 다루긴 하지만 closed form으로 $\det(L+I)$으로 normalization이 되기 때문에 N*N matrix의 determinant time complexity는 $\mathcal{O}(N^{3})$ 정도가 된다고 합니다. matrix multiplication을 최적화해서 Coppersmith-Winograd algorithm을 사용하면 $\mathcal{O}(N^{2.376})$정도로 최적화할 수 있다고 합니다.

2.4.2 Marginalization

L-ensemble로 접근한 경우에 marginal kernel 계산을 위해서 matrix inversion이 계산과정에 포함되어 알고리즘에 따라 $\mathcal{O}(N^w)$정도로 늘어나게 됩니다.

• eg. Gauss-Jordan elimination을 쓰면 w=3

2.4.3 Conditioning

특별한 점은 조건부 확률을 계산할 수 있고 이 또한 DPP라는 것입니다. 게다가 어떤건 포함되어 있고 어떤건 포함하는 경우에서의 조건부 확률까지 나타낼 수 있게 됩니다. 자세한 내용은 페이퍼를 참고하여도 이해에 큰 무리가 없다고 판단하여 생략하였습니다.

conditional DPP에서의 general marginal도 정리됩니다.

2.4.4 Sampling

실제로 sampling하는 과정은 다음과 같습니다.

Input : kernel L의 eigendecomposition

1. J = ${\lambda_{n} \over \lambda_n +1}$으로 sampling한 결과
2. V = J에 포함된 eigenvalue에 해당하는 eigenvector들
3. ground set $\mathcal{Y}$의 item i를 $Pr(i)={1\over \mid V \mid} \sum_{v \in V} (v^{T}e_{i})^2$의 확률로 1개를 sampling
4. $Y\gets Y \cup i$
5. V $\gets$ $e_{i}$에 orthgonal한 V의 subspace의 orthonormal basis

특히 step 1에서 뽑을 때 replacement가 허용되지 않습니다. 이는 V가 linearly independent해야 하기 때문입니다.

이것이 왜 DPP sampling이 되는지는 다음과 같습니다.

Definition 2.4

marginal kernel의 eigenvalue가 {0,1}에 포함되면 elementary DPP, $\mathcal{P}^V$라고 부르고 이 때 marginal kernel $K^V=\sum_{v \in V}vv^{T}$

Lemma 2.5

• $W_{n}$ for $n=1,2,…,N$ be an arbitrary sequence of $k\times k$ rank-one matrices
• Let $(W_n)_i$ denote the ith column of $W_n$
• Let $W_{J} = \sum_{n\in J} W_{n}$

$\det (W_{J}) = \sum_{n_{1},…,n_{k} \in J} \det ( [(W_{n1})_{1} \mid … ])$

증명 process는 다음과 같습니다.

1. $\det (W_{J}) = \det (\sum_{n\in J}W_n)$, by multilinearity of determinant,
2. $\det (W_{J}) = \det ([ (W_{n1})$₁ + $(W_{n2})$₁+…$\mid$…])

이를 간단히 생각해보면 $K\times K$ matrix이니 k개의 칸에 각 칸 마다 $\mid J\mid$ 만큼 숫자가 들어갈 수 있지만 다른 칸과 겹치는 경우 determinant 값은 0이 되기 때문에 결과적으로 $n_{1}$부터 $n_{k}$까지 총 k개의 서로다른 숫자 조합에 대한 summation이 되는 것이다.

Lemma 2.6 L-ensemble로 뽑는다는게 결국 mixture of elemeentary DPP를 진행하는 것을 말합니다.
즉, $ \mathcal{P} = {\det (L_{J}) \over \det (L+I)}$ 에서

1. $\det (L_{J}) = \sum_{n_{1},…,n_{k} \in J} \det ( [\lambda_{n1}(v_{n1}v_{n1}^{T})_{1} \mid … ])$
2. $\det (L_{J}) = \sum_{n_{1},…,n_{k} \in J} \det ( [\lambda_{n1} W_{n1} \mid …\mid \lambda_{nk} W_{nk} ])$
3. $ \mathcal{P} = {1 \over \det (L+I)} \sum_{n_{1},…,n_{k} \in J} \det ( [\lambda_{n1} W_{n1} \mid …\mid \lambda_{nk} W_{nk} ])$
4. $ \mathcal{P} = {1 \over \prod_{n=1}^{N} (\lambda_{n}+1)} \sum_{n_{1},…,n_{k} \in J} \det ( [\lambda_{n1} W_{n1} \mid …\mid \lambda_{nk} W_{nk} ])$
5. $ \mathcal{P} = \det (\sum_{n=1}^{N} {\lambda_{n} \over \lambda_{n}+1} W_{n})$

정리하자면 다음과 같습니다.

• mixutre는 각 eigenvalue로 만든 matrix의 weighted sum 형태이며 각 weight는 ${\lambda_{n} \over \lambda_{n}+1}$ 로 정의된다.
• 결국 algorithm에서 step 1의 의미는 eigenvector를 eigenvalue에 따라 sampling하는 것이라 생각합니다.
• 그렇게 모아둔 eigenvector의 index 중에서 Step 3의 과정으로 DPP 이용한 sampling이 된다는 것입니다.

---

3. Representation and algorithms

3.1 Quality vs diversity

$ L = B^{T}\times B$로 서술하여 Gram matrix로 사용할 수 있습니다. 다만 B matrix를 한번 더 Factorization을 거쳐서 quality term $q_{i} \in \mathbb{R}^{+}$과 diversity feature $\phi_{i} \in \mathbb{R}^{D}$로 나누어서 서술해보도록 합니다.

즉, $L_{ij}=q_{i}(\phi_{i})^{T}\phi_{i}q_{j}$ 이 되며 similarity $S_{ij} = (\phi_{i})^{T}\phi_{i} = {L_{ij}\over \sqrt{L_{ii}L_{jj}}} $

• 이렇게 정의하였을때 앞서 언급한 내용처럼 cosine similarity가 커질수록 $L_{ij}^{2}$가 증가하여 determinant 값은 감소하게 된다고 생각할 수 있습니다.

$\mathcal{P} \propto (\prod_{i\in \mathrm{Y}}q_{i}^{2})\det (S_{\mathrm{Y}})$

3.2.2 Comparing DPPs and MRFs

More generally, semidefiniteness means that the DPP diversity feature vectors must satisfy the triangly inequality, leading to
$\sqrt{1-S_{ij}} + \sqrt{1-S_{jk}} \ge \sqrt{1-S_{ik}}$ for all $i, j, k\in \mathcal{Y}$
The similarity measure therefore obeys a type of transitivity with large $S_{ij}, S_{jk}$ implying large $S_{ij}$

3.3 Dual Representation

N이 너무 큰 경우에 다루기 힘드니 $C=B\times B^{T}$ 로 정의해서 $D\times D$ 의 matrix로 해서 좀 다루기 편하게 하는 방식을 소개합니다. 뒤의 내용에서는 앞의 내용과 마찬가지로 동일하게 eigendecomposition이 되고(Proposition 3.1), 그 후marginalization, normalization이 다 가능함을 보입니다.

마찬가지로 sampling도 mappling을 통해서 기존의 V set을 만들어 낼 수 있게 되어 진행할 수 있습니다. 단 eigenvalue는 동일해서 first loop은 동일하게 진행되지만 eigenvector는 mapping을 해야해서 조금 달라지게 된다.

3.4 Random projection

D차원도 아직 너무 크면 diversity feature의 dimension을 낮추지만 좋은 근사값을 가지도록 하는 random projection을 수행하게 되어 문제를 해결하는 내용이 있습니다.

---

5. $k$-DPP

fixed cardinality를 다루는 것이 본 장의 주요 내용입니다.

5.1 Definition

$P^{k}(\mathrm{Y}) = {\det(L_{\mathrm{Y}}) \over \sum_{\mathrm{Y}’=k}\det (L_{\mathrm{Y}’})}$

이렇게 정의하였을 때 기존의 DPP와 다른점은,

• marginal probability가 ${k\over N}$ 이다. 전체 N개 중에서 크기가 k인 집합에 포함될 확률이기 때문입니다.
• 동일하게 item pair에 대한 marginal probability는 ${k(k-1)\over N(N-1)}$이 됩니다.

5.1.1 Alternative models of Size

$\mathcal{P}(\mathrm{Y}) = \mathcal{P}_{size} (\mid Y\mid)\mathcal{P}^{\mid Y \mid}(Y)$

이건 크기가 k일 확률에 대한 size model과 그 때의 k-DPP모델을 합친 것을 기존의 DPP로 생각하자는 아이디어입니다.

5.2 Inference

5.2.1 Normalization

$e_{k}(\lambda_{1},…,\lambda_{N}) = \sum_{J\in \mathcal{Y}, \mid J\mid} \prod_{n\in J} \lambda_{n}$ 라고 symmetric polynomial을 정의하면,

*Proposition 5.1 normalization constant for k-DPP

$Z_{k} = \sum_{\mid Y’ \mid} \det (L_{Y’}) = e_{k}(\lambda_{1},…,\lambda_{N})$

증명 process는 다음과 같습니다.

1. $\sum_{Y\in \mathcal{Y}} \det(L_{Y}) = \det(L+I)$
2. $\sum_{\mid Y’\mid =k} \det(L_{Y’}) = \det(L+I) \sum_{\mid Y’\mid =k} \mathcal{P}(Y’)$, 즉, determinant에 DPP를 곱한 형태이니 mixture of elementary DPP임을 이용하여
3. $\det(L+I) \sum_{\mid Y’\mid =k} \mathcal{P}(Y’) = \sum_{\mid J\mid = k} \sum_{\mid Y’\mid = k} \mathcal{P}(Y’)\prod_{n\in J}\lambda_{n}$
4. $\det(L+I) \sum_{\mid Y’\mid =k} \mathcal{P}(Y’) = \sum_{\mid J\mid = k} \prod_{n\in J}\lambda_{n}$
5. $\sum_{\mid J\mid = k} \prod_{n\in J}\lambda_{n} = e_{k}(\lambda_{1},…,\lambda_{N}) = e_{k}^{N}$

• Step 3에서 J와 Y’의 cardinality가 모두 k인 경우라면 DPP의 marginal probability는 1일 수 밖에 없습니다. Y’의 subset인 J가 크기가 같다는 조건이 있다면 일어날 수 있는 건 전부 다 뽑는 한 경우만 있기 때문입니다.

5.2.2 Sampling

앞서서 symmetric polynomial을 구하였다고 하였을 때, 분자는 기존의 L-ensemble의 정의를 따라 쓰면 다음과 같다.

$\mathcal{P}^{k} = {1\over e_{k}^{N}} \det(L+I)\mathcal{P}(Y)$

또한 Lemma 2.6에서 사용한 관점으로 $\det(L_{J})$를 이용하여 서술하면

$\mathcal{P}^{k} = {1\over e_{k}^{N}} \sum_{\mid J\mid=k} \mathcal{P}^{V_{J}}(Y) \prod_{n\in J}\lambda_{n} $

Theorem 5.2

N>1이며 $1\le k\le N$ 인 환경에서

$n<N$ 이며 $0\le l \le n$ 인 단계에서 set J에 set J’의 element를 추가하려는 상황을 고려해봅시다.

그 때의 J’이 추가되는 확률은 k-DPP 확률 값이므로 ${1\over e_{l}^{N}} \times \prod_{n’\in J’}\lambda_{n’}$ 가 됩니다.

WLOG 맨 처음에 어떤 값 w를 추가한 상황에서 set J’를 추가하는 상황이라고 생각해보면 전체 item 중 남은 item도 N-1개, 그 때의 set J’의 크기는 k-1이어야 하므로 앞서 언급한 set J’이 추가될 확률은 ${1\over e_{k-1}^{N-1}} \times \prod_{n\in J’}\lambda_{n}$ 이 됩니다.

• 즉 지금 상황은 w를 뽑은 상태에서 남은 element를 뽑는 상황을 말하고 있습니다.

각 단계별 확률을 곱해보면

(w를 뽑을 확률) $\times {1\over e_{k-1}^{N-1}} \times \prod_{n\in J’}\lambda_{n}$ = ${1\over e_{k}^{N}} \times \prod_{n\in J}\lambda_{n}$

(w를 뽑을 확률) = $\lambda_N {e_{k-1}^{N-1}\over e_{k}^{N}} $

• 즉 w를 뽑고 남은 element를 뽑는다고 할 때 w를 뽑을 확률을 구할 수 있습니다.

반대로 w가 뽑히지 않는 상황에서 확률은 다음과 같습니다.

$1- \lambda_N {e_{k-1}^{N-1}\over e_{k}^{N}} ={e_{k-1}^{N-1}\over e_{k}^{N}} $

• 이는 symmetric polynomial의 성질로 인해 $e_{k}^N-\lambda_{N}e_{k-1}^{N-1} = e_{k}^{N-1}$ 이기 때문입니다.

본 경우에도 동일하게 전체 프로세스 확률을 구해보면

${e_{k-1}^{N-1}\over e_{k}^{N}} * {1\over e_{k}^{N-1}} \times \prod_{n\in J} \lambda_{n} = {1\over e_{k}^{N}} \times \prod_{n\in J}\lambda_{n}$

즉 한 element를 선택할 확률은 다음과 같이 정리할 수 있습니다.

$\lambda_N {e_{k-1}^{N-1}\over e_{k}^{N}} $

이를 바탕으로 sampling은 다음과 같습니다.

1. symmetric polynomial 구하기
2. if $u~U[0,1] < \lambda_N {e_{k-1}^{N-1}\over e_{k}^{N}}, then\ J \gets J\cup {n}$

5.2.3 Marginalization 이후 이후로 동일하게 marginalization, conditioning이 어떻게 진행되는지 본 논문에서는 정리하고 있지만 생략하도록 하겠습니다.