Мультипликативный метод обновления веса

Метод обновления мультипликативных весов — это алгоритмический метод, наиболее часто используемый для принятия решений и прогнозирования, а также широко используемый в теории игр и разработке алгоритмов. Самый простой вариант использования — это задача прогнозирования на основе советов экспертов, в которой лицу, принимающему решения, необходимо итеративно выбирать эксперта, совету которого следовать. Метод присваивает экспертам начальные веса (обычно идентичные начальные веса) и обновляет эти веса мультипликативно и итеративно в соответствии с обратной связью о том, насколько хорошо выступил эксперт: уменьшая его в случае плохой работы и увеличивая в противном случае. ^[1] Он неоднократно обнаруживался в самых разных областях, таких как машинное обучение ( AdaBoost , Winnow , Hedge), оптимизация (решение линейных программ ), теоретическая информатика (разработка быстрого алгоритма для LP и SDP ) и теория игр .

Имя

«Мультипликативные веса» подразумевают итерационное правило, используемое в алгоритмах, полученных на основе метода обновления мультипликативного веса. ^[2] Ему даются разные названия в разных областях, где он был обнаружен или переоткрыт.

История и предыстория

Самая ранняя известная версия этой техники заключалась в алгоритме под названием « фиктивная игра », который был предложен в теории игр в начале 1950-х годов. Григориадис и Хачиян ^[3] применил рандомизированный вариант «фиктивной игры» для эффективного решения игр с нулевой суммой для двух игроков, используя алгоритм мультипликативных весов. В этом случае игрок присваивает больший вес действиям, которые привели к лучшему результату, и выбирает свою стратегию, основываясь на этих весах. В машинном обучении Литтлстоун применил самую раннюю форму правила обновления мультипликативных весов в своем знаменитом алгоритме веяния , который похож на более ранний алгоритм обучения перцептрона Мински и Пейперта . Позже он обобщил алгоритм отсеивания до алгоритма взвешенного большинства. Фройнд и Шапир последовали его шагам и обобщили алгоритм отсеивания в форме алгоритма хеджирования.

Алгоритм мультипликативных весов также широко применяется в вычислительной геометрии , например, Кеннета Кларксона алгоритм линейного программирования (LP) с ограниченным числом переменных за линейное время. ^[4]^[5] Позднее Бронниманн и Гудрич применили аналогичные методы для поиска покрытий множеств для гиперграфов малой размерности VC . ^[6]

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

В области информатики некоторые исследователи ранее наблюдали тесные связи между алгоритмами мультипликативного обновления, используемыми в разных контекстах. Янг обнаружил сходство между быстрыми алгоритмами LP и методом пессимистических оценок Рагхавана для дерандомизации алгоритмов рандомизированного округления; Кливанс и Серведио связали алгоритмы повышения в теории обучения с доказательствами леммы XOR Яо; Гарг и Хандекар определили общую структуру для задач выпуклой оптимизации, которая содержит Гарга-Конеманна и Плоткина-Шмойса-Тардоса в качестве подслучаев. ^[1]

Алгоритм Хеджа — это частный случай зеркального спуска .

Общая настройка

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

Алгоритмический анализ

Алгоритм халвинга ^[2]

Учитывая последовательную игру между противником и агрегатором, которого консультируют N экспертов, цель состоит в том, чтобы агрегатор совершил как можно меньше ошибок. Предположим, среди N экспертов есть эксперт, который всегда дает правильный прогноз. В алгоритме халвинга сохраняются только последовательные эксперты. Эксперты, допустившие ошибки, будут уволены. Каждое решение агрегатор принимает большинством голосов среди оставшихся экспертов. Поэтому каждый раз, когда агрегатор допускает ошибку, как минимум половина оставшихся экспертов увольняется. Агрегатор допускает не более $log 2 (N)$ ошибок. ^[2]

Алгоритм взвешенного большинства ^[1]^[7]

