Método de actualización de peso multiplicativo

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 un tomador de decisiones necesita decidir iterativamente sobre un experto cuyo consejo seguir. El método asigna pesos iniciales a los expertos (generalmente pesos iniciales idénticos) y actualiza estos pesos de manera multiplicativa e iterativa de acuerdo con la retroalimentación de qué tan bien se desempeñó un experto: reduciéndolo en caso de un desempeño deficiente y aumentándolo en caso contrario. ^[1] Se descubrió 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 (diseño 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 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 winnow , que es similar al algoritmo de aprendizaje de perceptrón anterior 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 acotado 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ña dimensión VC . ^[6]

En el campo de la investigación de operaciones y de los problemas de toma de decisiones estadísticas en línea, se han encontrado de forma independiente el algoritmo de mayoría ponderada y sus versiones más complicadas.

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 de LP rápidos y el método de estimadores pesimistas de Raghavan para la desaleatorización de algoritmos de redondeo aleatorios; Klivans y Servedio vincularon los algoritmos de refuerzo en la teoría del aprendizaje con las pruebas del lema XOR de Yao; Garg y Khandekar definieron un marco común para los 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 espejo .

Configuración general

Se debe tomar una decisión binaria en función de las opiniones de n expertos para obtener un resultado asociado. En la primera ronda, las opiniones de todos los expertos tienen el mismo peso. El responsable de la toma de decisiones tomará la primera decisión basándose en la predicción de la mayoría de los expertos. Luego, en cada ronda sucesiva, actualizará repetidamente el peso de la opinión de cada experto en función de la exactitud de sus predicciones anteriores. Algunos 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 jugado entre un adversario y un agregador que es asesorado por N expertos, el objetivo es que el agregador cometa la menor cantidad 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, solo se conservan los expertos consistentes. Los expertos que cometen errores serán descartados. Para cada decisión, el agregador decide tomando una votación mayoritaria entre los expertos restantes. Por lo tanto, cada vez que el agregador comete un error, al menos la mitad de los expertos restantes son descartados. El agregador comete como máximo $log 2 (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 descarta su asesoramiento. Dada la misma configuración de "asesoramiento de expertos", supongamos que tenemos n decisiones y necesitamos seleccionar una decisión para cada bucle. En cada bucle, cada decisión implica un costo. Todos los costos se revelarán después de tomar la decisión. El costo es 0 si el experto está en lo correcto y 1 en caso contrario. El objetivo de este algoritmo es limitar sus pérdidas acumuladas 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 cada vez. 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 : Fijar un . Para cada experto, asociar el peso ≔1. Para = , ,..., 1 . Realizar 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 un mayor peso total de expertos que la asesoran (deshaciendo los empates arbitrariamente). 2 . Para cada experto i que haya predicho incorrectamente, disminuir su peso para la siguiente ronda multiplicándolo por un factor de (1-η): = (regla de actualización) $\eta \leq 1/2$  $estilo de visualización {w_{i}}^{1}}$   ${\estilo de visualización t}$  ${\mathit {1}}$  ${\mathit {2}}$  ${\estilo de visualización T}$   $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$  $estilo de visualización w_{i}^{t+1}}$  $(1-\eta )w_{i}^{t}$

Si , el peso del consejo del experto permanecerá igual. Cuando aumenta , el peso del consejo del experto disminuirá. Tenga en cuenta que algunos investigadores lo fijan en el algoritmo de mayoría ponderada. $\eta = 0$ ${\estilo de visualización \eta}$ $\eta = 1/2$

Después de los pasos, 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 : ${\estilo de visualización T}$ $Estilo de visualización m_{i}^{T}}$ $Estilo de visualización M^{T}}$ ${\estilo de visualización i}$

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

En particular, esto es válido para i, que es el mejor experto. Dado que el mejor experto tendrá el menor , dará el mejor límite para la cantidad de errores cometidos por el algoritmo en su conjunto. $Estilo de visualización m_{i}^{T}}$

Algoritmo de mayoría ponderada aleatoria

Este algoritmo puede entenderse de la siguiente manera: ^[2]^[8]

Dada la misma configuración con N expertos, considere la situación especial en la que las proporciones de expertos que predicen resultados positivos y negativos, contando los pesos, son cercanas al 50 %. En ese caso, podría haber un empate. Siguiendo la regla de actualización de pesos del algoritmo de mayoría ponderada, las predicciones realizadas por el algoritmo serían aleatorias. El algoritmo calcula las probabilidades de que los expertos predigan resultados positivos o negativos y luego toma una decisión aleatoria en función de la fracción calculada: ^{[ se necesita más explicación ]}

