RUI: Fourier-Based Learning of Fundamental Function Classes

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

Machine learning is increasingly used to automate many tasks, such as training email clients to recognize unwanted email messages. The knowledge gained by a machine learning algorithm must be represented internally in some form. For example, assume that an email filtering algorithm has learned that if an email message contains the phrase ``fast profits'' then it is very likely an unwanted message, while if it contains the phrase ``computational learning theory'' then it is likely a legitimate message. The algorithm might represent this knowledge by associating a large negative numeric weight with the first phrase and a large positive weight with the second. Given a new message, the algorithm could first determine which phrases were present in the message, sum the corresponding weights, and mark the message as unwanted if the sum was negative. The described knowledge representation is a form of linear threshold function; such functions are the basis for many common knowledge representations produced by machine learning programs.This research addresses foundational questions related to the learning of linear threshold functions and other important classes of functions. Answers to such questions should be useful to theoreticians and could lead to better applied machine learning algorithms and the identification of fundamental limitations of certain algorithmic approaches, saving wasted development efforts. The primary research methodology used is discrete Fourier analysis, and a second project goal is to develop new Fourier techniques applicable beyond learning. A third project objective is to provide a stimulating research experience to undergraduate and Master's students.