Regístrate | Conectar
El Tamiz Libros Recursos Series Únete 9 Users Online
Skip to content

Teoría de juegos XX – Los tenistas (y II)




Vamos a buscar el fondo... (Image*After)

En el artículo anterior pusimos a Ana y a Alberto a jugar al tenis, y acabamos descubriendo que no tenían una estrategia pura que fuera dominante, así que propusimos una estrategia mixta, de modo que en vez de decidir sistemáticamente una de las opciones, lo hacían con una probabilidad p.

Contamos que John Nash había demostrado que todos los juegos tienen al menos un equilibrio de Nash en estrategias mixtas, pero que utilizó una demostración no constructiva, de modo que no proporcionaba un método para averiguar cuál era ese equilibrio. Después de que Cruzki nos advirtiera de que sí existe un método analítico, complicado, para hacerlo, he visto que algo tan básico como la Wikipedia efectivamente también lo dice (debí haberla consultado antes de escribir aquel párrafo, mea culpa). Pero como no conozco ese método, no puedo contároslo; si alguien se anima a hacer un artículo…

Por lo tanto, en este artículo veremos una aproximación para encontrar una estrategia usando el método del gradiente y veremos cómo interpretar ese método desde el punto de vista de la teoría de juegos.

Método del gradiente

Aunque probablemente algunos de nuestros lectores conozcan el método del gradiente, vamos a dedicarle unos párrafos por el bien de los que no lo conozcan.

El método del gradiente se puede utilizar para encontrar el máximo de una función cuando no se conoce dicha función o cuando aún conociéndola el método analítico es complicado. Ahí es nada.

A poco que el lector haya llegado hasta la secundaria, recordará que existe un método analítico para encontrar el máximo o los máximos de una función conocida: calculamos la derivada de la función, la igualamos a 0 y resolvemos la ecuación. Eso nos encuentra un punto que puede ser un máximo o un mínimo. Para averiguar si era un máximo o un mínimo, podíamos calcular la derivada de la derivada en ese punto y en función de su signo descubríamos si era un máximo o un mínimo.

El problema viene cuando no conocemos la función: no podemos calcular su derivada, de modo que malamente vamos a resolver la ecuación de igualarla a 0. O incluso si la conocemos, puede que no sea simplemente una parábola, sino una función muy compleja, y calcular su derivada y encontrar los ceros puede no ser trivial.

Lo que intenta el método del gradiente es aprovechar el conocimiento que nos da la derivada, aún sin conocer la función. Supongo que al lector que haya terminado la secundaria le habrán explicado que la derivada de una función indica el ritmo de crecimiento (si es positiva) o de decrecimiento (si es negativa), de una función. Pues bien, vamos a aprovechar esa idea.

Podemos fijarnos, por ejemplo, en la primera gráfica del dibujo de abajo. En el punto X=12, la función está decreciendo a un ritmo de 6, y por lo tanto decimos que la derivada de la función en X=12 vale -6.

Pero antes de seguir, un par de incisos:

  • Hemos dicho que el método del gradiente se utiliza para encontrar el máximo de una función. El lector astuto se dará cuenta rápidamente de por el mismo precio nos permitirá encontrar el mínimo, simplemente multiplicando por -1 en algún sitio… bien, pues en esta explicación vamos a buscar un mínimo, porque me simplifica alguna de las analogías, y por el camino indicaremos el método para encontrar tanto el mínimo como el máximo.
  • El método se llama “del gradiente” porque los matemáticos llaman gradiente a una derivada de más de una dimensión. En la explicación usaremos una función monodimensional, pero nada impide aplicar este método cuando la función es bidimensional o tridimensional o ndimensional.

El método del gradiente es un método iterativo. Empiezo en algún sitio al azar, y voy repitiendo pasos hasta que me voy acercando cada vez al máximo/mínimo que voy buscando. El procedimiento de cada paso es el siguiente:

1. Encontrar la derivada de la función en el punto en que estamos.

En nuestro ejemplo, hemos supuesto que el punto en que estamos es en X=12, y que su derivada es -6. ¿Y eso cómo lo sabemos? Buena pregunta. Porque si conocemos la fórmula de la función, no necesitamos andar haciendo zarandajas con el método del gradiente: ya estudiamos en el “cole” cómo averiguar el máximo/mínimo. Pero si no conocemos la fórmula de la función, malamente vamos a conocer su derivada.

Así que se suelen usar estimaciones. Por ejemplo, si llamo X (mayúscula) al punto actual y x (minúscula) al punto del paso anterior, puedo decir que  la derivada es:

Si habéis estudiado algo de derivadas, sabréis que eso no es mala aproximación; y si no las habéis estudiado, pues os fiáis de mí y listo.

