Функция роста

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

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

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

Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Функцией роста множества алгоритмов A называется максимальное значение коэффициента разнообразия \Delta^A(X^L) по всем возможным выборкам длины L:

\Delta^A(L) = max \Delta^A(X^L)

Функция роста не зависит ни от выборки, ни от метода обучения, и является мерой сложности множества алгоритмов A.

В теории Вапника-Червоненкиса доказывается, что функция роста \Delta^A(L) либо равна 2^L, либо растёт полиномиально по L, причём промежуточных вариантов не существует.

Пусть множество A конечно. Число алгоритмов, попарно неразличимых на выборке X^L, не превышает числа всех алгоритмов, поэтому для функции роста справедлива оценка \Delta^A(L) \leq |A|.

См. также

Размерность Вапника-Червоненкиса

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