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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (оформление)
Текущая версия (00:11, 12 декабря 2015) (править) (отменить)
 
(1 промежуточная версия не показана)
Строка 5: Строка 5:
Пусть имеются <tex>C</tex> - класс множеств и некоторое множество <tex>X</tex>. Говорят, что <tex>C</tex> имеет разнообразие <tex>X</tex> (<tex>C</tex> to shatter <tex>X</tex>), если для любого подмножества <tex>T \subset X</tex> существует <tex>U \in C</tex> такой, что <tex>U \cap X = T</tex>.
Пусть имеются <tex>C</tex> - класс множеств и некоторое множество <tex>X</tex>. Говорят, что <tex>C</tex> имеет разнообразие <tex>X</tex> (<tex>C</tex> to shatter <tex>X</tex>), если для любого подмножества <tex>T \subset X</tex> существует <tex>U \in C</tex> такой, что <tex>U \cap X = T</tex>.
-
Альтернативная формуровка: <tex>C</tex> имеет разнообразие <tex>X</tex>, если <tex>2^X</tex> — булеан (множество всех подмножеств) совпадает с множеством <tex>\{U \cap X | U \in C \}</tex>.
+
Альтернативная формулировка: <tex>C</tex> имеет разнообразие <tex>X</tex>, если <tex>2^X</tex> — булеан (множество всех подмножеств) совпадает с множеством <tex>\{U \cap X | U \in C \}</tex>.
Пример: класс <tex>C</tex> — класс полуплоскостей плоскости, <tex>X</tex> — множество из произвольных 4 точек на плоскости. <tex>C</tex> не имеет разнообразия <tex>X</tex>, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой.
Пример: класс <tex>C</tex> — класс полуплоскостей плоскости, <tex>X</tex> — множество из произвольных 4 точек на плоскости. <tex>C</tex> не имеет разнообразия <tex>X</tex>, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой.
Строка 11: Строка 11:
Рассмотрим задачу классификации на два класса. Пусть множество <tex>X</tex> — множество объектов; <tex>Y = \{0,1\}</tex> - множество ответов; класс множеств <tex>C</tex> — класс алгоритмов, множество целевых функций вида <tex>X \rightarrow Y</tex>; <tex>X^L</tex> — подмножество <tex>X</tex> мощности <tex>L</tex>. Класс алгоритмов <tex>C</tex> имеет многообразие <tex>X^L</tex> (разбивает <tex>X^L</tex>), если для любого подмножества <tex>T</tex> множества <tex>X^L</tex> существует алгоритм из класса <tex>C</tex>, отделяющий объекты из <tex>T</tex> от объектов из <tex>X^L\setminus T</tex>.
Рассмотрим задачу классификации на два класса. Пусть множество <tex>X</tex> — множество объектов; <tex>Y = \{0,1\}</tex> - множество ответов; класс множеств <tex>C</tex> — класс алгоритмов, множество целевых функций вида <tex>X \rightarrow Y</tex>; <tex>X^L</tex> — подмножество <tex>X</tex> мощности <tex>L</tex>. Класс алгоритмов <tex>C</tex> имеет многообразие <tex>X^L</tex> (разбивает <tex>X^L</tex>), если для любого подмножества <tex>T</tex> множества <tex>X^L</tex> существует алгоритм из класса <tex>C</tex>, отделяющий объекты из <tex>T</tex> от объектов из <tex>X^L\setminus T</tex>.
 +
== Литература ==
 +
# 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.
[[Категория:Теория вычислительного обучения]]
[[Категория:Теория вычислительного обучения]]

Текущая версия

Данная статья является непроверенным учебным заданием.
Студент: Участник: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.
Личные инструменты