Hay problemas de aprendizaje que no son decidibles

Por Francisco R. Villatoro, el 19 enero, 2019. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Nature • Noticias • Science ✎ 4

Calcular, entender y aprender son conceptos intuitivos, pero su formulación matemática no lo es. Gracias a ella se pueden aplicar a problemas sobre conjuntos transfinitos. Se publica en Nature Machine Intelligence un sencillo problema de aprendizaje que es equivalente a la hipótesis del continuo de Cantor. Así, este problema se puede aprender si se acepta la hipótesis del continuo, pero no se puede aprender si no se acepta dicha hipótesis. Más aún este problema de aprendizaje es indecidible usando los axiomas de Zermelo–Fraenkel, junto al axioma de elección, la axiomática ZFC estándar en teoría de conjuntos. Un bello teorema metamatemático en la teoría del aprendizaje automático sin ningún efecto sobre sus aplicaciones prácticas en inteligencia artificial.

Se ha usado el formalismo PAC de Vapnik–Chervonenkis (VC) para el aprendizaje, donde PAC se refiere a problemas de aprendizaje que probablemente tienen una aproximación a la respuesta correcta (probably approximately correct learning). El teorema fundamental del aprendizaje PAC  es la existencia de una dimensión VC, que permite obtener cotas inferiores y superiores a la complejidad computacional estadística (el número de ejemplos necesarios durante el aprendizaje) para un problema binario de clasificación (decidir si los ejemplos son un tipo o de otro tipo). El nuevo problema de aprendizaje PAC no tiene dimensión VC, salvo que se acepte la hipótesis del continuo.

Un resultado metamatemático en la teoría matemática del aprendizaje que ha recibido cierto eco en los medios gracias a su publicación en el primer número de la nueva revista Nature Machine Intelligence. Los que hayan entendido algo de lo que he escrito, podrán disfrutar de todos los detalles en Shai Ben-David, Pavel Hrubeš, …, Amir Yehudayoff, «Learnability can be undecidable,» Nature Machine Intelligence 1: 44–48 (07 Jan 2019), doi: 10.1038/s42256-018-0002-3. Quien prefiera versiones muy digeridas de este resultado pueden consultar Davide Castelvecchi, «Machine learning leads mathematicians to unsolvable problem,» Nature 565: 277 (08 Jan 2019), doi: 10.1038/d41586-019-00083-3, y Lev Reyzin, «Unprovability comes to machine learning,» Nature 565: 166-167 (07 Jan 2019), doi: 10.1038/d41586-019-00012-4.

Por cierto, los que prefieran un resultado similar basado en el teorema de la parada para máquinas de Turing disfrutarán de Sairaam Venkatraman, S Balasubramanian, R Raghunatha Sarma, «PAC-learning is Undecidable,» arXiv:1808.06324 [cs.LG]. Como es obvio, sin el eco mediático que ofrecen las noticias publicadas en Nature, este artículo ha pasado desapercibido para los medios. En dicho artículo se demuestra que no existe ninguna máquina de Turing capaz de decidir si un problema de aprendizaje PAC se puede resolver o no. Tampoco tiene ninguna utilidad práctica en inteligencia artificial.

Supongo que sabes que la hipótesis del continuo afirma que entre el cardinal de los números enteros (0, léase alef-sub-cero) y el cardinal de todos sus subconjuntos (20), su conjunto potencia, no existe ningún otro cardinal. Si se asume el axioma de elección, la hipótesis del continuo implica que 1 = 20. Se denomina hipótesis del continuo porque el cardinal de los números reales, el continuo, es 20. Por supuesto, Cantor creía que la hipótesis del continuo se podía probar usando la axiomática de conjuntos ZFC. Hilbert lo incluyó en su lista de 23 problemas matemáticos para el siglo XX. Gödel (1940) demostró que es una hipótesis consistente, no puede probarse que es falsa, y Cohen (1963) probó que es una hipótesis independiente, no puede probarse que es cierta. Para esto último desarrolló el método de forcing, que se usa en el nuevo trabajo. Por tanto, la hipótesis del continuo puede añadirse como cierta o como falsa a la axiomática ZFC bifurcando la matemática en dos matemáticas diferentes pero igualmente consistentes.

Ben-David y sus colegas consideran el problema de aprendizaje llamado estimación del máximo (EMX). En términos prácticos imagina el conjunto X de todos los visitantes de una web con publicidad. Para cada anuncio A, sea FA ⊆ X el conjunto de usuarios interesados. Sin conocer qué usuarios visitan la web, el problema EMX consiste en determinar qué anuncio maximiza el número de usuarios interesados en dicho anuncio. En general, dada una familia F de subconjuntos de X, el problema EMX consiste en encontrar el subconjunto en F cuya medida probabilística es máxima con respecto a una distribución de probabilidad P desconocida.