В отличие от алгоритма деления пополам, который увольняет экспертов, допустивших ошибки, алгоритм взвешенного большинства не учитывает их советы. Предположим, что у нас есть n решений, и нам нужно выбрать одно решение для каждого цикла. В каждом цикле каждое решение влечет за собой затраты. Все затраты будут известны после выбора. Стоимость равна 0, если эксперт прав, и 1 в противном случае. Цель этого алгоритма — ограничить его совокупные потери примерно до уровня лучших экспертов. Самый первый алгоритм, который делает выбор на основе большинства голосов на каждой итерации, не работает, поскольку большинство экспертов каждый раз могут постоянно ошибаться. Алгоритм взвешенного большинства исправляет описанный выше тривиальный алгоритм, сохраняя вес экспертов вместо фиксации стоимости на уровне 1 или 0. ^[1] Это позволит сделать меньше ошибок по сравнению с алгоритмом деления пополам.

   Initialization: 
      Fix an  $\eta \leq 1/2$ . For each expert, associate the weight  ${w_{i}}^{1}$ ≔1.
   For  $t$  =  ${\mathit {1}}$ ,  ${\mathit {2}}$ ,..., $T$ 
      1. Make the prediction given by the weighted majority of the experts' predictions based on their weights $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$ . That is, choose 0 or 1 depending on which prediction has a higher total weight of experts advising it (breaking ties arbitrarily). 
      2. For every expert i that predicted wrongly, decrease his weight for the next round by multiplying it by a factor of (1-η):
            $w_{i}^{t+1}$ = $(1-\eta )w_{i}^{t}$  (update rule)

Если $\eta =0$ , вес совета эксперта останется прежним. Когда $\eta$ увеличивается, вес совета эксперта уменьшается. Обратите внимание, что некоторые исследователи фиксируют $\eta =1/2$ в алгоритме взвешенного большинства.

После $T$ шаги, пусть $m_{i}^{T}$ - количество ошибок эксперта i и $M^{T}$ — количество ошибок, допущенных нашим алгоритмом. Тогда мы имеем следующую оценку для каждого $i$ :

     $M^{T}\leq 2(1+\eta )m_{i}^{T}+{\frac {2\ln(n)}{\eta }}$ .

В частности, это справедливо для i, являющегося лучшим экспертом. Поскольку лучший эксперт будет иметь наименьшее $m_{i}^{T}$ , это даст наилучшую оценку количества ошибок, допущенных алгоритмом в целом.

Алгоритм рандомизированного взвешенного большинства

Этот алгоритм можно понять следующим образом: ^[2]^[8]

Учитывая ту же настройку с N экспертами. Рассмотрим особую ситуацию, когда доля экспертов, предсказывающих как положительные, так и отрицательные результаты, с учетом весов, близка к 50%. Тогда может быть ничья. Следуя правилу обновления веса в алгоритме взвешенного большинства, прогнозы, сделанные алгоритмом, будут рандомизированы. Алгоритм вычисляет вероятности того, что эксперты прогнозируют положительные или отрицательные результаты, а затем принимает случайное решение на основе вычисленной доли: ^{[ нужны дальнейшие объяснения ]}

предсказывать

f(x)={\begin{cases}1&{\text{with probability}}{\frac {q_{1}}{W}}\\0&{\text{otherwise}}\end{cases}}

