Образец сложность из машинного обучения алгоритма представляет собой количество тренинга-образцы , которые нужны для того , чтобы успешно изучить целевую функцию.
Точнее, сложность выборки - это количество обучающих выборок, которые нам нужно предоставить алгоритму, чтобы функция, возвращаемая алгоритмом, находилась в пределах произвольно малой ошибки наилучшей возможной функции с вероятностью, произвольно близкой к 1.
Возможны два варианта сложности выборки:
- Слабый вариант фиксирует определенное распределение ввода-вывода;
- Сильный вариант принимает сложность выборки наихудшего случая по всем распределениям ввода-вывода.
Теорема об отсутствии бесплатного обеда, обсуждаемая ниже, доказывает, что в общем случае сильная сложность выборки бесконечна, то есть не существует алгоритма, который мог бы изучить глобально оптимальную целевую функцию с использованием конечного числа обучающих выборок.
Однако, если нас интересует только конкретный класс целевых функций (например, только линейные функции), то сложность выборки конечна и линейно зависит от размерности VC в классе целевых функций. [1]
Определение
Позволять быть пространством, которое мы называем входным пространством, и - пространство, которое мы называем выходным пространством, и пусть обозначить продукт . Например, при настройке двоичной классификации обычно является конечномерным векторным пространством и это набор .
Исправьте пространство гипотез функций . Алгоритм обучения окончен вычислимая карта из к . Другими словами, это алгоритм, который принимает на вход конечную последовательность обучающих выборок и выводит функцию из к . Типичные алгоритмы обучения включают минимизацию эмпирического риска без или с регуляризацией Тихонова .
Исправить функцию потерь , например, квадрат потерь , где . Для данного распределения на , ожидаемый риск гипотезы (функция) является
В нашей обстановке у нас есть , где алгоритм обучения и представляет собой последовательность векторов, которые нарисованы независимо от . Определите оптимальный риск
Другими словами, сложность выборки определяет степень согласованности алгоритма: при заданной точности и уверенность , нужно пробовать точки данных, чтобы гарантировать, что риск выходной функции находится в пределах наилучшего из возможных, с вероятностью не менее . [2]
При вероятном приблизительно правильном обучении (PAC) каждый заинтересован в том, является ли сложность выборки полиномиальной , т.е. ограничен полиномом от а также . Если является полиномом для некоторого алгоритма обучения, то говорят, что пространство гипотез можно изучить с помощью PAC . Обратите внимание, что это более сильное понятие, чем возможность научиться.
Неограниченное пространство гипотез: бесконечная сложность выборки
Можно спросить, существует ли алгоритм обучения, чтобы сложность выборки была конечной в строгом смысле, то есть существует ограничение на количество необходимых выборок, чтобы алгоритм мог изучить любое распределение по пространству ввода-вывода с помощью указанная целевая ошибка. Более формально спрашивают, существует ли алгоритм обучения, так что для всех , существует натуральное число такое, что для всех , у нас есть
Таким образом, чтобы сделать заявления о скорости сходимости величины
- ограничить пространство вероятностных распределений , например, с помощью параметрического подхода, или
- ограничить пространство гипотез , как и в подходах без распространения.
Ограниченное пространство гипотез: конечная сложность выборки
Последний подход приводит к таким концепциям, как размерность VC и сложность Радемахера, которые контролируют сложность пространства.. Меньшее пространство гипотез вносит больше предвзятости в процесс вывода, а это означает, чтоможет быть больше, чем максимально возможный риск в большем пространстве. Однако, ограничивая сложность пространства гипотез, алгоритм может создавать более единообразно согласованные функции. Этот компромисс приводит к концепции регуляризации . [2]
Теорема из теории VC состоит в том, что следующие три утверждения эквивалентны для пространства гипотез:
- можно изучить с помощью PAC.
- Размер венчурного капитала конечно.
- является равномерным классом Гливенко-Кантелли .
Это дает возможность доказать, что определенные пространства гипотез могут быть изучены с помощью PAC и, соответственно, могут быть изучены.
Пример пространства гипотез, изучаемого с помощью PAC
, и разреши - пространство аффинных функций на , то есть функции вида для некоторых . Это линейная классификация со смещенной задачей обучения. Теперь обратите внимание, что четыре компланарные точки в квадрате не могут быть разрушены какой-либо аффинной функцией, поскольку никакая аффинная функция не может быть положительной на двух диагонально противоположных вершинах и отрицательной на оставшихся двух. Таким образом, размер VC является , так что конечно. Из приведенной выше характеристики классов, изучаемых с помощью PAC, следует, что является PAC-обучаемым, и, соответственно, обучаемым.
Границы сложности выборки
Предполагать это класс бинарных функций (функций для ). Потом, является -PAC-обучаемый с выборкой размера: [3]
Предполагать является классом функций с действительными значениями с диапазоном значений в . Потом, является -PAC-обучаемый с выборкой размера: [5] [6]
Другие настройки
В дополнении к обучению под наблюдение настройки, образец сложность имеет отношение к полу под наблюдением обучения проблемы , в том числе активного обучения , [7] , где алгоритм может задать для меток специально выбранных входы для того , чтобы снизить затраты на получение много ярлыков. Концепция сложности выборки также проявляется в обучении с подкреплением , [8] онлайн-обучении и неконтролируемых алгоритмах, например, для изучения словаря . [9]
Эффективность в робототехнике
Высокая сложность выборки означает, что для выполнения поиска по дереву Монте-Карло требуется много вычислений . [10] Это равносильно модельному поиску методом грубой силы в пространстве состояний. Напротив, высокоэффективный алгоритм имеет низкую сложность выборки. [11] Возможные методы уменьшения сложности выборки - это метрическое обучение [12] и обучение с подкреплением на основе моделей. [13]
Рекомендации
- ^ a b Вапник, Владимир (1998), Статистическая теория обучения , Нью-Йорк: Wiley.
- ^ а б Росаско, Лоренцо (2014), Последовательность, обучаемость и регуляризация , Лекционные заметки для курса MIT 9.520.
- ^ Стив Ханнеке (2016). «Оптимальная выборочная сложность обучения PAC» . J. Mach. Учить. Res . 17 (1): 1319–1333.
- ^ Эренфойхт, Анджей; Хаусслер, Дэвид; Кирнс, Майкл; Валиант, Лесли (1989). «Общая нижняя граница количества примеров, необходимых для обучения». Информация и вычисления . 82 (3): 247. DOI : 10.1016 / 0890-5401 (89) 90002-3 .
- ^ Энтони, Мартин; Бартлетт, Питер Л. (2009). Обучение нейронной сети: теоретические основы . ISBN 9780521118620.
- ^ Моргенштерн, Джейми; Roughgarden, Тим (2015). О псевдоразмерности аукционов, близких к оптимальным . НИПС. Curran Associates. С. 136–144. arXiv : 1506.03684 .
- ^ Балкан, Мария-Флорина ; Ханнеке, Стив; Вортман Воган, Дженнифер (2010). «Настоящая примерная сложность активного обучения» . Машинное обучение . 80 (2–3): 111–139. DOI : 10.1007 / s10994-010-5174-у .
- ^ Какаде, Шам (2003), О типовой сложности обучения с подкреплением (PDF) , докторская диссертация, Университетский колледж Лондона: Gatsby Computational Neuroscience Unit.
- ^ Вайнсенчер, Даниил; Маннор, Ши; Брукштейн, Альфред (2011). «Примерная сложность изучения словаря» (PDF) . Журнал исследований в области машинного обучения . 12 : 3259–3281.
- ^ Кауфманн, Эмили и Кулен, Воутер М (2017). Поиск в дереве Монте-Карло по идентификации лучшей руки . Достижения в системах обработки нейронной информации. С. 4897–4906.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Фидельман, Пегги и Стоун, Питер (2006). Щипок за подбородок: пример обучения навыкам на роботах с ногами . Чемпионат мира по футболу среди роботов. Springer. С. 59–71.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Верма, Накул и Брэнсон, Кристин (2015). Примерная сложность изучения дистанционных метрик Махаланобиса . Достижения в области нейронных систем обработки информации. С. 2584–2592.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Курутах, Танард и Клавера, Игнаси и Дуан, Ян и Тамар, Авив и Аббель, Питер (2018). «Оптимизация политики доверительного региона модели-ансамбля». arXiv : 1802.10592 [ cs.LG ].CS1 maint: несколько имен: список авторов ( ссылка )