The Independent Sentinel #08

Resolución de ecuaciones con Redes Neuronales, Prophet y el problema más importante de la computación

¡Hola!

Soy Javier Fuentes, CEO de Akoios, bienvenido de nuevo a The Independent Sentinel. Como ya sabes, en esta newsletter hablamos (o al menos lo intentamos) sobre Ciencia de Datos e Inteligencia Artificial de manera divulgativa y cercana.

Si aún no te has suscrito y quieres hacerlo, puedes hacerlo aquí:

¡Suscríbete ahora!

En esta edición hablaremos de resolución de ecuaciones con IA, de predicciones en series temporales y del problema del viajero: el problema que ilustra la conjetura más famosa (y aún no probada) de la ciencia de la computación: ¿P = NP?.

Traveling Salesman (1921) Stars: Roscoe 'Fatty' Arbuckle, Betty Ross Clarke, Frank Holland ~ Director: Joseph Henabery

¡Comenzamos! 💼


🎼  ¿Quieres banda sonora? ¡Dale al Play!


1. Inteligencia Artificial

Algoritmos 💻

Pese a la mala prensa de las grandes compañías tecnológicas entre amplios sectores de la población, personalmente siempre me ha parecido muy positivo el hecho de que contribuyan liberando como open-source algoritmos, modelos y plataformas. Hoy hablaremos de Prophet, un procedimiento de predicción para series temporales creado por Facebook.

La predicción es una de las aplicaciones más comunes de la Ciencia de Datos en el mundo empresarial, por ejemplo, para su uso en tareas como planificar capacidad, establecer objetivos o detectar anomalías. De modo particular en Facebook, el uso principal de este algoritmo ha sido el de realizar predicciones de negocio en entornos con tendencias no lineales, estacionalidad o efectos vacacionales.

Cualquier Científico de Datos que se haya tenido que pelear con series temporales, habrá podido comprobar en sus carnes lo complicado que es realizar buenas predicciones y la importancia de tener experiencia en este ámbito para poder obtener resultados razonables.

Prophet permite justamente predecir series temporales sin ser un experto en este campo y poder extraer información relevante y patrones de interés en situaciones complejas en las que:

  • Disponemos de observaciones horarias, diarias o semanales con un histórico de varios meses o, idealmente, al menos un año.

  • Tenemos estacionalidad a varios niveles (día de la semana o mes en el que se está).

  • Hay eventos vacacionales en intervalos irregulares (e.g. La Final de la Champions League).

  • Hay datos faltantes y outliers significativos.

  • Hay cambios de tendencia históricos (Por ejemplo, el lanzamiento de un nuevo producto)

  • Hay tendencias no lineales entre los datos.

Además, de esto, la parte diferencial de Prophet es que no es totalmente automático, sino que permite “ajustar” parámetros manualmente (lo que se conoce como “analyst in the loop”) para incorporar conocimiento humano de un especialista con conocimiento específico de dominio (e.g. especificidades de los ciclos de venta en España).

La siguiente figura ilustra este proceso semi-automático.

El proceso de predicción semi-automático propuesto por Prophet

Desde el punto de más técnico, Prophet usa un modelo de regresión aditiva con 4 componentes principales:

  • Un componente de detección de cambios en tendencias.

  • Un componente de estacionalidad anual.

  • Un componente de estacionalidad semanal.

  • Una lista de días festivos proporcionada por el usuario.

Si quieres más información sobre los fundamentos técnicos de Prophet puedes leer el paper asociado “Forecasting at scale”.

La forma más sencilla de empezar a usar Prophet es instalar el paquete desde iPyPI (Python) o CRAN (R). Puedes leer la guía introductoria o revisar la extensa documentación disponible.


👉 Usando tecnología Titan puedes poner en productivo fácilmente modelos que usen Prophet, basta con que importes los paquetes Python requeridos en tu Notebook y los uses normalmente. Escríbenos a info@akoios.com y te contamos cómo hacerlo. También puedes solicitar un acceso gratuito para probar nuestro producto aquí https://lnkd.in/gPz-2mJ

Casos de uso ⚙️

Seguimos casualmente con Facebook. Hace unas semanas, el departamento de de Inteligencia Artificial de facebook anunciaba un Caso de Uso inédito hasta el momento:

