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