On the learnability of Boolean formulae
On the learnability of Boolean formulae
复制标题
论布尔公式的可学习性
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
L. Valiant
中科院分区：
文献类型：
--
作者：
M. Kearns;Ming Li;L. Pitt;L. Valiant
我们研究了从实例中学习布尔表达式的计算可行性。我们的目标是证明结果，并开发通用技术，阐明在多项式时间内可学习的表达式类和显然不可学习的表达式类之间的边界。对于布尔表达式和其他可能的知识表示，这个边界的阐明是复杂性理论对人工智能潜在贡献的一个例子。我们采用在/lo]中引入的无分布学习模型。在[4，10，11，12]中可以找到这个模型的更完整的讨论和论证。[4]包括一些讨论，更具体地说，有关无限表示，如几何的，而不是有限的情况下，布尔函数。其他近期相关工作见[1，2，7，& g]。本文的结果分为三类：可学习类的闭包性质，负结果和分布特定的正结果。闭包属性有两种。在第3节中，我们讨论了可学习类的成员在布尔运算下的闭包。假设类可以从正面或负面的经验中学习，
We study the computational feasibility of learning boolean expressions from examples. Our goals are to prove results and develop general techniques that shed light on the boundary between the classes of expressions that are learnable in polynomial time and those that are apparently not. The elucidation of this boundary, for boolean expressions and possibly other knowledge representations, is an example of the potential contribution of complexity theory to artificial intelligence. We employ the distribution-free model of learning introduced in /lo]. A more complete discussion and justification of this model can be found in [4,10,11,12]. [4] includes some discussion that is relevant more particularly to infinite representations, such as geometric ones, rather than the finite case of boolean functions. For other recent related work see [1,2,7,&g]. The results of this paper fall into three categories: closure properties of learnable classes, negative results, and distribution-specific positive results. The closure properties are of two kinds. In section 3 we discuss closure under boolean operations on the members of the learnable classes. The assumption that the classes are learnable from positive or negative ex-