WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

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

Определение

Пусть задано множество и некоторое семейство индикаторных функций (алгоритмов классификации, решающих правил) , где  — аргумент функций,  — вектор параметров, задающий функцию. Каждая такая функция сопоставляет каждому элементу множества один из двух заданных классов. VC-размерностью семейства называется наибольшее число , такое, что существует подмножество из элементов множества , которые функции из могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого , то VC-размерность полагается равной бесконечности.

VC-размерность можно обобщить и на случай семейства функций , принимающих действительные значения. Его VC-размерность определяется как VC-размерность семейства индикаторных функций , где пробегает область значений функций .[1]

Примеры

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

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

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

См. также

Ссылки

Примечания

  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..

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии