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

Материал из 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\leq L, \\ \leq \Phi^L_l, & l\geq L\end{cases}, где \Phi^L_l  = C^0_l + C^1_l + \dots + C^L_l\; (тогда ёмкость семейства A полагают равной L).

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

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

Доказательство леммы. Сначала докажем лемму для 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, 1\leq h\leq L-1, докажем, что тогда она выполняется для L + 1 и h. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки X^{L + 1} справедливо \forall\,X^{h + 1}\subseteq X^{L + 1}\ \Delta(A, X^{h + 1})\,<\,2^{h + 1}\ (*). Разобъем X^{L + 1} на две части: X^{L + 1} = X^L\,\cup\,\{x_{\tiny L + 1}\}. Будем обозначать за \mathscr{A}(A, X^K) множество карт ошибок семейства алгоритмов A на выборке X^K:\ \mathscr{A}(A, X^K) = \{\,\tilde a(a,X^K)\::\:a\in A\,\}. Рассмотрим множества \mathscr{A}_1 = \mathscr{A}(A, X^{L + 1}) и \mathscr{A}_2 = \mathscr{A}(A, X^L). Сопоставим каждому элементу из \mathscr{A}_1 его сужение на X^L. За \mathscr{A}' обозначим совокупность тех карт из \mathscr{A}_2, которые соответствуют двум элементам множества \mathscr{A}_1. Каждый из оставшихся элементов \mathscr{A}_2 имеет ровно один прообраз, их совокупность обозначим за \mathscr{A}''.

|\mathscr{A}_1| = 2|\mathscr{A}'| + |\mathscr{A}''| = \Delta(A, X^L) + |\mathscr{A}'|.

Докажем, что для совокупности алгоритмов A' = \{a\in A\ \mid\ \tilde a(a,X^L)\in\mathscr{A}'\}, X^L и h - 1 выполнена левая часть импликации из формулировки леммы. Предположим, что это не так, т.е. \exists\ X^h\subseteq X^L\::\:\Delta(A', X^h) = 2^h. Тогда для выборки X^h \cup \{x_{\tiny L + 1}\} = X^{h + 1} \subseteq X^{L + 1} выполняется \Delta(A, X^{h + 1}) = 2^{h + 1}, что протеворечит условию (*). Итак \forall\,X^h\subseteq X^{L + 1}\ \Delta(A', X^h)\,<\,2^h. Отсюда по предположению индукции: \Delta(A', X^L)\leq \Phi^{h - 1}_L.

Далее, учитывая, что любая выборка длины h + 1 из X^L является и выборкой длины h + 1 из X^{L + 1}, принимая во внимание условие (*) и предположение индукции, получим \Delta(A, X^L)\leq \Phi^h_L. Окончательно:

\Delta(A, X^{L + 1}) = |\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}.

Лемма доказана.

Доказательство теоремы. Пусть для некоторого L\ \Delta^A(L)\,<\,2^L. Тогда для любой подвыборки X^L произвольной выборки X^l,\,l\,>\,L,\;\Delta(A, X^L)\,<\,2^L. Отсюда по лемме Вапника-Червоненкиса \Delta(A, X^l)\leq \Phi^L_l\;\forall X^l. Следовательно, \Delta^A(l)\leq\Phi^L_l, из чего следует доказываемое утверждение.

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

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