predecir

f(x)={\begin{cases}1&{\text{con probabilidad}}{\frac {q_{1}}{W}}\\0&{\text{en caso contrario}}\end{cases}}

dónde

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

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

  $E\left[\#{\text{errores del alumno}}\right]\leq \alpha _{\beta }\left(\#{\text{ errores del mejor experto}}\right)+c_{\beta }\ln(N)$

donde y . $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ $c_{\beta }={\frac {1}{1-\beta }}$

Tenga en cuenta que solo 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 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 la cantidad de errores que cometerá el algoritmo. ^[9] Sin embargo, es importante señalar que en algunas investigaciones, las personas definen en el algoritmo de mayoría ponderada y permiten en el algoritmo de mayoría ponderada aleatorio . ^[2] $\alpha _{\beta }\rightarrow 1$ $\beta \rightarrow 1$ $\eta = 1/2$ $0\leq \eta \leq 1$

Aplicaciones

El método de pesos multiplicativos se utiliza habitualmente para resolver un problema de optimización con restricciones. 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 restricción correspondiente en el punto representado por un evento. ^[1]

Solución aproximada de juegos de suma cero (algoritmo Oracle):[1][9]

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

Cuando el jugador de la fila usa plan y el jugador de la columna usa plan , la ganancia del jugador es ≔ , asumiendo . $estilo de visualización p_{r}}$ ${\estilo de visualización i}$ $estilo de visualización p_{c}}$ ${\estilo de visualización j}$ $estilo de visualización p_{c}}$ $A\izquierda(i,j\derecha)$ $Estilo de visualización A_{ij}}$ $A\left(i,j\right)\in \left[0,1\right]$

Si el jugador elige una acción de una distribución sobre las filas, entonces el resultado esperado para el jugador que selecciona la acción es . $estilo de visualización p_{r}}$ ${\estilo de visualización i}$ ${\estilo de visualización P}$ $estilo de visualización p_{c}}$ ${\estilo de visualización j}$ $A(P,j)=E_{i\in P}[A(i,j)]$

Para maximizar , el jugador debe elegir el plan . De manera similar, el beneficio esperado para el jugador es . Elegir el plan minimizaría este beneficio. Por el teorema de mínimos y máximos de John Von Neumann, obtenemos: $A\izquierda(P,j\derecha)$ $estilo de visualización p_{c}}$ ${\estilo de visualización j}$ $estilo de visualización p_{l}}$ $A(i,P)=E_{j\in P}[A(i,j)]$ ${\estilo de visualización i}$

  $\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 sobre filas, Q y j cambian en las columnas.

Entonces, denotemos el valor común de las cantidades anteriores, también llamado "valor del juego". Sea un parámetro de error. Para resolver el juego de suma cero limitado por el error aditivo de , $\lambda ^{*}$ $\delta >0$ ${\estilo de visualización \delta}$

  $\lambda ^{*}-\delta \leq \min _{i}A\left(i,q\right)$   $\max _{j}A\left(p,j\right)\leq \lambda ^{*}+\delta$

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

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

Aprendizaje automático

En el 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 Winnow

Basándose en los conocimientos actuales 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 el aprendizaje automático para resolver un programa lineal.

Se dan ejemplos etiquetados donde son vectores de características y son sus etiquetas. ${\estilo de visualización m}$ $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ $a_{j}\in \mathbb {R} ^{n}$ $l_{j}\in \izquierda\{-1,1\derecha\}\cuadrado$

El objetivo es encontrar pesos no negativos de modo que, para todos los ejemplos, el signo de la combinación ponderada de las características coincida con sus etiquetas. Es decir, se requiere que para todos los . Sin pérdida de generalidad, supongamos que el peso total es 1, de modo que forman una distribución. Por lo tanto, por conveniencia de notación, redefinimos como , el problema se reduce a encontrar una solución para el siguiente PL: $l_{j}a_{j}x\geq 0$ ${\estilo de visualización j}$ $Estilo de visualización a_ {j}}$ $Estilo de visualización l_{j}a_{j}}$

  $\forall j=1,2,{\text{…}},m:a_{j}x\geq 0$ , , . ${\estilo de visualización 1*x=1}$  $\para todo 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 utiliza 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, utilizando una actualización multiplicativa. ^[13]

Análisis

