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

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

Пример

Представьте себе, что каждое утро перед фондового рынка открытием мы получаем прогноз от каждого из наших «экспертов» о том, пойдет ли фондовый рынок вверх или вниз. Наша цель — каким-то образом объединить этот набор прогнозов в один прогноз, который мы затем используем для принятия решения о покупке или продаже на день. Основная проблема заключается в том, что мы не знаем, какие эксперты дадут лучшие или худшие прогнозы. RWMA дает нам возможность реализовать эту комбинацию так, что наша запись прогноза будет почти так же хорош, как прогноз одного эксперта, который, оглядываясь назад, дал наиболее точные прогнозы.

Мотивация

В машинном обучении алгоритм взвешенного большинства (WMA) представляет собой детерминированный алгоритм метаобучения для агрегирования экспертных прогнозов. В псевдокоде WMA выглядит следующим образом:

initialize all experts to weight 1
for each round:
    add each expert's weight to the option they predicted
    predict the option with the largest weighted sum
    multiply the weights of all experts who predicted wrongly by  ${\frac {1}{2}}$

Предположим, есть $n$ эксперты и лучшие эксперты делают $m$ ошибки. Тогда алгоритм взвешенного большинства (WMA) дает не более $2.4(\log _{2}n+m)$ ошибки. Эта оценка весьма проблематична в случае экспертов, склонных к ошибкам. Предположим, например, что лучший эксперт допускает ошибку в 20% случаев; то есть в $N=100$ раунды с использованием $n=10$ эксперты, лучший эксперт делает $m=20$ ошибки. Тогда алгоритм взвешенного большинства гарантирует только верхнюю границу $2.4(\log _{2}10+20)\approx 56$ ошибки.

Поскольку это известное ограничение алгоритма взвешенного большинства, были исследованы различные стратегии, чтобы улучшить зависимость от $m$ . В частности, мы можем добиться большего, введя рандомизацию.

Черпая вдохновение из алгоритма метода обновления мультипликативных весов , мы будем вероятностно делать прогнозы на основе того, как эксперты работали в прошлом. Как и в случае с WMA, каждый раз, когда эксперт делает неправильный прогноз, мы уменьшаем его вес. Отражая MWUM, мы затем будем использовать веса, чтобы составить распределение вероятностей действий и извлечь наши действия из этого распределения (вместо детерминированного выбора большинства голосов, как это делает WMA). ^[2]

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

Алгоритм рандомизированного взвешенного большинства представляет собой попытку улучшить зависимость границы ошибки WMA от $m$ . Вместо прогнозирования на основе большинства голосов, веса используются как вероятности выбора экспертов в каждом раунде и обновляются с течением времени (отсюда и название «рандомизированное взвешенное большинство»).

Именно, если $w_{i}$ вес эксперта $i$ , позволять $W=\sum _{i}w_{i}$ . Мы будем следовать за экспертом $i$ с вероятностью ${\frac {w_{i}}{W}}$ . В результате получается следующий алгоритм:

initialize all experts to weight 1.
for each round:
    add all experts' weights together to obtain the total weight  $W$ 
    choose expert  $i$  randomly with probability  ${\frac {w_{i}}{W}}$  
    predict as the chosen expert predicts
    multiply the weights of all experts who predicted wrongly by  $\beta$

Цель состоит в том, чтобы ограничить ожидаемое количество ошибок для наихудшего случая. предполагая, что противник должен выбрать один из ответов как правильно, прежде чем мы подбросим монету. Это разумное предположение, например, в приведенном выше примере фондового рынка: отклонение цены акции не должно зависеть от мнений экспертов, которые влияют на частные решения о покупке или продаже, поэтому мы можем рассматривать изменение цены так, как если бы оно было решил до того, как эксперты дали свои рекомендации на день.

Рандомизированный алгоритм в худшем случае лучше, чем детерминированный алгоритм ( алгоритм взвешенного большинства ): в последнем худший случай был тогда, когда веса были разделены 50/50. Но в рандомизированной версии, поскольку веса используются как вероятности, вероятность того, что все будет сделано правильно, все равно будет 50/50. Кроме того, если обобщить умножение весов неверных экспертов на $\beta <1$ вместо строго ${\frac {1}{2}}$ позволяет нам найти компромисс между зависимостью от $m$ и $\log _{2}n$ . Этот компромисс будет определен количественно в разделе анализа.

Анализ

