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

Некоторыми быстрыми примерами гиперпараметров могут быть learning rate в алгоритмах на основе градиента или depth of a tree в алгоритмах на основе дерева решений, которые могут напрямую влиять на способность модели точно соответствовать обучающим данным. Гиперпараметры регуляризации, такие как условия регуляризации L1 или L2, могут помочь модели лучше обобщать новые данные за счет ограничения сложности модели. Для алгоритмов итеративной оптимизации, таких как стохастический градиентный спуск, гиперпараметры, такие как learning rate и momentum, могут влиять на то, насколько быстро модель сходится к минимуму. Гиперпараметры, связанные со сложностью модели (например, глубина дерева решений, number of layers в нейронной сети), могут привести к переобучению, если установлено слишком высокое значение, и недостаточному подбору, если установлено слишком низкое значение.

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

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

Это будет длинная статья (возможно, в обучении нет последовательного деления пополам), так что расслабьтесь, возьмите чашку кофе и наслаждайтесь :)

Уменьшение успеха вдвое

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

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

Бандитские алгоритмы

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

Задача о многоруком бандите
Представьте себе игрока, стоящего перед рядом игровых автоматов (или «одноруких бандитов»). Каждая машина предоставляет разную, неизвестную вероятность вознаграждения. Игрок хочет максимизировать общее вознаграждение за серию нажатий рычага. Задача состоит в том, чтобы найти оптимальную стратегию распределения запросов между машинами, чтобы максимизировать ожидаемое совокупное вознаграждение. Это предполагает компромисс:

Исследование: игрок использует различные рычаги, чтобы получить больше информации об ожидаемом вознаграждении от каждого автомата.

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

Алгоритмы бандита при последовательном уменьшении пополам
Последовательное сокращение пополам использует структуру Multi-Armed Bandit для решения проблемы оптимизации гиперпараметров. Каждая рука бандита соответствует отдельной конфигурации гиперпараметров, и выдергивание руки похоже на оценку конфигурации с определенным вычислительным бюджетом. «Награда» — это показатель производительности, который вы оптимизируете, например точность или рейтинг F1.

Типы бандитских алгоритмов

Эпсилон-жадный: этот подход всегда использует самый известный вариант, за исключением эпсилон-доли времени, когда он случайным образом исследует другие варианты.

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

Выборка Томпсона: используется байесовский подход, поддерживающий распределение вероятностей по ожидаемому вознаграждению для каждой руки и выборку из этих распределений для выбора руки.

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

Связь с Минимизацией сожалений
Конечная цель — минимизировать «сожаление», которое представляет собой разницу между совокупным вознаграждением, полученным за следование выбору алгоритма, и совокупным вознаграждением за всегда выбор лучшего варианта. Последовательное сокращение вдвое призвано свести к минимуму это сожаление путем агрессивного сокращения менее перспективных вооружений и перераспределения ресурсов в пользу более эффективных.

Вычислительный бюджет

Общий объем вычислительных ресурсов, выделенных для задачи, обычно измеряется в эпохах для нейронных сетей или в итерациях для таких алгоритмов, как повышение градиента.

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

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

Повышение градиента. Бюджетом может быть количество итераций повышения или количество деревьев в ансамбле.

Варианты распределения бюджета

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

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

Бюджет в параллельных вычислениях

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

Конфигурация

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

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

Скорость обучения: определяет размер шагов, предпринимаемых во время оптимизации.
Условия регуляризации: контролируйте сложность модели, чтобы предотвратить переобучение.
Количество слоев или единиц: для нейронных сетей влияет на емкость модели.
Раунды повышения: для ансамблевых методов, таких как повышение градиента, определение количества объединенных слабых учащихся.

Оценка конфигураций
Каждая конфигурация проходит процесс оценки, чтобы определить, насколько хорошо она работает на проверочном наборе. Метрикой оценки может быть что угодно: от точности и оценки F1 до более специфичных для предметной области показателей, таких как площадь под кривой (AUC) для задач классификации.

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

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

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

Допустим, вы начинаете с конфигураций N и коэффициента уменьшения η (эта). После каждого раунда только N/η конфигураций переходят в следующий раунд, и каждая выжившая конфигурация получает в η раз больше вычислительного бюджета, чем раньше. Эффективность алгоритма обусловлена ​​его способностью быстро отбрасывать неэффективные конфигурации, концентрируя вычислительные ресурсы на тех, которые дают многообещающие результаты. Этот механизм позволяет последовательному халвингу более эффективно исследовать пространство гиперпараметров, обеспечивая более высокую вероятность нахождения почти оптимальной конфигурации при сохранении ограниченного вычислительного бюджета.

Алгоритмическое прохождение последовательного халвинга

Некоторые концепции легче понять с помощью кода, чем просто теории. Следовательно. Я создал пример с использованием XGBoost для быстрого ознакомления с алгоритмом последовательного халвинга, а затем углубился в алгоритмические этапы.