Supongamos que la tasa de aprendizaje y para , es elegida por Hedge. Entonces, para todos los expertos , $\eta >0$ $t\en [T]$ $estilo de visualización p^{t}}$ ${\estilo de visualización i}$

  $\suma_{t\leq T}p^{t}m^{t}\suma_{t\leq T}m_{i}^{t}+{\frac {\ln(N)}{\eta }}+\eta T$

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

 1. Elija la distribución donde . $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$  $\Phi t=\sum _{i}w_{i}^{t}$  2. Observar el coste de la decisión . $estilo de visualización m^{t}}$  3. Establecer  $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 aprendiz 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 pesos . El proceso se repite. Después de T iteraciones, la hipótesis final es el resultado. La hipótesis combina los resultados de las T hipótesis débiles utilizando un voto de mayoría ponderada. ^[12] $w^{t}$ ${\estilo de visualización t}$ $estilo de visualización p^{t}}$ $estilo de visualización h_{t}}$ $estilo de visualización h_{t}}$ $estilo de visualización w^{t+1}}$ $estilo de visualización h_ {f}}$ $estilo de visualización h_ {f}}$

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

  $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 de forma aproximada[14]

Problema

Dada una matriz y , ¿existe una tal que ? $m\times n$ $A$ $b\in \mathbb {R} ^{n}$ $x$ $Ax\geq b$

  $\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 , 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. $\epsilon >0$ $x$ $Ax\geq b-\epsilon$ $x$

Solución

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

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

Si existe ax que satisface (1), entonces x satisface (2) para todo . La contrapositiva de esta afirmación también es verdadera. Supongamos que si el oráculo devuelve una solución factible para a , la solución que devuelve tiene un ancho acotado de . Por lo tanto, 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 realiza como máximo llamadas a un oráculo acotado en ancho para el problema (2). La contrapositiva también es verdadera. Las actualizaciones multiplicativas se aplican en el algoritmo en este caso. $p\in \Delta _{n}$ $p$ $x$ $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ $2\epsilon$ ${\frac {\ln(m)}{\epsilon ^{2}}}$

Otras aplicaciones

Teoría de juegos evolutiva: La actualización de pesos multiplicativos es la variante de 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 evolutivos . Converge al equilibrio de Nash cuando se aplica a un juego de congestión . ^[15]

Investigación de operaciones 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, se han encontrado de forma independiente el algoritmo de mayoría ponderada y sus versiones más complicadas. ^[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 cubiertas de conjuntos para hipergrafos con pequeña dimensión VC . ^[6]

Método de descenso de gradiente ^[1]

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

Marco de Plotkin, Shmoys y Tardos para el empaquetado y recubrimiento de LP ^[1]

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

Aproximación O (logn) para muchos problemas NP-hard ^[1]

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

Conjuntos de núcleo duro y el lema XOR ^[1]

Algoritmo de Hannan y pesos multiplicativos ^[1]

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

Referencias

^ abcdefghijklmnopqrs Arora, Sanjeev ; Hazan, Elad; Kale, 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 .
^ abcdefg "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 aleatoria en tiempo sublineal para juegos matriciales". Operations Research Letters . 18 (2): 53–58. doi :10.1016/0167-6377(95)00032-0.
^ ab 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.
^ ab 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.
^ ab Bronnimann, H.; Goodrich, MT (1995). "Coberturas de conjuntos casi óptimas en dimensión VC finita". Geometría discreta y computacional . 14 (4): 463–479. doi : 10.1007/BF02570718 .Versión preliminar en el 10º Simposio Anual de Geometría Computacional (SCG'94).
^ "Conferencia 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.
^ abc "Un kit de herramientas para el algoritmista". 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 de 2018 sobre Economía y Computación. ACM, 2018.
^ Foster, Dean P.; Vohra, Rakesh (1999). "El arrepentimiento en el problema de decisión en línea" (PDF) . Juegos y comportamiento económico . 29 (1–2): 7–35. doi :10.1006/game.1999.0740.
^ abc Yoav, Freund. Robert, E. Schapire (1996). TA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting* , pág. 55. Revista de ciencias de la computación y de sistemas.
^ "Aprendizaje en línea de los 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 al aprendizaje genérico sin arrepentimiento en juegos de congestión". Actas del cuadragésimo primer simposio anual de la ACM sobre teoría de la computación. ACM, 2009.

Enlaces externos

La teoría de juegos de la vida: un artículo de la revista Quanta que describe el uso del método en la biología evolutiva en un artículo de Erick Chastain, Adi Livnat, Christos Papadimitriou y Umesh Vazirani