Оценка снизу регрета алгоритма агрегирования экспертных прогнозов для переменного числа активных экспертов

В работе [1] рассмотрена задача прогнозирования временного ряда с постоянно растущим множеством экспертов. Результат прогнозирования сравнивается с ретроспективно самым лучшим составным результатом экспертов, состоящим из к элементарных. Там же предложен алгоритм решения этой задачи и таким образом установлена верхняя оценка регрета R t = О(к ln Т ). Настоящая работа устанавливает нижние оценки регрета.

Вклад работы заключается в следующем:

Теорема 1 дает оценку регрета в ситуации, когда длина игры заранее известна экспертам и Природе. Следствие 1 рассматривает ситуацию когда игра не слишком короткая (m > mo ^ Т >  2^т0), а эксперты сменяются не слишком часто (к <  аД, в этой ситуации

• (с) Зухба Р. Д., Зухба А. В., 2025

(с) Федеральное государственное автономное образовательное учреждение высшего образования

«Московский физико-технический институт (пациопальпый исследовательский университет)», 2025

работает оценка R t > C i k ln Т. Теорема 2 рассматривает случай, когда длина игры заранее неизвестна игрокам. Следствие 2 показывает, что если игра не слишком короткая, то работет оценка R t > C 2 k 1пТ. Таким образом, в сценариях из теорем 1 и 2 выполняется оценка R t = ^(k 1nT), то еств порядок роста нижней оценки совпадает с порядком роста верхней оценки из работы [1].

Теорема 3 показывает, что если элементарные эксперты сменяются часто, k > aT, а = const, то регрет пропорционален длине игры Т. Таким образом, любой алгоритм агрегации работает не намного лучше, чем самый худший алгоритм.

Теорема 4 в явном виде доказывает оценку снизу на регрет решения задачи, поставленной в работе [2].

• 1.1.    Прогнозирование с использованием экспертных стратегий

Прогнозирование с использованием экспертных стратегий имеет форму игры с двумя участниками: Природа и Предсказатель.

Природа генерирует неизвестную другим участникам последовательность {_У 1 ,У 2 , ... ,Ут } элементов множества исходов Y.

Задачей Предсказателя является предсказание этой последовательности. Он может выдавать прогнозы у из множества Г, которое обычно является выпуклым подмножеством конечномерного пространства.

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

У Предсказателя есть доступ к набору прогнозирующих алгоритмов, называемых экспертами i G Х, где Х - некоторое индексное множество. Каждый эксперт на каждом шаге игры дает свой прогноз f^t, i G Х и Предсказатель строит свой прогноз yt на их основе.

После этого Природа сообщает истинное значение y_t и вычисляются потери li,t = ^(fi,t,yt) экспертов и потери h_t = X(y_t,y_t) Предсказателя, где X(y,y) : Г х Y ^ R -функция потерь, которая принимает неотрицательные значения.

Важной особенностью данного подхода является то, что Предсказатель не пользуется никакими предположениями о природе прогнозируемой последовательности {yt}- Она может быть случайной или детерминированой, возможно Природа выбирает исходы в зависимости от прогноза Предсказателя. Поведение Природы может быть даже адаптивно-враждебным, то есть исходы выбираются так, чтобы максимизировать потери Предсказателя.

Эту постановку задачи можно рассматривать как повторяющуюся игру между Предсказателем, который дает прогнозы y_t, и Природой, которая выбирает прогноз экспертов fi,t и истинньie исходы y_t.

Игра 1. Прогнозирование с использованием экспертных стратегий

FOR t = 1, 2,...,Т

• 1)    Природа выбирает следующий истинный исход y_t, ио не сообщает его Предсказателю.

• 2)    Для каждого эксперта i G Х Природа представляет предсказание f i,_t.

• 3)    Предсказатель также представляет свое предсказание y_t.

• 4)    Участники игры получают истинное значение y _t и несут потери: l i, _t = X(f i, _t ,y _t ) - потери эксперта i, h _t = X(y _t ,y _t ) - потери Предсказателя.

ENDFOR

т

В конце игры подсчитываются суммарные потери Предсказателя Нт = ^J h_t и суммар-t=i

т ные потери каждого эксперта Li,T = 52 Kt, i ^ -А.

t =i '

Задачей Предсказателя является минимизация величины регрета, который в классической постановке1 определяется как Rt = Нт-minLiT- Эту величину можно рассматриватв ieH ’ как меру сожаления Предсказателя о том, что он не послушался советов одного, самого лучшего в ретроспективе, эксперта.

• 1.2.    Составные эксперты

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