Por supuesto, en el artículo se considera un conjunto X continuo y no numerable, con cardinal 20, el intervalo de números reales [0,1]. La familia de conjuntos F* son todos los conjuntos finitos del intervalo [0,1] y la distribución de probabilidad P* está en la clase de todos las distribuciones sobre [0,1] con soporte finito. El teorema demostrado por Ben-David y sus colegas afirma que el problema de aprendizaje EMX de F* con respecto a P* es independiente de los axiomas ZFC. Para ello se usa la técnica de forcing de Cohen. Se construyen dos modelos (o universos) para dicho problema, uno con la hipótesis del continuo donde el problema de aprendizaje EMX de F* tiene solución porque el cardinal de [0,1] es 1  y otro sin la hipótesis del continuo donde el cardinal de [0,1] es mayor que k para todo entero k donde no tiene solución.

No me molestaré en mostrar los detalles de la demostración. Lo cierto es que es muy sencilla para quien esté acostumbrado al lenguaje de la teoría de modelos. Pero será casi imposible de entender para quien no haya disfrutado nunca de una demostración de este tipo. Los interesados pueden disfrutarla en el artículo original que es de acceso gratuito (open access). Lo único que me limitaré a comentar es que la indecidibilidad de este problema de aprendizaje tiene su origen en la indecibilidad de la existencia de la función de aprendizaje (la distribución de probabilidad en el problema EMX), no en el algoritmo de aprendizaje; por tanto, no impone ninguna restricción a la aplicación práctica del algoritmo de aprendizaje en problemas prácticos y/o conceptuales. Recuerda que, en general, la existencia de funciones sobre dominios infinitos (y transfinitos) es un asunto sutil, por no llamarlo salvajemente contraintuitivo.

El otro artículo, de Venkatraman y sus colegas, considera la máquina de Turing no determinista que implementa el algoritmo de aprendizaje (L) que resuelve el problema de aprendizaje PAC sobre una familia de funciones hipotéticas (H) dentro de una clase de funciones (C). Aplicada al aprendizaje del problema del problema de la parada (aceptar o rechazar la hipótesis de que una máquina de Turing para), se reduce este problema de aprendizaje PAC al problema de la parada de máquinas de Turing. Como este último es indecidible, el primero también lo es. Quizás esta demostración sea mucho más fácil de entender para los lectores de este blog (al menos para los que sean informáticos y recuerden la demostración del teorema de la parada de Turing de sus estudios universitarios). Aún así, remito al artículo (solo tiene 5 páginas) a todos los interesantes en los detalles (son más sencillos de lo que parece a priori).

En resumen, que no se confundan quienes piensen que estos resultados están relacionados con el problema de la consciencia, o con los límites de la inteligencia artificial. Ni el encéfalo humano, ni los ordenadores presentes y futuros resuelven problemas similares a los considerados en estos artículos teóricos. Ni la consciencia, ni la superinteligencia requieren la solución de problemas con conjuntos de datos de cardinalidad transfinita. A pesar de ello, me gusta que problemas como la hipótesis del continuo y la indecidibilidad aparezcan en este blog y en algunos medios.



4 Comentarios

  1. Si admitimos que nuestro aprendizaje está basado en la fuerza (intensidad) de las conexiones sinápticas y una red neuronal puede simular estas intensidades de conexión (pesos), el problema se reduce a crear una red neuronal con la misma complejidad que un cerebro humano, entonces, ambas pensarán igual, y tendrán la capacidad de descubrir los mismos problemas de indecibilidad.

  2. Pero la demostración de Venkatraman y compañía sobre PAC-learning sí parece tener impacto práctico, ¿no? porque tal como ocurre con todas las demostraciones de esta linea, nos dicen que nada nos impide hacer un algoritmo que resuelva este tipo de aprendizaje tal cual han definido, pero simpre podrá aprovecharse nuestro algoritmo para crear un problema de aprendizaje no abordable por nuestro propio algoritmo.

  3. Me interesa la AI y sus aplicaciones, pero soy un absoluto ignorante en matemáticas (mi culpa, mi desidia, mi presunción), este artículo, e insisto en que desconozco la teoría, lo he leído de principio a fin, no he podido dejarlo como otros de la misma temática, no se porque me ha resultado fascinante, si por las matemáticas teóricas o por la explicación del profesor Francis. Dicen que la matemáticas son bellas y hasta ahora no lo había comprendido, tb dicen que un buen profesor ayuda a interesarse por una materia, esto ya lo había experimentado en mi carrera.
    Agradezco al Prof. Francis el darme a conocer esta bonita y paradójica cuestión matemática..

Deja un comentario