Algoritmo de mayoría ponderada aleatoria

El algoritmo de mayoría ponderada aleatoria es un algoritmo de la teoría del aprendizaje automático que permite agregar predicciones de expertos a una serie de problemas de decisión. ^[1] Es un método simple y eficaz basado en la votación ponderada que mejora el límite de error del algoritmo de mayoría ponderada determinista . De hecho, en el límite, su tasa de predicción puede ser arbitrariamente cercana a la del experto que mejor predice.

Ejemplo

Imaginemos que cada mañana, antes de que abra el mercado de valores , recibimos una predicción de cada uno de nuestros "expertos" sobre si el mercado de valores subirá o bajará. Nuestro objetivo es combinar de algún modo este conjunto de predicciones en una única predicción que luego utilizamos para tomar una decisión de compra o venta para el día. El principal desafío es que no sabemos qué expertos darán mejores o peores predicciones. La RWMA nos ofrece una forma de hacer esta combinación de modo que nuestro historial de predicciones sea casi tan bueno como el del experto individual que, en retrospectiva, dio las predicciones más precisas.

Motivación

En el aprendizaje automático , el algoritmo de mayoría ponderada (WMA) es un algoritmo de metaaprendizaje determinista para agregar predicciones de expertos. En pseudocódigo, el WMA es el siguiente:

inicializar todos los expertos con peso 1Para cada ronda: Añade el peso de cada experto a la opción que predijeron Predecir la opción con la suma ponderada más grande multiplicar los pesos de todos los expertos que predijeron erróneamente por ${\displaystyle {\frac {1}{2}}}$

Supongamos que hay expertos y que el mejor experto comete errores. En ese caso, el algoritmo de mayoría ponderada (WMA) comete errores como máximo. Este límite es muy problemático en el caso de expertos muy propensos a cometer errores. Supongamos, por ejemplo, que el mejor experto comete un error el 20 % de las veces; es decir, en las rondas en las que se utilizan expertos, el mejor experto comete errores. En ese caso, el algoritmo de mayoría ponderada solo garantiza un límite superior de errores. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle 2.4(\log _{2}n+m)}$ ${\displaystyle N=100}$ ${\displaystyle n=10}$ ${\displaystyle m=20}$ ${\displaystyle 2.4(\log _{2}10+20)\approx 56}$

Como esta es una limitación conocida del algoritmo de mayoría ponderada, se han explorado varias estrategias para mejorar la dependencia de . En particular, podemos hacerlo mejor introduciendo la aleatorización. ${\displaystyle m}$

Inspirándonos en el algoritmo del método de actualización de pesos multiplicativos , realizaremos predicciones de forma probabilística en función del desempeño de los expertos en el pasado. De forma similar al método de actualización de pesos multiplicativos, cada vez que un experto haga una predicción incorrecta, disminuiremos su peso. Siguiendo el ejemplo del método de actualización de pesos multiplicativos, utilizaremos los pesos para realizar una distribución de probabilidad sobre las acciones y extraeremos nuestra acción a partir de esta distribución (en lugar de elegir de forma determinista el voto mayoritario como lo hace el método de actualización de pesos multiplicativos). ^[2]

Algoritmo de mayoría ponderada aleatoria (RWMA)

El algoritmo de mayoría ponderada aleatoria es un intento de mejorar la dependencia del límite de error del WMA de . En lugar de predecir en función del voto de la mayoría, los pesos se utilizan como probabilidades para elegir a los expertos en cada ronda y se actualizan con el tiempo (de ahí el nombre de mayoría ponderada aleatoria). ${\displaystyle m}$

Precisamente, si es el peso de experto , sea . Seguiremos a experto con probabilidad . Esto da como resultado el siguiente algoritmo: ${\displaystyle w_{i}}$ ${\displaystyle i}$ ${\displaystyle W=\sum _{i}w_{i}}$ ${\displaystyle i}$ ${\displaystyle {\frac {w_{i}}{W}}}$

inicializar todos los expertos al peso 1.Para cada ronda: Sume los pesos de todos los expertos para obtener el peso total. Elija un experto al azar con probabilidad. ${\displaystyle W}$ ${\displaystyle i}$ ${\displaystyle {\frac {w_{i}}{W}}}$  predecir como predice el experto elegido multiplicar los pesos de todos los expertos que predijeron erróneamente por ${\displaystyle \beta }$

El objetivo es limitar el número de errores esperados en el peor de los casos, suponiendo que el adversario tiene que seleccionar una de las respuestas como correcta antes de lanzar la moneda. Esta es una suposición razonable, por ejemplo, en el ejemplo del mercado de valores proporcionado anteriormente: la variación del precio de una acción no debería depender de las opiniones de los expertos que influyen en las decisiones privadas de compra o venta, por lo que podemos tratar el cambio de precio como si se hubiera decidido antes de que los expertos dieran sus recomendaciones para el día.

