Английская Википедия:Concept class

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description Шаблон:Multiple issuesIn 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. 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 <math>c: X\to Y</math>, i.e. from examples to classifier labels (where <math>Y = \{0, 1\}</math> and where c is a subset of X), c is then said to be a concept. A concept class <math>C</math> 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. Not every subclass is reachable.Шаблон:Why

Background

Шаблон:Expand section A sample <math>s</math> is a partial function from <math>X</math>Шаблон:What to <math>\{0, 1\}</math>. Identifying a concept with its characteristic function mapping <math>X</math> to <math>\{0, 1\}</math>, it is a special case of a sample.

Two samples are consistent if they agree on the intersection of their domains. A sample <math>s'</math> extends another sample <math>s</math> if the two are consistent and the domain of <math>s</math> is contained in the domain of <math>s'</math>.

Examples

Suppose that <math>C = S^+(X)</math>. Then:

• the subclass <math>\{\{x\}\}</math> is reachable with the sample <math>s = \{(x, 1)\}</math>;Шаблон:Why
• the subclass <math>S^+(Y)</math> for <math>Y\subseteq X</math> are reachable with a sample that maps the elements of <math>X - Y</math> to zero;Шаблон:Why
• the subclass <math>S(X)</math>, which consists of the singleton sets, is not reachable.Шаблон:Why

Applications

Let <math>C</math> be some concept class. For any concept <math>c\in C</math>, we call this concept <math>1/d</math>-good for a positive integer <math>d</math> if, for all <math>x\in X</math>, at least <math>1/d</math> of the concepts in <math>C</math> agree with <math>c</math> on the classification of <math>x</math>. The fingerprint dimension <math>FD(C)</math> of the entire concept class <math>C</math> is the least positive integer <math>d</math> such that every reachable subclass <math>C'\subseteq C</math> contains a concept that is <math>1/d</math>-good for it. This quantity can be used to bound the minimum number of equivalence queriesШаблон:What needed to learn a class of concepts according to the following inequality:<math display="inline">FD(C) - 1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil</math>.