Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
复制标题
DOI：
10.4230/lipics.itcs.2018.28
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Dana Moshkovitz;Michal Moshkovitz
中科院分区：
文献类型：
--
作者：
Dana Moshkovitz;Michal Moshkovitz
对于任何一个假设类，都可以将一个二部图联系起来，该图的一个顶点是一边的假设H，另一边是所有可能的标号样本X，并且一个假设与所有与其一致的标号样本相连。我们称这个图为假设图。我们证明了任何假设图是混合的假设类不能用少于Omega(log^2|H|)个记忆比特学习，除非学习者使用至少大量|H|^Omega(1)标记的例子。我们的工作建立在一个组合框架的基础上，该框架是我们在之前的工作中提出的，用于证明空间受限学习的下界。通过定义伪随机性的新概念--熵采样器，得到了强下界。拉兹用不同的想法得出了类似的结果。
With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses graph. We prove that any hypothesis class whose hypotheses graph is mixing cannot be learned using less than Omega(log^2 |H|) memory bits unless the learner uses at least a large number |H|^Omega(1) labeled examples. Our work builds on a combinatorial framework that we suggested in a previous work for proving lower bounds on space bounded learning. The strong lower bound is obtained by defining a new notion of pseudorandomness, the entropy sampler. Raz obtained a similar result using different ideas.