Коэффициент разнообразия

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

(Различия между версиями)
Перейти к: навигация, поиск
м (→Коэффициент разнообразия семейства алгоритмов)
(дополнение)
 
(5 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
==Коэффициент разнообразия семейства алгоритмов==
+
{{TOCright}}
-
{{Main|Функция роста}}
+
'''Коэффициент разнообразия''' (shattering coefficient) множества бинарных функций
-
Пусть <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>F = \bigl\{ f:\;X\to\{0,1\} \bigr\}</tex>
 +
на выборке объектов
 +
<tex>X^L=(x_1,\ldots,x_L)\subset X</tex>
 +
— это мощность множества всевозможных <tex>L</tex>-мерных бинарных векторов вида
 +
<tex>\bigl( f(x_1),\ldots,f(x_L) \bigr)</tex>:
 +
::<tex>\Delta(F, X^L) = \| \bigl\{\,\bigl( f(x_1),\ldots,f(x_L) \bigr):\;f\in F\,\bigr\} \|.</tex>
-
'''Определение.''' ''Карта (вектор)'' ошибок алгоритма <tex>a\::\:X \rightarrow Y</tex> на выборке <tex>X^L</tex> есть отображение <tex>X^L \rightarrow \{0,\,1\}</tex>, равное единице, если алгоритм ошибается на объекте, и нулю в противном случае:<br>
+
Иногда также говорят о ''мощности проекции множества функций <tex>F</tex> на выборку <tex>X</tex>''
-
:<tex>\tilde a(x;\,a,X^L) = [a(x) \neq y(x)]</tex>
+
<ref>''Petra Philips'' [http://Data-Dependent Analysis of Learning Algorithms infoeng.rsise.anu.edu.au/files/petra\_philips\_thesis.pdf]. PhD thesis. The Australian National University, Canberra. 2005.
 +
</ref>.
-
'''Определение.''' '''''Коэффициентом разнообразия''''' семейства алгоритмов <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>
+
<ref>''Райгородский, А. М.'' Экстремальные задачи теории графов и~анализ данных. М.:&nbsp;НИЦ «Регулярная и хаотическая динамика»>>, Институт компьютерных исследований, 2008.</ref>.
 +
''Shatter'' в буквальном переводе — «разбивать на мелкие кусочки, вдребезги».
-
Очевидно, <tex>\Delta(A, X^L) \leq 2^L</tex>.
+
В исходных работах [[Теория Вапника-Червоненкиса|Вапника и Червоненкиса]] (на русском языке) вводилось эквивалентное понятие ''индекс системы событий''<ref>{{П:Вапник 74}}</ref><ref>{{П:Вапник 79}}</ref>.
 +
Под «событием» понимается множество объектов
 +
<tex>S_f=\bigl\{x\in X:\; f(x)=1 \bigr\}</tex>, взаимно однозначно соотвествующее функции&nbsp;<tex>f</tex>,
 +
а под «системой событий» понимается множество
 +
<tex>S=\bigl\{S_f:\; f\in F \bigr\}</tex>.
-
[[Категория|Учебные материалы]]
+
Очевидно, <tex>\Delta(F, X^L) \leq 2^L</tex>.
 +
 
 +
Коэффициент разнообразия характеризует «богатство», «выразительные возможности» множества функций&nbsp;<tex>F</tex>.
 +
 
 +
== Понятия, связанные с коэффициентом разнообразия ==
 +
 
 +
Максимальное значение коэффициента разнообразия, достигаемое на всевозможных выборках длины <tex>L</tex>, называется ''[[функция роста|функцией роста]]'' множества&nbsp;<tex>F</tex>:
 +
::<tex>\Delta^F(L) = \max_{X^L} \Delta(F, X^L).</tex>
 +
 
 +
С функцией роста тесно связано понятие [[размерность Вапника–Червоненкиса|размерности Вапника–Червоненкиса]] (VC-dimension). В исходных работах она называлась ''ёмкостью'' множества&nbsp;<tex>F</tex>.
 +
 
 +
== Разнообразие семейства классификаторов ==
 +
 
 +
Пусть <tex>Y</tex> — конечное множество номеров (имён, меток) классов.
 +
Существует неизвестная ''целевая зависимость'' — отображение <tex>y:\:X \to Y</tex>.
 +
Пусть <tex>A:\: X\to Y</tex> — семейство [[классификатор|классификаторов]].
 +
 
 +
'''Коэффициент разнообразия множества классификаторов''' <tex>A</tex> — это коэффициент разнообразия множества функций
 +
::<tex>\bigl\{ f(x) = \bigl[ a(x) \neq y(x) \bigr]:\; a\in A \bigr\}.</tex>
 +
 
 +
В случае классификации на два класса коэффициент разнообразия множества классификаторов — это число всевозможных дихотомий выборки (способов разделить выборку на два класса), реализуемых всевозможными классификаторами <tex>a\in A</tex>.
 +
 
 +
== Применение ==
 +
 
 +
Коэффициент разнообразия используется в оценках [[обобщающая способность|обобщающей способности]], зависящих от данных.
 +
 
 +
==См. также==
 +
* [[Теория Вапника-Червоненкиса]]
 +
* [[Размерность Вапника-Червоненкиса]]
 +
* [[Функция роста]]
 +
 
 +
== Литература ==
 +
<references/>
 +
 
 +
[[Категория:Теория вычислительного обучения]]

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

Содержание

Коэффициент разнообразия (shattering coefficient) множества бинарных функций F = \bigl\{ f:\;X\to\{0,1\} \bigr\} на выборке объектов X^L=(x_1,\ldots,x_L)\subset X — это мощность множества всевозможных L-мерных бинарных векторов вида \bigl( f(x_1),\ldots,f(x_L) \bigr):

\Delta(F, X^L) = \| \bigl\{\,\bigl( f(x_1),\ldots,f(x_L) \bigr):\;f\in F\,\bigr\} \|.

Иногда также говорят о мощности проекции множества функций F на выборку X [1].

В некоторых работах переводится на русский язык как коэффициент дробления [1]. Shatter в буквальном переводе — «разбивать на мелкие кусочки, вдребезги».

В исходных работах Вапника и Червоненкиса (на русском языке) вводилось эквивалентное понятие индекс системы событий[1][1]. Под «событием» понимается множество объектов S_f=\bigl\{x\in X:\; f(x)=1 \bigr\}, взаимно однозначно соотвествующее функции f, а под «системой событий» понимается множество S=\bigl\{S_f:\; f\in F \bigr\}.

Очевидно, \Delta(F, X^L) \leq 2^L.

Коэффициент разнообразия характеризует «богатство», «выразительные возможности» множества функций F.

Понятия, связанные с коэффициентом разнообразия

Максимальное значение коэффициента разнообразия, достигаемое на всевозможных выборках длины L, называется функцией роста множества F:

\Delta^F(L) = \max_{X^L} \Delta(F, X^L).

С функцией роста тесно связано понятие размерности Вапника–Червоненкиса (VC-dimension). В исходных работах она называлась ёмкостью множества F.

Разнообразие семейства классификаторов

Пусть Y — конечное множество номеров (имён, меток) классов. Существует неизвестная целевая зависимость — отображение y:\:X \to Y. Пусть A:\: X\to Y — семейство классификаторов.

Коэффициент разнообразия множества классификаторов A — это коэффициент разнообразия множества функций

\bigl\{ f(x) = \bigl[ a(x) \neq y(x) \bigr]:\; a\in A \bigr\}.

В случае классификации на два класса коэффициент разнообразия множества классификаторов — это число всевозможных дихотомий выборки (способов разделить выборку на два класса), реализуемых всевозможными классификаторами a\in A.

Применение

Коэффициент разнообразия используется в оценках обобщающей способности, зависящих от данных.

См. также

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BE%D1%8D%D1%84%D1%84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82_%D1%80%D0%B0%D0%B7%D0%BD%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%B8%D1%8F»
Личные инструменты