Title: Phase transitions and stochastic local search in k-term DNF learning
Authors: Rueckert, Ulrich ×
Kramer, Stefan
De Raedt, Luc #
Issue Date: 2002
Publisher: Springer-verlag berlin
Series Title: Machine learning: ecml 2002 vol:2430 pages:405-417
Conference: European Conference on Machine Learning edition:13 location:Helsinki, Finland date:19-23 August 2002
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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
02-ecml.pdf Published 389KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science