Learning decision trees from random examples

No abstract is available for this paper.

• Publication year

  1988

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  1988-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0890-5401(89)90001-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Inferring Decision Trees Using the Minimum Description Length Principle

  1989cited by this paper
• Learnability and the Vapnik-Chervonenkis dimension

  1989cited by this paper
• Computational limitations on learning from examples

  1988cited by this paper
• Quantifying Inductive Bias: AI Learning Algorithms and Valiant's Learning Framework

  1988cited by this paper
• Occam's Razor

  1987cited by this paper
• On the learnability of Boolean formulae

  1987cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987cited by this paper
• A theory of the learnable

  1984cited by this paper

• The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

  2026cites this paper
• Active Learning for Decision Trees with Provable Guarantees

  2026cites this paper
• Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis

  2025influential citation
• Actively Learning Halfspaces without Synthetic Data

  2025cites this paper
• Sensitivity and Query Complexity under Uncertainty

  2025cites this paper
• Ehrenfeucht-Haussler Rank and Chain of Thought

  2025cites this paper
• The Probably Approximately Correct Learning Model in Computational Learning Theory

  2025influential citation
• Superconstant Inapproximability of Decision Tree Learning

  2024influential citation
• Lifting to Randomized Parity Decision Trees

  2024cites this paper
• Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems

  2024influential citation
• On the communication complexity of finding a king in a tournament

  2024cites this paper
• On the Power of Decision Trees in Auto-Regressive Language Modeling

  2024cites this paper
• Towards a theory of model distillation

  2024cites this paper
• Linear threshold functions in decision lists, decision trees, and depth-2 circuits

  2023cites this paper
• Randomized versus Deterministic Decision Tree Size

  2023influential citation
• Lifting Uniform Learners via Distributional Decomposition

  2023cites this paper
• Perspective on complexity measures targetting read-once branching programs

  2023cites this paper
• Proving Unsatisfiability with Hitting Formulas

  2023cites this paper
• Machine Learning-Based Prediction of Machine Hours and Fuel Consumption: A Case Study in Aruwakkalu Limestone Quarry, Sri Lanka

  2023cites this paper
• Properly learning decision trees with queries is NP-hard

  2023cites this paper
• On Rotation Distance of Rank Bounded Trees

  2023cites this paper
• Superpolynomial Lower Bounds for Learning Monotone Classes

  2023cites this paper
• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles

  2023cites this paper
• On Low-End Obfuscation and Learning

  2023cites this paper
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees

  2022cites this paper
• Decision Tree Complexity versus Block Sensitivity and Degree

  2022cites this paper
• Efficient Quantum Agnostic Improper Learning of Decision Trees

  2022cites this paper
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing

  2022cites this paper
• On (Simple) Decision Tree Rank

  2022cites this paper
• Open Problem: Properly learning decision trees in polynomial time?

  2022influential citation
• Decision tree heuristics can fail, even in the smoothed setting

  2021cites this paper
• On Learning and Testing Decision Tree

  2021cites this paper
• Properly learning decision trees in almost polynomial time

  2021influential citation
• Reconstruction and testing via decision trees

  2021influential citation
• Bounded Memory Active Learning through Enriched Queries

  2021cites this paper
• Learning stochastic decision trees

  2021cites this paper
• Machine learning-driven new material discovery

  2020cites this paper
• Testing and reconstruction via decision trees

  2020cites this paper
• Efficient Algorithms for Multidimensional Segmented Regression

  2020cites this paper
• Efficient Contextual Bandits with Continuous Actions

  2020cites this paper
• Universal guarantees for decision tree induction via a higher-order splitting criterion

  2020cites this paper
• Reconstructing Decision Trees

  2020cites this paper
• Query strategies for priced information, revisited

  2020cites this paper
• On the Optimality of Trees Generated by ID3

  2019cites this paper
• The log-approximate-rank conjecture is false

  2019cites this paper
• L G ] 1 9 Fe b 20 19 Beyond the Low-Degree Algorithm : Mixtures of Subcubes and Their Applications

  2019cites this paper