где

  $W=\sum _{i}{w_{i}}=q_{0}+q_{1}$ .

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

  $E\left[\#{\text{mistakes of the learner}}\right]\leq \alpha _{\beta }\left(\#{\text{ mistakes of the best expert}}\right)+c_{\beta }\ln(N)$

где $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ и $c_{\beta }={\frac {1}{1-\beta }}$ .

Обратите внимание, что рандомизирован только алгоритм обучения. В основе лежит предположение, что примеры и прогнозы экспертов не случайны. Единственная случайность — это случайность, при которой учащийся делает свой собственный прогноз. В этом рандомизированном алгоритме $\alpha _{\beta }\rightarrow 1$ если $\beta \rightarrow 1$ . По сравнению с взвешенным алгоритмом эта случайность вдвое сокращает количество ошибок, которые алгоритм может совершить. ^[9] Однако важно отметить, что в некоторых исследованиях люди определяют $\eta =1/2$ в алгоритме взвешенного большинства и позволяют $0\leq \eta \leq 1$ в алгоритме рандомизированного взвешенного большинства . ^[2]

Приложения

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

Приближенное решение игр с нулевой суммой (алгоритм Oracle): ^[1]^[9]

Предположим, нам дано распределение $P$ на экспертах. Позволять $A$ = матрица выигрышей конечной игры с нулевой суммой для двух игроков, где $n$ ряды.

Когда рядовой игрок $p_{r}$ использует план $i$ и колонка-плеер $p_{c}$ использует план $j$ , выигрыш игрока $p_{c}$ является $A\left(i,j\right)$ ≔ $A_{ij}$ , предполагая $A\left(i,j\right)\in \left[0,1\right]$ .

Если игрок $p_{r}$ выбирает действие $i$ из дистрибутива $P$ по строкам, то ожидаемый результат для игрока $p_{c}$ выбор действия $j$ является $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ .

Чтобы максимизировать $A\left(P,j\right)$ , игрок $p_{c}$ следует выбрать план $j$ . Аналогично, ожидаемый выигрыш игрока $p_{l}$ является $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ . Выбор плана $i$ минимизировал бы этот выигрыш. По теореме Джона фон Неймана о Мин-Максе мы получаем:

                                           $\min _{P}\max _{j}A\left(P,j\right)=\max _{Q}\min _{i}A\left(i,Q\right)$

где P и i изменяются в распределениях по строкам, Q и j меняются в столбцах.

Тогда пусть $\lambda ^{*}$ обозначают общее значение вышеуказанных величин, также называемое «ценностью игры». Позволять $\delta >0$ быть параметром ошибки. Чтобы решить игру с нулевой суммой, ограниченную аддитивной ошибкой $\delta$ ,

                                                  $\lambda ^{*}-\delta \leq \min _{i}A\left(i,q\right)$ 
                                                  $\max _{j}A\left(p,j\right)\leq \lambda ^{*}+\delta$

Итак, существует алгоритм решения игры с нулевой суммой с точностью до аддитивного коэффициента δ, используя O( $log 2 (n)$ / $\delta ^{2}$ ) вызовы ORACLE с дополнительным временем обработки O(n) на вызов ^[9]

Бейли и Пилиурас показали, что, хотя среднее по времени поведение обновления мультипликативных весов сходится к равновесию Нэша в играх с нулевой суммой, повседневное поведение (последняя итерация) отклоняется от него. ^[10]

Машинное обучение

В области машинного обучения Литтлстоун и Уормут обобщили алгоритм отсеивания до алгоритма взвешенного большинства. ^[11] Позже Фрейнд и Шапир обобщили его в виде алгоритма хеджирования. ^[12] Алгоритм AdaBoost, сформулированный Йоавом Фройндом и Робертом Шапиром, также использовал метод мультипликативного обновления веса. ^[1]

Алгоритм веяния

Основываясь на современных знаниях в области алгоритмов, метод мультипликативного обновления веса был впервые использован в алгоритме веяния Литтлстоуна. ^[1] Он используется в машинном обучении для решения линейной программы.

Данный $m$ отмеченные примеры $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ где $a_{j}\in \mathbb {R} ^{n}$ являются векторами признаков, а $l_{j}\in \left\{-1,1\right\}\quad$ это их этикетки.

Цель состоит в том, чтобы найти такие неотрицательные веса, чтобы для всех примеров знак взвешенной комбинации признаков соответствовал ее меткам. То есть требовать этого $l_{j}a_{j}x\geq 0$ для всех $j$ . Без ограничения общности предположим, что общий вес равен 1, чтобы они образовывали распределение. Поэтому для удобства обозначений переопределим $a_{j}$ быть $l_{j}a_{j}$ , задача сводится к поиску решения следующей ЛП:

                      $\forall j=1,2,{\text{…}},m:a_{j}x\geq 0$ ,
                      $1*x=1$ ,
                      $\forall i:x_{i}\geq 0$ .

Это общая форма LP.

Алгоритм хеджирования ^[2]

Алгоритм хеджирования аналогичен алгоритму взвешенного большинства. Однако их правила экспоненциального обновления различны. ^[2] Обычно он используется для решения проблемы двоичного распределения, в которой нам нужно распределить разные части ресурсов по N различным вариантам. Убыток для каждого варианта доступен в конце каждой итерации. Цель состоит в том, чтобы уменьшить общие потери, понесенные для конкретного распределения. Затем распределение для следующей итерации пересматривается на основе общих потерь, понесенных в текущей итерации, с использованием мультипликативного обновления. ^[13]

Анализ

Предположим, скорость обучения $\eta >0$ и для $t\in [T]$ , $p^{t}$ выбран Хеджем. Тогда для всех экспертов $i$ ,

                                 $\sum _{t\leq T}p^{t}m^{t}\leq \sum _{t\leq T}m_{i}^{t}+{\frac {\ln(N)}{\eta }}+\eta T$

Инициализация : исправить $\eta >0$ . Для каждого эксперта присвойте вес $w_{i}^{1}$ ≔1 Для t=1,2,...,T:

      1. Pick the distribution  $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$  where  $\Phi t=\sum _{i}w_{i}^{t}$ .
      2. Observe the cost of the decision  $m^{t}$ . 
      3. Set 
                               $w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}$ ).

