深度学习经典数据处理算法：Coreset 数据压缩算法
什么是Coreset 数据压缩
给定全集 P={p1,…,pn}、模型类 ℋ、损失 ℓ，coreset 是一个加权小子集(C,w)，C⊂P, |C|=k≪n，使得：
三个关键点：
① 加权：每个选中点带权重 wi，补偿"被代表"的点；
② 对任意 θ：这才是 coreset（vs 随机采样只在期望意义成立）；
③ ε 保证：可证明的近似。
简单说，加权小子集在标目容忍度内可以等价全集。
常见方法很多主要是看使用什么度量空间：特征距离（几何）/ 梯度（训练动态）/ 影响力（Hessian）/ 子模函数（覆盖+去重）
方法分类
算法介绍
k-center-greedy （几何）
目标：最小化覆盖半径
复杂度：O(nk) 贪心
保证：2-近似（贪心）
需训练：否
这算法到底在干嘛？从一堆点里挑 k 个当"代表"（中心）
实例:1D 选 5 个中心，看「覆盖半径」一路降
点：1, 2, 3, 7, 8, 9, 15, 16。规则：每步挑 d(p) 最大的点入选，再用它更新各点 d(p)=min(老值, 到它距)。
s₁=1（起点）：d(p)=2:1, 3:2, 7:6, 8:7, 9:8, 15:14,16:15→ 覆盖半径15
最大是 16 → 选它 ▼
s₂=16：用 16 更新后 d(p)=2:1, 3:2, 7:6,8:7, 9:7, 15:1 → 半径7（15 被 16 拉走，剩 8、9 最远）
最大是 8、9 并列 → 选 8 ▼
s₃=8：用 8 更新后 d(p)=2:1,3:2, 7:1, 9:1, 15:1 → 半径2（8 把 7、9 拉到 1，剩 3 最远）
最大是 3 → 选它 ▼
s₄=3：用 3 更新后 d(p)=2:1, 7:1, 9:1, 15:1 → 半径1（3 补上左侧，全员离最近中心 ≤1）
s₅：d(p) 全是 1，最大=1 → 已无处可补，再选半径也不会降（收敛）
半径15 → 7 → 2 → 1 → 1：每加一个代表就补掉当前最大的窟窿。S={1,3,8,9,16}
优：无需训练、可解释、实现极简。
缺：对离群点敏感（最远点常是噪声）；理论 2-近似对非凸损失失效。
CRAIG （梯度）
目标：子集加权梯度 ≈ 全集梯度
复杂度：O(n²) 预处理 + 贪心
保证：梯度误差上界
需训练：是（每 epoch 重选）
优：直接对齐训练目标，保真度高。
缺：要算/缓存所有点梯度，大数据内存压力大；需定期重选。
实际中：如果没有目标梯度，消除最多的就是同向冗余或者反向相消的冗余梯度
GLISTER （梯度 · bi-level）
目标：子集使验证集损失最小
复杂度：高（bi-level）
保证：无（启发式）
需训练：是
优：面向最终泛化性能，不浪费预算在"训练有用但验证无用"的点。
缺：需要干净验证集；bi-level 不稳定。
但是实际中，深度学习常用的方法更加暴力，直接是使用模型推理训练集根据loss排序
GradMatch （梯度 · SOTA）
目标：CRAIG + GLISTER 改进
复杂度：中
保证：梯度误差界 + 增强
需训练：是
对 CRAIG 的三点改进：①非负权重约束（NNLS）；②per-class匹配（防类别失衡）； ③增强（梯度 EMA 去噪）
数据是怎么被"压缩"的？
① 原始 n 个样本，每步训练要算全部梯度 ∇ℓⱼ → 贵；
② 选 k≪n 个代表 S，配权重 w，让k 个加权梯度之和 ≈ 全量梯度之和：Σi∈S wᵢ∇ℓᵢ ≈ Σj=1n ∇ℓⱼ；
③ 之后训练只训练这 k 个（loss 各乘 wᵢ 放大），算力O(n) → O(k)；
④权重 = 代表倍数：1 个选中样本"替身" wᵢ 个原始样本 → 这就是压缩；
⑤ 每 T 步重选一次（θ 在变，谁有代表性也跟着变）。
实例①
两类缺陷：数据两类，狗图像100 ， 猫图像10，预算 k=11
CRAIG 全局匹配：按数量贡献选 → 11 个里 ~10 狗 + 1 猫，凹坑几乎没代表
GradMatch per-class：分两类各匹配 —— 猫100→选 6（权 ≈17，1 个顶 17 张）；狗 10→选 5（权 ≈2）
两类各自被加权代表，长尾(凹坑)不被淹没；压缩 110→11 张，训练每步只过 11 个
实例②
非负权重约束（NNLS）
无约束时 CRAIG 可能解出 wᵢ < 0
负权重 = 反向使用样本，物理上不合法
NNLS 强制 w≥0 → 选真实正权代表点
实例③
EMA 梯度去噪
第 t 步 ∇ℓ 含 mini-batch 噪声，方向抖
∇̃ = 0.9∇̃ + 0.1∇ 平滑后稳定
匹配用 ∇̃ → 子集不再追噪声，选得更稳
优：所有方法里实测最强。
缺：实现最重；要调权重求解器。
DPP / k-DPP（ 几何 · 多样性）
目标：按多样性采样
复杂度：精确 NP-hard，近似 O(nk)
保证：多样性负相关
需训练：否
子集概率正比于其核矩阵行列式。行列式 = 体积，相似点共线 → 行列式小 → 难被采； 多样点 → 行列式大 → 易被采。把"多样性"变成可计算量。k-DPP 固定 |S|=k。说白了就是求两个向量的相似度，如果相似度高，认为是冗余，相似性低，认为是多样性需要的样本，度量空间可以使用希尔伯特空间。
优：多样性有理论最优。
缺：精确采样 NP-hard，实际用近似；核矩阵 O(n²) 存储。
Facility Location（子模）
目标：最大化总相似度覆盖
复杂度：O(nk) 贪心
保证：(1−1/e) 近似
需训练：否
简单理解，每个全集点被"子集里最像它的点"代表，把所有点的代表相似度加起来最大化。单调子模，贪心有 (1−1/e)≈63% 的理论保证（少数真实场景仍成立的保证）。
简单来说：F 衡量「全体被代表得有多好」；贪心每步挑能最大化提升 F 的点，自然倾向补盲区（E）而非堆冗余（B/D）；而且这种贪心对子模目标有63% 最优的理论保底。
优：保证扎实、可加各种"奖励项"（长尾、不确定性）。
缺：需定义好相似度度量。
理论保证 vs 现实
核心事实：Coreset的ε保证基于凸损失 + 固定模型类的假设。 深度网络非凸、训练中模型在变，保证基本失效。工业里当启发式数据选择用，别迷信"可证明"。
实测规律（来自 GradMatch 等论文）：
- 随机采样是很强的 baseline，别低估；
- k-center / Herding通常打平或略超随机，优势在小预算 + 长尾时才显著；
- GradMatch 才稳定优于随机，数据集越大优势越大；
- Influence在数据清洗（找错标/有害样本）上价值更高，而非压缩。
下期单独讲一下Influence算法，看看为什么Influence在数据清洗（找错标/有害样本）上价值更高，而非压缩。