Размерность Вапника — Червоненкиса
Размерность Вапника — Червоненкиса или 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>.[1]
Примеры
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (<math>2^3 = 8</math> способами, на рисунке ниже показаны три из них), но множества из четырёх и более точек — уже нет. Поэтому VC-размерность линейного классификатора на плоскости равна трём.
|
|
|
|
| Примеры разделения трёх точек на два класса |
Разделение невозможно для этих четырёх точек | ||
В общем случае, VC-размерность линейных классификаторов в <math>n</math>-мерном пространстве равна <math>n + 1</math>.
См. также
Напишите отзыв о статье "Размерность Вапника — Червоненкиса"
Ссылки
- [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]
Примечания
- ↑ Hastie, T., Tibshirani R., Friedman J. Chapter 7.9. Vapnik–Chervonenkis Dimension // [www-stat.stanford.edu/~tibs/ElemStatLearn/ The Elements of Statistical Learning: Data Mining, Inference, and Prediction]. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0..
Отрывок, характеризующий Размерность Вапника — Червоненкиса
Ослабевший французский офицер был Рамбаль; повязанный платком был его денщик Морель.Когда Морель выпил водки и доел котелок каши, он вдруг болезненно развеселился и начал не переставая говорить что то не понимавшим его солдатам. Рамбаль отказывался от еды и молча лежал на локте у костра, бессмысленными красными глазами глядя на русских солдат. Изредка он издавал протяжный стон и опять замолкал. Морель, показывая на плечи, внушал солдатам, что это был офицер и что его надо отогреть. Офицер русский, подошедший к костру, послал спросить у полковника, не возьмет ли он к себе отогреть французского офицера; и когда вернулись и сказали, что полковник велел привести офицера, Рамбалю передали, чтобы он шел. Он встал и хотел идти, но пошатнулся и упал бы, если бы подле стоящий солдат не поддержал его.
– Что? Не будешь? – насмешливо подмигнув, сказал один солдат, обращаясь к Рамбалю.
– Э, дурак! Что врешь нескладно! То то мужик, право, мужик, – послышались с разных сторон упреки пошутившему солдату. Рамбаля окружили, подняли двое на руки, перехватившись ими, и понесли в избу. Рамбаль обнял шеи солдат и, когда его понесли, жалобно заговорил:
– Oh, nies braves, oh, mes bons, mes bons amis! Voila des hommes! oh, mes braves, mes bons amis! [О молодцы! О мои добрые, добрые друзья! Вот люди! О мои добрые друзья!] – и, как ребенок, головой склонился на плечо одному солдату.
Между тем Морель сидел на лучшем месте, окруженный солдатами.
Морель, маленький коренастый француз, с воспаленными, слезившимися глазами, обвязанный по бабьи платком сверх фуражки, был одет в женскую шубенку. Он, видимо, захмелев, обнявши рукой солдата, сидевшего подле него, пел хриплым, перерывающимся голосом французскую песню. Солдаты держались за бока, глядя на него.
– Ну ка, ну ка, научи, как? Я живо перейму. Как?.. – говорил шутник песенник, которого обнимал Морель.
Vive Henri Quatre,
Vive ce roi vaillanti –
[Да здравствует Генрих Четвертый!
Да здравствует сей храбрый король!
и т. д. (французская песня) ]
пропел Морель, подмигивая глазом.
Сe diable a quatre…
– Виварика! Виф серувару! сидябляка… – повторил солдат, взмахнув рукой и действительно уловив напев.
– Вишь, ловко! Го го го го го!.. – поднялся с разных сторон грубый, радостный хохот. Морель, сморщившись, смеялся тоже.
– Ну, валяй еще, еще!
Qui eut le triple talent,
De boire, de battre,
Et d'etre un vert galant…
[Имевший тройной талант,
пить, драться
и быть любезником…]
– A ведь тоже складно. Ну, ну, Залетаев!..
– Кю… – с усилием выговорил Залетаев. – Кью ю ю… – вытянул он, старательно оттопырив губы, – летриптала, де бу де ба и детравагала, – пропел он.
– Ай, важно! Вот так хранцуз! ой… го го го го! – Что ж, еще есть хочешь?
