• Information Technology
  • Human Resources
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
My UCalgary
Webmail
D2L
ARCHIBUS
IRISS
  • Faculty of Arts
  • Cumming School of Medicine
  • Faculty of Environmental Design
  • Faculty of Graduate Studies
  • Haskayne School of Business
  • Faculty of Kinesiology
  • Faculty of Law
  • Faculty of Nursing
  • Faculty of Nursing (Qatar)
  • Schulich School of Engineering
  • Faculty of Science
  • Faculty of Social Work
  • Faculty of Veterinary Medicine
  • Werklund School of Education
  • Information TechnologiesIT
  • Human ResourcesHR
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
  • Libraries and Cultural Resources
View Item 
  •   PRISM Home
  • Science
  • Science Research & Publications
  • View Item
  •   PRISM Home
  • Science
  • Science Research & Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A SYMMETRIC VERSION SPACE ALGORITHM FOR LEARNING DISJUNCTIVE STRING CONCEPTS

Thumbnail
Download
1992-468-6.pdf.gz (194.1Kb)
Download Record
Download to EndNote/RefMan (RIS)
Download to BibTex
Author
Baltes, Jacky
Accessioned
2008-05-20T23:29:57Z
Available
2008-05-20T23:29:57Z
Computerscience
1999-05-27
Issued
1992-03-01
Subject
Computer Science
Type
unknown
Metadata
Show full item record

Abstract
The paper describes an algorithm to learn disjunctive string patterns from examples. An implementation of the algorithm learns concepts such as all C source files (*.c or *.h) in the UNIX domain. The algorithm is designed for an interactive learning model in which the number of questions to the user are minimized. Furthermore, only simple questions to the user are admissible. The representation language is restricted to a subset of regular expressions in order to reduce the complexity. The patterns in the concept grammar are extensions of Nix's gap patterns and Mo's annotated gap patterns. To learn sequences of patterns, the strings are broken up into units. The algorithm assumes that the first example is a good representative of the concept, that is, it contains all optional units. Even for limited disjunctions, the G-set of Mitchell's Candidate Elimination algorithm is infinite for domains that contain an infinite number of elements. A symmetric version space (SVS) algorithm using cover sets of the positive and negative examples computes only the most specific description that matches a set of examples and can therefore be used to learn in version spaces that make it impossible or infeasible to compute the most general descriptions. Two extra cover sets are maintained to avoid asking the user about all possible examples, a problem that arises when the number of terms in the concept is less than the maximum number of terms in a disjunction. The correctness of the SVS algorithm in version spaces with minimal generalization hierarchies, so called k-disjunctive version spaces, is shown. Furthermore, it is argued that an extended version of the SVS algorithm solves the swapping and splitting problem. The last result of the paper establishes that, though the size of the version space grows exponentially, the sample size complexity increases only linearly with the maximum length of units.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca
Corporate
University of Calgary
Faculty
Science
Doi
http://dx.doi.org/10.11575/PRISM/31285
Uri
http://hdl.handle.net/1880/46538
Collections
  • Science Research & Publications

Browse

All of PRISMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Download Results

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors

  • Email
  • SMS
  • 403.220.8895
  • Live Chat

Energize: The Campaign for Eyes High

Privacy Policy
Website feedback

University of Calgary
2500 University Drive NW
Calgary, AB T2N 1N4
CANADA

Copyright © 2017