Método de actualización de peso multiplicativo

Técnica algorítmica

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 expertos, en el que quien toma decisiones necesita decidir de forma iterativa qué experto debe 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 sobre qué tan bien se desempeñó un experto: reduciéndola en caso de un desempeño deficiente y aumentándola en caso contrario. ^[1] Fue descubierto repetidamente en campos muy diversos como el aprendizaje automático ( AdaBoost , Winnow , Hedge), la optimización (resolución de programas lineales ), la informática teórica (idealización de algoritmos rápidos para LP y SDP ) y la teoría de juegos .

Nombre

"Pesos multiplicativos" implica la regla iterativa utilizada en algoritmos derivados del método de actualización de pesos multiplicativos. ^[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 fue un algoritmo llamado " juego ficticio " que fue propuesto en la teoría de juegos a principios de los años cincuenta. 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 antigua de la regla de actualización de pesos multiplicativos en su famoso algoritmo winnow , que es similar al anterior algoritmo de aprendizaje de perceptrones de Minsky y Papert . Más tarde, generalizó el algoritmo winnow al algoritmo de mayoría ponderada. Freund y Schapire siguieron sus pasos y generalizaron el algoritmo winnow 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 hipergrafos con pequeñas dimensiones de VC . ^[6]

En el campo de la investigación de operaciones y de los problemas de 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 algoritmos de redondeo aleatorio; Klivans y Servedio vincularon los algoritmos de impulso en la teoría del aprendizaje con las pruebas del lema XOR 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 subcasos. ^[1]

El algoritmo Hedge es un caso especial de descenso de espejos .

Configuración general

Es necesario tomar una decisión binaria basada en las opiniones de n expertos para obtener un beneficio asociado. En la primera ronda, las opiniones de todos los expertos tienen el mismo peso. Quien toma las decisiones tomará la primera decisión basándose en la mayoría de las predicciones de los expertos. Luego, en cada ronda sucesiva, quien toma las decisiones actualizará repetidamente el peso de la opinión de cada experto dependiendo de la exactitud de sus predicciones anteriores. Los ejemplos de la vida real incluyen predecir si lloverá 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 el menor número de errores posible. Supongamos que hay un experto entre los N expertos que siempre da la predicción correcta. En el algoritmo de reducción a la mitad sólo 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 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 log ₂ ( N ) errores. ^[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 descuenta sus consejos. Dada la misma configuración de "consejo de experto", supongamos que tenemos n decisiones y necesitamos seleccionar una decisión para cada ciclo. En cada ciclo, cada decisión conlleva un costo. Todos los costos se revelarán después de hacer la elección. El coste es 0 si el experto acierta y 1 en caso contrario. El objetivo de este algoritmo es limitar sus pérdidas acumuladas a aproximadamente las mismas que las de los mejores expertos. El primer algoritmo que toma decisiones basándose en el voto mayoritario 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 una ponderación 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 asociar el peso ≔1. Para = , ,..., 1 . Haga la predicción dada por la mayoría ponderada de las predicciones de los expertos en función de sus pesos . Es decir, elegir 0 o 1 dependiendo de qué predicción tenga mayor peso total de expertos que la asesoran (rompiendo empates de forma arbitraria). 2 . Por cada experto i que predijo mal, disminuya su peso para la siguiente ronda multiplicándolo por un factor de (1-η): = (regla de actualización) ${\displaystyle \eta \leq 1/2}$ ${\displaystyle {w_{i}}^{1}}$  ${\displaystyle t}$ ${\displaystyle {\mathit {1}}}$ ${\displaystyle {\mathit {2}}}$ ${\displaystyle T}$  ${\displaystyle \mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}}$ ${\displaystyle w_{i}^{t+1}}$ ${\displaystyle (1-\eta )w_{i}^{t}}$

Si , el peso del consejo del experto seguirá siendo el mismo. Cuando aumente, el peso del consejo del experto disminuirá. Tenga en cuenta que algunos investigadores lo fijan en el algoritmo de mayoría ponderada. ${\displaystyle \eta =0}$ ${\displaystyle \eta }$ ${\displaystyle \eta =1/2}$

Después de los pasos, sea el número de errores del experto i y el número de errores que ha cometido nuestro algoritmo. Entonces tenemos el siguiente límite para cada : ${\displaystyle T}$ ${\displaystyle m_{i}^{T}}$ ${\displaystyle M^{T}}$ ${\displaystyle i}$

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

En particular, esto se aplica a i, que es el mejor experto. Dado que el mejor experto tendrá la menor cantidad de errores , dará el mejor límite en el número de errores cometidos por el algoritmo en su conjunto. ${\displaystyle m_{i}^{T}}$

Algoritmo de mayoría ponderada aleatoria

Este algoritmo se puede entender de la siguiente manera: ^{[2] [8]}

Dada la misma configuración con N expertos. Consideremos la situación especial en la que las proporciones de expertos que predicen cosas positivas y negativas, contando las ponderaciones, son cercanas al 50%. Entonces podría haber un empate. Siguiendo la regla de actualización de peso en el algoritmo de mayoría ponderada, las predicciones realizadas por el algoritmo serían aleatorias. El algoritmo calcula las probabilidades de que los expertos predigan cosas positivas o negativas y luego toma una decisión aleatoria basada en la fracción calculada: ^{[ se necesita más explicación ]}

predecir

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

dónde

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

El número de errores cometidos por el algoritmo de mayoría ponderada aleatoria está limitado por:

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

dónde y . ${\displaystyle \alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}}$ ${\displaystyle c_{\beta }={\frac {1}{1-\beta }}}$

