Разнообразие
Материал из MachineLearning.
м (оформление) |
|||
| (1 промежуточная версия не показана) | |||
| Строка 5: | Строка 5: | ||
Пусть имеются <tex>C</tex> - класс множеств и некоторое множество <tex>X</tex>. Говорят, что <tex>C</tex> имеет разнообразие <tex>X</tex> (<tex>C</tex> to shatter <tex>X</tex>), если для любого подмножества <tex>T \subset X</tex> существует <tex>U \in C</tex> такой, что <tex>U \cap X = T</tex>. | Пусть имеются <tex>C</tex> - класс множеств и некоторое множество <tex>X</tex>. Говорят, что <tex>C</tex> имеет разнообразие <tex>X</tex> (<tex>C</tex> to shatter <tex>X</tex>), если для любого подмножества <tex>T \subset X</tex> существует <tex>U \in C</tex> такой, что <tex>U \cap X = T</tex>. | ||
| - | Альтернативная | + | Альтернативная формулировка: <tex>C</tex> имеет разнообразие <tex>X</tex>, если <tex>2^X</tex> — булеан (множество всех подмножеств) совпадает с множеством <tex>\{U \cap X | U \in C \}</tex>. |
Пример: класс <tex>C</tex> — класс полуплоскостей плоскости, <tex>X</tex> — множество из произвольных 4 точек на плоскости. <tex>C</tex> не имеет разнообразия <tex>X</tex>, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой. | Пример: класс <tex>C</tex> — класс полуплоскостей плоскости, <tex>X</tex> — множество из произвольных 4 точек на плоскости. <tex>C</tex> не имеет разнообразия <tex>X</tex>, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой. | ||
| Строка 11: | Строка 11: | ||
Рассмотрим задачу классификации на два класса. Пусть множество <tex>X</tex> — множество объектов; <tex>Y = \{0,1\}</tex> - множество ответов; класс множеств <tex>C</tex> — класс алгоритмов, множество целевых функций вида <tex>X \rightarrow Y</tex>; <tex>X^L</tex> — подмножество <tex>X</tex> мощности <tex>L</tex>. Класс алгоритмов <tex>C</tex> имеет многообразие <tex>X^L</tex> (разбивает <tex>X^L</tex>), если для любого подмножества <tex>T</tex> множества <tex>X^L</tex> существует алгоритм из класса <tex>C</tex>, отделяющий объекты из <tex>T</tex> от объектов из <tex>X^L\setminus T</tex>. | Рассмотрим задачу классификации на два класса. Пусть множество <tex>X</tex> — множество объектов; <tex>Y = \{0,1\}</tex> - множество ответов; класс множеств <tex>C</tex> — класс алгоритмов, множество целевых функций вида <tex>X \rightarrow Y</tex>; <tex>X^L</tex> — подмножество <tex>X</tex> мощности <tex>L</tex>. Класс алгоритмов <tex>C</tex> имеет многообразие <tex>X^L</tex> (разбивает <tex>X^L</tex>), если для любого подмножества <tex>T</tex> множества <tex>X^L</tex> существует алгоритм из класса <tex>C</tex>, отделяющий объекты из <tex>T</tex> от объектов из <tex>X^L\setminus T</tex>. | ||
| + | == Литература == | ||
| + | # Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):929-965, October 1989. | ||
[[Категория:Теория вычислительного обучения]] | [[Категория:Теория вычислительного обучения]] | ||
Текущая версия
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Концепция разнообразия играет важную роль в теории Вапника-Червоненкиса. Разнообразие класса связано с такими ключевыми понятиями, как коэффициент разнообразия, функция роста, размерность Вапника-Червоненкиса.
Разнообразие класса
Пусть имеются - класс множеств и некоторое множество
. Говорят, что
имеет разнообразие
(
to shatter
), если для любого подмножества
существует
такой, что
.
Альтернативная формулировка: имеет разнообразие
, если
— булеан (множество всех подмножеств) совпадает с множеством
.
Пример: класс — класс полуплоскостей плоскости,
— множество из произвольных 4 точек на плоскости.
не имеет разнообразия
, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой.
Рассмотрим задачу классификации на два класса. Пусть множество — множество объектов;
- множество ответов; класс множеств
— класс алгоритмов, множество целевых функций вида
;
— подмножество
мощности
. Класс алгоритмов
имеет многообразие
(разбивает
), если для любого подмножества
множества
существует алгоритм из класса
, отделяющий объекты из
от объектов из
.
Литература
- Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):929-965, October 1989.
