Функция роста

Функция роста , также называемая коэффициентом разрушения или числом разрушения , измеряет богатство семейства множеств или класса функций. Она особенно используется в контексте статистической теории обучения , где она применяется для изучения свойств методов статистического обучения. Термин «функция роста» был придуман Вапником и Червоненкисом в их статье 1968 года, где они также доказали многие из ее свойств. ^[1] Это базовая концепция в машинном обучении . ^{[2] [3]}

Определения

Определение семейства наборов

Пусть — семейство множеств (множество множеств) и множество. Их пересечение определяется как следующее множество-семейство: ${\displaystyle H}$ ${\displaystyle C}$

${\displaystyle H\cap C:=\{h\cap C\mid h\in H\}}$

Размер пересечения (также называемый индексом ) относительно равен . Если множество содержит элементы, то индекс не превышает . Если индекс равен ровно 2 ^м , то говорят, что множество разбито , поскольку содержит все подмножества , то есть: ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle |H\cap C|}$ ${\displaystyle C_{m}}$ ${\displaystyle m}$ ${\displaystyle 2^{m}}$ ${\displaystyle C}$ ${\displaystyle H}$ ${\displaystyle H\cap C}$ ${\displaystyle C}$

${\displaystyle |H\cap C|=2^{|C|},}$

Функция роста измеряет размер как функцию от . Формально: ${\displaystyle H\cap C}$ ${\displaystyle |C|}$

${\displaystyle \operatorname {Growth} (H,m):=\max _{C:|C|=m}|H\cap C|}$

Определение класса гипотез

Эквивалентно, пусть будет классом гипотез (множеством бинарных функций) и множеством с элементами. Ограничение на — это множество бинарных функций на , которое может быть получено из : ^{[3] : 45} ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle H}$

${\displaystyle H_{C}:=\{(h(x_{1}),\ldots ,h(x_{m}))\mid h\in H,x_{i}\in C\}}$

Функция роста измеряет размер как функцию : ^{[3] : 49} ${\displaystyle H_{C}}$ ${\displaystyle |C|}$

${\displaystyle \operatorname {Growth} (H,m):=\max _{C:|C|=m}|H_{C}|}$

Примеры

1. Область определения — это вещественная прямая . Семейство множеств содержит все полупрямые (лучи) от заданного числа до положительной бесконечности, т. е. все множества вида для некоторого . Для любого множества вещественных чисел пересечение содержит множества: пустое множество, множество, содержащее наибольший элемент , множество, содержащее два наибольших элемента , и так далее. Следовательно: . ^{[1] : Пример 1} То же самое верно и для случая, когда содержит открытые полупрямые, закрытые полупрямые или и то, и другое. ${\displaystyle \mathbb {R} }$ ${\displaystyle H}$ ${\displaystyle \{x>x_{0}\mid x\in \mathbb {R} \}}$ ${\displaystyle x_{0}\in \mathbb {R} }$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle H\cap C}$ ${\displaystyle m+1}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle \operatorname {Growth} (H,m)=m+1}$ ${\displaystyle H}$

2. Область — это сегмент . Множество-семейство содержит все открытые множества. Для любого конечного множества действительных чисел пересечение содержит все возможные подмножества . Такие подмножества существуют , поэтому . ^{[1] : Пример 2} ${\displaystyle [0,1]}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle H\cap C}$ ${\displaystyle C}$ ${\displaystyle 2^{m}}$ ${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$

3. Область — это евклидово пространство . Множество-семейство содержит все полупространства вида: , где — фиксированный вектор. Тогда , где Comp — число компонент в разбиении n-мерного пространства m гиперплоскостями . ^{[1] : Пример 3} ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle H}$ ${\displaystyle x\cdot \phi \geq 1}$ ${\displaystyle \phi }$ ${\displaystyle \operatorname {Growth} (H,m)=\operatorname {Comp} (n,m)}$

4. Область определения — это вещественная линия . Семейство множеств содержит все вещественные интервалы, т. е. все множества вида для некоторого . Для любого множества вещественных чисел пересечение содержит все серии от 0 до последовательных элементов . Число таких серий равно , поэтому . ${\displaystyle \mathbb {R} }$ ${\displaystyle H}$ ${\displaystyle \{x\in [x_{0},x_{1}]|x\in \mathbb {R} \}}$ ${\displaystyle x_{0},x_{1}\in \mathbb {R} }$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle H\cap C}$ ${\displaystyle m}$ ${\displaystyle C}$ ${\displaystyle {m+1 \choose 2}+1}$ ${\displaystyle \operatorname {Growth} (H,m)={m+1 \choose 2}+1}$

Полиномиальный или экспоненциальный

Главное свойство, делающее функцию роста интересной, заключается в том, что она может быть либо полиномиальной, либо экспоненциальной — ничего промежуточного.

Следующее является свойством размера пересечения: ^{[1] : Лем.1}

• Если для некоторого набора размеров и для некоторого числа , - ${\displaystyle C_{m}}$ ${\displaystyle m}$ ${\displaystyle n\leq m}$ ${\displaystyle |H\cap C_{m}|\geq \operatorname {Comp} (n,m)}$
• тогда существует подмножество размера такое, что . ${\displaystyle C_{n}\subseteq C_{m}}$ ${\displaystyle n}$ ${\displaystyle |H\cap C_{n}|=2^{n}}$

Это подразумевает следующее свойство функции роста. ^{[1] : Th.1} Для каждого семейства возможны два случая: ${\displaystyle H}$

• Экспоненциальный случай : тождественно. ${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$
• Случай полинома : мажорируется по , где — наименьшее целое число, для которого . ${\displaystyle \operatorname {Growth} (H,m)}$ ${\displaystyle \operatorname {Comp} (n,m)\leq m^{n}+1}$ ${\displaystyle n}$ ${\displaystyle \operatorname {Growth} (H,n)<2^{n}}$

Другие свойства

Тривиальная верхняя граница

Для любого конечного : ${\displaystyle H}$

${\displaystyle \operatorname {Growth} (H,m)\leq |H|}$

поскольку для каждого число элементов в не более . Поэтому функция роста в основном интересна, когда бесконечна. ${\displaystyle C}$ ${\displaystyle H\cap C}$ ${\displaystyle |H|}$ ${\displaystyle H}$

Экспоненциальная верхняя граница

Для любого непустого : ${\displaystyle H}$

${\displaystyle \operatorname {Growth} (H,m)\leq 2^{m}}$

То есть функция роста имеет экспоненциальную верхнюю границу.

Мы говорим, что множество-семейство разбивает множество , если их пересечение содержит все возможные подмножества , т. е . Если разбивает множество размера , то , что является верхней границей. ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle H\cap C=2^{C}}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle \operatorname {Growth} (H,C)=2^{m}}$

Декартово пересечение

Определим декартово пересечение двух семейств множеств как:

${\displaystyle H_{1}\bigotimes H_{2}:=\{h_{1}\cap h_{2}\mid h_{1}\in H_{1},h_{2}\in H_{2}\}}$.

Тогда: ^{[2] : 57}

${\displaystyle \operatorname {Growth} (H_{1}\bigotimes H_{2},m)\leq \operatorname {Growth} (H_{1},m)\cdot \operatorname {Growth} (H_{2},m)}$

Союз

Для каждых двух семейств наборов: ^{[2] : 58}

${\displaystyle \operatorname {Growth} (H_{1}\cup H_{2},m)\leq \operatorname {Growth} (H_{1},m)+\operatorname {Growth} (H_{2},m)}$

Измерение ВК

Измерение VC определяется в соответствии со следующими двумя случаями: ${\displaystyle H}$