Позволять $W_{t}$ обозначают общий вес всех экспертов в раунде $t$ . Также пусть $F_{t}$ обозначают долю веса, придаваемую экспертам, которые предсказывают неправильный ответ в раунде $t$ . Наконец, позвольте $N$ быть общим количеством раундов в процессе.

По определению, $F_{t}$ вероятность того, что алгоритм допустит ошибку в раунде $t$ . Из линейности ожидания следует, что если $M$ обозначает общее количество ошибок, допущенных в течение всего процесса, $E[M]=\sum _{t=1}^{N}F_{t}$ .

После раунда $t$ , общий вес уменьшается на $\ (1-\beta )F_{t}W_{t}$ , поскольку все веса, соответствующие неправильному ответу, умножаются на $\ \beta <1$ . Отсюда следует, что $W_{t+1}=W_{t}(1-(1-\beta )F_{t})$ . Телескопируя, поскольку $W_{1}=n$ , отсюда следует, что общий вес после завершения процесса равен

{\begin{aligned}W=n\prod _{t=1}^{N}(1-(1-\beta )F_{t}).\end{aligned}}

С другой стороны, предположим, что $\ m$ — это количество ошибок, допущенных наиболее эффективным экспертом. В конце концов, этот эксперт имеет вес $\ \beta ^{m}$ . Отсюда следует, что общий вес составляет по крайней мере столько же; другими словами, $\ W\geq \beta ^{m}$ . Из этого неравенства и приведенного выше результата следует

{\begin{aligned}n\prod _{t=1}^{N}(1-(1-\beta )F_{t})\geq \beta ^{m}.\end{aligned}}

Взяв натуральный логарифм обеих частей, получим

{\begin{aligned}\ln n+\sum _{t=1}^{N}\ln(1-(1-\beta )F_{t})\geq m\ln \beta .\end{aligned}}

Теперь ряд Тейлора натурального логарифма равен

{\begin{aligned}\ln(1-x)=-x-{\frac {x^{2}}{2}}-{\frac {x^{3}}{3}}-\cdots \end{aligned}}

В частности, отсюда следует, что $\ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}$ .
Таким образом,

{\begin{aligned}\ln n-(1-\beta )\sum _{t=1}^{N}F_{t}\geq m\ln \beta .\end{aligned}}

напоминая, что $E[M]=\sum _{t=1}^{N}F_{t}$ и переставляя, отсюда следует, что

{\begin{aligned}E[M]\leq {\frac {m\ln(1/\beta )+\ln(n)}{1-\beta }}={\frac {\ln(1/\beta )}{1-\beta }}m+{\frac {1}{1-\beta }}\ln(n).\end{aligned}}

Теперь, как $\beta \to 1$ снизу первая константа стремится к $1$ ; однако вторая константа имеет тенденцию $+\infty$ . Чтобы количественно оценить этот компромисс, определите $\varepsilon =1-\beta$ быть наказанием, связанным с неверным прогнозом. Затем, снова применяя ряд Тейлора по натуральному логарифму:

{\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}=-{\frac {\ln(\beta )}{1-\beta }}={\frac {-\ln(1-\varepsilon )}{\varepsilon }}={\frac {\varepsilon +{\frac {\varepsilon ^{2}}{2}}+{\frac {\varepsilon ^{3}}{3}}+\cdots }{\varepsilon }}=1+{\frac {\varepsilon }{2}}+O(\varepsilon ^{2})\end{aligned}}

Отсюда следует, что ошибка связана при малых $\varepsilon$ , можно записать в виде $\ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)$ .

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

В частности, пока $m$ достаточно велик по сравнению с $\ln(n)$ (так что их отношение достаточно мало), можно присвоить

{\begin{aligned}\varepsilon ={\sqrt {\frac {\ln(n)}{m}}}\end{aligned}}

мы можем получить верхнюю оценку числа ошибок, равную

{\begin{aligned}m+O({\sqrt {m\ln(n)}}).\end{aligned}}

Это означает, что «граница сожаления» алгоритма (то есть, насколько хуже он работает, чем лучший эксперт) является сублинейной, т.е. $O({\sqrt {m\ln(n)}})$ .

Пересматривая мотивацию

Напомним, что мотивацией для алгоритма рандомизированного взвешенного большинства послужил пример, где лучший эксперт допускает ошибку в 20% случаев. Именно в $N=100$ раунды, с $n=10$ эксперты, где лучший эксперт делает $m=20$ ошибок, детерминированный алгоритм взвешенного большинства гарантирует только верхнюю границу $2.4(\log _{2}10+20)\approx 56$ . Из приведенного выше анализа следует, что минимизация числа ожидаемых ошибок в худшем случае эквивалентна минимизации функции

