This project studies "skewing", a novel machine learning approach that exploits the observation that some target functions are hard to learn only for some data distributions. Many practical machine learning algorithms, such as those for learning decision trees or Bayesian network structure, employ greedy strategies during learning, and although efficient, they have trouble learning some target functions, when presented with data having more than about a dozen variables or features; lookahead can help but is computationally expensive and prone to overfitting. Skewing is accurate when learning hard targets and it retains much of the efficiency of greedy strategies. This project addresses several research directions, including scaling to high-dimensional data, skewing for feature selection, and developing a theory of skewing. A broader impact of the project is further use of machine learning in Research Experiences for Undergraduates and in secondary school outreach. A second broader impact of the project is the development of machine learning systems that are more robust to the problem of myopia; these systems will be beneficial in a wide variety of practical domains including analysis of biological data.
