For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the annotator. In this work, we formalize these settings and study the problem of learning from such coarse data. Instead of observing the actual labels from a set $\mathcal{Z}$, we observe coarse labels corresponding to a partition of $\mathcal{Z}$ (or a mixture of partitions). Our main algorithmic result is that essentially any problem learnable from fine grained labels can also be learned efficiently when the coarse data are sufficiently informative. We obtain our result through a generic reduction for answering Statistical Queries (SQ) over fine grained labels given only coarse labels. The number of coarse labels required depends polynomially on the information distortion due to coarsening and the number of fine labels $|\mathcal{Z}|$. We also investigate the case of (infinitely many) real valued labels focusing on a central problem in censored and truncated statistics: Gaussian mean estimation from coarse data. We provide an efficient algorithm when the sets in the partition are convex and establish that the problem is NP-hard even for very simple non-convex sets.
翻译:对于许多学习问题,可能无法获得精细的标签信息;例如,根据注释者的专业知识,图像可以标记为哈士奇、狗或动物。本文中,我们正式化这些设置,并研究从这种粗糙数据中学习的问题。我们没有观察到来自集合$\mathcal{Z}$的实际标签,而是观察到对$\mathcal{Z}$的分区(或分区混合)对应的粗糙标签。我们的主要算法结果是:从粗数据中学到的任何可从细粒度标签学习的问题,在粗数据足够信息的情况下也可以被有效地学习。我们通过通用的归约来回答只使用粗标签就能够得出统计查询(Statistical Queries, SQ)的问题来获得结果。所需的粗标签数量取决于由于粗略化而导致的信息失真和精细标签的数量$|\mathcal{Z}|$的多项式。我们还研究了实值标签(无限多)的情况,重点关注了有关被审查和截断统计学的一个核心问题:从粗略数据中估计高斯均值。当分区中的集合是凸的时,我们提供了一种高效的算法,并确定即使是非常简单的非凸集合也是NP难问题。