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

Материал из 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$ . Более детально поведение функции роста описывается следующей теоремой:
Теорема. Для функции роста произвольного семейства алгоритмов есть ровно две возможности:

либо $\forall\,L\in\mathbb{N}\ \Delta^A(L) = 2^L\;$ (в этом случае говорят, что ёмкость семейства $A$ равна $\infty$ ),
либо $\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$ , из чего следует доказываемое утверждение.

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B5%D0%B9_%D0%9A%D1%83%D1%80%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 8: / Строка 8: @@
 Поскольку <tex>\Delta(A, X^L) \leq 2^L</tex> для любого семейства алгоритмов и любой выборки длины L, <tex>\Delta^A(L) \leq 2^L</tex>. Более детально поведение функции роста описывается следующей теоремой:<br>
 '''Теорема.''' Для функции роста произвольного семейства алгоритмов есть ровно две возможности:<br>
-:#либо <tex>\forall\,L\in\mathbb{N}\ \Delta^A(L) = 2^L</tex> (в этом случае говорят, что [[ёмкость]] семейства <tex>A</tex> равна <tex>\infty</tex>),
+:#либо <tex>\forall\,L\in\mathbb{N}\ \Delta^A(L) = 2^L\;</tex> (в этом случае говорят, что [[ёмкость]] семейства <tex>A</tex> равна <tex>\infty</tex>),
-:#либо <tex>\exists\,L\in \mathbb{N}\::\: \Delta^A(l)\,\begin{cases} = 2^l, & l\,<\,L \\ <\,2^l, & l\geq\,L\end{cases}</tex> (тогда [[ёмкость]] семейства <tex>A</tex> полагают равной <tex>L - 1</tex>).
+:#либо <tex>\exists\,L\in \mathbb{N}\::\: \Delta^A(l)\,\begin{cases} = 2^l, & l\leq L, \\ \leq \Phi^L_l, & l\geq L\end{cases}</tex>, где <tex>\Phi^L_l  = C^0_l + C^1_l + \dots + C^L_l\;</tex> (тогда [[ёмкость]] семейства <tex>A</tex> полагают равной <tex>L</tex>).
 Эту теорему можно доказать, опираясь на лемму [[Вапник, Владимир Наумович | Вапника]] -[[Червоненкис, Алексей Яковлевич | Червоненкиса]]:<br>
 '''Лемма.''' <tex>\forall\,A,\,L,\,h = 0,\,1,\,\dots,\,L - 1</tex> выполнено:<br>
-: для любой выборки<tex>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]</tex>.
+: для любой выборки <tex>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]</tex>.
 '''Доказательство леммы'''. Сначала докажем лемму для <tex>h = 0</tex> и <tex>h = L - 1</tex>. В случае <tex>h = 0</tex> выполнение левой части импликации из условия леммы означает, что на произвольном элементе выборки <tex>X^L</tex> все алгоритмы семейства ведут себя одинаково, но тогда <tex>\Delta(A,X^L) = 1 = \Phi^0_L</tex>. Если же <tex>h = L - 1</tex>, то лемма справедлива в силу оценки <tex>\Delta^A(L) \leq 2^L = \Phi^L_L</tex>.
