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

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

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

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

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

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

Однако, если нас интересует только конкретный класс целевых функций (например, только линейные функции), то сложность выборки конечна и линейно зависит от размерности VC в классе целевых функций.

Определение

Позвольте быть пространством, которое мы называем входным пространством, и быть пространством, которое мы называем выходным пространством, и пусть обозначает продукт . Например, в настройке двоичной классификации, как правило, это конечномерное векторное пространство и множество . ${\ 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 {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} = {\ underset {h \ in {\ mathcal {H}}} {\ inf}} {\ mathcal {E}} (час).}

Набор , для каждого . Обратите внимание, что это случайная величина, которая зависит от случайной величины , взятой из распределения . Алгоритм называется согласованным, если вероятностно сходится к . Другими словами, для всех существует положительное целое число , такое, что для всех мы имеем

{\ 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 \ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \ varepsilon] <\ delta.}

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

{\ 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}$

При вероятном приблизительно правильном (PAC) обучении нужно

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

{\ Displaystyle N (\ rho, \ epsilon, \ delta)}

{\ displaystyle 1 / \ epsilon}

{\ displaystyle 1 / \ delta}

{\ Displaystyle N (\ rho, \ epsilon, \ delta)}

{\ displaystyle {\ mathcal {H}}}

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

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

{\ Displaystyle \ sup _ {\ rho} \ left (\ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \ varepsilon] \ right) <\ delta,}

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

{\ 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}}}

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

{\ Displaystyle \ sup _ {\ rho} \ left (\ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \ varepsilon] \ right),}

нужно либо

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

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

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

регуляризации .

{\ displaystyle {\ mathcal {H}}}

{\ Displaystyle {\ mathcal {E}} _ {\ mathcal {H}} ^ {*}}

Теорема из теории VC состоит в

том, что следующие три утверждения эквивалентны для пространства гипотез :

{\ displaystyle {\ mathcal {H}}}

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

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

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

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

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

Допустим, есть класс бинарных функций (функций до ). Затем можно изучить -PAC с помощью выборки размера: ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle \ {0,1 \}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle (\ epsilon, \ delta)}$

{\ displaystyle N = O {\ bigg (} {\ frac {VC ({\ mathcal {H}}) + \ ln {1 \ over \ delta}} {\ epsilon}} {\ bigg)}}

где это измерение ВК из . Более того, любой алгоритм -PAC-обучения должен иметь сложность выборки:

{\ displaystyle VC ({\ mathcal {H}})}

{\ displaystyle {\ mathcal {H}}}

{\ displaystyle (\ epsilon, \ delta)}

{\ displaystyle {\ mathcal {H}}}

{\ Displaystyle N = \ Omega {\ bigg (} {\ frac {VC ({\ mathcal {H}}) + \ ln {1 \ over \ delta}} {\ epsilon}} {\ bigg)}}

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

Предположим , это класс функций с действительным знаком с диапазоном в . Затем можно изучить -PAC с помощью выборки размера: ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle [0, T]}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle (\ epsilon, \ delta)}$

{\ Displaystyle N = O {\ bigg (} T ^ {2} {\ frac {PD ({\ mathcal {H}}) \ ln {T \ over \ epsilon} + \ ln {1 \ over \ delta}} {\ epsilon ^ {2}}} {\ bigg)}}

где это Поллард псевдоразмерности из .

{\ Displaystyle PD ({\ mathcal {H}})}

{\ displaystyle {\ mathcal {H}}}

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

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

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

Высокая сложность выборки означает, что для выполнения поиска по дереву Монте-Карло требуется много вычислений . Это эквивалентно моделированному поиску методом грубой силы в пространстве состояний. Напротив, высокоэффективный алгоритм имеет низкую сложность выборки. Возможные методы уменьшения сложности выборки - это метрическое обучение и

обучение с подкреплением на основе моделей.

Languages

In other projects