Determinantal Point Process (DPP)

**Determinantal Point Process (DPP)**는 집합(Set)에서 다양성(Diversity) 을 고려하여 부분집합(subset)을 선택하기 위한 확률 모델이다.

직관적으로는:

“품질이 좋은 항목들을 선택하되, 서로 비슷한 항목은 동시에 선택될 확률을 낮춘다.”

즉, Quality + Diversity를 동시에 고려하는 샘플링 기법이다.

---

1. 왜 필요한가?

예를 들어 문서 검색 결과가 다음과 같다고 하자.

문서	내용
D1	GPT 논문
D2	GPT-2 논문
D3	GPT-3 논문
D4	RAG 논문
D5	Ontology 논문

Top-3를 relevance만으로 선택하면

$\{D1,D2,D3\}$

가 될 수 있다.

하지만 세 문서가 거의 비슷하다.

사용자는

$\{D1,D4,D5\}$

처럼 서로 다른 주제를 보고 싶을 수 있다.

DPP는 이런 문제를 해결한다.

---

2. 기본 아이디어

집합

$Y=\{1,2,\ldots,N\}$

에서 부분집합

$A \subseteq Y$

를 선택한다고 하자.

DPP는

P(A)

를 다음과 같이 정의한다.

$P(A) \propto \det(L_A)$

여기서

• L: PSD kernel matrix
• $L_A$: 부분집합 A에 해당하는 submatrix

이다.

---

3. Determinant가 왜 Diversity를 의미하는가?

가장 중요한 부분이다.

각 item을 벡터

$v_i$

로 표현한다고 하자.

Kernel:

$L_{ij}=v_i^Tv_j$

이면

$L_A=\begin{bmatrix}v_1^Tv_1 & v_1^Tv_2 \\v_2^Tv_1 & v_2^Tv_2\end{bmatrix}$

가 된다.

---

경우 1: 두 벡터가 매우 비슷

$v_1 \approx v_2$

이면

$\det(L_A)\approx 0$

이다.

즉, $P(A)\approx 0$

---

경우 2: 서로 직교

$v_1 \perp v_2$

이면

$L_A=\begin{bmatrix}1&0\\0&1\end{bmatrix}$

$\det(L_A)=1$

최대값이 된다.

---

즉 determinant는

“선택된 벡터들이 차지하는 부피(volume)”

를 의미한다.

$\det\begin{pmatrix}a&b\\b&c\end{pmatrix}=ac-b^2$

여기서 b가 크면(유사도가 높으면) determinant가 작아진다.

---

4. Quality + Diversity

실제 DPP는 다음 형태를 사용한다.

$L_{ij}=q_i\,s_{ij}\,q_j$

여기서

• $q_i$: quality
• $s_{ij}$: similarity

이다.

행렬 형태:

L = QSQ

---

그러면

$P(A)\propto\det(L_A)$ 은

$=\left(\prod_{i\in A} q_i^2\right)\det(S_A)$

로 분해된다.

---

즉, $\text{Quality}\times\text{Diversity}$ 가 된다.

---

5. 예시

논문 추천 시스템

논문	품질
LLM Safety	0.9
Jailbreak Attack	0.9
Prompt Compression	0.8
Ontology Matching	0.7

LLM Safety와 Jailbreak Attack이 매우 비슷하면

$s_{12}=0.95$

가 된다.

그러면 DPP는

$\{Safety,Compression,Ontology\}$

를 선택할 가능성이 높아진다.

---

6. k-DPP

일반 DPP는 부분집합 크기가 가변적이다.

|A| 가 달라질 수 있다.

---

많은 응용에서는

정확히 k개를 선택하고 싶다.

예:

• Top-10 retrieval
• Top-5 examples

이 경우

$P(A)=\frac{\det(L_A)}{\sum_{|B|=k}\det(L_B)}$

for $|A|=k$

를 사용한다.

이를 k-DPP라고 한다.

---

7. 머신러닝에서의 활용

(1) Retrieval

RAG 검색 결과 다양화

기존:

TopK

DPP:

TopK + Diversity

---

(2) In-Context Learning Example Selection

Few-shot 예제 선택

예:

• 비슷한 예제 5개
• 다양한 예제 5개

보통 후자가 일반화 성능이 좋다.

대표 논문:

• Diverse Demonstration Selection
• DPP-based ICL

---

(3) Active Learning

라벨링할 샘플 선택

원하지 않는 경우:

• 거의 같은 문장 100개

원하는 경우:

• 서로 다른 영역의 샘플

DPP가 자주 사용된다.

---

(4) Summarization

문장 선택

중복 문장을 제거하고

다양한 정보를 포함하는 요약 생성

---

(5) RAG Context Compression

최근 LLM/RAG 연구에서

• Similarity Ranking
• MMR
• DPP

를 비교하는 경우가 많다.

---

8. MMR과의 차이

MMR(Maximal Marginal Relevance)

선택을 순차적으로 수행한다.

$\text{MMR}=\lambda Relevance-(1-\lambda) Redundancy$

---

DPP는

$P(A)\propto\det(L_A)$

로 전체 집합을 한 번에 평가한다.

방법	특징
MMR	Greedy
DPP	Global optimization
MMR	빠름
DPP	다양성 반영 우수
MMR	검색 시스템 많이 사용
DPP	연구용/고품질 추천 시스템

---

9. LLM 연구에서 DPP 활용

최근 LLM 논문들에서 DPP는 주로 다음 용도로 사용된다.

Example Selection

$Embeddings \rightarrow DPP \rightarrow Few-shot examples$

---

Retrieval Diversification

$Retriever\rightarrow Top100\rightarrow DPP \rightarrow Top10$

---

Synthetic Data Selection

생성 데이터 수십만 개 중

• 품질 유지
• 중복 제거

를 위해 DPP 사용

---

Prompt Compression

문장 단위 중요도 추출 후

DPP로 redundancy 제거

---

핵심 요약

DPP는

$P(A)\propto \det(L_A)$

로 정의되는 확률 모델이며,

• determinant = 선택된 벡터들의 volume
• volume이 클수록 diversity가 높음
• 비슷한 항목은 함께 선택될 확률 감소
• 품질(quality)과 다양성(diversity)을 동시에 고려

한다.

따라서 현재 LLM 연구에서는 Few-shot example selection, RAG retrieval diversification, 데이터 선택(Data Selection), Prompt Compression 분야에서 가장 널리 사용되는 diversity-aware subset selection 기법 중 하나이다.

Fast Greedy MAP for DPP (Chen et al., NeurIPS 2018)

이 논문은 DPP에서 가장 널리 사용되는 문제인

$Y^*=\arg\max_{Y\subseteq \mathcal{V}} \det(L_Y)$

를 매우 빠르게 푸는 방법을 제안한다.

---

1. 문제: DPP MAP Inference

DPP에서 확률은

$P(Y)\propto \det(L_Y)$

이다.

우리가 실제 응용에서 원하는 것은 샘플링보다

“가장 좋은 subset 하나”

를 찾는 것이다.

즉,

$Y^*=\arg\max_Y \det(L_Y)$

이다.

이를 MAP(Maximum A Posteriori) inference라고 부른다.

---

예를 들어

RAG에서

Top-100 문서가 있다고 하면

$100 \rightarrow 10$

개를 선택해야 한다.

목표는

• relevance 유지
• diversity 최대화

이다.

---

2. 기존 Greedy MAP

DPP의 log-det는 submodular 함수이다.

$f(Y)=\log\det(L_Y)$

따라서 Greedy가

$(1-\frac1e)$

근사보장을 가진다.

---

Greedy는

매 단계

$i^*=\arg\max_i \left[ f(Y\cup\{i\})-f(Y)\right]$

를 선택한다.

---

문제는

매 후보마다

$\det(L_{Y\cup\{i\}})$

를 다시 계산해야 한다.

---

복잡도

$O(M^4)$

수준까지 증가한다.

(M=선택 수)

실제 Retrieval에서는 너무 느리다.

---

3. 핵심 아이디어

Chen et al.의 핵심은

determinant를 매번 처음부터 계산하지 말고

Cholesky decomposition을 재활용하자.

이다.

---

4. DPP Greedy에서의 Marginal Gain

현재 선택 집합을

Y

라고 하자.

후보 i 추가 시

$\Delta_i=\log\det(L_{Y\cup\{i\}})-\log\det(L_Y)$

---

Block determinant identity를 사용하면

$\Delta_i=\log(d_i^2)$

로 표현 가능하다.

여기서

$d_i^2$ 는

“이미 선택된 벡터 공간에 대해 남아있는 직교 성분의 크기”

