Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/111216
Title: The common order-theoretic structure of version spaces and ATMSs
Authors: Gunter, C.A.
Ngair, T.-H. 
Subramanian, D.
Keywords: Admissibility
Anti-chains
ATMS
Concept learning
Label update algorithms
Partial orders
Truth maintenance
Version spaces
Issue Date: Sep-1997
Citation: Gunter, C.A.,Ngair, T.-H.,Subramanian, D. (1997-09). The common order-theoretic structure of version spaces and ATMSs. Artificial Intelligence 95 (2) : 357-407. ScholarBank@NUS Repository.
Abstract: We demonstrate how order-theoretic abstractions can be useful in identifying, formalizing, and exploiting relationships between seemingly dissimilar AI algorithms that perform computations on partially-ordered sets. In particular, we show how the order-theoretic concept of an anti-chain can be used to provide an efficient representation for such sets when they satisfy certain special properties. We use anti-chains to identify and analyze the basic operations and representation optimizations in the version space learning algorithm and the assumption-based truth maintenance system (ATMS). Our analysis allows us to (1) extend the known theory of admissibility of concept spaces for incremental version space merging, and (2) develop new, simpler label-update algorithms for ATMSs with DNF assumption formulas. © 1997 Published by Elsevier Science B.V.
Source Title: Artificial Intelligence
URI: http://scholarbank.nus.edu.sg/handle/10635/111216
ISSN: 00043702
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

73
checked on Jun 23, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.