3 papers
cs.LG2023
Harnessing the Power of Choices in Decision Tree Learning
Guy Blanc, Jane Lange, Chirag Pabbaraju +3
We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These algorithms, which have been central t…
cs.LG2023
Multiclass Learnability Does Not Imply Sample Compression
Chirag Pabbaraju
A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the…
cs.LG2023
Provable benefits of score matching
Chirag Pabbaraju, Dhruv Rohatgi, Anish Sevekari +3
Score matching is an alternative to maximum likelihood (ML) for estimating a probability distribution parametrized up to a constant of proportionality. By fitting the ''score'' of…