论文标题
带有假设的决策树，以识别单调布尔功能和分类
Decision Trees with Hypotheses for Recognition of Monotone Boolean Functions and for Sorting
论文作者
论文摘要
在本文中，我们考虑了基于每个属性的两个查询的决策树，并根据有关所有属性值的假设进行查询。这样的决策树类似于精确学习中研究的树，不仅允许会员资格，而且还允许等效查询。我们研究了具有$ n $变量的单调布尔函数的识别问题，$ n = 2，\ ldots，4 $，以及对线性订购的$ n $ pairwise不同元素进行排序的问题，$ n = 3，\ ldots，6 $。对于这些问题中的每一个，我们比较了与假设不同类型的最佳（相对于可实现节点的深度或可实现节点的数量）的复杂性。我们还研究了由基于熵的贪婪算法构建的决策树的复杂性，并分析了这些树木从这些树中得出的决策规则的长度。
In this paper, we consider decision trees that use both queries based on one attribute each and queries based on hypotheses about values of all attributes. Such decision trees are similar to ones studied in exact learning, where not only membership but also equivalence queries are allowed. We investigate the problem of recognition of monotone Boolean functions with $n$ variables, $n=2, \ldots, 4$, and the problem of sorting $n$ pairwise different elements from linearly ordered set, $n=3, \ldots, 6$. For each of these problems, we compare the complexity of different types of optimal (relative to the depth or the number of realizable nodes) decision trees with hypotheses. We also study the complexity of decision trees constructed by entropy-based greedy algorithm and analyze the length of decision rules derived from these trees.
