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 agrega predicciones de expertos a una serie de problemas de decisión. ^{[ 1 ]} Es un método simple y eficaz basado en 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 con la mejor predicción.

Imaginemos que cada mañana, antes de la apertura de la bolsa , recibimos una predicción de cada uno de nuestros "expertos" sobre si el mercado subirá o bajará. Nuestro objetivo es combinar estas predicciones en una sola, que luego utilizaremos para decidir si comprar o vender ese día. El principal desafío radica en que desconocemos qué expertos darán mejores o peores predicciones. El RWMA nos ofrece una forma de realizar esta combinación, de manera que nuestro historial de predicciones sea prácticamente tan bueno como el del experto que, en retrospectiva, dio las predicciones más precisas.

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 1 para cada ronda: sumar el peso de cada experto a la opción que predijeron Predice la opción con la mayor suma ponderada. multiplicar los pesos de todos los expertos que predijeron erróneamente por${\displaystyle {\frac {1}{2}}}$

Supongamos que hay${\displaystyle n}$expertos y el mejor experto hace${\displaystyle m}$errores. Luego, el algoritmo de mayoría ponderada (WMA) hace como máximo${\displaystyle 2.4(\log _{2}n+m)}$errores. 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${\displaystyle N=100}$rondas usando${\displaystyle n=10}$expertos, el mejor experto hace${\displaystyle m=20}$errores. Entonces, el algoritmo de mayoría ponderada solo garantiza un límite superior de${\displaystyle 2.4(\log _{2}10+20)\approx 56}$errores.

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

Inspirándonos en el algoritmo del Método de Actualización de Pesos Multiplicativos , realizaremos predicciones probabilísticas basadas en el desempeño anterior de los expertos. De forma similar al WMA, cada vez que un experto realice una predicción errónea, disminuiremos su peso. Siguiendo el modelo del MWUM, utilizaremos los pesos para crear una distribución de probabilidad sobre las acciones y seleccionaremos nuestra acción a partir de esta distribución (en lugar de elegir deterministamente el voto mayoritario como lo hace el WMA). ^{[ 2 ]}

El algoritmo de mayoría ponderada aleatoria es un intento de mejorar la dependencia del límite de error del WMA en${\displaystyle m}$En lugar de predecir basándose en el voto mayoritario, 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).

Precisamente, si${\displaystyle w_{i}}$es el peso del experto${\displaystyle i}$, dejar${\displaystyle W=\sum _ {i}w_ {i}}$Seguiremos las recomendaciones de los expertos.${\displaystyle i}$con probabilidad${\displaystyle {\frac {w_{i}}{W}}}$Esto da como resultado el siguiente algoritmo:

Inicializar todos los expertos con peso 1. para cada ronda: Suma los pesos de todos los expertos para obtener el peso total.${\displaystyle W}$ elegir experto${\displaystyle i}$aleatoriamente con probabilidad${\displaystyle {\frac {w_{i}}{W}}}$ Predice 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 debe seleccionar una de las respuestas como correcta antes de que lancemos la moneda. Esta es una suposición razonable, por ejemplo, en el caso del mercado de valores mencionado 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 se daba cuando los pesos se dividían 50/50. Pero en la versión aleatoria, dado que los pesos se utilizan como probabilidades, seguiría habiendo una probabilidad del 50/50 de acertar. Además, generalizando a multiplicar los pesos de los expertos incorrectos por${\displaystyle \beta <1}$en lugar de estrictamente${\displaystyle {\frac {1}{2}}}$nos permite hacer un intercambio entre la dependencia de${\displaystyle m}$y${\displaystyle \log _{2}n}$Esta disyuntiva se cuantificará en la sección de análisis.

Dejar${\displaystyle W_{t}}$denota el peso total de todos los expertos en la ronda${\displaystyle t}$. También deja${\displaystyle F_{t}}$denota la fracción de peso asignada a los expertos que predicen la respuesta incorrecta en la ronda${\displaystyle t}$. Finalmente, dejemos${\displaystyle N}$sea ​​el número total de rondas en el proceso.

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

