Жадная альтернатива настройке гиперпараметров
Эта история покажет вам альтернативный алгоритм случайного поиска, который может быть полезен для настройки гиперпараметров. Я раскрою основную концепцию этого и приведу подробный пример алгоритма.
- Что такое жадный алгоритм?
- Концепция глубокого случайного поиска
- Обсуждение
Что такое жадный алгоритм?
В информатике используется алгоритм для систематического решения проблем. Есть много концепций о том, как разработать алгоритм. Жадное понятие - одно из самых основных. Решение определяется пошагово, и жадный алгоритм принимает свое решение (для решения проблемы на определенном этапе) на основе текущего наилучшего доступного решения. Давайте рассмотрим пример и посмотрим на рисунок 1. Вы можете увидеть дерево с взвешенными краями. Цель состоит в том, чтобы минимизировать общие затраты, чтобы добраться от узла A до узла F.
Правильный ответ - A-C-E-F. Однако жадный алгоритм выберет A-B-D-F. Либо выберите узел B, либо выберите узел C в начале, и жадный алгоритм, очевидно, выберет узел B над узлом C. Я должен признать, что это довольно неблагоприятный пример для жадного алгоритма, но он показывает слабость такого алгоритма. Жадный алгоритм находит решение, но нет гарантии, что это лучшее решение в целом.
Концепция глубокого случайного поиска
В случайном поиске вы просто проверяете случайную комбинацию гиперпараметров, лежащих в указанном диапазоне. Алгоритм делает предположения наугад. В глубоком случайном поиске (DRS) вы делаете то же самое, но после определенного количества предположений вы обновляете диапазоны своих гиперпараметров. Следующий пример демонстрирует алгоритм.
На рисунке 2 показан простой случайный поиск в двух измерениях, A и B. Начальные диапазоны на уровне 1 - [A0; A1] и [B0; B1]. После определенного количества предположений диапазон каждого измерения сокращается вдвое, и теперь у вас есть четыре (только в 2D) квадранте. В n измерениях вы получите 2 в степени n квадрантов, если разрезать каждое измерение пополам. Лучшее решение, найденное на данный момент, находится в первом квадранте. Это тот, который мы поднимаем на уровень 2.
На уровне 2 мы сначала должны указать новые диапазоны (показанные на рисунке 3), а затем сделать то же самое снова. Предположения, сделанные на уровне 2, обозначены красным цветом (синие - на уровне 1). Новое лучшее решение расположено во втором квадранте. И снова, это квадрант, который мы переходим на уровень 3, последний уровень.
Как и раньше, после указания новых диапазонов выполняется случайный поиск (предположения, сделанные на уровне 3, отображаются зеленым цветом). Теперь мы снова можем определить лучшее решение, которое представляет собой решение нашего глубокого случайного поиска.
Обсуждение
Глубокий случайный поиск - это жадный многоуровневый случайный поиск. На каждом уровне выполняется случайный поиск, и диапазоны измерений обновляются в соответствии с наиболее известным решением. Обновление диапазонов - это жадная часть DRS. Лучшее решение может быть расположено в другом квадранте, чем самое известное решение, и теперь DRS больше не может найти общее лучшее решение. В этом слабость DRS.
Однако DRS может помочь найти новые хорошие решения и новые диапазоны для ваших гиперпараметров для дальнейших исследований и анализа. Также вы можете попробовать разные методы обновления диапазонов. Например, вы можете очень много сокращений, которые вы выполняете на каждом уровне (по одному для каждого измерения в этом примере). Или вы определяете новый метод определения квадранта, который выходит на следующий уровень. В этом примере мы взяли квадрант, который включает наиболее известное решение. В качестве альтернативы вы можете определить индекс производительности для каждого квадранта, на который влияет каждое предположение в квадранте. Количество предположений, которые вы делаете на каждом уровне, и количество уровней являются общими параметрами DRS.
