Блок 1) Hill Climber - Оптимизация

КУРС НЕКЛАССИЧЕСКОЙ ОПТИМИЗАЦИИ

Блок 1) Hill Climber - Оптимизация

Обложка Hill Climber и его многочисленные варианты: простой, жадный, случайный и другие!

Здравствуйте и добро пожаловать обратно на этот полный курс неклассической оптимизации! В этом посте мы начнем с первого алгоритма: Hill Climbing! Если вы новичок в этом курсе, вы можете ознакомиться с обзором ниже!

Для начала, что такое Hill Climbing? Hill Climbing относится к области локальных поисков, цель которых - найти минимум или максимум целевой функции. Алгоритм считается локальным поиском, поскольку он работает с небольшими шагами относительно своего текущего положения в надежде найти лучшую позицию.

Оглавление

• Обзор и базовый алгоритм восхождения на холм
• Распространенные проблемы
• Варианты для альпинистов
• Создание нашей реализации
• Функции цели тестирования
• Код
• Заключение

Обзор и базовый алгоритм восхождения на холм

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

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

Наша цель - найти точку максимума, которая находится в точке (0,0). Как работает Hill Climber, чтобы найти максимальную точку? Сначала мы выбираем случайную начальную точку, делаем шаг во всех возможных направлениях и перемещаемся в позицию, которая имеет наибольшее значение функции. Для этой задачи у нас есть восемь возможных ходов для каждой позиции. Два для движения только в направлении x (как положительно, так и отрицательно); два для движения только в направлении y (как положительно, так и отрицательно); и четыре для движения в направлении x (как положительное, так и отрицательное) и в направлении y (как положительное, так и отрицательное). После тестирования следующих восьми позиций мы выбираем лучшую позицию. Слева внизу изображен именно такой сценарий. У нас есть начальная точка красного цвета, а восемь цветных точек вокруг - это возможные направления для шага. Однако обратите внимание, что направление, в котором сделан шаг, - это желтая верхняя левая точка, так как это дало наилучшее значение. Просто повторяем этот процесс до схождения. В правой части у нас есть начальная

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

Базовый алгоритм Hill-Climber может быть изображен ниже. Сначала мы случайным образом выбираем начальное состояние, затем выбираем различные переменные, к которым нужно шагать, размеры шага, а затем тестируем все сгенерированные новые позиции. После тестирования мы выбираем лучшую позицию для входа и перезапускаем процесс. Прекращение происходит, когда наш алгоритм либо достиг определенного пользователем максимального количества итераций, либо когда алгоритм застаивается / сходится: когда текущая позиция не изменяется после указанного количества итераций.

Общие проблемы

При реализации базовой версии алгоритма возникают три распространенных проблемы:

1. Для многомерных задач, сколько переменных мы выбираем для тестирования, прежде чем приступить к работе?
2. Какой должен быть размер шага в каждом направлении?
3. Проблемы с застреванием

Если у нас есть n-мерная целевая функция, существует 2 ^ n возможных ходов состояний, которые следует учитывать. В примере, приведенном выше в трехмерном гауссовском распределении, было 8 возможных ходов, 2³ = 8. Причина, по которой это число растет экспоненциально, заключается в том, что мы должны учитывать «диагональные» движения, когда мы движемся в направлениях, которые учитывают взаимодействие между несколькими переменными, а не одной. Теперь очевидная проблема состоит в том, что оценка 2 ^ n точек на каждом временном шаге является чрезвычайно дорогой задачей, когда n становится больше, чем примерно 15. Мы можем уменьшить это, не учитывая «диагональные» состояния; вместо этого мы рассматриваем только ходы с одной переменной. В этой структуре существует 2 * n возможных перемещений в одно состояние (как вперед, так и назад для каждой переменной), при условии отсутствия диагональных перемещений. Таким образом, для жадного подхода нам нужно протестировать 2 * n возможных состояний, прежде чем выбирать наилучшее состояние для перехода. Для больших пространств состояний или когда у нас разрешено ограниченное количество вычислений функций, это может отнимать время и для больших n. Распространенный способ решения этой проблемы - уменьшить количество переменных, к которым нужно перейти, просто взяв случайную выборку из заданного набора переменных и протестировав только шаги в этих переменных.

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

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

