論文の概要: A Simple Approximation Algorithm for Optimal Decision Tree

• arxiv url: http://arxiv.org/abs/2505.15641v1
• Date: Wed, 21 May 2025 15:21:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-22 15:42:59.736644
• Title: A Simple Approximation Algorithm for Optimal Decision Tree
• Title（参考訳）: 最適決定木に対する簡易近似アルゴリズム
• Authors: Zhengjia Zhuo, Viswanath Nagarajan,
• Abstract要約: 最適決定木(odt)は、アクティブラーニング、エンティティ識別、医療診断などの応用における基本的な問題である。 各クエリはコストを発生させ、各仮説に対して既知の応答を持つ。 odt の簡単なアルゴリズムと解析を行い,近似比が 8 ln m$ であることを示す。
• 参考スコア（独自算出の注目度）: 5.26062227842158
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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$.
• Abstract（参考訳）: 最適決定木 (\odt) は、能動的学習、実体識別、医療診断などの応用における基本的な問題である。 odt の例は$m$仮説によって与えられ、ある確率分布に従って未知の `true'' 仮説が引き出される。 各クエリはコストを発生させ、各仮説に対して既知の応答を持つ。 目標は、真の仮説を特定するために、期待されるクエリコストを最小限にすることである。 任意のコスト、確率、レスポンスを持つ最も一般的な設定を考えます。 \odt は$\ln m$ よりもよく近似できるNPハードであり、それで知られる$O(\ln m)$近似アルゴリズムが存在する。 しかし、これらのアルゴリズムや分析は非常に複雑である。 さらに、先頭の定数因子は大きい。 簡単なアルゴリズムと解析を行い、近似比が 8 \ln m$ であることを示す。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity [8.100854060749212]
  本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。 我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
  論文  参考訳（メタデータ） (2023-12-09T19:22:10Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。 $mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-17T15:27:33Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Approximation Algorithms for Active Sequential Hypothesis Testing [3.840659854046464]
  本稿では,アクティブシーケンシャル仮説テストのための最初の近似アルゴリズムを提案する。 アルゴリズムの性能を合成データと実データの両方を用いて数値的に調査し,アルゴリズムが提案した方針を上回っていることを示した。
  論文  参考訳（メタデータ） (2021-03-07T03:49:19Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。