Введение
Теория вычислительного обучения
В математической теории вычислительного обучения, понятие над областью X представляет собой полную булеву функцию над X. Класс понятий — это класс понятий. Классы понятий являются предметом изучения теории вычислительного обучения. Терминология, связанная с классами понятий, часто встречается в теории моделей, в контексте вероятно приближенно корректного (PAC) обучения. В данном контексте, если множество Y рассматривается как множество (выходов классификатора) меток, а X — как множество примеров, то отображение, то есть соответствие между примерами и метками классификатора (где и где c является подмножеством X), называется понятием. Класс понятий — это совокупность таких понятий. Для заданного класса понятий C, подкласс D является достижимым, если существует выборка s, такая что D содержит ровно те понятия из C, которые являются расширениями для s.
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. 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.
Предыстория
Образец — это частичная функция из области D в область R. Отождествляя понятие с его характеристической функцией, отображающей D в R, можно сказать, что это частный случай образца. Два образца считаются согласованными, если они совпадают на пересечении областей их определения. Образец S расширяет другой образец T, если они оба согласованны и область определения S содержится в области определения T.
Приложения
Пусть задан некоторый класс концепций. Для любой концепции , мы называем эту концепцию хорошей для положительного целого числа , если для всех , по крайней мере, концепций из совпадают с концепцией в классификации . Размерность отпечатка (fingerprint dimension) всего класса концепций – это наименьшее положительное целое число , такое что каждый достижимый подкласс содержит концепцию, которая является хорошей для него. Эта величина может быть использована для оценки минимального количества запросов эквивалентности, необходимых для обучения класса концепций, согласно следующему неравенству: