Участник:Алексей Куренной/Песочница
Материал из MachineLearning.
Определение
Пусть и
- множества произвольной природы. Будем называть
множеством объектов, а
- множеством ответов. За
обозначим L-элементную выборку из
, т.е. подмножество
, мощность которого равна
.
Определение. Функцией роста семейства алгоритмов называется функция:
, где
- коэффициент разнообразия семейства
на выборке
.
Оценки функции роста
Поскольку для любого семейства алгоритмов и любой выборки длины L,
. Более детально поведение функции роста описывается следующей теоремой:
Теорема. Для функции роста произвольного семейства алгоритмов есть ровно две возможности:
Эту теорему можно доказать, опираясь на лемму Вапника - Червоненкиса:
Лемма. выполнено:
- для любой выборки
.
Доказательство леммы. Сначала докажем лемму для и
. В случае
выполнение левой части импликации из условия леммы означает, что на произвольном элементе выборки
все алгоритмы семейства ведут себя одинаково, но тогда
. Если же
, то лемма справедлива в силу оценки
.
Теперь предположим, что лемма верна для некоторого и всех
, докажем, что тогда она выполняется для
и
. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки
справедливо
. Разобъем
на две части:
. Будем обозначать за
множество карт ошибок семейства алгоритмов
на выборке
. Рассмотрим множества
и
. Сопоставим каждому элементу из
его сужение на
. За
обозначим совокупность тех карт из
, которые соответствуют двум элементам множества
. Каждый из оставшихся элементов
имеет ровно один прообраз, их совокупность обозначим за
.
.
Докажем, что для совокупности алгоритмов ,
и
выполнена левая часть импликации из формулировки леммы. Предположим, что это не так, т.е.
. Тогда для выборки
выполняется
, что протеворечит условию
. Итак
. Отсюда по предположению индукции:
.
Далее, учитывая, что любая выборка длины из
является и выборкой длины
из
, принимая во внимание условие
и предположение индукции, получим
.
Окончательно:
.
Лемма доказана.
Доказательство теоремы. Пусть для некоторого . Тогда для любой подвыборки
произвольной выборки
. Отсюда по лемме Вапника-Червоненкиса
. Следовательно,
, из чего следует доказываемое утверждение.