实例硬度的概念可能会解决您正在寻找的内容。实例硬度假设数据集中的每个实例都有一个硬度属性，表明它被监督学习算法错误分类的可能性。从某种意义上说，实例硬度着眼于每个个体的硬度，而不是数据的硬度。但是，可以聚合实例硬度以从本质上表征数据集的硬度。但是，与所有聚合方法一样，聚合数据时会丢失一些信息。希望这可以给你一些方向。

统计学习理论通常处理样本复杂性，即我需要多少样本才能产生具有高概率的低误差假设。更具体地说，如果是一组样本，而作为输入时某些学习算法返回的假设，那么通常会生成以下形式的语句 如果对于某些。$S$$h_S$$S$

在上面我们完全忽略了是如何生成的。计算学习理论是处理这些类型的计算问题的领域。例如，可能需要生成的算法在时间中运行，请注意，以上是实现这一点的必要条件。其他常见的研究是如果算法可以访问不同的信息会发生什么（成员查询允许学习算法查询预言机以获取它选择的点标签），学习者在在线学习中犯了多少错误，如果反馈是有限的，如强化学习等。$h_S$$h_S$$\text{poly}(1/\epsilon, 1/\delta)$

还有很多，而且这是一个令人着迷的领域，但我不会列出它们，而是向您介绍Kearns 和 Vazirani的《计算学习理论导论》一书，这是对该主题的一个很好的介绍。