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

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

Версия от 17:34, 3 января 2010; DmitryKonstantinov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Данная статья является непроверенным учебным заданием.
Студент: Участник: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|.

См. также

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

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