University of Hertfordshire Research Archive

        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UHRABy Issue DateAuthorsTitlesThis CollectionBy Issue DateAuthorsTitles

        Arkivum Files

        My Downloads
        View Item 
        • UHRA Home
        • University of Hertfordshire
        • Research publications
        • View Item
        • UHRA Home
        • University of Hertfordshire
        • Research publications
        • View Item

        Approximation of Boolean Functions by Local Search

        Author
        Albrecht, A.
        Wong, C.K.
        Attention
        2299/4299
        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.
        Publication date
        2004
        Published in
        Computational Optimization and Applications
        Published version
        https://doi.org/10.1023/B:COAP.0000004980.80957.05
        Other links
        http://hdl.handle.net/2299/4299
        Metadata
        Show full item record
        Keep in touch

        © 2019 University of Hertfordshire

        I want to...

        • Apply for a course
        • Download a Prospectus
        • Find a job at the University
        • Make a complaint
        • Contact the Press Office

        Go to...

        • Accommodation booking
        • Your student record
        • Bayfordbury
        • KASPAR
        • UH Arts

        The small print

        • Terms of use
        • Privacy and cookies
        • Criminal Finances Act 2017
        • Modern Slavery Act 2015
        • Sitemap

        Find/Contact us

        • T: +44 (0)1707 284000
        • E: ask@herts.ac.uk
        • Where to find us
        • Parking
        • hr
        • qaa
        • stonewall
        • AMBA
        • ECU Race Charter
        • disability confident
        • AthenaSwan