Размерность Вапника — Червоненкиса (Jg[byjukvm, Fghuntg — Cyjfkuyutnvg)

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

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

Определение

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

VC-размерность можно обобщить и на случай семейства функций $\{g(x,\alpha )\}$ , принимающих действительные значения. Его VC-размерность определяется как VC-размерность семейства индикаторных функций $\{I(g(x,\alpha )>\beta )\}$ , где $\beta$ пробегает область значений функций $g$ .^[1]

Примеры

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


Примеры разделения трёх точек на два класса			Разделение невозможно для этих четырёх точек

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

См. также

Метод опорных векторов

Ссылки

Информация с сайта www.machinelearning.ru

Примечания

↑ Hastie, T., Tibshirani R., Friedman J. Chapter 7.9. Vapnik–Chervonenkis Dimension // The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0..

[1] Hastie, T., Tibshirani R., Friedman J. Chapter 7.9. Vapnik–Chervonenkis Dimension // The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0..

[1]

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG