Сложность Радемахера

В теории вычислительного обучения ( машинное обучение и теория вычислений ) сложность Радемахера , названная в честь Ганса Радемахера , измеряет богатство класса множеств относительно распределения вероятностей . Эту концепцию также можно распространить на вещественнозначные функции.

Определения

Радемахеровская сложность множества

Учитывая набор $A\subseteq \mathbb {R} ^{m}$ , сложность Радемахера A определяется следующим образом: ^[1]^[2]^: 326

\operatorname {Rad} (A):={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{a\in A}\sum _{i=1}^{m}\sigma _{i}a_{i}\right]

где $\sigma _{1},\sigma _{2},\dots ,\sigma _{m}$ являются независимыми случайными величинами, полученными из распределения Радемахера , т.е. $\Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1)=1/2$ для $i=1,2,\dots ,m$ , и $a=(a_{1},\ldots ,a_{m})$ . Некоторые авторы принимают абсолютное значение суммы перед взятием супремума, но если $A$ симметричен , это не имеет значения.

Радемахеровская сложность функционального класса

Позволять $S=\{z_{1},z_{2},\dots ,z_{m}\}\subset Z$ быть выборкой точек и рассмотреть класс функции ${\mathcal {F}}$ действительных функций над $Z$ . Тогда Радемахера эмпирическая сложность ${\mathcal {F}}$ данный $S$ определяется как:

\operatorname {Rad} _{S}({\mathcal {F}})={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{f\in {\mathcal {F}}}\sum _{i=1}^{m}\sigma _{i}f(z_{i})\right]

Это также можно записать, используя предыдущее определение: ^[2]^: 326

\operatorname {Rad} _{S}({\mathcal {F}})=\operatorname {Rad} ({\mathcal {F}}\circ S)

где ${\mathcal {F}}\circ S$ обозначает композицию функции , т.е.:

{\mathcal {F}}\circ S:=\{(f(z_{1}),\ldots ,f(z_{m}))\mid f\in {\mathcal {F}}\}

Позволять $P$ быть распределением вероятностей по $Z$ . функционального Сложность Радемахера класса ${\mathcal {F}}$ относительно $P$ для размера выборки $m$ является:

\operatorname {Rad} _{P,m}({\mathcal {F}}):=\mathbb {E} _{S\sim P^{m}}\left[\operatorname {Rad} _{S}({\mathcal {F}})\right]

где вышеуказанное ожидание берется за одинаково независимо распределенную (iid) выборку $S=(z_{1},z_{2},\dots ,z_{m})$ созданный в соответствии с $P$ .

Интуиция

Сложность Радемахера обычно применяется к функциональному классу моделей, которые используются для классификации, с целью измерения их способности классифицировать точки, взятые из вероятностного пространства с произвольными обозначениями. Когда класс функций достаточно богат, он содержит функции, которые могут соответствующим образом адаптироваться к каждому расположению меток, моделируемому случайным отбором меток. $\sigma _{i}$ под ожиданием, так что это количество в сумме будет максимальным.

Примеры

1. $A$ содержит один вектор, например, $A=\{(a,b)\}\subset \mathbb {R} ^{2}$ . Затем:

\operatorname {Rad} (A)={1 \over 2}\cdot \left({1 \over 4}\cdot (a+b)+{1 \over 4}\cdot (a-b)+{1 \over 4}\cdot (-a+b)+{1 \over 4}\cdot (-a-b)\right)=0

То же самое верно для каждого класса одноэлементных гипотез. ^[3]^: 56

2. $A$ содержит два вектора, например, $A=\{(1,1),(1,2)\}\subset \mathbb {R} ^{2}$ . Затем:

{\begin{aligned}\operatorname {Rad} (A)&={1 \over 2}\cdot \left({1 \over 4}\cdot \max(1+1,1+2)+{1 \over 4}\cdot \max(1-1,1-2)+{1 \over 4}\cdot \max(-1+1,-1+2)+{1 \over 4}\cdot \max(-1-1,-1-2)\right)\\[5pt]&={1 \over 8}(3+0+1-2)={1 \over 4}\end{aligned}}

Использование сложности Радемахера

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

Ограничение репрезентативности

В машинном обучении желательно иметь обучающий набор , который представляет истинное распределение некоторых выборочных данных. $S$ . Это можно оценить количественно, используя понятие репрезентативности . Обозначим через $P$ распределение вероятностей, из которого взяты выборки. Обозначим через $H$ множество гипотез (потенциальных классификаторов) и обозначим через $F$ соответствующий набор функций ошибок, т. е. для каждой гипотезы $h\in H$ , есть функция $f_{h}\in F$ , который сопоставляет каждую обучающую выборку (признаки, метку) с ошибкой классификатора. $h$ (обратите внимание, что в этом случае гипотеза и классификатор используются как взаимозаменяемые). Например, в случае, когда $h$ представляет собой двоичный классификатор, функция ошибок представляет собой функцию потерь 0–1, т.е. функцию ошибок $f_{h}$ возвращает 0, если $h$ правильно классифицирует образец и еще 1. Опустим индекс и напишем $f$ вместо $f_{h}$ когда основная гипотеза не имеет значения. Определять:

