CAREER: Structural Properties and Irrelevant Attributes: Implications for Learning and Complexity

这个项目的研究部分解决了计算学习理论和复杂性的基本问题。它还解决了由实际应用驱动的特定学习问题。计算学习理论为机器学习问题的正式研究提供了一个框架。该项目的第一个目标是确定学习的充分必要条件，证明下界，设计学习算法。一个重点是学习的查询模型，它代表了学习者可以向老师或专家提问或进行实验的情况。重点讨论了禁止投影对布尔函数类的可学习性的影响。该项目还旨在确定语言的结构属性，以证明复杂性结果。它特别针对解决有关具有随机性和非确定性能力的自动机的开放问题。该项目的另一个主要目标是开发在不相关数据存在下进行学习的算法。一个特殊的问题是开发PAC（可能近似正确）算法，该算法以以下方式在不相关属性存在时具有鲁棒性：它们仅依赖于它们正在学习的概念之外的几个属性。这个问题是理论性的，但受到实际应用（如医学诊断）的推动。在这些应用中，输出假设用于未来预测（诊断）。确定一个属性的值是昂贵的，可能涉及临床测试，因此需要限制必须确定其值的属性的数量。这个项目的教育部分包括本科和研究生教育的目标。在本科阶段，一个基本目标是使理论课程对广泛的学生易于理解和智力上令人兴奋。实现这一目标的方法包括：准备讲义，介绍历史和传记材料，使用算法动画向学生展示算法，以及使用计算机实验室的算法实验。在研究生阶段，该项目包括教授一门计算复杂性理论的研究生课程，其中包含重要的研究内容。此外，去年开始的计算学习理论阅读小组也将继续进行。

The research component of this project addresses fundamental questions in computational learning theory and complexity. It also addresses specific learning problems that are motivated by practical applications. Computational learning theory provides a framework for the formal study of problems in machine learning. The first goal of this project is to determine necessary and sufficient conditions for learning, prove lower bounds, and design learning algorithms. A focus is on query models of learning, which represent situations in which a learner can ask questions of a teacher or expert, or perform experiments. Emphasis is placed on the effect of forbidden projections on the learnability of investigating Boolean function classes. The project also aims to determine structural properties of languages, in order to prove complexity results. It is directed particularly at resolving open questions concerning automata with powers of both randomness and nondeterminism. Another major goal of the project is to develop algorithms for learning in the presence of irrelevant data. A particular problem is to develop PAC (Probably Approximately Correct) algorithms that are robust in the presence of irrelevant attributes in the following way: they depending on only a few more attributes then the concept they are learning. This problem is theoretical but motivated by practical applications, such as medical diagnosis. In these applications, output hypotheses are used for future prediction (diagnosis). Determining the value of an attribute is expensive perhaps involving a clinical test, and therefore it is desirable to limit the number of attributes whose values must be determined. The educational component of this project includes goals in both undergraduate and graduate education. At the undergraduate level a basic goal is to make theoretical courses accessible and intellectually exciting to a wide range of students. Methods for achieving this goal include the following: preparing handouts, introducing historical and biographical material, presenting algorithms to students using algorithm animation, and using computer lab `algorithm experiments.` At the graduate level, the project includes teaching a graduate course in computational complexity theory with a significant research component. In addition, a reading group in computational learning theory, started last year, will be continued.