Abstract
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 ∈ {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.
Article PDF
Similar content being viewed by others
References
Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining associations between sets of items in massive databases. Proc. of the ACM-SIGMOD 1993 International Conference on Management of Data (pp. 207–216).Washington, DC.
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., & Verkamo, I. (1996). Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining (pp. 307–328). Menlo Park, CA: AAAI Press.
Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proc. of the 20th International Conference on Very Large Databases. Santiago, Chile.
Aizenstein, H., Blum, A., Khardon, R., Kushilevitz, E., Pitt, L., & Roth, D. (1998a). On learning read-k-satisfy-j DNF. SIAM Journal on Computing, 27(6), 1515–1530.
Aizenstein, H., Hegedus, T., Hellerstein, L., & Pitt, L. (1998b). Complexity theoretic hardness results for query learning. Computational Complexity, 7, 19–53.
Angluin, D. (1988). Queries and concept learning. Machine Learning, 2(4), 319–342.
Angluin, D., Hellerstein, L., & Karpinski, M. (1993). Learning read-once formulas with queries. Journal of the ACM, 40(1), 185–210.
Bioch, J., & Ibaraki, T. (1995). Complexity of identification and dualization of positive Boolean functions. Information and Computation, 123(1), 50–63.
Bshouty, N., Cleve, R., Gavald`a, R., Kannan, S., & Tamon, C. (1996). Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52(3), 421–433.
Bshouty, N., Hancock, T., & Hellerstein, L. (1995a) Learning arithmetic read-once formulas. SIAM Journal on Computing, 24(4), 706–735.
Bshouty, N., Hancock, T., & Hellerstein, L. (1995b). Learning Boolean read-once formulas over generalized bases. Journal of Computer and System Sciences, 50(3), 521–542.
Eiter, T., & Gottlob, G. (1995). Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6), 1278–1304.
Fredman, M., & Khachiyan, L. (1996). On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21(3), 618–628.
Gainanov, D.N. (1984). On one criterion of optimality of an algorithm for evaluating monotonic boolean functions. USSR Computational Mathematics and Mathematical Physics, 24, 176–181.
Garey, M., & Johnson, D. (1979). Computers and intractability—A guide to the theory of NP-completeness.W.H. Freeman and Company.
Godfrey, P. (1997). Minimization in cooperative response to failing queries. International Journal of Cooperative Information Systems World Scientific, 6(2), 95–149.
Gunopulos, D., Mannila, H., & Saluja, S. (1997). Discovering all most specific sentences by randomized algorithms. In F. Afrati & P. Kolaitis (Eds.), Proceedings of International Conference on Database Theory. Delphi, Greece.
Gurvich, V., & Khachiyan, L. (1995). Generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions. (Technical Report, LCSR-TR-251). Dept. of Computer Science, Rutgers University, Discrete Applied Math, to appear.
Hancock, T., & Mansour, Y. (1991). Learning monotone kμ-DNF formulas on product distributions. Proc. 4th Annu. Workshop on Comput. Learning Theory (pp. 179–183). San Mateo, CA: Morgan Kaufmann.
Hirsh, H., Mishra, N., & Pitt, L. (1997). Version spaces without boundary sets. Proceedings of the 14th National Conference on Artificial Intelligence (pp. 491–496).
Johnson, D., Papadimitriou, C., & Yannakakis, M. (1988).Ongenerating all maximal independent sets. Information Processing Letters, 27(3), 119–123.
Karp, R., & Wigderson, A. (1985). A fast parallel algorithm for the maximal independent set problem. Journal of the ACM, 32(4), 762–773.
Kautz, H., Kearns, M., & Selman, B. (1993). Reasoning with characteristic models. Proceedings of the 11th National Conference on Artificial Intelligence (pp. 34–39). Washington, DC: AAAI Press.
Khardon, R. (1995). Translating between horn representations and their characteristic models. Journal of AI Research, 3, 349–372.
Khardon, R., Mannila, H., & Roth, D. (1999). Reasoning with examples: Propositional formulae and database dependencies. Acta Informatica, 36(4), 267–286.
Khardon, R., & Roth, D. (1994). Reasoning with models. Proceedings of the 12th National Conference on Artificial Intelligence, (Vol. 2, pp. 1148–1153). Seattle, Washington: AAAI Press.
Kivinen, J., & Mannila, H. (1995). Approximate inference of functional dependencies from relations. Theoretical Computer Science, 149(1), 129–149.
Korobkov, V. (1965). On monotone functions of the algebra of logic. Problemy Kibernetiki, 13, 5–28.
Lawler, E., Lenstra, J., & Kan, A. Rinnooy (1980). Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM Journal on Computing, 9(3), 558–565.
Makino, K., & Ibaraki, T. (1997). The maximum latency and identification of positive Boolean functions. SIAM Journal on Computing, 26, 1363–1383.
Makino, K., & Ibaraki, T. (1998). A fast and simple algorithm for identifying 2-monotonic positive Boolean functions. Journal of Algorithms, 26(2), 291–305.
Mannila, H., & Räihä, K. (1992a). On the complexity of inferring functional dependencies. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 40.
Mannila, H., & Räihä, K. (1992b). The Design of Relational Databases. Addison-Wesley.
Mannila, H., & Toivonen, H. (1996). On an algorithm for finding all interesting sentences. In R. Trappl (Ed.), Cybernetics and Systems (pp. 973–978).
Mannila, H., & Toivonen, H. (1997). Levelwise Search and Borders of Theories in Knowledge Discovery. (Report C-1997–8). University of Helsinki, Department of Computer Science.
Mitchell, T. (1982) Generalization as search. Artificial Intelligence, 18, 203–226.
Pillaipakkamnatt, K., & Raghavan, V. (1995). Read-twice DNF formulas are properly learnable. Information and Computation, 122(2), 236–267.
Pillaipakkamnatt, K., & Raghavan, V. (1996). On the limits of proper learnability of subclasses of DNF formulas. Machine Learning, 25, 237–263.
Selman, B., & Kautz, H. (1991). Knowledge compilation using horn approximations. In Kathleen Dean, Thomas L., & McKeown (Eds.), Proceedings of the 9th National Conference on Artificial Intelligence (pp. 904–909). MIT Press.
Srikant, R., & Agrawal, R. (1995). Mining generalized association rules. Proceedings of the 21st International Conference on Very Large Databases. Zurich, Switzerland.
Tremblay, J.P., & Manohar, R. (1961). Discrete Mathematical Structures with Applications to Computer Science. McGraw-Hill.
Tsukiyama, S., Ide, M., Ariyoshi, H., & Shirakawa, I. (1977). A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing, 6(3), 505–517.
Valiant, L. (1984). A theory of the learnable. Commun. ACM, 27(11), 1134–1142.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Domingo, C., Mishra, N. & Pitt, L. Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries. Machine Learning 37, 89–110 (1999). https://doi.org/10.1023/A:1007627028578
Issue Date:
DOI: https://doi.org/10.1023/A:1007627028578