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

Материал из 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|$ .