Рассмотрим разбиение всего интервала прогнозирования 1 .. .Т на подынтервалы Aj = \tj- i ,tj — 1], ^ГД^е 1 = t o < ^1 < ... < tk = Т + 1. Каждому такому подынтервалу поставим в соответствие эксперта ij, j = 1 .. .к. Такой набор интервалов и соответствующих им экспертов назовем составным экспертом Е = (ii, Ai,... ,ij, Aj, ... ,ik , Ak), а составляющие его эксперты будут называться элементарными. Составной эксперт на каждом из интервалов Aj дает такие же прогпозы. как и эксперт ij.

Суммарные потери элементарного эксперта ij на интервале Aj обозначим L {^ j ) (ij ) = ^2 К-t ^а суммарные потери составного эксперта Е на всем временном ^te ^ _j

k интервале обозначим Lt(Е) = 52 L(^.)(ij). Теперь регретом называется величина j=i     3

Rt = Нт — min Lt(Е). где минимум берется по всем составным экспертам, состоящим из к Е элементарных. Эту величину можно рассматривать как меру сожаления Предсказателя о том, что он на каждом из интервалов Aj не послушался советов эксперта ij, где разбиение на подынтервалы и выбор соответствующих экспертов оптимальны в ретроспективе. Требуется построить такой алгоритм прогнозирования, чтобы минимизировать регрет для любого поведения остальных участников игры (экспертов и Природы).

Предложеный в работе [2] алгоритм называется Fixed Share, его регрет

R t ба

к + 1

V

ln N +— ln

( %)^k (1 — of -^k-1

рТ

+ T ■

Ниже в теореме 4 мы предлагаем доказательство оценки снизу R > Ск lnN на регрет любого алгоритма, решающего эту задачу.

• 1.3.    Растущее множество экспертов

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

Игра 2. Прогнозирование с использованием экспертных стратегий для растущего множества экспертов

FOR t = 1 , 2,...,Т

• 1)    Природа выбирает следующий истинный исход y_t, ио не сообщает его Предсказателю.

• 2)    Активируется еще один эксперт i = t.

• 3)    Для каждого активного эксперта i = 1 .. .t Природа представляет предсказание f i, _t.

• 4)    Предсказатель также представляет свое предсказание y_t.

• 5)    Участники игры получают истинное значение y _t и несут потери: l _i , _t = A(f _i , _t ,y_t') ~ потери эксперта i, h _t = A(y _t ,y _t ) - потери Предсказателя.

• 2.    Оценка регрета снизу

ENDFOR

Точно так же, как и в работе [2], рассматриваются составные эксперты Е = (ii, Ai,...,ij, Aj,... ,ik, Ak), но накладывается дополнительное условие что эксперт ij должен быть активирован к началу интервала Aj.2 Рассматривается регрет Rt = Нт-minLt(Е), где минимум берется по всем таким составным экспертам, состоящим Е из к элементарных.

В работе [1] предложен алгоритм решения этой задачи и доказана оценка на его регрет

R t < 1(к + 1)(2lnln(T + 1)+ln с) + -(2к + 3)ln(T + 1) = О(к ln Т ). Г]                                                        Г]

Для оценки регрета снизу рассмотрим модифицированную версию игры, в которой Природа может выбирать исходы в зависимости от прогнозов Предсказателя. Такой подход рассматривался, например, в работе [6].

Игра 3. Прогнозирование с использованием экспертных стратегий для растущего множества экспертов с адаптивным поведением Природы

FOR t = 1, 2,...,Т

• 1)    Активируется еще один эксперт i = t.

• 2)    Для каждого активного эксперта i = 1 .. .t Природа представляет предсказание f _i , _t.

• 3)    Предсказатель также представляет свое предсказание y_t.

• 4)    Природа выбирает следующий истинный исход y _t и сообщает его Предсказателю.

• 5)    Участники игры несут потери: l _i , _t = A(f _i , _t ,y _t ) - потери эксперта i, h _t = A(y _t ,y _t ) - потери Предсказателя.

ENDFOR

В следующих теоремах предложены (адаптивно враждебные) стратегии Природы для разных сценариев проведения игры.

В играх ниже все отклики yt будут лежать на отрезке [—1,1]. Пусть функция потерь А(у, y) удовлетворяет (достаточно слабым и естественным) условиям A(y,y) = 0; V^y ^: Ь — y| — 1 ‘^ A(y,y) — 1- В частности, этим условиям удовлетворяет квадратичная функция потерь A(y,y) = (у — y)², которая использовалась в работе [1].

Лемма 1. Пусть в игре 3 к некоторому шагу s активировано не менее, чем 2^т экспертов. Тогда существует такая стратегия Природы, что для любого поведения Предсказателя в течение следующих т шагов игры, Предсказатель несет суммарные потери не меньше т, а один из экспертов несет суммарные потери 0.

Доказательство. Существенную роль будут играть 2^т экспертов. Остальные эксперты, в том числе те, которые будут активированы в течение следующих шагов, тоже выдают какие-то прогнозы, но существенно не влияют на прохождение игры.

