Skip to content
This repository has been archived by the owner on Oct 3, 2024. It is now read-only.

Latest commit

 

History

History
190 lines (122 loc) · 23.6 KB

L1-Hyperparameters.md

File metadata and controls

190 lines (122 loc) · 23.6 KB
Raw

Гиперпараметры

Выбор алгоритма и настройка гиперпараметров

Гиперпараметры - это параметры в схеме обучения любого алгоритма предсказания. Сама по себе схема в общем случае выглядит следующим образом:

  1. На вход алгоритма обучения модели $a$ мы подаём гиперпараметры, которые задают поведение алгоритма, и набор данных $X$.
  2. $a$ возвращает некие параметры $\delta$.
  3. Далее, на вход алгоритма предсказания $a_{\delta}$ мы подаём $\delta$ и объект $x$.
  4. $a_{\delta}$ возвращает некое предсказание $y$.

Исходя из этого, гиперпараметры - это:

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

На самом деле, для нахождения гиперпараметров (как части данных) можно также установить задачу оптимизации как и в случае с $\delta$. Пусть имеется

  • $\mathcal{D}$ - набор данных;
  • $A$ - алгоритм обучения;
  • $p$ - гиперпараметры алгоритма обучения;
  • $\mathcal{L}$ - функция ошибки (валидация);

Тогда нашей задачей оптимизации будет нахождение $\argmin$ ошибки по нашим гиперпараметрам от алгоритма и данных:

$$ p_{\text{best}} = \argmin_{p}{\mathcal{L}(A_{p}, \mathcal{D})} $$

Поиск нужных гиперпараметров мы можем рассматривать как часть обучения. Будем считать, что у нас есть множество гиперпараметров $P = {p_1, ~ p_2, ~ \ldots}$. Разделим набор данных $X$ на два подмножества: $X_{\mathtt{train}}$ и $X_{\mathtt{valid}}$, где валидационное множество обычно считается 25% от всей выборки $X$. Схема настройки гиперпараметров:

  • Будем перебирать гиперпараметры $p_i$ и запускать алгоритм обучения модели $a$ на $p_i$ и $X_{\mathtt{train}}$.
  • $a$ возвращает некие параметры модели $\delta_i$.
  • Далее, на вход алгоритма предсказания $a_{\delta}$ мы подаём $\delta_i$ и объект из $X_{\mathtt{valid}}$.
  • $a_{\delta}$ возвращает некое предсказание $y$.
  • $y$ подаём в функцию ошибки (валидации) и на основе его значения либо запомним $p_i$, либо сможем выбрать более оптимальные, лучшие параметры $p_j$.
  • Наконец, $p_{\text{best}}$ вместе с набором данных $X$ подаём в алгоритм обучения модели $a$ и получаем финальные параметры модели $\delta_{\text{best}}$.

Точно такую же задачу можно задать на выборе алгоритма $A_{\text{best}}$ для набора данных $\mathcal{D}$ относительно ошибки $\mathcal{L}$:

$$ A_{\text{best}} = \argmin_{A}{\mathcal{L}(A, \mathcal{D})} $$

А если хотим совместить? С одной стороны, мы могли бы выбирать алгоритм настройкой гиперпараметров, тогда:

  • Рассмотрим несколько алгоритмов обучения $A^1, ~ A^2, ~ \ldots$
  • с соответствующими списками гиперпараметров ${p^1_1, ~ p^1_2, ~ \ldots}$, ${p^2_1, ~ p^2_2, ~ \ldots}$, $\ldots$

Мы бы построили универсальный алгоритм $A^u$ со списком гиперпараметров ${c, ~ p^1_1, ~ p^1_2, ~ \ldots, ~ p^2_1, ~ p^2_2, ~ \ldots}$, где гиперпараметр $c$ указывает на выбираемый алгоритм $A^c$.

