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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: ==Коэффициент разнообразия семейства алгоритмов== {{Main|Функция роста}} Пусть <tex>X</tex> и <tex>Y</tex> - множеств...)
Строка 1: Строка 1:
-
==Коэффициент разнообразия семейства алгоритмов==
+
==Определение==
-
{{Main|Функция роста}}
+
Пусть <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>y\::\:X \rightarrow Y</tex>, которое назовем ''целевой зависимостью''. За <tex>X^L</tex> обозначим ''L-элементную выборку'' из <tex>X</tex>, т.е. подмножество <tex>X</tex>, мощность которого равна L.
+
-
'''Определение.''' ''Карта (вектор)'' ошибок алгоритма <tex>a\::\:X \rightarrow Y</tex> на выборке <tex>X^L</tex> есть отображение <tex>X^L\::\:\rightarrow \{0,\,1\}</tex>, равное единице, если алгоритм ошибается на объекте, и нулю в противном случае:<br>
+
'''Определение.''' '''''Функцией роста''''' семейства алгоритмов <tex>A</tex> называется функция:<br>
-
:<tex>\tilde a(x;\,a,X^L) = [a(x) \neq y(x)]</tex>
+
:<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>A</tex> на выборке <tex>X^L</tex> называется число всевозможных карт ошибок данного семейства на выборке <tex>X^L\:</tex>:<br>
+
==Оценки функции роста==
-
:<tex>\Delta(A, X^L) = \|\{\,\tilde a(a,X^L)\::\:a\in A\,\}\|</tex>
+
Поскольку <tex>\Delta(A, X^L) \leq 2^L</tex> для любого семейства алгоритмов и любой выборки длины L, <tex>\Delta^A(L) \leq 2^L</tex>. Более детально поведение функции роста описывается следующей теоремой:<br>
-
Очевидно, <tex>\Delta(A, X^L) \leq 2^L</tex>.
+
'''Теорема.''' Для функции роста произвольного семейства алгоритмов есть ровно две возможности:<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

Определение

Пусть 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}.

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

Источник — «http://www.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»
Личные инструменты