Концептуальный класс

В теории вычислительного обучения в математике понятием в области X является полная булева над X. функция Класс концептов — это класс концептов. Концептуальные классы являются предметом теории вычислительного обучения .

Терминология концептуальных классов часто появляется в теории моделей, связанной с вероятно приблизительно правильным (PAC) обучением. В этом случае, если взять набор Y как набор меток (выход классификатора), а X — набор примеров, карта $c:X\to Y$, т.е. от примеров к меткам классификатора (где $Y=\{0,1\}$ и где c — подмножество X ), тогда c называют концепцией . Концептуальный класс $C$ тогда представляет собой совокупность таких понятий.

Для данного класса понятий C подкласс D достижим , если существует выборка s такая, что D содержит именно те понятия из C, которые являются расширениями s . Не каждый подкласс доступен.

Фон

Образец ​ $s$ является частичной функцией от $X$ к $\{0,1\}$. Идентификация понятия с помощью его характерного отображения функций $X$ к $\{0,1\}$, это частный случай выборки.

Две выборки согласованы , если они совпадают в пересечении своих областей. Образец $s'$ расширяет другой образец $s$ если они согласованы и область $s$ содержится в области $s'$.

Примеры

Предположим, что $C=S^{+}(X)$. Затем:

• подкласс $\{\{x\}\}$ достижим с помощью образца $s=\{(x,1)\}$;
• подкласс $S^{+}(Y)$ для $Y\subseteq X$ достижимы с помощью выборки, которая отображает элементы $X-Y$ до нуля?
• подкласс $S(X)$, состоящий из одноэлементных наборов, недостижим .

Приложения

Позволять $C$ быть неким концептуальным классом. Для любой концепции $c\in C$мы называем это понятие $1/d$-хорошо для положительного целого числа $d$ если для всех $x\in X$, по меньшей мере $1/d$ концепций в $C$ согласен с $c$ по классификации $x$. Размер отпечатка пальца $FD(C)$ всего концептуального класса $C$ наименьшее положительное целое число $d$ такой, что каждый достижимый подкласс $C'\subseteq C$ содержит понятие, которое $1/d$- молодец. Это количество можно использовать для ограничения минимального количества запросов эквивалентности. необходимо изучить класс понятий согласно следующему неравенству : ${\textstyle FD(C)-1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil }$.