Si las técnicas de aprendizaje automático siguen mejorando, ¿cuál es el papel de los algoritmos en el futuro?

23

Veamos el futuro dentro de 30 años. Seamos optimistas y asumamos que las áreas relacionadas con el aprendizaje automático continúan desarrollándose tan rápido como lo que hemos visto en los últimos 10 años. Eso sería genial, pero ¿cuál sería el papel de los algoritmos tradicionales en un futuro así?

Aquí, mediante "algoritmos tradicionales", me refiero al proceso habitual que seguimos en TCS: formalizar un problema computacional bien definido , diseñar algoritmos para resolver el problema y probar garantías formales de rendimiento .

Ahora, ¿cuáles son las áreas de aplicación en las que debemos usar el diseño y análisis de algoritmos tradicionales también en el futuro, y es muy poco probable que cualquier avance del aprendizaje automático haga que los algoritmos tradicionales sean irrelevantes?

Al principio, esto puede parecer una pregunta tonta: ¡Por supuesto que tendremos que poder ordenar, buscar, indexar, etc. también en el futuro! Por supuesto, tendremos que ser capaces de hacer transformadas de Fourier de manera eficiente, multiplicar matrices grandes, encontrar caminos más cortos, resolver problemas de optimización lineal.

Pero, una vez más, una vez que comienzas a profundizar en las aplicaciones en las que tradicionalmente utilizamos los algoritmos que diseñamos, no está del todo claro que el diseño y análisis de algoritmos tradicionales sea la respuesta correcta a tales problemas: en aplicaciones relacionadas con la búsqueda , generalmente estamos interesados ​​en encontrar algo que coincida estrechamente con un ser humano en un sentido vago mal definido (por ejemplo, similitud semántica), no algo que sea óptimo en algún sentido matemático (por ejemplo, distancia mínima de edición). En aplicaciones relacionadas con la planificación de rutas, generalmente estamos interesados ​​en encontrar rutas que sean buenas en base a ejemplos (por ejemplo, otras personas lo prefieren), no rutas que sean óptimas en algún sentido matemático (por ejemplo, la distancia más corta o el precio más barato). Y una vez que tenga algún componente humano vago y mal definido en la imagen, podría ser el caso de que es mejor tratar de enseñarle a la computadora a producir buenas respuestas basadas en ejemplos, en lugar de intentar que aparezca un investigador de TCS con un problema computacional formal que podemos abordar mediante el diseño y análisis de algoritmos tradicionales.

Entonces, ¿cuáles son las áreas de aplicación (preferiblemente aplicaciones industriales reales y directas) en las que está absolutamente claro que lo que hemos estado haciendo en algoritmos en el pasado también será la forma correcta (y la única forma posible) de avanzar en el ¿futuro?

Los algoritmos que se usan como subrutinas en las técnicas de aprendizaje automático parecen ser un candidato obvio a prueba de futuro, pero esto depende en gran medida de la técnica particular de aprendizaje automático que usemos, y como hemos visto en los últimos diez años, esto podría cambiar rápidamente .

Jukka Suomela
fuente
2
Esto parece depender de si el problema corresponde naturalmente a un problema limpio que se puede aproximar en DTIME ( ) para algunos que no es ni demasiado grande ni demasiado pequeño, pero no se cree que sea aproximable en DTIME ( ). Si la tarea es bastante "fácil" desde la perspectiva de los algoritmos, pero requiere garantías en tiempo real, o es difícil, pero no está claro cómo extraer la dureza para resolverla a través de métodos estándar, entonces el modelo de El proceso subyacente ofrecido por el aprendizaje automático (y otras técnicas estadísticas) podría ser el enfoque más práctico. nccncε
András Salamon
44
Soy escéptico de la opinión de que los enfoques son exclusivos. ¿Tenemos razones para pensar que no será posible definir formalmente los problemas que resuelven los algoritmos de aprendizaje automático y construir buenos modelos teóricos que analicen su rendimiento? Esto podría requerir mejores modelos para algoritmos basados ​​en datos (que considero algoritmos con alta complejidad descriptiva), pero ¿es ese un obstáculo que no se puede superar?
Neal Young

Respuestas:

6

Esta es una pregunta que me ha estado atormentando recientemente, así que me alegra que la haya hecho.
Sin embargo, estoy menos interesado en clasificar las áreas de aplicación para las cuales el aprendizaje automático dominará el enfoque computacional que el impacto en el avance en el campo de los algoritmos (tradicionales). ¿En qué tipo de investigación de "algoritmos creados por humanos" todavía nos interesará, en 30 años? Es cierto que esta es la pregunta más difícil de responder en general, porque es la aplicación la que determina qué calidad de resultado se requiere.

Creo que los algoritmos de enumeración estarán entre los sobrevivientes. Seguirá siendo necesario probar todas las entradas a un chip o realizar una búsqueda exhaustiva. La atención específica del objeto, el diseño finamente ajustado requerido para generar cada instancia de objeto exactamente (o al menos) una vez; y la amplificación del tiempo de ejecución de cualquier esfuerzo desperdiciado (puede haber un número exponencial de instancias, en función de la descripción del objeto); estos factores me hacen escéptico de que un proceso de aprendizaje automatizado de propósito general pueda coincidir con un ingenioso, solución diseñada específicamente en esta área.

Gara Pruesse
fuente
4

El problema con las soluciones de aprendizaje automático es que no hay forma de saber si realmente calcularon lo que querías.

Espero que se hagan cargo de todos los dominios donde un resultado incorrecto no es catastrófico (es decir, en todas partes donde actualmente utilizamos heurística) o el resultado puede verificarse fácilmente (problemas de búsqueda para los que sabe que existe una solución (porque verificando "allí no hay solución "podría ser difícil)).

Para los dominios restantes, esperaría que los algoritmos se probaran formalmente (por ejemplo, usando Coq / Gallina) con frecuencia. Con suerte, el aprendizaje automático eventualmente hará que probar cosas en tales sistemas sea tan fácil como en papel (o incluso más fácil). Incluso podría llegar al punto en que los humanos solo escriban la especificación y el algoritmo y su prueba de corrección se encuentren utilizando el aprendizaje automático. (Tenga en cuenta que el algoritmo en sí mismo no utiliza el aprendizaje automático, pero se encontró con sus pruebas de corrección utilizando el aprendizaje automático)

Por lo tanto, podemos encontrarnos escribiendo solo asistentes de prueba, especificaciones de programas y algoritmos de aprendizaje automático.

xavierm02
fuente