Участник:Алексей Куренной/Песочница
Материал из MachineLearning.
(→Оценки функции роста) |
|||
Строка 11: | Строка 11: | ||
:#либо <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\,<\,L \\ <\,2^l, & l\geq\,L\end{cases}</tex> (тогда [[ёмкость]] семейства <tex>A</tex> полагают равной <tex>L - 1</tex>). | ||
- | Эту теорему можно доказать, опираясь на лемму Вапника-Червоненкиса:<br> | + | Эту теорему можно доказать, опираясь на лемму [[Вапник, Владимир Наумович | Вапника]] -[[Червоненкис, Алексей Яковлевич | Червоненкиса]]:<br> |
'''Лемма.''' <tex>\forall\,A,\,L,\,h = 0,\,1,\,\dots,\,L - 1</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\ [(\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>h = 0</tex> и <tex>h = L - 1</tex>. В случае <tex>h = 0</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>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> отсюда следует, что |
[[Категория|Учебные материалы]] | [[Категория|Учебные материалы]] |
Версия 22:33, 11 декабря 2008
Определение
Пусть и
- множества произвольной природы. Будем называть
множеством объектов, а
- множеством ответов. За
обозначим L-элементную выборку из
, т.е. подмножество
, мощность которого равна
.
Определение. Функцией роста семейства алгоритмов называется функция:
, где
- коэффициент разнообразия семейства
на выборке
.
Оценки функции роста
Поскольку для любого семейства алгоритмов и любой выборки длины L,
. Более детально поведение функции роста описывается следующей теоремой:
Теорема. Для функции роста произвольного семейства алгоритмов есть ровно две возможности:
Эту теорему можно доказать, опираясь на лемму Вапника - Червоненкиса:
Лемма. выполнено:
- для любой выборки
.
Доказательство леммы. Сначала докажем лемму для и
. В случае
выполнение левой части импликации из условия леммы означает, что на произвольном элементе выборки
все алгоритмы семейства ведут себя одинаково, но тогда
. Если же
, то лемма справедлива в силу оценки
.
Теперь предположим, что лемма верна для некоторого и всех
, докажем, что тогда она выполняется для
и
. Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки
справедливо
. Разобъем
на две части:
. Будем обозначать за
множество карт ошибок семейства алгоритмов
на выборке
. Рассмотрим множества
и
. Сопоставим каждому элементу из
его сужение на
. За
обозначим совокупность тех карт из
, которые при указанном сопоставлении имеют два прообраза. Каждый из оставшихся элементов
обладает ровно одним прообразом, их совокупность обозначим за
. Очевидно,
. Докажем, что для совокупности алгоритмов
,
и
выполнена левая часть импликации из формулировки леммы. Предположим, что это не так. Тогда
. В силу задания
отсюда следует, что