Open Access
Lecture Notes in Computer Science, pages 193-204
A Simulated Annealing-Based Learning Algorithm for Boolean DNF
Andreas Albrecht
1
,
Kathleen Steinhöfel
2
2
GMD, National Research Center for IT, Berlin, Germany
|
Publication type: Book Chapter
Publication date: 1999-01-01
Journal:
Lecture Notes in Computer Science
scimago Q2
SJR: 0.352
CiteScore: 2.4
Impact factor: —
ISSN: 03029743, 16113349, 18612075, 18612083
Abstract
We describe a stochastic algorithm learning Boolean functions from positive and negative examples. The Boolean functions are represented by disjunctive normal form formulas. Given a target DNF F depending on n variables and a set of uniformly distributed positive and negative examples, our algorithm computes a hypothesis H that rejects a given fraction of negative examples and has an ɛ-bounded error on positive examples. The stochastic algorithm utilises logarithmic cooling schedules for inhomogeneous Markov chains. The paper focuses on experimental results and comparisons with a previous approach where all negative examples have to be rejected [4]. The computational experiments provide evidence that a relatively high percentage of correct classifications on additionally presented examples can be achieved, even when misclassifications are allowed on negative examples. The detailed convergence analysis will be presented in a forthcoming paper [3].
Found
Nothing found, try to update filter.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.