Алгоритм AdaBoost

Этот алгоритм ^[12] поддерживает набор весов $w^{t}$ над обучающими примерами. На каждой итерации $t$ , распределение $p^{t}$ вычисляется путем нормализации этих весов. Это распределение передается слабому учащемуся WeakLearn, который генерирует гипотезу. $h_{t}$ это (надеюсь) имеет небольшую погрешность в отношении распределения. Используя новую гипотезу $h_{t}$ , AdaBoost генерирует следующий весовой вектор $w^{t+1}$ . Процесс повторяется. После T таких итераций окончательная гипотеза $h_{f}$ это выход. Гипотеза $h_{f}$ объединяет результаты T слабых гипотез с использованием взвешенного большинства голосов. ^[12]

Input: 
      Sequence of  $N$  labeled examples ( $x_{1}$ , $y_{1}$ ),...,( $x_{N}$ ,  $y_{N}$ )
      Distribution  $D$  over the  $N$  examples
      Weak learning algorithm "'WeakLearn"'
      Integer  $T$  specifying number of iterations
Initialize the weight vector:  $w_{i}^{1}=D(i)$  for  $i=1,2,...,N$ .
Do for  $t=1,2,...,T$ 
      1. Set  $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$ .
      2. Call WeakLearn, providing it with the distribution  $p^{t}$ ; get back a hypothesis  $h_{t}:X\rightarrow$  [0,1].
      3. Calculate the error of  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}|h_{t}(x_{i})-y_{i}|$ .
      4. Set  $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$ .                                     
      5. Set the new weight vector to be  $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ .

Output the hypothesis:

       $f(x)=h_{f}(x)={\begin{cases}1&{\text{if}}\sum _{t=1}^{T}(\log(1/\beta _{t}))h_{t}(x)\geq {\frac {1}{2}}\sum _{t=1}^{T}\log(1/\beta _{t})\\0&{\text{otherwise}}\end{cases}}$

Приближенное решение линейных программ ^[14]

Проблема

Учитывая $m\times n$ матрица $A$ и $b\in \mathbb {R} ^{n}$ , Есть ли $x$ такой, что $Ax\geq b$ ?

                       $\exists ?x:Ax\geq b$               (1)

Предположение

Использование алгоритма оракула при решении задачи с нулевой суммой с параметром ошибки $\epsilon >0$ , выход будет либо точкой $x$ такой, что $Ax\geq b-\epsilon$ или доказательство того, что $x$ не существует, т. е. не существует решения этой линейной системы неравенств.

Решение

Данный вектор $p\in \Delta _{n}$ , решает следующую расслабленную задачу

                      $\exists ?x:p^{\textsf {T}}\!\!Ax\geq p^{\textsf {T}}\!b$              (2)

Если существует ax, удовлетворяющий (1), то x удовлетворяет (2) для всех $p\in \Delta _{n}$ . Противоположность этого утверждения также верна. Предположим, что оракул возвращает допустимое решение для $p$ , решение $x$ он возвращает ограниченную ширину $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ . Таким образом, если существует решение (1), то существует алгоритм, выход которого x удовлетворяет системе (2) с точностью до аддитивной ошибки $2\epsilon$ . Алгоритм делает максимум ${\frac {\ln(m)}{\epsilon ^{2}}}$ обращается к оракулу с ограниченной шириной для решения проблемы (2). Противоположение также справедливо. В этом случае в алгоритме применяются мультипликативные обновления.

Другие приложения