Варианты для альпинистов

Как подробно описано выше, есть три распространенные проблемы, с которыми сталкивается Hill Climber. В ответ было разработано множество вариантов решения этих проблем. Алгоритм, описанный до сих пор для Hill Climber, известен как Steepest Ascent Hill Climber, где традиционный Simple Hill Climber проверяет каждую позицию одну за другой и первым дает лучшее значение. выбирается вместо того, чтобы проверять все соседние позиции и переходить в лучшую. Стохастический подъем на холм - еще один популярный вариант, который выбирает позицию и перемещается в нее вероятностно. Это три очень хорошо известных варианта - остальные варианты, которые будут описаны ниже, не имеют традиционных названий.

Настоящий жадный подход должен будет оценивать 2 ^ n или 2 * n возможных позиций за итерацию, в зависимости от разрешения диагоналей или нет. Как указывалось ранее, это может привести к потере вычислительного времени, когда n велико. Чтобы уменьшить это, мы можем проверить либо одну случайную величину, либо несколько случайных величин. Это можно назвать Восхождение на гору с отбором стохастической переменной.

С другой стороны, предполагая, что мы всегда выбираем оценку всех 2 * n возможных позиций, тогда наш алгоритм всегда будет детерминированно следовать одному и тому же пути от начальной точки до сходимости, поскольку он всегда будет выбирать локального лучшего соседа. Это может быть проблематично, когда алгоритм застревает в локальных оптимумах. Чтобы ввести дисперсию, алгоритм может перемещаться в позиции, вероятностно определяемые их значениями функций. Возьмем, к примеру, ниже, где у нас есть пять возможных соседей. Мы вычисляем их значения функций и делим каждое значение на сумму значений функций, чтобы получить вероятность:

Теперь вместо того, чтобы всегда выбирать соседа 2 для перехода при выборе наибольшего значения F (x), мы выбираем из заданных вероятностей, чтобы добавить некоторую дисперсию к пути. Это можно назвать Восхождение на холм с выбором стохастического соседа. Очевидный недостаток состоит в том, что для достижения точки потребуется гораздо больше итераций; однако включенная дисперсия может быть тем, что нужно, чтобы выйти за пределы локальных оптимумов.

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

Создание нашей реализации

Для наших реализаций мы создадим две разные версии Hill Climber. Во-первых, мы создадим классический Steepest Ascent Hill Climber, который создаст 2 * n возможных соседних состояний для оценки, прежде чем выбирать лучшее для перехода. Во-вторых, мы будем использовать сочетание размера запланированного шага и выбора стохастической переменной. Вместо того, чтобы проверять каждый возможный шаг в текущей позиции, наш алгоритм будет выбирать случайный набор переменных на каждой итерации и проверять шаги для этих выбранных переменных. Для размера шага расписания наш алгоритм будет делать случайный шаг вперед или назад в выбранной переменной через единый размер шага. Единый размер шага работает путем равномерного случайного шага между двумя значениями. Например, мы берем случайное значение из U (-0,1, 0,1) и используем его в качестве размера шага.

Для нашего альпиниста на самый крутой подъем на гору нам нужно определить размер шага. Поскольку домен каждой переменной может быть разным, мы не можем предполагать глобальный статический размер шага; вместо этого нам нужно определить размер шага для каждой переменной. Классический способ сделать это - сделать процентный шаг от общего размера домена для каждой переменной. Например, предположим, что у нас есть следующие границы области для x = [- 5,5] и y = [0,15] в двумерной задаче с двумя входами. Таким образом, наша нижняя граница для наших переменных будет [-5, 0], а верхняя граница будет [5, 15]. Мы можем создать общие границы, которые измеряют размер доменного пространства для каждой переменной, вычитая верхнюю границу из нижней для каждой переменной: [5 - (- 5), 15-0] = [10,15]. Затем мы берем размер шага в процентах, скажем, 0,01. Тогда 0,01 * [10,15] = [0,1, 0,15]. Теперь это наши размеры шага для соответствующих переменных: 0,1 для x и 0,15 для y. Вот реализация Steepest Ascent:

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

