Метод обновления мультипликативного веса - Multiplicative weight update method

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

имя

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

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

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

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

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

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

Общие настройки

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

Анализ алгоритмов

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

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

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

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

   Инициализация: Исправить ${\displaystyle \eta \leq 1/2}$. Для каждого эксперта свяжите вес ${\displaystyle {w_{i}}^{1}}$≔1.   Для ${\displaystyle t}$ = ${\displaystyle {\mathit {1}}}$, ${\displaystyle {\mathit {2}}}$,…,${\displaystyle T}$      1. Сделайте прогноз, основанный на взвешенном большинстве прогнозов экспертов, на основе их весов.${\displaystyle \mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}}$. То есть выберите 0 или 1 в зависимости от того, какой прогноз имеет больший общий вес советников (произвольное разрушение связей). 2. Для каждого эксперта i, который предсказал неверно, уменьшите его вес для следующего раунда, умножив его на коэффициент (1-η): ${\displaystyle w_{i}^{t+1}}$=${\displaystyle (1-\eta )w_{i}^{t}}$ (обновить правило)

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

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

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

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

Рандомизированный алгоритм взвешенного большинства^[2][9]

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

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

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

где

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Winnow

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

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

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

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

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

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

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

Анализ

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

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

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

      1. Выберите дистрибутив ${\displaystyle p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}}$ где ${\displaystyle \Phi t=\sum _{i}w_{i}^{t}}$. 2. Обратите внимание на стоимость решения. ${\displaystyle m^{t}}$. 3. Установить ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}}$).

Алгоритм AdaBoost

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

Ввод:       Последовательность ${\displaystyle N}$ помеченные примеры (${\displaystyle x_{1}}$,${\displaystyle y_{1}}$),…,(${\displaystyle x_{N}}$, ${\displaystyle y_{N}}$) Распределение ${\displaystyle D}$ над ${\displaystyle N}$ примеры Алгоритм слабого обучения "WeakLearn" 'Integer ${\displaystyle T}$ указание количества итерацийИнициализировать вектор веса: ${\displaystyle w_{i}^{1}=D(i)}$ для ${\displaystyle i=1}$,..., ${\displaystyle N}$.Делать для ${\displaystyle t=1}$,..., ${\displaystyle N}$      1. Набор ${\displaystyle p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}}$.      2. Вызов Слабый, снабдив его раздачей ${\displaystyle p^{t}}$; вернуть гипотезу ${\displaystyle h_{t}:X\rightarrow }$ [0,1].      3. Рассчитайте погрешность ${\displaystyle h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}}$|${\displaystyle h_{t}(x_{i})}$.      4. Набор ${\displaystyle \beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}}$.                                           5. Установите новый вектор веса как ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}}$.Вывод гипотеза:

      ${\displaystyle 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}){\frac {q_{1}}{W}}\\0&{\text{otherwise}}\end{cases}}}$

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

Проблема

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

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

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

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

Решение

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

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

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

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

Эволюционная теория игр

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

Исследование операций и принятие статистических решений в режиме онлайн^[7]

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

Вычислительная геометрия

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

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

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

Плоткин, Шмойс, Тардос рамки для упаковка /покрытие LP^[7]

Приблизительный проблемы с потоком нескольких товаров^[7]

O (logn) - приближение для многих NP-сложные задачи^[7]

Теория обучения и повышение^[7]

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

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

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

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

1. «Метод обновления мультипликативных весов: метаалгоритм и приложения» (PDF). Май 2012 г.
2. «Алгоритм мультипликативных весов *» (PDF). Получено 9 ноября 2016.
3. «Сублинейный алгоритм рандомизированного приближения для матричных игр». 1995 г. Отсутствует или пусто | url = (Помогите)
4. КЕННЕТ Л. КЛАРКСОН. Алгоритм Лас-Вегаса для линейного программирования, когда размерность мала., В Proc. 29-я FOCS, стр. 452–456. IEEE Comp. Soc. Press, 1988. [DOI: 10.1109 / SFCS.1988.21961] 123, 152.
5. КЕННЕТ Л. КЛАРКСОН. Алгоритм Лас-Вегаса для линейного и целочисленного программирования, когда размерность мала., J. ACM, 42: 488–499, 1995. [DOI: 10.1145 / 201019.201036] 123, 152.
6. Х. БРОННИМАН И ¨ M.T. ГУДРИЧ. Почти оптимальные покрытия множеств в конечной VC-размерности., Дискретные вычисления. Geom., 14: 463–479, 1995. Предварительная версия в 10th Ann. Symp. Комп. Геом. (SCG'94). [DOI: 10.1007 / BF02570718] 123, 152
7. «Метод обновления мультипликативных весов: метаалгоритм и приложения» (PDF). 2012.
8. «Лекция 8: Принятие решений в условиях полной неопределенности: алгоритм мультипликативного веса» (PDF). 2013.
9. «COS 511: основы машинного обучения» (PDF). 20 марта 2006 г.
10. «Инструментарий алгоритмиста». 8 декабря 2009 г.. Получено 9 ноября 2016.
11. Бейли, Джеймс П. и Георгиос Пилиурас. «Обновление мультипликативных весов в играх с нулевой суммой». Материалы конференции ACM по экономике и вычислениям 2018 г. ACM, 2018.
12. ДИН П. ФОСТЕР И РАКЕШ ВОХРА (1999). Сожаление о проблеме онлайн-решения, п. 29. Игры и экономическое поведение.
13. Йоав, Фройнд. Роберт, Э. Шапир (1996). Теоретико-технологическое обобщение онлайн-обучения и его применение для повышения квалификации *, п. 55. Журнал компьютерных и системных наук.
14. «Онлайн-обучение от экспертов: взвешенное большинство и хеджирование» (PDF). Получено 7 декабря 2016.
15. «Основы выпуклой оптимизации» (PDF). Получено 9 ноября 2016.
16. Клейнберг, Роберт, Георгиос Пилиурас и Ева Тардос. «Мультипликативные обновления превосходят обычное беспроблемное обучение в играх с перегрузками». Материалы сорок первого ежегодного симпозиума ACM по теории вычислений. ACM, 2009.

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