Оптимизация – это раздел математики, который занимается поиском наилучших значений входных переменных для получения оптимального значения на выходе.
У него есть приложения в экономике, финансах, управленческих науках, логистике, но наиболее важно для целей этого сообщения в блоге то, что оптимизация является важной задачей в большинстве методов машинного обучения, которые исследуются и используются сегодня.
Большинство алгоритмов обучения с учителем требуют от нас оптимизации параметров конкретной модели машинного обучения, чтобы минимизировать функцию стоимости. Наиболее известным алгоритмом оптимизации, используемым для этой цели, является Алгоритм градиентного спуска. Но алгоритмы машинного обучения также имеют гиперпараметры, значения которых сильно влияют на эффективность модели. Многие исследователи изучают способы оптимизации гиперпараметров для повышения эффективности моделей.
Цель этой статьи — познакомить читателей с классом алгоритмов, называемых природными метаэвристическими алгоритмами оптимизации. Но прежде чем сделать это, давайте рассмотрим некоторые важные концепции, которые помогут нам понять эти алгоритмы.
Определение 1:
Целью оптимизации является минимизация/максимизация набора функций fᵢ(x) с учетом другого набора ограничений gᵢ(x).
Набор функций fᵢ называется целевыми функциями. Если значение i равно 1, это называется однокритериальной оптимизацией. Если i›1, это называется многокритериальной оптимизацией. Для простоты давайте пока будем заниматься только задачами однокритериальной оптимизации.
Входная переменная x представляет собой вектор со значениями в действительной области (x∈ ℝⁿ). Значения, охватываемые x, называются областью поиска. Нам нужно найти оптимальное значение x в среде поиска, такое, что fᵢ(x) является минимальным/максимальным, а ограничения gᵢ(x) встречаются.
Основная задача наших алгоритмов оптимизации — найти правильную стратегию поиска оптимальности. Ландшафт поиска имеет бесконечное количество точек. Понимание свойств нашей целевой функции и ограничений помогает нам выбрать правильный алгоритм оптимизации.
Поиск оптимальности подобен поиску сокровища в холмистой местности за ограниченное время¹. Мы не ищем все точки. Давайте рассмотрим некоторые стратегии, которые используют различные алгоритмы оптимизации для поиска в поисковой среде.
1. Если функция f дважды дифференцируема, мы можем найти локальный и глобальный оптимумы, установив первую производную равной нулю и исследуя собственные значения матрицы Гессе. Но так обстоит дело с большинством проблем.
2. Используя нашу аналогию с поиском сокровищ, предположим, что мы знаем, что сокровище находится в самой глубокой долине. Мы могли бы начать с какой-то точки ландшафта поиска и продолжать двигаться вниз по самому крутому склону. Это и есть алгоритм градиентного спуска. Но это работает только в том случае, если существует один глобальный оптимум и целевая функция везде дифференцируема, как функция среднеквадратичной ошибки в линейной регрессии.
Методы, описанные в 1 и 2, являются детерминированными. С одной и той же начальной позицией детерминированный алгоритм будет следовать одному и тому же пути поиска и давать один и тот же результат при каждом выполнении. С другой стороны, алгоритмы стохастической оптимизации имеют элемент случайности. Эти алгоритмы полезны, когда функция возражения не является непрерывной или если в ландшафте поиска много локальных оптимумов. Если запустить стохастический алгоритм дважды, мы получим разные результаты, хотя они могут быть близкими.
Стохастические алгоритмы можно разделить на эвристические и метаэвристические. Различие между ними тонкое.
Эвристика обеспечивает «достаточно хорошее» решение за разумное время, но не гарантирует наилучшее решение.
Метаэвристика является расширением эвристического алгоритма. Эта ключевая черта, которая отличает их друг от друга, выражена во фразе «разведка и эксплуатация». Исследование означает поиск оптимальных решений в глобальном масштабе с помощью рандомизации и использования средств поиска в локальном пространстве наилучшего решения, полученного на данный момент. Надлежащий баланс обоих этих компонентов гарантирует, что глобальный оптимум будет найден, хотя это еще не гарантировано.
И эвристика, и метаэвристика являются методами, основанными на следах и ошибках, но они значительно сокращают пространство поиска благодаря некоторым умным стратегиям.
Метаэвристические алгоритмы, вдохновленные природой, как следует из названия, представляют собой метаэвристические алгоритмы, вдохновленные природными явлениями. На самом деле оптимизация лежит в основе механизма выживания живых существ. Многие исследователи наблюдали эти явления и применяли их для задач оптимизации в вычислительном мире.
Предположим, что в нашей охоте за сокровищами у нас есть команда из многих человек. Каждый ищет пространство самостоятельно и сообщает результаты друг другу. Эти результаты влияют на решение, которое команда принимает при дальнейшем поиске. В этом заключается идея метаэвристики на основе популяции. «Исследование против эксплуатации» может быть достигнуто с помощью метаэвристики, основанной на популяции, потому что присутствие многих людей позволяет нам исследовать, а наилучшие полученные результаты могут быть эксплуатированы. Баланс поддерживается с помощью управляющих переменных, значения которых меняются при каждой итерации алгоритма.
Самые популярные метаэвристические алгоритмы, вдохновленные природой, используемые сегодня, основаны на популяции.
Существует два вида метаэвристик, основанных на популяции, вдохновленной природой: эволюционные алгоритмы, которые были популяризированы генетическим алгоритмом, и интеллект роя, который был популяризирован с помощью оптимизации роя частиц² (PSO).
Генетические алгоритмы основаны на теории естественного отбора Дарвина. Здесь отсеиваются лица, показавшие наихудшие результаты³, и выбираются другие лица вместе с их потомками⁴. Этот процесс повторяется в течение заданного числа итераций, и фиксируется позиция человека с лучшим результатом.
Оптимизация роя частиц — это метод, вдохновленный движением птиц в небе во время миграции. Птицы мигрируют стаей в более подходящий климатический регион. Когда одна из птиц на периферии почувствует более теплую область, она меняет направление полета, и все остальные птицы немедленно следуют за ней. Опять же, если другая птица чувствует более теплый регион, она снова направляет движение стаи. Движение людей в PSO вдохновлено этим явлением.
В PSO есть управляющие переменные, называемые global_best(gb), в которых хранится позиция человека с лучшим результатом, и personal_best(pb), в которой хранится лучшая позиция, которую каждый человек посетил до сих пор. Каждый индивид движется немного к своему пб и немного к своему гб. Расстояние, на которое они перемещаются в каждом направлении, уменьшается с каждой итерацией.
Вдохновленные природой алгоритмы очень полезны, если ландшафт поиска не является непрерывным или если целевые функции слишком сложны. Это делает их очень полезными для оптимизации гиперпараметров в глубоком обучении.
Возьмем в качестве примера простую нейронную сеть. Его гиперпараметрами являются скорость обучения (α), размер партии, оптимизатор, снижение скорости обучения, количество скрытых слоев, количество нейронов в каждом скрытом слое. Все это составляет входной вектор x in Определение 1. Целевыми функциями fᵢ являются точность проверочного набора, функция потерь, точность и т. д. Эта проблема имеет много ограничений gᵢ. Например, 0‹α‹1.
Если мы используем вдохновленную природой метаэвристику для решения вышеупомянутой проблемы, то каждый человек будет инициализирован некоторыми значениями гиперпараметров, и обучение будет происходить со всеми ними.
В случае генетического алгоритма, например, все особи, дающие большие потери, будут устранены, а для следующей итерации будут созданы новые особи. Этот процесс будет повторяться в течение заданного числа итераций.
Точность как функция гиперпараметров в нейронной сети чрезвычайно сложна. Гиперпараметры определяют количество фактических параметров и их значения в нейронной сети. Они определяют весь тренировочный процесс. Итак, вы можете себе представить, насколько сложно было бы представить точность как функцию гиперпараметров. Таким образом, детерминированная оптимизация или простая эвристика не могут решить эту проблему. Вдохновленные природой метаэвристики, основанные на популяции, такие как генетические алгоритмы и оптимизация роя частиц, могут решить их достаточно хорошо.
использованная литература
- Ян, XS (2010). Метаэвристические алгоритмы, вдохновленные природой. Лунивер пресс.
- Кеннеди, Дж., и Эберхарт, Р. (1995, ноябрь). Оптимизация роя частиц. В Материалы Международной конференции по нейронным сетям ICNN’95 (том 4, стр. 1942–1948). IEEE.
Примечания
3. Плохие результаты означают, что полученное значение целевой функции было большим, если это задача минимизации, или малым, если это задача максимизации.
4. Как и в биологии, особи, которые не были отобраны, перекрещиваются (комбинируются каким-либо образом) и применяется некоторая мутация. Полученные особи называются потомками.
