EXACT LEARNING BOOLEAN FUNCTIONS VIA THE MONOTONE THEORY

被引：103

作者：

BSHOUTY, NH

机构：

[1] Department of Computer Science, The University of Calgary, Calgary

来源：

INFORMATION AND COMPUTATION | 1995年 / 123卷 / 01期

关键词：

D O I：

10.1006/inco.1995.1164

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the learnability of boolean functions from membership and equivalence queries. We develop the Monotone Theory that proves (1) Any boolean function is learnable in polynomial time in its minimal disjunctive normal form size, its minimal conjunctive normal form size, and the number of variables n. In particular, (2) Decision trees are learnable. Our algorithms are in the model of exact learning with membership queries and unrestricted equivalence queries. The hypotheses to the equivalence queries and the output hypotheses are depth 3 formulas. (C) 1995 Academic Press. Inc.

引用

页码：146 / 153

页数：8

共 24 条

[1]

AIZENSTEIN H, 1992, 5TH P ANN WORKSH COM, P71

[2]

AIZENSTEIN H, 1991, 32ND P S F COMP SCI

[3]

AIZENSTEIN H, 1992, 33RD P ANN IEEE S F, P523

[4] CONSTRUCTION OF ASYMPTOTICALLY GOOD LOW-RATE ERROR-CORRECTING CODES THROUGH PSEUDORANDOM GRAPHS [J].

ALON, N ;

BRUCK, J ;

NAOR, J ;

NAOR, M ;

ROTH, RM .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1992, 38 (02) :509-516

[5]

ANGLUIN D, 1992, MACH LEARN, V9, P147, DOI 10.1007/BF00992675

[6]

Angluin D., 1988, Machine Learning, V2, P319, DOI 10.1023/A:1022821128753

[7]

ANGLUIN D, 1991, 23RD P ANN ACM S THE, P444

[8] RANK-R DECISION TREES ARE A SUBCLASS OF R-DECISION LISTS [J].

BLUM, A .

INFORMATION PROCESSING LETTERS, 1992, 42 (04) :183-185

[9]

BLUM A, 1992, 24TH P ANN ACM S THE, P382

[10]

BSHOUTY NH, 1992, 24TH P ANN ACM S THE

← 1 2 3 →