Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries

被引:48
作者
Domingo, C [1 ]
Mishra, N
Pitt, L
机构
[1] Tokyo Inst Technol, Dept Math & Comp Sci, Meguro Ku, Tokyo 1528522, Japan
[2] Hewlett Packard Labs, Palo Alto, CA 94304 USA
[3] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA
关键词
dualization; monotone CNF/DNF; read-restricted formulas; output polynomial-time algorithms; incremental algorithms; learning monotone formulas; membership queries;
D O I
10.1023/A:1007627028578
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We consider exact learning monotone CNF formulas in which each variable appears at most some constant k times ("read-k" monotone CNF). Let f : {0, 1}(n) --> {0, 1} be expressible as a read-k monotone CNF formula for some natural number k. We give an incremental output polynomial time algorithm for exact learning both the read-k CNF and (not necessarily read restricted) DNF descriptions of f. The algorithm's only method of obtaining information about f is through membership queries, i.e., by inquiring about the value f(x) for points x is an element of {0, 1}(n). The algorithm yields an incremental polynomial output time solution to the (read-k) monotone CNF/DNF dualization problem. The unrestricted versions remain open problems of importance.
引用
收藏
页码:89 / 110
页数:22
相关论文
共 43 条
[1]  
Agarwal R., 1994, P 20 INT C VER LARG, V487, P499
[2]  
Agrawal R., 1993, SIGMOD Record, V22, P207, DOI 10.1145/170036.170072
[3]  
Agrawal R., 1996, Advances in Knowledge Discovery and Data Mining, P307
[4]   On learning read-k-satisfy-j DNF [J].
Aizenstein, H ;
Blum, A ;
Khardon, R ;
Kushilevitz, E ;
Pitt, L ;
Roth, D .
SIAM JOURNAL ON COMPUTING, 1998, 27 (06) :1515-1530
[5]   Complexity theoretic hardness results for query learning [J].
Aizenstein, H ;
Hegedus, T ;
Hellerstein, L ;
Pitt, L .
COMPUTATIONAL COMPLEXITY, 1998, 7 (01) :19-53
[6]   LEARNING READ-ONCE FORMULAS WITH QUERIES [J].
ANGLUIN, D ;
HELLERSTEIN, L ;
KARPINSKI, M .
JOURNAL OF THE ACM, 1993, 40 (01) :185-210
[7]  
Angluin D., 1988, Machine Learning, V2, P319, DOI 10.1007/BF00116828
[8]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[9]   COMPLEXITY OF IDENTIFICATION AND DUALIZATION OF POSITIVE BOOLEAN FUNCTIONS [J].
BIOCH, JC ;
IBARAKI, T .
INFORMATION AND COMPUTATION, 1995, 123 (01) :50-63
[10]   LEARNING BOOLEAN READ-ONCE FORMULAS OVER GENERALIZED BASES [J].
BSHOUTY, NH ;
HANCOCK, TR ;
HELLERSTEIN, L .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 50 (03) :521-542