On Learning Ring-Sum-Expansions

Paul Fischer, H. -U. Simon

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    The problem of learning ring-sum-expansions from examples is studied. Ring-sum-expansions (RSE) are representations of Boolean functions over the base {#123;small infinum, (+), 1}#125;, which reflect arithmetic operations in GF(2). k-RSE is the class of ring-sum-expansions containing only monomials of length at most k:. term-RSE is the class of ring-sum-expansions having at most I: monomials. It is shown that k-RSE, k>or=1, is learnable while k-term-RSE, k>2, is not learnable if RPnot=NP. Without using a complexity-theoretical hypothesis, it is proven that k-RSE, k>or=1, and k-term-RSE, k>or=2 cannot be learned from positive (negative) examples alone. However, if the restriction that the hypothesis which is output by the learning algorithm is also a k-RSE is suspended, then k-RSE is learnable from positive (negative) examples only. Moreover, it is proved that 2-term-RSE is learnable by a conjunction of a 2-CNF and a 1-DNF. Finally the paper presents learning (on-line prediction) algorithms for k-RSE that are optimal with respect to the sample size (worst case mistake bound)
    Original languageEnglish
    JournalSIAM Journal on Computing
    Volume21
    Issue number1
    Pages (from-to)181-192
    ISSN0097-5397
    DOIs
    Publication statusPublished - 1992

    Fingerprint

    Dive into the research topics of 'On Learning Ring-Sum-Expansions'. Together they form a unique fingerprint.

    Cite this