- Размерность Вапника — Червоненкиса
-
Размерность Вапника — Червоненкиса
Размерность Вапника — Червоненкиса или VC-размерность — это характеристика семейства алгоритмов для решения задачи классификации с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названное в честь Владимира Вапника и Алексея Червоненкиса.
Сами Вапник и Червоненкис предпочитают называть эту величину комбинаторной размерностью, так как, как выяснилось, она была известна алгебраистам еще до открытия их теории машинного обучения.[1]
Определение
Пусть задано множество X и некоторое семейство индикаторных функций (алгоритмов классификации, решающих правил) , где — аргумент функций, α — вектор параметров, задающий функцию. Каждая такая функция f(x,α) сопоставляет каждому элементу множества X один из двух заданных классов. VC-размерностью семейства называется наибольшее число h, такое, что существует подмножество из h элементов множества X, которые функции из могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого h, то VC-размерность полагается равной бесконечности.
VC-размерность можно обобщить и на случай семейства функций {g(x,α)}, принимающих действительные значения. Его VC-размерность определяется, как VC-размерность семейства индикаторных функций {I(g(x,α) > β)}, где β пробегает область значений функций g.[2]
Примеры
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (23 = 8 способами, на рисунке ниже показаны два из них), но множества из четырёх и более точек — уже нет. Поэтому VC-размерность линейного классификатора на плоскости равна трём.
Примеры разделения трёх
точек на два классаРазделение невозможно
для этих четырёх точекВ общем случае, VC-размерность линейных классификаторов в n-мерном пространстве равна n + 1.
Примечания
- ↑ Лекции А. А. Червоненкиса в школе анализа данных Яндекса, стр. 114.
- ↑ 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.
Wikimedia Foundation. 2010.
Размерность Вапника — Размерность Вапника Червоненкиса или VC размерность это характеристика семейства алгоритмов для решения задачи классификации с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в… … Википедия
Вапник, Владимир Наумович — Владимир Наумович Вапник (6 декабря 1936; СССР) специалист в области машинного обучения. Закончил Узбекский государственный университет в 1958. Защитил диссертацию на соискание степени кандидата наук по статистике в Институте проблем… … Википедия
Вапник — Вапник, Владимир Наумович Владимир Наумович Вапник специалист в области машинного обучения. Закончил Узбекский государственный университет в 1958. Защитил диссертацию на соискание степени кандидата наук по статистике в Институте проблем… … Википедия
Червоненкис, Алексей Яковлевич — Червоненкис Алексей Яковлевич (7 сентября 1938) российский ученый, ведущий сотрудник Института проблем управления им. В. А. Трапезникова РАН, профессор Лондонского университета (англ. Royal Holloway University of London).… … Википедия
Теория распознавания образов — Запрос «Распознавание образов» перенаправляется сюда; о романе Уильяма Гибсона см. Распознавание образов (роман) … Википедия