Сложность образца - Sample complexity

Часть серии по
Машинное обучение и сбор данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Разработка функций Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Контролируемое обучение (классификация • регресс) Деревья решений Ансамбли Упаковка Повышение Случайный лес k-NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k-средства Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k-NN Фактор локального выброса
Искусственная нейронная сеть Автоэнкодер Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Дилемма смещения – дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Схема машинного обучения

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

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

Возможны два варианта сложности выборки:

• Слабый вариант фиксирует определенное распределение ввода-вывода;
• Сильный вариант принимает сложность выборки наихудшего случая по всем распределениям ввода-вывода.

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

Однако, если нас интересует только определенный класс целевых функций (например, только линейные функции), тогда сложность выборки конечна и линейно зависит от Размер ВК по классу целевых функций.^[1]

Определение

Позволять ${ displaystyle X}$ быть пространством, которое мы называем входным пространством, и ${ displaystyle Y}$ - пространство, которое мы называем выходным пространством, и пусть ${ displaystyle Z}$ обозначить продукт ${ Displaystyle X раз Y}$. Например, при настройке двоичной классификации ${ displaystyle X}$ обычно является конечномерным векторным пространством и ${ displaystyle Y}$ это набор ${ displaystyle {- 1,1 }}$.

Исправьте пространство гипотез ${ displaystyle { mathcal {H}}}$ функций ${ displaystyle h двоеточие от X до Y}$. Алгоритм обучения окончен ${ displaystyle { mathcal {H}}}$ вычислимая карта из ${ displaystyle Z ^ {*}}$ к ${ displaystyle { mathcal {H}}}$. Другими словами, это алгоритм, который принимает на вход конечную последовательность обучающих выборок и выводит функцию из ${ displaystyle X}$ к ${ displaystyle Y}$. Типичные алгоритмы обучения включают: минимизация эмпирического риска, без или с Тихоновская регуляризация.

