Разнообразие
Материал из MachineLearning.
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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.
