Участник:Алексей Куренной/Песочница
Материал из MachineLearning.
(Новая: ==Коэффициент разнообразия семейства алгоритмов== {{Main|Функция роста}} Пусть <tex>X</tex> и <tex>Y</tex> - множеств...) |
|||
Строка 1: | Строка 1: | ||
- | == | + | ==Определение== |
- | + | Пусть <tex>X</tex> и <tex>Y</tex> - множества произвольной природы. Будем называть <tex>X</tex> ''множеством объектов'', а <tex>Y</tex> - ''множеством ответов''. За <tex>X^L</tex> обозначим ''L-элементную выборку'' из <tex>X</tex>, т.е. подмножество <tex>X</tex>, мощность которого равна <tex>L</tex>. | |
- | Пусть <tex>X</tex> и <tex>Y</tex> - множества произвольной природы. Будем называть <tex>X</tex> ''множеством объектов'', а <tex>Y</tex> - ''множеством ответов | + | |
- | '''Определение.''' '' | + | '''Определение.''' '''''Функцией роста''''' семейства алгоритмов <tex>A</tex> называется функция:<br> |
- | + | :<tex>\Delta^A(L) = \sup_{\small{X^L}}\,\Delta(A,X^L)</tex>, где <tex>\Delta(A,X^L)</tex> - [[коэффициент разнообразия]] семейства <tex>A</tex> на выборке <tex>X^L</tex>. | |
- | + | ==Оценки функции роста== | |
- | :<tex>\Delta(A, X^ | + | Поскольку <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>\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> | ||
+ | '''Лемма.''' <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>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>. | ||
[[Категория|Учебные материалы]] | [[Категория|Учебные материалы]] |
Версия 14:00, 11 декабря 2008
Определение
Пусть и - множества произвольной природы. Будем называть множеством объектов, а - множеством ответов. За обозначим L-элементную выборку из , т.е. подмножество , мощность которого равна .
Определение. Функцией роста семейства алгоритмов называется функция:
- , где - коэффициент разнообразия семейства на выборке .
Оценки функции роста
Поскольку для любого семейства алгоритмов и любой выборки длины L, . Более детально поведение функции роста описывается следующей теоремой:
Теорема. Для функции роста произвольного семейства алгоритмов есть ровно две возможности:
Эту теорему можно доказать, опираясь на лемму Вапника-Червоненкиса:
Лемма. выполнено:
- для любой выборки.
Доказательство леммы. Сначала докажем лемму для и . В случае выполенение левой части импликации из условия леммы означает, что на произвольном элементе выборки все алгоритмы семейства ведут себя одинаково, но тогда . Если же , то лемма справедлива в силу оценки .
Теперь предположим, что лемма верна для некоторого и всех , докажем, что тогда она выполняется для и . Рассмотрим произвольное семейство алгоритмов. Пусть для некоторой выборки справедливо .