• ID3 Learns Juntas for Smoothed Product Distributions

  2019cites this paper
• Query-driven PAC-Learning for Reasoning

  2019cites this paper
• Top-down induction of decision trees: rigorous guarantees and inherent limitations

  2019cites this paper
• Beyond the low-degree algorithm: mixtures of subcubes and their applications

  2018influential citation
• 10-11-2003 Learning DNF From Random Walks

  2017cites this paper
• Submodular Goal Value of Boolean Functions

  2017cites this paper
• Integrated Common Sense Learning and Planning in POMDPs

  2016influential citation
• The Complexity of DNF of Parities

  2016cites this paper
• On the Goal Value of a Boolean Function

  2016cites this paper
• Multi-level repair decision-making process for composite structures

  2016cites this paper
• Lower Bounds for Linear Decision Trees with Bounded Weights

  2015cites this paper
• Patient Populations, Clinical Associations, and System Efficiency in Healthcare Delivery System

  2015cites this paper
• Learning Using 1-Local Membership Queries

  2015cites this paper
• The Complexity of some exact and approximate isomorphism problems[HBNI Th80]

  2014cites this paper
• (Nearly-)tight bounds on the contiguity and linearity of cographs

  2014cites this paper
• Learning high-dimensional networks with nonlinear interactions by a novel tree-embedded graphical model

  2014cites this paper
• Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees

  2013cites this paper
• On the Isomorphism Problem for Decision Trees and Decision Lists

  2013cites this paper
• A Polynomial Time Algorithm for Lossy Population Recovery

  2013cites this paper
• Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs

  2013influential citation
• Restriction access

  2012cites this paper
• A Practical View of Large-Scale Classication: Feature Selection and Real-Time Classication

  2012cites this paper
• Learning implicitly in reasoning in PAC-Semantics

  2012influential citation
• Hierarchical linear support vector machine

  2012cites this paper
• (Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs

  2012cites this paper
• Boolean Function Complexity Advances and Frontiers

  2012cites this paper
• Logical analysis of data: classification with justification

  2011cites this paper
• Efficient and provably secure steganography

  2011cites this paper
• Grey-box steganography

  2011cites this paper
• Dynamic Successive Feed-Forward Neural Network for Learning Fuzzy Decision Tree

  2011cites this paper
• k + Decision Trees - (Extended Abstract)

  2010cites this paper
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators

  2010cites this paper
• A Computational Decision Theory for Interactive Assistants

  2010cites this paper
• An Algebraic Perspective on Boolean Function Learning

  2009cites this paper
• Lower Bounds on Quantum Query Complexity for Read-Once Decision Trees with Parity Nodes

  2009cites this paper
• On the learnability of monotone functions

  2009cites this paper
• Collisions Lead to Shallower Decision Trees

  2008cites this paper
• Decision trees are PAC-learnable from most product distributions: a smoothed analysis

  2008cites this paper
• Agnostically learning decision trees

  2008cites this paper
• Online Learning versus Ooine Learning

  2007cites this paper
• A Decision-Theoretic Model of Assistance

  2007cites this paper
• Learnability of Some Eecient Representations of Boolean Functions

  2007cites this paper
• Improving access to organized information

  2006cites this paper
• Exact Learning Composed Classes with a Small Number of Mistakes

  2006cites this paper
• Toward Attribute Efficient Learning of Decision Lists and Parities

  2006cites this paper
• On PAC learning algorithms for rich Boolean function classes

  2006influential citation
• Learning Comprehensible Theories from Structured Data

  2005cites this paper
• Learning mixtures of product distributions over discrete domains

  2005cites this paper
• Learning Random Log-Depth Decision Trees under Uniform Distribution

  2005cites this paper
• Learning with Decision Lists of Data-Dependent Features

  2005cites this paper
• Generalization Behaviour of Alkemic Decision Trees

  2005cites this paper
• The strength of weak learnability

  2004cites this paper
• Learning Conjunctions of Horn Clauses

  2004cites this paper
• Learnability and automatizability

  2004cites this paper