論文の概要: Properly Learning Decision Trees with Queries Is NP-Hard

• arxiv url: http://arxiv.org/abs/2307.04093v1
• Date: Sun, 9 Jul 2023 04:29:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-11 15:28:13.169348
• Title: Properly Learning Decision Trees with Queries Is NP-Hard
• Title（参考訳）: クエリで決定木を適切に学習するNP-Hard
• Authors: Caleb Koch and Carmen Strassle and Li-Yang Tan
• Abstract要約: PACがクエリで決定木を適切に学習することはNPハードであることを証明する。 我々は、決定木最小化の異なる問題に対して、最もよく知られた下界を単純化し、強化する。
• 参考スコア（独自算出の注目度）: 5.117810469621253
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro-Lavin-Raghavan 1999; Mehta-Raghavan 2002; Feldman 2016). While there has been a long line of work, dating back to (Pitt-Valiant 1988), establishing the hardness of properly learning decision trees from random examples, the more challenging setting of query learners necessitates different techniques and there were no previous lower bounds. En route to our main result, we simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization (Zantema-Bodlaender 2000; Sieling 2003). On a technical level, we introduce the notion of hardness distillation, which we study for decision tree complexity but can be considered for any complexity measure: for a function that requires large decision trees, we give a general method for identifying a small set of inputs that is responsible for its complexity. Our technique even rules out query learners that are allowed constant error. This contrasts with existing lower bounds for the setting of random examples which only hold for inverse-polynomial error. Our result, taken together with a recent almost-polynomial time query algorithm for properly learning decision trees under the uniform distribution (Blanc-Lange-Qiao-Tan 2022), demonstrates the dramatic impact of distributional assumptions on the problem.
• Abstract（参考訳）: PACが問合せ付き決定木を適切に学習することがNPハードであることを証明する(Bshouty 1993; Guijarro-Lavin-Raghavan 1999; Mehta-Raghavan 2002; Feldman 2016)。 ランダムな例から判断木を適切に学習することの難しさを確立する(pitt-valiant 1988)まで遡る長い作業があったが、クエリ学習者のより困難な設定にはさまざまなテクニックが必要であり、それまでの下限は存在しなかった。 そこで本研究では,決定木最小化問題(Zantema-Bodlaender 2000; Sieling 2003)について,最もよく知られた下界を単純化し,強化する。 技術的レベルでは、決定木複雑性について研究するが、いかなる複雑性尺度に対しても考慮できる硬度蒸留の概念を導入し、大きな決定木を必要とする関数に対しては、その複雑さに責任がある小さな入力の集合を識別する一般的な方法を与える。 我々の手法は、一定のエラーを許容するクエリ学習者を規則化さえしている。 これは、逆多項式誤差のみを保持するランダムな例の設定に対する既存の下界とは対照的である。 その結果,一様分布下で決定木を適切に学習する近多項時間問合せアルゴリズム(blanc-lange-qiao-tan 2022)を組み合わせることで,分布仮定が問題に劇的な影響を与えることを示した。

関連論文リスト

• Learning accurate and interpretable decision trees [27.203303726977616]
  我々は、同じドメインから繰り返しデータにアクセスして決定木学習アルゴリズムを設計するためのアプローチを開発する。 本研究では,ベイズ決定木学習における事前パラメータのチューニングの複雑さについて検討し,その結果を決定木回帰に拡張する。 また、学習した決定木の解釈可能性について検討し、決定木を用いた説明可能性と精度のトレードオフを最適化するためのデータ駆動型アプローチを提案する。
  論文  参考訳（メタデータ） (2024-05-24T20:10:10Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.0]
  古典的なクエリアルゴリズムが決定木として与えられると、古典的なクエリアルゴリズムよりも高速な量子クエリアルゴリズムはいつ存在するのか? 我々は、下層の決定木の構造に基づく一般的な構成を提供し、これが上から四進的な量子スピードアップをもたらすことを証明している。
  論文  参考訳（メタデータ） (2022-03-06T14:04:06Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Trading Complexity for Sparsity in Random Forest Explanations [20.87501058448681]
  決定木の厳格な多数を占める主要な要因である主な理由を紹介する。 さまざまなデータセットで実施された実験は、ランタイムの複雑さとスパシティのトレードオフの存在を明らかにしている。
  論文  参考訳（メタデータ） (2021-08-11T15:19:46Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  我々は、異なる確率変数の符号が、おそらく不等で未知の確率で独立に反転するときに、イジングモデルを学習するタスクを考える。 しかし, この不同一性は, 葉ノードが近傍と位置を交換して形成する小さな同値類に限られる。
  論文  参考訳（メタデータ） (2020-06-10T01:32:45Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。 本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2020-02-12T17:43:23Z)

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

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