El algoritmo aleatorio es mejor en el peor de los casos que el algoritmo determinista ( algoritmo de mayoría ponderada ): en este último, el peor caso fue cuando los pesos se dividieron 50/50. Pero en la versión aleatoria, dado que los pesos se utilizan como probabilidades, todavía habría una probabilidad del 50/50 de acertar. Además, generalizar para multiplicar los pesos de los expertos incorrectos por en lugar de estrictamente nos permite equilibrar la dependencia de y . Esta compensación se cuantificará en la sección de análisis. ${\displaystyle \beta <1}$ ${\displaystyle {\frac {1}{2}}}$ ${\displaystyle m}$ ${\displaystyle \log _{2}n}$

Análisis

Sea el peso total de todos los expertos en la ronda . Sea también la fracción del peso asignado a los expertos que predicen la respuesta incorrecta en la ronda . Por último, sea el número total de rondas en el proceso. ${\displaystyle W_{t}}$ ${\displaystyle t}$ ${\displaystyle F_{t}}$ ${\displaystyle t}$ ${\displaystyle N}$

Por definición, es la probabilidad de que el algoritmo cometa un error en la ronda . De la linealidad de la expectativa se deduce que si denota el número total de errores cometidos durante todo el proceso, . ${\displaystyle F_{t}}$ ${\displaystyle t}$ ${\displaystyle M}$ ${\displaystyle E[M]=\sum _{t=1}^{N}F_{t}}$

Después de la ronda , el peso total se reduce en , ya que todos los pesos correspondientes a una respuesta incorrecta se multiplican por . Entonces se deduce que . Al realizar la telescopía, ya que , se deduce que el peso total después de que el proceso concluye es ${\displaystyle t}$ ${\displaystyle \ (1-\beta )F_{t}W_{t}}$ ${\displaystyle \ \beta <1}$ ${\displaystyle W_{t+1}=W_{t}(1-(1-\beta )F_{t})}$ ${\displaystyle W_{1}=n}$

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

Por otra parte, supongamos que es el número de errores cometidos por el experto con mejor desempeño. Al final, este experto tiene un peso . Se deduce, entonces, que el peso total es al menos este; en otras palabras, . Esta desigualdad y el resultado anterior implican ${\displaystyle \ m}$ ${\displaystyle \ \beta ^{m}}$ ${\displaystyle \ W\geq \beta ^{m}}$

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

Tomando el logaritmo natural de ambos lados obtenemos

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

Ahora, la serie de Taylor del logaritmo natural es

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

En particular, se deduce que . Por lo tanto, ${\displaystyle \ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}}$

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

Recordando esto y reordenando, se deduce que ${\displaystyle E[M]=\sum _{t=1}^{N}F_{t}}$

${\displaystyle {\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}}}$

Ahora bien, como se ve a continuación, la primera constante tiende a ; sin embargo, la segunda tiende a . Para cuantificar esta disyuntiva, definamos como la penalización asociada con una predicción incorrecta. Luego, aplicando nuevamente la serie de Taylor del logaritmo natural, ${\displaystyle \beta \to 1}$ ${\displaystyle 1}$ ${\displaystyle +\infty }$ ${\displaystyle \varepsilon =1-\beta }$

${\displaystyle {\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}}}$

De ello se deduce que el límite de error, para α pequeño , se puede escribir en la forma . ${\displaystyle \varepsilon }$ ${\displaystyle \ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)}$

En inglés, cuanto menos penalicemos a los expertos por sus errores, más expertos adicionales provocarán errores iniciales, pero más nos acercaremos a capturar la precisión predictiva del mejor experto a medida que pase el tiempo. En particular, dado un valor suficientemente bajo y suficientes rondas, el algoritmo de mayoría ponderada aleatoria puede acercarse arbitrariamente a la tasa de predicción correcta del mejor experto. ${\displaystyle \varepsilon }$

En particular, siempre que sea suficientemente grande en comparación con (para que su relación sea suficientemente pequeña), podemos asignar ${\displaystyle m}$ ${\displaystyle \ln(n)}$

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

Podemos obtener un límite superior en el número de errores igual a

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

Esto implica que el "límite de arrepentimiento" del algoritmo (es decir, cuánto peor se desempeña que el mejor experto) es sublineal, en . ${\displaystyle O({\sqrt {m\ln(n)}})}$

Revisando la motivación

Recordemos que la motivación para el algoritmo de mayoría ponderada aleatoria se dio con un ejemplo en el que el mejor experto comete un error el 20% de las veces. Precisamente, en rondas con expertos, donde el mejor experto comete errores, el algoritmo de mayoría ponderada determinista solo garantiza un límite superior de . Del análisis anterior, se deduce que minimizar el número de errores esperados en el peor de los casos es equivalente a minimizar la función ${\displaystyle N=100}$ ${\displaystyle n=10}$ ${\displaystyle m=20}$ ${\displaystyle 2.4(\log _{2}10+20)\approx 56}$

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

