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

Атрибут моделей машинного обучения

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

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

Существует два варианта сложности выборки:

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

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

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

Определение

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

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

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

В нашей настройке мы имеем , где — алгоритм обучения, а — последовательность векторов, которые все взяты независимо из . Определим оптимальный риск Set , для каждого размера выборки . — случайная величина и зависит от случайной величины , которая взята из распределения . Алгоритм называется последовательным, если вероятностно сходится к . Другими словами, для всех существует положительное целое число , такое, что для всех размеров выборки мы имеем ${\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}}(h).}$$ ${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$ ${\displaystyle n}$ ${\displaystyle h_{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle \rho ^{n}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {E}}(h_{n})}$ ${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$ ${\displaystyle \epsilon ,\delta >0}$ ${\displaystyle N}$ ${\displaystyle n\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}}}$

Другими словами, сложность выборки определяет степень согласованности алгоритма: при заданной точности и уверенности необходимо сделать выборку точек данных, чтобы гарантировать, что риск выходной функции находится в пределах наилучшего возможного с вероятностью не менее . ^[2] ${\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 n\geq N}$

$${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}$$где , с как и выше. Теорема об отсутствии бесплатных обедов гласит, что без ограничений на пространство гипотез это не так, т.е. всегда существуют «плохие» распределения, для которых сложность выборки произвольно велика. ^[1] ${\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 и сложность Радемахера , которые контролируют сложность пространства . Меньшее пространство гипотез вносит больше смещения в процесс вывода, что означает, что может быть больше, чем наилучший возможный риск в большем пространстве. Однако, ограничивая сложность пространства гипотез, алгоритму становится возможным производить более однородно согласованные функции. Этот компромисс приводит к концепции регуляризации . ^[2] ${\displaystyle {\mathcal {H}}}$ ${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$

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

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

Предположим, что есть класс бинарных функций (функций для ). Тогда, является ли -PAC-обучаемым с выборкой размера: ^[3] где - размерность VC для . Более того, любой алгоритм -PAC-обучения для должен иметь сложность выборки: ^[4] Таким образом, сложность выборки является линейной функцией размерности VC пространства гипотез. ${\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 )}}$$ ${\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 )}}$$

Предположим , что есть класс функций с действительными значениями с диапазоном в . Тогда является -PAC-обучаемым с выборкой размера: ^{[5] [6]} где - псевдоразмерность Полларда . ${\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}}}$

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

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

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

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

Смотрите также

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

Ссылки

1. Вапник, Владимир (1998), Статистическая теория обучения , Нью-Йорк: Wiley.
2. Rosasco, Lorenzo (2014), Согласованность, обучаемость и регуляризация , Конспект лекций для курса MIT 9.520.
3. Стив Ханнеке (2016). «Оптимальная сложность выборки обучения PAC». J. Mach. Learn. Res . 17 (1): 1319–1333. arXiv : 1507.00473 .
4. Эренфойхт, Анджей; Хаусслер, Дэвид; Кернс, Майкл; Валиант, Лесли (1989). «Общая нижняя граница числа примеров, необходимых для обучения». Информация и вычисления . 82 (3): 247. doi : 10.1016/0890-5401(89)90002-3 .
5. Энтони, Мартин; Бартлетт, Питер Л. (2009). Обучение нейронных сетей: теоретические основы . ISBN 9780521118620.
6. Моргенштерн, Джейми; Рафгарден, Тим (2015). О псевдоизмерении почти оптимальных аукционов. NIPS. Curran Associates. стр. 136–144. arXiv : 1506.03684 .
7. Балкан, Мария-Флорина ; Ханнеке, Стив; Вортман Воган, Дженнифер (2010). «Истинная сложность выборки активного обучения». Машинное обучение . 80 (2–3): 111–139. doi : 10.1007/s10994-010-5174-y .
8. Какаде, Шам (2003), О сложности выборки обучения с подкреплением (PDF) , докторская диссертация, Университетский колледж Лондона: Подразделение вычислительной нейронауки Гэтсби.
9. Vainsencher, Daniel; Mannor, Shie; Bruckstein, Alfred (2011). «Образец сложности изучения словаря» (PDF) . Журнал исследований машинного обучения . 12 : 3259–3281.
10. Кауфманн, Эмили и Кулен, Воутер М. (2017). Поиск по дереву Монте-Карло по наилучшей идентификации руки . Достижения в области нейронных систем обработки информации. С. 4897–4906.{{cite conference}}: CS1 maint: multiple names: authors list (link)
11. Фидельман, Пегги и Стоун, Питер (2006). Щипок подбородка: исследование опыта обучения навыкам на шагающем роботе . Кубок мира по футболу среди роботов. Springer. С. 59–71.{{cite conference}}: CS1 maint: multiple names: authors list (link)
12. Верма, Накул и Брэнсон, Кристин (2015). Пример сложности обучения метрикам расстояния Махаланобиса . Достижения в области нейронных систем обработки информации. С. 2584–2592.{{cite conference}}: CS1 maint: multiple names: authors list (link)
13. Курутах, Танард и Клавера, Игнаси и Дуан, Ян и Тамар, Авив и Аббил, Питер (2018). «Оптимизация политики доверительного региона модели-ансамбля». arXiv : 1802.10592 [cs.LG].{{cite arXiv}}: CS1 maint: multiple names: authors list (link)