标签延迟也能学！新理论DCD揭秘需要多少样本，适度等待竟比立即标签更强
Delay Complexity Dimension: Learning with Delayed and Censored Labels
📖 AI 总结
该研究探讨了在标签随机延迟到达且超出观测窗口后被截尾的情况下，二分类器的PAC学习问题，核心问题是这种观测模型需要多少样本。作者提出了依赖分布的延迟复杂度维度（DCD），将VC维度与观测信道的精确标签信息率相结合，证明任何学习器都需要Ω(DCD/ε²)量级的样本，而一种预言机伪标签ERM方法在下界所在的实例族上可达到该速率（相差常数与对数因子）。理论还导出了利用延迟信息降低残余标签方差的量化方案、具有(1-1/e)保证的加速策略，以及无延迟场景中不存在的新现象：在固定采集时域下，适度的观测窗口可严格优于即时标签。合成数据与Criteo转化日志实验支持了上述预测，而关于标注者多样性预测的预算匹配检验则报告为负面结果。
🔑 关键词速览
| Delay Complexity Dimension (DCD) | 一种依赖于分布的复杂度度量，结合 VC 维与观察信道的标签信息率，用于刻画延迟和删失标签下的样本复杂度。 |
| PAC learning | Probably Approximately Correct 学习，一种机器学习理论框架，要求学习器以高概率输出近似正确的假设。 |
| Censored labels | 删失标签，指在观察窗口结束后仍未到达的标签，其真实值不可观测。 |
| VC dimension | Vapnik-Chervonenkis 维，衡量假设类复杂度的经典指标，常用于 PAC 学习中的样本复杂度下界。 |
| ERM | 经验风险最小化，一种通过最小化训练集上的经验误差来学习模型的方法。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