学习条件平均值：在经典学习框架中扩展了对局部平均标签的预测能力。
Learning Conditional Averages
- 通过引入邻域系统，将传统学习任务扩展为预测每个实例周围标签的平均值。
- 给出了可学习性的完全刻画，样本复杂度紧致到对数因子内。
- 适用于可解释性、公平性与推荐系统等场景，理论意义强。
我们提出了在 PAC 框架下学习条件平均值的问题。学习者接收来自已知概念类中未知目标概念的标记样本，如同标准 PAC 学习。但不同于学习目标概念本身，其目标是为每个实例预测其邻域内的平均标签——任意包含该实例的点集。当所有邻域为单点集时，问题退化为经典 PAC 学习。更一般地，它将 PAC 学习推广到涵盖可解释性、公平性与推荐系统等领域中的学习任务。主要贡献是完整刻画了条件平均值何时可学习，并给出了紧致的样本复杂度上界，误差控制在对数因子内。该刻画依赖于两个新型组合参数的联合有限性，这些参数同时依赖于概念类和邻域系统，且与关联邻域图的独立数密切相关。
原文摘要 · Abstract (English)
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in standard PAC learning. However, instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood -- an arbitrary subset of points that contains the instance. In the degenerate case where all neighborhoods are singletons, the problem reduces exactly to classic PAC learning. More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains, including explainability, fairness, and recommendation systems. Our main contribution is a complete characterization of when conditional averages are learnable, together with sample complexity bounds that are tight up to logarithmic factors. The characterization hinges on the joint finiteness of two novel combinatorial parameters, which depend on both the concept class and the neighborhood system, and are closely related to the independence number of the associated neighborhood graph.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。