Рассмотрим конечные последовательности (fli,d2,...,o_m)₁ все члены которых принимают значения или 1 ил и —1. Всего существует 2^т таких последовательностей, сопоставим каждую из них одному из 2^т экспертов. Стратегия каждого эксперта состоит в том, что он выдает члены своей последовательности в качестве прогнозов в течение следующих т шагов, то есть fi,_s+n = d_n.

На каждом шаге Предсказатель дает прогноз y_t. Стратегия Природы состоит в том, чтобы давать отклик по правилу

{ 1, если у < 0,

• —1, если у > 0.

Тогда на каждом шаге выполняется |у- — yt| > 1, значит, ht = X(yt,yt) > 1, значит, за т s+m шагов Предсказатель несет суммарные потери £ ht > т.

t=s+1

На каждом шаге Природа давала отклики 1 ил и —1, значит, найдется такой эксперт, который на каждом шаге давал точный прогноз, значит, он несет суммарные потери 0. Лемма доказана. □

Теорема 1. Пусть к,т - натуральные числа. Тогда существует такая стратегия Природы в игре 3, длящейся Т = 2^т + кт шагов, что для любого поведения Предсказателя выполняется

Ry = Н т — min Ту (Е ) >  кт,

Е где минимум берется по всем составным экспертам, состоящим из к + 1 элементарных.

Доказательство. Разобьем интервал прогнозирования [1,Т] на подынтервалы

△ 1 = [1, 2^m ], An = [2^т + (п — 2)т + 1, 2^т + (п — 1)т], п = 2,...,к + 1.

На интервале Ai все эксперты дают прогнозы, равные 0, а Природа дает отклик y_t = 0. Таким образом активируются 2^т экспертов и каждый из них несет нулевые суммарные потери за этот период. Поскольку функция потерь неотрицательна, Предсказатель несет неотрицательные потери за этот период. Эксперты, которые будут активированы на последующих шагах, выдают какие-то прогнозы, но существенно не влияют на прохождение игры.

На интервале A2, то есть в течение следующих т шагов, эксперты и Природа реализуют стратегию из леммы 1. За эти т шагов Предсказатель несет суммарные потери не меньше т. а один из экспертов песет суммарные потери 0. пазовом этого эксперта i2-

На каждом из интервалов A3,..., A^+i эксперты и Природа повторяют стратегию из леммы 1. Экспертов, которые несут суммарные потери 0, в течение этих периодов, назовем i3,i4,... ,ik+1-

Таким образом, за Т = 2^т+кт шагов Предсказатель несет суммарные потери Н _т >  кт.

Рассмотрим составного эксперта Е = (1, A₁,i₂, A₂,..., i_n, A_n,... ,i/_s+₁, Ak+₁). Поскольку каждый из этих элементарных экспертов несет нулевые потери на соответствующем периоде игры, то суммарные потери Ту(Е ) составного эксперта Е также равны нулю. Тогда регрет Предсказателя

R t = Ну — min Ту (Е ) >  кт — 0.

Теорема доказана. □

Следствие 1. Пусть в условиях теоремы 1 дополнительно известно, что существуют такие константы то > 1 и а <     что т > то, к < аТ. Тогда выполняется оценка

2 т о

R t >  кт >  C i k ln Т, где Pi - некоторая константа, то есть R t = П(к 1пТ).

Действительно, к < аТ = а(2т + кт). Решая это неравенство, получим т      13— тт      1 тт    тт к < У2— < 2то 2  < -тД- = 2-,

• 1    — ат 1 — Д—т 1 — С-т  т

2то          2т значит, Т = 2т + кт < 2т + 2т, тогда т> 1од2Т — 1 = (1П2 — 1ПТ)1пТ'

Так как Т = 2т + кт > 2т > 2т0, тогда 1пТ > то 1п2, значит, т> (512-i)1пТ = C11пТ,

'значит. R _t >  кт > C_ik 1пТ. □

Заметим, что каждый из экспертов в теореме 1 выдавал точный прогноз в течение первых 2^т шагов, но это всё равно не позволяет эффективно агрегировать прогнозы этих экспертов на последующих кт шагах.

Теорема 2. Существует такая стратегия Природы в игре 3, длящейся То шагов, что для любого поведения Предсказателя и для любого к в течение первых Т = 2^к< То шагов игры выполняется

Rt = Ht — min Lt (E) >  ---------, где минимум берется no всем составным экспертам, состоящим из к элементарных.

Доказательство. Разделим все шаги игры на интервалы

A_i = [1;2], A_n = [2”^-i + 1;2”], п = 2,....

Рассмотрим следующую стратегию Природы:

На интервале Ai все эксперты дают прогнозы, равные 0, а Природа дает отклик y_t = 0.

К началу интервала А_Г1,п >  1 активировано 2”^-i экспертов. На шагах 2”^-i < t <  2”^-i + п — 1 эксперты и Природа реализуют стратегию из леммы 1. За эти п — 1 шагов Предсказатель несет суммарные потери не меньше п — 1, а один из экспертов несет суммарные потери 0, назовем этого эксперта j_n.

На шагах 2”^-i + (п —1) + 1 <  t < 2” все эксперты дают прогнозы, равные 0, а Природа дает отклик y_t = 0. Таким образом активируются 2” экспертов и все эксперты несут нулевые потери на этих шагах. Предсказатель несет неотрицательные потери.

Рассмотрим составного эксперта E = (1, A i ,..., j_n, А_п,...,Д, А&). Каждый из элементарных экспертов несет нулевые потери на соответствующем периоде игры, поэтому суммарные потери L t (E ) составного эксперта E также равны нулю.

Суммарные потери Предсказателя не меньше 0 + 1 + 2 + ... + (к — 1) = Й-Д^-²). Тогда регрет Предсказателя R t = H t — шзп Lt (E) >  ^{( к i)( k 2)} . Теорема доказана. □

