Abstract
Instance retraction is a difficult problem for concept learning by version spaces. In this paper, two new version-space representations are introduced: instance-based maximal boundary sets and instancebased minimal boundary sets. They are correct representations for the class of admissible concept languages and are efficiently computable. Compared to other representations, they are the most efficient practical version-space representations for instance retraction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Haussler, D.: Quantifying Inductive Bias: AI Learning Algorithms and Valiants Learning Framework. Artificial Intelligence 36 (1988) 177–221
Hirsh, H.: Polynomial-Time Learning with Version Spaces. In: Proceedings of the Tenth National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA (1992) 117–122
Hirsh, H., Mishra, N., Pitt, L.: Version Spaces without Boundary Sets. In: Proceedings of the Fourteenth National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA (1997) 491–496
Idemstam-Almquist, P.: Demand Networks: An Alternative Representation of Version Spaces. Master’s Thesis, Department of Computer Science and Systems Sciences, Stockholm University, Stockholm, Sweden (1990)
Mitchell, T.: Machine Learning. McGraw-Hill, New York, NY (1997)
Sablon, G., DeRaedt, L., Bruynooghe, L.: Iterative Versionspaces. Artificial Intelligence 69 (1994) 393–410
Smirnov, E.N.: Conjunctive and Disjunctive Version Spaces with Instance-Based Boundary Sets. Ph.D. Thesis, Department of Computer Science, Universiteit Maastricht, Maastricht, The Netherlands (2001)
Smirnov, E.N., Braspenning, P.J.: Version Space Learning with Instance-Based Boundary Sets. In: Proceedings of The Thirteenth European Conference on Artificial Intelligence. Jonh Willey and Sons, Chichester, UK (1998) 460–464
Smirnov, E.N., Sprinkhuizen-Kuyper, I.G., van den Herik, H.J.: Further Developments in Efficient Instance Retraction. Technical Report CS 02-02, Department of Computer Science, Universiteit Maastricht, Maastricht, The Netherlands (2002)
Smith, B.D., Rosenbloom, P.S.: Incremental Non-Backtracking Focusing: A Polynomially Bounded Algorithm for Version Spaces. In: Proceedings of the Eight National Conference on Artificial Intelligence, MIT Press, MA (1990) 848–853
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Smirnov, E.N., Sprinkhuizen-Kuyper, I.G., van den Herik, H.J. (2002). Efficient Instance Retraction. In: Scott, D. (eds) Artificial Intelligence: Methodology, Systems, and Applications. AIMSA 2002. Lecture Notes in Computer Science(), vol 2443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46148-5_3
Download citation
DOI: https://doi.org/10.1007/3-540-46148-5_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44127-4
Online ISBN: 978-3-540-46148-7
eBook Packages: Springer Book Archive