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

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

Определения [ править ]

Радемахерская сложность набора [ править ]

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

${\ displaystyle \ operatorname {Rad} (A): = {\ frac {1} {m}} \ operatorname {E} \ 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 я = 1,2, \ точки, м}$${\displaystyle a=(a_{1},\ldots ,a_{m})}$${\displaystyle A}$

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

Учитывая образец , и класс вещественных функций , определенных на области пространства , где есть функция потерь из классификатора , то эмпирическая Радемахер сложность в данный определяются как:${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})\in Z^{m}}$${\displaystyle F}$${\displaystyle Z}$${\displaystyle f}$${\displaystyle f(z)=\ell (h(x),y)}$${\displaystyle h}$${\displaystyle F}$${\displaystyle S}$

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

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

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

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

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

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

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

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

Примеры [ править ]

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

${\displaystyle \operatorname {Rad} (A)={1 \over 1}\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}}}$

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

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

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

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

${\displaystyle L_{P}(f):=\operatorname {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 \operatorname {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}(F,S)]\leq 2\cdot \operatorname {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}

4. (Лемма Какаде и Тевари) Если все векторы в управляются липшицевой функцией , то Rad ( A ) умножается (не более чем) на константу Липшица функции. В частности, если все векторы in управляются сжимающим отображением , то 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}}$

Это означает , что для любого набора с в большинстве элементов . Семейство наборов можно рассматривать как набор двоичных векторов над . Подстановка этого в лемму Массарта дает:${\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. Определите набор скалярных произведений векторов в с векторами в единичном шаре 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)}$

Эквивалентность Радемахера и гауссовой сложности [ править ]

Для данного набора выполняется следующее: Где гауссовская сложность A?${\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)}$

Ссылки [ править ]

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