Tenga en cuenta que sólo el algoritmo de aprendizaje es aleatorio. La suposición subyacente es que los ejemplos y las predicciones de los expertos no son aleatorios. La única aleatoriedad es aquella 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 la cantidad de errores que cometerá el algoritmo. ^[9] Sin embargo, es importante tener en cuenta que en algunas investigaciones, las personas definen el algoritmo de mayoría ponderada y permiten el algoritmo de mayoría ponderada aleatoria . ^[2] ${\displaystyle \alpha _{\beta }\rightarrow 1}$ ${\displaystyle \beta \rightarrow 1}$ ${\displaystyle \eta =1/2}$ ${\displaystyle 0\leq \eta \leq 1}$

Aplicaciones

El método de pesos multiplicativos se suele utilizar para resolver un problema de optimización restringida. Sea cada experto la restricción del 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 sobre el punto representado por un evento. ^[1]

Resolver juegos de suma cero aproximadamente (algoritmo de Oracle): [1] [9]

Supongamos que nos dieron la distribución de expertos. Sea = matriz de pagos de un juego finito de suma cero para dos jugadores, con filas. ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle n}$

Cuando el jugador de la fila usa un plan y el jugador de la columna usa un plan , el pago del jugador es ≔ , suponiendo . ${\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]}$

Si el jugador elige una acción de una distribución entre las filas, entonces el resultado esperado para el jugador que selecciona la acción es . ${\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]}$

Para maximizar , el jugador debe elegir el plan . De manera similar, el pago esperado para el jugador es . Elegir un plan minimizaría esta recompensa. Por el teorema mínimo-máximo de John Von Neumann, obtenemos: ${\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)}$

donde P e i cambian en las distribuciones de las filas, Q y j cambian en las columnas.

Luego, denotemos el valor común de las cantidades anteriores, también denominado "valor del juego". Sea un parámetro de error. Para resolver el juego de suma cero acotado por el error aditivo de , ${\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 }$

Entonces, existe un algoritmo que resuelve el juego de suma cero hasta un factor aditivo de δ usando O( log ₂ ( n ) / ) llamadas a ORACLE, con un tiempo de procesamiento adicional de O(n) por llamada ^[9] ${\displaystyle \delta ^{2}}$

Bailey y Piliouras demostraron que aunque el comportamiento promedio temporal de la actualización de los pesos multiplicativos converge con los equilibrios de Nash en juegos de suma cero, el comportamiento diario (última iteración) se aleja de él. ^[10]

Aprendizaje automático

En aprendizaje automático, Littlestone y Warmuth generalizaron el algoritmo winnow 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 aventamiento

Basado en el conocimiento actual en algoritmos, el método de actualización de peso multiplicativo se utilizó por primera vez en el algoritmo winnow de Littlestone. ^[1] Se utiliza en aprendizaje automático para resolver un programa lineal.

Se dan ejemplos etiquetados dónde están los vectores de características y sus etiquetas. ${\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 }$

El objetivo es encontrar ponderaciones no negativas tales que, en todos los ejemplos, el signo de la combinación ponderada de las características coincida con sus etiquetas. Es decir, exigir eso 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 como , el problema se reduce a encontrar una solución al siguiente PL: ${\displaystyle l_{j}a_{j}x\geq 0}$ ${\displaystyle j}$ ${\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}$

