Связь между выпуклой оптимизацией и машинным обучением

Когда я впервые начал самоучиться машинному обучению, я был удивлен, узнав, что у меня уже был некоторый опыт в этом. В колледже я прошел только один вводный курс по информатике, поэтому ожидал, что кривая обучения будет намного выше. Мне пригодился мой предыдущий урок линейной алгебры, а также Серия линейной алгебры 3Blue1Brown (очень рекомендую). Чего я не ожидал, так это моего урока по оптимизации. Вероятно, это связано с тем, что я прошел этот курс до того, как узнал что-либо о машинном обучении, и поэтому сразу же забыл обо всех очевидных отношениях между ними, которые упоминались в классе. Но когда я начал изучать линейную регрессию, я все еще помню, как видел слова градиентный спуск и думал: Подождите, я уже знаю, что это такое. Теория выпуклости позволила легко понять, почему мы можем использовать градиентный спуск для решения функции стоимости линейной регрессии. В этом посте я надеюсь осветить основы этой теории и предложить более глубокое понимание линейной регрессии.

Выпуклость

Начнем с определения выпуклости через выпуклые множества и выпуклые функции. Учебник по выпуклой оптимизации Стивена Бойда - отличный ресурс по этой теме. Выпуклое множество определяется следующим образом:

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

Это определение выпуклого множества совпадает с определением выпуклой функции, показанным ниже:

Как сказано в учебнике по Convex Optimization, вы можете интуитивно представить себе выпуклую функцию как такую, в которой, если вы проведете линию от (x, f (x)) до (y, f (y)), тогда график выпуклой функции будет ниже этой линии. Ниже приведены три примера, в которых мы применяем эту интуицию, чтобы определить, является ли функция выпуклой.

Мы можем видеть, что график в середине не является выпуклым, потому что, когда мы рисуем отрезок прямой, соединяющий две точки на графике, есть некоторые точки (x, f (x)), где f (x) больше, чем соответствующая точка на графике. отрезок линии.

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

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

Обзор линейной регрессии

Цель линейной регрессии - подогнать лучшую линейную модель к набору данных. Допустим, есть m выборок данных в n-мерном пространстве. В каждом из этих примеров есть n функций, которые соответствуют одному выходному значению. У нас есть доступ к входным и выходным данным, но мы хотим выяснить, существует ли линейная зависимость, которая сопоставляет входные данные с выходными данными. Здесь на помощь приходит модель линейной регрессии. Эта модель записывается в форме:

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

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

Выпуклость функции затрат.

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

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

Вывод

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