@inproceedings{0b76444fad9a4d9490465db8e3299ae1,
title = "Why skewing works: Learning difficult boolean functions with greedy tree learners",
abstract = "We analyze skewing, an approach that has been empirically observed to enable greedy decision tree learners to learn {"}difficult{"} Boolean functions, such as parity, in the presence of irrelevant variables. We prove that, in an idealized setting, for any function and choice of skew parameters, skewing finds relevant variables with probability 1. We present experiments exploring how different parameter choices affect the success of skewing in empirical settings. Finally, we analyze a variant of skewing called Sequential Skewing.",
author = "Bernard Rosell and Lisa Hellerstein and Soumya Ray and David Page",
year = "2005",
language = "English (US)",
isbn = "1595931805",
series = "ICML 2005 - Proceedings of the 22nd International Conference on Machine Learning",
pages = "729--736",
editor = "L. Raedt and S. Wrobel",
booktitle = "ICML 2005 - Proceedings of the 22nd International Conference on Machine Learning",
note = "ICML 2005: 22nd International Conference on Machine Learning ; Conference date: 07-08-2005 Through 11-08-2005",
}