Un sistema de Inteligencia Artificial capaz de resolver ecuaciones matemáticas avanzadas usando razonamiento simbólico.

La idea es similar a un modelo NLP (Natural Language Processing) en el que las fórmulas se consideran como un idioma y, llegar a las soluciones, se asimila a un proceso de traducción (!).

Usando este enfoque y redes neuronales, han conseguido resolver problemas de integración y ecuaciones diferenciales de primer y segundo orden (¡qué bien nos hubiera venido esto en la universidad 🤓!).

Usando técnicas ya conocidas de Neural Machine Translation (NMT) y representando las ecuaciones en modo de árbol, han conseguido traducir los problemas en soluciones:

La fórmula ya expresada en forma de árbol, el formato idóneo para usarlo como entrada de un modelo de traducción.

Una vez entrenado, el modelo obtuvo mejores resultados (tanto en velocidad como en precisión) que los programas algebraicos clásicos de resolución de ecuaciones como Matlab y Mathematica.

Varios ejemplos de ecuaciones resueltas con este técnica que ni Matlab, Mathematica o yo mismo pudimos resolver.

Veremos si esto queda en anécdota o va más allá, en cualquier caso, el enfoque propuesto plantea un camino que bien merece le pena recorrer.

Puedes encontrar más información técnica aquí.

2. Historias 📔

El problema -aún no resuelto- más importante de la computación

