Алгоритм Hedge

Материал из MachineLearning.

Перейти к: навигация, поиск
Статья написана с использованием LLM GPT-5.6 Sol xhigh и проверено участником Aleksandr Iakovlev 09:38, 17 июля 2026 (MSD)


Содержание

Алгоритм Hedge (англ. hedge — страховать, ограничивать риск) — алгоритм онлайнового обучения, который на каждом шаге распределяет вес между конечным числом экспертов или действий, а после получения полной информации об их потерях экспоненциально уменьшает веса неудачных экспертов. Алгоритм конкурирует с лучшим фиксированным экспертом, выбранным задним числом: при ограниченных потерях разность накопленных потерь растёт сублинейно по числу раундов.[1]

Hedge относится к методам обучения с советами экспертов (prediction with expert advice) и к общему семейству multiplicative weights. Его современную форму удобно записывать через экспоненту; в исходной работе использовался параметр \beta\in[0,1]. Названия exponentially weighted forecaster и Hedge иногда употребляются почти как синонимы, однако точное значение зависит от протокола: прогноз может быть выпуклой смесью ответов экспертов либо результатом случайного выбора одного эксперта.

Постановка задачи

Пусть имеются N экспертов. Ими могут быть люди, правила, ранее обученные модели или любые алгоритмы прогнозирования; независимость и вероятностная корректность их советов не предполагаются. Игра длится T раундов. На раунде t:

  1. эксперты сообщают прогнозы, а обучающийся выбирает распределение p_t=(p_{t,1},\ldots,p_{t,N}) на симплексе \Delta_N;
  2. среда раскрывает исход и вектор потерь экспертов \ell_t=(\ell_{t,1},\ldots,\ell_{t,N});
  3. обучающийся несёт смесь потерь \widehat\ell_t=\langle p_t,\ell_t\rangle.

Последняя формула буквально описывает распределение ресурса между действиями. Если обучающийся случайно выбирает эксперта I_t\sim p_t, то она задаёт условное математическое ожидание потери: \mathbb E[\ell_{t,I_t}\mid p_t]=\widehat\ell_t. Если прогнозы лежат в выпуклом множестве, а потеря выпукла по прогнозу, можно выдать взвешенный прогноз. Тогда по неравенству Йенсена его фактическая потеря не больше \widehat\ell_t.[1]

Обозначим накопленные потери

\widehat L_T=\sum_{t=1}^T\widehat\ell_t,\qquad L_{T,i}=\sum_{t=1}^T\ell_{t,i}.

Статическое сожаление (regret) относительно лучшего эксперта равно

R_T=\widehat L_T-\min_{1\leq i\leq N}L_{T,i}.

Цель состоит не в восстановлении «истинного» эксперта, а в обеспечении R_T=o(T) для любой допустимой последовательности потерь. Тогда средняя добавочная потеря R_T/T стремится к нулю. Сравнение проводится с одним и тем же экспертом на всех раундах; сменяющийся оракул является более сильным эталоном и требует других алгоритмов.

Экспоненциальное обновление весов

Пусть \eta>0 — скорость обучения. При равномерном начальном доверии полагают w_{1,i}=1. Перед раундом веса нормируются:

p_{t,i}=\frac{w_{t,i}}{W_t},\qquad W_t=\sum_{j=1}^N w_{t,j}.

После наблюдения всего вектора потерь выполняется обновление

w_{t+1,i}=w_{t,i}\exp(-\eta\ell_{t,i}).

Следовательно,

w_{t+1,i}=\exp(-\eta L_{t,i}),\qquad p_{t,i}=\frac{\exp(-\eta L_{t-1,i})}{\sum_j\exp(-\eta L_{t-1,j})}.

Эксперт с меньшей накопленной потерей получает больший вес, но вес любого эксперта при конечном \eta остаётся положительным. В обозначениях исходного Hedge обновление имеет вид w_{t+1,i}=w_{t,i}\beta^{\ell_{t,i}}. При 0<\beta<1 подстановка \eta=-\ln\beta даёт экспоненциальную форму; крайние значения параметра рассматриваются отдельно или как предел.

Неравномерное априорное доверие задаётся начальными весами w_{1,i}=\pi_i, где \pi\in\Delta_N. Оно усиливает гарантию для заранее правдоподобных экспертов, но ошибочный малый приоритет входит в оценку логарифмическим штрафом.

Псевдокод 

Вход: число экспертов N, скорость обучения eta > 0
Инициализировать w[i] = 1 для i = 1,...,N
Для t = 1,...,T:
    получить текущие советы экспертов
    p[i] = w[i] / sum_j w[j]
    выдать выпуклую смесь советов либо выбрать I ~ p
    получить исход и все потери loss[i] в [0,1]
    для каждого i:
        w[i] = w[i] * exp(-eta * loss[i])

