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.