Feb, 2024
可学习性是一个紧凑属性
Learnability is a Compact Property
TL;DR近期的学习研究显示，学习问题的可学习性可能是不可判定的，或者与标准集合论的ZFC公理无关。此外，这些问题的可学习性可能不是有限特性：简单来说，通过检查问题的有限投影无法检测出可学习性。然而，学习理论在定义学习的维度时充斥着只考虑问题的有限限制的概念，即具有有限特性的性质。如何调和这些结果呢？具体而言，哪些学习问题容易受到逻辑不可判定性的影响，哪些问题可以用有限特性来解决？我们证明了具有测度损失的监督学习的困难可以通过有限特性来精确描述。尤其是我们证明了学习一个假设类的样本复杂度可以通过检查其有限投影来判断。对于广泛类别的适当损失函数的可实现和了解学习，我们证明了一个确切的紧致性结果：一个类别在具有给定样本复杂度时可以学习，仅当其所有有限投影也是如此。对于具有不适当损失函数的可实现学习，我们证明了样本复杂度的确切紧致性可能会失败，并提供了样本复杂度相差2倍的相匹配上下界。我们猜想对于了解学习的情况可能存在更大的差距。我们技术工作的核心是一个关于变量分配的紧致性结果，它在保持函数类别在目标值以下方面具有广泛的兴趣，该结果推广了霍尔（Hall）经典匹配定理，可能具有独立的兴趣。