Toward Attribute Efficient Learning of Decision Lists and Parities
By Adam R. Klivans, Rocco A. Servedio. 2006
83 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Statistical Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Cynthia Rudin
- Jonathan Ullman
- Tong Wang
- Salil P. Vadhan
- Himabindu Lakkaraju
- Philip M. Long
- Margo I. Seltzer
- Allison Chang
In Statistical Learning Theory
- Salil P. Vadhan
- Margo I. Seltzer
- Chudi Zhong
- Jonathan Ullman
- Philip M. Long
- Jimmy J. Lin
- Diane Hu
- Justin Thaler
Citations in the corpus
- Generalized and Scalable Optimal Sparse Decision Trees (2020, background): “It is possible to create assumptions that reduce hard decision tree optimization to cases where greedy algorithms suffice, such as independence between features (Klivans & Servedio, 2006), but these assumptions do not hold in reality.”
- Optimal Sparse Decision Trees (2019, background): “Other works [11] make overly strong assumptions (e.”
- Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, background): “Learning decision lists has been particularly well studied [5, 38, 21] and has been successfully used for building small and interpretable models [3, 24].”
- ORC: Ordered Rules for ClassificationA Discrete Optimization Approach to Associative Classification (2012, background): “The second category of sorted-rule-based classification algorithms produces decision lists [see Rivest, 1987, Klivans and Servedio, 2006, Sokolova et al., 2003, Anthony, 2005, Long and Servedio, 2007, Marchand and Sokolova, 2005, Rudin et al., 2011].”
- Faster Algorithms for Privately Releasing Marginals (2012, methodology): “We can approximate disjunctions over the set Y k using a well-known transformation of the Chebyshev polynomials (see, e.g., [17, Theorem 8] and [15, Claim 5.4]).”
- Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions (2006, methodology): “It is well known that the “halving algorithm” (see [1, 2, 19]) can learn length-k decision lists using only O(k log n) examples, but the running time of the algorithm is nk. Klivans and Servedio [16] used polynomial threshold functions together with Winnow to obtain a tradeoff between running time a”