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

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

(Различия между версиями)

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

Содержание

1 Понятия, связанные с коэффициентом разнообразия
2 Разнообразие семейства классификаторов
3 См. также
4 Литература

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