이다.

---

기하학적으로

$d_i^2=\|v_i^\perp\|^2$

이다.

---

즉, 이미 선택된 것들과 비슷한 후보는

$d_i \approx 0$

이 된다.

---

5. Cholesky View

선택된 집합의 kernel

$L_Y$

에 대해

$L_Y=VV^T$

라 하자.

---

새 원소 i에 대해

$c_i$ 를 정의하면

$d_i^2=L_{ii}-c_i^Tc_i$

가 된다.

---

중요한 점은

Greedy 한 단계 후

$c_i$ 를 재활용 가능하다는 것이다.

---

즉 determinant를 다시 계산하지 않고

$d_i^2$ 만 갱신한다.

---

6. Fast Greedy Update

새 원소 j 선택

$j=\arg\max_i d_i^2$

---

그러면

모든 후보 i에 대해

$e_i=\frac{L_{ij}-\langle c_i,c_j\rangle}{d_j}$

계산

---

이후

$c_i\leftarrow[c_i,e_i]$

확장

---

$d_i^2\leftarrow d_i^2-e_i^2$

갱신

---

이 과정은 Gram-Schmidt와 거의 동일하다.

---

7. 알고리즘 직관

초기

$d_i^2=L_{ii}$

---

반복:

Step 1

가장 큰

$d_i^2$

선택

---

Step 2

새 방향 추가

---

Step 3

나머지 후보들의 직교 성분 제거

$d_i^2\leftarrow d_i^2-e_i^2$

---

Step 4

반복

---

결과적으로

선택되는 벡터들은

서로 거의 직교하게 된다.

즉 diversity가 커진다.

---

8. 계산복잡도

기존 Greedy

O(Nk^3)

혹은

O(N^3)

수준

---

Fast Greedy

O(Nk^2)

---

여기서

• N = 후보 수
• k = 선택 개수

---

Retrieval에서는

보통

$k\ll N$

이므로 큰 속도 향상이 난다.

---

9. 기하학적 해석

DPP는

선택된 벡터들이 만드는 평행다면체(parallelepiped)의 부피를 최대화한다.

$\det(L_Y)=\text{Volume}(Y)^2$

---

Fast Greedy는 사실상

Gram-Schmidt 직교화 과정을 수행하면서

매번 가장 큰 새로운 방향을 제공하는 벡터를 선택한다.

---

즉, $d_i^2=\|v_i^\perp\|^2$

가 가장 큰 후보를 고르는 것이다.

---

10. LLM/RAG에서의 활용

최근 Retrieval 논문들은

1. Retriever

Top100

2. Similarity Matrix 생성

$S_{ij}$

3. DPP Kernel

$L_{ij}=q_iS_{ij}q_j$

4. Fast Greedy MAP
5. Top-k diverse documents

---

형태를 많이 사용한다.

특히

• RAG document selection
• Few-shot example selection
• Data subset selection
• Prompt compression
• Long-context pruning

에서 자주 등장한다.

---

Chen et al. (2018)의 핵심 한 줄

기존 DPP MAP inference는 반복적으로 determinant를 계산해야 해서 느렸지만,

$d_i^2=L_{ii}-c_i^Tc_i$

를 유지하면서 Cholesky/Gram-Schmidt 방식으로 업데이트하여,

O(Nk^2)

복잡도로 거의 동일한 MAP 해를 매우 빠르게 구하는 알고리즘을 제안하였다. 이는 현재 DPP 기반 retrieval diversification의 사실상 표준 구현으로 사용된다.

DPP (Fast Greedy MAP) vs MMR vs mRMR

세 방법 모두 본질적으로는

“좋은 항목을 선택하되 중복(redundancy)을 줄이자”

라는 목표를 가진다.

하지만 수학적 목적함수와 최적화 방식이 상당히 다르다.

---

1. 한눈에 비교

방법	목적	Diversity 고려	Selection 방식
MMR	Relevance-Redundancy	Pairwise	Greedy
mRMR	Relevance-Redundancy	Pairwise Average	Greedy
DPP	Volume Maximization	Global	Greedy MAP / Sampling

---

2. MMR (Maximal Marginal Relevance)

원래 정보검색(IR) 분야에서 제안됨.

목적함수:

$\text{MMR}(x)=\lambda Rel(x)-(1-\lambda)\max_{y\in S}Sim(x,y)$

