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

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (December 2021) (Learn how and when to remove this message) This article may need to be rewritten to comply with Wikipedia's quality standards, as the article should cover more aspects of concept classes in a more balanced way, so as to avoid violating WP:UNDUE. You can help. The talk page may contain suggestions. (December 2021) (Learn how and when to remove this message)

В теории вычислительного обучения в математике понятие над доменом 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] [ почему? ]}

This section needs expansion. You can help by adding to it. (December 2021)

Образец — это частичная функция от ^{[ необходимо разъяснение ]} до . ^[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 }$