En nuestro ejemplo, para X=12 hemos estimado de algún modo que D=-6.

2. Calcular la corrección que debo hacer en el siguiente salto.

La fórmula para hacer la corrección es distinta si estamos buscando un máximo o un mínimo (este es el signo que decíamos más arriba que había que cambiar para aplicar el método a un caso u otro):

En nuestro ejemplo, aplicamos la fórmula (ver la segunda gráfica) y nos sale que X’=15.

¿Por qué hemos elegido K=0,5? Buena pregunta. No lo sabemos. Hace falta ir aplicando el algoritmo con distintos valores de K e ir probando hasta que encontramos un K que hace que el algoritmo funcione. Sí, es así de artesanal. Como primera aproximación, si algún día tenéis que usar un algoritmo como este, se puede usar un K que sea un orden de magnitud menor que la relación entre los valores de x y f(x). Como veis, todo muy artesanal.

3. Repetir desde el paso 1 tantas veces como sea necesario.

¿Por qué funciona este método? Funciona porque en algún momento nos pasaremos del mínimo que estábamos buscando. En nuestro ejemplo eso ocurre en la segunda/tercera figura. En la tercera figura, en X=15, la derivada es 3, de modo que en el siguiente paso (figura 4) ¡retrocedemos!

La idea es que, si hemos escogido un valor de K adecuado, iremos dando saltitos hacia adelante y hacia atrás, y esos saltitos serán cada vez más pequeños y estarán alrededor del mínimo de la función.

¡Conseguido!

Se puede hacer una analogía con una canica y un cuenco (mira las imágenes que hay a continuación). Cuando empezamos, la canica está en X=12, pero en cuanto la soltamos, caerá rodando por la pendiente (eso es lo que representa la derivada). Aunque se va rozando (y eso es lo que representa multiplicar por K), subirá un poco por el otro lado de la pendiente. En algún momento se parará al otro lado y volverá a bajar y acabará quedando en el fondo del cuenco (o mejor dicho, bailando con vaivenes cada vez más infinitamente pequeños alrededor del fondo del cuenco).

Precisamente esta es la forma de averiguar si ya hemos terminado y hemos llegado al mínimo (o lo bastante cerca, al menos): vamos monitorizando continuamente la variación que se está produciendo entre paso y paso, y cuando esa variación es muy pequeña, es que ya estamos en el fondo.

¿Este método funciona siempre? Pues no, no siempre. Podemos imaginar un cuenco de arcilla deformado que tenga una hendidura en un lado, como el que se ve en la siguiente figura:

En este caso podría ocurrir que la bola se parase en la hendidura, en vez de seguir rodando hasta el fondo de verdad. Eso es lo que los matemáticos llaman un mínimo local por contraposición al mínimo “de verdad”[1] que representa el fondo del cuenco.

Lo que se suele hacer en estos casos es añadirle un poco de ruido al procedimiento. Si mantenemos la analogía del cuenco y la canica, es como si, además de dejar que la canica fuera rodando hasta alcanzar el fondo, sacudiéramos un poco el cuenco de vez en cuando.

Entonces las fórmulas del paso 2 serían:

Ese valor aleatorio debe poder ser positivo o negativo, y en realidad no importa mucho si sigue una distribución gaussiana o uniforme o triangular o… Lo que sí es importante es que su valor no sea ni muy pequeño (en cuyo caso no valdría para nada) ni muy grande (en cuyo caso la canica no pararía quieta ni siquiera cerca del fondo del cuenco). Una vez más: artesanal.

Hay una ventaja colateral del uso de este ruido: sabemos que en el mínimo la derivada es cero… pero también sabemos que no estamos usando la derivada, sino una estimación. Por lo tanto, podría ser que la estimación nos diera 0 (aunque el valor real no fuera 0) y el procedimiento se paralizara. Pues bien, este ruido nos garantiza que aunque nos equivoquemos en la estimación, antes o después seguiremos moviéndonos un pelín y no nos quedaremos atascados.

Debemos hacer hincapié, una vez más, en que para aplicar este método ni siquiera es necesario conocer la función, de modo que a veces también se llama a este método “de prueba y error”. Pruebo, me he equivocado, corrijo, vuelvo a probar, me he equivocado pero menos, bien, sigo corrigiendo, uf, ahora me he pasado, deshago la corrección y pruebo con un poco menos de corrección…

No obstante, este método no es mágico. Puede que la función no tenga un mínimo absoluto (imaginad un coseno, por ejemplo) o que no tenga mínimo (imaginad una recta) o que empecemos tan lejos de él que no seamos capaces de llegar hasta allí, o que elijamos K o rand malos.

Equilibrio de los tenistas

