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

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

Версия от 22:51, 9 января 2010; Vokov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

Коэффициент разнообразия (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.

Применение

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

См. также

Литература

Личные инструменты