Коэффициент разнообразия
Материал из MachineLearning.
(категория, ссылки) |
(переработка) |
||
Строка 1: | Строка 1: | ||
- | + | {{TOCright}} | |
- | + | '''Коэффициент разнообразия''' (shattering coefficient) множества бинарных функций | |
+ | <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>F</tex> на выборку <tex>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>. | ||
- | ''' | + | В некоторых работах переводится на русский язык как ''коэффициент дробления'' |
- | + | <ref>''Райгородский, А. М.'' Экстремальные задачи теории графов и~анализ данных. М.: НИЦ «Регулярная и хаотическая динамика»>>, Институт компьютерных исследований, 2008.</ref>. | |
+ | ''Shatter'' в буквальном переводе — «разбивать на мелкие кусочки, вдребезги». | ||
- | Очевидно, <tex>\Delta( | + | В исходных работах [[Теория Вапника-Червоненкиса|Вапника и Червоненкиса]] (на русском языке) вводилось эквивалентное понятие ''индекс системы событий''<ref>{{П:Вапник 74}}</ref><ref>{{П:Вапник 79}}</ref>. |
+ | Под «событием» понимается множество объектов | ||
+ | <tex>S_f=\bigl\{x\in X:\; f(x)=1 \bigr\}</tex>, взаимно однозначно соотвествующее функции <tex>f</tex>, | ||
+ | а под «системой событий» понимается множество | ||
+ | <tex>S=\bigl\{S_f:\; f\in F \bigr\}</tex>. | ||
+ | |||
+ | Очевидно, <tex>\Delta(F, X^L) \leq 2^L</tex>. | ||
+ | Коэффициент разнообразия характеризует «богатство», «выразительные возможности» множества функций <tex>F</tex>. | ||
+ | |||
+ | == Понятия, связанные с коэффициентом разнообразия == | ||
+ | |||
+ | Максимальное значение коэффициента разнообразия, достигаемое на всевозможных выборках длины <tex>L</tex>, называется ''[[функция роста|функцией роста]]'' множества <tex>F</tex>: | ||
+ | ::<tex>\Delta^F(L) = \max_{X^L} \Delta(F, X^L).</tex> | ||
+ | |||
+ | С функцией роста тесно связано понятие [[размерность Вапника–Червоненкиса|размерности Вапника–Червоненкиса]] (VC-dimension). В исходных работах она называлась ''ёмкостью'' множества <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/> | ||
[[Категория:Теория вычислительного обучения]] | [[Категория:Теория вычислительного обучения]] |
Версия 22:46, 9 января 2010
|
Коэффициент разнообразия (shattering coefficient) множества бинарных функций на выборке объектов — это мощность множества всевозможных -мерных бинарных векторов вида :
Иногда также говорят о мощности проекции множества функций на выборку [1].
В некоторых работах переводится на русский язык как коэффициент дробления [1]. Shatter в буквальном переводе — «разбивать на мелкие кусочки, вдребезги».
В исходных работах Вапника и Червоненкиса (на русском языке) вводилось эквивалентное понятие индекс системы событий[1][1]. Под «событием» понимается множество объектов , взаимно однозначно соотвествующее функции , а под «системой событий» понимается множество .
Очевидно, . Коэффициент разнообразия характеризует «богатство», «выразительные возможности» множества функций .
Понятия, связанные с коэффициентом разнообразия
Максимальное значение коэффициента разнообразия, достигаемое на всевозможных выборках длины , называется функцией роста множества :
С функцией роста тесно связано понятие размерности Вапника–Червоненкиса (VC-dimension). В исходных работах она называлась ёмкостью множества .
Разнообразие семейства классификаторов
Пусть — конечное множество номеров (имён, меток) классов. Существует неизвестная целевая зависимость — отображение . Пусть — семейство классификаторов.
Коэффициент разнообразия множества классификаторов — это коэффициент разнообразия множества функций
В случае классификации на два класса коэффициент разнообразия множества классификаторов — это число всевозможных дихотомий выборки (способов разделить выборку на два класса), реализуемых всевозможными классификаторами .