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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (оформление)
м (литература)
Строка 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.
[[Категория:Теория вычислительного обучения]]
[[Категория:Теория вычислительного обучения]]

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

Данная статья является непроверенным учебным заданием.
Студент: Участник: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.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BD%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%B8%D0%B5»
Личные инструменты