Равномерная сходимость по вероятности - Uniform convergence in probability

Для использования в других целях см. равномерное схождение.

Равномерная сходимость по вероятности это форма сходимость по вероятности в статистическая асимптотическая теория и теория вероятности. Это означает, что при определенных условиях эмпирические частоты всех событий в определенной семье событий сходятся к своим теоретические вероятности. Равномерная сходимость по вероятности имеет приложения к статистика а также машинное обучение как часть теория статистического обучения.

В закон больших чисел говорит, что для каждого Один событие, его эмпирическая частота в последовательности независимых испытаний сходится (с большой вероятностью) к его теоретической вероятности. Но в некоторых приложениях нас интересует не одно событие, а целое. семейство событий. Мы хотели бы знать, сходится ли эмпирическая частота каждого события в семье к его теоретической вероятности. одновременно.^{[нужна цитата ]} Теорема о равномерной сходимости дает достаточное условие для этой сходимости. Грубо говоря, если семейство событий достаточно простое (его Размер ВК достаточно мало), то имеет место равномерная сходимость.

Определения

Для класса предикаты ${displaystyle H}$ определен на множестве ${displaystyle X}$ и набор образцов ${displaystyle x=(x_{1},x_{2},dots ,x_{m})}$, куда ${displaystyle x_{i}in X}$, то эмпирическая частота из ${displaystyle hin H}$ на ${displaystyle x}$ является

${displaystyle {widehat {Q}}_{x}(h)={frac {1}{m}}|{i:1leq ileq m,h(x_{i})=1}|.}$

В теоретическая вероятность из ${displaystyle hin H}$ определяется как ${displaystyle Q_{P}(h)=P{yin X:h(y)=1}.}$

Теорема о равномерной сходимости грубо утверждает, что если ${displaystyle H}$ "просто" и мы сами (с заменой) берем образцы из ${displaystyle X}$ по любому распределению ${displaystyle P}$, тогда с большой вероятностью, эмпирическая частота будет близка к своей ожидаемое значение, что является теоретической вероятностью.^{[нужна цитата ]}

Здесь «простой» означает, что Размерность Вапника – Червоненкиса класса ${displaystyle H}$ мала по сравнению с размером выборки. Другими словами, достаточно простой набор функций ведет себя примерно так же на небольшой случайной выборке, как и на распределении в целом.

Теорема о равномерной сходимости была впервые доказана Вапником и Червоненкисом.^[1] используя концепцию функция роста.

Теорема о равномерной сходимости

Утверждение теоремы о равномерной сходимости выглядит следующим образом:^[2]

Если ${displaystyle H}$ это набор ${displaystyle {0,1}}$-значные функции, определенные на множестве ${displaystyle X}$ и ${displaystyle P}$ это распределение вероятностей на ${displaystyle X}$ тогда для ${displaystyle varepsilon >0}$ и ${displaystyle m}$ положительное целое число, имеем:

${displaystyle P^{m}{|Q_{P}(h)-{widehat {Q_{x}}}(h)|geq varepsilon { ext{ for some }}hin H}leq 4Pi _{H}(2m)e^{-varepsilon ^{2}m/8}.}$

где для любого ${displaystyle xin X^{m},}$,