Эволюционная теория игр: Обновление мультипликативных весов — это вариант уравнения репликатора (динамики репликатора) с дискретным временем, который является широко используемой моделью в эволюционной теории игр . Оно сходится к равновесию Нэша, когда применяется к игре с перегрузками . ^[15]

Исследование операций и принятие статистических решений онлайн: В области исследования операций и задач принятия статистических решений в режиме онлайн независимо друг от друга были найдены алгоритм взвешенного большинства и его более сложные версии. ^[1]

Вычислительная геометрия: Алгоритм мультипликативных весов также широко применяется в вычислительной геометрии . ^[1] например, Кларксона алгоритм линейного программирования (ЛП) с ограниченным числом переменных за линейное время. ^[4]^[5] Позже Бронниманн и Гудрич применили аналогичные методы для поиска покрытий множеств для гиперграфов с небольшой размерностью VC . ^[6]

Метод градиентного спуска ^[1]

матрицы Обновление мультипликативных весов ^[1]

Каркас Плоткин, Шмойс, Тардос для упаковки пластинок . ^[1]

Аппроксимация задач многотоварного потока ^[1]

O (logn) - аппроксимация для многих NP-трудных задач. ^[1]

Изучение теории и повышение квалификации ^[1]

Жесткие множества и лемма XOR ^[1]

Алгоритм Ханнана и мультипликативные веса ^[1]