• В случае полинома = наибольшее целое число, для которого . ${\displaystyle \operatorname {VCDim} (H)=n-1}$ ${\displaystyle d}$ ${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$
• В экспоненциальном случае . ${\displaystyle \operatorname {VCDim} (H)=\infty }$

Так что если-и-только-если . ${\displaystyle \operatorname {VCDim} (H)\geq d}$ ${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$

Функцию роста можно рассматривать как уточнение концепции размерности VC. Размерность VC говорит нам только о том, равно ли или меньше , тогда как функция роста говорит нам, как именно изменяется в зависимости от . ${\displaystyle \operatorname {Growth} (H,d)}$ ${\displaystyle 2^{d}}$ ${\displaystyle \operatorname {Growth} (H,m)}$ ${\displaystyle m}$

Другая связь между функцией роста и размерностью VC задается леммой Зауэра–Шелаха : ^{[3] : 49}

Если , то: ${\displaystyle \operatorname {VCDim} (H)=d}$

для всех : ${\displaystyle m}$ ${\displaystyle \operatorname {Growth} (H,m)\leq \sum _{i=0}^{d}{m \choose i}}$

В частности,

для всех : ${\displaystyle m>d+1}$ ${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}=O(m^{d})}$

поэтому, когда размерность VC конечна, функция роста растет полиномиально с . ${\displaystyle m}$

Эта верхняя граница точна, т.е. для всех существует с размерностью VC такое, что: ^{[2] : 56} ${\displaystyle m>d}$ ${\displaystyle H}$ ${\displaystyle d}$

${\displaystyle \operatorname {Growth} (H,m)=\sum _{i=0}^{d}{m \choose i}}$

Энтропия

В то время как функция роста связана с максимальным размером пересечения, энтропия связана со средним размером пересечения: ^{[1] : 272–273}

${\displaystyle \operatorname {Entropy} (H,m)=E_{|C_{m}|=m}{\big [}\log _{2}(|H\cap C_{m}|){\big ]}}$

Размер пересечения имеет следующее свойство. Для каждого семейства множеств : ${\displaystyle H}$

${\displaystyle |H\cap (C_{1}\cup C_{2})|\leq |H\cap C_{1}|\cdot |H\cap C_{2}|}$

Следовательно:

${\displaystyle \operatorname {Entropy} (H,m_{1}+m_{2})\leq \operatorname {Entropy} (H,m_{1})+\operatorname {Entropy} (H,m_{2})}$

Более того, последовательность сходится к константе, когда . ${\displaystyle \operatorname {Entropy} (H,m)/m}$ ${\displaystyle c\in [0,1]}$ ${\displaystyle m\to \infty }$

Более того, случайная величина концентрируется вблизи . ${\displaystyle \log _{2}{|H\cap C_{m}|/m}}$ ${\displaystyle c}$

Приложения в теории вероятностей

Пусть будет множеством, на котором определена вероятностная мера . Пусть будет семейством подмножеств (= семейством событий). ${\displaystyle \Omega }$ ${\displaystyle \Pr }$ ${\displaystyle H}$ ${\displaystyle \Omega }$

Предположим, что мы выбираем набор , содержащий элементы , где каждый элемент выбирается случайным образом в соответствии с мерой вероятности , независимо от других (т.е. с заменами). Для каждого события мы сравниваем следующие две величины: ${\displaystyle C_{m}}$ ${\displaystyle m}$ ${\displaystyle \Omega }$ ${\displaystyle P}$ ${\displaystyle h\in H}$

• Его относительная частота в , т.е. ; ${\displaystyle C_{m}}$ ${\displaystyle |h\cap C_{m}|/m}$
• Его вероятность . ${\displaystyle \Pr[h]}$

Нас интересует разность, . Эта разность удовлетворяет следующей верхней границе: ${\displaystyle D(h,C_{m}):={\big |}|h\cap C_{m}|/m-\Pr[h]{\big |}}$

${\displaystyle \Pr \left[\forall h\in H:D(h,C_{m})\leq {\sqrt {8(\ln \operatorname {Growth} (H,2m)+\ln(4/\delta )) \over m}}\right]~~~~>~~~~1-\delta }$

что эквивалентно: ^{[1] : Th.2}

${\displaystyle \Pr {\big [}\forall h\in H:D(h,C_{m})\leq \varepsilon {\big ]}~~~~>~~~~1-4\cdot \operatorname {Growth} (H,2m)\cdot \exp(-\varepsilon ^{2}\cdot m/8)}$

Другими словами: вероятность того, что для всех событий в относительная частота близка к вероятности, ограничена снизу выражением, которое зависит от функции роста . ${\displaystyle H}$ ${\displaystyle H}$

Следствием этого является то, что если функция роста является полиномиальной по (т.е. существует такая , что ), то указанная выше вероятность стремится к 1 при . Т.е. семейство обладает равномерной сходимостью по вероятности . ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \operatorname {Growth} (H,m)\leq m^{n}+1}$ ${\displaystyle m\to \infty }$ ${\displaystyle H}$

Ссылки

1. Вапник, В. Н.; Червоненкис, А. Я. (1971). "О равномерной сходимости относительных частот событий к их вероятностям". Теория вероятностей и ее приложения . 16 (2): 264. doi :10.1137/1116025.Это английский перевод, сделанный Б. Секлером, русской статьи: "О равномерной сходимости относительных частот событий к их вероятностям". Докл. АН . 181 (4): 781. 1968.Перевод был воспроизведен как: Вапник, В. Н.; Червоненкис, А. Я. (2015). "О равномерной сходимости относительных частот событий к их вероятностям". Меры сложности . стр. 11. doi :10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
2. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258., особенно раздел 3.2
3. Шалев-Шварц, Шай; Бен-Дэвид, Шай (2014). Понимание машинного обучения – от теории к алгоритмам . Cambridge University Press. ISBN 9781107057135.