論文の概要: Testing and reconstruction via decision trees

• arxiv url: http://arxiv.org/abs/2012.08735v1
• Date: Wed, 16 Dec 2020 04:18:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-03 02:43:11.722381
• Title: Testing and reconstruction via decision trees
• Title（参考訳）: 決定木によるテストと再構築
• Authors: Guy Blanc, Jane Lange, Li-Yang Tan
• Abstract要約: 決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。 mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time で実行するテスターは、未知の関数への$mathrmpoly(log s, 1/varepsilon)cdot n$ queryを作る。
• 参考スコア（独自算出の注目度）: 19.304587350775385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. Our first result is a tester that runs in $\mathrm{poly}(\log s, 1/\varepsilon)\cdot n\log n$ time, makes $\mathrm{poly}(\log s,1/\varepsilon)\cdot \log n$ queries to an unknown function $f$, and: $\circ$ Accepts if $f$ is $\varepsilon$-close to a size-$s$ decision tree; $\circ$ Rejects if $f$ is $\Omega(\varepsilon)$-far from decision trees of size $s^{\tilde{O}((\log s)^2/\varepsilon^2)}$. Existing testers distinguish size-$s$ decision trees from those that are $\varepsilon$-far from from size-$s$ decision trees in $\mathrm{poly}(s^s,1/\varepsilon)\cdot n$ time with $\tilde{O}(s/\varepsilon)$ queries. We therefore solve an incomparable problem, but achieve doubly-exponential-in-$s$ and exponential-in-$s$ improvements in time and query complexities respectively. We obtain our tester by designing a reconstruction algorithm for decision trees: given query access to a function $f$ that is close to a small decision tree, this algorithm provides fast query access to a small decision tree that is close to $f$. By known relationships, our results yield reconstruction algorithms for numerous other boolean function properties -- Fourier degree, randomized and quantum query complexities, certificate complexity, sensitivity, etc. -- which in turn yield new testers for these properties. Finally, we give a hardness result for testing whether an unknown function is $\varepsilon$-close-to or $\Omega(\varepsilon)$-far-from size-$s$ decision trees. We show that an efficient algorithm for this task would yield an efficient algorithm for properly learning decision trees, a central open problem of learning theory. It has long been known that proper learning algorithms for any class $\mathcal{H}$ yield property testers for $\mathcal{H}$; this provides an example of a converse.
• Abstract（参考訳）: 決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。 最初の結果は、$\mathrm{poly}(\log s, 1/\varepsilon)\cdot n\log n$ timeで実行されるテスターで、$\mathrm{poly}(\log s,1/\varepsilon)\cdot \log n$クエリを未知の関数に$f$、$\circ$ accepts if $f$ is $\varepsilon$-close to a size-$s$ decision tree; $\circ$ rejects if $f$ is $\omega(\varepsilon)$-far from decision tree of size $s^{\tilde{o}((\log s)^2/\varepsilon^2)} とします。 既存のテスターは、$s$決定木と$\varepsilon$-farと$\mathrm{poly}(s^s,1/\varepsilon)\cdot n$ time with $\tilde{o}(s/\varepsilon)$ queryとを区別する。 したがって、比較不能な問題を解決するが、時間とクエリの複雑さの2倍の指数関数的改善をそれぞれ達成する。 このアルゴリズムは,小さな決定木に近い関数$f$に対するクエリアクセスを与えられた場合,f$に近い小さな決定木に対する高速なクエリアクセスを提供する。 既知の関係によって、我々の結果は、フーリエ度、ランダム化および量子クエリの複雑度、証明書の複雑さ、感度など、他の多くのブール関数特性の再構成アルゴリズムをもたらす。 これによって、これらのプロパティの新しいテスタが生まれます。 最後に、未知関数が$\varepsilon$-close-toか$\omega(\varepsilon)$-far-from size-$s$ decision treeであるかどうかをテストするための難しい結果を与える。 この課題に対する効率的なアルゴリズムは、学習理論の中心的なオープン問題である決定木を適切に学習するための効率的なアルゴリズムをもたらす。 任意のクラスに対する適切な学習アルゴリズムである$\mathcal{H}$ yield property testers for $\mathcal{H}$が知られている。

関連論文リスト

• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• 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)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。 その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。 学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
  論文  参考訳（メタデータ） (2022-10-12T16:25:48Z)
• On Learning and Testing Decision Tree [0.22843885788439797]
  我々は$phi(s,1/epsilon)=2O(log3s)/epsilon3)$を達成する新しいアルゴリズムを与える。 また,Deep-d$決定木の試験可能性について検討し,分布自由なテスターを与える。
  論文  参考訳（メタデータ） (2021-08-10T11:04:06Z)
• Learning stochastic decision trees [19.304587350775385]
  対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。 私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
  論文  参考訳（メタデータ） (2021-05-08T04:54:12Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)

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

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