-Теперь предположим, что лемма верна для некоторого <tex>L</tex> и всех <tex>h'\leq h</tex>, докажем, что тогда она выполняется для <tex>L + 1</tex> и <tex>h</tex>. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки <tex>X^{L + 1}</tex> справедливо <tex>\forall\,X^{h + 1}\subseteq X^{L + 1}\ \Delta(A, X^{h + 1})\,<\,2^{h + 1}</tex>. Разобъем <tex>X^{L + 1}</tex> на две части: <tex>X^{L + 1} = X^L\,\cup\,\{x_{\tiny L + 1}\}</tex>. Будем обозначать за <tex>\mathscr{A}(A, X^K)</tex> множество [[Коэффициент разнообразия | карт ошибок]] семейства алгоритмов <tex>A</tex> на выборке <tex>X^K:\ \mathscr{A}(A, X^K) = \{\,\tilde a(a,X^K)\::\:a\in A\,\}</tex>. Рассмотрим множества <tex>\mathscr{A}_1 = \mathscr{A}(A, X^{L + 1})</tex> и <tex>\mathscr{A}_2 = \mathscr{A}(A, X^L)</tex>. Сопоставим каждому элементу из <tex>\mathscr{A}_1</tex> его сужение на <tex>X^L</tex>. За <tex>\mathscr{A}'</tex> обозначим совокупность тех карт из <tex>\mathscr{A}_2</tex>, которые при указанном сопоставлении имеют два прообраза. Каждый из оставшихся элементов <tex>\mathscr{A}_2</tex> обладает ровно одним прообразом, их совокупность обозначим за <tex>\mathscr{A}''</tex>. Очевидно, <tex>|\mathscr{A}_1| = 2|\mathscr{A}'| + |\mathscr{A}''| = \Delta(A, X^L) + |\mathscr{A}'|</tex>. Докажем, что для совокупности алгоритмов <tex>A' = \{a\in A\ \mid\ \tilde a(a,X^L)\in\mathscr{A}'\}</tex>, <tex>X^L</tex> и <tex>h - 1</tex> выполнена левая часть импликации из формулировки леммы. Предположим, что это не так. Тогда <tex>\exists\ X^h\subseteq X^L\::\:\Delta(A', X^h) = 2^h</tex>. В силу задания <tex>A'</tex> отсюда следует, что
+Теперь предположим, что лемма верна для некоторого <tex>L</tex> и всех <tex>h'\leq h, 1\leq h\leq L-1</tex>, докажем, что тогда она выполняется для <tex>L + 1</tex> и <tex>h</tex>. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки <tex>X^{L + 1}</tex> справедливо <tex>\forall\,X^{h + 1}\subseteq X^{L + 1}\ \Delta(A, X^{h + 1})\,<\,2^{h + 1}\ (*)</tex>. Разобъем <tex>X^{L + 1}</tex> на две части: <tex>X^{L + 1} = X^L\,\cup\,\{x_{\tiny L + 1}\}</tex>. Будем обозначать за <tex>\mathscr{A}(A, X^K)</tex> множество [[Коэффициент разнообразия | карт ошибок]] семейства алгоритмов <tex>A</tex> на выборке <tex>X^K:\ \mathscr{A}(A, X^K) = \{\,\tilde a(a,X^K)\::\:a\in A\,\}</tex>. Рассмотрим множества <tex>\mathscr{A}_1 = \mathscr{A}(A, X^{L + 1})</tex> и <tex>\mathscr{A}_2 = \mathscr{A}(A, X^L)</tex>. Сопоставим каждому элементу из <tex>\mathscr{A}_1</tex> его сужение на <tex>X^L</tex>. За <tex>\mathscr{A}'</tex> обозначим совокупность тех карт из <tex>\mathscr{A}_2</tex>, которые соответствуют двум элементам множества <tex>\mathscr{A}_1</tex>. Каждый из оставшихся элементов <tex>\mathscr{A}_2</tex> имеет ровно один прообраз, их совокупность обозначим за <tex>\mathscr{A}''</tex>.
+:<tex>|\mathscr{A}_1| = 2|\mathscr{A}'| + |\mathscr{A}''| = \Delta(A, X^L) + |\mathscr{A}'|</tex>.
+Докажем, что для совокупности алгоритмов <tex>A' = \{a\in A\ \mid\ \tilde a(a,X^L)\in\mathscr{A}'\}</tex>, <tex>X^L</tex> и <tex>h - 1</tex> выполнена левая часть импликации из формулировки леммы. Предположим, что это не так, т.е. <tex>\exists\ X^h\subseteq X^L\::\:\Delta(A', X^h) = 2^h</tex>. Тогда для выборки <tex>X^h \cup \{x_{\tiny L + 1}\} = X^{h + 1} \subseteq X^{L + 1}</tex> выполняется <tex>\Delta(A, X^{h + 1}) = 2^{h + 1}</tex>, что протеворечит условию <tex>(*)</tex>. Итак <tex>\forall\,X^h\subseteq X^{L + 1}\ \Delta(A', X^h)\,<\,2^h</tex>. Отсюда по предположению индукции: <tex>\Delta(A', X^L)\leq \Phi^{h - 1}_L</tex>.
+Далее, учитывая, что любая выборка длины <tex>h + 1</tex> из <tex>X^L</tex> является и выборкой длины <tex>h + 1</tex> из <tex>X^{L + 1}</tex>, принимая во внимание условие <tex>(*)</tex> и предположение индукции, получим <tex>\Delta(A, X^L)\leq \Phi^h_L</tex>.
+Окончательно:<br>
+:<tex>\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}</tex>.
+Лемма доказана.
+'''Доказательство теоремы'''. Пусть для некоторого <tex>L\ \Delta^A(L)\,<\,2^L</tex>. Тогда для любой подвыборки <tex>X^L</tex> произвольной выборки <tex>X^l,\,l\,>\,L,\;\Delta(A, X^L)\,<\,2^L</tex>. Отсюда по лемме Вапника-Червоненкиса <tex>\Delta(A, X^l)\leq \Phi^L_l\;\forall X^l</tex>. Следовательно, <tex>\Delta^A(l)\leq\Phi^L_l</tex>, из чего следует доказываемое утверждение.
 [[Категория|Учебные материалы]]

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

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

Текущая версия

Определение

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

Просмотры

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

Навигация

Поиск

Инструменты