Участник:Алексей Куренной/Песочница

Материал из MachineLearning.

Перейти к: навигация, поиск

Определение

Пусть X и Y - множества произвольной природы. Будем называть X множеством объектов, а Y - множеством ответов. За X^L обозначим L-элементную выборку из X, т.е. подмножество X, мощность которого равна L.

Определение. Функцией роста семейства алгоритмов A называется функция:

\Delta^A(L) = \sup_{\small{X^L}}\,\Delta(A,X^L), где \Delta(A,X^L) - коэффициент разнообразия семейства A на выборке X^L.

Оценки функции роста

Поскольку \Delta(A, X^L) \leq 2^L для любого семейства алгоритмов и любой выборки длины L, \Delta^A(L) \leq 2^L. Более детально поведение функции роста описывается следующей теоремой:
Теорема. Для функции роста произвольного семейства алгоритмов есть ровно две возможности:

  1. либо \forall\,L\in\mathbb{N}\ \Delta^A(L) = 2^L (в этом случае говорят, что ёмкость семейства A равна \infty),
  2. либо \exists\,L\in \mathbb{N}\::\: \Delta^A(l)\,\begin{cases} = 2^l, & l\,<\,L \\ <\,2^l, & l\geq\,L\end{cases} (тогда ёмкость семейства A полагают равной L - 1).

Эту теорему можно доказать, опираясь на лемму Вапника-Червоненкиса:
Лемма. \forall\,A,\,L,\,h = 0,\,1,\,\dots,\,L - 1 выполнено:

для любой выборки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].

Доказательство леммы. Сначала докажем лемму для h = 0 и h = L - 1. В случае h = 0 выполенение левой части импликации из условия леммы означает, что на произвольном элементе выборки X^L все алгоритмы семейства ведут себя одинаково, но тогда \Delta(A,X^L) = 1 = \Phi^0_L. Если же h = L - 1, то лемма справедлива в силу оценки \Delta^A(L) \leq 2^L = \Phi^L_L.

Теперь предположим, что лемма верна для некоторого L и всех h'\leq h, докажем, что тогда она выполняется для L + 1 и h. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки X^{L + 1} справедливо \forall\,X^{h + 1}\subseteq X^{L + 1}\ \Delta(A, X^{h + 1})\,<\,2^{h + 1}.

Учебные материалы

Личные инструменты