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.