論文の概要: Superconstant Inapproximability of Decision Tree Learning

• arxiv url: http://arxiv.org/abs/2407.01402v1
• Date: Mon, 1 Jul 2024 15:53:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-03 20:51:04.369324
• Title: Superconstant Inapproximability of Decision Tree Learning
• Title（参考訳）: 決定木学習における超コンスタント不適応性
• Authors: Caleb Koch, Carmen Strassle, Li-Yang Tan,
• Abstract要約: PAC学習決定木をクエリで適切に学習する作業について検討する。 Koch, Strassle, および Tan の最近の研究は、仮説木 $T$ が最適に小さいことが要求されるこのタスクの最も厳密なバージョンは NP-hard であることを示した。 仮に$T$が最適の任意の定数係数の範囲内にあるとしても、そのタスクはNPハードのままであることを示す。
• 参考スコア（独自算出の注目度）: 7.420043502440765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree $T$ is required to be optimally small, is NP-hard. Their work leaves open the question of whether the task remains intractable if $T$ is only required to be close to optimal, say within a factor of 2, rather than exactly optimal. We answer this affirmatively and show that the task indeed remains NP-hard even if $T$ is allowed to be within any constant factor of optimal. More generally, our result allows for a smooth tradeoff between the hardness assumption and the inapproximability factor. As Koch et al.'s techniques do not appear to be amenable to such a strengthening, we first recover their result with a new and simpler proof, which we couple with a new XOR lemma for decision trees. While there is a large body of work on XOR lemmas for decision trees, our setting necessitates parameters that are extremely sharp, and are not known to be attainable by existing XOR lemmas. Our work also carries new implications for the related problem of Decision Tree Minimization.
• Abstract（参考訳）: PAC学習決定木をクエリで適切に学習する作業について検討する。 Koch, Strassle, および Tan の最近の研究は、仮説木 $T$ が最適に小さいことが要求されるこのタスクの最も厳密なバージョンは NP-hard であることを示した。 彼らの研究は、もし$T$がちょうど最適であるのではなく、例えば2の係数の範囲内でのみ必要であるなら、そのタスクが難解であるかどうかという疑問を解き放つ。 我々はこれを肯定的に答え、もし$T$が最適の定数係数内にあるとしても、そのタスクがNPハードのままであることを示す。 より一般的には、この結果は硬度仮定と不近似係数とのスムーズなトレードオフを可能にする。 Koch et al の手法はそのような強化には耐えられないように見えるため、我々はまず、決定木に対する新しい XOR レムマを結合した、より単純で単純な証明によって、それらの結果を回復する。 決定木に対するXOR補題には多くの研究があるが、我々の設定は極めて鋭く、既存のXOR補題では達成できないパラメータを必要とする。 また,本研究は,決定木最小化の問題に対する新たな意味ももたらしている。

関連論文リスト

• Properly Learning Decision Trees with Queries Is NP-Hard [5.117810469621253]
  PACがクエリで決定木を適切に学習することはNPハードであることを証明する。 我々は、決定木最小化の異なる問題に対して、最もよく知られた下界を単純化し、強化する。
  論文  参考訳（メタデータ） (2023-07-09T04:29:43Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。 その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。 学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
  論文  参考訳（メタデータ） (2022-10-12T16:25:48Z)
• On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
  十分な理由は、決定木を$T$とインスタンスを$x$とすると、決定を$T(x)$とします。 本稿では,決定木に対する$delta$sufficient-reasonsの計算複雑性について検討する。 決定木の構造的制約を識別し,SATソルバがこれらの問題に実際にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-06-30T21:58:31Z)
• There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes [64.05903267230467]
  相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。 場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
  論文  参考訳（メタデータ） (2022-06-09T04:23:26Z)
• Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
  決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。 16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
  論文  参考訳（メタデータ） (2021-12-29T18:22:28Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。 我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。 すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
  論文  参考訳（メタデータ） (2021-09-01T22:12:47Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  我々はUniversal Dependency Treebankから多くの言語における最先端の出力を分析する。 最悪の制約違反率は24%です。
  論文  参考訳（メタデータ） (2020-10-06T08:31:14Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。 我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
  論文  参考訳（メタデータ） (2020-08-20T03:42:40Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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