Е

Следствие 2. Пусть в условиях теоремы 2 дополнительно известно, что к > ко, где к о >  2 - константа. Тогда выполняется опенка R t >  ^{( к} ^^ ²⁾ > С т к 1пТ, где С т - некоторая константа, то есть R t = П(к 1пТ ).

Действительно, Т = 2^к, значит, к ln Т = к² ln2, тогда

(к - 1)(к - 2)

^{R t}  -----2-----

>        - (1 - 2 )2

к2

т >

(1 -2 У

к2

—ЫУ

2ln2

ln2 - С₂к lnT. □

Теорема 3. Пусть a - константа, к > аТ. Тогда существует такая стратегия

Природы в игре 3, длящейся Т шагов, что для любого поведения Предсказателя

Rt -Ht - min Lt(E) >aT - 1, где минимум берется по всем составным экспертам, состоящим из к элементарных.

Доказательство. Разделим все шаги игры на к интервалов произвольным образом. К началу каждого интервала, кроме Ai, активировано не менее двух экспертов. На одном из шагов интервала A_n эти два эксперта и Природа реализуют стратегию из леммы 1. На всех остальных шагах игры все эксперты дают прогнозы, равные 0, а Природа дает отклик yt — 0. Таким образом, на каждом интервале A_n, кроме первого, Предсказатель несет суммарные потери не меньше 1, а один из экспертов несет суммарные потери 0, назовем этого экспорта j_n.

Тогда суммарные потери L t (E) составного эксперта E — (1, Ai,... ,j_n, A_n, ... ,jk , A^) равны 0, а суммарные потери Предсказателя не меньше к - 1. Значит, R _t — H _t - min L_t (E) — к - 1 >  аТ - 1. Теорема доказана. □ Е

Заметим, что так как для любых y_t,7_t € [-1,1] величин а потерь h_t — (7 - y)²< 4, то для любых стратегий экспертов, Природы и Предсказателя выполняется оценка R t <  4Т. Таким образом, в условиях теоремы 3 любой алгоритм агрегации работает не намного лучше, чем самый худший алгоритм.

Напомним, что в работе [2], рассматривалось конечное и фиксированное множество экспертов. Рассмотрим игру, аналогичную игре 3, но для фиксированного множества из N экспертов. Следующая теорема дает оценку снизу на регрет Предсказателя в такой игре.

Теорема 4. Пусть в постановке задачи из работы [2] задано N экспертов. Тогда существует такая стратегия Природы в игре, длящейся Т >  kLlog₂NJ шагов, что для любого поведения Предсказателя

Rt — Ht - min Lt (E) — к Llog2 NJ, Е где минимум берется no всем составным экспертам, состоящим из к элементарных.

Доказательство. Пусть т — Ll°g2 NJ. Разделим все шаги игры на к интервалов, каждый длиной не меньше т. На каждом интервале в течение т шагов эксперты и Природа реализуют стратегию из леммы 1. На всех остальных шагах все эксперты дают прогнозы, равные 0, а Природа дает отклик y_t — 0. Таким образом, на каждом интервале A_n Предсказатель несет суммарные потери не меньше т, а один из экспертов несет суммарные потери 0, назовем этого эксперта j_n.

Тогда суммарные потери L t (E ) составного эксперта E —   (ji, Ai,...,jk, A^)

равны 0, а суммарные потери Предсказателя не меньше кт. Значит, R _t — H _t - min L_t (E) — кт — kLlog₂NJ. Теорема доказана. □ Е

Заметим, что при к — 1, то есть для случая простого, а не составного эксперта эта оценка переходит в известную оценку R — Q(lnN) для классической постановки задачи ([7, теорема 3.6]).