С другой же, мы могли бы получить набор гиперпараметров выбором алгоритма, тогда:

  • Специализируем алгоритмы $A^1, ~ A^2, ~ \ldots$ соответствующими гиперпараметрами ${p^1_1, ~ p^1_2, ~ \ldots}$, ${p^2_1, ~ p^2_2, ~ \ldots}$, $\ldots$
  • Получим список алгоритмов для выбора $A^1_1, ~ A^1_2, ~ \ldots, A^2_1, ~ A^2_2, ~ \ldots$

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

Есть два основных подхода к конфигурации: линейный подход (pipeline) и древовидный подход:

  • Линейный подход. Мы задаём линейный конвейер обработки набора данных $X$ с помощью разных алгоритмов и гиперпараметров для получения конкретных параметров, которые затем используются в следующем алгоритме и гиперпараметрах, чтобы получить следующие параметры модели.
  • Древовидный подход. Мы делим каждую сущность (будь то алгоритм или гиперпараметры) на дерево с вершинами: вершина ИЛИ - выбирается один из $n$, вершина И выбираются все, и Лист - обычно, это неделимые данные.

Методы поиска гиперпараметров

Поиск по сетке (Grid search)

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

Грубо говоря, полный перебор вариантов. Мы можем оптимизировать потребляемую память, получая значения "на лету" (например, простейшие преобразования).

Какие проблемы? Очевидно, что такой подход требует слишком много времени: для $d$ гиперпараметров, у которых $k$ значений потребуется $k^d$ итераций. Причем, мы не можем в легкую рассчитать время работы: взяв слишком много параметров значений, мы рискуем выйти за границу дозволено по времени, с другой стороны, если мы уменьшим число таких параметров, то не факт, что мы выберем лучшие параметры для модели.

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

Случайный поиск (Random search)

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

В чём есть преимущества? В отличии от сетки, мы не берем какой-то шаг выбора параметров для гиперпараметров, а значит у нас появляется больший шанс выбрать, например, тот вариант, который будет лучший, но лежит между двумя значениями сетки параметров. Может работать с гиперпараметрами у которых бесконечное число значений (так как мы выберем какое-то множество из $\mathtt{n_iter}$) и не требует использовать древовидную конфигурацию.

В чём проблемы? Если у нас есть категориальные параметры, то, из-за случайного выбора, может получиться так, что некоторые комбинации с категориями могут повторяться, а некоторые могут быть вообще не рассмотрены. Например, для получения всех $n$ значений требуется в среднем $\mathcal{O}(n\log{(n)})$ повторов, в то же время сетка всегда делает $\mathcal{O}(n)$ итераций, чтобы перебрать все категории.

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

Как же выбрать распределение? Существует следующие рекомендательные виды при трёх случаях:

Иногда виды распределений смешивают, чтобы получить более "честный" результат выбора. Например, если на некотором отрезке встречаются значения из интервала $[0, 1]$, то есть смысл сменить вид с равномерного, например, на нормальное, так как наше абсолютное смещение в районе нуля будет всегда наибольшим.

Оптимизация чёрного ящика (Black-Box Optimization)

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

  • Если выходное значение функции $\mathcal{L}$ достиг желаемого минимума при некотором фиксированном времени (грубо говоря, $\varepsilon$).
  • Если количество вызовов функции $\mathcal{L}$ достиг максимального количества вызовов (грубо говоря, количество итераций).

В Black-Box у нас бывают задачи решения оптимизации абстрактных и числовых объектов.

При оптимизации абстрактных объектов помимо функции ошибок $\mathcal{L}$ нам иногда нужны операторы:

  • Генерация - создаёт новый объект

    $$ \mathtt{rand}() ~ : ~ X $$

  • Мутация - создаёт из объекта $x$ новый объект $x'$, который похож на $x$

    $$ \mathtt{mutate}(x) ~ : ~ X \to X $$

  • Кроссовер - создаёт из двух объектов третий, который одновременно похож на первый и второй

    $$ \mathtt{cross}(x_1, ~ x_2) ~ : ~ X \times X \to X $$