Apliquemos este método a las decisiones que deben tomar Ana y Alberto. Recordemos que, dado que estábamos usando estrategias mixtas, cada uno de ellos elegirá una opción o la otra con una determinada probabilidad.

Ahora tenemos dos variables: Pana y Palberto. Pana es la probabilidad con la que Ana elige posicionarse para recibir un drive (léase “p-ana”, no todo seguido, “pana”), mientras que Palberto es la probabilidad con que Alberto elige sacar hacia el drive (léase “p-alberto”). Y la magnitud medida es la esperanza del pago para esos Pana y Palberto.[2]

Hemos preparado una hoja excel para representar visualmente esta función bidimensional. La dejamos ahí colgada por si alguien quiere jugar con ella, pero lo interesante es que podemos ver la forma que tiene la función en la siguiente imagen:

Vemos que los casos extremos, en que Pana=0, Pana=1, Palberto=0 y Palberto=1 coinciden con las estrategias puras de la matriz de pagos. Por ejemplo, si Pana=0 (es decir, Ana nunca elige ir al drive) y Pana=1 (es decir, Alberto siempre elige tirar el drive), el pago esperado es 30, que es justo lo que decía la matriz para la combinación de estrategias puras Drive-Revés. Esto no es sorprendente, si no fuera así, es que hemos cometido un error.

Debemos darnos cuenta de que Alberto intenta maximizar el pago, busca el Palberto que le dé la máxima esperanza de pago, así que él usará la versión de la fórmula de corrección que tiene el signo positivo. En cambio Ana intenta minimizar el pago, busca el valor de Pana que dé la mínima esperanza de pago, así que usará la versión de la fórmula con el signo negativo.

Insistimos, una vez más, en que para que Ana y Alberto utilicen esta aproximación no necesitan conocer la función, ni la gráfica, ni nada, pueden usar la función como “caja negra”.

Así que elegimos K=0,0005, un nivel de ruido de 0,0001 y unos valores iniciales arbitrarios y realizamos 1000 pasos del algoritmo. Hemos hecho un programita de 70 líneas en Java (aunque tiene extensión .txt, porque si no WordPress no nos deja subirlo a El Cedazo) para hacer todo el proceso, y el resultado lo tenemos en el siguiente fichero de texto. No necesitas el programa, solo lo dejamos aquí por si alguien quiere trastear con él. Y respecto al fichero de resultado… tampoco hace falta, en realidad: vamos a comentar aquí los aspectos más interesantes.

En la primera línea vemos los valores iniciales, que son arbitrarios:

Estado inicial: Alberto P drive: 0,4000 (+0,1000); Ana P drive: 0,4000 (+0,1000);
  0: 27,500000; Alberto P drive: 0,5000 (-0,0025); Ana P drive: 0,5000 (+0,0025);
En cada paso vamos aplicando el algoritmo explicado arriba, buscando Ana el mínimo y Alberto el máximo:
  1: 27,549858; Alberto P drive: 0,4975 (-0,0101); Ana P drive: 0,5025 (-0,0099);
  2: 27,647302; Alberto P drive: 0,4874 (-0,0049); Ana P drive: 0,4926 (+0,0050);
  3: 27,748474; Alberto P drive: 0,4825 (-0,0101); Ana P drive: 0,4976 (-0,0100);
En cada paso imprimimos el número de paso, la probabilidad Palberto de que Alberto elija sacar al drive y la probabilidad Pana de que Ana se prepare para un drive. Entre paréntesis mostramos la corrección que vamos a hacer para el siguiente paso (es decir, en cuánto modificaremos respectivamente Palberto y Pana). Y a la izquierda vamos pintado la esperanza de pago de esa combinación de Pana y Palberto:
  i: esperanza; Alberto P drive: Palberto (Delta); Ana P drive: Pana (Delta);
Según vamos calculando pasos vamos viendo cómo Alberto sigue reduciendo su Palberto, porque parece que mejora cuando lo hace, mientras que Ana va haciendo bailar su Pana alrededor de un cierto equilibrio, porque no parece que ella gane o pierda al modificar eso.
  4: 27,834586; Alberto P drive: 0,4724 (-0,0043); Ana P drive: 0,4876 (+0,0042);
  5: 27,924570; Alberto P drive: 0,4681 (-0,0105); Ana P drive: 0,4918 (-0,0107);
  6: 28,000946; Alberto P drive: 0,4576 (-0,0036); Ana P drive: 0,4811 (+0,0035);
  7: 28,077405; Alberto P drive: 0,4540 (-0,0106); Ana P drive: 0,4847 (-0,0107);
  8: 28,144423; Alberto P drive: 0,4434 (-0,0033); Ana P drive: 0,4739 (+0,0030);
  9: 28,213113; Alberto P drive: 0,4402 (-0,0107); Ana P drive: 0,4770 (-0,0113);
 10: 28,264860; Alberto P drive: 0,4295 (-0,0024); Ana P drive: 0,4657 (+0,0023);