Los métodos computacionales muestran que el valor óptimo es aproximadamente , lo que da como resultado el número mínimo de errores esperados en el peor de los casos de . Cuando se aumenta el número de rondas (por ejemplo, a ) mientras se mantiene igual la tasa de precisión del mejor experto, la mejora puede ser incluso más drástica; el algoritmo de mayoría ponderada garantiza solo una tasa de error en el peor de los casos del 48,0 %, pero el algoritmo de mayoría ponderada aleatoria, cuando se ajusta correctamente al valor óptimo de , logra una tasa de error en el peor de los casos del 20,2 %. ${\displaystyle \beta \approx 0.641}$ ${\displaystyle E[M]\approx 31.19}$ ${\displaystyle N=1000000}$ ${\displaystyle \varepsilon \approx 0.0117}$

Usos del algoritmo de mayoría ponderada aleatoria (RWMA)

El algoritmo de mayoría ponderada aleatoria se puede utilizar para combinar varios algoritmos, en cuyo caso se puede esperar que el algoritmo RWMA tenga un rendimiento casi tan bueno como el mejor de los algoritmos originales en retrospectiva. Tenga en cuenta que el algoritmo RWMA se puede generalizar para resolver problemas que no tienen variables de error binarias, lo que lo hace útil para una amplia clase de problemas.

Además, se puede aplicar el algoritmo de mayoría ponderada aleatoria en situaciones en las que los expertos toman decisiones que no se pueden combinar (o no se pueden combinar fácilmente). Por ejemplo, el algoritmo de mayoría ponderada aleatoria se puede aplicar a juegos repetidos o al problema de la ruta más corta en línea. En el problema de la ruta más corta en línea, cada experto le indica una forma diferente de conducir hasta el trabajo. Usted elige una ruta utilizando el algoritmo de mayoría ponderada aleatoria. Más tarde, descubre qué tan bien le hubiera ido utilizando todas las rutas sugeridas y penaliza de manera apropiada. El objetivo es tener una pérdida esperada no mucho mayor que la pérdida del mejor experto.

Aplicaciones en software

El algoritmo de mayoría ponderada aleatoria se ha propuesto como un nuevo método para varias aplicaciones prácticas de software, particularmente en los dominios de detección de errores y ciberseguridad. ^{[3] [4]} Por ejemplo, Varsha y Madhavu (2021) describen cómo se puede utilizar el algoritmo de mayoría ponderada aleatoria para reemplazar la votación convencional dentro de un enfoque de clasificación de bosque aleatorio para detectar amenazas internas. Utilizando resultados experimentales, muestran que este enfoque obtuvo un mayor nivel de precisión y recuperación en comparación con el algoritmo de bosque aleatorio estándar. Moustafa et al. (2018) han estudiado cómo se podría utilizar un clasificador de conjunto basado en el algoritmo de mayoría ponderada aleatoria para detectar errores en una etapa más temprana del proceso de desarrollo de software, después de haber sido entrenado en repositorios de software existentes.

Extensiones

• Problema del bandido multiarmado .
• Algoritmo eficiente para algunos casos con muchos expertos.
• Configuración de expertos/"especialistas" del sueño.

Véase también

• Aprendizaje automático
• Algoritmo de mayoría ponderada
• Teoría de juegos
• Bandido de múltiples brazos

Referencias

1. Littlestone, N.; Warmuth, M. (1994). "El algoritmo de mayoría ponderada". Información y computación . 108 (2): 212–261. doi : 10.1006/inco.1994.1009 .
2. "COS 511: Fundamentos del aprendizaje automático" (PDF) . 20 de marzo de 2006.
3. Suresh, P. Varsha; Madhavu, Minu Lalitha (2021). "Ataque interno: detección de ciberataques internos mediante aprendizaje automático". 2021 12.ª Conferencia internacional sobre tecnologías informáticas, de comunicación y de redes (ICCCNT) . págs. 1–7. doi :10.1109/ICCCNT51525.2021.9579549. ISBN 978-1-7281-8595-8.
4. Moustafa, Sammar; El Nainay, Mustafa Y; El Makky, Nagwa; Abougabal, Mohamed S. (2018). "Predicción de errores de software mediante técnicas de votación por mayoría ponderada". Revista de ingeniería de Alejandría . 57 (4): 2763–2774. doi : 10.1016/j.aej.2018.01.003 .

Lectura adicional

• Mayoría ponderada y mayoría ponderada aleatoria
• Teoría del aprendizaje automático de Avrim Blum (2004)
• Rob Schapire 2006 Fundamentos del aprendizaje automático
• Predicción a partir de los consejos de los expertos
• Uri Feige, Robi Krauthgamer, Moni Naor. Teoría de juegos algorítmicos
• Fundamentos teóricos del aprendizaje automático (notas) de Nika Haghtalab 2020