Determinantal Point Process.
本文目录：
- 行列式点过程的定义
- 通过L-ensemble构造核矩阵
- 初等行列式点过程 Elementary DPPs
- 质量-多样性分解 quality-diversity decomposition
- 其他类型的行列式点过程
1. 行列式点过程的定义
在机器学习中，行列式点过程 (determinantal point process, DPP)是一种解决子集选择问题的方法，即从样本集合中选择具有多样性(diversity)的一个子集。DPP赋予该子集上的分布能够使得选择两个相似程度较高样本的概率是负相关的，即越相似的样本越不容易被同时采样到。
一般地，行列式点过程\(\mathcal{P}\)是在一个离散的有限基本点集\(\mathcal{Y} = \{1,2,...,N\}\)的幂集\(2^\mathcal{Y}\)上定义的概率测度 (probability measure)。
- 幂集 (power set)：原集合中的所有子集（包括全集和空集）构成的集族。设\(\mathcal{X}\)是一个有限集，$|$ \(\mathcal{P}\) $|=k$，则\(\mathcal{X}\)的幂集的势为$w^k$。比如集合\(\{a,b,c\}\)的幂集共有8个子集：\(\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\)
设\(\mathcal{A} \in \mathcal{Y}\)是集合\(\mathcal{Y}\)的一个子集，$Y$是根据DPP从集合\(\mathcal{Y}\)中随机采样$N$个点生成的一个子集，则：
\[P(A ⊆ Y) = \det(K_A)\]其中$K$是相似度矩阵(核矩阵，DPP kernel)，通常是$N\times N$的实对称半正定方阵。$K_A$是由$A$中元素在\(\mathcal{Y}\)中的标号相对应的元素构成的$K$的主子式（principle minors, 任选$i$行$i$列的子方阵）。下图给出一个从四个元素的集合中选择其中两个元素的例子：
对于\(\forall \mathcal{A} \in \mathcal{Y}\)，\(P(A ⊆ Y) = \det(K_A) \in [0,1]\)，因此$K$的所有特征值与主子式都应处于$[0,1]$，即$K$是半正定矩阵。$K$也被称为边缘核，因为它确定了DPP的边缘分布：
\[P(A ⊆ Y) = \sum_{Y':A ⊆ Y'} P(Y=Y')\]- 当\(A=\{\}\)时，人为定义$\det(K_{\Phi})=1$，即任意一个DPP生成的随机过程中选中的点构成的集合都包含空集。
- 当\(A=\{i\}\)时，有\(P(i ⊆ Y) = K_{i,i}\)，即$K$的对角线给出了单个元素包含于$Y$的边缘概率。
- 当\(A=\{i,j\}\)时，有:
从上式可以观察到，非对角元素$K_{i,j}=K_{j,i}$表示成对元素之间的负相关度量。$K_{i,j}$值越大，表示$i,j$越不可能同时出现。如果$K_{i,j}$表示$Y$中成对元素之间相似性的度量，则相似程度较高的元素不太可能同时出现。
通过DPP采样的点中距离越近的点越不容易成对出现，因此DPP采样比独立采样所能覆盖的范围更好。
2. 通过L-ensemble构造核矩阵
下面讨论如何构造DPP中的核矩阵$K$。为了对真实数据建模，通常做法是通过L-ensemble来构造边缘核矩阵$K$。具体地，L-ensemble通过一个半正定矩阵$L$定义DPP：
\[P_L(Y) ∝ \det(L_Y)\]其中矩阵$L$定义为一个核函数：
\[L_{i,j} = g(i)^Tg(j)\]
概率函数需要进行归一化。已知有如下关系：
\[\sum_{Y ⊆ \mathcal{Y}} \det(L_Y) = \det(L+I)\]上式借助了行列式的加法性质（以二阶行列式为例）：
\[\begin{vmatrix} a_{11}+1 & a_{12} \\ a_{21} & a_{22} \end{vmatrix} = \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ a_{21} & a_{22} \end{vmatrix}\]则$\det(L+I)$等价于（仍以二阶行列式为例）：
\[\begin{aligned} \det(L+I) &= \begin{vmatrix} L_{1,1}+1 & L_{1,2} \\ L_{2,1} & L_{2,2}+1 \end{vmatrix} = \begin{vmatrix} L_{1,1} & L_{1,2} \\ L_{2,1} & L_{2,2}+1 \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ L_{2,1} & L_{2,2}+1 \end{vmatrix} \\ &= \begin{vmatrix} L_{1,1} & L_{1,2} \\ L_{2,1} & L_{2,2} \end{vmatrix} + \begin{vmatrix} L_{1,1} & L_{1,2} \\ 0 & 1 \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ L_{2,1} & L_{2,2} \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ 0 & 1 \end{vmatrix} \\ &= \det(\{1,2\}) + \det(\{1\})+ \det(\{2\})+ \det(\{\}) \end{aligned}\]上述两个元素可以推广到任意$N$个元素的情形。则最终可以得到归一化的概率形式：
\[P_L(Y) = \frac{\det(L_Y)}{\sum_{Y ⊆ \mathcal{Y}} \det(L_Y)} = \frac{\det(L_Y)}{ \det(L+I)}\]根据由边缘核定义的DPP的边缘分布：
\[\begin{aligned} P(A ⊆ Y) &= \sum_{Y':A ⊆ Y'} P(Y=Y') = \det(K_A) \\ &= \sum_{Y':A ⊆ Y'} \frac{\det(L_{Y'})}{\det(L+I)} = \frac{1}{\det(L+I)}\sum_{Y':A ⊆ Y'} \det(L_{Y'}) \end{aligned}\]仍然根据前述行列式拆分规则可得：
\[\sum_{Y':A ⊆ Y'} \det(L_{Y'}) = \det(L+I_{\overline{A}})\]其中$I_{\overline{A}}$是指如果集合$A$包含索引$i$，则\([I_{\overline{A}}]_{i,i}=0\)；如果不包含索引$i$，则\([I_{\overline{A}}]_{i,i}=1\)。下面给出一个二阶行列式的例子：
\[\begin{aligned} \det(L+I) &= \begin{vmatrix} L_{1,1} & L_{1,2} \\ L_{2,1} & L_{2,2} \end{vmatrix} + \begin{vmatrix} L_{1,1} & L_{1,2} \\ 0 & 1 \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ L_{2,1} & L_{2,2} \end{vmatrix} + \begin{vmatrix} 1 & 0 \\ 0 & 1 \end{vmatrix} \\ &= \det(\{1,2\}) + \det(\{1\})+ \det(\{2\})+ \det(\{\}) \\ \text{if } A&= \{1\} \\ \sum_{Y':A ⊆ Y'} \det(L_{Y'}) &= \det(\{1,2\}) + \det(\{1\}) \\ &= \begin{vmatrix} L_{1,1} & L_{1,2} \\ L_{2,1} & L_{2,2} \end{vmatrix} + \begin{vmatrix} L_{1,1} & L_{1,2} \\ 0 & 1 \end{vmatrix} = \begin{vmatrix} L_{1,1} & L_{1,2} \\ L_{2,1} & L_{2,2}+1 \end{vmatrix} \\ &= \det(\begin{bmatrix} L_{1,1} & L_{1,2} \\ L_{2,1} & L_{2,2} \end{bmatrix}+\begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}) \end{aligned}\]根据上述结论，DPP的边缘分布可进一步写作：
\[\begin{aligned} P(A ⊆ Y) &= \sum_{Y':A ⊆ Y'} P(Y=Y') = \det(K_A) \\ &= \sum_{Y':A ⊆ Y'} \frac{\det(L_{Y'})}{\det(L+I)} = \frac{1}{\det(L+I)}\sum_{Y':A ⊆ Y'} \det(L_{Y'}) \\ &= \frac{\det(L+I_{\overline{A}})}{\det(L+I)} = \det\{(L+I_{\overline{A}})(L+I)^{-1}\} \end{aligned}\]当$A$取\(\mathcal{Y}\)的全集\(\{1,2,...,N\}\)时，有：
\[\det(K) = \det\{(L+0)(L+I)^{-1}\}\]因此得到以下推导：
\[\begin{aligned} K &= (L+0)(L+I)^{-1} \\ &= (L+I-I)(L+I)^{-1} \\ &= I-(L+I)^{-1} \\ I-K &= (L+I)^{-1} \\(L+I)(I-K) &= I \\L(I-K) + (I-K) &= I \\ L(I-K) &= K \\ L &= K(I-K)^{-1} \end{aligned}\]上式进一步整理得：
\[\begin{aligned} K &= L(L+I)^{-1} = I-(L+I)^{-1} \\ L &= K(I-K)^{-1} \end{aligned}\]在此基础上，如果存在$L$的特征值分解：
\[L = V \Lambda V^{-1} = \sum_n \lambda_nv_nv_n^T\]则可得到：
\[\begin{aligned} K &= L(L+I)^{-1} \\ &= V \Lambda V^{-1}(V \Lambda V^{-1}+V V^{-1})^{-1} \\ &= V \Lambda V^{-1}V( \Lambda +I)^{-1} V^{-1} \\ &= V \{ \Lambda ( \Lambda +I)^{-1} \} V^{-1} \\ &= \sum_n \frac{\lambda_n}{\lambda_n+1}v_nv_n^T \end{aligned}\]3. 初等行列式点过程 Elementary DPPs
如果核矩阵$K$的每一个特征值都在\(\{0,1\}\)中，则对应的DPP称为初等行列式点过程 (elementary DPPs)。
一个初等DPP \(\mathcal{P}^V\)的核矩阵$K^V$的特征值分解可以由一组标准正交向量积\(\{v_n\}_{n \in V}\)表示：
\[K^V = \sum_{n \in V} v_n v_n^T\]如果$Y$~\(\mathcal{P}^V\)，则集合$Y$的势(cardinality) $|Y|$是固定的：
\[\begin{aligned} \Bbb{E} [|Y|] &=\sum_n \Bbb{I}(i \in Y) = \sum_n K_{n,n}^V \\ &= \text{tr}(K^V) = \sum_{n\in V} ||v_n||^2 = |V| \end{aligned}\]由\(\text{rank}(K^V)\) $=|V|$可知$P(|Y|>|V|)=0$，因此$P(|Y|=|V|)=1$。
⚪ 采样引理 Sampling lemma
对于任意DPP \(\mathcal{P}_L\)，如果其L-ensemble矩阵$L$的特征值分解为：
\[L = \sum_n \lambda_nv_nv_n^T\]则\(\mathcal{P}_L\)可以表示为一系列初等DPP的混合：
4. 质量-多样性分解 quality-diversity decomposition
在采样时，希望能分别衡量采样样本的质量(quality)和多样性(diversity)，因此对DPP进行质量-多样性分解 (quality-diversity decomposition)。
将DPP的L-ensemble矩阵$L$写作Gramian矩阵：
\[L=B^TB, \quad B_i = q_i\phi_i\]其中\(q_i \in \Bbb{R}^+\)用于衡量样本$i$的质量；\(\phi_i \in \Bbb{R}^D\)是$D$维多样性特征向量，\(\|\phi_i\|^2=1\)。
定义\(S \in \Bbb{R}^{N \times N}\), $S_{i,j} = \phi_i^T \phi_j$，则有：
\[\begin{aligned} L_{i,j} &= q_i\phi_i^T\phi_jq_j = q_iS_{i,j}q_j \\ S_{i,j} &= \frac{q_i\phi_i^T\phi_jq_j}{q_iq_j} = \frac{L_{i,j}}{\sqrt{L_{i,i}L_{j,j}}} \in [-1,1] \end{aligned}\]矩阵$L$的分解如下：
则采样过程可以理解为分别按质量$q$和多样性$S$进行采样：
\[P_L(Y) ∝ \det(L_Y) = \det(S_Y) \cdot \prod_{i \in Y} q_i^2\]⚪ 对偶形式
在对DPP的矩阵$L$进行分解时需要处理$N\times N$的矩阵。当$N$很大时计算效率很低。因此引入如下对偶表示：
\[C = BB^T\]其中$C$是$D\times D$的矩阵。对比$L=B^TB$，可知$C$和$L$具有相同的非零特征值，且两者的特征向量线性相关。有以下命题：
$C$存在以下特征值分解：
\[C = \sum_{n=1}^D \lambda_n \hat{v}_n \hat{v}_n^T\]当且仅当$L$存在以下特征值分解：
\[\begin{aligned} L&=B^TB = B^T(\sum_{n=1}^D \hat{v}_n \hat{v}_n^T )B \\ &= \sum_{n=1}^D \lambda_n [\frac{1}{\sqrt{\lambda_n}}B^T\hat{v}_n][\frac{1}{\sqrt{\lambda_n}}\hat{v}_n^TB] \\ &= \sum_{n=1}^D \lambda_n [\frac{1}{\sqrt{\lambda_n}}B^T\hat{v}_n][\frac{1}{\sqrt{\lambda_n}}B^T\hat{v}_n]^T \end{aligned}\]当维度$D$也比较大时，可以采用投影到低维空间($d«D$)的方法：
5. 其他类型的行列式点过程
（1）条件行列式点过程 Conditional-DPP
在一些实际问题中，集合\(\mathcal{Y}\)并不是固定的，而是取决于输入变量$X$：\(\mathcal{Y}(X)\)。
条件行列式点过程(Conditional-DPP) \(\mathcal{P}\) $(Y|X)$定义为每一种子集\(Y ⊆ \mathcal{Y}(X)\)上的分布：
\[\mathcal{P}(Y|X) ∝ \det(L_Y(X))\]其中$L(X)$是取决于输入变量$X$的半正定核。根据质量-多样性分解：
\[L_{i,j}(X) = q_i(X)\phi_i^T(X)\phi_j(X)q_j(X) = q_i(X)S_{i,j}(X)q_j(X)\]其中$q_i,\phi_i$可以设置为从数据中学习得到的隐函数。
（2）k-DPP
如果将子集元素的个数固定为$k$，则对应k-DPP方法。
一种k-DPP的实现思路是将DPP调整到势为$k$的集合上：
\[P_L^k(Y) = \frac{\det(L_Y)}{\sum_{|Y'| =k} \det(L_{Y'})} = \frac{\det(L_Y)}{e_k(\lambda_1,\lambda_2,\cdots \lambda_N)}\]其中$e_k$表示$k$阶初等对称多项式(elementary symmetric polynomial)：
\[e_k(\lambda_1,\lambda_2,\cdots \lambda_N) = \sum_{J⊆\{1,\cdots N\} , |J| = k} \prod_{n \in J} \lambda_n\]下面是一个$N=3$的例子：
\[\begin{aligned} e_1(\lambda_1,\lambda_2, \lambda_3) &= \lambda_1+\lambda_2+ \lambda_3 \\ e_2(\lambda_1,\lambda_2, \lambda_3) &= \lambda_1\lambda_2+\lambda_1\lambda_3+ \lambda_2\lambda_3 \\ e_3(\lambda_1,\lambda_2, \lambda_3) &= \lambda_1\lambda_2 \lambda_3 \end{aligned}\]另一种k-DPP的实现思路是将其看作一系列初等DPP的组合：
\[\mathcal{P} ∝ \sum_{J⊆\{1,\cdots N\} , |J| = k} \mathcal{P}^J \prod_{n \in J} \lambda_n\]
从k-DPP中采样的目标是寻找同时满足信息丰富性和多样性的分配模式(mode)：
\[A^* = \mathop{\arg \max}_{A} P_L^k(Y=A) ∝ \mathop{\arg \max}_{A} \det(L_A)\]然而上述问题是NP-hard问题，通常采用贪心算法 (Greedy Algorithm)求解，即逐个向批量中增加样本：
\[A^{(t+1)} = A^{(t)} ∪ \{ \mathop{\arg \max}_{j} \det(L_{A^{(t)} ∪ \{j\}}) \}\]
