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

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]

References

edit
  1. ^ Chase, H., & Freitag, J. (2018). Model Theory and Machine Learning. arXiv preprint arXiv:1801.06566.
  2. ^ a b c d e f g h i j k l Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004.