Active DPP：基于行列式点过程的批量主动学习.

paper：Batch Active Learning Using Determinantal Point Processes

本文作者提出了基于行列式点过程(DPP)的批量主动学习方法。行列式点过程是一类排斥点过程，可以用于生成不同批次的样本。具体地，作者使用了两个DPP：不确定性DPP根据学习模型提供的不确定性得分选择数据样本，探索DPP旨在寻找新的决策边界。通过该方法选择的样本既具有足够的信息量，由具有多样性。样本选择后由人类专家进行标记，并进一步训练模型。

1. 行列式点过程

行列式点过程是在集合 $\mathcal{X}$ 的有限子集 $X$ 上定义的概率测度。L-ensemble通过一个实对称半正定 $N\times N$ 核矩阵 $L$ 定义DPP，则对子集 $X=A \in \mathcal{X}$ 进行采样的概率为：

P (X = A) \propto det (L_{A})

$P(X = A ) ∝ \det(L_A)$

在本工作中每个批次选择 $k$ 个样本，因此采用k-DPP方法，即限制 $|A| = k$ 。对矩阵 $L$ 进行分解 $L=D^TD$ ，则有：

P (X = A) \propto det (L_{A}) = {Vol}^{2} ({D_{i}}_{i \in A})

$P(X = A ) ∝ \det(L_A) = \text{Vol}^2(\{D_i\}_{i \in A})$

由上式可知概率与相关体积的平方成正比。对于通用的k-DPP方法，可以近似实现：

P (X = A) \propto {Vol}^{2 α} ({D_{i}}_{i \in A})

$P(X = A ) ∝ \text{Vol}^{2\alpha}(\{D_i\}_{i \in A})$

从k-DPP中采样的目标是寻找同时满足信息丰富和多样性的分配模式：

A^{*} = arg max A P (X = A)

$A^* = \mathop{\arg \max}_{A} P(X = A )$

然而上述问题是NP-hard问题，因此需要采用近似算法。

⚪ 贪心算法 Greedy Algorithm

贪心算法是指逐个向批量中增加样本：

A^{(m + 1)} = A^{(m)} \cup {arg max j {Vol}^{2 α} ({D_{i}}_{i \in A^{(m)} \cup {j}})}

$A^{(m+1)} = A^{(m)} ∪ \{ \mathop{\arg \max}_{j} \text{Vol}^{2\alpha}(\{D_i\}_{i \in A^{(m)} ∪ \{j\}}) \}$

贪心算法是寻找分配模式的 $k^{O(k)}$ 阶近似算法。

⚪ 凸松弛算法 Convex Relaxation Algorithm

凸松弛算法是寻找分配模式的 $e^k$ 阶近似算法。考虑与k-DPP相关的生成多项式：

g (v_{1}, . \dots, v_{N}) = \sum A : | A | = k det (L_{A}) \prod i \in A v_{i}

$g(v_1,.\cdots ,v_N) = \sum_{A:|A|=k} \det(L_A) \prod_{i \in A} v_i$

则寻找分配模式等价于在满足约束 $v_1+\cdots +v_N=k$ 的非负整数 $v_1,\cdots v_N$ 上最大化 $g(v_1,.\cdots ,v_N)$ 。用非负实数替换整数，并将 $g$ 调整为凹函数 $\log (g)$ ，则可得到原问题的一个松弛问题：

max {log g (v_{1}, . \dots, v_{N}) | v_{1} + \dots + v_{N} = k}

$\max \{ \log g(v_1,.\cdots ,v_N) | v_1+\cdots +v_N=k \}$

⚪ 最大坐标舍入算法 Maximum Coordinate Rounding

本文作者提出了一种最大坐标舍入算法，可以在线性时间内完成搜索，避免了凸松弛算法的超线性多项式时间。算法流程如下：

在满足约束 $v_1+\cdots +v_N=k$ 的非负整数 $v_1,\cdots v_N$ 上寻找 $\log g(v_1,.\cdots ,v_N)$ 的极大值
记上述过程寻找的非负整数中的最大值为 $v_i^{*}$ ，把样本 $i$ 加入 $A$ 中，使用条件DPP递归地寻找 $k-1$ 个样本加入 $A$ 。

可以证明上述过程也是寻找分配模式的 $e^k$ 阶近似算法。

2. Active DPP

本文提出的基于DPP的主动学习方法希望能够采样到同时具有丰富的信息量与多样性的样本，因此在DPP分布的基础上进行一些修改。

对矩阵 $L$ 进行分解 $L=D^TD$ ，则有：

$\begin{aligned} L&=B^TB, \quad B_i = q_i\phi_i \\ L_{i,j} &= q_i\phi_i^T\phi_jq_j = q_iS_{i,j}q_j \end{aligned}$

其中 $q_i \in \Bbb{R}^+$ 用于衡量样本 $i$ 的信息量； $\phi_i \in \Bbb{R}^D$ 衡量样本的多样性；两个样本之间的相似性计算为 $S_{i,j} = \phi_i^T \phi_j$ ，使用高斯核实现：

$S_{i,j} = \exp(-\frac{h(\mathcal{X}_i,\mathcal{X}_j)^2}{2\sigma^2})$

对于不确定性，将样本的信息量得分 $q_i$ 设置为不确定性得分，并引入超参数 $\gamma$ 表示对不确定性的关注程度：

$L_{i,j} = q_i^{\gamma/\alpha}S_{i,j}q_j^{\gamma/\alpha}$

3. 实验分析

作为对比，作者设置了几种不同的采样策略：

均匀采样：从一批样本中随机均匀采样一个子集进行标注，样本中可能会有冗余信息；
被动DPP：构造DPP时设置每个样本同等重要 $q_i$ ，此时样本均匀地覆盖样本空间，减轻了冗余问题；
$\epsilon$ -贪心：采样时如果只盲目选择不确定性较高的样本，则可能会引入偏见，即样本只聚焦在某个决策边界附近，从而错过较远的其他决策边界。为了避免该问题，作者使用了 $\epsilon$ -贪心设置，即每次采样时选择 $(1-\epsilon)k$ 个不确定性较高的样本，然后再均匀采样 $\epsilon k$ 个样本。