Введение в оптимизацию: градиентные алгоритмы скачать в хорошем качестве

Введение в оптимизацию: градиентные алгоритмы

Концептуальный обзор алгоритмов оптимизации на основе градиента. ПРИМЕЧАНИЕ: В 2:20 допущена опечатка в уравнении наклона, вместо него должно быть delta_y/delta_x. Это видео входит в серию вводных обучающих материалов по оптимизации. ТЕСТ: https://goo.gl/forms/1NaFUcqCnWgWbrQh1 РАСШИФРОВКА: Здравствуйте! Добро пожаловать на курс «Введение в оптимизацию». В этом видео рассматриваются алгоритмы, основанные на градиенте. Градиентные алгоритмы и безградиентные алгоритмы — два основных метода решения задач оптимизации. В этом видео мы изучим основные принципы работы решателей, основанных на градиенте. Градиентные решатели используют производные для поиска оптимального значения функции. Чтобы понять, как это работает, представьте, что вы идёте по склону горы, пытаясь найти дорогу к месту стоянки у подножия горы. Как вы узнаете, куда идти? Возможно, вы могли бы пойти по тропе, посмотреть на карту или воспользоваться GPS. Возможно, вы даже сможете увидеть пункт назначения и направиться прямо туда. А теперь представьте, что у вас нет карты, GPS, тропы, а вокруг деревья, которые не позволяют вам видеть ничего, кроме местности непосредственно вокруг вас. Что дальше? Не зная ничего, кроме того, что кемпинг находится у подножия горы, один из возможных вариантов — спуститься вниз. Вы можете осмотреться, оценить уклон горы в небольшой видимой области и пойти в направлении самого крутого спуска. Вы можете продолжать делать это, время от времени останавливаясь, чтобы найти лучший путь, и в конце концов добраться до кемпинга. На базовом уровне это то же самое, что делают алгоритмы, основанные на градиенте. Есть три основных этапа: Направление поиска: Первый шаг — выбор направления движения. Решатель оценивает уклон, беря производную в текущем положении. В одном измерении эта производная и есть уклон. В более чем одном измерении это называется градиентом. Затем решатель использует эту информацию вместе с другими правилами для выбора направления движения. Это называется направлением поиска. Размер шага: Следующий шаг — определить, насколько далеко двигаться в выбранном направлении. Не следует заходить слишком далеко в одном направлении, иначе можно вернуться на другую гору. Однако необходимо пройти достаточно далеко, чтобы продвинуться к цели. Значение, которое выбирает решатель, называется размером шага. Проверка сходимости: После выбора направления и размера шага решатель движется в выбранном направлении. Затем он проверяет, достиг ли он дна. Если нет, он снова использует наклон для выбора нового направления и размера шага. Это продолжается до тех пор, пока решатель не достигнет подножия горы, или минимума. Мы называем это сходимостью. Существует множество вариантов выполнения этих шагов, но это основные идеи, лежащие в основе работы алгоритма оптимизации на основе градиента. Давайте посмотрим, как это может выглядеть на реальной функции. Попробуем найти минимум уравнения x^3 + 15x^2 + y^3 + 15y^2. Начнём с визуализации функции. Это график значений функции в диапазоне от -10 до 10 в обоих направлениях. Обратите внимание, как функция спадает к минимуму в центре. Для начала нам нужно дать оптимизатору начальное предположение. Выберем (8,8). Другой способ представления этой информации — контурный график, где линии представляют собой постоянные уровни или значения функции. Теперь мы можем наблюдать, как оптимизатор выбирает направление поиска и делает шаг, направление и ещё один шаг. В конце концов, он достигает точки минимума при x = 0, y = 0. Градиентные алгоритмы имеют свои сильные и слабые стороны. Они широко используются, обладают высокой производительностью и хорошо масштабируются для решения больших задач. Однако для них требуются плавные, непрерывные градиенты функции, а их вычисление может быть ресурсоёмким. Многие оптимизаторы, основанные на градиенте, склонны находить локальные минимумы, а не глобальный оптимум, то есть они найдут дно ближайшей долины, а не самую низкую точку на всей карте. Оптимизаторы, основанные на градиенте, — мощный инструмент, но, как и в любой задаче оптимизации, требуются опыт и практика, чтобы понять, какой метод подходит именно вам.