Learning monotone decision trees in polynomial time
Learning monotone decision trees in polynomial time
复制标题
在多项式时间内学习单调决策树
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
Ryan O'Donnell;R. Servedio
本文给出了一个算法，该算法可以学习任意单调布尔函数f：{-1，1} nrn {-1，1}到任意常数精度，在均匀分布下，在n中的时间多项式中，在f的决策树大小中.这是第一个算法，可以学习任意单调布尔函数，以高精度，使用随机的例子，在时间多项式的复杂性的合理措施f。结果的一个关键成分是一个新的界限，表明大小为s的决策树计算的任何单调函数的平均灵敏度必须是最radic（log s）。这个界限已经被证明在决策树复杂性的研究中具有独立的效用（Schramm等人，2005年）。我们以各种方式推广上述基本不等式和学习结果;特别是分区大小（比决策树大小更强的复杂性度量），布尔立方体上的p偏置度量（而不仅仅是均匀分布）和实值（而不仅仅是布尔值）函数
We give an algorithm that learns any monotone Boolean function f: {-1, 1}n rarr {-1, 1} to any constant accuracy, under the uniform distribution, in time polynomial in n and in the decision tree size of f. This is the first algorithm that can learn arbitrary monotone Boolean functions to high accuracy, using random examples only, in time polynomial in a reasonable measure of the complexity of f. A key ingredient of the result is a new bound showing that the average sensitivity of any monotone function computed by a decision tree of size s must be at most radic(log s). This bound has already proved to be of independent utility in the study of decision tree complexity (Schramm et al., 2005). We generalize the basic inequality and learning result described above in various ways; specifically, to partition size (a stronger complexity measure than decision tree size), p-biased measures over the Boolean cube (rather than just the uniform distribution), and real-valued (rather than just Boolean-valued) functions