"""
Author: Viresh Jivane

Description: 
This python program demonstrates application of Successive Halving
for hyperparameter tuning using XGBoost and scikit-learn's digits dataset.

Dependencies: 
- scikit-learn
- xgboost
- numpy
- prettytable
"""

import itertools
import numpy as np
from xgboost import XGBClassifier
from prettytable import PrettyTable
from sklearn.datasets import load_digits
from sklearn.metrics import accuracy_score
from sklearn.model_selection import StratifiedShuffleSplit, train_test_split

ptable = PrettyTable()
ptable.field_names = ["Num Configs", "Best Config", "Accuracy"]
digits = load_digits()
X, y = digits.data, digits.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

N = 100  # number of configurations
eta = 2  # pruning factor. less aggressive
r = 250  # minimum budget
# configuration combinations with 'max_depth' and 'learning_rate'
max_depth_values = list(range(2, 10))
learning_rate_values = [0.001, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5]
all_combinations = list(itertools.product(max_depth_values, learning_rate_values))
initial_configs = [{'max_depth': md, 'learning_rate': lr} for md, lr in all_combinations][:100]
configs = initial_configs.copy()
final_best_config = None
final_best_accuracy = 0.0

# tuning + pruning interations
while len(configs) > 1:
    n = len(configs)
    r_i = r
    n_i = int(np.ceil(n / eta)) # no. of configs to keep after pruning
    splits= StratifiedShuffleSplit(n_splits=1, test_size=None, train_size=r_i)
    for train_index, _ in splits.split(X_train, y_train):
        X_subset = X_train[train_index]
        y_subset = y_train[train_index]

    performance = {}
    for config in configs:
        model = XGBClassifier(**config)
        model.fit(X_subset, y_subset)
        y_pred = model.predict(X_test)
        performance[str(config)] = round(accuracy_score(y_test, y_pred), 3)

    # prune after sort
    sorted_configs = sorted(configs, key=lambda x: -performance[str(x)])
    configs = sorted_configs[:n_i]
    # increment budget
    r_i *= eta
    best_config_str = max(performance, key=performance.get)
    ptable.add_row([len(configs), best_config_str, performance[best_config_str]])

    if performance[best_config_str] > final_best_accuracy:
        final_best_config = best_config_str
        final_best_accuracy = performance[best_config_str]

print("Configurations and their Accuracies:")
print(ptable)
final_ptable = PrettyTable()
final_ptable.field_names = ["Final Best Config", "Final Best Accuracy"]
final_ptable.add_row([final_best_config, final_best_accuracy])
print("Final Best Configuration:")
print(final_ptable)

Давайте разберемся в приведенном выше коде с линзой последовательного халвинга.

Инициализация
Алгоритм инициализируется путем выборки большого набора конфигураций (N). Эти конфигурации предназначены для гиперпараметров 'max_depth' и 'learning_rate'.

Распределение ресурсов
Начальный бюджет вычислений (r) определяется для каждой конфигурации. Этот бюджет относится к количеству точек данных, используемых для первоначального обучения модели. Бюджет используется для ограничения ресурсов и времени, затрачиваемых на конфигурации, которые могут оказаться неоптимальными.

Обучение и оценка
Каждая выборочная конфигурация обучается с использованием r в качестве вычислительного бюджета. Производительность конфигурации оценивается с использованием точности. В случае последовательного сокращения пополам раунды ранней остановки (r) действуют как вычислительный бюджет. Каждая модель обучается до тех пор, пока не достигнет r раундов без улучшения производительности.

Сокращение
После обучения и оценки всех конфигураций они сортируются по производительности. (N/η) конфигураций с наихудшей производительностью отбрасываются. Это часть алгоритма, разделяющая пополам.

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

Итерация
Алгоритм повторяет этапы обучения и оценки, сокращения и увеличения ресурсов до тех пор, пока не останется только одна конфигурация. Это гарантирует, что только наиболее перспективным конфигурациям будет предоставлено больше ресурсов, а менее перспективные будут удалены раньше.

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

Плюсы последовательного халвинга

  • Эффективность использования ресурсов. За счет итеративного сокращения менее перспективных конфигураций последовательное сокращение пополам позволяет лучше использовать вычислительные ресурсы.
  • Быстрое устранение. Неэффективные конфигурации удаляются на ранней стадии, что экономит время.
  • Масштабируемость: подходит для многомерных пространств гиперпараметров, поскольку не требует исчерпывающего поиска.

Минусы последовательного халвинга

  • Риск преждевременного сокращения. На первых этапах с ограниченными ресурсами могут быть исключены конфигурации, которые могли бы работать лучше при большем количестве ресурсов.
  • Зависимость от параметра. Производительность может зависеть от собственных гиперпараметров, таких как η и r.
  • Недостаток исследования. Алгоритм может застрять в локальных оптимумах и недостаточно исследовать все конфигурационное пространство.

Заключение

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

Использованная литература: