Concept class
From Wikipedia the free encyclopedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
In computational learning theory in mathematics, a concept over a domain X is a total Boolean function over X. A concept class is a class of concepts. Concept classes are a subject of computational learning theory.
Concept class terminology frequently appears in model theory associated with probably approximately correct (PAC) learning.[1] In this setting, if one takes a set Y as a set of (classifier output) labels, and X is a set of examples, the map , i.e. from examples to classifier labels (where and where c is a subset of X), c is then said to be a concept. A concept class is then a collection of such concepts.
Given a class of concepts C, a subclass D is reachable if there exists a sample s such that D contains exactly those concepts in C that are extensions to s.[2] Not every subclass is reachable.[2][why?]
Background[edit]
This section needs expansion. You can help by adding to it. (December 2021) |
A sample is a partial function from [clarification needed] to .[2] Identifying a concept with its characteristic function mapping to , it is a special case of a sample.[2]
Two samples are consistent if they agree on the intersection of their domains.[2] A sample extends another sample if the two are consistent and the domain of is contained in the domain of .[2]
Examples[edit]
Suppose that . Then:
- the subclass is reachable with the sample ;[2][why?]
- the subclass for are reachable with a sample that maps the elements of to zero;[2][why?]
- the subclass , which consists of the singleton sets, is not reachable.[2][why?]
Applications[edit]
Let be some concept class. For any concept , we call this concept -good for a positive integer if, for all , at least of the concepts in agree with on the classification of .[2] The fingerprint dimension of the entire concept class is the least positive integer such that every reachable subclass contains a concept that is -good for it.[2] This quantity can be used to bound the minimum number of equivalence queries[clarification needed] needed to learn a class of concepts according to the following inequality:.[2]