Как машины учатся и почему это важно

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

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

Но задумывались ли вы когда-нибудь, откуда оно взялось? Почему он позволяет учиться на обучающем наборе и обобщать невидимые данные? Почему больший тренировочный сет приносит лучшие результаты?

В этой статье мы узнаем, почему и как кроется эта известная проблема.

Контур

Ожидаемый риск, эмпирический риск

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

Ожидаемый риск расширяет эту концепцию на все примеры. Фактически, мы можем определить ожидаемый риск (R) как ожидаемое значение (E)функции потерь V:

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

Когда-то была ожидаемая минимизация риска. Затем вмешалась реальность.

Дело в том, что это может быть решением, за исключением того, что мы не знаем плотность вероятности p(x, y)по всему пространству X x Y.

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

Чтобы использовать его на практике, важно ввести приблизительное значение ожидаемого риска: эмпирический риск. Его определение простое:

Поскольку теперь мы используем эмпирическую плотность вероятности, мы можем количественно определить риск как конечное среднее значений, которые функция потерь принимает на обучающем наборе (с lчислом примеров). Мы можем вычислить это значение в известном конечном пространстве.

Но связаны ли ожидаемый и эмпирический риски каким-либо образом, что делает это число значимым? Да, Закон больших чисел приходит нам на помощь и показывает, что эмпирический риск сходится к ожидаемому для достаточно большого числа примеров:

«Достаточно большое количество примеров» здесь позволяет нам понять, почему достаточно большой обучающий набор имеет решающее значение при обучении модели машинного обучения.

Следовательно, принцип минимизации эмпирического риска (ERM) ищет
функцию f, которая минимизирует эмпирический риск. На этом этапе может показаться, что
проблема решена, и нам нужно только найти подходящий
класс функций H (пространство гипотез) и минимизировать Remp [f ] в
H. Ну, не совсем так.

Проблема минимизации эмпирического риска связана с двумя основными проблемами:

  1. Выбор пространства гипотез H нетривиален.
  2. Это может быть некорректно поставленная задача с неуникальными и нестабильными решениями.

Непротиворечивость алгоритма минимизации эмпирического риска

Чтобы решить эти вопросы, нам нужно пройти через некоторые предварительные концепции.

Учитывая 1) минимизатор ожидаемого риска и 2) минимизатор эмпирического риска в фиксированном пространстве гипотез H, алгоритм ERM непротиворечив, если:

Как проверить непротиворечивость ERM? Теорема Вапника-Червоненкиса является ее необходимым и достаточным условием.

Теорема Вапника-Червоненкиса

Учитывая Hпространствогипотез, алгоритм ERM непротиворечив в H тогда и только тогда, когда ∀ϵ › 0:

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

Почему теоремы Вапника-Червоненкиса

Но как теорема VC помогает проверить свойство согласованности? Начнем с этой неравноценности.

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

Левая неэквивалентность (1 ≤ 2) взята непосредственно из изображения 8. Правильный вариант (2 ≤ 3) был введен для того, чтобы каким-то образом связать термин согласованности, что позволяет обеспечить свойство согласованности. Затем мы устанавливаем термин 3 таким же, как 2, добавляя и вычитая эквивалентное количество:

Тогда, учитывая свойство:

Так просто, как кажется: эмпирический риск в минимизаторе эмпирического риска, безусловно, меньше или равен самому эмпирическому риску, но в минимизаторе ожидаемого риска. Это позволяет нам продолжить и написать:

Где зеленый операнд происходит непосредственно от применения вышеуказанного свойства к 3. Наконец, мы можем обобщить все пространство гипотез, просто взяв sup:

И начальная неэквивалентность теперь выглядит так:

Если вы снова посмотрите на Изображение 7, вы заметите, как теорема VC приводит к тому, что величина в правой части стремится к нулю. Для Теоремы сжатия, поскольку и левая, и правая часть стремятся к нулю, средний член также стремится к нулю: и это именно то, что требует от нас проверка согласованности (Изображение 6).

