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