Open Access
Open access
Lecture Notes in Computer Science, pages 193-204

A Simulated Annealing-Based Learning Algorithm for Boolean DNF

Publication typeBook Chapter
Publication date1999-01-01
scimago Q2
SJR0.352
CiteScore2.4
Impact factor
ISSN03029743, 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 

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Share
Cite this
GOST | RIS | BibTex
Found error?