Просмотр кода страницы Размерность Вапника — Червоненкиса

'''Размерность Вапника — Червоненкиса''' или '''VC-размерность''' — это характеристика семейства алгоритмов для решения [[Задача классификации|задачи классификации]] с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названное в честь [[Вапник, Владимир Наумович|Владимира Вапника]] и [[Червоненкис, Алексей Яковлевич|Алексея Червоненкиса]].

Сами Вапник и Червоненкис предпочитают называть эту величину '''комбинаторной размерностью''', так как выяснилось, она была известна алгебраистам еще до открытия их теории [[Машинное обучение|машинного обучения]].

== Определение ==
Пусть задано множество <math>X</math> и некоторое семейство индикаторных функций (алгоритмов классификации, решающих правил) <math>\mathcal{F} = \{ f(x, \alpha) \}</math>, где <math>x \in X</math> — аргумент функций, <math>\alpha</math> — вектор параметров, задающий функцию. Каждая такая функция <math>f(x, \alpha)</math> сопоставляет каждому элементу множества <math>X</math> один из двух заданных классов. VC-размерностью семейства <math>\mathcal{F}</math> называется наибольшее число <math>h</math>, такое, что существует подмножество из <math>h</math> элементов множества <math>X</math>, которые функции из <math>\mathcal{F}</math> могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого <math>h</math>, то VC-размерность полагается равной бесконечности.

VC-размерность можно обобщить и на случай семейства функций <math>\{ g(x, \alpha) \}</math>, принимающих действительные значения. Его VC-размерность определяется как VC-размерность семейства индикаторных функций <math>\{ I(g(x, \alpha) > \beta) \}</math>, где <math>\beta</math> пробегает [[область значений]] функций <math>g</math>.<ref>{{Книга:The Elements of Statistical Learning|часть=Chapter 7.9. Vapnik–Chervonenkis Dimension}}</ref>

== Примеры ==
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый [[линейный классификатор]]. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (<math>2^3 = 8</math> способами, на рисунке ниже показаны три из них), но множества из четырёх и более точек — уже нет. Поэтому VC-размерность линейного классификатора на плоскости равна трём.

{| border="0" cellpadding="4" cellspacing="0" align="center"
| align="center" bgcolor=#ddffdd | [[Файл:VC1.svg]]
| align="center" bgcolor=#ddffdd | [[Файл:VC2.svg]]
| align="center" bgcolor=#ddffdd | [[Файл:VC3.svg]]
| align="center" bgcolor=#ffdddd | [[Файл:VC4.svg]]
|-
| colspan="3" align="center" bgcolor=#ddffdd | '''Примеры разделения трёх<br />точек на два класса'''
| align="center" bgcolor=#ffdddd | '''Разделение невозможно<br />для этих четырёх точек'''
|}

В общем случае, VC-размерность линейных классификаторов в <math>n</math>-мерном пространстве равна <math>n + 1</math>.

== См. также ==
* [[Метод опорных векторов]]

== Ссылки ==
*[http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%92%D0%B0%D0%BF%D0%BD%D0%B8%D0%BA%D0%B0-%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%B5%D0%BD%D0%BA%D0%B8%D1%81%D0%B0 Информация с сайта www.machinelearning.ru]

== Примечания ==
{{примечания}}
{{Машинное обучение}}

[[Категория:Машинное обучение]]