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.