Al cabo de unas 80 iteraciones vemos que la situación comienza a estabilizarse alrededor de Palberto=0,60 y Pana=0,20, lo que nos da una esperanza de pago de unos 26.
 70: 25,908907; Alberto P drive: 0,5456 (+0,0157); Ana P drive: 0,1665 (-0,0015);
 71: 25,932192; Alberto P drive: 0,5613 (+0,0007); Ana P drive: 0,1650 (+0,0078);
 72: 25,948265; Alberto P drive: 0,5620 (+0,0107); Ana P drive: 0,1728 (-0,0011);
 73: 25,961400; Alberto P drive: 0,5727 (+0,0006); Ana P drive: 0,1717 (+0,0062);
 74: 25,970496; Alberto P drive: 0,5733 (+0,0074); Ana P drive: 0,1779 (-0,0008);
 75: 25,977898; Alberto P drive: 0,5807 (+0,0005); Ana P drive: 0,1771 (+0,0048);
 76: 25,982911; Alberto P drive: 0,5812 (+0,0056); Ana P drive: 0,1819 (-0,0006);
 77: 25,987540; Alberto P drive: 0,5867 (+0,0002); Ana P drive: 0,1812 (+0,0037);
 78: 25,990161; Alberto P drive: 0,5869 (+0,0055); Ana P drive: 0,1849 (-0,0006);
 79: 25,994119; Alberto P drive: 0,5925 (+0,0003); Ana P drive: 0,1844 (+0,0036);
 80: 25,995621; Alberto P drive: 0,5927 (+0,0028); Ana P drive: 0,1879 (-0,0001);
 81: 25,997265; Alberto P drive: 0,5955 (+0,0004); Ana P drive: 0,1878 (+0,0070);
 82: 25,998927; Alberto P drive: 0,5959 (+0,0024); Ana P drive: 0,1948 (-0,0002);
 83: 25,999542; Alberto P drive: 0,5983 (-0,0000); Ana P drive: 0,1946 (+0,0020);
 84: 25,999705; Alberto P drive: 0,5983 (-0,0022); Ana P drive: 0,1966 (-0,0000);
 85: 25,999330; Alberto P drive: 0,5960 (-0,0000); Ana P drive: 0,1966 (-0,0188);
En el paso 88-89 vemos un salto muy abrupto, probablemente debido a que el ruido que introdujimos ha hecho “saltar a la bolita” un montón. Vemos incluso que eso nos ha llevado en el paso 90 a probabilidades 0. Fijaos que 0,66-2,10 = -1,44, pero como esto debe ser una probabilidad está forzado a estar entre 0 y 1, así que nuestro algoritmo lo devuelve al 0 si se convierte en negativo y lo devuelve al 1 si crece más que eso[3].
 87: 26,066505; Alberto P drive: 0,6597 (+0,0005); Ana P drive: 0,1777 (+0,6558);
 88: 24,093026; Alberto P drive: 0,6602 (-2,1011); Ana P drive: 0,8335 (+0,0014);
 89: 45,047486; Alberto P drive: 0,0000 (-0,0157); Ana P drive: 0,8349 (-7,3437);
 90: 20,000000; Alberto P drive: 0,0000 (-0,0000); Ana P drive: 0,0000 (-0,0149);
 91: 20,000000; Alberto P drive: 0,0000 (-0,0000); Ana P drive: 0,0000 (+0,0002);
 92: 20,005450; Alberto P drive: 0,0000 (-0,0001); Ana P drive: 0,0002 (-0,0152);
 93: 20,000000; Alberto P drive: 0,0000 (-0,0002); Ana P drive: 0,0000 (-0,0151);