En la edición anterior de la newsletter (TIS #7) hablábamos del clásico problema matemático de los 7 puentes de Königsberg.

A mediados del siglo XIX, dos matemáticos, William Rowan Hamilton y Thomas Kirkman formularon un problema similar pero mucho más conocido: El problema del vendedor ambulante.

Un vendedor ambulante de los de verdad. ¡Cómo para no optimizar el recorrido!

La idea de este problema, abreviado como TSP por sus siglas en inglés (Traveling Salesman Problem) tiene su origen en un problema similar al de los 7 puentes de Königsberg y parte un planteamiento equivalente:

Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen?

Estos dos matemáticos proponían el concepto de camino hamiltoniano (similar al camino euleriano). Mientras que el camino euleriano es un camino en el que cada arista (puente) se visita una sola vez, el camino hamiltoniano es un camino en el que cada vértice (ciudad) se visita una sola vez.

La resolución del problema pasa por encontrar el camino hamiltoniano más corto que sea posible entre las ciudades planteadas.

Para ilustrar el problema, Hamilton creó un juego al que llamo “Icosian Game” , un juego que tenía como objetivo encontrar un camino en los puntos de un dodecaedro. Este divertimento llegó a convertirse en un juego de mesa primigenio del que aún existen 3 unidades en el mundo:

El Juego Icosian. Fuente: Puzzle Museum

El objetivo del juego era recorrer los 20 puntos (ciudades) usando los caminos disponibles en el tablero.

La enunciación general del TSP llegó en 1930 por parte del matemático Karl Menger (hijo del famoso economista Carl Menger, fundador de la Escuela Austríaca de Economía) y se promocionó más adelante por parte de los matemáticos de Princeton, Hassler Whitney y Merrill Flood (uno de los creadores del conocido Dilema del Prisionero).

Lo interesante de este problema, aparte de ser más complejo aún que el problema de los puentes de Königsberg, es que es usado para probar y validar diversos métodos de optimización, como los conocidos algoritmos evolutivos o genéticos.

Aunque el problema pueda parecer sencillo, su complejidad crece según se van aumentando los puntos (ciudades) a visitar.

De forma general, para n ciudades, el número de rutas posibles es (n − 1)! = (n − 1) · (n − 2) · (n − 3) · · · 3 · 2 · 1

Por ejemplo, para 10 ciudades habría 9! = 362880 rutas o soluciones posibles (lo que puede parecer una complejidad razonable).

Si en cambio escogiésemos 100 ciudades tendríamos la friolera de 99! = 933262154439441526816992388562667004907159682643816214685929
638952175999932299156089414639761565182862536979208272237582
511852109168640000000000000000000000 (9.3326215443944E+155) rutas posibles

No se puede decir que el problema no tenga solución, ya que siempre es posible un acercamiento al mismo por fuerza bruta, probando todas las posibilidades y viendo cual minimiza la distancia. La clave radica en encontrar un buen algoritmo que nos permitan reducir la complejidad del método directo.

En los años 50 comenzó una carrera para resolver -usando distintos algoritmos- el problema con más ciudades (nodos) cada vez:

Avances en la resolución del TSP. Fuente.

La solución más compleja de la que se tiene constancia tuvo lugar en 2006, donde el matemático William J. Cook y su equipo resolvieron el TSP para 85900 puntos usando un algoritmo de su propia creación: El Concorde.

Por lo general, existen tres vías para resolver problemas de esta complejidad:

  • Algoritmos “exactos”, válidos para problemas de dimensiones pequeñas

  • Algoritmos heurísticos de aproximación (sub-óptimos) como, por ejemplo, los algoritmos evolutivos.

  • Encontrar casos específicos del problema (“subproblemas”)

Entre estos enfoques, los algoritmos evolutivos (considerados como una variante de la Inteligencia Artificial), han servido para obtener aproximaciones satisfactorias a soluciones del TSP. Entre estos algoritmos meta-heurísticos se encuentran los conocidos Algoritmos Genéticos o, por ejemplo, el menos conocido pero no menos interesante algoritmo de optimización mediante Colonia de Hormigas.

Optimización mediante Ant Colony. Fuente.

Como bien ilustra todo esto, lo aparentemente trivial puede esconder problemas muy interesantes y de complejidad extrema.

Tan en así que, la resolución del problema del viajante, implicaría a su vez la resolución del problema más importante de la computación, la conjetura “P vs NP”.

Este es uno de los 7 problemas del milenio y existe una una recompensa de $1,000,000 por parte del Instituto Matemático Clay para quién logre resolverlo.

¿Qué son los problemas P y NP?

  • De manera muy sencilla, podemos decir que los problemas de clase “P” son fácilmente resolubles (Algoritmos de programación lineal, ecuaciones simples) para los ordenadores en un tiempo razonable de acuerdo a su complejidad.

  • Por su parte, los problemas NP (e.g. TSP) son aquellos dónde la solución podría ser muy difícil de encontrar (e.g. que tardase millones de años en calcularse) pero que, una vez encontrada, es fácil comprobar su validez. En el ejemplo del viajante, puede ser muy difícil calcular la ruta pero siempre es relativamente sencillo comprobar si la solución calculada es correcta o no.

En base a esto, la resolución del problema pasa por descubrir si:

P (problemas con soluciones fáciles de encontrar) son iguales a NP (problemas con soluciones fáciles de comprobar)

Como explican en este artículo del MIT Technology Review:

Si P es igual a NP, todos los problemas NP contendrían un atajo oculto, lo que permitiría que los ordenadores encontrasen rápidamente soluciones perfectas. Pero si P no es igual a NP, entonces no existen dichos atajos, y la potencia de resolución de problemas de los ordenadores seguirá siendo fundamental y permanentemente limitada.

En definitiva, saber si realmente los problemas P son como los NP, nos permitiría saber a ciencia cierta qué tipos de problemas pueden ser resueltos por los ordenadores y cuáles no.

Todo parece indicar que P ≠ NP, pero todavía nadie ha logrado demostrarlo. Como comenta Scott Aaronson, un investigador de complejidad en el Laboratorio de Inteligencia Artificial del MIT:

"Hay buenas razones por las que muy pocas personas creen que P es igual a NP. Si así fuera, estaríamos viviendo en un universo muy distinto y probablemente ya nos habríamos dado cuenta".

¡Gracias como siempre por leer hasta aquí! Feliz fin de semana.


Eventos 🎫

👉 El próximo Jueves día 5 participaremos en los 101 Panel Tech Days de Panel Sistemas. Si quieres venir a conocer de primera mano cómo resolvemos el problema de la puesta en producción de modelos, puedes apuntarte aquí.


¿Te gusta The Independent Sentinel? Ayúdanos a que nos conozca más gente interesada en IA, Ciencia de Datos y Computación. ¡Basta con que compartas nuestra URL!

¿Te has perdido alguna edición? Puedes leer todas aquí:

👉 Si quieres conocer mejor cómo funciona nuestro producto Titan, no te pierdas nuestra serie de tutoriales publicados en Medium.

👉 Si quieres, puedes solicitar un acceso gratuito para probar nuestro producto aquí https://lnkd.in/gPz-2mJ