提出简单算法求解最优决策树，逼近比仅8倍对数级别。
A Simple Approximation Algorithm for Optimal Decision Tree
- 基于贪心策略构造决策树，每次选择最能减少不确定性的查询。
- 理论证明期望查询成本不超过最优解的8倍ln m。
- 算法简洁易实现，适合需要快速部署的医疗诊断等场景。
最优决策树（ extit{ODT}）是主动学习、实体识别和医学诊断等应用中的核心问题。给定m个假设，其中真实假设按某种概率分布随机生成。算法需通过提问来识别真实假设，每个提问有固定成本且对每个假设产生已知响应。目标是最小化识别真实假设的期望查询成本。本文研究具有任意成本、概率和响应的一般情形。 extit{ODT} 无法在优于 \\( \ln m \\\) 的范围内被近似，已有算法可达到 \\$(O(\ln m))\\$ 近似比，但其方法或分析复杂，常数因子较大。本文提出一种简单算法与分析，证明其近似比为 \\$(8 \ln m)\\$。
原文摘要 · Abstract (English)
Optimal decision tree (\odt) is a fundamental problem arising in applications such as active learning, entity identification, and medical diagnosis. An instance of \odt is given by $m$ hypotheses, out of which an unknown ``true'' hypothesis is drawn according to some probability distribution. An algorithm needs to identify the true hypothesis by making queries: each query incurs a cost and has a known response for each hypothesis. The goal is to minimize the expected query cost to identify the true hypothesis. We consider the most general setting with arbitrary costs, probabilities and responses. \odt is NP-hard to approximate better than $\ln m$ and there are $O(\ln m)$ approximation algorithms known for it. However, these algorithms and/or their analyses are quite complex. Moreover, the leading constant factors are large. We provide a simple algorithm and analysis for \odt, proving an approximation ratio of $8 \ln m$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。