Poco a poco el algoritmo vuelve a su punto de equilibrio, hasta que alrededor del paso 130 vemos cómo las correcciones ya son ambas muy pequeñitas alrededor de 0, es decir estamos bailando alrededor del punto de equilibrio: Palberto=0,60 y Pana=0,20, con una esperanza de pago de 26.
125: 26,000060; Alberto P drive: 0,6012 (-0,0002); Ana P drive: 0,1990 (-0,0001);
126: 26,000056; Alberto P drive: 0,6010 (-0,0001); Ana P drive: 0,1989 (+0,0001);
127: 26,000049; Alberto P drive: 0,6010 (+0,0002); Ana P drive: 0,1990 (+0,0001);
128: 26,000054; Alberto P drive: 0,6012 (+0,0000); Ana P drive: 0,1991 (-0,0001);
129: 26,000062; Alberto P drive: 0,6012 (+0,0003); Ana P drive: 0,1990 (+0,0001);
130: 26,000070; Alberto P drive: 0,6015 (+0,0002); Ana P drive: 0,1991 (+0,0001);
131: 26,000070; Alberto P drive: 0,6017 (-0,0001); Ana P drive: 0,1992 (+0,0000);
132: 26,000065; Alberto P drive: 0,6016 (-0,0000); Ana P drive: 0,1992 (+0,0003);
133: 26,000040; Alberto P drive: 0,6016 (+0,0001); Ana P drive: 0,1995 (-0,0000);
Dejamos correr el procedimiento otros 900 pasos, por si acaso estábamos en un mínimo local y el ruido nos saca de él, llevándonos al mínimo global. Por ejemplo podemos ver que en los alrededores del paso 480 parece que el ruido le pega otro buen empujón a la bolita:
466: 26,000009; Alberto P drive: 0,6005 (+0,0001); Ana P drive: 0,1996 (+0,0001);
467: 26,000009; Alberto P drive: 0,6006 (-0,0001); Ana P drive: 0,1997 (-0,0000);
468: 26,000009; Alberto P drive: 0,6005 (-0,0000); Ana P drive: 0,1997 (-0,0001);
469: 26,000012; Alberto P drive: 0,6005 (-0,0122); Ana P drive: 0,1995 (+0,0000);
470: 25,999734; Alberto P drive: 0,5883 (-0,0001); Ana P drive: 0,1995 (+0,0146);
471: 26,008411; Alberto P drive: 0,5881 (-0,0368); Ana P drive: 0,2142 (-0,0002);
472: 26,033978; Alberto P drive: 0,5513 (-0,0006); Ana P drive: 0,2140 (+0,0589);
473: 26,179673; Alberto P drive: 0,5507 (-0,1144); Ana P drive: 0,2729 (-0,0013);
474: 26,585896; Alberto P drive: 0,4363 (-0,0018); Ana P drive: 0,2716 (+0,1570);
475: 27,891466; Alberto P drive: 0,4345 (-0,3642); Ana P drive: 0,4286 (-0,0041);
476: 31,945654; Alberto P drive: 0,0704 (-0,0055); Ana P drive: 0,4245 (+0,4924);
477: 45,184340; Alberto P drive: 0,0648 (-1,1955); Ana P drive: 0,9169 (-0,0134);
478: 47,106177; Alberto P drive: 0,0000 (-0,0148); Ana P drive: 0,9035 (+0,0718);
479: 49,259674; Alberto P drive: 0,0000 (+0,0002); Ana P drive: 0,9753 (-0,0150);
480: 48,802286; Alberto P drive: 0,0002 (-1,1508); Ana P drive: 0,9603 (-0,0152);
481: 48,355219; Alberto P drive: 0,0000 (+1,1247); Ana P drive: 0,9452 (-0,0148);
Pero rápidamente volvemos hacia el punto de equilibrio, de modo que en los alrededores del paso 500 ya estamos otra vez en el mismo sitio que antes.
497: 26,000031; Alberto P drive: 0,6005 (+0,0000); Ana P drive: 0,1988 (-0,0001);
498: 26,000033; Alberto P drive: 0,6005 (+0,0002); Ana P drive: 0,1988 (-0,0001);
499: 26,000047; Alberto P drive: 0,6007 (-0,0000); Ana P drive: 0,1987 (+0,0001);
500: 26,000040; Alberto P drive: 0,6007 (+0,0002); Ana P drive: 0,1988 (-0,0001);
501: 26,000057; Alberto P drive: 0,6009 (+0,0000); Ana P drive: 0,1988 (+0,0000);
502: 26,000058; Alberto P drive: 0,6010 (-0,0002); Ana P drive: 0,1988 (+0,0001);
503: 26,000040; Alberto P drive: 0,6007 (+0,0001); Ana P drive: 0,1989 (+0,0000);
504: 26,000044; Alberto P drive: 0,6008 (-0,0000); Ana P drive: 0,1989 (-0,0002);
505: 26,000047; Alberto P drive: 0,6008 (+0,0000); Ana P drive: 0,1988 (-0,0001);
¿Sabemos que ya hemos llegado al final del algoritmo? Pues no, no lo sabemos. Tenemos que intuirlo. A lo mejor estamos en un mínimo local y es necesario seguir dejándolo otros 1000 pasos para llegar al mínimo global. O a lo mejor 1000 pasos es muy poco y necesitamos 1 millón de pasos. O a lo mejor hemos elegido un K y/o un nivel de ruido tales que esto no funciona. O a lo mejor la función en realidad no tiene un máximo/mínimo y estamos haciendo el canelo. Como veis, algo muy artesanal, muy basado en la experiencia.

