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

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

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

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

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

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

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

${\displaystyle \operatorname {Рост} (H,m):=\max _{C:|C|=m}|H\cap C|}$

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

${\displaystyle \operatorname {Рост} (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 С}$${\displaystyle м}$${\displaystyle H\cap C}$${\displaystyle м+1}$${\displaystyle С}$${\displaystyle С}$${\displaystyle \operatorname {Рост} (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}$