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

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

Определения

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

Позволять $H$ быть семейством множеств (набором множеств) и $C$ набор. Их пересечение определяется как следующее семейство множеств:

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

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

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

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

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

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

Эквивалентно, пусть $H$ быть классом гипотез (набором бинарных функций) и $C$ набор с $m$ элементы. Ограничение ​ ​ $H$ к $C$ представляет собой набор бинарных функций на $C$ которое может быть получено из $H$:

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

Функция роста измеряет размер $H_{C}$ как функция $|C|$:

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

Примеры

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

2. Домен – это сегмент $[0,1]$. Семейство наборов $H$ содержит все открытые множества. Для любого конечного множества $C$ из $m$ действительные числа, пересечение $H\cap C$ содержит все возможные подмножества $C$. Есть $2^{m}$ такие подмножества, поэтому $\operatorname {Growth} (H,m)=2^{m}$.

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

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

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

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

Следующее является свойством размера пересечения:

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

Отсюда следует следующее свойство функции роста. Для каждой семьи $H$ есть два случая:

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

Другие объекты недвижимости

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

Для любого конечного $H$:

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

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

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

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

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

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

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

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

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

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

Затем:

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

Союз

Для каждых двух множеств-семейств:

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

Размер венчурного капитала

Размер венчурного капитала $H$ определяется в соответствии с этими двумя случаями:

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

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

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

Еще одну связь между функцией роста и размерностью VC дает лемма Зауэра – Шела :

Если $\operatorname {VCDim} (H)=d$, затем:

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

В частности,

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

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

Эта верхняя граница точная, т.е. для всех $m>d$ существует $H$ с размером ВК $d$ такой, что:

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

Энтропия

Хотя функция роста связана с максимальным размером пересечения,энтропия средним связана со размером пересечения :

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

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

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

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

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

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

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

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

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

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

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

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

$\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$

что эквивалентно:

$\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)$

Прописью: вероятность того, что для всех событий в $H$, относительная частота близка к вероятности, ограничена снизу выражением, которое зависит от функции роста $H$.

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