Pero bueno… algo habrá que hacer… supongamos que lo damos por bueno. Hemos encontrado que si Alberto saca al drive con probabilidad 0,60 (es decir, el 60% de las veces) y Ana se prepara para recibir un drive con probabilidad 0,20 (es decir el 20% de las veces), Alberto obtendrá un pago de 26 (que, recordemos, significaba que podría conseguir el ace con probabilidad del 26%). Cualquier intento por parte de uno de ellos de mejorar el pago esperado (subirlo, en el caso de Alberto; y bajarlo, en el caso de Ana) será contrarrestado por el otro, así que esa es la mejor situación en que pueden estar.

Aprendizaje y experiencia

Mi intención era dedicar el final de esta segunda parte a reestudiar el juego del ciempiés desde esta nueva perspectiva. Pero como llevamos ya 3000 palabras, vamos a dejarlo para el próximo artículo, y así le dedicamos el tiempo que se merece.

Así que podemos dedicar unos párrafos a relacionar el método del gradiente con el aprendizaje.

Hemos visto cómo algunos textos llamaban a este método “de prueba y error”, que es básicamente lo que hacen los animales (el hombre incluido, obviamente) cuando están aprendiendo: prueban, se equivocan, corrigen, vuelven a probar… una y otra vez… y si la corrección es astuta, acaban haciéndolo bien.

Imaginemos un bebé que está aprendiendo a tenerse quieto en pie. Si se va mucho hacia adelante, se cae de bruces. Sigue probando y cayéndose, hasta que un día se echa un poco menos hacia adelante, y se da cuenta (el cerebro es una máquina maravillosa) de que se cae más despacio, o que incluso no se cae. Así que la próxima vez se echa más hacia atrás… y claro, se cae de culo. Vaya, ha corregido demasiado. La próxima vez se echa para atrás también, pero no tanto. ¡Bien! Así poco a poco va ajustando y al cabo de un par de semanas es capaz de mantenerse erguido en pie.

La gracia es que para aprovechar este método no es necesario conocer la función de la cual queremos encontrar el máximo/mínimo: simplemente vamos probando. En el caso del bebé, no necesita conocer la Ley de la Gravitación, ni calcular su centro de masas, ni ningún otro de los conceptos que utilizaría un físico para explicar el fenómeno.

Este método está relacionado con otros mecanismos de aprendizaje de Inteligencia Artificial, como por ejemplo las redes neuronales. Es como si pusiéramos muchas neuronas artificiales, todas ellas aprendiendo con algo parecido a este método del gradiente, y luego resolviendo el problema entre todas. De este modo son capaces de atacar problemas mucho más complejos que los que podríamos abordar con este método aislado.

Por cierto, y aunque no esté relacionado con la teoría de juegos, este es el motivo por el que no se debe sobreproteger a los bebés: deben poder equivocarse, que les duela la caída, y que la próxima vez corrijan. Hombre, conviene procurar no hacer el aprendizaje al lado de una hoguera o un precipicio, pero, vaya, si se caen al suelo y lloran, así aprenden que no deben inclinarse tanto hacia adelante. Así lo hemos aprendido todos, y es mejor que te ocurra cuando tienes 1 año que cuando tienes 2. Y cuando ya somos más mayores, las decisiones serán más importantes (económicas, sociales, laborales…) y las consecuencias más graves: pues una vez más, hay que dejar que la gente (todos: bebes, niños, adolescentes y adultos) cometa sus errores y aprenda de ellos.

Una vez más: todo dentro de un orden. Encontrar ese punto que separa el “mejor que se equivoque y aprenda” de “se ha equivocado tanto que ha muerto o se ha arruinado la vida” es el que padres, profesores, jefes, gobernantes… tienen que encontrar. ¡Y es muy difícil!

  1. También llamado mínimo global cuando se quiere explicitar ese hecho. []
  2. Recuerdo que usamos esperanza en el sentido matemático: media. []
  3. Técnicamente se dice que “satura en 0″ y “satura en 1″ o que debe estar en el intervalo [0,1]. []

Sobre el autor:

J ( )

 

