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

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

Определения

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

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

${displaystyle operatorname {Rad} (A):={frac {1}{m}}operatorname {E} left[sup _{ain A}sum _{i=1}^{m}sigma _{i}a_{i}ight]}$

куда ${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})in Z^{m}}$, и класс ${displaystyle F}$ вещественнозначных функций, определенных на доменном пространстве ${displaystyle Z}$, то эмпирическая сложность Радемахера из ${displaystyle F}$ данный ${displaystyle S}$ определяется как:

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

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

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

куда ${displaystyle Fcirc S}$ обозначает функциональная композиция, то есть:

${displaystyle Fcirc S:={(f(z_{1}),ldots ,f(z_{m}))mid fin F}}$

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

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

где вышеупомянутое ожидание взято за одинаково независимо распределены (i.i.d.) образец ${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 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)ight)=0}$

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

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

${displaystyle {egin{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)ight)[5pt]&={1 over 8}(3+0+1-2)={1 over 4}end{aligned}}}$

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

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

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

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

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

${displaystyle L_{S}(f):={1 over m}sum _{i=1}^{m}f(z_{i})}$ - оценочная ошибка некоторой функции ошибок ${displaystyle fin F}$ по образцу ${displaystyle S}$.

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

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

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

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

$${displaystyle operatorname {E} _{Ssim P^{m}}[operatorname {Rep} _{P}(F,S)]leq 2cdot operatorname {E} _{Ssim P^{m}}[operatorname {Rad} (Fcirc S)]}$$

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

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

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

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

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

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

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

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

3. Рад (А + B) = Рад (А) + Рад (B).^[3]:56

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

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

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

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

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

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

Границы, относящиеся к размерности ВК

Позволять ${displaystyle H}$ быть установить семью чей Размер ВК является ${displaystyle d}$. Известно, что функция роста из ${displaystyle H}$ ограничено как:

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

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

${displaystyle operatorname {Rad} (Hcap h)leq {sqrt {2dlog(em/d) over m}}}$

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

Границы, относящиеся к линейным классам

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle operatorname {Rad} (A)leq {6c over m}cdot {igg (}{sqrt {dlog(2{sqrt {d}})}}+2{sqrt {d}}{igg )}=O{igg (}{c{sqrt {dlog(d)}} over m}{igg )}}$

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

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

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

1. Балкан, Мария-Флорина (15–17 ноября 2011 г.). "Теория машинного обучения - сложность Радемахера" (PDF). Получено 10 декабря 2016.
2. Глава 26 в Шалев-Шварц, Шай; Бен-Давид, Шай (2014). Понимание машинного обучения - от теории к алгоритмам. Издательство Кембриджского университета. ISBN  9781107057135.
3. Мохри, Мехриар; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения. США, Массачусетс: MIT Press. ISBN  9780262018258.
4. Буске, О. (2004). Введение в статистическую теорию обучения. Биологическая кибернетика, 3176(1), 169–207. http://doi.org/10.1007/978-3-540-28650-9_8

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