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