Равномерная сходимость по вероятности - 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 {(инь 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} (м)}$ определяется как:

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

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

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

В Лемма Зауэра – Шелаха.^[3] связывает сокрушительное число ${displaystyle Pi _ {h} (м)}$ в 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 {для некоторых}} hin H}}$ и

${displaystyle R = {(r, s) в X ^ {m} imes X ^ {m}: | {widehat {Q_ {r}}} (h) - {widehat {Q}} _ {s} (h) | geq varepsilon / 2 {ext {для некоторых}} 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 {align} & P ^ {2m} (R) [5pt] geq {} & P ^ {2m} {существует 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: существует 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 {выровнено}}}$

поскольку ${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 {выравнивается} здесь 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 {(потому что}} | Gamma _ {m} | {ext {конечно)}} [5pt] = { } & int _ {X ^ {2m}} Pr [сигма (x) в R], dP ^ {2m} (x) quad {ext {(ожидание)}} [5pt] leq {} & max _ {xin X ^ {2m}} (Pr [сигма (x) в R]). Конец {выровнен}}}$

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

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

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

${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} (2 м)}$. Это означает, что есть функции ${displaystyle h_ {1}, h_ {2}, ldots, h_ {t} в H}$ такой, что для любого ${displaystyle hin H, существует 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 {гидроразрыв {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 (сумма _ {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}}$.

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

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