Please use this identifier to cite or link to this item:
|Title:||The common order-theoretic structure of version spaces and ATMSs||Authors:||Gunter, C.A.
Label update algorithms
|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.
checked on Jun 23, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.