Если наблюдается только потеря выбранного эксперта, строку обновления выполнять нельзя: неизвестные компоненты \ell_{t,i} нельзя считать нулевыми. Это уже задача с бандитской обратной связью.

Граница сожаления

Рассмотрим конечные N\geq2, постоянное \eta>0, полную обратную связь и произвольные, в том числе состязательные, потери \ell_{t,i}\in[0,1]. Для смеси потерь Hedge выполняется детерминированная оценка

R_T\leq\frac{\ln N}{\eta}+\frac{\eta T}{8}.

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

Эскиз доказательства

В качестве потенциала возьмём сумму весов W_t. На одном шаге

\ln\frac{W_{t+1}}{W_t}=\ln\left(\sum_i p_{t,i}e^{-\eta\ell_{t,i}}\right)\leq-\eta\widehat\ell_t+\frac{\eta^2}{8}.

Здесь применена лемма Хёффдинга к случайной величине со значениями в [0,1]. Суммирование по раундам даёт

\ln\frac{W_{T+1}}{W_1}\leq-\eta\widehat L_T+\frac{\eta^2T}{8}.

С другой стороны, сумма весов не меньше веса любого эксперта i. Поскольку W_1=N,

\ln\frac{W_{T+1}}{W_1}\geq-\eta L_{T,i}-\ln N.

Сопоставляя неравенства и минимизируя по i, получаем заявленную границу. Для априорного распределения \pi индивидуальная оценка принимает вид

\widehat L_T-L_{T,i}\leq\frac{\ln(1/\pi_i)}{\eta}+\frac{\eta T}{8}.

Константа 1/8 относится именно к потерям на отрезке [0,1] и смеси потерь. Другие стандартные доказательства используют более грубое квадратичное неравенство и получают член \eta T/2; это не противоречие, а иная константа при тех же асимптотических порядках.

Выбор скорости обучения

При известном горизонте T равномерная оценка минимизируется выбором

\eta=\sqrt{\frac{8\ln N}{T}},

после чего

R_T\leq\sqrt{\frac{T\ln N}{2}}.

Оценка применима при перечисленных выше условиях; при N=1 сожаление тождественно нулю. Если потери лежат в [a,b], где b>a, их можно нормировать на [0,1]. При обновлении в исходном масштабе следует взять \eta=\sqrt{8\ln N/T}/(b-a); тогда граница равна (b-a)\sqrt{T\ln N/2} и имеет порядок (b-a)\sqrt{T\ln N}.

Большое \eta быстро концентрирует массу на текущем лидере и повышает чувствительность к кратковременным неудачам; малое \eta дольше сохраняет почти равномерную смесь. Если T заранее неизвестно, применяют перезапуски на горизонтах, удваивающихся по длине, или варианты с меняющейся скоростью обучения. При тех же предположениях о конечном числе экспертов, полной информации и потерях в [0,1] они сохраняют порядок O(\sqrt{T\ln N}), но конкретная константа зависит от схемы; формулу для постоянного \eta нельзя без доказательства переносить на произвольную последовательность скоростей.

Пример

Пусть есть три эксперта, \eta=\ln2, а начальные веса равны единице. На первом раунде потери равны \ell_1=(0,1,1/2). Распределение равномерно, поэтому

\widehat\ell_1=\frac13\left(0+1+\frac12\right)=\frac12,

а новые веса равны w_2=(1,1/2,1/\sqrt2). Перед вторым раундом их нормировка даёт приближённо

p_2=(0{,}4531,\;0{,}2265,\;0{,}3204).

Если \ell_2=(1,0,1/2), то

\widehat\ell_2\approx0{,}4531+0{,}3204/2=0{,}6133.

После обновления w_3=(1/2,1/2,1/2): накопленная потеря каждого эксперта оказалась равна единице, поэтому распределение снова стало равномерным. Накопленная смесь потерь составляет приблизительно 1{,}1133, а сожаление после двух раундов — 0{,}1133. Пример показывает, что Hedge не обязан на каждом коротком отрезке превосходить лучшего эксперта; гарантия ограничивает накопленный разрыв.

Полная и бандитская обратная связь

В основном протоколе Hedge после каждого исхода известны потери всех экспертов. Это full-information feedback: обновляются все N весов. В задаче многорукого бандита обучающийся видит только \ell_{t,I_t} выбранного действия. Для такого протокола предназначен Exp3.[1]

Exp3 строит оценку неизвестного вектора, например