При оптимизации в числовом пространстве мы считаем $X = \mathbb{R}^m$ и это позволяет нам проводить больше по количеству операций (а также более легковесные). Численные методы по сути являются частным случаем абстрактных, то есть мы можем легко предложить вышеописанным оператором аналогичные числовые операторы. Ещё одно из преимуществ такой оптимизации: вместо небольшого изменения каждой координаты, можно менять случайное подмножество координат.

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

Байесовская оптимизация

Здесь мы используем так называемую суррогатную функцию $a(x)$ для аппроксимации функции ошибок $\mathcal{L}(x)$, причем в отличии от неё она вычисляется во много быстрее. Возникает дилемма исследования и использования: хочется как можно лучше аппроксимировать и найти минимум $\mathcal{L}(x)$.

Ещё данную оптимизацию называют частным случаем обучения с подкреплением. Здесь нам нужны алгоритмы машинного обучению для аппроксимации, так как там вектор гиперпараметров становится вектором признаков для обучения.

Проблема числовых и категориальных гиперпараметров

Обычно, в машинном обучении, мы стараемся работать с векторами (пакетами) чисел: категории мы приводим к One-Hot кодированию (битовый вектор) и обрабатываем по своему, числовые значения оставляем как есть. Обычно, мы подаём алгоритму функцию ошибки и не задумываемся, и казалось бы, мы также могли бы сделать при смешивании двух видов значений, но это не так:

  • В одном случае функция ошибки берёт $x \in \mathbb{R}$ и возвращает ошибку

    $$ \mathcal{L}(\mathbb{R}^m) \to \mathtt{Err} $$

  • В другом же - мы берём на вход гиперпараметры и возвращаем ошибку

    $$ \mathcal{L}(P) \to \mathtt{Err} $$

А если мы хотим иметь гиперпараметры, в которых встречаются числовые параметры, то нам нужна промежуточная функция преобразования $\mathbb{R}^M \to P$. И на этом этапе могут возникнуть проблемы и разногласия:

  • Пусть числа - это и есть целочисленные значения, тогда

    $$ \begin{aligned} 0.1 \rightarrowtail 0 \to \mathtt{Err}1 \ 0.2 \rightarrowtail 0 \to \mathtt{Err}{\underline{\mathbf{1}}} \end{aligned} $$

    То есть, мы хоть и изменили значение, но алгоритм считает, что ничего не изменилось.

  • Тоже самое происходит и с категориями. Мы сделали One-Hot кодирование, а затем вернули категориальные значения с помощью $\argmax$, тогда

    $$ \begin{aligned} [0.1, ~ 7, ~ -3] \rightarrowtail 2 \to \mathtt{Err}_1 \ [0.1, ~ 6, ~ -3] \rightarrowtail 2 \to \mathtt{Err}1 \ [0.1, ~ 7, ~ 6] \rightarrowtail 2 \to \mathtt{Err}{\underline{\mathbf{1}}} \end{aligned} $$

    Казалось бы, на третьей итерации у нас произошли сильные изменения в отличия от первой и должна была быть другая ошибка, но из-за $\argmax$ - ровно та же.

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

Тоже самое касается линейной конфигурации. Возьмем модель SVM и приведем гиперпараметры: $C$, $\mathtt{kernel} = {\mathtt{poly}, ~ \mathtt{gauss}}$, $\gamma$, d.

  • если выбрано ядро $\mathtt{poly}$, то от изменения $\gamma$ функция ошибки не изменится. Аналогично с ядром $\mathtt{gauss}$ и гиперпараметром $d$
  • если модифицируются сразу все числовые гиперпараметры, то изменение одного из них может ухудшить гиперпараметр для одного ядра и улучшить для другого, но целевая функция будет вычислена только для текущего выбранного ядра.