Esta es la 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 asignación binaria en el 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 particular. Luego 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

Supongamos que Hedge elige la tasa de aprendizaje y para . Entonces para todos los expertos , ${\displaystyle \eta >0}$ ${\displaystyle t\in [T]}$ ${\displaystyle p^{t}}$ ${\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}$

Inicialización : arreglar un archivo . Para cada experto, asociar el peso ≔1 Para t=1,2,...,T: ${\displaystyle \eta >0}$ ${\displaystyle w_{i}^{1}}$

 1. Elija la distribución donde . ${\displaystyle p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}}$ ${\displaystyle \Phi t=\sum _{i}w_{i}^{t}}$ 2. Observe el costo de la decisión . ${\displaystyle m^{t}}$ 3. Establecer  ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}}$).

Algoritmo AdaBoost

Este algoritmo ^[12] mantiene un conjunto de pesos sobre los ejemplos de entrenamiento. En cada iteración , se calcula una distribución normalizando estos pesos. Esta distribución se envía al alumno débil WeakLearn, que genera una hipótesis que (con suerte) tiene un pequeño error con respecto a la distribución. Utilizando la nueva hipótesis , AdaBoost genera el siguiente vector de peso . El proceso se repite. Después de T tales iteraciones, la hipótesis final es el resultado. La hipótesis combina los resultados de las T hipótesis débiles utilizando una mayoría ponderada de votos. ^[12] ${\displaystyle w^{t}}$ ${\displaystyle t}$ ${\displaystyle p^{t}}$ ${\displaystyle h_{t}}$ ${\displaystyle h_{t}}$ ${\displaystyle w^{t+1}}$ ${\displaystyle h_{f}}$ ${\displaystyle h_{f}}$

Aporte : Secuencia de ejemplos etiquetados ( , ),...,( , ) ${\displaystyle N}$ ${\displaystyle x_{1}}$ ${\displaystyle y_{1}}$ ${\displaystyle x_{N}}$ ${\displaystyle y_{N}}$ Distribución sobre los ejemplos. ${\displaystyle D}$ ${\displaystyle N}$ Algoritmo de aprendizaje débil "'WeakLearn"' Entero que especifica el número de iteraciones Inicializa el vector de peso: para . Hazlo por 1 . Colocar . 2 . Llame a WeakLearn , proporcionándole la distribución ; obtener una hipótesis [0,1]. 3 . Calcule el error de . 4 . Colocar . 5 . Establezca el nuevo vector de peso en . ${\displaystyle T}$ ${\displaystyle w_{i}^{1}=D(i)}$ ${\displaystyle i=1,2,...,N}$  ${\displaystyle t=1,2,...,T}$  ${\displaystyle p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}}$ ${\displaystyle p^{t}}$ ${\displaystyle h_{t}:X\rightarrow }$ ${\displaystyle h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}|h_{t}(x_{i})-y_{i}|}$ ${\displaystyle \beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}}$ ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}}$Salida de la hipótesis:

  ${\displaystyle f(x)=h_{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})\\0&{\text{otherwise}}\end{cases}}}$

Resolver programas lineales aproximadamente [14]

Problema

Dada una matriz y , ¿existe tal que ? ${\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)

Suposición

Usando el algoritmo de Oracle para resolver un problema de suma cero, con un parámetro de error , el resultado sería un punto tal que o una prueba que no existe, es decir, no hay solución para este sistema lineal de desigualdades. ${\displaystyle \epsilon >0}$ ${\displaystyle x}$ ${\displaystyle Ax\geq b-\epsilon }$ ${\displaystyle x}$

Solución

Dado el vector , resuelve el siguiente problema relajado ${\displaystyle p\in \Delta _{n}}$

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

Si existe ax que satisface (1), entonces x satisface (2) para todos . La contrapositiva de esta afirmación también es cierta. Supongamos que si Oracle devuelve una solución factible para a , la solución que devuelve tiene un ancho acotado . Entonces, si hay una solución para (1), entonces existe un algoritmo cuyo resultado x satisface el sistema (2) hasta un error aditivo de . El algoritmo realiza como máximo llamadas a un oráculo de ancho limitado para el problema (2). El contrapositivo también es cierto. En este caso, las actualizaciones multiplicativas se aplican en el algoritmo. ${\displaystyle p\in \Delta _{n}}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle \max _{i}|{(Ax)}_{i}-b_{i}|\leq 1}$ ${\displaystyle 2\epsilon }$ ${\displaystyle {\frac {\ln(m)}{\epsilon ^{2}}}}$

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 comúnmente utilizado en la teoría de juegos evolutiva . 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.

