Learning Random Log-Depth Decision Trees under Uniform Distribution
Learning Random Log-Depth Decision Trees under Uniform Distribution
复制标题
学习均匀分布下的随机对数深度决策树
DOI：
10.1137/s0097539704444555
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
J. C. Jackson;R. Servedio
我们考虑了随机对数深度决策树的三种自然模型。我们给出了一个有效的算法，对于这些模型中的每一个，作为决策树，除了使用均匀分布的随机示例的逆多项式分数之外，其他所有模型都可以学习。
We consider three natural models of random log-depth decision trees. We give an efficient algorithm that for each of these models learns-as a decision tree-all but an inverse polynomial fraction of such trees using only uniformly distributed random examples.