Разнообразие

Материал из MachineLearning.

Перейти к: навигация, поиск
Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Концепция разнообразия играет важную роль в теории Вапника-Червоненкиса. Разнообразие класса связано с такими ключевыми понятиями, как коэффициент разнообразия, функция роста, размерность Вапника-Червоненкиса.

Разнообразие класса

Пусть имеются C - класс множеств и некоторое множество X. Говорят, что C имеет разнообразие X (C to shatter X), если для любого подмножества T \subset X существует U \in C такой, что U \cap X = T.

Альтернативная формуровка: C имеет разнообразие X, если 2^X — булеан (множество всех подмножеств) совпадает с множеством \{U \cap X | U \in C \}.

Пример: класс C — класс полуплоскостей плоскости, X — множество из произвольных 4 точек на плоскости. C не имеет разнообразия X, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой.

Рассмотрим задачу классификации на два класса. Пусть множество X — множество объектов; Y = \{0,1\} - множество ответов; класс множеств C — класс алгоритмов, множество целевых функций вида X \rightarrow Y; X^L — подмножество X мощности L. Класс алгоритмов C имеет многообразие X^L (разбивает X^L), если для любого подмножества T множества X^L существует алгоритм из класса C, отделяющий объекты из T от объектов из X^L\setminus T.

Литература

  1. 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.
Личные инструменты