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

Rademacher complexity

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

Определения

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

Учитывая набор , то Радемахера сложность А определяется следующим образом:[1][2]:326

куда независимые случайные величины, взятые из Распределение Радемахера т.е. за , и . Некоторые авторы берут абсолютное значение суммы перед супремумом, но если симметрично, это не имеет значения.

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

Учитывая образец , и класс вещественнозначных функций, определенных на доменном пространстве , то эмпирическая сложность Радемахера из данный определяется как:

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

куда обозначает функциональная композиция, то есть:

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

где вышеупомянутое ожидание взято за одинаково независимо распределены (i.i.d.) образец генерируется в соответствии с .

Примеры

1. содержит один вектор, например, . Потом:

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

2. содержит два вектора, например, . Потом:

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

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

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

В машинное обучение, желательно иметь Обучающий набор который представляет собой истинное распределение некоторых выборочных данных . Это можно количественно оценить, используя понятие представительность. Обозначим через то распределение вероятностей из которых взяты образцы. Обозначим через множество гипотез (потенциальных классификаторов) и обозначим через соответствующий набор функций ошибок, т.е.для каждой гипотезы , есть функция , который сопоставляет каждую обучающую выборку (функции, метку) с ошибкой классификатора (обратите внимание, что в этом случае гипотеза и классификатор используются как синонимы). Например, в случае, если представляет двоичный классификатор, функция ошибок - это функция потерь 0–1, т.е. функция ошибок возвращает 1, если правильно классифицирует образец и 0 остальное. Опускаем индекс и пишем вместо когда основная гипотеза неуместна. Определять:

- ожидаемая ошибка некоторой функции ошибок на реальном распределении ;
- оценочная ошибка некоторой функции ошибок по образцу .

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

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

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

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

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

Например, (с функцией двоичной ошибки),[2]:328 для каждого , с вероятностью не менее , для каждой гипотезы :

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

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

1. Если все векторы в переводятся на постоянный вектор , то Rad (А) не меняется.

2. Если все векторы в умножаются на скаляр , то Rad (А) умножается на .

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

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

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

6. (Лемма Массарта) Сложность Радемахера конечного множества логарифмически растет с размером множества. Формально пусть быть набором векторов в , и разреши быть средним векторов в . Потом:

В частности, если - набор двоичных векторов, норма не более , так:

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

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

для всех :

Это означает, что для каждого набора максимум с элементы . Набор-семья можно рассматривать как набор двоичных векторов над . Подстановка этого в лемму Массарта дает:

С более продвинутыми методами (Оценка энтропии Дадли и верхняя граница Хаусслера[4]) можно показать, например, что существует постоянная , так что любой класс -индикаторные функции с Размерность Вапника – Червоненкиса имеет сложность Радемахера, ограниченную сверху величиной .

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

Следующие оценки относятся к линейным операциям на - постоянный набор векторов в .[2]:332–333

1. Определите набор скалярных произведений векторов в с векторами в единичный мяч. Потом:

2. Определите набор скалярных произведений векторов в с векторами в единичном шаре 1-нормы. Потом:

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

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

Предполагать набор векторов, длина (норма) которых не превосходит . Тогда для каждого целого числа :

В частности, если лежит в d-мерное подпространство , тогда:

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

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

Гауссова сложность представляет собой аналогичную сложность с аналогичным физическим смыслом и может быть получена из сложности Радемахера с использованием случайных величин вместо , куда находятся Гауссовский i.i.d. случайные величины с нулевым средним и дисперсией 1, т.е. . Известно, что сложности Гаусса и Радемахера эквивалентны с точностью до логарифмических множителей.

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

  1. ^ Балкан, Мария-Флорина (15–17 ноября 2011 г.). "Теория машинного обучения - сложность Радемахера" (PDF). Получено 10 декабря 2016.
  2. ^ а б c d е ж грамм Глава 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