Функции цели тестирования

Пришло время протестировать две наши реализации на реальных целевых функциях! Если вы помните на странице обзора курса, мы протестируем наши алгоритмы на трех функциях: Сфера, Шуберт и Эгхолдер, где цель каждый должен найти глобальный минимум. Глобальный минимум для сферической функции равен F (X) = 0, F (X) = - 12870,88 (изменяется для разных n) для Шуберта и F (X) = - 959,64 для Eggholder. Сфера - это выпуклая функция без локальных минимумов, в то время как и Шуберт, и Эггхолдер очень модальны с множеством локальных минимумов и максимумов.

И для Sphere, и для Shubert мы будем тестировать с n = 1000 и допускать 100000 оценок функций. Поскольку каждый запуск алгоритма зависит от начальной случайной позиции, они будут повторяться 30 раз для каждой функции, а средний результат будет сохранен для сравнения. Кроме того, процент размера шага будет проверяться при следующих значениях: [1, 0,5, 0,1, 0,01]. Теперь следует заметить, что процент размера шага, равный 1, чрезвычайно велик, чтобы его можно было рассматривать как локальный поиск для Hill Climber, поскольку размер шага имеет максимальное значение, достаточно большое, чтобы охватить всю область; однако всякий раз, когда мы проверяем единый размер шага, это поможет нам создать исследование, поскольку шаг равномерно выбирается из всего домена, а не статичен.

Тестирование наискорейшего спуска

Сначала давайте протестируем наш алгоритм Наименьшего спуска. Поскольку этот алгоритм проверяет 2 * n возможных соседей, а при n = 1000, 2000 оценок функций будут проверяться на каждой итерации. Следовательно, максимальное количество итераций будет 50. Вот результаты:

Как мы видим, всего с 100 000 оценками функций, Steepest Descent Climber не находит минимальных точек даже близко к фактическим глобальным минимальным точкам. Вероятно, это связано с тем, что мы запускаем его только для 50 итераций, давайте вместо этого выполним 1000 итераций: это соответствует 2 миллионам оценок функций! Вот результаты:

Несмотря на то, что мы выполнили в 20 раз больше итераций, конечные найденные минимальные точки все еще далеки от фактических глобальных минимальных точек. Обратите внимание, что для функции Sphere процент шагов 0,5 и 0,1 показал наилучшие результаты, в то время как для Shubert процент шага 1 показал наилучшие результаты. Это демонстрирует, что процент шага - еще один гиперпараметр, который необходимо настроить для конкретной проблемы.

Тестирование стохастической переменной с равномерным шагом

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

Как мы видим, эта индивидуальная реализация Hill Climber показала себя лучше, чем классический Stochastic Descent Hill Climber. Это демонстрирует силу случайных размеров шага. Несмотря на то, что мы использовали здесь равномерное распределение, вместо этого можно было бы взять выборку из гауссовского или любого другого типа распределения. Наилучший процент шага для функции «Сфера» составлял 0,1, в то время как для функции Шуберта он составлял 1 и 0,5. Чтобы не было ничего похожего, давайте посмотрим, насколько хорошо алгоритм будет работать с 2 миллионами вычислений функций:

Как мы видим выше, при 2 миллионах оценок глобальный минимум был почти найден с шагом 0,01 процента для сферической функции и процентом шага 1 для функции Шуберта.

Тестирование функции Eggholder

Можно возразить, что крутой спуск плохо работает из-за большой размерности доменного пространства, n = 1000 в двух предыдущих целевых функциях. Вместо этого давайте протестируем оба алгоритма на 2 входной размерной функции Эггхолдера с ограничением в 1000 оценок функции. Вот результаты:

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

Код

Если вы хотите поиграть с описанными выше алгоритмами, весь код для этого курса доступен ниже в моем репозитории GitHub!

Вывод

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

Следите за новостями о следующем блоке в этой серии, в котором мы расскажем о моделировании отжига!