L_{P}(f):=\mathbb {E} _{z\sim P}[f(z)]

– ожидаемая ошибка некоторой функции ошибок

f\in F

о реальном распределении

P

;

L_{S}(f):={1 \over m}\sum _{i=1}^{m}f(z_{i})

– предполагаемая ошибка некоторой функции ошибок

f\in F

по образцу

S

.

Репрезентативность выборки $S$ , относительно $P$ и $F$ , определяется как:

\operatorname {Rep} _{P}(F,S):=\sup _{f\in F}(L_{P}(f)-L_{S}(f))

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

Ожидаемая репрезентативность выборки может быть ограничена сверху сложностью Радемахера функционального класса: ^[2]^: 326

\mathbb {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}(F,S)]\leq 2\cdot \mathbb {E} _{S\sim P^{m}}[\operatorname {Rad} (F\circ S)]

Ограничение ошибки обобщения

Когда сложность Радемахера невелика, можно изучить класс гипотез H, используя эмпирическую минимизацию риска .

Например, (с функцией двоичной ошибки), ^[2]^: 328 для каждого $\delta >0$ , с вероятностью по крайней мере $1-\delta$ , для каждой гипотезы $h\in H$ :

L_{P}(h)-L_{S}(h)\leq 2\operatorname {Rad} (F\circ S)+4{\sqrt {2\ln(4/\delta ) \over m}}

Ограничение сложности Радемахера

Поскольку меньшая сложность Радемахера лучше, полезно иметь верхние границы сложности Радемахера различных наборов функций. Следующие правила можно использовать для верхней границы сложности Радемахера набора. $A\subset \mathbb {R} ^{m}$ . ^[2]^{: 329–330}

1. Если все векторы в $A$ переводятся постоянным вектором $a_{0}\in \mathbb {R} ^{m}$ , то Rad( A ) не изменится.

2. Если все векторы в $A$ умножаются на скаляр $c\in \mathbb {R}$ , то Rad( A ) умножается на $|c|$ .

3. $\operatorname {Rad} (A+B)=\operatorname {Rad} (A)+\operatorname {Rad} (B)$ . ^[3]^: 56

4. (Лемма Какаде и Тевари) Если все векторы в $A$ управляются функцией Липшица , то Rad( A ) (не более) умножается на константу Липшица функции. В частности, если все векторы из $A$ управляются сжимающим отображением , то Rad( A ) строго уменьшается.

5. Радемахеровская сложность выпуклой оболочки $A$ равно Рад( А ).

6. (Лемма Массара) Радемахеровская сложность конечного множества растет логарифмически с размером множества. Формально пусть $A$ быть набором $N$ векторы в $\mathbb {R} ^{m}$ , и пусть ${\bar {a}}$ быть средним значением векторов в $A$ . Затем:

\operatorname {Rad} (A)\leq \max _{a\in A}\|a-{\bar {a}}\|\cdot {{\sqrt {2\log N}} \over m}

В частности, если $A$ представляет собой набор бинарных векторов, норма не более ${\sqrt {m}}$ , так:

\operatorname {Rad} (A)\leq {\sqrt {2\log N \over m}}

Границы, связанные с измерением VC

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

для всех

m>d+1

:

\operatorname {Growth} (H,m)\leq (em/d)^{d}

Это означает, что для каждого набора $h$ с максимум $m$ элементы, $|H\cap h|\leq (em/d)^{d}$ . Семейство наборов $H\cap h$ можно рассматривать как набор двоичных векторов над $\mathbb {R} ^{m}$ . Подстановка этого в лемму Массара дает:

\operatorname {Rad} (H\cap h)\leq {\sqrt {2d\log(em/d) \over m}}

С помощью более продвинутых методов ( граница энтропии Дадли и верхняя граница Хаусслера ^[4]) можно показать, например, что существует константа $C$ , такой, что любой класс $\{0,1\}$ -индикаторные функции размерности Вапника–Червоненкиса $d$ имеет сложность Радемахера, ограниченную сверху $C{\sqrt {\frac {d}{m}}}$ .

Границы, связанные с линейными классами

Следующие оценки относятся к линейным операциям над $S$ – постоянный набор $m$ векторы в $\mathbb {R} ^{n}$ . ^[2]^{: 332–333}

1. Определить $A_{2}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{2}\leq 1\}=$ набор скалярных произведений векторов в $S$ с векторами в единичном шаре . Затем:

\operatorname {Rad} (A_{2})\leq {\max _{i}\|x_{i}\|_{2} \over {\sqrt {m}}}

2. Определить $A_{1}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{1}\leq 1\}=$ набор скалярных произведений векторов в $S$ с векторами в единичном шаре 1-нормы. Затем:

