Este artículo es mi recuento gratuito de Learnability puede ser indecidible, Shai Ben-David, et al.

Recientemente en Habré, el artículo El aprendizaje automático se enfrentó a un problema matemático no resuelto , que es una traducción del artículo de Shay Ben-David en el artículo de Nature News del mismo nombre. Sin embargo, debido a la naturaleza del tema y la brevedad de la revisión original, me quedó completamente incomprensible lo que había en el artículo. Al conocer a Shai Ben-David como el autor del excelente libro "Comprender el aprendizaje automático: de la teoría a los algoritmos", me interesé en este tema, me familiaricé con este trabajo e intenté esbozar los puntos principales aquí.

Debo decir de inmediato que el artículo es bastante complicado y, tal vez, me perdí algunos puntos importantes, pero mi revisión será más completa que la que ya está en Habré.

Algunas palabras sobre el aprendizaje PAC en general

Lo primero que me confundió en una revisión de Nature News fue que el problema de aprendizaje en sí mismo se presentaba como algo completamente nuevo. De hecho, este es un problema largo y relativamente bien estudiado.

Existe una teoría del aprendizaje probablemente casi correcto (Probablemente un aprendizaje aproximadamente correcto, PAC ).

Esta teoría se remonta a los años 80 del siglo pasado. Sin embargo, no proporciona ningún indicador medible que refleje la capacidad de aprendizaje de un algoritmo. Pero esa respuesta la da la teoría del aprendizaje estadístico ( teoría VC ) ya desarrollada por V. Vapnik y A. Chervonenkis. Esta teoría se basa en un indicador numérico de dimensión VC. La dimensión VC es una estimación combinatoria del tamaño máximo de datos que el algoritmo puede dividir en dos partes de todas las formas posibles.

El teorema principal de la teoría VC, en una de las posibles formulaciones, prueba el hecho de que si la dimensión VC del algoritmo es finita, entonces está entrenada en PAC. Además, la dimensión VC es un indicador de la rapidez con que al aumentar el tamaño de la muestra empírica el valor del riesgo empírico converge con el valor del riesgo promedio.

Por lo tanto, el problema del aprendizaje automático de los algoritmos de aprendizaje automático per se está relativamente bien estudiado y tiene una base matemática rigurosa.

¿Cuál es, entonces, el tema de un artículo en Nature?

Los autores escriben que el problema con la teoría PAC, basada en varias dimensiones de dimensión, es que no es universal.

Los autores dan un ejemplo interesante de un problema cuya declaración en sí está diseñada para que el éxito no pueda formularse como PAC-learning. Los autores escriben:

Imagine que tenemos un sitio de Internet en el que mostramos anuncios. Defina X como el conjunto de todos los visitantes potenciales a este sitio. La publicidad se selecciona de un determinado grupo de publicidad. Condicionalmente, suponga que cada anuncio del grupo está dirigido a alguna categoría de usuarios: anuncios deportivos para fanáticos de los deportes, etc. La tarea es colocar exactamente el tipo de publicidad que sea más relevante para los visitantes del sitio .

El problema aquí es que no sabemos realmente quién visitará el sitio en el futuro. Para resumir, la declaración de tal problema se puede describir de la siguiente manera:

Tener un conjunto de características $$$F$sobre el set $$$X$encontrar tal función $$$F_ {best}$para que sea métrica sobre la distribución desconocida $$$P$Fue máximo. Además, es necesario encontrar dicha función basada en un conjunto limitado de cantidades independientes idénticamente distribuidas de $$$P$

Entrenamiento EMX

Shai Ben-David y sus colegas presentan un nuevo concepto: E estimula el M a X imum (aprendizaje EMX), que solo proporciona criterios de aprendizaje para tales problemas de maximización:

Para conjunto de características $$$F$, conjuntos de entrada $$$X$y distribución desconocida $$$P$para cualquier número $$$d = d (\ epsilon, \ delta)$funcion $$$G (s)$es $$$(\ epsilon, \ delta)$-Entrenado en EMX para cualquier distribución $$$P$:

$$

$$Pr_ {S \ sim P ^ d} [\ mathbb {E} _P (G (S)) \ leq \ sup_ {h \ in F} \ mathbb {E} (h) - \ epsilon] \ leq \ delta$$

Esta definición de aprendizaje es indudablemente más general que el concepto de PAC.

Entonces, ¿dónde tiene que ver el continuo y el "problema no resuelto de las matemáticas"?

Los autores prueban el siguiente teorema:
Rotación de EMX $$$F$con respecto $$$P$independiente del sistema de axioma Zermelo - Frenkel con el axioma de elección (en adelante ZFC).

En otras palabras, usando axiomas matemáticos estándar, en el caso general no podemos probar la posibilidad de encontrar una solución al problema de aprendizaje de EMX o probar la imposibilidad de encontrar esta solución.

Los autores también muestran que para el caso general del aprendizaje EMX, no existe un análogo de la dimensión VC (o cualquier otra dimensión) que sería finito en el caso de la mensurabilidad EMX, y viceversa, la capacidad de aprendizaje EMX se derivaría de su finitud. Más estrictamente lo tienen formulado de la siguiente manera:

Hay una constante $$$c$que si asumimos la consistencia de ZFC, entonces no existe tal propiedad $$$A (X, Y)$que para algunos$$ $ en línea $ m, M> c $ en línea $ para cualquier $$$X$y conjunto de características $$$F$se realizaría:

• Si $$$A (X, Y)$cierto entonces $$$(1/3, 1/3)$complejidad del aprendizaje EMX $$$F$no excede M;
• Si $$$A (X, Y)$falso entonces $$$(1/3, 1/3)$complejidad del aprendizaje EMX $$$F$al menos m;

Por el contrario, esto es cierto para, por ejemplo, la dimensión VC, ya que para $$$A (X, Y)$igual $$$VC \ leq d$será esencialmente una formulación del teorema principal de la teoría VC.

Conclusión

El mensaje del trabajo está, de hecho, poco relacionado con los problemas prácticos del aprendizaje automático, o incluso con las cuestiones teóricas de la teoría del aprendizaje estadístico. Me pareció que hay dos pensamientos principales en el trabajo:

• Una hermosa conexión entre el aprendizaje EMX y los teoremas de Gödel;
• La imposibilidad fundamental de crear una caracterización universal del aprendizaje (como la dimensión VC) para la clase general de problemas de aprendizaje automático.

Al mismo tiempo, personalmente no me gusta por completo el encabezado "El aprendizaje automático ha encontrado un problema matemático no resuelto", utilizado en la traducción de una revisión de este artículo . En mi opinión, este es un clickbait absoluto, además, simplemente no corresponde a la realidad. El trabajo original no significa que alguien se topó con algo. El aprendizaje automático y la teoría PAC funcionaron y continúan funcionando. Se señala que la teoría PAC no se puede generalizar a algunas afirmaciones particulares del problema del aprendizaje automático, se encuentran conexiones interesantes con los teoremas de Gödel, pero ni una palabra sobre algún problema no resuelto que el aprendizaje automático ha encontrado.