On learning read-k-satisfy-j DNF

被引：8

作者：

Aizenstein, H

Blum, A

Khardon, R

Kushilevitz, E

Pitt, L

Roth, D

机构：

[1] Univ Pittsburgh, Sch Med, Western Psychiat Inst & Clin, Pittsburgh, PA 15213 USA

[2] Carnegie Mellon Univ, Sch Comp Sci, Pittsburgh, PA 15213 USA

[3] Harvard Univ, Aiken Computat Lab, Cambridge, MA 02138 USA

[4] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[5] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 06期

关键词：

DNF; learning; computational learning theory; decision trees;

D O I：

10.1137/S0097539794274398

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for k . j = 0(logn/log log n), where n is the number of input variables.

引用

页码：1515 / 1530

页数：16

共 37 条

[1]

AIZENSTEIN H, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P170, DOI 10.1109/SFCS.1991.185366

[2]

Aizenstein H., 1992, Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, P71, DOI 10.1145/130385.130393

[3] ON THE LEARNABILITY OF DISJUNCTIVE NORMAL-FORM FORMULAS [J].

AIZENSTEIN, H ;

PITT, L .

MACHINE LEARNING, 1995, 19 (03) :183-208

[4]

Aizenstein H., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P523, DOI 10.1109/SFCS.1992.267799

[5]

AIZENSTEIN H, 1993, UIUCDCSR931813 U ILL

[6]

ANGLUIN D, 1990, MACH LEARN, V5, P121, DOI 10.1023/A:1022692615781

[7]

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

[8] LEARNING READ-ONCE FORMULAS WITH QUERIES [J].

ANGLUIN, D ;

HELLERSTEIN, L ;

KARPINSKI, M .

JOURNAL OF THE ACM, 1993, 40 (01) :185-210

[9]

Angluin D., 1988, Machine Learning, V2, P319, DOI 10.1007/BF00116828

[10] WHEN WONT MEMBERSHIP QUERIES HELP [J].

ANGLUIN, D ;

KHARITONOV, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 50 (02) :336-355

← 1 2 3 4 →