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

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

(Различия между версиями)
Перейти к: навигация, поиск

Версия 16:42, 3 января 2010

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

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

Пусть имеются 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.

Личные инструменты