论文标题
通过算法重新审视的不稳定公式定理
The unstable formula theorem revisited via algorithms
论文作者
论文摘要
本文是关于模型理论的基础结果的令人惊讶的相互作用，关于理论的稳定性以及学习算法稳定性的稳定性。首先，为了应对现有学习模型中的差距，我们引入了一种新的统计学习模型，称为“最终正确”或PEC。我们根据该模型来表征Littlestone（稳定）类。作为推论，Littlestone类具有自然统计意义上的频繁简短定义。为了根据频繁的定义获得Littlestone类的表征，我们构建了一个等价定理，突出了许多现有近似算法和新PEC的共同点。这是指模型理论中类型的确定性的类比，但具有自己的特征。利用这些定理和最近的其他作品，我们提出了Shelah著名的不稳定配方定理的完整算法类似物，其算法属性代替了无限的算法。
This paper is about the surprising interaction of a foundational result from model theory, about stability of theories, with algorithmic stability in learning. First, in response to gaps in existing learning models, we introduce a new statistical learning model, called ``Probably Eventually Correct'' or PEC. We characterize Littlestone (stable) classes in terms of this model. As a corollary, Littlestone classes have frequent short definitions in a natural statistical sense. In order to obtain a characterization of Littlestone classes in terms of frequent definitions, we build an equivalence theorem highlighting what is common to many existing approximation algorithms, and to the new PEC. This is guided by an analogy to definability of types in model theory, but has its own character. Drawing on these theorems and on other recent work, we present a complete algorithmic analogue of Shelah's celebrated Unstable Formula Theorem, with algorithmic properties taking the place of the infinite.
