On Learning and Characterizing Classes of Boolean Functions

计算学习中的一个中心问题是确定哪些类型的布尔函数(概念)可以通过有效的算法来学习。学习的难度在不同的学习模式中可能会有所不同。这些模型代表了学习可能发生的不同条件。这个项目的一个主要目标是在各种学习模型中区分可有效学习的布尔函数类和不可学习的布尔函数类。将研究的学习模型包括查询模型和属性有效模型。在查询模型中，学习算法可以通过询问查询来获得关于正在学习的函数的信息。查询模型代表学习者可以接触到老师或专家，或者可以进行实验和观察结果的情况。在属性效率模型中，即使在存在大量无关信息的情况下，学习者也被期望有效地学习。在文本自动分类等应用机器学习问题中，无关信息的存在是一个常见的复杂问题。本项目的另一个主要方面涉及布尔函数类的刻画。该项目旨在发现布尔函数类的特征与学习和识别这些类中的函数的复杂性之间的联系。这种方法的灵感部分来自于图论中的工作。布尔函数类的刻画还没有像图类刻画那样被广泛地研究。该项目的一个目标是为布尔函数类做已经为图类所做的事情：在类的刻画和涉及类的问题的复杂性之间建立联系。这个项目的重点将是在基本运算下关闭的布尔函数类，例如变量的置换和常量的变量替换。将注意力限制在这样的函数类上的动机是为了在学习和复杂性方面获得优雅的结果，这些结果可能并不适用于所有布尔函数类。

CCR-9877122HellersteinA central problem in computational learning is to determine which types of Boolean functions (concepts) can be learned by efficient algorithms. The difficulty of learning can vary in different learning models. The models represent different conditions under which learning might take place. A major goal of this project is to distinguish, in a variety of learning models, between classes of Boolean functions that are efficiently learnable and classes that are not.Among the learning models that will be studied are query models and attribute-efficient models. In query models, the learning algorithm can obtain information about the function being learned by asking queries. Query models represent situations in which the learner has access to a teacher or expert, or can perform experiments and observe outcome. In attribute-efficient models, the learner is expected to learn efficiently even in the presence of a lot of irrelevant information. The presence of irrelevant information is a common complication in applied machine learning problems such as automatic text categorization.Another major aspect of this project concerns characterizations of classes of Boolean functions. The project aims to discover connections between characterizations of Boolean function classes and the complexity of learning and recognizing functions in those classes. This approach is inspired in part by work in graph theory. The characterization of Boolean function classes has not been studied as extensively as the characterization of graph classes. A goal of the project is to do for classes of Boolean functions what has been done for classes of graphs: to establish connections between characterizations of classes and the complexity of problems involving the classes. A focus of this project will be on classes of Boolean functions that are closed under basic operations, such as permutation of variables, and substitution of constants for variables. The motivation for restricting attention to such function classes is to obtain elegant results in learning and complexity, results that may not hold for all Boolean function classes.