Чего нам в настоящее время не хватает, так это рабочего алгоритма, который мы можем использовать для проверки согласованности и использования ERM.

Меры мощности

Показатели мощности, в частности VC Dimension, позволяют нам использовать ERM на практике. Но сначала важно обсудить основополагающую идею: свойство разрушения.

Разрушение

Учитывая Xвходное пространство, S его подмножество и H пространство гипотез, тогда S говорят быть разбитымH, тогда и только тогда, когда:

Чего ждать? Это шутка?

Ладно ладно, не волнуйся, скоро все станет ясно. На простом английском языке это свойство означает, что для каждого S', содержащегося в S, существует функция f, принадлежащая H такие, что fпересекается с Sравно S'. Давайте посмотрим на это графически.

Для простоты мы считаем набор из трех точек в R² с метками {-1, 1} равным S, а множество всех допустимых полуплоскостей должно быть H. Итак, мы должны рассмотреть все S', содержащиеся в S, и найти полуплоскость, которая отделяет S' от остальные точки.

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

Не существует полуплоскости, которая разделяла бы эти две группы точек.

Размер ВК

VC-размерностьпространства гипотез H – это мощность (количество элементов) наибольшего подмножества S входного пространства X, разделенный H. Он присваивает номер пространству определенных функций.

В приведенном выше примере размер VC полуплоскостей (H) равен 3, поскольку, как мы видели, пространство S, состоящее из 4 элементов, не разбито пространство таких функций.

венчурный капитал

Граница VCвводит границудля ожидаемого риска. В частности, если взяты lпримеры и h ‹ lявляется размерностью VCпространства H, то с вероятностью не менее 1 - η:

С (B — A) / 2 коэффициентом, зависящим от функции потерь, и ϵ так называемым членом мощности, равным:

Таким образом, исходя из приведенного выше определения VC Bound, мы можем написать:

Эта неэквивалентность представляет собой верхнюю границудля операнда теоремы Вапника-Червоненкиса. Устремляя l к бесконечности, как того требует теорема VC, мы можем заметить, что выражение yellow стремится к 0:

Итак, собираем все вместе:

В результате проверяются как теорема VC, так и непротиворечивость алгоритма ERM.

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

Граница не может быть минимизирована только против f,поскольку член емкости является свойством пространства гипотез H, а не конкретной функции f из H. Мы должны ввести некоторую форму структуры на H и минимизировать элементы этой структуры. По этой причине этот алгоритм известен как Минимизация структурных рисков (SRM).

Минимизация структурных рисков

Алгоритм минимизации структурных рисков рассматривает последовательность пространств гипотез:

Такой, что:

Проще говоря, мы должны рассмотреть последовательность пространств гипотез с возрастающей емкостью (размерность VC). Затем мы можем искать пространство гипотез, которое минимизирует:

Таким образом, мы должны найти пространство гипотез Hm, которое минимизирует сумму эмпирического риска, рассчитанного в минимизаторе эмпирического риска в этом конкретном пространстве гипотез, и члена емкости.

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

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

Минимизация структурного риска при воспроизведении ядерных гильбертовых пространств

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

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

Тогда m-е пространство гипотез определяется выражением:

Можно показать, что мощность Hm увеличивается в зависимости от Am. Таким образом, мы можем записать задачу ERM как задачу минимума с ограничениями:

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

Мы здесь! Посмотрите на изображение 1. Вот как возникает популярная проблема оптимизации машинного обучения и почему она используется для поиска хорошего компромисса между переоснащением и недообучением.

Я очень надеюсь, что вам понравилась эта статья. Если это так, не стесняйтесь похлопать меня или больше.

Подпишитесь на меня, чтобы увидеть больше подобных статей.

Обратитесь в Linkedin за комментариями и предложениями.

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



Присоединяйтесь к Medium по моей реферальной ссылке — Габриэле Маттиоли
Прочитайте все статьи Габриэле Маттиоли (и тысяч других авторов на Medium). Ваш членский взнос напрямую…medium.com