Después de la ronda${\displaystyle t}$, el peso total disminuye en${\displaystyle \ (1-\beta )F_{t}W_{t}}$, ya que todos los pesos correspondientes a una respuesta incorrecta se multiplican por${\displaystyle \ \beta <1}$De ello se deduce que${\displaystyle W_{t+1}=W_{t}(1-(1-\beta )F_{t})}$. Al extenderse telescópicamente, ya que${\displaystyle W_{1}=n}$De ello se deduce que el peso total una vez finalizado el proceso es

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

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

${\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 se obtiene

${\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${\displaystyle \ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}}$. De este modo,

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

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

${\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, como${\displaystyle \beta \to 1}$Desde abajo, la primera constante tiende a${\displaystyle 1}$; sin embargo, la segunda constante tiende a${\displaystyle +\infty }$Para cuantificar esta compensación, defina${\displaystyle \varepsilon =1-\beta }$ser la penalización asociada a hacer una predicción incorrecta. Luego, aplicando nuevamente la serie de Taylor del logaritmo natural,

${\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 error está ligado, para pequeños${\displaystyle \varepsilon }$, se puede escribir en la forma${\displaystyle \ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)}$.

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

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

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

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${\displaystyle N=100}$rondas, con${\displaystyle n=10}$expertos, donde el mejor experto hace${\displaystyle m=20}$errores, el algoritmo determinista de mayoría ponderada solo garantiza un límite superior de${\displaystyle 2.4(\log _{2}10+20)\approx 56}$Según el 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 {\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${\displaystyle \beta \approx 0.641}$, lo que resulta en el número mínimo de errores esperados en el peor de los casos.${\displaystyle E[M]\approx 31.19}$. Cuando se aumenta el número de rondas (por ejemplo, a${\displaystyle N=1000000}$) mientras que la tasa de precisión del mejor experto se mantiene igual, la mejora puede ser aún más dramática; 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 adecuadamente al valor óptimo de${\displaystyle \varepsilon \approx 0.0117}$, logra una tasa de error en el peor de los casos del 20,2%.

El algoritmo de mayoría ponderada aleatoria (RWMA) puede utilizarse para combinar varios algoritmos, en cuyo caso se espera que su rendimiento sea prácticamente igual al del mejor de los algoritmos originales, a posteriori. Cabe destacar que el RWMA puede generalizarse para resolver problemas que no contienen variables de error binarias, lo que lo hace útil para una amplia gama de problemas.

Además, el algoritmo de mayoría ponderada aleatoria (RWMA) se puede aplicar en situaciones donde los expertos toman decisiones que no se pueden combinar (o no se pueden combinar fácilmente). Por ejemplo, el RWMA se puede aplicar a juegos repetidos o al problema del camino más corto en línea. En este último, cada experto sugiere una ruta diferente para ir al trabajo. Se elige una ruta usando el RWMA. Posteriormente, se determina qué tan bien se habría obtenido el resultado con todas las rutas sugeridas y se aplica la penalización correspondiente. El objetivo es que la pérdida esperada no sea mucho mayor que la del mejor experto.

• Problema del bandido multi-brazo .
• Algoritmo eficiente para algunos casos con muchos expertos.
• Entorno de expertos/especialistas en sueño.

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

• Mayoría ponderada y mayoría ponderada aleatoria
• Avrim Blum (2004) teoría del aprendizaje automático
• Rob Schapire, 2006, Fundamentos del aprendizaje automático
• Predicciones basadas en el consejo de expertos
• Uri Feige, Robi Krauthgamer, Moni Naor. Teoría de juegos algorítmicos
• Nika Haghtalab 2020 Fundamentos teóricos del aprendizaje automático (Apuntes)