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

Теория вычислительного обучения

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

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

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

Фон

Образец — это частичная функция от ^{[ необходимо разъяснение ]} до . ^[2] Идентифицируя концепцию с ее характерной функцией, отображаемой на , это частный случай образца. ^[2] ${\displaystyle s}$ ${\displaystyle X}$ ${\displaystyle \{0,1\}}$ ${\displaystyle X}$ ${\displaystyle \{0,1\}}$

Два образца согласованы , если они согласны в пересечении своих доменов. ^[2] Образец расширяет другой образец , если они согласованы и домен содержится в домене . ^[2] ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s'}$

Примеры

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

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

Приложения

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

Ссылки

1. Чейз, Х. и Фрейтаг, Дж. (2018). Теория моделей и машинное обучение. Препринт arXiv arXiv:1801.06566.
2. Angluin, D. (2004). "Queries revisited" (PDF) . Теоретическая информатика . 313 (2): 188–191. doi :10.1016/j.tcs.2003.11.004.