El método de actualización de pesos multiplicativos es una técnica algorítmica más comúnmente utilizada para la toma de decisiones y la predicción, y también ampliamente implementada en la teoría de juegos y el diseño de algoritmos. El caso de uso más simple es el problema de la predicción a partir del asesoramiento de un experto, en el que un responsable de la toma de decisiones debe decidir iterativamente sobre un experto cuyo consejo seguir. El método asigna ponderaciones iniciales a los expertos (normalmente ponderaciones iniciales idénticas) y actualiza estas ponderaciones de forma multiplicativa e iterativa de acuerdo con la retroalimentación de qué tan bien se desempeñó un experto: reduciéndola en caso de desempeño deficiente y aumentándola en caso contrario. [1] Se descubrió repetidamente en campos muy diversos, como el aprendizaje automático ( AdaBoost , Winnow, Hedge), optimización (resolución de programas lineales ), informática teórica (diseño de algoritmos rápidos para LP y SDP ) y teoría de juegos .
Nombre
"Pesos multiplicativos" implica la regla iterativa utilizada en los algoritmos derivados del método de actualización del peso multiplicativo. [2] Se le da con diferentes nombres en los diferentes campos donde fue descubierto o redescubierto.
Historia y antecedentes
La primera versión conocida de esta técnica estaba en un algoritmo llamado " juego ficticio " que se propuso en la teoría de juegos a principios de la década de 1950. Grigoriadis y Khachiyan [3] aplicaron una variante aleatoria de "juego ficticio" para resolver juegos de suma cero de dos jugadores de manera eficiente utilizando el algoritmo de pesos multiplicativos. En este caso, el jugador asigna mayor peso a las acciones que tuvieron un mejor resultado y elige su estrategia basándose en estos pesos. En el aprendizaje automático , Littlestone aplicó la forma más temprana de la regla de actualización de pesos multiplicativos en su famoso algoritmo de aventar , que es similar al algoritmo de aprendizaje de perceptrones anterior de Minsky y Papert . Más tarde, generalizó el algoritmo de aventar al algoritmo de mayoría ponderada. Freund y Schapire siguieron sus pasos y generalizaron el algoritmo de aventar en forma de algoritmo de cobertura.
El algoritmo de pesos multiplicativos también se aplica ampliamente en geometría computacional , como el algoritmo de Kenneth Clarkson para programación lineal (LP) con un número limitado de variables en tiempo lineal. [4] [5] Más tarde, Bronnimann y Goodrich emplearon métodos análogos para encontrar cubiertas de conjuntos para hipergráficos con pequeñas dimensiones de VC . [6]
En el campo de problemas de investigación de operaciones y toma de decisiones estadísticas en línea, el algoritmo de mayoría ponderada y sus versiones más complicadas se han encontrado de forma independiente.
En el campo de la informática, algunos investigadores han observado previamente las estrechas relaciones entre los algoritmos de actualización multiplicativa utilizados en diferentes contextos. Young descubrió las similitudes entre los algoritmos LP rápidos y el método de estimadores pesimistas de Raghavan para la desaleatorización de los algoritmos de redondeo aleatorios; Klivans y Servedio vincularon los algoritmos de impulso en la teoría del aprendizaje a las pruebas del XOR Lemma de Yao; Garg y Khandekar definieron un marco común para problemas de optimización convexa que contiene a Garg-Konemann y Plotkin-Shmoys-Tardos como subcasas. [1]
Configuración general
Se debe tomar una decisión binaria basada en las opiniones de n expertos para lograr una recompensa asociada. En la primera ronda, todas las opiniones de los expertos tienen el mismo peso. El tomador de decisiones tomará la primera decisión basándose en la mayoría de las predicciones de los expertos. Luego, en cada ronda sucesiva, el tomador de decisiones actualizará repetidamente el peso de la opinión de cada experto en función de la exactitud de sus predicciones anteriores. Los ejemplos de la vida real incluyen predecir si llueve mañana o si el mercado de valores subirá o bajará.
Análisis de algoritmos
Algoritmo de reducción a la mitad [2]
Dado un juego secuencial entre un adversario y un agregador asesorado por N expertos, el objetivo es que el agregador cometa la menor cantidad de errores posible. Suponga que hay un experto entre los N expertos que siempre da la predicción correcta. En el algoritmo de reducción a la mitad, solo se retienen los expertos consistentes. Los expertos que cometan errores serán despedidos. Para cada decisión, el agregador decide por mayoría de votos entre los expertos restantes. Por lo tanto, cada vez que el agregador comete un error, al menos la mitad de los expertos restantes son despedidos. El agregador comete como máximo errores de log 2 ( N ) . [2]
Algoritmo de mayoría ponderada [1] [7]
A diferencia del algoritmo de reducción a la mitad que descarta a los expertos que han cometido errores, el algoritmo de mayoría ponderada descarta sus consejos. Dada la misma configuración de "asesoramiento de expertos", suponga que tenemos n decisiones y necesitamos seleccionar una decisión para cada ciclo. En cada ciclo, cada decisión tiene un costo. Todos los costos se revelarán después de realizar la elección. El costo es 0 si el experto tiene razón y 1 en caso contrario. El objetivo de este algoritmo es limitar sus pérdidas acumulativas a aproximadamente lo mismo que el mejor de los expertos. El primer algoritmo que toma decisiones basadas en el voto de la mayoría en cada iteración no funciona, ya que la mayoría de los expertos pueden equivocarse constantemente en todo momento. El algoritmo de mayoría ponderada corrige el algoritmo trivial anterior manteniendo un peso de expertos en lugar de fijar el costo en 1 o 0. [1] Esto cometería menos errores en comparación con el algoritmo de reducción a la mitad.
Inicialización : Arreglar un . Para cada experto, asocie el peso ≔1. Para = , , ..., 1 . Realice la predicción dada por la mayoría ponderada de las predicciones de los expertos en función de sus ponderaciones. . Es decir, elegir 0 o 1 dependiendo de qué predicción tenga un mayor peso total de expertos que la aconsejen (rompiendo empates de forma arbitraria). 2 . Por cada experto i que predijo incorrectamente, disminuya su peso para la siguiente ronda multiplicándolo por un factor de (1-η): = (regla de actualización)
Si , el peso del consejo del experto seguirá siendo el mismo. Cuándoaumenta, el peso de los consejos del experto disminuirá. Tenga en cuenta que algunos investigadores corrigen en el algoritmo de mayoría ponderada.
Después pasos, deja sea el número de errores del experto i y sea el número de errores que ha cometido nuestro algoritmo. Entonces tenemos el siguiente límite para cada:
.
En particular, esto es válido para i, que es el mejor experto. Dado que el mejor experto tendrá menos, dará el mejor límite sobre el número de errores cometidos por el algoritmo en su conjunto.
Algoritmo de mayoría ponderada aleatoria [2] [8]
Dada la misma configuración con N expertos. Considere la situación especial en la que las proporciones de expertos que predicen positivos y negativos, contando los pesos, se acercan al 50%. Entonces, podría haber un empate. Siguiendo la regla de actualización del peso en el algoritmo de mayoría ponderada, las predicciones realizadas por el algoritmo serían aleatorias. El algoritmo calcula las probabilidades de los expertos que predicen positivos o negativos, y luego toma una decisión aleatoria basada en la fracción calculada:
predecir
dónde
.
El número de errores cometidos por el algoritmo de mayoría ponderada aleatoria se limita a:
dónde y .
Tenga en cuenta que solo el algoritmo de aprendizaje es aleatorio. El supuesto subyacente es que los ejemplos y las predicciones de los expertos no son aleatorios. La única aleatoriedad es la aleatoriedad en la que el alumno hace su propia predicción. En este algoritmo aleatorio, Si . En comparación con el algoritmo ponderado, esta aleatoriedad redujo a la mitad el número de errores que va a cometer el algoritmo. [9] Sin embargo, es importante tener en cuenta que en algunas investigaciones, las personas definen en el algoritmo de mayoría ponderada y permitir en el algoritmo de mayoría ponderada aleatoria . [2]
Aplicaciones
El método de pesos multiplicativos se usa generalmente para resolver un problema de optimización restringido. Deje que cada experto sea la restricción en el problema y los eventos representen los puntos en el área de interés. El castigo del experto corresponde a qué tan bien se satisface su correspondiente restricción en el punto representado por un evento. [1]
Resolviendo juegos de suma cero aproximadamente (algoritmo de Oracle): [1] [9]
Supongamos que nos dieron la distribución en expertos. Dejar = matriz de pagos de un juego finito de suma cero de dos jugadores, con filas.
Cuando el jugador de la fila plan de usos y el jugador de la columna plan de usos , la recompensa del jugador es ≔, asumiendo .
Si jugador elige acción de una distribución sobre las filas, luego el resultado esperado para el jugador seleccionando acción es .
Para maximizar , jugador debería elegir plan . Del mismo modo, la recompensa esperada para el jugador es . Elegir planminimizaría esta recompensa. Por el teorema Min-Max de John Von Neumann, obtenemos:
donde P e i cambian sobre las distribuciones sobre filas, Q yj cambian sobre las columnas.
Entonces, deja denotar el valor común de las cantidades anteriores, también denominado como el "valor del juego". Dejarser un parámetro de error. Para resolver el juego de suma cero limitado por el error aditivo de,
Entonces, hay un algoritmo que resuelve un juego de suma cero hasta un factor aditivo de δ usando O ( log 2 ( n ) /) llamadas a ORACLE, con un tiempo de procesamiento adicional de O (n) por llamada [9]
Bailey y Piliouras demostraron que, aunque el comportamiento promedio en el tiempo de la actualización de los pesos multiplicativos converge a los equilibrios de Nash en los juegos de suma cero, el comportamiento del día a día (última iteración) se aleja de él. [10]
Aprendizaje automático
En el aprendizaje automático, Littlestone y Warmuth generalizaron el algoritmo de aventar al algoritmo de mayoría ponderada. [11] Más tarde, Freund y Schapire lo generalizaron en forma de algoritmo de cobertura. [12] El algoritmo AdaBoost formulado por Yoav Freund y Robert Schapire también empleó el método de actualización de peso multiplicativo. [1]
Algoritmo de aventar
Basado en el conocimiento actual en algoritmos, el método de actualización de peso multiplicativo se utilizó por primera vez en el algoritmo de aventar de Littlestone. [1] Se utiliza en aprendizaje automático para resolver un programa lineal.
Dado ejemplos etiquetados dónde son vectores de características, y son sus etiquetas.
El objetivo es encontrar ponderaciones no negativas de modo que, para todos los ejemplos, el signo de la combinación ponderada de las características coincida con sus etiquetas. Es decir, exigir que para todos . Sin pérdida de generalidad, suponga que el peso total es 1 para que formen una distribución. Por lo tanto, por conveniencia de notación, redefina ser - estar , el problema se reduce a encontrar una solución al siguiente LP:
, , .
Esta es una forma general de LP.
Algoritmo de cobertura [2]
El algoritmo de cobertura es similar al algoritmo de mayoría ponderada. Sin embargo, sus reglas de actualización exponencial son diferentes. [2] Generalmente se usa para resolver el problema de la asignación binaria en la que necesitamos asignar diferentes porciones de recursos en N opciones diferentes. La pérdida con cada opción está disponible al final de cada iteración. El objetivo es reducir la pérdida total sufrida por una asignación en particular. A continuación, se revisa la asignación para la siguiente iteración, en función de la pérdida total sufrida en la iteración actual mediante la actualización multiplicativa. [13]
Análisis
Asume la tasa de aprendizaje y para , es elegido por Hedge. Entonces para todos los expertos,
Inicialización : corrige un. Para cada experto, asocie el peso≔1 Para t = 1,2, ..., T:
1. Elija la distribución dónde . 2. Observe el costo de la decisión. . 3. Establecer ).
Algoritmo AdaBoost
Este algoritmo [12] mantiene un conjunto de pesossobre los ejemplos de formación. En cada iteración, una distribución se calcula normalizando estos pesos. Esta distribución se alimenta al aprendiz débil WeakLearn que genera una hipótesisque (con suerte) tiene un pequeño error con respecto a la distribución. Usando la nueva hipótesis, AdaBoost genera el siguiente vector de peso . El proceso se repite. Después de T tales iteraciones, la hipótesis finales la salida. La hipótesiscombina los resultados de las hipótesis T débiles utilizando un voto mayoritario ponderado. [12]
Entrada : Secuencia de ejemplos etiquetados , ), ..., ( , ) Distribución sobre el ejemplos Algoritmo de aprendizaje débil "'WeakLearn"' Entero especificar el número de iteraciones Inicializar el vector de peso: por , ..., .Hacer para , ..., 1 . Colocar . 2 . Llame a WeakLearn , proporcionándole la distribución ; recuperar una hipótesis [0,1]. 3 . Calcule el error de | . 4 . Colocar . 5 . Establezca el nuevo vector de peso para que sea .Genere la hipótesis:
Resolviendo programas lineales aproximadamente [14]
Problema
Dado un matriz y , Hay una tal que ?
(1)
Suposición
Usando el algoritmo de Oracle para resolver un problema de suma cero, con un parámetro de error , la salida sería un punto tal que o una prueba de que no existe, es decir, no hay solución para este sistema lineal de desigualdades.
Solución
Vector dado , resuelve el siguiente problema relajado
(2)
Si existe ax que satisface (1), entonces x satisface (2) para todos . Lo contrario de esta afirmación también es cierto. Suponga que si Oracle devuelve una solución factible para un, la solución devuelve tiene un ancho acotado . Entonces, si hay una solución para (1), entonces hay un algoritmo que su salida x satisface el sistema (2) hasta un error aditivo de. El algoritmo hace como máximollamadas a un oráculo de ancho limitado para el problema (2). Lo contrapositivo también es cierto. Las actualizaciones multiplicativas se aplican en el algoritmo en este caso.
Otras aplicaciones
Teoría de juegos evolutivos
La actualización de pesos multiplicativos es la variante en tiempo discreto de la ecuación del replicador (dinámica del replicador), que es un modelo de uso común en la teoría de juegos evolutivos . Converge al equilibrio de Nash cuando se aplica a un juego de congestión . [15]
Investigación operativa y toma de decisiones estadísticas en línea [1]
En el campo de problemas de investigación de operaciones y toma de decisiones estadísticas en línea, el algoritmo de mayoría ponderada y sus versiones más complicadas se han encontrado de forma independiente.
Geometría Computacional
El algoritmo de pesos multiplicativos también se aplica ampliamente en geometría computacional , [1] como el algoritmo de Clarkson para programación lineal (LP) con un número limitado de variables en tiempo lineal. [4] [5] Más tarde, Bronnimann y Goodrich emplearon métodos análogos para encontrar Cubiertas de conjuntos para hipergráficos con una pequeña dimensión de VC . [6]
Método de descenso de gradiente [1]
Actualización de pesos multiplicativos de matrices [1]
Plotkin, Shmoys, Tardos estructura para empaquetar / cubrir LPs [1]
Aproximación a los problemas de flujo de múltiples productos básicos [1]
O (logn) - aproximación para muchos problemas NP-difíciles [1]
Aprendizaje teórico y refuerzo [1]
Conjuntos estrictos y el lema XOR [1]
Algoritmo de Hannan y pesos multiplicativos [1]
Optimización convexa en línea [1]
Referencias
- ^ a b c d e f g h i j k l m n o p q r s Arora, Sanjeev ; Hazan, Elad; Kale, Satyen (2012). "El método de actualización de pesos multiplicativos: un meta-algoritmo y aplicaciones" . Teoría de la Computación . 8 : 121-164. doi : 10.4086 / toc.2012.v008a006 .
- ^ a b c d e f g "El algoritmo de pesos multiplicativos *" (PDF) . Consultado el 9 de noviembre de 2016 .
- ^ Grigoriadis, Michael D .; Khachiyan, Leonid G. (1995). "Un algoritmo de aproximación aleatorizado en tiempo sublineal para juegos matriciales". Cartas de investigación operativa . 18 (2): 53–58. doi : 10.1016 / 0167-6377 (95) 00032-0 .
- ^ a b Kenneth L. Clarkson. Un algoritmo de Las Vegas para programación lineal cuando la dimensión es pequeña. , En Proc. 29th FOCS, págs. 452–456. IEEE Comp. Soc. Press, 1988. [doi: 10.1109 / SFCS.1988.21961] 123, 152.
- ^ a b Kenneth L. Clarkson. Un algoritmo de Las Vegas para programación lineal y entera cuando la dimensión es pequeña. , Journal of the ACM, 42: 488–499, 1995. [doi: 10.1145 / 201019.201036] 123, 152.
- ^ a b H. Bronnimann y MT Goodrich. Cubiertas de juego casi óptimas en dimensión VC finita. , Computación discreta. Geom. , 14: 463–479, 1995. Versión preliminar en 10th Ann. Symp. Comp. Geom. (SCG'94). [doi: 10.1007 / BF02570718] 123, 152
- ^ "Lección 8: Toma de decisiones bajo incertidumbre total: el algoritmo de ponderación multiplicativa" (PDF) . 2013.
- ^ "COS 511: Fundamentos del aprendizaje automático" (PDF) . 20 de marzo de 2006.
- ^ a b c "Kit de herramientas de un algoritmo" . 8 de diciembre de 2009 . Consultado el 9 de noviembre de 2016 .
- ^ Bailey, James P. y Georgios Piliouras. "Actualización de pesos multiplicativos en juegos de suma cero". Actas de la Conferencia ACM 2018 sobre Economía y Computación. ACM, 2018.
- ^ Foster, Dean P .; Vohra, Rakesh (1999). "Lamento en el problema de decisión en línea" (PDF) . Juegos y comportamiento económico . 29 (1–2): 7–35. doi : 10.1006 / juego.1999.0740 .
- ^ a b c Yoav, Freund. Robert, E. Schapire (1996). TA Generalización de la teoría de la decisión del aprendizaje en línea y una aplicación para impulsar * , p. 55. Revista de ciencias informáticas y de sistemas.
- ^ "Aprendizaje en línea de expertos: mayoría ponderada y cobertura" (PDF) . Consultado el 7 de diciembre de 2016 .
- ^ "Fundamentos de la optimización convexa" (PDF) . Consultado el 9 de noviembre de 2016 .
- ^ Kleinberg, Robert, Georgios Piliouras y Eva Tardos. "Las actualizaciones multiplicativas superan el aprendizaje genérico sin arrepentimiento en los juegos de congestión". Actas del cuadragésimo primer simposio anual ACM sobre teoría de la computación. ACM, 2009.
enlaces externos
- The Game Theory of Life en un artículo de la revista Quanta que describe el uso del método para la biología evolutiva en un artículo de Erick Chastain, Adi Livnat, Christos Papadimitriou y Umesh Vazirani