论文标题
树木尺寸和Sauer-Shelah二分法
Tree Dimension and the Sauer-Shelah Dichotomy
论文作者
论文摘要
我们引入树维及其水平的变体，以测量二进制树中叶子集的复杂性。然后，我们使用级别的树尺寸在此类集合的大小上提供一个紧密的上限。反过来，这意味着VC维度的著名Sauer-Shelah引理和Bhaskar的Littlestone尺寸版本，从而更清楚地了解了为什么这些结果将相同的上限放在其各自的破碎功能上。我们还按树维度对最大叶子集的同构类型进行了分类。最后，我们将此分析概括为更高的树木。
We introduce tree dimension and its leveled variant in order to measure the complexity of leaf sets in binary trees. We then provide a tight upper bound on the size of such sets using leveled tree dimension. This, in turn, implies both the famous Sauer-Shelah Lemma for VC dimension and Bhaskar's version for Littlestone dimension, giving clearer insight into why these results place the exact same upper bound on their respective shatter functions. We also classify the isomorphism types of maximal leaf sets by tree dimension. Finally, we generalize this analysis to higher-arity trees.
