Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries (Q5941371): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Created claim: Wikidata QID (P12): Q126778400, #quickstatements; #temporary_batch_1722035971323
 
Property / Wikidata QID
 
Property / Wikidata QID: Q126778400 / rank
 
Normal rank

Latest revision as of 00:32, 27 July 2024

scientific article; zbMATH DE number 1635559
Language Label Description Also known as
English
Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
scientific article; zbMATH DE number 1635559

    Statements

    Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    20 August 2001
    0 references
    A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time \(O(n^{2}\log n)\), where \(n\) is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time \(O(n^{4}\log n)\) [cf. \textit{D. Angluin}, J. Comput. Syst. Sci. 21, No. 1, 46-62 (1980; Zbl 0454.68108)]. Second, we give a parallel version of this algorithm that requires time \(O(\log n)\) and \(O(n^{3}/\log n)\) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is \(O(\ell^{2}\log\ell)\) provided the sample strings are drawn from the target language according to a probability distribution with expected string length \(\ell\). The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.
    0 references
    inductive learning
    0 references
    one-variable pattern languages
    0 references
    average-case analysis
    0 references
    parallelization
    0 references

    Identifiers