Sample exclusion dimension

From Wikipedia, the free encyclopedia

This does not cite its references or sources.
Please help improve this article by introducing appropriate citations. (help, get involved!) This article has been tagged since June 2006.

Exclusion dimension is a dimension in the exact concept learning with queries.

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 Y\subseteq X 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' w.r.t. C, where c' is a concept not in C.


 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../s/a/m/Sample_exclusion_dimension.html"