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

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

Версия от 16:42, 3 января 2010; DmitryKonstantinov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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