여기서

• S: 이미 선택된 집합
• Rel(x): query relevance
• Sim(x,y): similarity

---

선택 과정

$x^*=\arg\max_x\Big[\lambda Rel(x)-(1-\lambda)\max_{y\in S} Sim(x,y)\Big]$

---

특징

중복 패널티는

$\max Sim$ 만 사용

즉, “가장 비슷한 놈 하나”

만 본다.

---

3. mRMR

Feature Selection에서 매우 유명

논문:

Minimum Redundancy Maximum Relevance

---

목표

$\max\left(Relevance-Redundancy\right)$

---

대표 형태

$Score(x)=I(x;Y)-\frac1{|S|}\sum_{y\in S}I(x;y)$

---

여기서

$I(\cdot)$ 는 mutual information

---

즉, $\text{좋은 feature}$ 면서 $\text{기존 feature들과 덜 중복}$인 것을 선택

---

특징

MMR:

$\max Sim$

---

mRMR:

$avg(Sim)$

---

즉 mRMR이 좀 더 안정적이다.

---

4. DPP

DPP는 pairwise penalty를 직접 사용하지 않는다.

---

목적

$\max\det(L_S)$

또는

$\max\log\det(L_S)$

---

Kernel

$L_{ij}=q_i s_{ij} q_j$

---

그러면

$\det(L_S)=\Big(\prod q_i^2\Big)\det(S_S)$

---

여기서

$\det(S_S)$ 가 diversity를 담당

---

5. 가장 큰 차이

MMR/mRMR은

pairwise similarity 기반

---

DPP는

전체 집합의 기하구조를 본다.

---

예를 들어

세 벡터

$v_1,v_2,v_3$

---

MMR/mRMR

$Sim(v_i,v_j)$

만 고려

---

DPP

$\det\begin{bmatrix}v_1^Tv_1 & v_1^Tv_2 & v_1^Tv_3\\v_2^Tv_1 & v_2^Tv_2 & v_2^Tv_3\\v_3^Tv_1 & v_3^Tv_2 & v_3^Tv_3\end{bmatrix}$

---

즉

3-way interaction

4-way interaction

…

전체를 고려

---

6. Information-Theoretic 관점

mRMR

명시적으로

I(X;Y) 사용

---

즉, Feature Selection 전용

---

MMR

Heuristic

---

Similarity 기반

---

DPP

확률 모델

$P(S)\propto \det(L_S)$

---

통계적으로 정의됨

---

8. 계산량 비교

후보 수: N

선택 수: k

---

MMR

O(Nk)

---

매우 빠름

---

mRMR

Mutual Information 계산 필요

보통

O(Nk)

~O(N^2)

---

DPP Fast Greedy

Chen et al.

O(Nk^2)

---

조금 더 비쌈

---

9. LLM/RAG에서의 실제 사용

최근 Retrieval 분야

가장 흔함

MMR

이유:

• 구현 쉬움
• 매우 빠름
• LangChain 기본 지원

---

연구 논문

DPP

이유:

• Diversity 우수
• Few-shot selection 효과 좋음
• Retrieval diversification 효과 좋음

---

거의 안 씀

mRMR

이유:

• Feature Selection용으로 설계됨
• Document Retrieval에는 부적합

---

10. LLM 논문 관점

사용자의 연구 분야(Example Selection, Prompt Compression, RAG Compression)에 적용하면:

문제	추천
RAG Retrieval	MMR 또는 DPP
Few-shot Example Selection	DPP
Prompt Compression	DPP
Data Subset Selection	DPP
Neuron Selection	mRMR
SAE Feature Selection	mRMR
Circuit Edge Selection	mRMR + DPP

---

연구자 관점의 핵심 차이

MMR은

$\text{Relevance}-\text{Worst Redundancy}$

를 최적화한다.

mRMR은

$\text{Relevance}-\text{Average Redundancy}$

를 최적화한다.

DPP(Fast Greedy MAP)는

$\max \log\det(L_S)$

를 통해

선택된 항목들이 만드는 전체 표현 공간의 부피(volume) 를 최대화한다.

따라서 LLM의 example selection, retrieval diversification, prompt compression처럼 집합 전체의 다양성이 중요한 경우에는 일반적으로 DPP가 MMR/mRMR보다 더 강력한 선택 기준으로 평가된다.