DataDeep

Sapere aude

Оптимизация в машинном обучении

| Комментарии

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

Если эти вопросы вызывают интерес — заходите.

Связь оптимизации и машинного обученния

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

Разобравшись с оптимизацией “на пальцах”, определим ее формально, а формально задача математической оптимизации записывается следующим образом:

Так вот, просто и незатейливо. Но постойте, кто эти , , и какое отношение они имеют к машинному обучению?

Оказывается, большинство задач машинного обучения формулируются именно таким образом: в виде минимизации некоего функционала по некоторому параметру . Например, в случае задачи классификации или регрессии мы стараемся предсказывать одну переменную () на основе другой () с помощью набора функций–“оракулов” , выбирая наилучшую из них на основе обучающей выборки — в таком случае мы хотим минимизировать ошибку предсказания на имеющейся выборке. Ошибку предсказания чаще всего записывают как

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

Метод -средних

Этот метод решает задачу кластеризации — разбиения множества точек на () непересекающихся множеств-кластеров. Результат кластеризации методом $K$-средних — это, во-первых, разбиение множества ${1,\ldots,N}$ на кластеров: и, во-вторых, центр каждого из этих кластеров: . Функция при фиксированном $K$ для метода $K$-средних записывается следующим образом

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

Линейная регрессия с квадратичной функцией потерь

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

— здесь минимизируется среднеквадратичное отклонение “предсказаний” от истинных значений .

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

Математическая оптимизация

Решив, что оптимизация в машинном обучении, а значит и в нашем арсенале — must have, обсудим ее поподробнее.

Математическая оптимизация зародилась в XVIII–XIX века и окончательно оформилась в XX веке. За этот срок у нее появилось множество видов, подвидов, методов и приложений. Как мы и упомянали выше, общая задача оптимизации ставится следующим образом

но от настолько общей постановки мало толку — совершенно непонятно как ее решать: не имея информации о природе и , мы безоружны, можем только вслепую тыкать “пальцем в небо” (вернее, в ) в надежде попасть в точку минимума. Собственно, чем не вариант, есть даже схожий по идее метод с вполне себе научным названием: метод равномерного поиска (aka перебора). Суть его, как вы уже догадались, состоит в том, чтобы наложить -сетку на множество и измерить функцию в каждом узле сетки. Так найдется узел с наименьшим значением , и … пользы от этого знания будет чуть больше чем никакой. Без дополнительных ограничений на и/или наш ничего не говорит ни о наимаеньшем значении не о соответствующем аргументе . Действительно, может меняться сколь угодно быстро, принимая между узлами сетки какие угодно значения, а то и вовсе быть разрывной. То есть знания о функции в узлах не говорит ничего о ней вне этих узлов. Так вот, старались-старались, считали функцию в каждом узле, а толку — ноль.

Но не стоит отчаиваться, надо это дело исправить. В чем наша проблема? Проблема наша в излишнней свободе функции $\risk$, точнее в неограниченной скорости ее изменения.

Так давайте ее ограничим! Например, вот так:

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

где — размерность . Местоположении , однако, до сих пор остается загадкой.

Можно продолжить модифицировать метод перебора, добиваясь лучших гарантий точности (как по параметру, так и по значению функции), и увеличивая вычислительную эффективность (мы вычислили порядка раз, где — объем , что даже в невинном единичном кубе при даст миллион). Но это займет немало времени, а метод перебора интересен нам сейчас с той только точки зрения, что демонстрирует две важные идеи:

  1. There is no free lucnh. Чтобы эффективно решить задачу оптимизации, нам нужно ее ограничить — сузить круг поисков. Тем быстрее и точнее мы хотим ее решить, тем более жесткие ограничения нам придется накладывать;
  2. Лучшее — враг хорошего. Иногда достаточно найти приближенное к оптимальному решение, сэкономив при этом на ресурсах.

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

Градиентные методы

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

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

Таким образом, в окрестности точки мы приблизили линейной функцией. Градиентные методы эксплуатируют это приближение, полагаясь на то, что минимизация эквивалентна минимизации ее линейного приближения в небольшой окрестности точки . А что такое “небольшая окрестность”? Ограничим ее шаром с радиусом , тогда в этой окрестности минимум будет достигаться при

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

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

К счастью, мы можем избавится от этих недостатков, немного изменив наш алгоритм

Этот “алгоритм” есть ни что иное, как метод градиентного спуска (gradient descent). Известно, что при некоторых условиях на и (например, выпукла, удовлетворяет условию Липшица, а ), значение в оценках метода градиентного спуска стремится к оптимальному

— это не может не радовать.

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

Пример. Линейная регрессия с использованием метода градиентного спуска

Выше мы уже упомянали задачу линейной регрессии (с квадратичной функцией ошибки). Напомним ее целевую функцию :

В матричном виде она записывается как

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

В первую очередь нам нужны данные: , для простоты возьмем модельные ():

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

“Лишний” индекс к мы добавили неспроста: если обозначить для всех , то можно переписать и более того, в матричной форме

где

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

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

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

Заключение

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

Напоследок, порекомендую пару интересных материалов по теме:

  • Введение в оптимизацию. Поляк Б.Т. — книга от ученого с мировым именем, не только формальным, но и доступным языком рассказывает об основнах оптимизации, помогая уяснить в первую очередь не конкретные задачи и метода, а идеи, стоящие за ними;
  • EE364a: Convex Optimization. Бойд С. — записанные курсы Стэндфордского университета по выпуклой оптимизации (мы этого еще не знаем, но методы выпуклой оптимизации — если не самые важные, то абсолютно незаменимые в машинном обучении);
  • Методы оптимизации в машинном обучении. Кропотов Д.А. — развернутое содержание курса лекций факультета вычислительной математики и кибернетики МГУ. Без конспектов, к сожалению но с отличной подборкой литературы;
  • Machine learning — курс посвященный машинному обучению от известного ученого и сооснователя сервиса онлайн-обучения Coursera.org Andrew Ng, который помимо объяснения самих алгоритмов большое внимание уделяет вопросу оптимизации. Между прочим, картинка для привлечения внимания взята из слайдов одной и лекций этого курса (лекции второй недели, посвященные простейшей линейной регрессии).

До встречи!

Комментарии