深度学习经典数据处理算法：Coreset 数据压缩算法

什么是Coreset 数据压缩给定全集 P{p1,…,pn}、模型类 ℋ、损失 ℓcoreset 是一个加权小子集(C,w)C⊂P, |C|k≪n使得三个关键点① 加权每个选中点带权重 wi补偿被代表的点② 对任意 θ这才是 coresetvs 随机采样只在期望意义成立③ ε 保证可证明的近似。简单说加权小子集在标目容忍度内可以等价全集。常见方法很多主要是看使用什么度量空间特征距离几何/ 梯度训练动态/ 影响力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 → 半径715 被 16 拉走剩 8、9 最远最大是 8、9 并列 → 选 8 ▼s₃8用 8 更新后 d(p)2:1,3:2, 7:1, 9:1, 15:1 → 半径28 把 7、9 拉到 1剩 3 最远最大是 3 → 选它 ▼s₄3用 3 更新后 d(p)2:1, 7:1, 9:1, 15:1 → 半径13 补上左侧全员离最近中心 ≤1s₅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ᵢ∇ℓᵢ ≈ Σj1n ∇ℓⱼ③ 之后训练只训练这 k 个loss 各乘 wᵢ 放大算力O(n) → O(k)④权重 代表倍数1 个选中样本替身 wᵢ 个原始样本 → 这就是压缩⑤ 每 T 步重选一次θ 在变谁有代表性也跟着变。实例①两类缺陷数据两类狗图像100 猫图像10预算 k11CRAIG 全局匹配按数量贡献选 → 11 个里 ~10 狗 1 猫凹坑几乎没代表GradMatch per-class分两类各匹配 —— 猫100→选 6权 ≈171 个顶 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在数据清洗找错标/有害样本上价值更高而非压缩。