En el campo de la investigación de operaciones y de los problemas de 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. ^[1]

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 acotado de variables en tiempo lineal. ^{[4] [5]} Más tarde, Bronnimann y Goodrich emplearon métodos análogos para encontrar Set Cover para hipergrafos con pequeña dimensión VC . ^[6]

Método de descenso de gradiente ^[1]

Actualización de pesos multiplicativos de matrices ^[1]

Plotkin, Shmoys, Tardos estructura para empaquetar / cubrir LP ^[1]

Aproximación de problemas de flujo de múltiples productos ^[1]

O (logn) - aproximación para muchos problemas NP-difíciles ^[1]

Teoría del aprendizaje y potenciación ^[1]

Conjuntos incondicionales y el lema XOR ^[1]

Algoritmo de Hannan y pesos multiplicativos ^[1]

Optimización convexa en línea ^[1]

Referencias

1. Arora, Sanjeev ; Hazán, Elad; Col rizada, Satyen (2012). "El método de actualización de pesos multiplicativos: un metaalgoritmo y aplicaciones". Teoría de la Computación . 8 : 121–164. doi : 10.4086/toc.2012.v008a006 .
2. "El algoritmo de pesos multiplicativos *" (PDF) . Consultado el 9 de noviembre de 2016 .
3. Grigoriadis, Michael D.; Khachiyan, Leonid G. (1995). "Un algoritmo de aproximación aleatoria en tiempo sublineal para juegos matriciales". Cartas de investigación operativa . 18 (2): 53–58. doi :10.1016/0167-6377(95)00032-0.
4. Kenneth L. Clarkson. Un algoritmo de Las Vegas para programación lineal cuando la dimensión es pequeña. , En proceso. 29º FOCS, págs. Comp. IEEE. Soc. Prensa, 1988.[doi:10.1109/SFCS.1988.21961] 123, 152.
5. Kenneth L. Clarkson. Un algoritmo de Las Vegas para programación lineal y entera cuando la dimensión es pequeña. , Revista de la ACM, 42:488–499, 1995. [doi:10.1145/201019.201036] 123, 152.
6. Bronnimann, H.; Goodrich, MT (1995). "Cubiertas de conjunto casi óptimas en dimensiones VC finitas". Geometría discreta y computacional . 14 (4): 463–479. doi : 10.1007/BF02570718 .Versión preliminar en 10º Ann. Síntoma. comp. Geom. (SCG'94).
7. "Conferencia 8: Toma de decisiones bajo total incertidumbre: el algoritmo de peso multiplicativo" (PDF) . 2013.
8. "COS 511: Fundamentos del aprendizaje automático" (PDF) . 20 de marzo de 2006.
9. "Juego de herramientas de un algoritmista". 8 de diciembre de 2009 . Consultado el 9 de noviembre de 2016 .
10. Bailey, James P. y Georgios Piliouras. "Actualización de pesos multiplicativos en juegos de suma cero". Actas de la Conferencia ACM de 2018 sobre Economía y Computación. ACM, 2018.
11. Foster, Dean P.; Vohra, Rakesh (1999). "Arrepentimiento en el problema de la decisión online" (PDF) . Juegos y comportamiento económico . 29 (1–2): 7–35. doi : 10.1006/juego.1999.0740.
12. Yoav, Freund. Robert, E. Schapire (1996). Generalización teórica de decisiones de asistencia técnica del aprendizaje en línea y una aplicación al impulso* , p. 55. revista de ciencias informáticas y de sistemas.
13. "Aprendizaje en línea de expertos: mayoría ponderada y cobertura" (PDF) . Consultado el 7 de diciembre de 2016 .
14. "Fundamentos de la optimización convexa" (PDF) . Consultado el 9 de noviembre de 2016 .
15. 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 de ACM sobre teoría de la informática. ACM, 2009.

enlaces externos

• The Game Theory of Life, un artículo de la revista Quanta que describe el uso del método en biología evolutiva en un artículo de Erick Chastain, Adi Livnat, Christos Papadimitriou y Umesh Vazirani.