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