Сложность примера

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

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

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

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

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

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

Определение

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

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

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

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

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

$${\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).$$

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

$$\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .$$

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

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

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

: бесконечная

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

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

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

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

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

нужно либо

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

выборочная

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

Это теорема теории VC , согласно которой следующие три утверждения эквивалентны для пространства гипотез. ${\mathcal {H}}$:

1. ${\mathcal {H}}$ является PAC-обучаемым.
2. Размер венчурного капитала ${\mathcal {H}}$ конечно.
3. ${\mathcal {H}}$ — однородный класс Гливенко-Кантелли .

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

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

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

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

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

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

где $VC({\mathcal {H}})$ размерность VC ​ ${\mathcal {H}}$.Более того, любой $(\epsilon ,\delta )$-PAC-алгоритм обучения для ${\mathcal {H}}$ должен иметь выборочную сложность:

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

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

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

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

где $PD({\mathcal {H}})$ — это псевдоразмерность Полларда ${\mathcal {H}}$.

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

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

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

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

См. также

• Активное обучение (машинное обучение)