\operatorname {Rad} (A_{1})\leq \max _{i}\|x_{i}\|_{\infty }\cdot {\sqrt {2\log(2n) \over m}}

Границы, связанные с покрытием чисел

Следующая оценка связывает сложность Радемахера множества $A$ к его внешнему числу покрытия – количеству шаров данного радиуса $r$ чей союз содержит $A$ . Связка приписывается Дадли. ^[2]^: 338

Предполагать $A\subset \mathbb {R} ^{m}$ представляет собой набор векторов, длина (норма) которых не превосходит $c$ . Тогда для каждого целого числа $M>0$ :

\operatorname {Rad} (A)\leq {c\cdot 2^{-M} \over {\sqrt {m}}}+{6c \over m}\cdot \sum _{i=1}^{M}2^{-i}{\sqrt {\log \left(N_{c\cdot 2^{-i}}^{\text{ext}}(A)\right)}}

В частности, если $A$ лежит в d -мерном подпространстве $\mathbb {R} ^{m}$ , затем:

\forall r>0:N_{r}^{\text{ext}}(A)\leq (2c{\sqrt {d}}/r)^{d}

Подстановка этого значения в предыдущую оценку дает следующую оценку сложности Радемахера:

\operatorname {Rad} (A)\leq {6c \over m}\cdot {\bigg (}{\sqrt {d\log(2{\sqrt {d}})}}+2{\sqrt {d}}{\bigg )}=O{\bigg (}{c{\sqrt {d\log(d)}} \over m}{\bigg )}

Гауссова сложность

Гауссова сложность — это аналогичная сложность с аналогичным физическим смыслом, и ее можно получить из сложности Радемахера с использованием случайных величин. $g_{i}$ вместо $\sigma _{i}$ , где $g_{i}$ являются гауссовскими случайными величинами i.id с нулевым средним и дисперсией 1, т.е. $g_{i}\sim {\mathcal {N}}(0,1)$ . Известно, что сложности Гаусса и Радемахера эквивалентны с точностью до логарифмических множителей.

Эквивалентность Радемахера и Гауссовой сложности.

Учитывая набор $A\subseteq \mathbb {R} ^{n}$ тогда это справедливо ^[5]:
${\frac {G(A)}{2{\sqrt {\log {n}}}}}\leq {\text{Rad}}(A)\leq {\sqrt {\frac {\pi }{2}}}G(A)$
Где $G(A)$ — гауссова сложность A. В качестве примера рассмотрим радмахерову и гауссову сложности шара L1. Сложность Радемахера равна ровно 1, тогда как сложность по Гауссу порядка ${\sqrt {\log d}}$ (что можно показать, применив известные свойства супремумов набора субгауссовских случайных величин). ^[5]

Ссылки

^ Балкан, Мария-Флорина (15–17 ноября 2011 г.). «Теория машинного обучения – сложность Радемахера» (PDF) . Проверено 10 декабря 2016 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Глава 26 в Шалев-Шварц, Шай; Бен-Давид, Шай (2014). Понимание машинного обучения – от теории к алгоритмам . Издательство Кембриджского университета. ISBN 9781107057135 .
^ Jump up to: ^а ^б Мори, Мехриар ; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258 .
^ Буске, О. (2004). Введение в статистическую теорию обучения. Биологическая кибернетика , 3176 (1), 169–207. дои : 10.1007/978-3-540-28650-9_8
^ Jump up to: ^а ^б Уэйнрайт, Мартин (2019). Многомерная статистика: неасимптотическая точка зрения . Кембридж, Великобритания. стр. Упражнение 5.5. ISBN 978-1-108-62777-1 . OCLC 1089254580 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

Питер Л. Бартлетт, Шахар Мендельсон (2002) Радемахер и гауссовы сложности: границы риска и структурные результаты . Журнал исследований машинного обучения 3 463–482
Джорджио Ньекко, Марчелло Сангинети (2008) Границы ошибки аппроксимации через сложность Радемахера . Прикладные математические науки, Vol. 2, 2008, вып. 4, 153–176

[b11-1] Балкан, Мария-Флорина (15–17 ноября 2011 г.). «Теория машинного обучения – сложность Радемахера» (PDF) . Проверено 10 декабря 2016 г.

[book14-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Глава 26 в Шалев-Шварц, Шай; Бен-Давид, Шай (2014). Понимание машинного обучения – от теории к алгоритмам . Издательство Кембриджского университета. ISBN 9781107057135 .

[book12-3] Jump up to: ^а ^б Мори, Мехриар ; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258 .

[4] Буске, О. (2004). Введение в статистическую теорию обучения. Биологическая кибернетика , 3176 (1), 169–207. дои : 10.1007/978-3-540-28650-9_8

[:0-5] Jump up to: ^а ^б Уэйнрайт, Мартин (2019). Многомерная статистика: неасимптотическая точка зрения . Кембридж, Великобритания. стр. Упражнение 5.5. ISBN 978-1-108-62777-1 . OCLC 1089254580 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[1]

[2]

[3]

[4]

[5]