\widetilde\ell_{t,i}=\frac{\ell_{t,i}\mathbf1\{I_t=i\}}{p_{t,i}},

и подставляет её в экспоненциальное обновление; для контроля дисперсии вероятности должны оставаться положительными, часто за счёт явного исследования. Для N действий, T раундов, потерь в [0,1], подходящей настройки параметров и среды, не реагирующей на текущий реализованный случайный выбор, стандартная ожидаемая гарантия Exp3 имеет порядок O(\sqrt{TN\ln N}), тогда как full-information Hedge — O(\sqrt{T\ln N}). Следовательно, Exp3 использует идею Hedge, но не является тем же алгоритмом. Если при бандитской обратной связи советы дают отдельные эксперты о распределениях на действиях, естественным аналогом служит Exp4, а не простой Hedge.

Связь с другими методами

Multiplicative weights
Это метаметод, объединяющий множество правил мультипликативного обновления в обучении, теории игр и оптимизации. Hedge — его реализация для ограниченных потерь и сравнения с лучшим фиксированным действием. Поэтому всякий Hedge использует multiplicative weights, но не всякий алгоритм multiplicative weights является Hedge.[1]
Weighted Majority
Классический детерминированный алгоритм взвешенного большинства решает прежде всего задачу бинарных предсказаний: ошибившиеся эксперты теряют фиксированную долю веса, а итог определяется пороговым голосованием. Hedge обобщает эту идею на дробные ограниченные потери и распределение действий. Рандомизированные варианты Weighted Majority особенно близки к Hedge, но протокол и вид гарантии следует указывать явно.[1]
Экспоненциально взвешенный прогноз
При выпуклом пространстве прогнозов алгоритм, выдающий среднее советов с весами e^{-\eta L_{t-1,i}}, обычно называют Exponentially Weighted Average Forecaster. В описанной постановке это форма Hedge с детерминированным смешанным прогнозом. Её не следует путать с экспоненциальным скользящим средним, которое усредняет прошлые наблюдения по времени, а не перераспределяет доверие между экспертами по их потерям.
Зеркальный спуск
На симплексе шаг зеркального спуска с отрицательной энтропией, или эквивалентный шаг FTRL, имеет вид
p_{t+1}=\arg\min_{p\in\Delta_N}\left\{\eta\langle p,\ell_t\rangle+D_{\rm KL}(p||p_t)\right\}.
Его решение есть p_{t+1,i}\propto p_{t,i}e^{-\eta\ell_{t,i}}. Тем самым Hedge является энтропийным зеркальным спуском для линейных потерь на симплексе; общий зеркальный спуск допускает другие области, брэгмановские дивергенции и градиенты произвольных выпуклых функций.[1]
AdaBoost
AdaBoost исторически выведен Freund и Schapire из той же теоретико-решающей идеи и также экспоненциально меняет веса. Но в бустинге веса относятся к обучающим объектам, на каждом шаге строится новый слабый классификатор, а его коэффициент зависит от ошибки. В Hedge фиксированный набор экспертов существует заранее и оценивается по последовательности раундов. Это родственные, но не тождественные алгоритмы.

Применения

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

Вычислительная сложность

При явном векторе из N потерь один раунд требует O(N) операций и O(N) памяти; за T раундов — O(TN) времени. Стоимость вычисления самих советов экспертов в эту оценку не входит. Чтобы избежать численного обнуления весов, хранят логарифмы s_{t,i}=-\eta L_{t-1,i} и вычисляют нормировку через log-sum-exp, предварительно вычитая \max_i s_{t,i}.

Ограничения

  • Базовая гарантия требует ограниченных потерь; выбросы необходимо обоснованно ограничивать или масштабировать. Иначе один раунд может разрушить приведённую оценку.
  • Hedge требует полной обратной связи. Подстановка нулей вместо ненаблюдаемых потерь создаёт смещённое обновление и не превращает его в Exp3.
  • Сожаление измеряется относительно лучшего постоянного эксперта. При дрейфе среды нужны рестарты, дисконтирование или алгоритмы, конкурирующие с меняющейся последовательностью экспертов.
  • Явное хранение весов непрактично для огромного или бесконечного класса экспертов без дополнительной структуры.
  • Выпуклая смесь советов допустима не во всяком пространстве решений. При невыпуклой потере гарантия для смеси может не следовать из потерь экспертов; тогда применяют рандомизацию или специальное правило агрегации.
  • Малая regret-оценка является относительной: если все эксперты плохи, Hedge также может иметь большую абсолютную потерю.

См. также

Примечания


Литература

Источник — «http://recognition.su/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Hedge»