Материал из MachineLearning.
Определение
Пусть 
и 
- множества произвольной природы. Будем называть множеством объектов, а - множеством ответов. За 
обозначим L-элементную выборку из , т.е. подмножество , мощность которого равна 
.
Определение. Функцией роста семейства алгоритмов 
называется функция:
 = \sup_{\small{X^L}}\,\Delta(A,X^L))
, где )
- коэффициент разнообразия семейства на выборке .
Оценки функции роста
Поскольку  \leq 2^L)
для любого семейства алгоритмов и любой выборки длины L,  \leq 2^L)
. Более детально поведение функции роста описывается следующей теоремой:
Теорема. Для функции роста произвольного семейства алгоритмов есть ровно две возможности:
- либо
 = 2^L\;)
(в этом случае говорят, что ёмкость семейства равна 
),
- либо
\,\begin{cases} = 2^l, & l\leq L, \\ \leq \Phi^L_l, & l\geq L\end{cases})
, где 
(тогда ёмкость семейства полагают равной ).
Эту теорему можно доказать, опираясь на лемму Вапника - Червоненкиса:
Лемма. 
выполнено:
- для любой выборки
![X^L\ \left[\left(\forall\,X^{h + 1}\subseteq X^L\ \Delta(A, X^{h + 1})\,<\,2^{h + 1}\right)\Rightarrow\Delta(A, X^L)\leq\Phi^h_L\right]](../mimetex/?X^L\ \left[\left(\forall\,X^{h + 1}\subseteq X^L\ \Delta(A, X^{h + 1})\,<\,2^{h + 1}\right)\Rightarrow\Delta(A, X^L)\leq\Phi^h_L\right])
.
Доказательство леммы. Сначала докажем лемму для 
и 
. В случае выполнение левой части импликации из условия леммы означает, что на произвольном элементе выборки все алгоритмы семейства ведут себя одинаково, но тогда  = 1 = \Phi^0_L)
. Если же , то лемма справедлива в силу оценки  \leq 2^L = \Phi^L_L)
.
Теперь предположим, что лемма верна для некоторого и всех 
, докажем, что тогда она выполняется для 
и 
. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки 
справедливо \,<\,2^{h + 1}\ (*))
. Разобъем на две части: 
. Будем обозначать за )
множество карт ошибок семейства алгоритмов на выборке  = \{\,\tilde a(a,X^K)\::\:a\in A\,\})
. Рассмотрим множества )
и )
. Сопоставим каждому элементу из 
его сужение на . За 
обозначим совокупность тех карт из 
, которые соответствуют двум элементам множества . Каждый из оставшихся элементов имеет ровно один прообраз, их совокупность обозначим за 
.
 + |\mathscr{A}'|)
.
Докажем, что для совокупности алгоритмов \in\mathscr{A}'\})
, и 
выполнена левая часть импликации из формулировки леммы. Предположим, что это не так, т.е.  = 2^h)
. Тогда для выборки 
выполняется  = 2^{h + 1})
, что протеворечит условию )
. Итак \,<\,2^h)
. Отсюда по предположению индукции: \leq \Phi^{h - 1}_L)
.
Далее, учитывая, что любая выборка длины 
из является и выборкой длины из , принимая во внимание условие и предположение индукции, получим \leq \Phi^h_L)
.
Окончательно:
 = |\mathscr{A}_1| = \Delta(A, X^L) + |\mathscr{A}'| = \Delta(A, X^L) + \Delta(A', X^L) \leq \Phi^h_L + \Phi^{h - 1}_L = \Phi^h_{L + 1})
.
Лемма доказана.
Доказательство теоремы. Пусть для некоторого \,<\,2^L)
. Тогда для любой подвыборки произвольной выборки \,<\,2^L)
. Отсюда по лемме Вапника-Червоненкиса \leq \Phi^L_l\;\forall X^l)
. Следовательно, \leq\Phi^L_l)
, из чего следует доказываемое утверждение.
Учебные материалы
