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

Мера сложности вещественных функций

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

Определения

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

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

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

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

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

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

${\displaystyle \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}

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

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

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

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

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

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

Интуиция

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

Примеры

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

${\displaystyle \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. содержит два вектора, например, . Затем: ${\displaystyle A}$ ${\displaystyle A=\{(1,1),(1,2)\}\subset \mathbb {R} ^{2}}$

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle L_{P}(f):=\mathbb {E} _{z\sim P}[f(z)]}$– ожидаемая ошибка некоторой функции ошибок реального распределения ; ${\displaystyle f\in F}$ ${\displaystyle P}$

${\displaystyle L_{S}(f):={1 \over m}\sum _{i=1}^{m}f(z_{i})}$– предполагаемая ошибка некоторой функции ошибок на выборке . ${\displaystyle f\in F}$ ${\displaystyle S}$

Репрезентативность выборки по отношению к и определяется как: ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle F}$

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

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

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

$${\displaystyle \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} для каждого , с вероятностью не менее , для каждой гипотезы : ${\displaystyle \delta >0}$ ${\displaystyle 1-\delta }$ ${\displaystyle h\in H}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть — семейство множеств , размерность VC которого равна . Известно, что функция роста ограничена следующим образом: ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle H}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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)}}}$

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

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

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

${\displaystyle \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 )}}$

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

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

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

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

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

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

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