Abstract
In the past decade, there has been a lot of interest in phase transitions within artificial intelligence, and more recently, in machine learning and inductive logic programming. We investigate phase transitions in learning k-term DNF boolean formulae, a practically relevant class of concepts. We do not only show that there exist phase transitions, but also characterize and locate these phase transitions using the parameters k, the number of positive and negative examples, and the number of boolean variables. Subsequently, we investigate stochastic local search (SLS) for k-term DNF learning. We compare several variants that first reduce k-term DNF to SAT and then apply well-known SLS algorithms, such as GSAT and WalkSAT. Our experiments indicate that WalkSAT is able to solve the largest fraction of hard problem instances.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bain, M. E. (1994) Learning logical exceptions in chess. PhD thesis. Department of Statistics and Modelling Science, University of Strathclyde, Scotland
Barber, M. N. (1983) Finite-size scaling. Phase Transitions and critical phenomena, Vol. 8, 145–266, Academic Press
Cheeseman, P., Kanefsky, B., and Taylor, W. M. (1991). Where the really hard problems are. Proceedings of the 12th IJCAI, 331–337
Domingos, P. (1999) The role of Occam’s razor in knowledge discovery. Data Mining and Knowledge Discovery, Vol. 3, Nr. 4, 409–425
Gent, I. P., and Walsh, T. (1995). The number partition phase transition. Research report 95-185, Department of Computer Science, University of Strathclyde
Gent, I. P., and Walsh, T. (1996). The TSP phase transition, Artificial Intelligence, 88, 1–2, 349–358
Giordana, A., Saitta, L., Sebag, M., and Botta, M. (2000) Analyzing Relational Learning in the Phase Transition Framework. Proc. 17th International Conf. on Machine Learning, 311–318
Giordana, A., Saitta, L. (2000) Phase Transitions in Relational Learning. Machine Learning, 41(2), 217–25
Giordana, A., Saitta, L., and Zini, F. (1994) Learning disjunctive concepts by means of genetic algorithms. Proc. 11th International Conf. on Machine Learning, 96–104
Giordana, A., Botta, M., and Saitta, L. (1999) An experimental study of phase transitions in matching. IJCAI 1999, 1198–1203
Hoos, H. H. (1998) Stochastic local search—methods, models, applications, PhD Thesis, Technische Universität Darmstadt
Kamath, A. P., Karmarkar, N. K., Ramakrishnan, K. G., and Resende, M. G. C. (1991). A continous approach to inductive inference. Mathematical Programming, 57, 1992, 215–238.
Kearns, M. J., and Vazirani, U. V. (1994). An introduction to computational learning theory. Cambridge, MA: MIT Press
Kirkpatrick, S., and Selman, B. (1994). Critical behavior in the satisfiability of random boolean expressions. Science, 264, 1297–1301
Kovacic, M. (1994) MILP-a stochastic approach to Inductive Logic Programming. Proc. 4th International Workshop on Inductive Logic Programming, 123–138
McAllester, D., Selman, B., and Kautz, H. (1997) Evidence for invariants in local search. Proceedings of the 14th National Conference on Artificial Intelligence, 321-326
Mitchell, D., Selman, B., and Levesque, H. (1992) Hard and easy distributions of SAT problems. Proceedings of the 10th National Conference on Artificial Intelligence, AAAI Press/ MIT Press, San Jose, CA, 459–465
Mooney, R. J. (1995) Encouraging experimental results on learning CNF. Machine Learning, Vol. 19, 1, 79–92
Nalimov, E. V., Haworth, G.McC., and Heinz, E. A. (2000) Space-efficient indexing of chess endgame tables. ICGA Journal, Vol. 23, Nr. 3, 148–162
Plotkin, G. D. (1970) A note on inductive generalization. Machine Intelligence 5, Edinburgh University Press, 153–163.
Quinlan, J. R., and Cameron-Jones, R. M. (1995) Induction of logic programs: FOIL and related systems. New Generation Computing, Vol. 13, 287–312
Selman, B., and Kautz, H. A. (1992) A new method for solving hard satisfiability problems. Proceedings of the 10th National Conference on Artificial Intelligence, San Jose, CA, 440–446
Selman, B., Kautz, H. A., and Cohen, B. (1993) Local search strategies for satisfiability testing. Proceedings of the 10th National Conference on Artificial Intelligence, San Jose, CA
Selman, B., and Kautz, H. A. (1993) Domain-independent extensions to GSAT: solving large structured satisfiability problems. Proceedings of IJCAI 93, 290–295
Selman, B., Kautz, H. A. and Cohen, B. (1994) Noise strategies for improving local search. Proceedings of the 14th National Conference on Artificial Intelligence, 337–343
Webb, G. J. (1996) Further evidence against the utility of Occam’s razor. Journal of Artificial Intelligence Research, Vol. 4, 397–417
Weisstein, E. W. (2002) Stirling number of the second kind, http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rückert, U., Kramer, S., De Raedt, L. (2002). Phase Transitions and Stochastic Local Search in k-Term DNF Learning. In: Elomaa, T., Mannila, H., Toivonen, H. (eds) Machine Learning: ECML 2002. ECML 2002. Lecture Notes in Computer Science(), vol 2430. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36755-1_34
Download citation
DOI: https://doi.org/10.1007/3-540-36755-1_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44036-9
Online ISBN: 978-3-540-36755-0
eBook Packages: Springer Book Archive