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

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

Версия 17:37, 3 января 2010

Данная статья является непроверенным учебным заданием. Студент: Участник:DmitryKonstantinov Преподаватель: Участник:Константин Воронцов Срок: 8 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

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

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

Пусть имеются - класс множеств и некоторое множество . Говорят, что имеет разнообразие ( to shatter ), если для любого подмножества существует такой, что .

Альтернативная формуровка: имеет разнообразие , если — булеан (множество всех подмножеств) совпадает с множеством .

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

Рассмотрим задачу классификации на два класса. Пусть множество — множество объектов; - множество ответов; класс множеств — класс алгоритмов, множество целевых функций вида ; — подмножество мощности . Класс алгоритмов имеет многообразие (разбивает ), если для любого подмножества множества существует алгоритм из класса , отделяющий объекты из от объектов из .