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