{\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}20+{\frac {1}{1-\beta }}\ln(10).\end{aligned}}

Вычислительные методы показывают, что оптимальное значение составляет примерно $\beta \approx 0.641$ , что приводит к минимальному числу ожидаемых ошибок в худшем случае $E[M]\approx 31.19$ . При увеличении количества раундов (скажем, до $N=1000000$ ) хотя уровень точности лучшего эксперта остается прежним, улучшение может быть еще более значительным; алгоритм взвешенного большинства гарантирует только наихудший уровень ошибок в размере 48,0%, но алгоритм рандомизированного взвешенного большинства, если он правильно настроен на оптимальное значение $\varepsilon \approx 0.0117$ , достигает наихудшего уровня ошибок 20,2%.

Использование алгоритма рандомизированного взвешенного большинства (RWMA)

Алгоритм рандомизированного взвешенного большинства можно использовать для объединения нескольких алгоритмов, и в этом случае можно ожидать, что RWMA будет работать почти так же хорошо, как и лучшие из исходных алгоритмов в ретроспективе. Обратите внимание, что RWMA можно обобщить для решения задач, в которых нет двоичных переменных ошибок, что делает его полезным для широкого класса задач.

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

Приложения в программном обеспечении

Алгоритм рандомизированного взвешенного большинства был предложен в качестве нового метода для нескольких практических программных приложений, особенно в области обнаружения ошибок и кибербезопасности. ^[3] ^[4] Например, Варша и Мадхаву (2021) описывают, как алгоритм рандомизированного взвешенного большинства может использоваться для замены обычного голосования в рамках подхода классификации случайного леса для обнаружения внутренних угроз. Используя экспериментальные результаты, они показывают, что этот подход обеспечивает более высокий уровень точности и полноты по сравнению со стандартным алгоритмом случайного леса. Мустафа и др. (2018) изучили, как ансамблевый классификатор , основанный на алгоритме рандомизированного взвешенного большинства, можно использовать для обнаружения ошибок на более ранних этапах процесса разработки программного обеспечения, после обучения на существующих репозиториях программного обеспечения.

Расширения

Проблема многорукого бандита .
Эффективный алгоритм для некоторых случаев со многими экспертами.
Спящие эксперты/спящие специалисты.

См. также

Ссылки

^ Литлстоун, Н.; Вармут, М. (1994). «Алгоритм взвешенного большинства» . Информация и вычисления . 108 (2): 212–261. дои : 10.1006/inco.1994.1009 .
^ «COS 511: Основы машинного обучения» (PDF) . 20 марта 2006 г.
^ Суреш, П. Варша; Мадхаву, Мину Лалита (2021). «Инсайдерская атака: обнаружение внутренних кибератак с использованием машинного обучения». 2021 12-я Международная конференция по вычислительным коммуникативным и сетевым технологиям (ICCCNT) . стр. 1–7. дои : 10.1109/ICCCNT51525.2021.9579549 . ISBN 978-1-7281-8595-8 .
^ Мустафа, Саммар; Эль-Найнай, Мустафа Ю; Эль Макки, я упал; Абугабал, Мохаммед С. (2018). «Прогнозирование ошибок программного обеспечения с использованием методов взвешенного большинства» . Александрийский инженерный журнал . 57 (4): 2763–2774. дои : 10.1016/август 2018.01.003 .

Дальнейшее чтение

[LW94-1] Литлстоун, Н.; Вармут, М. (1994). «Алгоритм взвешенного большинства» . Информация и вычисления . 108 (2): 212–261. дои : 10.1006/inco.1994.1009 .

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

[VL21-3] Суреш, П. Варша; Мадхаву, Мину Лалита (2021). «Инсайдерская атака: обнаружение внутренних кибератак с использованием машинного обучения». 2021 12-я Международная конференция по вычислительным коммуникативным и сетевым технологиям (ICCCNT) . стр. 1–7. дои : 10.1109/ICCCNT51525.2021.9579549 . ISBN 978-1-7281-8595-8 .

[SE18-4] Мустафа, Саммар; Эль-Найнай, Мустафа Ю; Эль Макки, я упал; Абугабал, Мохаммед С. (2018). «Прогнозирование ошибок программного обеспечения с использованием методов взвешенного большинства» . Александрийский инженерный журнал . 57 (4): 2763–2774. дои : 10.1016/август 2018.01.003 .

[1]

[2]

[3]

[4]