Онлайн- выпуклая оптимизация ^[1]

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с Арора, Санджив ; Хазан, Элад; Кале, Сатьен (2012). «Метод обновления мультипликативных весов: метаалгоритм и приложения» . Теория вычислений . 8 : 121–164. дои : 10.4086/toc.2012.v008a006 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г «Алгоритм мультипликативных весов *» (PDF) . Проверено 9 ноября 2016 г.
^ Григориадис, Майкл Д.; Хачиян, Леонид Георгиевич (1995). «Алгоритм рандомизированной аппроксимации сублинейного времени для матричных игр». Письма об исследованиях операций . 18 (2): 53–58. дои : 10.1016/0167-6377(95)00032-0 .
^ Перейти обратно: ^а ^б Кеннет Л. Кларксон. Алгоритм Лас-Вегаса для линейного программирования при небольших размерах. , В Proc. 29-й FOCS, стр. 452–456. IEEE Комп. Соц. Пресс, 1988. [doi:10.1109/SFCS.1988.21961] 123, 152.
^ Перейти обратно: ^а ^б Кеннет Л. Кларксон. Алгоритм Лас-Вегаса для линейного и целочисленного программирования при небольшой размерности. , Журнал ACM, 42:488–499, 1995. [doi:10.1145/201019.201036] 123, 152.
^ Перейти обратно: ^а ^б Бронниманн, Х.; Гудрич, МТ (1995). «Почти оптимальное множество покрытий в конечной VC-мерности» . Дискретная и вычислительная геометрия . 14 (4): 463–479. дои : 10.1007/BF02570718 . Предварительная версия в 10-й Энн. Симп. Комп. Геом. (СКГ'94).
^ «Лекция 8: Принятие решений в условиях полной неопределенности: алгоритм мультипликативного веса» (PDF) . 2013.
^ «COS 511: Основы машинного обучения» (PDF) . 20 марта 2006 г.
^ Перейти обратно: ^а ^б ^с «Инструментарий алгоритмиста» . 8 декабря 2009 года . Проверено 9 ноября 2016 г.
^ Бейли, Джеймс П. и Георгиос Пилиурас. «Обновление мультипликативных весов в играх с нулевой суммой». Материалы конференции ACM по экономике и вычислениям 2018 года. АКМ, 2018.
^ Фостер, Дин П.; Вохра, Ракеш (1999). «Сожаление о проблеме онлайн-решения» (PDF) . Игры и экономическое поведение . 29 (1–2): 7–35. дои : 10.1006/game.1999.0740 .
^ Перейти обратно: ^а ^б ^с Йоав, Фрейнд. Роберт, Э. Шапир (1996). TA Теоретико-решающее обобщение онлайн-обучения и применение к повышению* , с. 55. журнал компьютерных и системных наук.
^ «Онлайн-обучение у экспертов: взвешенное большинство и хеджирование» (PDF) . Проверено 7 декабря 2016 г.
^ «Основы выпуклой оптимизации» (PDF) . Проверено 9 ноября 2016 г.
^ Кляйнберг, Роберт, Георгиос Пилиурас и Ева Тардос. «Мультипликативные обновления превосходят стандартное обучение без сожалений в играх с перегрузками». Материалы сорок первого ежегодного симпозиума ACM по теории вычислений. АКМ, 2009.

Внешние ссылки

Статья The Game Theory of Life в журнале Quanta Magazine, описывающая использование этого метода в эволюционной биологии в статье Эрика Честейна, Ади Ливната, Христаса Пападимитриу и Умеша Вазирани.

[ref1-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с Арора, Санджив ; Хазан, Элад; Кале, Сатьен (2012). «Метод обновления мультипликативных весов: метаалгоритм и приложения» . Теория вычислений . 8 : 121–164. дои : 10.4086/toc.2012.v008a006 .

[ref2-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г «Алгоритм мультипликативных весов *» (PDF) . Проверено 9 ноября 2016 г.

[3] Григориадис, Майкл Д.; Хачиян, Леонид Георгиевич (1995). «Алгоритм рандомизированной аппроксимации сублинейного времени для матричных игр». Письма об исследованиях операций . 18 (2): 53–58. дои : 10.1016/0167-6377(95)00032-0 .

[Kenneth_L._Clarkson_pp._452-4] Перейти обратно: ^а ^б Кеннет Л. Кларксон. Алгоритм Лас-Вегаса для линейного программирования при небольших размерах. , В Proc. 29-й FOCS, стр. 452–456. IEEE Комп. Соц. Пресс, 1988. [doi:10.1109/SFCS.1988.21961] 123, 152.

[Kenneth_L._Clarkson_1995-5] Перейти обратно: ^а ^б Кеннет Л. Кларксон. Алгоритм Лас-Вегаса для линейного и целочисленного программирования при небольшой размерности. , Журнал ACM, 42:488–499, 1995. [doi:10.1145/201019.201036] 123, 152.

[M.T._GOODRICH._1995-6] Перейти обратно: ^а ^б Бронниманн, Х.; Гудрич, МТ (1995). «Почти оптимальное множество покрытий в конечной VC-мерности» . Дискретная и вычислительная геометрия . 14 (4): 463–479. дои : 10.1007/BF02570718 . Предварительная версия в 10-й Энн. Симп. Комп. Геом. (СКГ'94).

[ref5-7] «Лекция 8: Принятие решений в условиях полной неопределенности: алгоритм мультипликативного веса» (PDF) . 2013.

[ref6-8] «COS 511: Основы машинного обучения» (PDF) . 20 марта 2006 г.

[ref7-9] Перейти обратно: ^а ^б ^с «Инструментарий алгоритмиста» . 8 декабря 2009 года . Проверено 9 ноября 2016 г.

[Bailey_and_Piliouras_EC18-10] Бейли, Джеймс П. и Георгиос Пилиурас. «Обновление мультипликативных весов в играх с нулевой суммой». Материалы конференции ACM по экономике и вычислениям 2018 года. АКМ, 2018.

[11] Фостер, Дин П.; Вохра, Ракеш (1999). «Сожаление о проблеме онлайн-решения» (PDF) . Игры и экономическое поведение . 29 (1–2): 7–35. дои : 10.1006/game.1999.0740 .

[ref8-12] Перейти обратно: ^а ^б ^с Йоав, Фрейнд. Роберт, Э. Шапир (1996). TA Теоретико-решающее обобщение онлайн-обучения и применение к повышению* , с. 55. журнал компьютерных и системных наук.

[ref16-13] «Онлайн-обучение у экспертов: взвешенное большинство и хеджирование» (PDF) . Проверено 7 декабря 2016 г.

[ref11-14] «Основы выпуклой оптимизации» (PDF) . Проверено 9 ноября 2016 г.

[Kleinberg,_Piliouras,_Tardos_09-15] Кляйнберг, Роберт, Георгиос Пилиурас и Ева Тардос. «Мультипликативные обновления превосходят стандартное обучение без сожалений в играх с перегрузками». Материалы сорок первого ежегодного симпозиума ACM по теории вычислений. АКМ, 2009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Имя