${displaystyle Q_{P}(h)=P{(yin X:h(y)=1},}$

${displaystyle {widehat {Q}}_{x}(h)={frac {1}{m}}|{i:1leq ileq m,h(x_{i})=1}|}$

и ${displaystyle |x|=m}$. ${displaystyle P^{m}}$ указывает, что вероятность взята за ${displaystyle x}$ состоящий из ${displaystyle m}$ i.i.d. извлекает из раздачи ${displaystyle P}$.

${displaystyle Pi _{H}}$ определяется как: Для любого ${displaystyle {0,1}}$-значные функции ${displaystyle H}$ над ${displaystyle X}$ и ${displaystyle Dsubseteq X}$,

${displaystyle Pi _{H}(D)={hcap D:hin H}.}$

И для любого натурального числа ${displaystyle m}$, то сокрушительное число ${displaystyle Pi _{H}(m)}$ определяется как:

${displaystyle Pi _{H}(m)=max |{hcap D:|D|=m,hin H}|.}$

С точки зрения теории обучения можно рассматривать ${displaystyle H}$ быть Концепция / Гипотеза класс, определенный в наборе экземпляров ${displaystyle X}$. Прежде чем переходить к деталям доказательства теоремы, сформулируем лемму Зауэра, которая нам понадобится в нашем доказательстве.

Лемма Зауэра – Шелаха.

В Лемма Зауэра – Шелаха.^[3] связывает сокрушительное число ${displaystyle Pi _{h}(m)}$ в VC Dimension.

Лемма: ${displaystyle Pi _{H}(m)leq left({frac {em}{d}}ight)^{d}}$, куда ${displaystyle d}$ это VC Dimension концептуального класса ${displaystyle H}$.

Следствие: ${displaystyle Pi _{H}(m)leq m^{d}}$.

Доказательство теоремы о равномерной сходимости

^[1] и ^[2] являются источниками доказательства ниже. Прежде чем мы перейдем к деталям доказательства Теорема о равномерной сходимости мы представим общий обзор доказательства.

1. Симметризация: Преобразуем проблему анализа ${displaystyle |Q_{P}(h)-{widehat {Q}}_{x}(h)|geq varepsilon }$ в проблему анализа ${displaystyle |{widehat {Q}}_{r}(h)-{widehat {Q}}_{s}(h)|geq varepsilon /2}$, куда ${displaystyle r}$ и ${displaystyle s}$ i.i.d образцы размера ${displaystyle m}$ составлен согласно распределению ${displaystyle P}$. Можно просмотреть ${displaystyle r}$ как исходный произвольно выбранный образец длины ${displaystyle m}$, пока ${displaystyle s}$ можно рассматривать как образец для испытаний, который используется для оценки ${displaystyle Q_{P}(h)}$.
2. Перестановка: С ${displaystyle r}$ и ${displaystyle s}$ выбираются одинаково и независимо, поэтому замена элементов между ними не изменит распределение вероятностей на ${displaystyle r}$ и ${displaystyle s}$. Итак, попробуем ограничить вероятность ${displaystyle |{widehat {Q}}_{r}(h)-{widehat {Q}}_{s}(h)|geq varepsilon /2}$ для некоторых ${displaystyle hin H}$ рассматривая эффект определенного набора перестановок объединенной выборки ${displaystyle x=r||s}$. В частности, мы рассматриваем перестановки ${displaystyle sigma (x)}$ которые обмениваются ${displaystyle x_{i}}$ и ${displaystyle x_{m+i}}$ в некотором подмножестве ${displaystyle {1,2,...,m}}$. Символ ${displaystyle r||s}$ означает конкатенацию ${displaystyle r}$ и ${displaystyle s}$.^{[нужна цитата ]}
3. Приведение к конечному классу: Теперь мы можем ограничить класс функций ${displaystyle H}$ к фиксированному образцу соединения и, следовательно, если ${displaystyle H}$ имеет конечную размерность VC, проблема сводится к задаче, связанной с конечным функциональным классом.

Приведем технические детали доказательства.

Симметризация

Лемма: Позволять ${displaystyle V={xin X^{m}:|Q_{P}(h)-{widehat {Q}}_{x}(h)|geq varepsilon { ext{ for some }}hin H}}$ и

${displaystyle R={(r,s)in X^{m} imes X^{m}:|{widehat {Q_{r}}}(h)-{widehat {Q}}_{s}(h)|geq varepsilon /2{ ext{ for some }}hin H}.}$

Тогда для ${displaystyle mgeq {frac {2}{varepsilon ^{2}}}}$, ${displaystyle P^{m}(V)leq 2P^{2m}(R)}$.

Доказательство: по неравенству треугольника
если ${displaystyle |Q_{P}(h)-{widehat {Q}}_{r}(h)|geq varepsilon }$ и ${displaystyle |Q_{P}(h)-{widehat {Q}}_{s}(h)|leq varepsilon /2}$ тогда ${displaystyle |{widehat {Q}}_{r}(h)-{widehat {Q}}_{s}(h)|geq varepsilon /2}$.

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

${displaystyle {egin{aligned}&P^{2m}(R)[5pt]geq {}&P^{2m}{exists hin H,|Q_{P}(h)-{widehat {Q}}_{r}(h)|geq varepsilon { ext{ and }}|Q_{P}(h)-{widehat {Q}}_{s}(h)|leq varepsilon /2}[5pt]={}&int _{V}P^{m}{s:exists hin H,|Q_{P}(h)-{widehat {Q}}_{r}(h)|geq varepsilon { ext{ and }}|Q_{P}(h)-{widehat {Q}}_{s}(h)|leq varepsilon /2},dP^{m}(r)[5pt]={}&Aend{aligned}}}$

поскольку ${displaystyle r}$ и ${displaystyle s}$ независимы.

Теперь для ${displaystyle rin V}$ исправить ${displaystyle hin H}$ такой, что ${displaystyle |Q_{P}(h)-{widehat {Q}}_{r}(h)|geq varepsilon }$. За это ${displaystyle h}$, мы покажем, что

${displaystyle P^{m}left{|Q_{P}(h)-{widehat {Q}}_{s}(h)|leq {frac {varepsilon }{2}}ight}geq {frac {1}{2}}.}$

Таким образом, для любого ${displaystyle rin V}$, ${displaystyle Ageq {frac {P^{m}(V)}{2}}}$ и поэтому ${displaystyle P^{2m}(R)geq {frac {P^{m}(V)}{2}}}$. И поэтому мы выполняем первый шаг нашей высокоуровневой идеи.

Уведомление, ${displaystyle mcdot {widehat {Q}}_{s}(h)}$ биномиальная случайная величина с математическим ожиданием ${displaystyle mcdot Q_{P}(h)}$ и дисперсия ${displaystyle mcdot Q_{P}(h)(1-Q_{P}(h))}$. К Неравенство Чебышева мы получили

${displaystyle P^{m}left{|Q_{P}(h)-{widehat {Q_{s}(h)}}|>{frac {varepsilon }{2}}ight}leq {frac {mcdot Q_{P}(h)(1-Q_{P}(h))}{(varepsilon m/2)^{2}}}leq {frac {1}{varepsilon ^{2}m}}leq {frac {1}{2}}}$

для упомянутой границы ${displaystyle m}$. Здесь мы используем тот факт, что ${displaystyle x(1-x)leq 1/4}$ за ${displaystyle x}$.

Перестановки

Позволять ${displaystyle Gamma _{m}}$ быть набором всех перестановок ${displaystyle {1,2,3,dots ,2m}}$ это меняет местами ${displaystyle i}$ и ${displaystyle m+i}$ ${displaystyle forall i}$ в некотором подмножестве ${displaystyle {1,2,3,ldots ,2m}}$.

Лемма: Позволять ${displaystyle R}$ быть любым подмножеством ${displaystyle X^{2m}}$ и ${displaystyle P}$ любое распределение вероятностей на ${displaystyle X}$. Потом,

${displaystyle P^{2m}(R)=E[Pr[sigma (x)in R]]leq max _{xin X^{2m}}(Pr[sigma (x)in R]),}$

где ожидание закончилось ${displaystyle x}$ выбран в соответствии с ${displaystyle P^{2m}}$, и вероятность больше ${displaystyle sigma }$ выбирается единообразно из ${displaystyle Gamma _{m}}$.

Доказательство: Для любого ${displaystyle sigma in Gamma _{m},}$

${displaystyle P^{2m}(R)=P^{2m}{x:sigma (x)in R}}$

(поскольку перестановки координат сохраняют распределение продукта ${displaystyle P^{2m}}$.)

${displaystyle {egin{aligned} herefore P^{2m}(R)={}&int _{X^{2m}}1_{R}(x),dP^{2m}(x)[5pt]={}&{frac {1}{|Gamma _{m}|}}sum _{sigma in Gamma _{m}}int _{X^{2m}}1_{R}(sigma (x)),dP^{2m}(x)[5pt]={}&int _{X^{2m}}{frac {1}{|Gamma _{m}|}}sum _{sigma in Gamma _{m}}1_{R}(sigma (x)),dP^{2m}(x)[5pt]&{ ext{(because }}|Gamma _{m}|{ ext{ is finite)}}[5pt]={}&int _{X^{2m}}Pr[sigma (x)in R],dP^{2m}(x)quad { ext{(the expectation)}}[5pt]leq {}&max _{xin X^{2m}}(Pr[sigma (x)in R]).end{aligned}}}$

Максимум гарантированно существует, поскольку существует только конечный набор значений, которые может принимать вероятность при случайной перестановке.

Приведение к конечному классу

Лемма: На основании предыдущей леммы

${displaystyle max _{xin X^{2m}}(Pr[sigma (x)in R])leq 4Pi _{H}(2m)e^{-varepsilon ^{2}m/8}}$.

Доказательство. Определим ${displaystyle x=(x_{1},x_{2},ldots ,x_{2m})}$ и ${displaystyle t=|H|_{x}|}$ что самое большее ${displaystyle Pi _{H}(2m)}$. Это означает, что есть функции ${displaystyle h_{1},h_{2},ldots ,h_{t}in H}$ такой, что для любого ${displaystyle hin H,exists i}$ между ${displaystyle 1}$ и ${displaystyle t}$ с ${displaystyle h_{i}(x_{k})=h(x_{k})}$ за ${displaystyle 1leq kleq 2m.}$

Мы видим, что ${displaystyle sigma (x)in R}$ если и только для некоторых ${displaystyle h}$ в ${displaystyle H}$ удовлетворяет,${displaystyle |{frac {1}{m}}|{1leq ileq m:h(x_{sigma _{i}})=1}|-{frac {1}{m}}|{m+1leq ileq 2m:h(x_{sigma _{i}})=1}||geq {frac {varepsilon }{2}}}$. Следовательно, если мы определим ${displaystyle w_{i}^{j}=1}$ если ${displaystyle h_{j}(x_{i})=1}$ и ${displaystyle w_{i}^{j}=0}$ иначе.

За ${displaystyle 1leq ileq m}$ и ${displaystyle 1leq jleq t}$у нас есть это ${displaystyle sigma (x)in R}$ если и только для некоторых ${displaystyle j}$ в ${displaystyle {1,ldots ,t}}$ удовлетворяет ${displaystyle |{frac {1}{m}}left(sum _{i}w_{sigma (i)}^{j}-sum _{i}w_{sigma (m+i)}^{j}ight)|geq {frac {varepsilon }{2}}}$. По объединению мы получаем

${displaystyle Pr[sigma (x)in R]leq tcdot max left(Pr[|{frac {1}{m}}left(sum _{i}w_{sigma _{i}}^{j}-sum _{i}w_{sigma _{m+i}}^{j}ight)|geq {frac {varepsilon }{2}}]ight)}$

${displaystyle leq Pi _{H}(2m)cdot max left(Pr left[left|{frac {1}{m}}left(sum _{i}w_{sigma _{i}}^{j}-sum _{i}w_{sigma _{m+i}}^{j}ight)ight|geq {frac {varepsilon }{2}}ight]ight).}$

Поскольку распределение по перестановкам ${displaystyle sigma }$ единообразно для каждого ${displaystyle i}$, так ${displaystyle w_{sigma _{i}}^{j}-w_{sigma _{m+i}}^{j}}$ равно ${displaystyle pm |w_{i}^{j}-w_{m+i}^{j}|}$, с равной вероятностью.

Таким образом,

${displaystyle Pr left[left|{frac {1}{m}}left(sum _{i}left(w_{sigma _{i}}^{j}-w_{sigma _{m+i}}^{j}ight)ight)ight|geq {frac {varepsilon }{2}}ight]=Pr left[left|{frac {1}{m}}left(sum _{i}|w_{i}^{j}-w_{m+i}^{j}|eta _{i}ight)ight|geq {frac {varepsilon }{2}}ight],}$

где вероятность справа больше ${displaystyle eta _{i}}$ и обе возможности одинаково вероятны. К Неравенство Хёффдинга, это самое большее ${displaystyle 2e^{-mvarepsilon ^{2}/8}}$.

Наконец, объединяя все три части доказательства, мы получаем Теорема о равномерной сходимости.

Рекомендации

1. Вапник, В. Н .; Червоненкис, А.Я. (1971). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятностей и ее приложения. 16 (2): 264. Дои:10.1137/1116025.Это английский перевод русской газеты Б. Секлера: «О равномерной сходимости относительных частот событий к их вероятностям». Докл. Акад. Наук. 181 (4): 781. 1968.Перевод был воспроизведен как:Вапник, В. Н .; Червоненкис, А.Я. (2015). «О равномерной сходимости относительных частот событий к их вероятностям». Меры сложности. п. 11. Дои:10.1007/978-3-319-21852-6_3. ISBN  978-3-319-21851-9.
2. Мартин Энтони Питер, л. Бартлетт. Обучение нейронной сети: теоретические основы, страницы 46–50. Первое издание, 1999. Cambridge University Press ISBN  0-521-57353-X
3. Шам Какаде и Амбудж Тевари, CMSC 35900 (весна 2008 г.) Теория обучения, лекция 11