Давайте начнем с предыстории:
Компромисс между погрешностью и дисперсией.Методы с высокой дисперсией могут хорошо представлять обучающую выборку, но подвержены риску переобучения. Напротив, высокое смещение обычно приводит к более простым моделям, которые могут не соответствовать данным.
Точно так же большой компромисс заключается в том, что чем больше ваш класс гипотез, тем лучше лучшая гипотеза моделирует лежащую в основе истинную функцию, но тем сложнее найти эту лучшую гипотезу.
класс гипотез: он состоит из всех возможных гипотез, которые вы ищете, независимо от их формы.
В конечной гипотезе количество примеров для обеспечения вероятного приблизительно правильного (PAC) обучения равно логарифмическому размеру пространства гипотезы.
Владимир Вапник и Алексей Червоненкис написали статью, позволяющую оценить сложность выборки для бесконечных классов гипотез.
Что такое бесконечный класс гипотез?
Если мы возьмем два атрибута x1 и x2 на оси x-y и моя гипотеза будет прямой линией,
а если x1 и x2 являются действительными значениями, количество линейных функций может быть бесконечным. Например: это может быть круг, треугольник и т. д.
Идея «VCD» заключается в том, что размер класса гипотез является плохой мерой того, насколько «сложным» или насколько «выразительным» на самом деле является класс гипотез. В нем говорилось, что даже если пространство гипотез бесконечно, пока выборка конечна, мы можем знать, сколько выборок нам нужно.
Что такое разбиение наборов?
Пример: число классов =› (n) может быть помечено 2^n способами.
Если для каждой маркировки существует функция в пространстве гипотез, которая согласуется с маркировкой, то мы скажем, этот набор точек разбит пространством гипотез.
VC-размерность класса понятий «C» определяется как мощность наибольшего множества, которое может быть разбито «C». Если сколь угодно большие множества могут быть разбиты с помощью «C», то говорят, что VC-размерность + бесконечна.
Учитывая набор 'F' подмножеств множества {S}, мы говорим, что конечное подмножество {A} множества {S} разбито при условии, что каждое подмножество {B}, содержащееся в {A}, может быть записано как пересечение {A} с элементом 'F'.
Таким образом, множество {A} из трех точек общего положения на плоскости «S» разбивается набором полуплоскостей «F», но множество из четырех точек «A» на плоскости не разбивается набором полуплоскостей. коллекция 'F' полуплоскостей.
- Если существует хотя бы одно подмножество {X} размера d, которое можно разбить, то VCD ≥ d
- Если никакое подмножество размера «d» не может быть разбито, то VCD ‹ d
Чем больше подмножество {X}, которое можно разрушить, тем более выразительным (и менее предвзятым) является пространство гипотез.
Хорошо для чтения:
Теперь, когда мы знаем VCD, важно отметить, что примеры, достаточные для изучения PAC, определяются как:
VCD является гораздо лучшим индикатором способности моделей вписываться в произвольные данные, чем можно предположить по количеству параметров в моделях.
- По сравнению с конечной гипотезой => ln(H),
поскольку VC(H) ≤ ln(H), это может обеспечить более точную верхнюю границу количества примеров, необходимых для обучения PAC. .
Нижние границы VCD:
Рассмотрим класс понятий «C», такой что:
- VC(H) > 2,
- любой ученик L
- и любой 0‹эпсилон‹1/8,
- 0‹дельта‹1/100
Тогда существует распределение D и целевая концепция C, такие, что если L наблюдает меньше, чем:
примеров, то с вероятностью не менее дельты L выводит гипотезу с ошибкой больше эпсилон, т. е. мы не получаем приблизительную гипотезу.
LinkedIn: https://www.linkedin.com/in/vivekg-/
Ознакомьтесь с моим юридическим пространством здесь: https://easylaw.quora.com
