HPC & Algorítmica & complejidad computacional. Recopilación de enlaces, febrero 2016.

Una serie de enlaces sobre los temas sobre los que tratamos en esta serie.

En uno desarrollo mi opinión sobre el reciente resultado en Go. Mi conclusión es que, aunque el avance es real, no es más que incremental, y por lo tanto no es más que otra operación de marketing de Google. Y aparentemente el mercado así lo ha entendido también: tras un subidón en bolsa, ha vuelto a bajar para estabilizarse en un determinado nivel.

Quizás los compradores que están evitando la caída libre de este valor estén apostando por otro próximo subidón en marzo, cuando Alphago se enfrente a Lee Sedol (serie de partidas previstas para entre 8 y 15 de marzo; ¿ hay intencionalidad cronológica ?: la presentación de resultados del primer trimestre / 1Q es en general, creo, en la primera quincena de abril; si ganan la partida, pueden tapar unos malos resultados; si pierden, tampoco se lo va a tener nadie en cuenta…).

Esto es obviamente absurdo a cualquier plazo que supere este mes de marzo del año corriente: gane o pierda, lo que está claro es que la empresa Google (grupo Alphabet) es manifiestamente incapaz o bien de incorporar los avances en IA para mejorar la tecnología de su negocio nuclear (el buscador) o bien cuando los incorpora lo empeora, de tal manera que su buscador falla más (falsos positivos, inflación artificial de resultados de búsqueda mediante búsquedas inversas automatizadas etc…) que una escopeta de feria.

Es cada vez más un buscador…¡¡ de ruido !!.

1. Big data & discrete math.

2.MASETH y AMSETH refutadas.

Son versiones más fuertes que NSETH, SETH o ETH. Por lo tanto podría darse el caso que MASETH y AMSETH sean falsas pero las otras verdaderas.

Pido disculpas al lector (en singular: no espero que lo lea más de uno, por no explicar las siglas…).

Relacionado. Complete Problems of Propositional Logic for the Exponential Hierarchy. 

Relacionado. Polynomial Depth, Highness and Lowness for E.

3. Redes de interconexión. Una entrevista al CTO de Cray.

4. ¿ El estancamiento en supercomputación ?

Disclaimer. Que enlace a un artículo de este autor no quiere decir ni que me interesen en general los temas sobre los que hable ni que esté de acuerdo con los contenidos de sus publicaciones. Es más cuando los leo, que no siempre, suelo estar en completo desacuerdo. Esto no es necesariamente aplicable a este caso. 

5. Grafos de Cayley y Grafos de Johnson.

As an application, we determine which Johnson graphs are Cayley graphs.

Nos hemos interesado por este tema hace poco.

6. Hamilton paths in Cayley graphs on Coxeter groups: I∗

Un artículo reciente sobre este tema, artículo que desconocía.

7. P = Ecuaciones diferenciales ordinarias.

8. E-commerce. Marketplaces y el problema de la clasificación de items. 

Una aplicación de machine learning al e-commerce.9. Uncomputability of the generalized capacity

What is the maximum rate at which we can send information over a channel? We define the capacity of a channel as the answer to this question. For an important family of channels the capacity is given by a simple optimization problem as proven in Shannon’s noisy coding theorem. Furthermore, for these channels, we have the Blahut-Arimoto algorithm that allows to efficiently solve the optimization problem and compute the capacity. In groundbreaking work, Verdu and Han proved a coding theorem for general channels. However, despite considerable effort, there is no equivalent to the Blahut-Arimoto algorithm for computing the generalized capacity. Here, we show that such an algorithm can not exist.

10. AI y optimización no convexa.

11. Isomorfismo de grafos.

12. AI (Alphago) vs. GO. ¿ Otra operación de marketing de Google ?. 

El artículo de Nature sobre este tema.

Se están leyendo muchas exageraciones sobre este tema. Algunos comentarios que pueden matizar el logro:

–Se estima que hay unos 600 millones de jugadores activos de ajedrez y unos 60 millones de Go. La mayoría de estos últimos de Korea, China y Japón.

Es decir, en primer lugar, por el volumen de aficionados el nivel competitivo del Ajedrez es mucho mayor que el del Go; y en segundo lugar el nivel del Go en Europa, si juzgamos por el número de jugadores en relación a Asia debe de ser bastante bajo.

Enlaces relevantes sobre el número de aficionados de Ajedrez y Go. 1 y 2.

–El jugador que se ha enfrentado a Alphago, aunque campeón de Europa, no era más que un profesional de 2 Dans (el nivel máximo pro es de 9 dans; también hay clasificación para amateurs), equivalente a un ELO de ajedrez de 2350, es decir nivel de Maestro en ajedrez.

Me pregunto desde cuando ganaban las máquinas a este nivel humano. La respuesta es clara, mucho antes de que Deep Blue ganase a Kasparov, en las famosas partidas de 1996/1997:

In 1981, Cray Blitz scored 5–0 in the Mississippi State Championship. In round 4 it defeated Joe Sentef (2262) to become the first computer to beat a master in tournament play and the first computer to gain a master rating (2258).

Mi opinión es que si no  se había llegado a este nivel es porque por la escasa visibilidad global (en términos de marketing) del Go frente al Ajedrez, los esfuerzos se habían centrado más en este último deporte.

Por lo tanto, aunque tiene su mérito por parte de la máquina, todos los que seguimos este tema estamos a la espera del prometido match contra Lee SedolAs of 2014 many people regard the Korean Lee Sedol as the world’s strongest player, as he has been dominating for several years in many events and especially in the Fujitsu Cup, which can be regarded as the top “international title”.

Sobre lo que no hay duda es que la máquina acabará ganando al hombre, también en Go, más temprano que tarde.

Nota al margen. Me pregunto si para humanos jugar bien al ajedrez otorga alguna ventaja para jugar bien al Go y viceversa. Estaría bien un enfrentamieto a dos juegos entre Magnus Carlssen y Lee Sedol. Fin de nota.

Relacionado. Un artículo de un experto que muestra escepticismo sobre el logro de Alphago. 

Relacionado. Francis the Emule se hace eco del logro.

Relacionado. Ha fallecido Marvin Minski, uno de los padres de la AI.

13.  Go vs. Ajedrez.

He estado leyendo sobre las reglas del Go, que desconocía. Pese a que el Go es bastante más simétrico que el ajedrez (todas las piezas son similares) y tienen reglas más sencillas, en realidad es más complejo.

No he encontrado nada muy interesante sobre comparativa de ambos juegos.  Algunos datos: para empezar el tamaño del tablero, parámetro importante para determinar la complejidad de un juego es muy diferente: 8×8 vs. 19×19. También varía el número de piezas (181+180 en Go vs. 16+16 en ajedrez). Y en mi (de momento desinformada) opinión la asimetría en la función de las piezas hace que el ajedrez sea más sencillo. Es más, y de nuevo reflejo en el comentario una opinión desinformada, Go todavía contiene algunas asimetrías (no todos los puntos del tablero son equivalentes) que lo hacen más sencillo. Me pregunto si el desenlace sería el mismo (ganan negras, ganan blancas; creo que hay reglas adicionales que hacen el empate imposible) sobre un tablero de tipo redondo o tórico. El concepto de usar diferentes tableros ya existe en ajedrez (cilíndrico). O esféricoVer también. La pregunta se puede hacer más general: ¿ es importante la “topología” o forma del tablero para la complejidad y para el desenlace ?.

Los analistas de ambos juegos delimitan fases similares: apertura, fase intermedia y final. Por mi parte, tras una breve reflexión no tengo ni idea cual sería una apertura, sino buena, al menos aceptable (¿ mejor posicionarse en el centro en los primeros movimientos que en los extremos (es decir esquinas o bordes del tablero) o es al contrario ?. Tampoco tengo la mínima intuición sobre cual sería una estrategia adecuada (¿ si se empieza  en el centro, intentar formar una cruz con extremos en las esquinas o en la mitad de los lados del tablero ?). Ni idea. Como siempre, hasta que se juega unas cuantas veces no tienes criterio…

A priori, la que me parece la mejor estrategia ahora mismo combinaría las ideas anteriores: alternar posicionamiento de piezas en el centro y en los extremos para formar cuatro cuadrados / triangulos (de los que la cruz serían algunos lados). De ser esta la óptima (seguramente nunca lo sabremos) aparentemente no afectaría demasiado la forma del tablero.

14. Siri y Google Now, una evaluación.

 

 

 

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: