論文の概要: On Learning and Testing Decision Tree

• arxiv url: http://arxiv.org/abs/2108.04587v1
• Date: Tue, 10 Aug 2021 11:04:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-11 19:29:48.455832
• Title: On Learning and Testing Decision Tree
• Title（参考訳）: 学習とテストの意思決定木について
• Authors: Nader H. Bshouty and Catherine A. Haddad-Zaknoon
• Abstract要約: 我々は$phi(s,1/epsilon)=2O(log3s)/epsilon3)$を達成する新しいアルゴリズムを与える。 また,Deep-d$決定木の試験可能性について検討し,分布自由なテスターを与える。
• 参考スコア（独自算出の注目度）: 0.22843885788439797
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study learning and testing decision tree of size and depth that are significantly smaller than the number of attributes $n$. Our main result addresses the problem of poly$(n,1/\epsilon)$ time algorithms with poly$(s,1/\epsilon)$ query complexity (independent of $n$) that distinguish between functions that are decision trees of size $s$ from functions that are $\epsilon$-far from any decision tree of size $\phi(s,1/\epsilon)$, for some function $\phi > s$. The best known result is the recent one that follows from Blank, Lange and Tan,~\cite{BlancLT20}, that gives $\phi(s,1/\epsilon)=2^{O((\log^3s)/\epsilon^3)}$. In this paper, we give a new algorithm that achieves $\phi(s,1/\epsilon)=2^{O(\log^2 (s/\epsilon))}$. Moreover, we study the testability of depth-$d$ decision tree and give a {\it distribution free} tester that distinguishes between depth-$d$ decision tree and functions that are $\epsilon$-far from depth-$d^2$ decision tree. In particular, for decision trees of size $s$, the above result holds in the distribution-free model when the tree depth is $O(\log(s/\epsilon))$. We also give other new results in learning and testing of size-$s$ decision trees and depth-$d$ decision trees that follow from results in the literature and some results we prove in this paper.
• Abstract（参考訳）: 本稿では,n$の属性数よりもかなり小さいサイズと深さの学習とテストの意思決定木について検討する。 我々の主な結果はpoly$(n,1/\epsilon)$ time algorithm with poly$(s,1/\epsilon)$ query complexity (independent of $n$) with the function that are decision tree of size $s$ from that function that $\epsilon$-far from any decision tree of size $\phi(s,1/\epsilon)$ for some function $\phi > s$である。 最もよく知られた結果は、空白、ランジュ、タン、～\cite{blanclt20} から続き、$\phi(s,1/\epsilon)=2^{o((\log^3s)/\epsilon^3)}$ となる。 本稿では,$\phi(s,1/\epsilon)=2^{o(\log^2 (s/\epsilon))} を達成する新しいアルゴリズムを提案する。 さらに,Deep-d$決定木とDeep-d^2$決定木から$\epsilon$-farの関数を区別するDeep-d$決定木の有効性について検討し,Deep-d$決定木とDeep-d$決定木との区別を行う。 特に、$s$の決定木の場合、木深さが$O(\log(s/\epsilon))$であるとき、上記の結果は分布のないモデルに成り立つ。 また,本論文で得られた文献といくつかの結果をもとに,サイズ決定木と深さ決定木について,学習とテストに関する新たな結果を提示する。

関連論文リスト

• 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)
• On Computing Optimal Tree Ensembles [7.424944196676223]
  ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。 最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
  論文  参考訳（メタデータ） (2023-06-07T13:30:43Z)
• 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)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。 我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。 すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
  論文  参考訳（メタデータ） (2021-09-01T22:12:47Z)
• 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)
• 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)

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

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