Testing problems with sub-learning sample complexity
Testing problems with sub-learning sample complexity
复制标题
测试具有子学习样本复杂性的问题
DOI：
10.1145/279943.279996
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
M. Kearns;D. Ron
我们研究确定一类功能H的问题H，是否包含h中的未知目标函数f还是与H中的任何功能都“远”。与学习问题相比，我们必须在其中构建一个良好根据样本数据，在H中的F近似，在测试问题中，我们只需要确定良好的近似值。对于S s的决策树和具有S隐藏单位的特殊类别的神经网络所需的示例仅为〜O（p s）基于组合结构，表明这些类别可以通过一小部分的粗大分区来近似，并依靠重复的生日悖论的重复应用。
We study the problem of determining, for a class of functions H, whether an unknown target function f is contained in H or is “far” from any function in H. Thus, in contrast to problems of learning, where we must construct a good approximation to f in H on the basis of sample data, in problems of testing we are only required to determine the existence of a good approximation. Our main results demonstrate that, over the domain [0; 1] for constant d, the number of examples required for testing grows only as ~ O( p s) for both decision trees of size s and a special class of neural networks with s hidden units. This is in contrast to the (s) examples required for learning these same classes. Our tests are based on combinatorial constructions demonstrating that these classes can be approximated by small classes of coarse partitions of space, and rely on repeated application of the well-known birthday paradox.