Исправить функцию потерь ${ displaystyle { mathcal {L}} двоеточие Y times Y to mathbb {R} _ { geq 0}}$, например, квадрат потерь ${ Displaystyle { mathcal {L}} (у, у ') = (у-у') ^ {2}}$, куда ${ Displaystyle ч (х) = у '}$. Для данного распределения ${ displaystyle rho}$ на ${ Displaystyle X раз Y}$, то ожидаемый риск гипотезы (функции) ${ displaystyle h in { mathcal {H}}}$ является

${ Displaystyle { mathcal {E}} (h): = mathbb {E} _ { rho} [{ mathcal {L}} (h (x), y)] = int _ {X times Y} { mathcal {L}} (h (x), y) , d rho (x, y)}$

В нашей обстановке у нас есть ${ displaystyle h = { mathcal {A}} (S_ {n})}$, куда ${ displaystyle { mathcal {A}}}$ алгоритм обучения и ${ Displaystyle S_ {n} = ((x_ {1}, y_ {1}), ldots, (x_ {n}, y_ {n})) sim rho ^ {n}}$ представляет собой последовательность векторов, которые нарисованы независимо от ${ displaystyle rho}$. Определите оптимальный риск

Набор ${ displaystyle h_ {n} = { mathcal {A}} (S_ {n})}$, для каждого ${ displaystyle n}$. Обратите внимание, что ${ displaystyle h_ {n}}$ это случайная переменная и зависит от случайной величины ${ displaystyle S_ {n}}$, взятый из распределения ${ displaystyle rho ^ {n}}$. Алгоритм ${ displaystyle { mathcal {A}}}$ называется последовательный если ${ Displaystyle { mathcal {E}} (ч_ {п})}$ вероятностно сходится к ${ Displaystyle { mathcal {E}} _ { mathcal {H}} ^ {*}}$. Другими словами, для всех ${ displaystyle epsilon, delta> 0}$, существует натуральное число ${ displaystyle N}$, так что для всех ${ Displaystyle п geq N}$, у нас есть

В сложность образца из ${ displaystyle { mathcal {A}}}$ тогда минимальный ${ displaystyle N}$ для которого это верно, как функция ${ displaystyle rho, epsilon}$, и ${ displaystyle delta}$. Запишем сложность образца как ${ Displaystyle N ( rho, epsilon, delta)}$ чтобы подчеркнуть, что это значение ${ displaystyle N}$ зависит от ${ displaystyle rho, epsilon}$, и ${ displaystyle delta}$. Если ${ displaystyle { mathcal {A}}}$ является не соответствует, то положим ${ Displaystyle N ( rho, epsilon, delta) = infty}$. Если существует алгоритм, для которого ${ Displaystyle N ( rho, epsilon, delta)}$ конечно, то мы говорим, что пространство гипотез ${ displaystyle { mathcal {H}}}$ является обучаемый.

Другими словами, сложность выборки ${ Displaystyle N ( rho, epsilon, delta)}$ определяет степень согласованности алгоритма: при заданной точности ${ displaystyle epsilon}$ и уверенность ${ displaystyle delta}$, нужно пробовать ${ Displaystyle N ( rho, epsilon, delta)}$ точки данных, чтобы гарантировать, что риск выходной функции находится в пределах ${ displaystyle epsilon}$ наилучшего из возможных, с вероятностью не менее ${ displaystyle 1- delta}$ .^[2]

В возможно приблизительно правильное (PAC) обучение, возникает вопрос, является ли сложность выборки многочлен, то есть ${ Displaystyle N ( rho, epsilon, delta)}$ ограничен полиномом от ${ displaystyle 1 / epsilon}$ и ${ displaystyle 1 / delta}$. Если ${ Displaystyle N ( rho, epsilon, delta)}$ является полиномом для некоторого алгоритма обучения, то говорят, что пространство гипотез ${ displaystyle { mathcal {H}}}$ является PAC-обучаемый. Учтите, что это более сильное понятие, чем возможность научиться.

Неограниченное пространство гипотез: бесконечная сложность выборки

Можно спросить, существует ли алгоритм обучения, в котором сложность выборки конечна в строгом смысле, то есть существует ограничение на количество необходимых выборок, чтобы алгоритм мог изучить любое распределение в пространстве ввода-вывода с помощью указанная целевая ошибка. Более формально спрашивают, существует ли алгоритм обучения ${ displaystyle { mathcal {A}}}$, так что для всех ${ displaystyle epsilon, delta> 0}$, существует натуральное число ${ displaystyle N}$ такой, что для всех ${ Displaystyle п geq N}$, у нас есть

куда ${ displaystyle h_ {n} = { mathcal {A}} (S_ {n})}$, с ${ Displaystyle S_ {n} = ((x_ {1}, y_ {1}), ldots, (x_ {n}, y_ {n})) sim rho ^ {n}}$ как указано выше. В Теорема об отсутствии бесплатного обеда говорит, что без ограничений на пространство гипотез ${ displaystyle { mathcal {H}}}$, это не так, т.е. всегда существуют «плохие» распределения, для которых сложность выборки сколь угодно велика.^[1]

Таким образом, чтобы сделать заявления о скорости сходимости величины

нужно либо

• ограничить пространство вероятностных распределений ${ displaystyle rho}$, например с помощью параметрического подхода, или
• ограничить пространство гипотез ${ displaystyle { mathcal {H}}}$, как и в подходах без распространения.

Ограниченное пространство гипотез: конечная сложность выборки

Последний подход приводит к таким концепциям, как Размер ВК и Радемахерская сложность которые контролируют сложность пространства ${ displaystyle { mathcal {H}}}$. Меньшее пространство гипотез вносит больше предвзятости в процесс вывода, а это означает, что ${ Displaystyle { mathcal {E}} _ { mathcal {H}} ^ {*}}$ может быть больше, чем максимально возможный риск в большем пространстве. Однако, ограничивая сложность пространства гипотез, алгоритм может создавать более единообразно согласованные функции. Этот компромисс приводит к концепции регуляризация.^[2]

Это теорема из Теория ВК что следующие три утверждения эквивалентны для пространства гипотез ${ displaystyle { mathcal {H}}}$:

1. ${ displaystyle { mathcal {H}}}$ можно изучить с помощью PAC.
2. Размер VC ${ displaystyle { mathcal {H}}}$ конечно.
3. ${ displaystyle { mathcal {H}}}$ униформа Класс Гливенко-Кантелли.

Это дает возможность доказать, что определенные пространства гипотез можно выучить с помощью PAC и, соответственно, изучить.

Пример пространства гипотез, изучаемого с помощью PAC

${ Displaystyle X = mathbb {R} ^ {d}, Y = {- 1,1 }}$, и разреши ${ displaystyle { mathcal {H}}}$ - пространство аффинных функций на ${ displaystyle X}$, то есть функции вида ${ Displaystyle х mapsto langle w, x rangle + b}$ для некоторых ${ displaystyle w in mathbb {R} ^ {d}, b in mathbb {R}}$. Это линейная классификация со смещенной задачей обучения. Теперь обратите внимание, что четыре компланарные точки квадрата не могут быть разрушены какой-либо аффинной функцией, поскольку никакая аффинная функция не может быть положительной на двух диагонально противоположных вершинах и отрицательной на оставшихся двух. Таким образом, размер VC ${ displaystyle { mathcal {H}}}$ является ${ displaystyle d + 1}$, так что конечно. Из приведенной выше характеристики классов, изучаемых PAC, следует, что ${ displaystyle { mathcal {H}}}$ является PAC-обучаемым, и, соответственно, обучаемым.

Границы сложности выборки

Предполагать ${ displaystyle { mathcal {H}}}$ - это класс бинарных функций (функций для ${ displaystyle {0,1 }}$). Потом, ${ displaystyle { mathcal {H}}}$ является ${ displaystyle ( epsilon, delta)}$-PAC-обучаемый с выборкой размера:^[3]

куда ${ displaystyle VC ({ mathcal {H}})}$ это Размер ВК из ${ displaystyle { mathcal {H}}}$.Кроме того, любые ${ displaystyle ( epsilon, delta)}$-PAC-алгоритм обучения для ${ displaystyle { mathcal {H}}}$ должен иметь сложность образца:^[4]Таким образом, сложность выборки является линейной функцией Размер ВК пространства гипотез.

Предполагать ${ displaystyle { mathcal {H}}}$ является классом действительных функций с диапазоном в ${ displaystyle [0, T]}$. Потом, ${ displaystyle { mathcal {H}}}$ является ${ displaystyle ( epsilon, delta)}$-PAC-обучаемый с выборкой размера:^[5][6]

куда ${ Displaystyle PD ({ mathcal {H}})}$ является Псевдо-измерение Полларда из ${ displaystyle { mathcal {H}}}$.

Другие настройки

В дополнение к настройке контролируемого обучения, сложность выборки важна для полу-контролируемое обучение проблемы в том числе активное изучение,^[7] где алгоритм может запрашивать метки для специально выбранных входов, чтобы снизить стоимость получения множества меток. Концепция сложности выборки также проявляется в обучение с подкреплением,^[8] онлайн обучение, и неконтролируемые алгоритмы, например за изучение словаря.^[9]

Эффективность в робототехнике

Высокая сложность выборки означает, что для запуска Поиск в дереве Монте-Карло.^[10] Это равно a модель бесплатно поиск грубой силы в пространстве состояний. Напротив, высокоэффективный алгоритм имеет низкую сложность выборки.^[11] Возможные методы уменьшения сложности выборки: метрическое обучение^[12] и обучение с подкреплением на основе моделей.^[13]

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