论文标题
重建决策树
Reconstructing decision trees
论文作者
论文摘要
我们为决策树提供了第一个{\ sl重建算法}：给定对函数$ f $的查询，即$ \ mathrm {opt} $ - 接近size-$ s $决策树，我们的算法提供了查询$ t $ t $ t $ t $ t $ $ \ circ $ t $具有尺寸$ s = s^{o（（（\ log s）^2/\ varepsilon^3）} $; $ \ circ $ $ \ mathrm {dist}（f，t）\ le o（\ mathrm {opt}）+\ varepsilon $; $ \ circ $每个查询$ t $都用$ \ mathrm {poly}（（（\ log s）/\ varepsilon）\ cdot \ log n $ queries to $ f $，以及$ \ mathrm {poly}（（\ log s）/\ varepsilon \ cdot n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ time。 这产生了一个{\ sl耐受性测试仪}，该}区分了接近尺寸-$ s $决策树与远离尺寸-$ s $决策树的函数。对我们测试人员效率的$ s $的多聚集体依赖性呈指数级的依赖性，比现有测试仪的依赖性小。 由于众所周知，决策树的复杂性与许多其他布尔函数属性有关，因此我们的结果还为重建和测试这些属性提供了一种新的算法。
We give the first {\sl reconstruction algorithm} for decision trees: given queries to a function $f$ that is $\mathrm{opt}$-close to a size-$s$ decision tree, our algorithm provides query access to a decision tree $T$ where: $\circ$ $T$ has size $S = s^{O((\log s)^2/\varepsilon^3)}$; $\circ$ $\mathrm{dist}(f,T)\le O(\mathrm{opt})+\varepsilon$; $\circ$ Every query to $T$ is answered with $\mathrm{poly}((\log s)/\varepsilon)\cdot \log n$ queries to $f$ and in $\mathrm{poly}((\log s)/\varepsilon)\cdot n\log n$ time. This yields a {\sl tolerant tester} that distinguishes functions that are close to size-$s$ decision trees from those that are far from size-$S$ decision trees. The polylogarithmic dependence on $s$ in the efficiency of our tester is exponentially smaller than that of existing testers. Since decision tree complexity is well known to be related to numerous other boolean function properties, our results also provide a new algorithms for reconstructing and testing these properties.
