RUI: Fourier Analysis of Learning Problems and Function Classes

点击翻译按钮获取中文摘要

The general area within which this research is performed is known ascomputational learning theory. The starting point for research in thisarea is typically the definition of mathematical models of what the term``learning'' may mean in a variety of settings. The concept of learningcaptured by these models is then formally analyzed, frequently leadingto algorithms for solving learning problems within the models as well asto proofs that certain problems cannot be solved. Theselearning-theoretic models and results lend support to more applied workin machine learning, which in turn has demonstrated utility inapplications ranging from e-commerce to advanced research on vehiclesthat drive themselves.This project adds to the existing body of learning-theoretic knowledgein a number of ways, including analysis of a relatively new model calledProbably Exactly Correct learning, development of an algorithm thatlearns arguably the broadest class of functions yet shown to belearnable (majority of AC0 functions), and work toward extendinghardness results for learnability of a fundamental class, the class ofparity functions. The key tool used in these and other project tasks isFourier analysis of classes of functions. While the primary purpose ofthe Fourier analysis is to support research into learning questions, aside benefit is the enhancement of our understanding of severalinteresting classes of functions, such as majority of AC0. Furthermore,this project provides a stimulating research experience to undergraduateand master's students at a university that, from an NSF perspective, islargely an undergraduate institution.