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

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

(Различия между версиями)
Перейти к: навигация, поиск
(переработка)
м (оформление)
Строка 23: Строка 23:
Очевидно, <tex>\Delta(F, X^L) \leq 2^L</tex>.
Очевидно, <tex>\Delta(F, X^L) \leq 2^L</tex>.
 +
Коэффициент разнообразия характеризует «богатство», «выразительные возможности» множества функций&nbsp;<tex>F</tex>.
Коэффициент разнообразия характеризует «богатство», «выразительные возможности» множества функций&nbsp;<tex>F</tex>.

Версия 22:48, 9 января 2010

Содержание

Коэффициент разнообразия (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://www.recognition.su/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»
Личные инструменты