基于核心集的主动学习方法.

核心集(core-set)是计算几何中的概念，指能够近似一个较大的点集的较小的点集。在主动学习中，可以通过在整个数据集的核心集上进行训练，从而获得与整个训练集相似的性能。

记训练时共有$N$个数据样本，在第$t$轮训练时选择子集\(\mathcal{S}^{(t)}\)进行标注。学习目标的上界可以被拆分为泛化误差、训练误差和核心集误差之和。

\[\begin{aligned} \Bbb{E}_{(x,y) \text{~} p} [\mathcal{L}(x,y)] &\leq |\Bbb{E}_{(x,y) \text{~} p} [\mathcal{L}(x,y)] - \frac{1}{N}\sum_{i=1}^N\mathcal{L}(x_i,y_i) | \\ &+ \frac{1}{|\mathcal{S}^{(t)}|} \sum_{j=1}^{|\mathcal{S}^{(t)}|}\mathcal{L}(x_j^l,y_j) \\ &+ |\frac{1}{N}\sum_{i=1}^N\mathcal{L}(x_i,y_i)-\frac{1}{|\mathcal{S}^{(t)}|} \sum_{j=1}^{|\mathcal{S}^{(t)}|}\mathcal{L}(x_j^l,y_j)| \end{aligned}\]

则主动学习问题的目标与核心集误差类似：

\[\mathop{\min}_{\mathcal{S}^{(t+1)}:|\mathcal{S}^{(t+1)}|\leq b} |\frac{1}{N}\sum_{i=1}^N\mathcal{L}(x_i,y_i)-\frac{1}{|\mathcal{S}^{(t)} ∪ \mathcal{S}^{(t+1)} |} \sum_{j=1}^{|\mathcal{S}^{(t)} ∪ \mathcal{S}^{(t+1)}|}\mathcal{L}(x_j^l,y_j)|\]

上述问题等价于$k$-center问题，即选择$b$个中心点使得任意样本点和与其最近的中心点之间的距离的最大值最小化。

该问题是NP-hard问题，常用贪心算法求近似解。即每次选择一个样本，使其与已标注数据之间的距离最大，并标注该数据；重复进行$b$次。

实验结果表明，当分类类别数量较小时该方法的表现较好。当类别数增大或数据维度增大时，核心集方法的效率会下降。