{ 10 } Comentarios

  1. Gravatar cruzki | 08/02/2011 at 08:40 | Permalink

    @J

    “El método del gradiente se utiliza para encontrar el máximo de una función cuando no se conoce dicha función. Ahí es nada.”

    Discrepo y además por varias razones.

    1º En general el método del gradiente se usa AUN cuando se conoce la función. En general, derivar es “fácil” pero tremendamente costoso. Pero el verdadero problema se encuentra luego que, como bien dices, ¡Hay que igualar a 0!

    Esto en general es factible de computar, pero terriblemente costoso (MUCHO MUCHO más costoso que derivar) pues significa resolver un sistema de ecuaciones NO lineales por regla general. De hecho, si supieramos hacerlo podríamos calcular directamente los equilibrios de Nash.

    Ahora bien, en el método del gradiente sólo es necesario resolver sistemas de ecuaciones lineales (que si sabemos resolver muy rápidamente) y por lo tanto hace el método del descenso del gradiente factible.

    2º En general, lo que uno puede suponer, es que conoce una forma de “evaluar” la función a optimizar. Esto no quiere decir que conozca su expresión analítica (y por lo tanto derivar), sino que simplemente es capaz de calcualr f(x) para algunos x. De hecho, sólo en casos contados de control óptmo y cosas por el estilo, uno no conoce la función a optimizar ni puede calcular valores. Entonces no te queda más remedio que trabajar con la derivada y rezando para tener un punto de la función original para poder usar alguna técnica de resolución de ecuaciones diferenciales.

    En este contexto el problema obviamente es que no tiene ni idea de cual es su derivada y por lo tanto no hay forma de buscar en la dirección del gradiente (que si no me equivoco has nombrado antes. La parte de las cuentas la he leido en diagonal :P ). En estos casos, que SON LA INMENSA MAYORÍA según mi experiencia (y estoy casi seguro que te lo puedo probar… incluso en un artículo por aquí. Pero para eso necesito avanzar un par de entradas más en la serie de la lógica a la relatividad… a ver si leo de una vez mi tesis para tener algo de tiempo libre…), lo que se hace es tirar de algoritmos de inteligencia artificial varios que “aprenden” de alguna forma la dirección del gradiente. Técnicas de estas hay a patadas. Supongo que sería interesante hablar de todas ellas porque tienen miga algunas.

    Y con esto ya termino, que te he soltado un ladrillo de los guapos.

    PD: por cierto, es cruzki (i latina)

  2. Gravatar J | 08/02/2011 at 10:14 | Permalink

    “El método del gradiente se utiliza para encontrar el máximo de una función cuando no se conoce dicha función. Ahí es nada.”

    Discrepo y además por varias razones.

    [...]

    Cierto. Corregido, para la posteridad.

    Esto no quiere decir que conozca su expresión analítica (y por lo tanto derivar), sino que simplemente es capaz de calcualr f(x) para algunos x.

    Correcto. Eso es lo que quería transmitir. Alberto saca al directo con una cierta Palberto (lo que tú llamas x) y al cabo de 8 ó 10 saques estima el pago medio (lo que tú llamas f(x)). Corrige, y al cabo de otros pocos saques vuelve a estimar el pago medio. ¿Mejora o empeora? Con eso estima la derivada. Y corrige. Y así una y otra vez. Lo mismo que el bebé que aprende a tenerse erguido, y lo mismo que haces cuando entrenas muchos sistemas de IA.

    tirar de algoritmos de inteligencia artificial varios que “aprenden” de alguna forma la dirección del gradiente. Técnicas de estas hay a patadas. Supongo que sería interesante hablar de todas ellas porque tienen miga algunas.

    Sí que lo sería, sí. ¿Has oído hablar de El Cedazo? Uy, perdón. Acaba la tesis de una vez y escríbenos algo.

  3. Gravatar Pedro | 09/02/2011 at 07:25 | Permalink

    Yo no quería decir nada a cruzki, pero por cierto, ¿conoces El Cedazo? Es una página comunitaria en la que… ooops. :P

  4. Gravatar Sorrillo | 09/02/2011 at 12:35 | Permalink

    Como era eso de “antes simplista que …” :-)

    Ahora en serio, esta serie me gusta mucho ya que me ha abierto la mente a una nueva forma de analizar los problemas.

    Me sorprendo a mi mismo aplicando los conceptos de esta serie a mi vida cotidiana, viendo que efectivamente muchos dilemas se simplifican aplicando técnicas de la teoría de juegos.

    Pero …

    Este es el primer articulo de la serie en la que me he saltado gran parte de éste por contener demasiados números, que aunque sirvan para solucionar el problema del ejemplo no creo que ayuden a entender “superficialmente” la teoría de juegos.

    Echo en falta un lenguaje más llano, más divulgativo y con menos conceptos matemáticos.

    No quiero desmerecer el esfuerzo y probablemente no sea posible seguir profundizando en la teoría de juegos sin entrar de lleno en los análisis matemáticos correspondientes, si es así lo comprendo y me alegro que esta serie tenga continuidad por ese camino para aquellos a quienes interese.

    En cualquier caso gracias no solo por el artículo sino por todo el trabajo que desinteresadamente que estáis haciendo todos los articulistas de esta web. Un trabajo fantástico.

  5. Gravatar J | 09/02/2011 at 01:36 | Permalink

    Sorrillo,

    no solo acepto el tirón de orejas, sino que ya era consciente de él. No te preocupes, que seguiremos profundizando sin necesidad de números (aunque desgraciadamente, algún artículo sí hay aún en que son necesarios algunos números).

  6. Gravatar cruzki | 09/02/2011 at 09:13 | Permalink

    @ Pedro y J

    Si ya lo se. Tengo desde hace 2 años y pico un correo de Pedro en el buzon esperando ser liquidado. Mi tesis se esta alargando más de lo deseado, pero ya solo queda que me den fecha para la lectura. A ver si finiquito otros papeleos y puedo preparar la presentacion y ya estaré MUCHO más libre física e intelectualmente para seguir escribiendo por aquí. Que tengo pendiente la serie de estadística, la de cosmología y la de IA :P bufff. \me se deja de pensar en estas cosas y se pone a la burocracia a ver si puede empezar de nuevo a escribir.

  7. Gravatar H | 25/09/2011 at 05:33 | Permalink

    Hice una cosa, llegue a 26, pero no entiendo bien :P Tenés la matriz de pagos, no?:

    ……………………………………….Ana se prepara para… ……………………………………….Drive (60%)…Revés(40%) Alberto saca…… Al drive (10%)….. 10……………… 30 ……………………Al revés (90%)… 50……………… 20

    Lo que hice fue plantear: ……………………………………….Ana se prepara para… ……………………………………….Drive (y)…….Revés(1-y) Alberto saca…… Al drive (x)……… 10……………… 30 ……………………Al revés (1-x)….. 50……………… 20

    Entonces calculé la esperanza como vos en los tenistas I:

    E (x,y) = 10xy + 30x(1-y) + 50(1-x)y + 20(1-x)(1-y)

    Con un poco de álgebra se llega a:

    E (x,y) = -50xy + 10x +30y + 20

    Entonces planteo las derivadas parciales, igualo a 0 (cero) y calculo el valor de la incógnita que queda:

    dE(x,y)/dx = -50y + 10 = 0 50y = 10

                                         y = 0.2
    

    dE(x,y)/dy= -50x + 30 = 0 50x = 30 x = 0.6

    Luego reemplazo esos valos de x y de y en la fórmula de la esperanza:

    E(0.6,0.2) = 100.60.2 + 500.40.2 + 300.60.8 + 200.40.8 = 26

    No sé, supongo que si la matriz es más complicada, con mas variables y todo, te terminaría quedando un sistema de ecuaciones (de n ecuaciones y n incógnitas), pero no veo porque no se podría resolver. Dudo que no haya habido alguien que llegó a esto antes que yo, asique asumo que me estoy equivocando :P , si alguien me lo aclara… Quizás es pura casualidad.

    Por cierto, genial la serie, empece a leerla ayer y ya llegue hasta aca… :P Saludos, H

  8. Gravatar H | 25/09/2011 at 05:34 | Permalink

    El comentario anterior perdió todo el formato, lo lamento :S

  9. Gravatar J | 26/09/2011 at 06:52 | Permalink

    H,

    el ejemplo que intentas resolver es muy sencillo, y por eso lo encuentras fácil analíticamente. De hecho, yo mismo hice en privado lo mismo que tú, para verificar que el resultado encontrado por el gradiente era correcto.

    Pero si es más complicado, puede no serte tan fácil (hace unos meses te hubiera dicho que era imposible, pero gracias a cruzki he descubierto que no es imposible, solo difícil).

    El comentario anterior perdió todo el formato, lo lamento :S

    Es por los retornos de carro. Entre un párrafo y el siguiente tienes que meter un doble retorno de carro (es decir, una línea en blanco).

  10. Gravatar Javier B | 14/11/2013 at 06:54 | Permalink

    Maravilloso. Si no estuviera en la biblioteca de la U, aplaudiría el articulo de píe. Gracias J por la serie, y a Pedro por el sitio, de corazón.

{ 1 } Trackback

  1. [...] 2011 Teoría de juegos XX – Los tenistas (y II), de Javier “J” Sedano, que pode lerse en El Cedazo. Toda a serie Teoría de juegos está publicada en forma de libro, [...]

Escribe un comentario

Tu dirección de correo no es mostrada. Los campos requeridos están marcados *

Al escribir un comentario aquí nos otorgas el permiso irrevocable de reproducir tus palabras y tu nombre/sitio web como atribución.