論文の概要: Superpolynomial Lower Bounds for Decision Tree Learning and Testing
- arxiv url: http://arxiv.org/abs/2210.06375v1
- Date: Wed, 12 Oct 2022 16:25:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 16:19:29.201796
- Title: Superpolynomial Lower Bounds for Decision Tree Learning and Testing
- Title（参考訳）: 決定木学習とテストのための超多項下限
- Authors: Caleb Koch and Carmen Strassle and Li-Yang Tan
- Abstract要約: ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。
その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。
学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
- 参考スコア（独自算出の注目度）: 5.117810469621253
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish new hardness results for decision tree optimization problems,
adding to a line of work that dates back to Hyafil and Rivest in 1976. We
prove, under randomized ETH, superpolynomial lower bounds for two basic
problems: given an explicit representation of a function $f$ and a generator
for a distribution $\mathcal{D}$, construct a small decision tree approximator
for $f$ under $\mathcal{D}$, and decide if there is a small decision tree
approximator for $f$ under $\mathcal{D}$.
Our results imply new lower bounds for distribution-free PAC learning and
testing of decision trees, settings in which the algorithm only has restricted
access to $f$ and $\mathcal{D}$. Specifically, we show: $n$-variable size-$s$
decision trees cannot be properly PAC learned in time $n^{\tilde{O}(\log\log
s)}$, and depth-$d$ decision trees cannot be tested in time $\exp(d^{\,O(1)})$.
For learning, the previous best lower bound only ruled out
$\text{poly}(n)$-time algorithms (Alekhnovich, Braverman, Feldman, Klivans, and
Pitassi, 2009). For testing, recent work gives similar though incomparable
bounds in the setting where $f$ is random and $\mathcal{D}$ is nonexplicit
(Blais, Ferreira Pinto Jr., and Harms, 2021). Assuming a plausible conjecture
on the hardness of Set-Cover, we show our lower bound for learning decision
trees can be improved to $n^{\Omega(\log s)}$, matching the best known upper
bound of $n^{O(\log s)}$ due to Ehrenfeucht and Haussler (1989).
We obtain our results within a unified framework that leverages recent
progress in two lines of work: the inapproximability of Set-Cover and XOR
lemmas for query complexity. Our framework is versatile and yields results for
related concept classes such as juntas and DNF formulas.
- Abstract（参考訳）: 決定木最適化問題に対する新しい硬度結果を確立し、1976年にHyafil と Rivest にさかのぼる一連の作業を加えた。
関数 $f$ と分布 $\mathcal{d}$ の明示的な表現を与え、$\mathcal{d}$ 以下の小さな決定木近似器を構築し、$\mathcal{d}$ の下で$f$ の小さな決定木近似器が存在するかどうかを判定する。
この結果から,アルゴリズムが$f$と$\mathcal{D}$にしかアクセスできないような,分散のないPAC学習と決定木テストのための新しい下位境界が示唆された。
具体的には、$n$-variable size-$s$ decision treeは時間$n^{\tilde{O}(\log\log s)}$で学べず、deep-$d$ decision treeは時間$\exp(d^{\,O(1)})$でテストできない。
学習において、以前の最下限は$\text{poly}(n)$-timeアルゴリズム(Alekhnovich, Braverman, Feldman, Klivans, Pitassi, 2009)のみを除外した。
テストのために、最近の研究は、$f$がランダムで$\mathcal{d}$がunexplicit(blais, ferreira pinto jr., harms, 2021)という設定で類似しているが比較できない境界を与える。
Set-Cover の硬さに関する妥当な予想を仮定すると、学習決定木に対する下限は、Ehrenfeucht と Haussler (1989) により、最もよく知られた上限の$n^{O(\log s)}$と一致する$n^{\Omega(\log s)}$に改善できることを示す。
クエリ複雑性に対するset-cover と xor lemmas の近似可能性という,最近の2つの作業の進歩を活かした統一フレームワークで結果を得た。
我々のフレームワークは汎用性があり、juntasやdnf式のような関連する概念クラスの結果をもたらします。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees [3.5509551353363644]
ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-08T11:02:58Z) - On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
十分な理由は、決定木を$T$とインスタンスを$x$とすると、決定を$T(x)$とします。
本稿では,決定木に対する$delta$sufficient-reasonsの計算複雑性について検討する。
決定木の構造的制約を識別し,SATソルバがこれらの問題に実際にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-06-30T21:58:31Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - On Learning and Testing Decision Tree [0.22843885788439797]
我々は$phi(s,1/epsilon)=2O(log3s)/epsilon3)$を達成する新しいアルゴリズムを与える。
また,Deep-d$決定木の試験可能性について検討し,分布自由なテスターを与える。
論文 参考訳（メタデータ） (2021-08-10T11:04:06Z) - Testing and reconstruction via decision trees [19.304587350775385]
決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。
mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time で実行するテスターは、未知の関数への$mathrmpoly(log s, 1/varepsilon)cdot n$ queryを作る。
論文 参考訳（メタデータ） (2020-12-16T04:18:00Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。
すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。
アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
論文 参考訳（メタデータ） (2020-06-01T06:44:07Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。