Sample exclusion dimension
It is proposed that this article be deleted because of the following concern:
If you can address this concern by improving, copyediting, sourcing, renaming, or merging the page, please edit this page and do so. You may remove this message if you improve the article or otherwise object to deletion for any reason. Although not required, you are encouraged to explain why you object to the deletion, either in your edit summary or on the talk page. If this template is removed, do not replace it. This message has remained in place for seven days, so the article may be deleted without further notice. Find sources: "Sample exclusion dimension" – news · newspapers · books · scholar · JSTOR Nominator: Please consider notifying the author/project: {{subst:proposed deletion notify|Sample exclusion dimension|concern=created in 2005, no context, or sources.}} ~~~~Timestamp: 20080327222610 22:26, 27 March 2008 (UTC) Administrators: delete |
 |
Exclusion dimension is a dimension in the exact concept learning with queries.
In algorithmic learning theory, a concept over a domain X is a Boolean function over X. Here we only consider finite domains. A partial approximation S of a concept c is a Boolean function over such that c is an extension to S.
Let C be a class of concepts and c be a concept (not necessarily in C). Then a specifying set for c w.r.t. C, denoted by S is a partial approximation S of c such that C contains at most one extension to S. If we have observed a specifying set for some concept w.r.t. C, then we have enough information to verify a concept in C with at most one more mind change.
The exclusion dimension, denoted by XD(C), of a concept class is the maximum of the size of the minimum specifying set of c' with respect to C, where c' is a concept not in C.
References
- D. Angluin, "Queries Revisited", in Algorithmic Learning Theory: 12th International Conference, ALT 2001, Washington, DC, USA, November 2001, Proceedings, Springer, 2001.
 | This statistics-related article is a stub. You can help Wikipedia by expanding it. |