On Learning and Testing Decision Tree

• URL: http://arxiv.org/abs/2108.04587v1
• Date: Tue, 10 Aug 2021 11:04:06 GMT
• Title: On Learning and Testing Decision Tree
• Authors: Nader H. Bshouty and Catherine A. Haddad-Zaknoon
• Abstract summary: We give a new algorithm that achieves $phi(s,1/epsilon)=2O(log3s)/epsilon3)$. We also study the testability of depth-$d$ decision tree and give a it distribution free tester.
• Score: 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.

Related papers

• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• On Computing Optimal Tree Ensembles [7.424944196676223]
  Random forests and, more generally, (decisionnobreakdash-)tree ensembles are widely used methods for classification and regression. Recent algorithmic advances allow to compute decision trees that are optimal for various measures such as their size or depth. We provide two novel algorithms and corresponding lower bounds.
  arXiv  Detail & Related papers  (2023-06-07T13:30:43Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  We show that for any fixed $epsilon>0$ and depth $i$, there is a poly-time algorithm that learns random Xavier networks of depth $i$. The algorithm runs in time and sample complexity of $(bard)mathrmpoly(epsilon-1)$, where $bar d$ is the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to $(bard)mathrmpolylog(eps
  arXiv  Detail & Related papers  (2023-05-25T22:27:42Z)
• Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees [3.5509551353363644]
  We give the first algorithm that maintains an approximate decision tree over an arbitrary sequence of insertions and deletions of labeled examples. We provide a deterministic algorithm that maintains an $epsilon$-approximate tree using $O!left(fracd, f(n)n operatornamepolyfrachepsilonright)$ operations per update.
  arXiv  Detail & Related papers  (2023-02-08T11:02:58Z)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  We prove, under randomized ETH, superpolynomial lower bounds for two basic problems. Our results imply new lower bounds for distribution-free PAC learning and testing of decision trees. We show our lower bound for learning decision trees can be improved to $nOmega(log s)$.
  arXiv  Detail & Related papers  (2022-10-12T16:25:48Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  We give an $nO(loglog n)$-time membership query algorithm for properly and agnostically learning decision trees. Our algorithm shares similarities with practicals for learning decision trees. We show how every decision tree can be "pruned" so that every variable in the resulting tree is influential.
  arXiv  Detail & Related papers  (2021-09-01T22:12:47Z)
• Testing and reconstruction via decision trees [19.304587350775385]
  We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. A tester that runs in $mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time makes $mathrmpoly(log s,1/varepsilon)cdot n$ queries to an unknown function.
  arXiv  Detail & Related papers  (2020-12-16T04:18:00Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.