dc.contributor.author | Albrecht, A. | |
dc.contributor.author | Wong, C.K. | |
dc.date.accessioned | 2010-02-18T14:19:52Z | |
dc.date.available | 2010-02-18T14:19:52Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | Albrecht , A & Wong , C K 2004 , ' Approximation of Boolean Functions by Local Search ' , Computational Optimization and Applications , vol. 27 , no. 1 , pp. 53-82 . https://doi.org/10.1023/B:COAP.0000004980.80957.05 | |
dc.identifier.issn | 0926-6003 | |
dc.identifier.other | dspace: 2299/4299 | |
dc.identifier.uri | http://hdl.handle.net/2299/4299 | |
dc.description | “The original publication is available at www.springerlink.com”. Copyright Springer. [Full text of this article is not available in the UHRA] | |
dc.description.abstract | Usually, local search methods are considered to be slow. In our paper, we present a simulated annealing-based local search algorithm for the approximation of Boolean functions with a proven time complexity that behaves relatively fast on randomly generated functions. The functions are represented by disjunctive normal forms (DNFs). Given a set of m uniformly distributed positive and negative examples of length n generated by a target function F(x 1,...,x n), where the DNF consists of conjunctions with at most literals only, the algorithm computes with high probability a hypothesis H of length m · such that the error is zero on all examples. Our algorithm can be implemented easily and we obtained a relatively high percentage of correct classifications on test examples that were not presented in the learning phase. For example, for randomly generated F with n = 64 variables and a training set of m = 16384 examples, the error on the same number of test examples was about 19% on positive and 29% on negative examples, respectively. The proven complexity bound provides the basis for further studies on the average case complexity. | en |
dc.language.iso | eng | |
dc.relation.ispartof | Computational Optimization and Applications | |
dc.title | Approximation of Boolean Functions by Local Search | en |
dc.contributor.institution | School of Computer Science | |
dc.contributor.institution | Science & Technology Research Institute | |
dc.description.status | Peer reviewed | |
rioxxterms.versionofrecord | 10.1023/B:COAP.0000004980.80957.05 | |
rioxxterms.type | Journal Article/Review | |
herts.preservation.rarelyaccessed | true | |